hash/siphash.d

   1 /*
   2  * SipHash: a fast short-input PRF
   3  *
   4  * Example:
   5  * -----
   6  * // Create key
   7  * ubyte[16] key = cast(ubyte[])"To be|not to be!";
   8  * // Compute hash with key and arbitrary message
   9  * ulong  hashed = sipHash24Of(key, cast(ubyte[])"that is the question.");
  10  * assert(hashed == 17352353082512417190);
  11  * -----
  12  *
  13  * See_Also:
  14  *  https://www.131002.net/siphash/ -- SipHash: a fast short-input PRF
  15  *
  16  * Copyright: Copyright Masahiro Nakagawa 2012-.
  17  * License:   Boost License 1.0
  18  * Authors:   Masahiro Nakagawa
  19  *
  20  * modifications, CTFEcation, etc. by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
  21  */
  22 ///WARNING: not conforming to hash API!
  23 module iv.hash.siphash /*is aliced*/;
  24 private:
  25 import iv.alice;
  26
  27 /**
  28  * siphash template, which takes SipRound C and D parameters
  29  */
  30 public template SipHashImpl(usize C, usize D) {
  31   /**
  32    * Computes SipHash hashes of arbitrary data.
  33    *
  34    * Params:
  35    *  key     = 16 byte key to hash
  36    *  message = an arbitrary message
  37    *
  38    * Returns:
  39    *  a 8 byte hash value.
  40    */
  41   ulong sipHashOf(TK, TM) (auto ref in TK[16] key, in TM[] message) pure nothrow @trusted @nogc
  42   if (TK.sizeof == 1 && TM.sizeof == 1)
  43   {
  44     return sipHashOf(SipHashU8to64LE(key.ptr), SipHashU8to64LE(key.ptr, SipHashBlockSize), message);
  45   }
  46
  47   /// ditto
  48   ulong sipHashOf(TM) (in ulong k0, in ulong k1, in TM[] message) pure nothrow @trusted @nogc
  49   if (TM.sizeof == 1)
  50   {
  51     ulong v0 = k0^0x736f6d6570736575UL;
  52     ulong v1 = k1^0x646f72616e646f6dUL;
  53     ulong v2 = k0^0x6c7967656e657261UL;
  54     ulong v3 = k1^0x7465646279746573UL;
  55
  56     usize index;
  57     usize blocks = message.length&~7;
  58     while (index < blocks) {
  59       immutable mi = SipHashU8to64LE(message.ptr, index);
  60       v3 ^= mi;
  61       foreach (immutable _; 0..C) mixin(SipRound);
  62       v0 ^= mi;
  63       index += SipHashBlockSize;
  64     }
  65
  66     ulong tail = cast(ulong)(message.length&0xff)<<56;
  67     switch (message.length%SipHashBlockSize) {
  68       case 7: tail |= cast(ulong)message[index+6]<<48; goto case 6;
  69       case 6: tail |= cast(ulong)message[index+5]<<40; goto case 5;
  70       case 5: tail |= cast(ulong)message[index+4]<<32; goto case 4;
  71       case 4: tail |= cast(ulong)message[index+3]<<24; goto case 3;
  72       case 3: tail |= cast(ulong)message[index+2]<<16; goto case 2;
  73       case 2: tail |= cast(ulong)message[index+1]<< 8; goto case 1;
  74       case 1: tail |= cast(ulong)message[index+0]; break;
  75       default: break;
  76     }
  77
  78     v3 ^= tail;
  79     foreach (immutable _; 0..C) mixin(SipRound);
  80     v0 ^= tail;
  81
  82     v2 ^= 0xff;
  83     foreach (immutable _; 0..D) mixin(SipRound);
  84
  85     return v0^v1^v2^v3;
  86   }
  87 }
  88
  89 public alias SipHashImpl!(2, 4).sipHashOf sipHash24Of;
  90 public alias SipHashImpl!(4, 8).sipHashOf sipHash48Of;
  91
  92
  93 /**
  94  * SipHash object implements std.digest like API for supporting streaming update.
  95  *
  96  * Example:
  97  * -----
  98  * char[16] key = "To be|not to be!";
  99  * auto sh = SipHash!(2, 4)(key);
 100  *
 101  * sh.reset();
 102  * foreach (chunk; chunks(cast(ubyte[])"that is the question.", 2)) sh.put(chunk);
 103  * auto hashed = sh.finish();
 104  * -----
 105  */
 106 public struct SipHash(usize C, usize D) {
 107 private:
 108   immutable ulong k0, k1;
 109   ulong v0, v1, v2, v3;
 110
 111   usize processedLength;
 112   ubyte[SipHashBlockSize] message; // actually, this is an accummulator; bits 0..2 of [$-1] is a counter
 113
 114 public:
 115 pure nothrow @trusted @nogc:
 116   /// Constructs SipHash with 16 byte key.
 117   this(TK) (auto ref in TK[16] key) @nogc if (TK.sizeof == 1) {
 118     this(SipHashU8to64LE(key.ptr), SipHashU8to64LE(key.ptr, SipHashBlockSize));
 119   }
 120
 121   /// Constructs SipHash with two 8 byte key numbers.
 122   this (in ulong key0, in ulong key1) { k0 = key0; k1 = key1; reset(); }
 123
 124   /// Used to initialize the SipHash.
 125   void reset () {
 126     v0 = k0^0x736f6d6570736575UL;
 127     v1 = k1^0x646f72616e646f6dUL;
 128     v2 = k0^0x6c7967656e657261UL;
 129     v3 = k1^0x7465646279746573UL;
 130     processedLength = 0;
 131     message[$-1] = 0; // reset counter
 132   }
 133
 134   /**
 135    * Use this to feed the digest with data.
 136    * Also implements the `OutputRange` interface for `ubyte` and `const(ubyte)[])`.
 137    */
 138   void put(T) (scope const(T)[] data...) if (T.sizeof == 1) {
 139     usize didx = 0;
 140     usize dlen = data.length;
 141     ubyte left = (SipHashBlockSize-message[$-1])%SipHashBlockSize;
 142     // complete incomplete block, if any
 143     if (left) {
 144       ubyte midx = message[$-1];
 145       if (left > dlen) {
 146         // no data to fill the block, keep accumulating
 147         while (dlen--) message[midx++] = cast(ubyte)(data[didx++]);
 148         // fix pointer
 149         assert(midx < SipHashBlockSize);
 150         message[$-1] = midx;
 151         return;
 152       } else {
 153         // enough data to fill the block, fill it
 154         dlen -= left;
 155         while (left--) message[midx++] = cast(ubyte)(data[didx++]);
 156         // update hash
 157         immutable mi = SipHashU8to64LE(message.ptr);
 158         v3 ^= mi;
 159         foreach (immutable _; 0..C) mixin(SipRound);
 160         v0 ^= mi;
 161         processedLength += SipHashBlockSize;
 162         // clear accummulator
 163         message[$-1] = 0;
 164       }
 165     }
 166     // accummulator is empty, process full blocks
 167     foreach (immutable _0; 0..dlen/SipHashBlockSize) {
 168       if (__ctfe) {
 169         foreach (immutable idx; 0..SipHashBlockSize) message[idx] = cast(ubyte)data[didx+idx];
 170       } else {
 171         message[] = (cast(const(ubyte)[])data)[didx..didx+SipHashBlockSize];
 172       }
 173       immutable mi = SipHashU8to64LE(message.ptr);
 174       v3 ^= mi;
 175       foreach (immutable _1; 0..C) mixin(SipRound);
 176       v0 ^= mi;
 177       didx += SipHashBlockSize;
 178       processedLength += SipHashBlockSize;
 179     }
 180     // check if we have some incomplete data
 181     if ((dlen %= SipHashBlockSize) != 0) {
 182       // accumulate it
 183       message[$-1] = cast(ubyte)dlen;
 184       if (__ctfe) {
 185         foreach (immutable idx; 0..dlen) message[idx] = cast(ubyte)data[didx+idx];
 186       } else {
 187         message[0..dlen] = (cast(const(ubyte)[])data)[didx..didx+dlen];
 188       }
 189     }
 190   }
 191
 192   /**
 193    * Returns the finished SipHash hash as ubyte[8], not ulong.
 194    * This also calls `reset` to reset the internal state.
 195    */
 196   ubyte[8] resultUB(bool finishIt=false) () {
 197     import std.bitmanip : nativeToLittleEndian;
 198     return nativeToLittleEndian(result!finishIt);
 199   }
 200
 201   /**
 202    * Returns the finished SipHash hash as ubyte[8], not ulong.
 203    * This also calls `reset` to reset the internal state.
 204    */
 205   //ubyte[8] finish () { return result!true(); }
 206   alias finish = resultUB!true;
 207
 208   /**
 209    * Returns the finished SipHash hash as ubyte[8], not ulong.
 210    * This also calls `reset` to reset the internal state.
 211    */
 212   ulong result(bool finishIt=false) () {
 213     static if (!finishIt) {
 214       immutable sv0 = v0;
 215       immutable sv1 = v1;
 216       immutable sv2 = v2;
 217       immutable sv3 = v3;
 218     }
 219
 220     // process accumulated data, if any
 221     ulong tail = cast(ulong)((processedLength+message[$-1])&0xff)<<56;
 222     switch (message[$-1]) {
 223       case 7: tail |= cast(ulong)message[6]<<48; goto case 6;
 224       case 6: tail |= cast(ulong)message[5]<<40; goto case 5;
 225       case 5: tail |= cast(ulong)message[4]<<32; goto case 4;
 226       case 4: tail |= cast(ulong)message[3]<<24; goto case 3;
 227       case 3: tail |= cast(ulong)message[2]<<16; goto case 2;
 228       case 2: tail |= cast(ulong)message[1]<<8; goto case 1;
 229       case 1: tail |= cast(ulong)message[0]; break;
 230       default: break;
 231     }
 232
 233     v3 ^= tail;
 234     foreach (immutable _; 0..C) mixin(SipRound);
 235     v0 ^= tail;
 236
 237     v2 ^= 0xff;
 238     foreach (immutable _; 0..D) mixin(SipRound);
 239
 240     static if (!finishIt) {
 241       ulong res = v0^v1^v2^v3;
 242       v0 = sv0;
 243       v1 = sv1;
 244       v2 = sv2;
 245       v3 = sv3;
 246       return res;
 247     } else {
 248       return v0^v1^v2^v3;
 249     }
 250   }
 251
 252   /// very clever hack
 253   static ulong opIndex(TK, TD) (auto ref in TK[16] key, in TD[] data)
 254   if (TK.sizeof == 1 && TD.sizeof == 1)
 255   {
 256     return SipHashImpl!(C, D).sipHashOf(SipHashU8to64LE(key.ptr), SipHashU8to64LE(key.ptr, SipHashBlockSize), data);
 257   }
 258 }
 259
 260
 261 ulong SipHashU8to64LE(T) (in T* ptr, in usize i=0) pure nothrow @trusted @nogc if (T.sizeof == 1) {
 262   if (__ctfe) {
 263     version(LittleEndian) {
 264       return
 265         cast(ulong)ptr[i+0]|
 266         ((cast(ulong)ptr[i+1])<<8)|
 267         ((cast(ulong)ptr[i+2])<<16)|
 268         ((cast(ulong)ptr[i+3])<<24)|
 269         ((cast(ulong)ptr[i+4])<<32)|
 270         ((cast(ulong)ptr[i+5])<<40)|
 271         ((cast(ulong)ptr[i+6])<<48)|
 272         ((cast(ulong)ptr[i+7])<<56);
 273     } else {
 274       return
 275         cast(ulong)ptr[i+7]|
 276         ((cast(ulong)ptr[i+6])<<8)|
 277         ((cast(ulong)ptr[i+5])<<16)|
 278         ((cast(ulong)ptr[i+4])<<24)|
 279         ((cast(ulong)ptr[i+3])<<32)|
 280         ((cast(ulong)ptr[i+2])<<40)|
 281         ((cast(ulong)ptr[i+1])<<48)|
 282         ((cast(ulong)ptr[i+0])<<56);
 283     }
 284   } else {
 285     return *cast(ulong*)(ptr+i);
 286   }
 287 }
 288
 289 ulong sipHashROTL (in ulong u, in uint s) pure nothrow @trusted @nogc { pragma(inline, true); return (u<<s)|(u>>(64-s)); }
 290
 291 enum SipHashBlockSize = ulong.sizeof;
 292
 293 enum SipRound = q{
 294   v0 += v1;
 295   v1  = sipHashROTL(v1, 13);
 296   v1 ^= v0;
 297   v0  = sipHashROTL(v0, 32);
 298
 299   v2 += v3;
 300   v3  = sipHashROTL(v3, 16);
 301   v3 ^= v2;
 302
 303   v2 += v1;
 304   v1  = sipHashROTL(v1, 17);
 305   v1 ^= v2;
 306   v2  = sipHashROTL(v2, 32);
 307
 308   v0 += v3;
 309   v3  = sipHashROTL(v3, 21);
 310   v3 ^= v0;
 311 };
 312
 313
 314 version(iv_hash_unittest) unittest {
 315   import std.conv : to;
 316   import std.range : chunks;
 317   import std.bitmanip : littleEndianToNative, nativeToLittleEndian;
 318
 319   /*
 320     SipHash-2-4 output with
 321     key = 00 01 02 ...
 322     and
 323     message = (empty string)
 324     message = 00 (1 byte)
 325     message = 00 01 (2 bytes)
 326     message = 00 01 02 (3 bytes)
 327     ...
 328     message = 00 01 02 ... 3e (63 bytes)
 329   */
 330   static immutable ulong[64] testVectors = [
 331     0x726fdb47dd0e0e31UL, 0x74f839c593dc67fdUL, 0x0d6c8009d9a94f5aUL, 0x85676696d7fb7e2dUL,
 332     0xcf2794e0277187b7UL, 0x18765564cd99a68dUL, 0xcbc9466e58fee3ceUL, 0xab0200f58b01d137UL,
 333     0x93f5f5799a932462UL, 0x9e0082df0ba9e4b0UL, 0x7a5dbbc594ddb9f3UL, 0xf4b32f46226bada7UL,
 334     0x751e8fbc860ee5fbUL, 0x14ea5627c0843d90UL, 0xf723ca908e7af2eeUL, 0xa129ca6149be45e5UL,
 335     0x3f2acc7f57c29bdbUL, 0x699ae9f52cbe4794UL, 0x4bc1b3f0968dd39cUL, 0xbb6dc91da77961bdUL,
 336     0xbed65cf21aa2ee98UL, 0xd0f2cbb02e3b67c7UL, 0x93536795e3a33e88UL, 0xa80c038ccd5ccec8UL,
 337     0xb8ad50c6f649af94UL, 0xbce192de8a85b8eaUL, 0x17d835b85bbb15f3UL, 0x2f2e6163076bcfadUL,
 338     0xde4daaaca71dc9a5UL, 0xa6a2506687956571UL, 0xad87a3535c49ef28UL, 0x32d892fad841c342UL,
 339     0x7127512f72f27cceUL, 0xa7f32346f95978e3UL, 0x12e0b01abb051238UL, 0x15e034d40fa197aeUL,
 340     0x314dffbe0815a3b4UL, 0x027990f029623981UL, 0xcadcd4e59ef40c4dUL, 0x9abfd8766a33735cUL,
 341     0x0e3ea96b5304a7d0UL, 0xad0c42d6fc585992UL, 0x187306c89bc215a9UL, 0xd4a60abcf3792b95UL,
 342     0xf935451de4f21df2UL, 0xa9538f0419755787UL, 0xdb9acddff56ca510UL, 0xd06c98cd5c0975ebUL,
 343     0xe612a3cb9ecba951UL, 0xc766e62cfcadaf96UL, 0xee64435a9752fe72UL, 0xa192d576b245165aUL,
 344     0x0a8787bf8ecb74b2UL, 0x81b3e73d20b49b6fUL, 0x7fa8220ba3b2eceaUL, 0x245731c13ca42499UL,
 345     0xb78dbfaf3a8d83bdUL, 0xea1ad565322a1a0bUL, 0x60e61c23a3795013UL, 0x6606d7e446282b93UL,
 346     0x6ca4ecb15c5f91e1UL, 0x9f626da15c9625f3UL, 0xe51b38608ef25f57UL, 0x958a324ceb064572UL
 347   ];
 348
 349   char[16] key;
 350   foreach (ubyte i; 0..16) key[i] = i;
 351
 352   auto sh = SipHash!(2, 4)(key);
 353   ulong calcViaStreaming (ubyte[] message) {
 354     sh.reset();
 355     foreach (chunk; chunks(message, 3)) sh.put(chunk);
 356     return littleEndianToNative!ulong(sh.finish());
 357   }
 358
 359   ubyte[] message;
 360   foreach (ubyte i; 0..64) {
 361     auto result = sipHash24Of(key, message);
 362     assert(result == testVectors[i], "test vector failed for "~to!string(i));
 363     assert(calcViaStreaming(message) == testVectors[i], "test vector failed for "~to!string(i)~" in streaming");
 364     message ~= i;
 365   }
 366   // wow, we can do CTFE!
 367   //pragma(msg, sipHash24Of("0123456789abcdef", "Alice & Miriel"));
 368   static assert(sipHash24Of("0123456789abcdef", "Alice & Miriel") == 12689084848626545050LU);
 369   static assert(SipHash!(2, 4)["0123456789abcdef", "Alice & Miriel"] == 12689084848626545050LU);
 370 }