← Back to branch summary

~ci-train-bot/ubuntu-push/ubuntu-push-ubuntu-zesty-2405

« back to all changes in this revision

Viewing changes to external/murmur3/murmur32.go

  • Committer: Tarmac
  • Author(s): Samuele Pedroni (Canonical Services Ltd.)
  • Date: 2014-03-24 16:18:08 UTC
  • mfrom: (88.1.4 gethosts)
  • Revision ID: tarmac-20140324161808-5h9lgcg76d5ngaxn
[r=chipaca] introduce package gethosts implementing finding hosts to connect to for delivery of notifications

Show diffs side-by-side

added added

removed removed

Lines of Context:
external/murmur3/murmur32.go
 
1
package murmur3
 
2
 
 
3
// http://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/hash/Murmur3_32HashFunction.java
 
4
 
 
5
import (
 
6
        "hash"
 
7
        "unsafe"
 
8
)
 
9
 
 
10
// Make sure interfaces are correctly implemented.
 
11
var (
 
12
        _ hash.Hash   = new(digest32)
 
13
        _ hash.Hash32 = new(digest32)
 
14
)
 
15
 
 
16
const (
 
17
        c1_32 uint32 = 0xcc9e2d51
 
18
        c2_32 uint32 = 0x1b873593
 
19
)
 
20
 
 
21
// digest32 represents a partial evaluation of a 32 bites hash.
 
22
type digest32 struct {
 
23
        digest
 
24
        h1 uint32 // Unfinalized running hash.
 
25
}
 
26
 
 
27
func New32() hash.Hash32 {
 
28
        d := new(digest32)
 
29
        d.bmixer = d
 
30
        d.Reset()
 
31
        return d
 
32
}
 
33
 
 
34
func (d *digest32) Size() int { return 4 }
 
35
 
 
36
func (d *digest32) reset() { d.h1 = 1 }
 
37
 
 
38
func (d *digest32) Sum(b []byte) []byte {
 
39
        h := d.h1
 
40
        return append(b, byte(h>>24), byte(h>>16), byte(h>>8), byte(h))
 
41
}
 
42
 
 
43
// Digest as many blocks as possible.
 
44
func (d *digest32) bmix(p []byte) (tail []byte) {
 
45
        h1 := d.h1
 
46
 
 
47
        nblocks := len(p) / 4
 
48
        for i := 0; i < nblocks; i++ {
 
49
                k1 := *(*uint32)(unsafe.Pointer(&p[i*4]))
 
50
 
 
51
                k1 *= c1_32
 
52
                k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
 
53
                k1 *= c2_32
 
54
 
 
55
                h1 ^= k1
 
56
                h1 = (h1 << 13) | (h1 >> 19) // rotl32(h1, 13)
 
57
                h1 = h1*5 + 0xe6546b64
 
58
        }
 
59
        d.h1 = h1
 
60
        return p[nblocks*d.Size():]
 
61
}
 
62
 
 
63
func (d *digest32) Sum32() (h1 uint32) {
 
64
 
 
65
        h1 = d.h1
 
66
 
 
67
        var k1 uint32
 
68
        switch len(d.tail) & 3 {
 
69
        case 3:
 
70
                k1 ^= uint32(d.tail[2]) << 16
 
71
                fallthrough
 
72
        case 2:
 
73
                k1 ^= uint32(d.tail[1]) << 8
 
74
                fallthrough
 
75
        case 1:
 
76
                k1 ^= uint32(d.tail[0])
 
77
                k1 *= c1_32
 
78
                k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
 
79
                k1 *= c2_32
 
80
                h1 ^= k1
 
81
        }
 
82
 
 
83
        h1 ^= uint32(d.clen)
 
84
 
 
85
        h1 ^= h1 >> 16
 
86
        h1 *= 0x85ebca6b
 
87
        h1 ^= h1 >> 13
 
88
        h1 *= 0xc2b2ae35
 
89
        h1 ^= h1 >> 16
 
90
 
 
91
        return h1
 
92
}
 
93
 
 
94
/*
 
95
func rotl32(x uint32, r byte) uint32 {
 
96
        return (x << r) | (x >> (32 - r))
 
97
}
 
98
*/
 
99
 
 
100
// Sum32 returns the MurmurHash3 sum of data. It is equivalent to the
 
101
// following sequence (without the extra burden and the extra allocation):
 
102
//     hasher := New32()
 
103
//     hasher.Write(data)
 
104
//     return hasher.Sum32()
 
105
func Sum32(data []byte) uint32 {
 
106
 
 
107
        var h1 uint32 = 1
 
108
 
 
109
        nblocks := len(data) / 4
 
110
        var p uintptr
 
111
        if len(data) > 0 {
 
112
                p = uintptr(unsafe.Pointer(&data[0]))
 
113
        }
 
114
        p1 := p + uintptr(4*nblocks)
 
115
        for ; p < p1; p += 4 {
 
116
                k1 := *(*uint32)(unsafe.Pointer(p))
 
117
 
 
118
                k1 *= c1_32
 
119
                k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
 
120
                k1 *= c2_32
 
121
 
 
122
                h1 ^= k1
 
123
                h1 = (h1 << 13) | (h1 >> 19) // rotl32(h1, 13)
 
124
                h1 = h1*5 + 0xe6546b64
 
125
        }
 
126
 
 
127
        tail := data[nblocks*4:]
 
128
 
 
129
        var k1 uint32
 
130
        switch len(tail) & 3 {
 
131
        case 3:
 
132
                k1 ^= uint32(tail[2]) << 16
 
133
                fallthrough
 
134
        case 2:
 
135
                k1 ^= uint32(tail[1]) << 8
 
136
                fallthrough
 
137
        case 1:
 
138
                k1 ^= uint32(tail[0])
 
139
                k1 *= c1_32
 
140
                k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
 
141
                k1 *= c2_32
 
142
                h1 ^= k1
 
143
        }
 
144
 
 
145
        h1 ^= uint32(len(data))
 
146
 
 
147
        h1 ^= h1 >> 16
 
148
        h1 *= 0x85ebca6b
 
149
        h1 ^= h1 >> 13
 
150
        h1 *= 0xc2b2ae35
 
151
        h1 ^= h1 >> 16
 
152
 
 
153
        return h1
 
154
}