follin/hash.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, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 module iv.follin.hash /*is aliced*/;
  19 import iv.alice;
  20
  21
  22 // ////////////////////////////////////////////////////////////////////////// //
  23 version(X86) version = AnyX86;
  24 version(X86_64) version = AnyX86;
  25 version(AnyX86) version = HasUnalignedOps;
  26
  27
  28 /**
  29  * 64-bit implementation of fasthash
  30  *
  31  * Params:
  32  *   buf =  data buffer
  33  *   seed = the seed
  34  *
  35  * Returns:
  36  *   32-bit or 64-bit hash
  37  */
  38 package(iv.follin) usize hashBuffer (const(void)* buf, usize len, usize seed=0) pure nothrow @trusted @nogc {
  39   enum Get8Bytes = q{
  40     cast(ulong)data[0]|
  41     (cast(ulong)data[1]<<8)|
  42     (cast(ulong)data[2]<<16)|
  43     (cast(ulong)data[3]<<24)|
  44     (cast(ulong)data[4]<<32)|
  45     (cast(ulong)data[5]<<40)|
  46     (cast(ulong)data[6]<<48)|
  47     (cast(ulong)data[7]<<56)
  48   };
  49   enum m = 0x880355f21e6d1965UL;
  50   auto data = cast(const(ubyte)*)buf;
  51   ulong h = seed;
  52   ulong t;
  53   foreach (immutable _; 0..len/8) {
  54     version(HasUnalignedOps) {
  55       if (__ctfe) {
  56         t = mixin(Get8Bytes);
  57       } else {
  58         t = *cast(ulong*)data;
  59       }
  60     } else {
  61       t = mixin(Get8Bytes);
  62     }
  63     data += 8;
  64     t ^= t>>23;
  65     t *= 0x2127599bf4325c37UL;
  66     t ^= t>>47;
  67     h ^= t;
  68     h *= m;
  69   }
  70
  71   h ^= len*m;
  72   t = 0;
  73   switch (len&7) {
  74     case 7: t ^= cast(ulong)data[6]<<48; goto case 6;
  75     case 6: t ^= cast(ulong)data[5]<<40; goto case 5;
  76     case 5: t ^= cast(ulong)data[4]<<32; goto case 4;
  77     case 4: t ^= cast(ulong)data[3]<<24; goto case 3;
  78     case 3: t ^= cast(ulong)data[2]<<16; goto case 2;
  79     case 2: t ^= cast(ulong)data[1]<<8; goto case 1;
  80     case 1: t ^= cast(ulong)data[0]; goto default;
  81     default:
  82       t ^= t>>23;
  83       t *= 0x2127599bf4325c37UL;
  84       t ^= t>>47;
  85       h ^= t;
  86       h *= m;
  87       break;
  88   }
  89
  90   h ^= h>>23;
  91   h *= 0x2127599bf4325c37UL;
  92   h ^= h>>47;
  93   static if (usize.sizeof == 4) {
  94     // 32-bit hash
  95     // the following trick converts the 64-bit hashcode to Fermat
  96     // residue, which shall retain information from both the higher
  97     // and lower parts of hashcode.
  98     return cast(usize)(h-(h>>32));
  99   } else {
 100     return h;
 101   }
 102 }