Merge lp:~pedronis/ubuntu-push/gethosts into lp:ubuntu-push

[Samuele Pedroni]

introduce package gethosts implementing finding hosts to connect to for delivery of notifications

introduce package gethosts implementing finding hosts to connect to for delivery of notifications

vendorize an impl of murmur3

[lp:~pedronis/ubuntu-push/gethosts]

91. By Samuele Pedroni on 2014-03-24

newline

92. By Samuele Pedroni on 2014-03-24

remove .gitignore

[John Lenton (chipaca)]

review: Approve

=== added directory 'client/gethosts'
=== added file 'client/gethosts/gethost.go'
--- client/gethosts/gethost.go	1970-01-01 00:00:00 +0000
+++ client/gethosts/gethost.go	2014-03-24 15:37:31 +0000
@@ -0,0 +1,92 @@
+/*
+ Copyright 2013-2014 Canonical Ltd.
+
+ This program is free software: you can redistribute it and/or modify it
+ under the terms of the GNU General Public License version 3, as published
+ by the Free Software Foundation.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranties of
+ MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR
+ PURPOSE.  See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along
+ with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+// Package gethosts implements finding hosts to connect to for delivery of notifications.
+package gethosts
+
+import (
+	"encoding/json"
+	"errors"
+	"fmt"
+	"io/ioutil"
+	"net/http"
+	"time"
+
+	"launchpad.net/ubuntu-push/external/murmur3"
+	http13 "launchpad.net/ubuntu-push/http13client"
+)
+
+// GetHost implements finding hosts to connect to consulting a remote endpoint providing a hash of the device identifier.
+type GetHost struct {
+	hash        string
+	endpointUrl string
+	cli         *http13.Client
+}
+
+// New makes a GetHost.
+func New(deviceId, endpointUrl string, timeout time.Duration) *GetHost {
+	hash := murmur3.Sum64([]byte(deviceId))
+	return &GetHost{
+		hash:        fmt.Sprintf("%x", hash),
+		endpointUrl: endpointUrl,
+		cli: &http13.Client{
+			Transport: &http13.Transport{TLSHandshakeTimeout: timeout},
+			Timeout:   timeout,
+		},
+	}
+}
+
+type expected struct {
+	Hosts []string
+}
+
+var (
+	ErrRequest   = errors.New("request was not accepted")
+	ErrInternal  = errors.New("remote had an internal error")
+	ErrTemporary = errors.New("remote had a temporary error")
+)
+
+// Get gets a list of hosts consulting the endpoint.
+func (gh *GetHost) Get() ([]string, error) {
+	resp, err := gh.cli.Get(gh.endpointUrl + "?h=" + gh.hash)
+	if err != nil {
+		return nil, err
+	}
+	defer resp.Body.Close()
+	if resp.StatusCode != http.StatusOK {
+		switch {
+		case resp.StatusCode == http.StatusInternalServerError:
+			return nil, ErrInternal
+		case resp.StatusCode > http.StatusInternalServerError:
+			return nil, ErrTemporary
+		default:
+			return nil, ErrRequest
+		}
+	}
+	body, err := ioutil.ReadAll(resp.Body)
+	if err != nil {
+		return nil, err
+	}
+	var parsed expected
+	err = json.Unmarshal(body, &parsed)
+	if err != nil {
+		return nil, ErrTemporary
+	}
+	if len(parsed.Hosts) == 0 {
+		return nil, ErrTemporary
+	}
+	return parsed.Hosts, nil
+}

=== added file 'client/gethosts/gethost_test.go'
--- client/gethosts/gethost_test.go	1970-01-01 00:00:00 +0000
+++ client/gethosts/gethost_test.go	2014-03-24 15:37:31 +0000
@@ -0,0 +1,102 @@
+/*
+ Copyright 2013-2014 Canonical Ltd.
+
+ This program is free software: you can redistribute it and/or modify it
+ under the terms of the GNU General Public License version 3, as published
+ by the Free Software Foundation.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranties of
+ MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR
+ PURPOSE.  See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along
+ with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+package gethosts
+
+import (
+	"encoding/json"
+	"fmt"
+	"net/http"
+	"net/http/httptest"
+	"testing"
+	"time"
+
+	. "launchpad.net/gocheck"
+
+	"launchpad.net/ubuntu-push/external/murmur3"
+)
+
+func TestGetHosts(t *testing.T) { TestingT(t) }
+
+type getHostsSuite struct{}
+
+var _ = Suite(&getHostsSuite{})
+
+func (s *getHostsSuite) TestNew(c *C) {
+	gh := New("foobar", "http://where/hosts", 10*time.Second)
+	c.Check(gh.hash, Equals, fmt.Sprintf("%x", murmur3.Sum64([]byte("foobar"))))
+	c.Check(gh.endpointUrl, Equals, "http://where/hosts")
+}
+
+func (s *getHostsSuite) TestGet(c *C) {
+	ts := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
+		x := r.FormValue("h")
+		b, err := json.Marshal(map[string]interface{}{
+			"hosts": []string{"http://" + x},
+		})
+		if err != nil {
+			panic(err)
+		}
+		w.Header().Set("Content-Type", "application/json")
+		w.Write(b)
+	}))
+	defer ts.Close()
+	gh := New("foobar", ts.URL, 1*time.Second)
+	res, err := gh.Get()
+	c.Assert(err, IsNil)
+	c.Check(res, DeepEquals, []string{"http://c1130408a700afe0"})
+}
+
+func (s *getHostsSuite) TestGetTimeout(c *C) {
+	finish := make(chan bool, 1)
+	ts := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
+		<-finish
+	}))
+	defer func() {
+		time.Sleep(100 * time.Millisecond) // work around -race issue
+		ts.Close()
+	}()
+	defer func() {
+		finish <- true
+	}()
+	gh := New("foobar", ts.URL, 1*time.Second)
+	_, err := gh.Get()
+	c.Check(err, ErrorMatches, ".*closed.*")
+}
+
+func (s *getHostsSuite) TestGetErrorScenarios(c *C) {
+	status := make(chan int, 1)
+	body := make(chan string, 1)
+	ts := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
+		w.WriteHeader(<-status)
+		fmt.Fprintf(w, "%s", <-body)
+	}))
+	defer ts.Close()
+	gh := New("foobar", ts.URL, 1*time.Second)
+	scenario := func(st int, bdy string, expectedErr error) {
+		status <- st
+		body <- bdy
+		_, err := gh.Get()
+		c.Check(err, Equals, expectedErr)
+	}
+
+	scenario(http.StatusBadRequest, "", ErrRequest)
+	scenario(http.StatusInternalServerError, "", ErrInternal)
+	scenario(http.StatusGatewayTimeout, "", ErrTemporary)
+
+	scenario(http.StatusOK, "{", ErrTemporary)
+	scenario(http.StatusOK, "{}", ErrTemporary)
+}

=== modified file 'debian/copyright'
--- debian/copyright	2014-03-21 11:21:30 +0000
+++ debian/copyright	2014-03-24 15:37:31 +0000
@@ -10,6 +10,10 @@
 Copyright: 2009-2013 The Go Authors
 License: BSD-3-clause
 
+Files: external/murmur3/*
+Copyright: 2013 Sébastien Paolacci
+License: BSD-3-clause
+
 License: GPL-3.0
  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by

=== added directory 'external'
=== added file 'external/README'
--- external/README	1970-01-01 00:00:00 +0000
+++ external/README	2014-03-24 15:37:31 +0000
@@ -0,0 +1,3 @@
+Directly included vendorized small packages.
+
+* murmor3 comes from import at lp:~ubuntu-push-hackers/ubuntu-push/murmur at revno 10

=== added directory 'external/murmur3'
=== added file 'external/murmur3/LICENSE'
--- external/murmur3/LICENSE	1970-01-01 00:00:00 +0000
+++ external/murmur3/LICENSE	2014-03-24 15:37:31 +0000
@@ -0,0 +1,24 @@
+Copyright 2013, Sébastien Paolacci.
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+    * Redistributions in binary form must reproduce the above copyright
+      notice, this list of conditions and the following disclaimer in the
+      documentation and/or other materials provided with the distribution.
+    * Neither the name of the library nor the
+      names of its contributors may be used to endorse or promote products
+      derived from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
+DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

=== added file 'external/murmur3/README.md'
--- external/murmur3/README.md	1970-01-01 00:00:00 +0000
+++ external/murmur3/README.md	2014-03-24 15:37:31 +0000
@@ -0,0 +1,49 @@
+murmur3
+=======
+
+Native Go implementation of Austin Appleby's third MurmurHash revision (aka
+MurmurHash3).
+
+Reference algorithm has been slightly hacked as to support the streaming mode
+required by Go's standard [Hash interface](http://golang.org/pkg/hash/#Hash).
+
+
+Benchmarks
+----------
+
+Go tip as of 2013-03-11 (i.e almost go1.1), core i7 @ 3.4 Ghz. All runs
+include hasher instanciation and sequence finalization.
+
+<pre>
+
+Benchmark32_1       200000000         8.4 ns/op       119.39 MB/s
+Benchmark32_2       200000000         9.5 ns/op       211.69 MB/s
+Benchmark32_4       500000000         7.9 ns/op       506.24 MB/s
+Benchmark32_8       200000000         9.4 ns/op       853.40 MB/s
+Benchmark32_16      100000000        12.1 ns/op      1324.19 MB/s
+Benchmark32_32      100000000        18.2 ns/op      1760.81 MB/s
+Benchmark32_64       50000000        31.2 ns/op      2051.59 MB/s
+Benchmark32_128      50000000        58.7 ns/op      2180.34 MB/s
+Benchmark32_256      20000000       116.0 ns/op      2194.85 MB/s
+Benchmark32_512      10000000       227.0 ns/op      2247.43 MB/s
+Benchmark32_1024      5000000       449.0 ns/op      2276.88 MB/s
+Benchmark32_2048      2000000       894.0 ns/op      2289.87 MB/s
+Benchmark32_4096      1000000      1792.0 ns/op      2284.64 MB/s
+Benchmark32_8192       500000      3559.0 ns/op      2301.33 MB/s
+
+Benchmark128_1       50000000        33.2 ns/op        30.15 MB/s
+Benchmark128_2       50000000        33.3 ns/op        59.99 MB/s
+Benchmark128_4       50000000        35.4 ns/op       112.88 MB/s
+Benchmark128_8       50000000        36.6 ns/op       218.30 MB/s
+Benchmark128_16      50000000        35.5 ns/op       450.86 MB/s
+Benchmark128_32      50000000        35.3 ns/op       905.84 MB/s
+Benchmark128_64      50000000        44.3 ns/op      1443.76 MB/s
+Benchmark128_128     50000000        58.2 ns/op      2201.02 MB/s
+Benchmark128_256     20000000        85.3 ns/op      2999.88 MB/s
+Benchmark128_512     10000000       142.0 ns/op      3592.97 MB/s
+Benchmark128_1024    10000000       258.0 ns/op      3963.74 MB/s
+Benchmark128_2048     5000000       494.0 ns/op      4144.65 MB/s
+Benchmark128_4096     2000000       955.0 ns/op      4285.80 MB/s
+Benchmark128_8192     1000000      1884.0 ns/op      4347.12 MB/s
+
+</pre>

=== added file 'external/murmur3/murmur.go'
--- external/murmur3/murmur.go	1970-01-01 00:00:00 +0000
+++ external/murmur3/murmur.go	2014-03-24 15:37:31 +0000
@@ -0,0 +1,65 @@
+// Copyright 2013, Sébastien Paolacci. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+/*
+Native (and fast) implementation of Austin Appleby's MurmurHash3.
+
+Package murmur3 implements Austin Appleby's non-cryptographic MurmurHash3.
+
+ Reference implementation:
+    http://code.google.com/p/smhasher/wiki/MurmurHash3
+
+ History, characteristics and (legacy) perfs:
+    https://sites.google.com/site/murmurhash/
+    https://sites.google.com/site/murmurhash/statistics
+*/
+package murmur3
+
+type bmixer interface {
+	bmix(p []byte) (tail []byte)
+	Size() (n int)
+	reset()
+}
+
+type digest struct {
+	clen int      // Digested input cumulative length.
+	tail []byte   // 0 to Size()-1 bytes view of `buf'.
+	buf  [16]byte // Expected (but not required) to be Size() large.
+	bmixer
+}
+
+func (d *digest) BlockSize() int { return 1 }
+
+func (d *digest) Write(p []byte) (n int, err error) {
+	n = len(p)
+	d.clen += n
+
+	if len(d.tail) > 0 {
+		// Stick back pending bytes.
+		nfree := d.Size() - len(d.tail) // nfree ∈ [1, d.Size()-1].
+		if nfree < len(p) {
+			// One full block can be formed.
+			block := append(d.tail, p[:nfree]...)
+			p = p[nfree:]
+			_ = d.bmix(block) // No tail.
+		} else {
+			// Tail's buf is large enough to prevent reallocs.
+			p = append(d.tail, p...)
+		}
+	}
+
+	d.tail = d.bmix(p)
+
+	// Keep own copy of the 0 to Size()-1 pending bytes.
+	nn := copy(d.buf[:], d.tail)
+	d.tail = d.buf[:nn]
+
+	return n, nil
+}
+
+func (d *digest) Reset() {
+	d.clen = 0
+	d.tail = nil
+	d.bmixer.reset()
+}

=== added file 'external/murmur3/murmur128.go'
--- external/murmur3/murmur128.go	1970-01-01 00:00:00 +0000
+++ external/murmur3/murmur128.go	2014-03-24 15:37:31 +0000
@@ -0,0 +1,189 @@
+package murmur3
+
+import (
+	//"encoding/binary"
+	"hash"
+	"unsafe"
+)
+
+const (
+	c1_128 = 0x87c37b91114253d5
+	c2_128 = 0x4cf5ad432745937f
+)
+
+// Make sure interfaces are correctly implemented.
+var (
+	_ hash.Hash = new(digest128)
+	_ Hash128   = new(digest128)
+	_ bmixer    = new(digest128)
+)
+
+// Hack: the standard api doesn't define any Hash128 interface.
+type Hash128 interface {
+	hash.Hash
+	Sum128() (uint64, uint64)
+}
+
+// digest128 represents a partial evaluation of a 128 bites hash.
+type digest128 struct {
+	digest
+	h1 uint64 // Unfinalized running hash part 1.
+	h2 uint64 // Unfinalized running hash part 2.
+}
+
+func New128() Hash128 {
+	d := new(digest128)
+	d.bmixer = d
+	d.Reset()
+	return d
+}
+
+func (d *digest128) Size() int { return 16 }
+
+func (d *digest128) reset() { d.h1, d.h2 = 1, 1 }
+
+func (d *digest128) Sum(b []byte) []byte {
+	h1, h2 := d.h1, d.h2
+	return append(b,
+		byte(h1>>56), byte(h1>>48), byte(h1>>40), byte(h1>>32),
+		byte(h1>>24), byte(h1>>16), byte(h1>>8), byte(h1),
+
+		byte(h2>>56), byte(h2>>48), byte(h2>>40), byte(h2>>32),
+		byte(h2>>24), byte(h2>>16), byte(h2>>8), byte(h2),
+	)
+}
+
+func (d *digest128) bmix(p []byte) (tail []byte) {
+	h1, h2 := d.h1, d.h2
+
+	nblocks := len(p) / 16
+	for i := 0; i < nblocks; i++ {
+		t := (*[2]uint64)(unsafe.Pointer(&p[i*16]))
+		k1, k2 := t[0], t[1]
+
+		k1 *= c1_128
+		k1 = (k1 << 31) | (k1 >> 33) // rotl64(k1, 31)
+		k1 *= c2_128
+		h1 ^= k1
+
+		h1 = (h1 << 27) | (h1 >> 37) // rotl64(h1, 27)
+		h1 += h2
+		h1 = h1*5 + 0x52dce729
+
+		k2 *= c2_128
+		k2 = (k2 << 33) | (k2 >> 31) // rotl64(k2, 33)
+		k2 *= c1_128
+		h2 ^= k2
+
+		h2 = (h2 << 31) | (h2 >> 33) // rotl64(h2, 31)
+		h2 += h1
+		h2 = h2*5 + 0x38495ab5
+	}
+	d.h1, d.h2 = h1, h2
+	return p[nblocks*d.Size():]
+}
+
+func (d *digest128) Sum128() (h1, h2 uint64) {
+
+	h1, h2 = d.h1, d.h2
+
+	var k1, k2 uint64
+	switch len(d.tail) & 15 {
+	case 15:
+		k2 ^= uint64(d.tail[14]) << 48
+		fallthrough
+	case 14:
+		k2 ^= uint64(d.tail[13]) << 40
+		fallthrough
+	case 13:
+		k2 ^= uint64(d.tail[12]) << 32
+		fallthrough
+	case 12:
+		k2 ^= uint64(d.tail[11]) << 24
+		fallthrough
+	case 11:
+		k2 ^= uint64(d.tail[10]) << 16
+		fallthrough
+	case 10:
+		k2 ^= uint64(d.tail[9]) << 8
+		fallthrough
+	case 9:
+		k2 ^= uint64(d.tail[8]) << 0
+
+		k2 *= c2_128
+		k2 = (k2 << 33) | (k2 >> 31) // rotl64(k2, 33)
+		k2 *= c1_128
+		h2 ^= k2
+
+		fallthrough
+
+	case 8:
+		k1 ^= uint64(d.tail[7]) << 56
+		fallthrough
+	case 7:
+		k1 ^= uint64(d.tail[6]) << 48
+		fallthrough
+	case 6:
+		k1 ^= uint64(d.tail[5]) << 40
+		fallthrough
+	case 5:
+		k1 ^= uint64(d.tail[4]) << 32
+		fallthrough
+	case 4:
+		k1 ^= uint64(d.tail[3]) << 24
+		fallthrough
+	case 3:
+		k1 ^= uint64(d.tail[2]) << 16
+		fallthrough
+	case 2:
+		k1 ^= uint64(d.tail[1]) << 8
+		fallthrough
+	case 1:
+		k1 ^= uint64(d.tail[0]) << 0
+		k1 *= c1_128
+		k1 = (k1 << 31) | (k1 >> 33) // rotl64(k1, 31)
+		k1 *= c2_128
+		h1 ^= k1
+	}
+
+	h1 ^= uint64(d.clen)
+	h2 ^= uint64(d.clen)
+
+	h1 += h2
+	h2 += h1
+
+	h1 = fmix64(h1)
+	h2 = fmix64(h2)
+
+	h1 += h2
+	h2 += h1
+
+	return h1, h2
+}
+
+func fmix64(k uint64) uint64 {
+	k ^= k >> 33
+	k *= 0xff51afd7ed558ccd
+	k ^= k >> 33
+	k *= 0xc4ceb9fe1a85ec53
+	k ^= k >> 33
+	return k
+}
+
+/*
+func rotl64(x uint64, r byte) uint64 {
+	return (x << r) | (x >> (64 - r))
+}
+*/
+
+// Sum128 returns the MurmurHash3 sum of data. It is equivalent to the
+// following sequence (without the extra burden and the extra allocation):
+//     hasher := New128()
+//     hasher.Write(data)
+//     return hasher.Sum128()
+func Sum128(data []byte) (h1 uint64, h2 uint64) {
+	d := &digest128{h1: 1, h2: 1}
+	d.tail = d.bmix(data)
+	d.clen = len(data)
+	return d.Sum128()
+}

=== added file 'external/murmur3/murmur32.go'
--- external/murmur3/murmur32.go	1970-01-01 00:00:00 +0000
+++ external/murmur3/murmur32.go	2014-03-24 15:37:31 +0000
@@ -0,0 +1,154 @@
+package murmur3
+
+// http://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/hash/Murmur3_32HashFunction.java
+
+import (
+	"hash"
+	"unsafe"
+)
+
+// Make sure interfaces are correctly implemented.
+var (
+	_ hash.Hash   = new(digest32)
+	_ hash.Hash32 = new(digest32)
+)
+
+const (
+	c1_32 uint32 = 0xcc9e2d51
+	c2_32 uint32 = 0x1b873593
+)
+
+// digest32 represents a partial evaluation of a 32 bites hash.
+type digest32 struct {
+	digest
+	h1 uint32 // Unfinalized running hash.
+}
+
+func New32() hash.Hash32 {
+	d := new(digest32)
+	d.bmixer = d
+	d.Reset()
+	return d
+}
+
+func (d *digest32) Size() int { return 4 }
+
+func (d *digest32) reset() { d.h1 = 1 }
+
+func (d *digest32) Sum(b []byte) []byte {
+	h := d.h1
+	return append(b, byte(h>>24), byte(h>>16), byte(h>>8), byte(h))
+}
+
+// Digest as many blocks as possible.
+func (d *digest32) bmix(p []byte) (tail []byte) {
+	h1 := d.h1
+
+	nblocks := len(p) / 4
+	for i := 0; i < nblocks; i++ {
+		k1 := *(*uint32)(unsafe.Pointer(&p[i*4]))
+
+		k1 *= c1_32
+		k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
+		k1 *= c2_32
+
+		h1 ^= k1
+		h1 = (h1 << 13) | (h1 >> 19) // rotl32(h1, 13)
+		h1 = h1*5 + 0xe6546b64
+	}
+	d.h1 = h1
+	return p[nblocks*d.Size():]
+}
+
+func (d *digest32) Sum32() (h1 uint32) {
+
+	h1 = d.h1
+
+	var k1 uint32
+	switch len(d.tail) & 3 {
+	case 3:
+		k1 ^= uint32(d.tail[2]) << 16
+		fallthrough
+	case 2:
+		k1 ^= uint32(d.tail[1]) << 8
+		fallthrough
+	case 1:
+		k1 ^= uint32(d.tail[0])
+		k1 *= c1_32
+		k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
+		k1 *= c2_32
+		h1 ^= k1
+	}
+
+	h1 ^= uint32(d.clen)
+
+	h1 ^= h1 >> 16
+	h1 *= 0x85ebca6b
+	h1 ^= h1 >> 13
+	h1 *= 0xc2b2ae35
+	h1 ^= h1 >> 16
+
+	return h1
+}
+
+/*
+func rotl32(x uint32, r byte) uint32 {
+	return (x << r) | (x >> (32 - r))
+}
+*/
+
+// Sum32 returns the MurmurHash3 sum of data. It is equivalent to the
+// following sequence (without the extra burden and the extra allocation):
+//     hasher := New32()
+//     hasher.Write(data)
+//     return hasher.Sum32()
+func Sum32(data []byte) uint32 {
+
+	var h1 uint32 = 1
+
+	nblocks := len(data) / 4
+	var p uintptr
+	if len(data) > 0 {
+		p = uintptr(unsafe.Pointer(&data[0]))
+	}
+	p1 := p + uintptr(4*nblocks)
+	for ; p < p1; p += 4 {
+		k1 := *(*uint32)(unsafe.Pointer(p))
+
+		k1 *= c1_32
+		k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
+		k1 *= c2_32
+
+		h1 ^= k1
+		h1 = (h1 << 13) | (h1 >> 19) // rotl32(h1, 13)
+		h1 = h1*5 + 0xe6546b64
+	}
+
+	tail := data[nblocks*4:]
+
+	var k1 uint32
+	switch len(tail) & 3 {
+	case 3:
+		k1 ^= uint32(tail[2]) << 16
+		fallthrough
+	case 2:
+		k1 ^= uint32(tail[1]) << 8
+		fallthrough
+	case 1:
+		k1 ^= uint32(tail[0])
+		k1 *= c1_32
+		k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
+		k1 *= c2_32
+		h1 ^= k1
+	}
+
+	h1 ^= uint32(len(data))
+
+	h1 ^= h1 >> 16
+	h1 *= 0x85ebca6b
+	h1 ^= h1 >> 13
+	h1 *= 0xc2b2ae35
+	h1 ^= h1 >> 16
+
+	return h1
+}

=== added file 'external/murmur3/murmur64.go'
--- external/murmur3/murmur64.go	1970-01-01 00:00:00 +0000
+++ external/murmur3/murmur64.go	2014-03-24 15:37:31 +0000
@@ -0,0 +1,45 @@
+package murmur3
+
+import (
+	"hash"
+)
+
+// Make sure interfaces are correctly implemented.
+var (
+	_ hash.Hash   = new(digest64)
+	_ hash.Hash64 = new(digest64)
+	_ bmixer      = new(digest64)
+)
+
+// digest64 is half a digest128.
+type digest64 digest128
+
+func New64() hash.Hash64 {
+	d := (*digest64)(New128().(*digest128))
+	return d
+}
+
+func (d *digest64) Sum(b []byte) []byte {
+	h1 := d.h1
+	return append(b,
+		byte(h1>>56), byte(h1>>48), byte(h1>>40), byte(h1>>32),
+		byte(h1>>24), byte(h1>>16), byte(h1>>8), byte(h1))
+}
+
+func (d *digest64) Sum64() uint64 {
+	h1, _ := (*digest128)(d).Sum128()
+	return h1
+}
+
+// Sum64 returns the MurmurHash3 sum of data. It is equivalent to the
+// following sequence (without the extra burden and the extra allocation):
+//     hasher := New64()
+//     hasher.Write(data)
+//     return hasher.Sum64()
+func Sum64(data []byte) uint64 {
+	d := &digest128{h1: 1, h2: 1}
+	d.tail = d.bmix(data)
+	d.clen = len(data)
+	h1, _ := d.Sum128()
+	return h1
+}

=== added file 'external/murmur3/murmur_test.go'
--- external/murmur3/murmur_test.go	1970-01-01 00:00:00 +0000
+++ external/murmur3/murmur_test.go	2014-03-24 15:37:31 +0000
@@ -0,0 +1,225 @@
+package murmur3
+
+import (
+	"hash"
+	"testing"
+)
+
+var data = []struct {
+	h32   uint32
+	h64_1 uint64
+	h64_2 uint64
+	s     string
+}{
+	{0x514e28b7, 0x4610abe56eff5cb5, 0x51622daa78f83583, ""},
+	{0xbb4abcad, 0xa78ddff5adae8d10, 0x128900ef20900135, "hello"},
+	{0x6f5cb2e9, 0x8b95f808840725c6, 0x1597ed5422bd493b, "hello, world"},
+	{0xf50e1f30, 0x2a929de9c8f97b2f, 0x56a41d99af43a2db, "19 Jan 2038 at 3:14:07 AM"},
+	{0x846f6a36, 0xfb3325171f9744da, 0xaaf8b92a5f722952, "The quick brown fox jumps over the lazy dog."},
+}
+
+func TestRef(t *testing.T) {
+	for _, elem := range data {
+
+		var h32 hash.Hash32 = New32()
+		h32.Write([]byte(elem.s))
+		if v := h32.Sum32(); v != elem.h32 {
+			t.Errorf("'%s': 0x%x (want 0x%x)", elem.s, v, elem.h32)
+		}
+
+		if v := Sum32([]byte(elem.s)); v != elem.h32 {
+			t.Errorf("'%s': 0x%x (want 0x%x)", elem.s, v, elem.h32)
+		}
+
+		var h64 hash.Hash64 = New64()
+		h64.Write([]byte(elem.s))
+		if v := h64.Sum64(); v != elem.h64_1 {
+			t.Errorf("'%s': 0x%x (want 0x%x)", elem.s, v, elem.h64_1)
+		}
+
+		var h128 Hash128 = New128()
+		h128.Write([]byte(elem.s))
+		if v1, v2 := h128.Sum128(); v1 != elem.h64_1 || v2 != elem.h64_2 {
+			t.Errorf("'%s': 0x%x-0x%x (want 0x%x-0x%x)", elem.s, v1, v2, elem.h64_1, elem.h64_2)
+		}
+
+		if v1, v2 := Sum128([]byte(elem.s)); v1 != elem.h64_1 || v2 != elem.h64_2 {
+			t.Errorf("'%s': 0x%x-0x%x (want 0x%x-0x%x)", elem.s, v1, v2, elem.h64_1, elem.h64_2)
+		}
+	}
+}
+
+func TestIncremental(t *testing.T) {
+	for _, elem := range data {
+		h32 := New32()
+		h128 := New128()
+		for i, j, k := 0, 0, len(elem.s); i < k; i = j {
+			j = 2*i + 3
+			if j > k {
+				j = k
+			}
+			s := elem.s[i:j]
+			print(s + "|")
+			h32.Write([]byte(s))
+			h128.Write([]byte(s))
+		}
+		println()
+		if v := h32.Sum32(); v != elem.h32 {
+			t.Errorf("'%s': 0x%x (want 0x%x)", elem.s, v, elem.h32)
+		}
+		if v1, v2 := h128.Sum128(); v1 != elem.h64_1 || v2 != elem.h64_2 {
+			t.Errorf("'%s': 0x%x-0x%x (want 0x%x-0x%x)", elem.s, v1, v2, elem.h64_1, elem.h64_2)
+		}
+	}
+}
+
+//---
+
+func bench32(b *testing.B, length int) {
+	buf := make([]byte, length)
+	b.SetBytes(int64(length))
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		Sum32(buf)
+	}
+}
+
+func Benchmark32_1(b *testing.B) {
+	bench32(b, 1)
+}
+func Benchmark32_2(b *testing.B) {
+	bench32(b, 2)
+}
+func Benchmark32_4(b *testing.B) {
+	bench32(b, 4)
+}
+func Benchmark32_8(b *testing.B) {
+	bench32(b, 8)
+}
+func Benchmark32_16(b *testing.B) {
+	bench32(b, 16)
+}
+func Benchmark32_32(b *testing.B) {
+	bench32(b, 32)
+}
+func Benchmark32_64(b *testing.B) {
+	bench32(b, 64)
+}
+func Benchmark32_128(b *testing.B) {
+	bench32(b, 128)
+}
+func Benchmark32_256(b *testing.B) {
+	bench32(b, 256)
+}
+func Benchmark32_512(b *testing.B) {
+	bench32(b, 512)
+}
+func Benchmark32_1024(b *testing.B) {
+	bench32(b, 1024)
+}
+func Benchmark32_2048(b *testing.B) {
+	bench32(b, 2048)
+}
+func Benchmark32_4096(b *testing.B) {
+	bench32(b, 4096)
+}
+func Benchmark32_8192(b *testing.B) {
+	bench32(b, 8192)
+}
+
+//---
+
+func benchPartial32(b *testing.B, length int) {
+	buf := make([]byte, length)
+	b.SetBytes(int64(length))
+
+	start := (32 / 8) / 2
+	chunks := 7
+	k := length / chunks
+	tail := (length - start) % k
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		hasher := New32()
+		hasher.Write(buf[0:start])
+
+		for j := start; j+k <= length; j += k {
+			hasher.Write(buf[j : j+k])
+		}
+
+		hasher.Write(buf[length-tail:])
+		hasher.Sum32()
+	}
+}
+
+func BenchmarkPartial32_8(b *testing.B) {
+	benchPartial32(b, 8)
+}
+func BenchmarkPartial32_16(b *testing.B) {
+	benchPartial32(b, 16)
+}
+func BenchmarkPartial32_32(b *testing.B) {
+	benchPartial32(b, 32)
+}
+func BenchmarkPartial32_64(b *testing.B) {
+	benchPartial32(b, 64)
+}
+func BenchmarkPartial32_128(b *testing.B) {
+	benchPartial32(b, 128)
+}
+
+//---
+
+func bench128(b *testing.B, length int) {
+	buf := make([]byte, length)
+	b.SetBytes(int64(length))
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		Sum128(buf)
+	}
+}
+
+func Benchmark128_1(b *testing.B) {
+	bench128(b, 1)
+}
+func Benchmark128_2(b *testing.B) {
+	bench128(b, 2)
+}
+func Benchmark128_4(b *testing.B) {
+	bench128(b, 4)
+}
+func Benchmark128_8(b *testing.B) {
+	bench128(b, 8)
+}
+func Benchmark128_16(b *testing.B) {
+	bench128(b, 16)
+}
+func Benchmark128_32(b *testing.B) {
+	bench128(b, 32)
+}
+func Benchmark128_64(b *testing.B) {
+	bench128(b, 64)
+}
+func Benchmark128_128(b *testing.B) {
+	bench128(b, 128)
+}
+func Benchmark128_256(b *testing.B) {
+	bench128(b, 256)
+}
+func Benchmark128_512(b *testing.B) {
+	bench128(b, 512)
+}
+func Benchmark128_1024(b *testing.B) {
+	bench128(b, 1024)
+}
+func Benchmark128_2048(b *testing.B) {
+	bench128(b, 2048)
+}
+func Benchmark128_4096(b *testing.B) {
+	bench128(b, 4096)
+}
+func Benchmark128_8192(b *testing.B) {
+	bench128(b, 8192)
+}
+
+//---