X-Git-Url: https://git.m6w6.name/?a=blobdiff_plain;f=src%2Flibhashkit%2Fjenkins.cc;h=64595f691d7bc7607a709df90bdda0f525db3d69;hb=46bddd219732926aae6734a1962c3899b9946ffb;hp=a08287dbc2c85fc206586578322acbdad1e776de;hpb=5bb6f975322d3da0caf082b8d890132194d0a4ea;p=awesomized%2Flibmemcached diff --git a/src/libhashkit/jenkins.cc b/src/libhashkit/jenkins.cc index a08287db..64595f69 100644 --- a/src/libhashkit/jenkins.cc +++ b/src/libhashkit/jenkins.cc @@ -1,79 +1,63 @@ -/* vim:expandtab:shiftwidth=2:tabstop=2:smarttab: - * - * HashKit library - * - * Copyright (C) 2011-2012 Data Differential, http://datadifferential.com/ - * Copyright (C) 2006-2009 Brian Aker 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. - * - * * The names of its contributors may not 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 THE COPYRIGHT - * OWNER OR CONTRIBUTORS 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. - * - */ - /* -* -* By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this -* code any way you wish, private, educational, or commercial. It's free. -* Use for hash table lookup, or anything where one collision in 2^^32 is -* acceptable. Do NOT use for cryptographic purposes. -* http://burtleburtle.net/bob/hash/index.html -* -* Modified by Brian Pontz for libmemcached -* TODO: -* Add big endian support + +--------------------------------------------------------------------+ + | libmemcached - C/C++ Client Library for memcached | + +--------------------------------------------------------------------+ + | Redistribution and use in source and binary forms, with or without | + | modification, are permitted under the terms of the BSD license. | + | You should have received a copy of the license in a bundled file | + | named LICENSE; in case you did not receive a copy you can review | + | the terms online at: https://opensource.org/licenses/BSD-3-Clause | + +--------------------------------------------------------------------+ + | Copyright (c) 2006-2014 Brian Aker https://datadifferential.com/ | + | Copyright (c) 2020 Michael Wallner | + +--------------------------------------------------------------------+ */ #include "libhashkit/common.h" -#define hashsize(n) ((uint32_t)1<<(n)) -#define hashmask(n) (hashsize(n)-1) -#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) +#define hashsize(n) ((uint32_t) 1 << (n)) +#define hashmask(n) (hashsize(n) - 1) +#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) -#define mix(a,b,c) \ -{ \ - a -= c; a ^= rot(c, 4); c += b; \ - b -= a; b ^= rot(a, 6); a += c; \ - c -= b; c ^= rot(b, 8); b += a; \ - a -= c; a ^= rot(c,16); c += b; \ - b -= a; b ^= rot(a,19); a += c; \ - c -= b; c ^= rot(b, 4); b += a; \ -} +#define mix(a, b, c) \ + { \ + a -= c; \ + a ^= rot(c, 4); \ + c += b; \ + b -= a; \ + b ^= rot(a, 6); \ + a += c; \ + c -= b; \ + c ^= rot(b, 8); \ + b += a; \ + a -= c; \ + a ^= rot(c, 16); \ + c += b; \ + b -= a; \ + b ^= rot(a, 19); \ + a += c; \ + c -= b; \ + c ^= rot(b, 4); \ + b += a; \ + } -#define final(a,b,c) \ -{ \ - c ^= b; c -= rot(b,14); \ - a ^= c; a -= rot(c,11); \ - b ^= a; b -= rot(a,25); \ - c ^= b; c -= rot(b,16); \ - a ^= c; a -= rot(c,4); \ - b ^= a; b -= rot(a,14); \ - c ^= b; c -= rot(b,24); \ -} +#define final(a, b, c) \ + { \ + c ^= b; \ + c -= rot(b, 14); \ + a ^= c; \ + a -= rot(c, 11); \ + b ^= a; \ + b -= rot(a, 25); \ + c ^= b; \ + c -= rot(b, 16); \ + a ^= c; \ + a -= rot(c, 4); \ + b ^= a; \ + b -= rot(a, 14); \ + c ^= b; \ + c -= rot(b, 24); \ + } #define JENKINS_INITVAL 13 @@ -93,29 +77,33 @@ use a bitmask. For example, if you need only 10 bits, do In which case, the hash table should have hashsize(10) elements. */ -uint32_t hashkit_jenkins(const char *key, size_t length, void *) -{ - uint32_t a,b,c; /* internal state */ -#ifndef WORDS_BIGENDIAN - union { const void *ptr; size_t i; } u; +#if HAVE_ASAN +__attribute__((no_sanitize_address, no_sanitize("address"))) +#endif +uint32_t +hashkit_jenkins(const char *key, size_t length, void *) { + uint32_t a, b, c; /* internal state */ +#if !WORDS_BIGENDIAN + union { + const void *ptr; + size_t i; + } u; u.ptr = key; #endif /* Set up the internal state */ - a = b = c = 0xdeadbeef + ((uint32_t)length) + JENKINS_INITVAL; + a = b = c = 0xdeadbeef + ((uint32_t) length) + JENKINS_INITVAL; -#ifndef WORDS_BIGENDIAN - if ((u.i & 0x3) == 0) - { - const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ +#if !WORDS_BIGENDIAN + if ((u.i & 0x3) == 0) { + const uint32_t *k = (const uint32_t *) key; /* read 32-bit chunks */ /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ - while (length > 12) - { + while (length > 12) { a += k[0]; b += k[1]; c += k[2]; - mix(a,b,c); + mix(a, b, c); length -= 12; k += 3; } @@ -130,139 +118,196 @@ uint32_t hashkit_jenkins(const char *key, size_t length, void *) * still catch it and complain. The masking trick does make the hash * noticably faster for short strings (like English words). */ - switch(length) - { - case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; - case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; - case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; - case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; - case 8 : b+=k[1]; a+=k[0]; break; - case 7 : b+=k[1]&0xffffff; a+=k[0]; break; - case 6 : b+=k[1]&0xffff; a+=k[0]; break; - case 5 : b+=k[1]&0xff; a+=k[0]; break; - case 4 : a+=k[0]; break; - case 3 : a+=k[0]&0xffffff; break; - case 2 : a+=k[0]&0xffff; break; - case 1 : a+=k[0]&0xff; break; - case 0 : return c; /* zero length strings require no mixing */ - default: return c; + switch (length) { + case 12: + c += k[2]; + b += k[1]; + a += k[0]; + break; + case 11: + c += k[2] & 0xffffff; + b += k[1]; + a += k[0]; + break; + case 10: + c += k[2] & 0xffff; + b += k[1]; + a += k[0]; + break; + case 9: + c += k[2] & 0xff; + b += k[1]; + a += k[0]; + break; + case 8: + b += k[1]; + a += k[0]; + break; + case 7: + b += k[1] & 0xffffff; + a += k[0]; + break; + case 6: + b += k[1] & 0xffff; + a += k[0]; + break; + case 5: + b += k[1] & 0xff; + a += k[0]; + break; + case 4: + a += k[0]; + break; + case 3: + a += k[0] & 0xffffff; + break; + case 2: + a += k[0] & 0xffff; + break; + case 1: + a += k[0] & 0xff; + break; + case 0: + return c; /* zero length strings require no mixing */ + default: + return c; } - } - else if ((u.i & 0x1) == 0) - { - const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ - const uint8_t *k8; + } else if ((u.i & 0x1) == 0) { + const uint16_t *k = (const uint16_t *) key; /* read 16-bit chunks */ + const uint8_t *k8; /*--------------- all but last block: aligned reads and different mixing */ - while (length > 12) - { - a += k[0] + (((uint32_t)k[1])<<16); - b += k[2] + (((uint32_t)k[3])<<16); - c += k[4] + (((uint32_t)k[5])<<16); - mix(a,b,c); + while (length > 12) { + a += k[0] + (((uint32_t) k[1]) << 16); + b += k[2] + (((uint32_t) k[3]) << 16); + c += k[4] + (((uint32_t) k[5]) << 16); + mix(a, b, c); length -= 12; k += 6; } /*----------------------------- handle the last (probably partial) block */ - k8 = (const uint8_t *)k; - switch(length) - { - case 12: c+=k[4]+(((uint32_t)k[5])<<16); - b+=k[2]+(((uint32_t)k[3])<<16); - a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 11: c+=((uint32_t)k8[10])<<16; - /* fall through */ - case 10: c+=k[4]; - b+=k[2]+(((uint32_t)k[3])<<16); - a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 9 : c+=k8[8]; - /* fall through */ - case 8 : b+=k[2]+(((uint32_t)k[3])<<16); - a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 7 : b+=((uint32_t)k8[6])<<16; - /* fall through */ - case 6 : b+=k[2]; - a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 5 : b+=k8[4]; - /* fall through */ - case 4 : a+=k[0]+(((uint32_t)k[1])<<16); - break; - case 3 : a+=((uint32_t)k8[2])<<16; - /* fall through */ - case 2 : a+=k[0]; - break; - case 1 : a+=k8[0]; - break; - case 0 : return c; /* zero length requires no mixing */ - default: return c; + k8 = (const uint8_t *) k; + switch (length) { + case 12: + c += k[4] + (((uint32_t) k[5]) << 16); + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 11: + c += ((uint32_t) k8[10]) << 16; + /* fall through */ + case 10: + c += k[4]; + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 9: + c += k8[8]; + /* fall through */ + case 8: + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 7: + b += ((uint32_t) k8[6]) << 16; + /* fall through */ + case 6: + b += k[2]; + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 5: + b += k8[4]; + /* fall through */ + case 4: + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 3: + a += ((uint32_t) k8[2]) << 16; + /* fall through */ + case 2: + a += k[0]; + break; + case 1: + a += k8[0]; + break; + case 0: + return c; /* zero length requires no mixing */ + default: + return c; } - } - else - { /* need to read the key one byte at a time */ -#endif /* little endian */ - const uint8_t *k = (const uint8_t *)key; + } else { /* need to read the key one byte at a time */ +#endif /* little endian */ + const uint8_t *k = (const uint8_t *) key; /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ - while (length > 12) - { + while (length > 12) { a += k[0]; - a += ((uint32_t)k[1])<<8; - a += ((uint32_t)k[2])<<16; - a += ((uint32_t)k[3])<<24; + a += ((uint32_t) k[1]) << 8; + a += ((uint32_t) k[2]) << 16; + a += ((uint32_t) k[3]) << 24; b += k[4]; - b += ((uint32_t)k[5])<<8; - b += ((uint32_t)k[6])<<16; - b += ((uint32_t)k[7])<<24; + b += ((uint32_t) k[5]) << 8; + b += ((uint32_t) k[6]) << 16; + b += ((uint32_t) k[7]) << 24; c += k[8]; - c += ((uint32_t)k[9])<<8; - c += ((uint32_t)k[10])<<16; - c += ((uint32_t)k[11])<<24; - mix(a,b,c); + c += ((uint32_t) k[9]) << 8; + c += ((uint32_t) k[10]) << 16; + c += ((uint32_t) k[11]) << 24; + mix(a, b, c); length -= 12; k += 12; } /*-------------------------------- last block: affect all 32 bits of (c) */ - switch(length) /* all the case statements fall through */ - { - case 12: c+=((uint32_t)k[11])<<24; - /* fall through */ - case 11: c+=((uint32_t)k[10])<<16; - /* fall through */ - case 10: c+=((uint32_t)k[9])<<8; - /* fall through */ - case 9 : c+=k[8]; - /* fall through */ - case 8 : b+=((uint32_t)k[7])<<24; - /* fall through */ - case 7 : b+=((uint32_t)k[6])<<16; - /* fall through */ - case 6 : b+=((uint32_t)k[5])<<8; - /* fall through */ - case 5 : b+=k[4]; - /* fall through */ - case 4 : a+=((uint32_t)k[3])<<24; - /* fall through */ - case 3 : a+=((uint32_t)k[2])<<16; - /* fall through */ - case 2 : a+=((uint32_t)k[1])<<8; - /* fall through */ - case 1 : a+=k[0]; - break; - case 0 : return c; - default : return c; + switch (length) /* all the case statements fall through */ { + case 12: + c += ((uint32_t) k[11]) << 24; + /* fall through */ + case 11: + c += ((uint32_t) k[10]) << 16; + /* fall through */ + case 10: + c += ((uint32_t) k[9]) << 8; + /* fall through */ + case 9: + c += k[8]; + /* fall through */ + case 8: + b += ((uint32_t) k[7]) << 24; + /* fall through */ + case 7: + b += ((uint32_t) k[6]) << 16; + /* fall through */ + case 6: + b += ((uint32_t) k[5]) << 8; + /* fall through */ + case 5: + b += k[4]; + /* fall through */ + case 4: + a += ((uint32_t) k[3]) << 24; + /* fall through */ + case 3: + a += ((uint32_t) k[2]) << 16; + /* fall through */ + case 2: + a += ((uint32_t) k[1]) << 8; + /* fall through */ + case 1: + a += k[0]; + break; + case 0: + return c; + default: + return c; } -#ifndef WORDS_BIGENDIAN +#if !WORDS_BIGENDIAN } #endif - final(a,b,c); + final(a, b, c); return c; }