142 lines
4.7 KiB
C
142 lines
4.7 KiB
C
/**
|
|
* Copyright (2017) Baidu Inc. All rights reserved.
|
|
*
|
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
|
* you may not use this file except in compliance with the License.
|
|
* You may obtain a copy of the License at
|
|
*
|
|
* http://www.apache.org/licenses/LICENSE-2.0
|
|
*
|
|
* Unless required by applicable law or agreed to in writing, software
|
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
* See the License for the specific language governing permissions and
|
|
* limitations under the License.
|
|
*/
|
|
// Author: Su Hao (suhao@baidu.com)
|
|
//
|
|
// Description: The hashcode algorithm
|
|
|
|
#include "lightduer_hashcode.h"
|
|
#include "lightduer_log.h"
|
|
|
|
/* constants for duer_hashcode() */
|
|
#define DUER__STRHASH_SHORTSTRING 4096L
|
|
#define DUER__STRHASH_MEDIUMSTRING (256L * 1024L)
|
|
#define DUER__STRHASH_BLOCKSIZE 256L
|
|
|
|
#define DUER__SEED ((duer_u32_t) 0x738b3f34)
|
|
|
|
/* 'magic' constants for Murmurhash2 */
|
|
#define DUER__MAGIC_M ((duer_u32_t) 0x5bd1e995UL)
|
|
#define DUER__MAGIC_R 24
|
|
|
|
DUER_LOC_IMPL duer_u32_t duer_hashcode_compute(const duer_s8_t *data, duer_size_t len, duer_u32_t seed)
|
|
{
|
|
duer_u32_t hash = seed ^ ((duer_u32_t)len);
|
|
|
|
while (len >= 4) {
|
|
/* Portability workaround is required for platforms without
|
|
* unaligned access. The replacement code emulates little
|
|
* endian access even on big endian architectures, which is
|
|
* OK as long as it is consistent for a build.
|
|
*/
|
|
duer_u32_t k = (((duer_u32_t)data[0]) & 0xff) |
|
|
((((duer_u32_t)data[1]) & 0xff) << 8) |
|
|
((((duer_u32_t)data[2]) & 0xff) << 16) |
|
|
((((duer_u32_t)data[3]) & 0xff) << 24);
|
|
DUER_DUMPV("data", data, 4);
|
|
DUER_LOGV("k = %08x", k);
|
|
k *= DUER__MAGIC_M;
|
|
DUER_LOGV("k = %08x", k);
|
|
k ^= k >> DUER__MAGIC_R;
|
|
DUER_LOGV("k = %08x", k);
|
|
k *= DUER__MAGIC_M;
|
|
|
|
DUER_LOGV("k = %08x", k);
|
|
DUER_LOGV("hashcode = %08x", hash);
|
|
hash *= DUER__MAGIC_M;
|
|
DUER_LOGV("hashcode = %08x", hash);
|
|
hash ^= k;
|
|
data += 4;
|
|
len -= 4;
|
|
}
|
|
|
|
if (len == 3) {
|
|
hash ^= data[2] << 16;
|
|
--len;
|
|
}
|
|
if (len == 2) {
|
|
hash ^= data[1] << 8;
|
|
--len;
|
|
}
|
|
if (len == 1) {
|
|
hash ^= data[0];
|
|
hash *= DUER__MAGIC_M;
|
|
}
|
|
|
|
hash ^= hash >> 13;
|
|
hash *= DUER__MAGIC_M;
|
|
hash ^= hash >> 15;
|
|
return hash;
|
|
}
|
|
|
|
DUER_INT_IMPL duer_u32_t duer_hashcode(const duer_s8_t *data,
|
|
duer_size_t size,
|
|
duer_u32_t seed)
|
|
{
|
|
duer_u32_t hash = 0;
|
|
/*
|
|
* Sampling long strings by byte skipping (like Lua does) is potentially
|
|
* a cache problem. Here we do 'block skipping' instead for long strings:
|
|
* hash an initial part, and then sample the rest of the string with
|
|
* reasonably sized chunks.
|
|
*
|
|
* Skip should depend on length and bound the total time to roughly
|
|
* logarithmic.
|
|
*
|
|
* With current values:
|
|
*
|
|
* 1M string => 256 * 241 = 61696 bytes (0.06M) of hashing
|
|
* 1G string => 256 * 16321 = 4178176 bytes (3.98M) of hashing
|
|
*
|
|
* After an initial part has been hashed, an offset is applied before
|
|
* starting the sampling. The initial offset is computed from the
|
|
* hash of the initial part of the string. The idea is to avoid the
|
|
* case that all long strings have certain offset ranges that are never
|
|
* sampled.
|
|
*/
|
|
/* note: mixing len into seed improves hashing when skipping */
|
|
duer_u32_t str_seed = seed ? seed : DUER__SEED;
|
|
str_seed ^= ((duer_u32_t)size);
|
|
|
|
if (size <= DUER__STRHASH_SHORTSTRING) {
|
|
hash = duer_hashcode_compute(data, size, str_seed);
|
|
} else {
|
|
duer_size_t off;
|
|
duer_size_t skip;
|
|
|
|
if (size <= DUER__STRHASH_MEDIUMSTRING) {
|
|
skip = (duer_size_t)(16 * DUER__STRHASH_BLOCKSIZE + DUER__STRHASH_BLOCKSIZE);
|
|
} else {
|
|
skip = (duer_size_t)(256 * DUER__STRHASH_BLOCKSIZE + DUER__STRHASH_BLOCKSIZE);
|
|
}
|
|
|
|
hash = duer_hashcode_compute(data, (duer_size_t)DUER__STRHASH_SHORTSTRING,
|
|
str_seed);
|
|
off = DUER__STRHASH_SHORTSTRING + (skip * (hash % 256)) / 256;
|
|
|
|
/* XXX: inefficient loop */
|
|
while (off < size) {
|
|
duer_size_t left = size - off;
|
|
duer_size_t now =
|
|
(duer_size_t)(left > DUER__STRHASH_BLOCKSIZE ? DUER__STRHASH_BLOCKSIZE : left);
|
|
hash ^= duer_hashcode_compute(data + off, now, str_seed);
|
|
off += skip;
|
|
}
|
|
}
|
|
|
|
return hash;
|
|
}
|
|
|