mirror of
https://github.com/cnotch/ipchub.git
synced 2025-09-26 19:41:18 +08:00
103 lines
2.9 KiB
Go
103 lines
2.9 KiB
Go
/**********************************************************************************
|
||
* Copyright (c) 2009-2019 Misakai Ltd.
|
||
* This program is free software: you can redistribute it and/or modify it under the
|
||
* terms of the GNU Affero General Public License as published by the Free Software
|
||
* Foundation, either version 3 of the License, or(at your option) any later version.
|
||
*
|
||
* This program is distributed in the hope that it will be useful, but WITHOUT ANY
|
||
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
|
||
* PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.
|
||
*
|
||
* You should have received a copy of the GNU Affero General Public License along
|
||
* with this program. If not, see<http://www.gnu.org/licenses/>.
|
||
************************************************************************************/
|
||
|
||
// Package murmur 是murmur算法的实现，方网站：https://sites.google.com/site/murmurhash/
|
||
//
|
||
// MurmurHash算法：高运算性能，低碰撞率，由Austin Appleby创建于2008年，
|
||
// 现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。
|
||
// 2011年Appleby被Google雇佣，随后Google推出其变种的CityHash算法。
|
||
//
|
||
// 当key的长度大于10字节的时候，MurmurHash的运算速度才快于DJB。
|
||
// “从计算速度上来看，MurmurHash只适用于已知长度的、长度比较长的字符”。
|
||
package murmur
|
||
|
||
import (
|
||
"reflect"
|
||
"unsafe"
|
||
)
|
||
|
||
const (
|
||
c1_32 uint32 = 0xcc9e2d51
|
||
c2_32 uint32 = 0x1b873593
|
||
)
|
||
|
||
// OfString returns a murmur32 hash for the string
|
||
func OfString(value string) uint32 {
|
||
return Of(stringToBinary(value))
|
||
}
|
||
|
||
// Of returns a murmur32 hash for the data slice.
|
||
func Of(data []byte) uint32 {
|
||
// Seed is set to 37, same as C# version of emitter
|
||
var h1 uint32 = 37
|
||
|
||
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 << 24) | (((h1 >> 8) << 16) & 0xFF0000) | (((h1 >> 16) << 8) & 0xFF00) | (h1 >> 24)
|
||
}
|
||
|
||
func stringToBinary(v string) (b []byte) {
|
||
strHeader := (*reflect.StringHeader)(unsafe.Pointer(&v))
|
||
byteHeader := (*reflect.SliceHeader)(unsafe.Pointer(&b))
|
||
byteHeader.Data = strHeader.Data
|
||
|
||
l := len(v)
|
||
byteHeader.Len = l
|
||
byteHeader.Cap = l
|
||
return
|
||
}
|