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, 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.follin.hash /*is aliced*/;
  18 import iv.alice;
  19
  20
  21 // ////////////////////////////////////////////////////////////////////////// //
  22 version(X86) version = AnyX86;
  23 version(X86_64) version = AnyX86;
  24 version(AnyX86) version = HasUnalignedOps;
  25
  26
  27 /**
  28  * 64-bit implementation of fasthash
  29  *
  30  * Params:
  31  *   buf =  data buffer
  32  *   seed = the seed
  33  *
  34  * Returns:
  35  *   32-bit or 64-bit hash
  36  */
  37 package(iv.follin) usize hashBuffer (const(void)* buf, usize len, usize seed=0) pure nothrow @trusted @nogc {
  38   enum Get8Bytes = q{
  39     cast(ulong)data[0]|
  40     (cast(ulong)data[1]<<8)|
  41     (cast(ulong)data[2]<<16)|
  42     (cast(ulong)data[3]<<24)|
  43     (cast(ulong)data[4]<<32)|
  44     (cast(ulong)data[5]<<40)|
  45     (cast(ulong)data[6]<<48)|
  46     (cast(ulong)data[7]<<56)
  47   };
  48   enum m = 0x880355f21e6d1965UL;
  49   auto data = cast(const(ubyte)*)buf;
  50   ulong h = seed;
  51   ulong t;
  52   foreach (immutable _; 0..len/8) {
  53     version(HasUnalignedOps) {
  54       if (__ctfe) {
  55         t = mixin(Get8Bytes);
  56       } else {
  57         t = *cast(ulong*)data;
  58       }
  59     } else {
  60       t = mixin(Get8Bytes);
  61     }
  62     data += 8;
  63     t ^= t>>23;
  64     t *= 0x2127599bf4325c37UL;
  65     t ^= t>>47;
  66     h ^= t;
  67     h *= m;
  68   }
  69
  70   h ^= len*m;
  71   t = 0;
  72   switch (len&7) {
  73     case 7: t ^= cast(ulong)data[6]<<48; goto case 6;
  74     case 6: t ^= cast(ulong)data[5]<<40; goto case 5;
  75     case 5: t ^= cast(ulong)data[4]<<32; goto case 4;
  76     case 4: t ^= cast(ulong)data[3]<<24; goto case 3;
  77     case 3: t ^= cast(ulong)data[2]<<16; goto case 2;
  78     case 2: t ^= cast(ulong)data[1]<<8; goto case 1;
  79     case 1: t ^= cast(ulong)data[0]; goto default;
  80     default:
  81       t ^= t>>23;
  82       t *= 0x2127599bf4325c37UL;
  83       t ^= t>>47;
  84       h ^= t;
  85       h *= m;
  86       break;
  87   }
  88
  89   h ^= h>>23;
  90   h *= 0x2127599bf4325c37UL;
  91   h ^= h>>47;
  92   static if (usize.sizeof == 4) {
  93     // 32-bit hash
  94     // the following trick converts the 64-bit hashcode to Fermat
  95     // residue, which shall retain information from both the higher
  96     // and lower parts of hashcode.
  97     return cast(usize)(h-(h>>32));
  98   } else {
  99     return h;
 100   }
 101 }