hash/fasthash.d

   1 /* The MIT License
   2  * implementation of fasthash
   3  * http://code.google.com/p/fast-hash/
   4  *
   5  * Copyright (C) 2012 Zilong Tan (eric.zltan@gmail.com)
   6  *
   7  * Permission is hereby granted, free of charge, to any person
   8  * obtaining a copy of this software and associated documentation
   9  * files (the "Software"), to deal in the Software without
  10  * restriction, including without limitation the rights to use, copy,
  11  * modify, merge, publish, distribute, sublicense, and/or sell copies
  12  * of the Software, and to permit persons to whom the Software is
  13  * furnished to do so, subject to the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be
  16  * included in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  22  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  23  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  25  * SOFTWARE.
  26  */
  27 module iv.hash.fasthash /*is aliced*/;
  28 import iv.alice;
  29
  30
  31 /**
  32  * 64-bit implementation of fasthash
  33  *
  34  * Params:
  35  *   buf =  data buffer
  36  *   seed = the seed
  37  */
  38 public struct FastHash {
  39 public:
  40   enum has64bit = true;
  41   enum has32bit = true;
  42
  43 private:
  44   enum M = 0x880355f21e6d1965UL;
  45
  46 private:
  47   ulong seed; // initial seed value; MUST BE FIRST
  48   ulong hash; // current value
  49   ulong accum; // we operate 64-bit chunks; high 3 bits of accum used as counter
  50   ulong totallen;
  51
  52 public:
  53 nothrow @trusted @nogc:
  54   /// construct state with seed
  55   this (ulong aseed) pure { pragma(inline, true); hash = seed = aseed; }
  56
  57   /// reset state
  58   void reset () pure { pragma(inline, true); accum = totallen = 0; hash = seed; }
  59
  60   /// reset state
  61   void reset (ulong aseed) pure { pragma(inline, true); accum = totallen = 0; hash = seed = aseed; }
  62
  63   /// process data block
  64   void put(T) (scope const(T)[] data...) if (T.sizeof == 1) {
  65     if (data.length == 0) return; // nothing to do
  66     if (totallen == 0) hash = seed;
  67     auto bytes = cast(const(ubyte)*)data.ptr;
  68     auto len = data.length;
  69     if (totallen+len < totallen) assert(0, "FastHash: too much data"); // overflow
  70     totallen += len;
  71     auto h = hash;
  72     auto acc = accum;
  73     // do we have something in accum?
  74     if (acc) {
  75       // consume any carry bytes
  76       ubyte i = (acc>>61)&7;
  77       assert(i != 0);
  78       acc &= ~(7UL<<61);
  79       while (i < 8 && len) {
  80         acc |= (cast(ulong)(*bytes++))<<(i*8);
  81         ++i;
  82         --len;
  83       }
  84       if (i == 8) {
  85         // got 8 bytes, process 'em
  86         acc ^= acc>>23;
  87         acc *= 0x2127599bf4325c37UL;
  88         acc ^= acc>>47;
  89         h ^= acc;
  90         h *= M;
  91         acc = 0;
  92       } else {
  93         // update counter
  94         assert(i < 8);
  95         assert(len == 0);
  96         acc |= (cast(ulong)i)<<61;
  97       }
  98     }
  99     // now process 8-byte blocks
 100     assert(len == 0 || acc == 0);
 101     ulong t;
 102     foreach (immutable _; 0..len/8) {
 103       if (__ctfe) {
 104         t = cast(ulong)bytes[0]|
 105            (cast(ulong)bytes[1]<<8)|
 106            (cast(ulong)bytes[2]<<16)|
 107            (cast(ulong)bytes[3]<<24)|
 108            (cast(ulong)bytes[4]<<32)|
 109            (cast(ulong)bytes[5]<<40)|
 110            (cast(ulong)bytes[6]<<48)|
 111            (cast(ulong)bytes[7]<<56);
 112       } else {
 113         version(LittleEndian) {
 114           t = *cast(const(ulong)*)bytes;
 115         } else {
 116           t = cast(ulong)bytes[0]|
 117              (cast(ulong)bytes[1]<<8)|
 118              (cast(ulong)bytes[2]<<16)|
 119              (cast(ulong)bytes[3]<<24)|
 120              (cast(ulong)bytes[4]<<32)|
 121              (cast(ulong)bytes[5]<<40)|
 122              (cast(ulong)bytes[6]<<48)|
 123              (cast(ulong)bytes[7]<<56);
 124         }
 125       }
 126       bytes += 8;
 127       t ^= t>>23;
 128       t *= 0x2127599bf4325c37UL;
 129       t ^= t>>47;
 130       h ^= t;
 131       h *= M;
 132     }
 133     // do we have something to push into accum?
 134     if ((len &= 7) != 0) {
 135       foreach (immutable shift; 0..len) {
 136         acc |= (cast(ulong)(*bytes++))<<(shift*8);
 137       }
 138       acc |= (cast(ulong)len)<<61;
 139     }
 140     hash = h;
 141     accum = acc;
 142   }
 143
 144   /// finalize a hash (i.e. return current result).
 145   /// note that you can continue putting data, as this is not destructive
 146   @property ulong result64 () const pure {
 147     ulong h = hash;
 148     if (totallen == 0) h = seed;
 149     h ^= totallen*M;
 150
 151     ulong acc = accum;
 152     if (acc) {
 153       acc &= ~(7UL<<61);
 154       h ^= acc&(7UL<<61);
 155     }
 156     acc ^= acc>>23;
 157     acc *= 0x2127599bf4325c37UL;
 158     acc ^= acc>>47;
 159     h ^= acc;
 160     h *= M;
 161
 162     h ^= h>>23;
 163     h *= 0x2127599bf4325c37UL;
 164     h ^= h>>47;
 165     return h;
 166   }
 167
 168   /// finalize a hash (i.e. return current result).
 169   /// note that you can continue putting data, as this is not destructive
 170   @property uint result32 () const pure {
 171     pragma(inline, true);
 172     auto h = result64;
 173     // the following trick converts the 64-bit hashcode to Fermat
 174     // residue, which shall retain information from both the higher
 175     // and lower parts of hashcode.
 176     return cast(uint)(h-(h>>32));
 177   }
 178
 179   ulong finish64 () pure { auto res = result64; reset(); return res; } /// resets state
 180   ulong finish32 () pure { auto res = result32; reset(); return res; } /// resets state
 181 }
 182
 183
 184 /**
 185  * 64-bit implementation of fasthash
 186  *
 187  * Params:
 188  *   buf =  data buffer
 189  *   seed = the seed
 190  */
 191 ulong fastHash64(T) (const(T)[] buf, ulong seed=0) nothrow @trusted @nogc if (T.sizeof == 1) {
 192   auto hh = FastHash(seed);
 193   hh.put(buf);
 194   return hh.result64;
 195 }
 196
 197 /**
 198  * 32-bit implementation of fasthash
 199  *
 200  * Params:
 201  *   buf =  data buffer
 202  *   seed = the seed
 203  */
 204 uint fastHash32(T) (const(T)[] buf, ulong seed=0) nothrow @trusted @nogc if (T.sizeof == 1) {
 205   auto hh = FastHash(seed);
 206   hh.put(buf);
 207   return hh.result32;
 208 }
 209
 210
 211 /**
 212  * 64-bit implementation of fasthash
 213  *
 214  * Params:
 215  *   buf =  data buffer
 216  *   seed = the seed
 217  */
 218 ulong fastHash64(T) (const(T)[] buf, ulong seed=0) nothrow @trusted @nogc if (T.sizeof > 1) {
 219   auto hh = FastHash(seed);
 220   hh.put((cast(const(ubyte)*)buf.ptr)[0..buf.length*T.sizeof]);
 221   return hh.result64;
 222 }
 223
 224 /**
 225  * 32-bit implementation of fasthash
 226  *
 227  * Params:
 228  *   buf =  data buffer
 229  *   seed = the seed
 230  */
 231 uint fastHash32(T) (const(T)[] buf, ulong seed=0) nothrow @trusted @nogc if (T.sizeof > 1) {
 232   auto hh = FastHash(seed);
 233   hh.put((cast(const(ubyte)*)buf.ptr)[0..buf.length*T.sizeof]);
 234   return hh.result32;
 235 }
 236
 237
 238 version(iv_hash_unittest) unittest {
 239   static assert(fastHash32("Alice & Miriel") == 0x4773e2a3U);
 240   static assert(fastHash64("Alice & Miriel") == 0xfa02b41e417696c1UL);
 241
 242   /*{
 243     import std.stdio;
 244     writefln("0x%08xU", fastHash32("Alice & Miriel"));
 245     writefln("0x%016xUL", fastHash64("Alice & Miriel"));
 246   }*/
 247
 248   mixin(import("test.d"));
 249   doTest!(32, "FastHash")("Alice & Miriel", 0x4773e2a3U);
 250   doTest!(64, "FastHash")("Alice & Miriel", 0xfa02b41e417696c1UL);
 251 }