hash/joaat.d

   1 /* Invisible Vector Library
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, version 3 of the License ONLY.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  16  */
  17 module iv.hash.joaat /*is aliced*/;
  18 // Bob Jenkins' One-At-A-Time hash function
  19 import iv.alice;
  20
  21
  22 // this seems to give worser results
  23 //version = JoaatMixLength;
  24
  25
  26 /**
  27  * 32-bit implementation of joaat
  28  *
  29  * Params:
  30  *   buf =  data buffer
  31  *   seed = the seed
  32  */
  33 public struct JoaatHash {
  34 public:
  35   enum has64bit = false;
  36   enum has32bit = true;
  37
  38 private:
  39   uint seed; // initial seed value; MUST BE FIRST
  40   uint hash; // current value
  41   version(JoaatMixLength) {
  42     ulong totallen;
  43   } else {
  44     ubyte totallen;
  45   }
  46
  47 public:
  48 nothrow @trusted @nogc:
  49   /// construct state with seed
  50   this (uint aseed) pure { hash = seed = aseed; }
  51
  52   /// reset state
  53   void reset () pure { totallen = 0; hash = seed; }
  54
  55   /// reset state
  56   void reset (uint aseed) pure { totallen = 0; hash = seed = aseed; }
  57
  58   /// process data block
  59   void put(T) (scope const(T)[] data...) if (T.sizeof == 1) {
  60     if (data.length == 0) return; // nothing to do
  61     if (totallen == 0) hash = seed;
  62     auto bytes = cast(const(ubyte)*)data.ptr;
  63     auto len = data.length;
  64     version(JoaatMixLength) {
  65       if (totallen+len < totallen) assert(0, "FastHash: too much data"); // overflow
  66       totallen += len;
  67     } else {
  68       totallen = 1;
  69     }
  70     auto h = hash;
  71     foreach (immutable _; 0..len) {
  72       h += *bytes++;
  73       h += (h<<10);
  74       h ^= (h>>6);
  75     }
  76     hash = h;
  77   }
  78
  79   /// finalize a hash (i.e. return current result).
  80   /// note that you can continue putting data, as this is not destructive
  81   @property uint result32 () const pure {
  82     uint h = hash;
  83     if (totallen == 0) h = seed;
  84     version(JoaatMixLength) {
  85       ulong len = totallen;
  86       while (len != 0) {
  87         h += len&0xff;
  88         h += (h<<10);
  89         h ^= (h>>6);
  90         len >>= 8;
  91       }
  92     }
  93     h += (h<<3);
  94     h ^= (h>>11);
  95     h += (h<<15);
  96     return h;
  97   }
  98
  99   uint finish32 () pure { auto res = result32; reset(); return res; } /// resets state
 100 }
 101
 102
 103 /**
 104  * 32-bit implementation of joaathash
 105  *
 106  * Params:
 107  *   buf =  data buffer
 108  *   seed = the seed
 109  */
 110 uint joaatHash32(T) (const(T)[] buf, uint seed=0) nothrow @trusted @nogc if (T.sizeof == 1) {
 111   auto hh = JoaatHash(seed);
 112   hh.put(buf);
 113   return hh.result32;
 114 }
 115
 116
 117 /**
 118  * 32-bit implementation of joaathash
 119  *
 120  * Params:
 121  *   buf =  data buffer
 122  *   seed = the seed
 123  */
 124 uint joaatHash32(T) (const(T)[] buf, uint seed=0) nothrow @trusted @nogc if (T.sizeof > 1) {
 125   auto hh = JoaatHash(seed);
 126   hh.put((cast(const(ubyte)*)buf.ptr)[0..buf.length*T.sizeof]);
 127   return hh.result32;
 128 }
 129
 130
 131 version(iv_hash_unittest) unittest {
 132   version(JoaatMixLength) {
 133     enum HashValue = 0x17fa5136U;
 134   } else {
 135     enum HashValue = 0xb8519b5bU;
 136   }
 137   static assert(joaatHash32("Alice & Miriel") == HashValue);
 138
 139   /*{
 140     import std.stdio;
 141     writefln("0x%08xU", joaatHash32("Alice & Miriel"));
 142   }*/
 143
 144   mixin(import("test.d"));
 145   doTest!(32, "JoaatHash")("Alice & Miriel", HashValue);
 146 }