source/lib/fnv_hash.cpp

   1 /* Copyright (c) 2010 Wildfire Games
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining
   4  * a copy of this software and associated documentation files (the
   5  * "Software"), to deal in the Software without restriction, including
   6  * without limitation the rights to use, copy, modify, merge, publish,
   7  * distribute, sublicense, and/or sell copies of the Software, and to
   8  * permit persons to whom the Software is furnished to do so, subject to
   9  * the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included
  12  * in all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  15  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  16  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  17  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  18  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  19  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  20  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 /*
  24  * Fowler/Noll/Vo string hash
  25  */
  26
  27 #include "precompiled.h"
  28
  29
  30 // FNV1-A hash - good for strings.
  31 // if len = 0 (default), treat buf as a C-string;
  32 // otherwise, hash <len> bytes of buf.
  33 u32 fnv_hash(const void* buf, size_t len)
  34 {
  35         u32 h = 0x811c9dc5u;
  36         // give distinct values for different length 0 buffers.
  37         // value taken from FNV; it has no special significance.
  38
  39         const u8* p = (const u8*)buf;
  40
  41         // expected case: string
  42         if(!len)
  43         {
  44                 while(*p)
  45                 {
  46                         h ^= *p++;
  47                         h *= 0x01000193u;
  48                 }
  49         }
  50         else
  51         {
  52                 size_t bytes_left = len;
  53                 while(bytes_left != 0)
  54                 {
  55                         h ^= *p++;
  56                         h *= 0x01000193u;
  57
  58                         bytes_left--;
  59                 }
  60         }
  61
  62         return h;
  63 }
  64
  65
  66 // FNV1-A hash - good for strings.
  67 // if len = 0 (default), treat buf as a C-string;
  68 // otherwise, hash <len> bytes of buf.
  69 u64 fnv_hash64(const void* buf, size_t len)
  70 {
  71         u64 h = 0xCBF29CE484222325ull;
  72         // give distinct values for different length 0 buffers.
  73         // value taken from FNV; it has no special significance.
  74
  75         const u8* p = (const u8*)buf;
  76
  77         // expected case: string
  78         if(!len)
  79         {
  80                 while(*p)
  81                 {
  82                         h ^= *p++;
  83                         h *= 0x100000001B3ull;
  84                 }
  85         }
  86         else
  87         {
  88                 size_t bytes_left = len;
  89                 while(bytes_left != 0)
  90                 {
  91                         h ^= *p++;
  92                         h *= 0x100000001B3ull;
  93
  94                         bytes_left--;
  95                 }
  96         }
  97
  98         return h;
  99 }
 100
 101
 102 // special version for strings: first converts to lowercase
 103 // (useful for comparing mixed-case filenames).
 104 // note: still need <len>, e.g. to support non-0-terminated strings
 105 u32 fnv_lc_hash(const char* str, size_t len)
 106 {
 107         u32 h = 0x811c9dc5u;
 108         // give distinct values for different length 0 buffers.
 109         // value taken from FNV; it has no special significance.
 110
 111         // expected case: string
 112         if(!len)
 113         {
 114                 while(*str)
 115                 {
 116                         h ^= tolower(*str++);
 117                         h *= 0x01000193u;
 118                 }
 119         }
 120         else
 121         {
 122                 size_t bytes_left = len;
 123                 while(bytes_left != 0)
 124                 {
 125                         h ^= tolower(*str++);
 126                         h *= 0x01000193u;
 127
 128                         bytes_left--;
 129                 }
 130         }
 131
 132         return h;
 133 }