LCOV - code coverage report
Current view: top level - tommyds/tommyds - tommyhash.c (source / functions) Hit Total Coverage
Test: lcov.info Lines: 106 106 100.0 %
Date: 2018-04-02 17:50:51 Functions: 4 4 100.0 %

          Line data    Source code
       1             : /*
       2             :  * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
       3             :  *
       4             :  * Redistribution and use in source and binary forms, with or without
       5             :  * modification, are permitted provided that the following conditions
       6             :  * are met:
       7             :  *
       8             :  * 1. Redistributions of source code must retain the above copyright
       9             :  *    notice, this list of conditions and the following disclaimer.
      10             :  *
      11             :  * 2. Redistributions in binary form must reproduce the above copyright
      12             :  *    notice, this list of conditions and the following disclaimer in the
      13             :  *    documentation and/or other materials provided with the distribution.
      14             :  *
      15             :  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
      16             :  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      17             :  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      18             :  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
      19             :  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
      20             :  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
      21             :  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
      22             :  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
      23             :  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
      24             :  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
      25             :  * POSSIBILITY OF SUCH DAMAGE.
      26             :  */
      27             : 
      28             : #include "tommyhash.h"
      29             : 
      30             : /******************************************************************************/
      31             : /* hash */
      32             : 
      33   201326801 : tommy_inline tommy_uint32_t tommy_le_uint32_read(const void* ptr)
      34             : {
      35             :         /* allow unaligned read on Intel x86 and x86_64 platforms */
      36             : #if defined(__i386__) || defined(_M_IX86) || defined(_X86_) || defined(__x86_64__) || defined(_M_X64)
      37             :         /* defines from http://predef.sourceforge.net/ */
      38   201326801 :         return *(const tommy_uint32_t*)ptr;
      39             : #else
      40             :         const unsigned char* ptr8 = tommy_cast(const unsigned char*, ptr);
      41             :         return ptr8[0] + ((tommy_uint32_t)ptr8[1] << 8) + ((tommy_uint32_t)ptr8[2] << 16) + ((tommy_uint32_t)ptr8[3] << 24);
      42             : #endif
      43             : }
      44             : 
      45             : #define tommy_rot(x, k) \
      46             :         (((x) << (k)) | ((x) >> (32 - (k))))
      47             : 
      48             : #define tommy_mix(a, b, c) \
      49             :         do { \
      50             :                 a -= c;  a ^= tommy_rot(c, 4);  c += b; \
      51             :                 b -= a;  b ^= tommy_rot(a, 6);  a += c; \
      52             :                 c -= b;  c ^= tommy_rot(b, 8);  b += a; \
      53             :                 a -= c;  a ^= tommy_rot(c, 16);  c += b; \
      54             :                 b -= a;  b ^= tommy_rot(a, 19);  a += c; \
      55             :                 c -= b;  c ^= tommy_rot(b, 4);  b += a; \
      56             :         } while (0)
      57             : 
      58             : #define tommy_final(a, b, c) \
      59             :         do { \
      60             :                 c ^= b; c -= tommy_rot(b, 14); \
      61             :                 a ^= c; a -= tommy_rot(c, 11); \
      62             :                 b ^= a; b -= tommy_rot(a, 25); \
      63             :                 c ^= b; c -= tommy_rot(b, 16); \
      64             :                 a ^= c; a -= tommy_rot(c, 4);  \
      65             :                 b ^= a; b -= tommy_rot(a, 14); \
      66             :                 c ^= b; c -= tommy_rot(b, 24); \
      67             :         } while (0)
      68             : 
      69    16777239 : tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len)
      70             : {
      71    16777239 :         const unsigned char* key = tommy_cast(const unsigned char*, void_key);
      72             :         tommy_uint32_t a, b, c;
      73             : 
      74    16777239 :         a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + init_val;
      75             : 
      76    50331709 :         while (key_len > 12) {
      77    16777231 :                 a += tommy_le_uint32_read(key + 0);
      78    16777231 :                 b += tommy_le_uint32_read(key + 4);
      79    16777231 :                 c += tommy_le_uint32_read(key + 8);
      80             : 
      81    16777231 :                 tommy_mix(a, b, c);
      82             : 
      83    16777231 :                 key_len -= 12;
      84    16777231 :                 key += 12;
      85             :         }
      86             : 
      87    16777239 :         switch (key_len) {
      88             :         case 0 :
      89           1 :                 return c; /* used only when called with a zero length */
      90             :         case 12 :
      91           1 :                 c += tommy_le_uint32_read(key + 8);
      92           1 :                 b += tommy_le_uint32_read(key + 4);
      93           1 :                 a += tommy_le_uint32_read(key + 0);
      94           1 :                 break;
      95           1 :         case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
      96           2 :         case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
      97           3 :         case 9 : c += key[8]; /* fallthrough */
      98             :         case 8 :
      99           4 :                 b += tommy_le_uint32_read(key + 4);
     100           4 :                 a += tommy_le_uint32_read(key + 0);
     101           4 :                 break;
     102           2 :         case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
     103           3 :         case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
     104           4 :         case 5 : b += key[4]; /* fallthrough */
     105             :         case 4 :
     106    16777222 :                 a += tommy_le_uint32_read(key + 0);
     107    16777222 :                 break;
     108           3 :         case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
     109           8 :         case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
     110          11 :         case 1 : a += key[0]; /* fallthrough */
     111             :         }
     112             : 
     113    16777238 :         tommy_final(a, b, c);
     114             : 
     115    16777238 :         return c;
     116             : }
     117             : 
     118    16777239 : tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len)
     119             : {
     120    16777239 :         const unsigned char* key = tommy_cast(const unsigned char*, void_key);
     121             :         tommy_uint32_t a, b, c;
     122             : 
     123    16777239 :         a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + (init_val & 0xffffffff);
     124    16777239 :         c += init_val >> 32;
     125             : 
     126    50331709 :         while (key_len > 12) {
     127    16777231 :                 a += tommy_le_uint32_read(key + 0);
     128    16777231 :                 b += tommy_le_uint32_read(key + 4);
     129    16777231 :                 c += tommy_le_uint32_read(key + 8);
     130             : 
     131    16777231 :                 tommy_mix(a, b, c);
     132             : 
     133    16777231 :                 key_len -= 12;
     134    16777231 :                 key += 12;
     135             :         }
     136             : 
     137    16777239 :         switch (key_len) {
     138             :         case 0 :
     139           1 :                 return c + ((tommy_uint64_t)b << 32); /* used only when called with a zero length */
     140             :         case 12 :
     141           1 :                 c += tommy_le_uint32_read(key + 8);
     142           1 :                 b += tommy_le_uint32_read(key + 4);
     143           1 :                 a += tommy_le_uint32_read(key + 0);
     144           1 :                 break;
     145           1 :         case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
     146           2 :         case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
     147           3 :         case 9 : c += key[8]; /* fallthrough */
     148             :         case 8 :
     149           4 :                 b += tommy_le_uint32_read(key + 4);
     150           4 :                 a += tommy_le_uint32_read(key + 0);
     151           4 :                 break;
     152           2 :         case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
     153           3 :         case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
     154           4 :         case 5 : b += key[4]; /* fallthrough */
     155             :         case 4 :
     156    16777222 :                 a += tommy_le_uint32_read(key + 0);
     157    16777222 :                 break;
     158           3 :         case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
     159           8 :         case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
     160          11 :         case 1 : a += key[0]; /* fallthrough */
     161             :         }
     162             : 
     163    16777238 :         tommy_final(a, b, c);
     164             : 
     165    16777238 :         return c + ((tommy_uint64_t)b << 32);
     166             : }
     167             : 
     168    16777239 : tommy_uint32_t tommy_strhash_u32(tommy_uint64_t init_val, const void* void_key)
     169             : {
     170    16777239 :         const unsigned char* key = tommy_cast(const unsigned char*, void_key);
     171             :         tommy_uint32_t a, b, c;
     172    16777239 :         tommy_uint32_t m[3] = { 0xff, 0xff00, 0xff0000 };
     173             : 
     174    16777239 :         a = b = c = 0xdeadbeef + init_val;
     175             :         /* this is different than original lookup3 and the result won't match */
     176             : 
     177             :         while (1) {
     178    33554471 :                 tommy_uint32_t v = tommy_le_uint32_read(key);
     179             : 
     180    33554471 :                 if (tommy_haszero_u32(v)) {
     181    16777229 :                         if (v & m[0]) {
     182    16777227 :                                 a += v & m[0];
     183    16777227 :                                 if (v & m[1]) {
     184    16777224 :                                         a += v & m[1];
     185    16777224 :                                         if (v & m[2])
     186    16777219 :                                                 a += v & m[2];
     187             :                                 }
     188             :                         }
     189             : 
     190    16777229 :                         break;
     191             :                 }
     192             : 
     193    16777242 :                 a += v;
     194             : 
     195    16777242 :                 v = tommy_le_uint32_read(key + 4);
     196             : 
     197    16777242 :                 if (tommy_haszero_u32(v)) {
     198           6 :                         if (v & m[0]) {
     199           4 :                                 b += v & m[0];
     200           4 :                                 if (v & m[1]) {
     201           3 :                                         b += v & m[1];
     202           3 :                                         if (v & m[2])
     203           2 :                                                 b += v & m[2];
     204             :                                 }
     205             :                         }
     206             : 
     207           6 :                         break;
     208             :                 }
     209             : 
     210    16777236 :                 b += v;
     211             : 
     212    16777236 :                 v = tommy_le_uint32_read(key + 8);
     213             : 
     214    16777236 :                 if (tommy_haszero_u32(v)) {
     215           4 :                         if (v & m[0]) {
     216           3 :                                 c += v & m[0];
     217           3 :                                 if (v & m[1]) {
     218           2 :                                         c += v & m[1];
     219           2 :                                         if (v & m[2])
     220           1 :                                                 c += v & m[2];
     221             :                                 }
     222             :                         }
     223             : 
     224           4 :                         break;
     225             :                 }
     226             : 
     227    16777232 :                 c += v;
     228             : 
     229    16777232 :                 tommy_mix(a, b, c);
     230             : 
     231    16777232 :                 key += 12;
     232    16777232 :         }
     233             : 
     234             :         /* for lengths that are multiplers of 12 we already have called mix */
     235             :         /* this is different than the original lookup3 and the result won't match */
     236             : 
     237    16777239 :         tommy_final(a, b, c);
     238             : 
     239    16777239 :         return c;
     240             : }
     241             : 

Generated by: LCOV version 1.13