src/hash.c

   1 /*
   2  * PgBouncer - Lightweight connection pooler for PostgreSQL.
   3  *
   4  * Copyright (c) 2007 Marko Kreen, Skype Technologies OÜ
   5  *
   6  * Permission to use, copy, modify, and distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 #include "system.h"
  20 #include "hash.h"
  21
  22 /*
  23  * A simple version of Bob Jenkins' lookup3.c hash.
  24  *
  25  * It is supposed to give same results as hashlittle() on little-endian
  26  * and hashbig() on big-endian machines.
  27  *
  28  * Speed seems comparable to Jenkins' optimized version (~ -10%).
  29  * Actual difference varies as it depends on cpu/compiler/libc details.
  30  */
  31
  32 /* rotate uint32 */
  33 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
  34
  35 /* mix 3 32-bit values reversibly */
  36 #define mix(a, b, c) do { \
  37         a -= c;  a ^= rot(c, 4);  c += b; \
  38         b -= a;  b ^= rot(a, 6);  a += c; \
  39         c -= b;  c ^= rot(b, 8);  b += a; \
  40         a -= c;  a ^= rot(c,16);  c += b; \
  41         b -= a;  b ^= rot(a,19);  a += c; \
  42         c -= b;  c ^= rot(b, 4);  b += a; \
  43 } while (0)
  44
  45 /* final mixing of 3 32-bit values (a,b,c) into c */
  46 #define final(a, b, c) do { \
  47         c ^= b; c -= rot(b,14); \
  48         a ^= c; a -= rot(c,11); \
  49         b ^= a; b -= rot(a,25); \
  50         c ^= b; c -= rot(b,16); \
  51         a ^= c; a -= rot(c, 4); \
  52         b ^= a; b -= rot(a,14); \
  53         c ^= b; c -= rot(b,24); \
  54 } while (0)
  55
  56 /* short version - let compiler worry about memory access */
  57 uint32_t lookup3_hash(const void *data, size_t len)
  58 {
  59         uint32_t a, b, c;
  60         uint32_t buf[3];
  61         const uint8_t *p = data;
  62
  63         a = b = c = 0xdeadbeef + len;
  64         if (len == 0)
  65                 goto done;
  66
  67         while (len > 12) {
  68                 memcpy(buf, p, 12);
  69                 a += buf[0];
  70                 b += buf[1];
  71                 c += buf[2];
  72                 mix(a, b, c);
  73                 p += 12;
  74                 len -= 12;
  75         }
  76
  77         buf[0] = buf[1] = buf[2] = 0;
  78         memcpy(buf, p, len);
  79         a += buf[0];
  80         b += buf[1];
  81         c += buf[2];
  82         final(a, b, c);
  83 done:
  84         return c;
  85 }
  86
  87
  88 /*
  89  * Reversible integer hash function by Thomas Wang.
  90  */
  91
  92 uint32_t hash32(uint32_t v)
  93 {
  94         v = ~v + (v << 15);
  95         v = v ^ (v >> 12);
  96         v = v + (v << 2);
  97         v = v ^ (v >> 4);
  98         v = v * 2057;
  99         v = v ^ (v >> 16);
 100         return v;
 101 }
 102