hash/rg32.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.rg32 /*is aliced*/;
  18 // RadioGatun[32] hash function, based on the code by Sam Trenholme
  19
  20
  21 /// RadioGatun[32] hash function
  22 public struct RG32Hash {
  23 public:
  24   enum ByteSize = 32; // 32 bytes (aka 256 bits, if you cannot do the math)
  25
  26 private:
  27   ubyte[12] buf;
  28   uint[19] a; // mill
  29   uint[39] b; // belt
  30   uint bufused;
  31   uint o, hasdata;
  32
  33 public:
  34 nothrow @trusted @nogc:
  35   /// reset state
  36   void reset () pure { buf[] = 0; a[] = 0; b[] = 0; bufused = 0; o = 0; hasdata = 0; }
  37
  38   /// process data block
  39   void put(T) (scope const(T)[] data...) if (T.sizeof == 1) {
  40     if (data.length == 0) return; // nothing to do
  41     hasdata = 1;
  42     auto bytes = cast(const(ubyte)*)data.ptr;
  43     auto len = data.length;
  44     while (len > 0) {
  45       while (bufused < 12 && len > 0) {
  46         buf.ptr[bufused++] = *bytes++;
  47         --len;
  48       }
  49       if (bufused == 12) { processBuf(); bufused = 0; }
  50     }
  51   }
  52
  53   /// finalize a hash (i.e. return current result).
  54   /// note that you can continue putting data, as this is not destructive
  55   ubyte[ByteSize] finish () {
  56     if (!hasdata || bufused) processBuf();
  57     // end injection
  58     foreach (immutable uint c; 0..16) {
  59       rground(a.ptr, b.ptr, o);
  60       o += 1;
  61       if (o > 12) o=0;
  62     }
  63     ubyte[ByteSize] res = void;
  64     uint respos = 0;
  65     // end mangling
  66     foreach (immutable uint c; 0..4) {
  67       rground(a.ptr, b.ptr, o);
  68       o += 1;
  69       if (o > 12) o = 0;
  70       assert(respos < ByteSize && ByteSize-respos >= 8);
  71       res.ptr[respos++] = a.ptr[1]&0xff;
  72       res.ptr[respos++] = (a.ptr[1]>>8)&0xff;
  73       res.ptr[respos++] = (a.ptr[1]>>16)&0xff;
  74       res.ptr[respos++] = (a.ptr[1]>>24)&0xff;
  75       res.ptr[respos++] = a.ptr[2]&0xff;
  76       res.ptr[respos++] = (a.ptr[2]>>8)&0xff;
  77       res.ptr[respos++] = (a.ptr[2]>>16)&0xff;
  78       res.ptr[respos++] = (a.ptr[2]>>24)&0xff;
  79     }
  80     reset();
  81     return res[];
  82   }
  83
  84 private:
  85   void processBuf () {
  86     if (bufused == 0) return;
  87     uint[3] p = 0;
  88     uint offset = 0;
  89     bool done = false;
  90     foreach (immutable uint r; 0..3) {
  91       foreach (immutable uint q; 0..4) {
  92         uint x = buf.ptr[offset];
  93         if (offset >= bufused) {
  94           done = true;
  95           /* Spec says this should have a value
  96            * of 0x80; reference code gives this
  97            * a value of 1.  This is IMHO a bug
  98            * in the reference code. */
  99           x = 1;
 100         }
 101         ++offset;
 102         p.ptr[r] |= x<<(q*8);
 103         if (done) {
 104           foreach (immutable uint c; 0..3) {
 105             uint w = 13-o;
 106             if (w == 13) w = 0;
 107             b.ptr[w+c*13] ^= p.ptr[c];
 108             a.ptr[16+c] ^= p.ptr[c];
 109           }
 110           rground(a.ptr, b.ptr, o);
 111           o += 1;
 112           if (o == 13) o = 0;
 113           return;
 114         }
 115       }
 116     }
 117     foreach (immutable uint c; 0..3) {
 118       uint w = 13-o;
 119       if (w == 13) w = 0;
 120       b.ptr[w+c*13] ^= p.ptr[c];
 121       a.ptr[16+c] ^= p.ptr[c];
 122     }
 123     rground(a.ptr, b.ptr, o);
 124     o += 1;
 125     if (o == 13) o = 0;
 126   }
 127
 128 static:
 129   void mill (uint* a) {
 130     uint[19] A = void;
 131     uint x;
 132     // the following is the output of the awk script "make.mill.core"
 133     x = a[0]^(a[1]|(~a[2]));
 134     A.ptr[0] = x;
 135     x = a[7]^(a[8]|(~a[9]));
 136     A.ptr[1] = (x>>1)|(x<<31);
 137     x = a[14]^(a[15]|(~a[16]));
 138     A.ptr[2] = (x>>3)|(x<<29);
 139     x = a[2]^(a[3]|(~a[4]));
 140     A.ptr[3] = (x>>6)|(x<<26);
 141     x = a[9]^(a[10]|(~a[11]));
 142     A.ptr[4] = (x>>10)|(x<<22);
 143     x = a[16]^(a[17]|(~a[18]));
 144     A.ptr[5] = (x>>15)|(x<<17);
 145     x = a[4]^(a[5]|(~a[6]));
 146     A.ptr[6] = (x>>21)|(x<<11);
 147     x = a[11]^(a[12]|(~a[13]));
 148     A.ptr[7] = (x>>28)|(x<<4);
 149     x = a[18]^(a[0]|(~a[1]));
 150     A.ptr[8] = (x>>4)|(x<<28);
 151     x = a[6]^(a[7]|(~a[8]));
 152     A.ptr[9] = (x>>13)|(x<<19);
 153     x = a[13]^(a[14]|(~a[15]));
 154     A.ptr[10] = (x>>23)|(x<<9);
 155     x = a[1]^(a[2]|(~a[3]));
 156     A.ptr[11] = (x>>2)|(x<<30);
 157     x = a[8]^(a[9]|(~a[10]));
 158     A.ptr[12] = (x>>14)|(x<<18);
 159     x = a[15]^(a[16]|(~a[17]));
 160     A.ptr[13] = (x>>27)|(x<<5);
 161     x = a[3]^(a[4]|(~a[5]));
 162     A.ptr[14] = (x>>9)|(x<<23);
 163     x = a[10]^(a[11]|(~a[12]));
 164     A.ptr[15] = (x>>24)|(x<<8);
 165     x = a[17]^(a[18]|(~a[0]));
 166     A.ptr[16] = (x>>8)|(x<<24);
 167     x = a[5]^(a[6]|(~a[7]));
 168     A.ptr[17] = (x>>25)|(x<<7);
 169     x = a[12]^(a[13]|(~a[14]));
 170     A.ptr[18] = (x>>11)|(x<<21);
 171     a[0] = A.ptr[0]^A.ptr[1]^A.ptr[4];
 172     a[1] = A.ptr[1]^A.ptr[2]^A.ptr[5];
 173     a[2] = A.ptr[2]^A.ptr[3]^A.ptr[6];
 174     a[3] = A.ptr[3]^A.ptr[4]^A.ptr[7];
 175     a[4] = A.ptr[4]^A.ptr[5]^A.ptr[8];
 176     a[5] = A.ptr[5]^A.ptr[6]^A.ptr[9];
 177     a[6] = A.ptr[6]^A.ptr[7]^A.ptr[10];
 178     a[7] = A.ptr[7]^A.ptr[8]^A.ptr[11];
 179     a[8] = A.ptr[8]^A.ptr[9]^A.ptr[12];
 180     a[9] = A.ptr[9]^A.ptr[10]^A.ptr[13];
 181     a[10] = A.ptr[10]^A.ptr[11]^A.ptr[14];
 182     a[11] = A.ptr[11]^A.ptr[12]^A.ptr[15];
 183     a[12] = A.ptr[12]^A.ptr[13]^A.ptr[16];
 184     a[13] = A.ptr[13]^A.ptr[14]^A.ptr[17];
 185     a[14] = A.ptr[14]^A.ptr[15]^A.ptr[18];
 186     a[15] = A.ptr[15]^A.ptr[16]^A.ptr[0];
 187     a[16] = A.ptr[16]^A.ptr[17]^A.ptr[1];
 188     a[17] = A.ptr[17]^A.ptr[18]^A.ptr[2];
 189     a[18] = A.ptr[18]^A.ptr[0]^A.ptr[3];
 190     a[0] ^= 1;
 191   }
 192
 193   // the following is the output of "make.belt.core"
 194   void belt_00 (uint* a, uint *b) {
 195     uint q0 = b[12];
 196     uint q1 = b[25];
 197     uint q2 = b[38];
 198     b[0] ^= a[1];
 199     b[14] ^= a[2];
 200     b[28] ^= a[3];
 201     b[3] ^= a[4];
 202     b[17] ^= a[5];
 203     b[31] ^= a[6];
 204     b[6] ^= a[7];
 205     b[20] ^= a[8];
 206     b[34] ^= a[9];
 207     b[9] ^= a[10];
 208     b[23] ^= a[11];
 209     b[37] ^= a[12];
 210     mill(a);
 211     a[13] ^= q0;
 212     a[14] ^= q1;
 213     a[15] ^= q2;
 214   }
 215
 216   void belt_01 (uint* a, uint* b) {
 217     uint q0 = b[11];
 218     uint q1 = b[24];
 219     uint q2 = b[37];
 220     b[12] ^= a[1];
 221     b[13] ^= a[2];
 222     b[27] ^= a[3];
 223     b[2] ^= a[4];
 224     b[16] ^= a[5];
 225     b[30] ^= a[6];
 226     b[5] ^= a[7];
 227     b[19] ^= a[8];
 228     b[33] ^= a[9];
 229     b[8] ^= a[10];
 230     b[22] ^= a[11];
 231     b[36] ^= a[12];
 232     mill(a);
 233     a[13] ^= q0;
 234     a[14] ^= q1;
 235     a[15] ^= q2;
 236   }
 237
 238   void belt_02 (uint* a, uint* b) {
 239     uint q0 = b[10];
 240     uint q1 = b[23];
 241     uint q2 = b[36];
 242     b[11] ^= a[1];
 243     b[25] ^= a[2];
 244     b[26] ^= a[3];
 245     b[1] ^= a[4];
 246     b[15] ^= a[5];
 247     b[29] ^= a[6];
 248     b[4] ^= a[7];
 249     b[18] ^= a[8];
 250     b[32] ^= a[9];
 251     b[7] ^= a[10];
 252     b[21] ^= a[11];
 253     b[35] ^= a[12];
 254     mill(a);
 255     a[13] ^= q0;
 256     a[14] ^= q1;
 257     a[15] ^= q2;
 258   }
 259
 260   void belt_03 (uint* a, uint* b) {
 261     uint q0 = b[9];
 262     uint q1 = b[22];
 263     uint q2 = b[35];
 264     b[10] ^= a[1];
 265     b[24] ^= a[2];
 266     b[38] ^= a[3];
 267     b[0] ^= a[4];
 268     b[14] ^= a[5];
 269     b[28] ^= a[6];
 270     b[3] ^= a[7];
 271     b[17] ^= a[8];
 272     b[31] ^= a[9];
 273     b[6] ^= a[10];
 274     b[20] ^= a[11];
 275     b[34] ^= a[12];
 276     mill(a);
 277     a[13] ^= q0;
 278     a[14] ^= q1;
 279     a[15] ^= q2;
 280   }
 281
 282   void belt_04 (uint* a, uint* b) {
 283     uint q0 = b[8];
 284     uint q1 = b[21];
 285     uint q2 = b[34];
 286     b[9] ^= a[1];
 287     b[23] ^= a[2];
 288     b[37] ^= a[3];
 289     b[12] ^= a[4];
 290     b[13] ^= a[5];
 291     b[27] ^= a[6];
 292     b[2] ^= a[7];
 293     b[16] ^= a[8];
 294     b[30] ^= a[9];
 295     b[5] ^= a[10];
 296     b[19] ^= a[11];
 297     b[33] ^= a[12];
 298     mill(a);
 299     a[13] ^= q0;
 300     a[14] ^= q1;
 301     a[15] ^= q2;
 302   }
 303
 304   void belt_05 (uint* a, uint* b) {
 305     uint q0 = b[7];
 306     uint q1 = b[20];
 307     uint q2 = b[33];
 308     b[8] ^= a[1];
 309     b[22] ^= a[2];
 310     b[36] ^= a[3];
 311     b[11] ^= a[4];
 312     b[25] ^= a[5];
 313     b[26] ^= a[6];
 314     b[1] ^= a[7];
 315     b[15] ^= a[8];
 316     b[29] ^= a[9];
 317     b[4] ^= a[10];
 318     b[18] ^= a[11];
 319     b[32] ^= a[12];
 320     mill(a);
 321     a[13] ^= q0;
 322     a[14] ^= q1;
 323     a[15] ^= q2;
 324   }
 325
 326   void belt_06 (uint* a, uint* b) {
 327     uint q0 = b[6];
 328     uint q1 = b[19];
 329     uint q2 = b[32];
 330     b[7] ^= a[1];
 331     b[21] ^= a[2];
 332     b[35] ^= a[3];
 333     b[10] ^= a[4];
 334     b[24] ^= a[5];
 335     b[38] ^= a[6];
 336     b[0] ^= a[7];
 337     b[14] ^= a[8];
 338     b[28] ^= a[9];
 339     b[3] ^= a[10];
 340     b[17] ^= a[11];
 341     b[31] ^= a[12];
 342     mill(a);
 343     a[13] ^= q0;
 344     a[14] ^= q1;
 345     a[15] ^= q2;
 346   }
 347
 348   void belt_07 (uint* a, uint* b) {
 349     uint q0 = b[5];
 350     uint q1 = b[18];
 351     uint q2 = b[31];
 352     b[6] ^= a[1];
 353     b[20] ^= a[2];
 354     b[34] ^= a[3];
 355     b[9] ^= a[4];
 356     b[23] ^= a[5];
 357     b[37] ^= a[6];
 358     b[12] ^= a[7];
 359     b[13] ^= a[8];
 360     b[27] ^= a[9];
 361     b[2] ^= a[10];
 362     b[16] ^= a[11];
 363     b[30] ^= a[12];
 364     mill(a);
 365     a[13] ^= q0;
 366     a[14] ^= q1;
 367     a[15] ^= q2;
 368   }
 369
 370   void belt_08 (uint* a, uint* b) {
 371     uint q0 = b[4];
 372     uint q1 = b[17];
 373     uint q2 = b[30];
 374     b[5] ^= a[1];
 375     b[19] ^= a[2];
 376     b[33] ^= a[3];
 377     b[8] ^= a[4];
 378     b[22] ^= a[5];
 379     b[36] ^= a[6];
 380     b[11] ^= a[7];
 381     b[25] ^= a[8];
 382     b[26] ^= a[9];
 383     b[1] ^= a[10];
 384     b[15] ^= a[11];
 385     b[29] ^= a[12];
 386     mill(a);
 387     a[13] ^= q0;
 388     a[14] ^= q1;
 389     a[15] ^= q2;
 390   }
 391
 392   void belt_09 (uint* a, uint* b) {
 393     uint q0 = b[3];
 394     uint q1 = b[16];
 395     uint q2 = b[29];
 396     b[4] ^= a[1];
 397     b[18] ^= a[2];
 398     b[32] ^= a[3];
 399     b[7] ^= a[4];
 400     b[21] ^= a[5];
 401     b[35] ^= a[6];
 402     b[10] ^= a[7];
 403     b[24] ^= a[8];
 404     b[38] ^= a[9];
 405     b[0] ^= a[10];
 406     b[14] ^= a[11];
 407     b[28] ^= a[12];
 408     mill(a);
 409     a[13] ^= q0;
 410     a[14] ^= q1;
 411     a[15] ^= q2;
 412   }
 413
 414   void belt_10 (uint* a, uint* b) {
 415     uint q0 = b[2];
 416     uint q1 = b[15];
 417     uint q2 = b[28];
 418     b[3] ^= a[1];
 419     b[17] ^= a[2];
 420     b[31] ^= a[3];
 421     b[6] ^= a[4];
 422     b[20] ^= a[5];
 423     b[34] ^= a[6];
 424     b[9] ^= a[7];
 425     b[23] ^= a[8];
 426     b[37] ^= a[9];
 427     b[12] ^= a[10];
 428     b[13] ^= a[11];
 429     b[27] ^= a[12];
 430     mill(a);
 431     a[13] ^= q0;
 432     a[14] ^= q1;
 433     a[15] ^= q2;
 434   }
 435
 436   void belt_11 (uint* a, uint* b) {
 437     uint q0 = b[1];
 438     uint q1 = b[14];
 439     uint q2 = b[27];
 440     b[2] ^= a[1];
 441     b[16] ^= a[2];
 442     b[30] ^= a[3];
 443     b[5] ^= a[4];
 444     b[19] ^= a[5];
 445     b[33] ^= a[6];
 446     b[8] ^= a[7];
 447     b[22] ^= a[8];
 448     b[36] ^= a[9];
 449     b[11] ^= a[10];
 450     b[25] ^= a[11];
 451     b[26] ^= a[12];
 452     mill(a);
 453     a[13] ^= q0;
 454     a[14] ^= q1;
 455     a[15] ^= q2;
 456   }
 457
 458   void belt_12 (uint* a, uint* b) {
 459     uint q0 = b[0];
 460     uint q1 = b[13];
 461     uint q2 = b[26];
 462     b[1] ^= a[1];
 463     b[15] ^= a[2];
 464     b[29] ^= a[3];
 465     b[4] ^= a[4];
 466     b[18] ^= a[5];
 467     b[32] ^= a[6];
 468     b[7] ^= a[7];
 469     b[21] ^= a[8];
 470     b[35] ^= a[9];
 471     b[10] ^= a[10];
 472     b[24] ^= a[11];
 473     b[38] ^= a[12];
 474     mill(a);
 475     a[13] ^= q0;
 476     a[14] ^= q1;
 477     a[15] ^= q2;
 478   }
 479
 480   void rground (uint* a, uint* b, int offset) {
 481     final switch (offset) {
 482       case 0: belt_00(a, b); return;
 483       case 1: belt_01(a, b); return;
 484       case 2: belt_02(a, b); return;
 485       case 3: belt_03(a, b); return;
 486       case 4: belt_04(a, b); return;
 487       case 5: belt_05(a, b); return;
 488       case 6: belt_06(a, b); return;
 489       case 7: belt_07(a, b); return;
 490       case 8: belt_08(a, b); return;
 491       case 9: belt_09(a, b); return;
 492       case 10: belt_10(a, b); return;
 493       case 11: belt_11(a, b); return;
 494       case 12: belt_12(a, b); return;
 495     }
 496   }
 497 }
 498
 499
 500 ubyte[RG32Hash.ByteSize] RG32HashOf(T) (const(T)[] data) nothrow @trusted @nogc if (T.sizeof == 1) {
 501   RG32Hash h;
 502   h.put(data);
 503   return h.finish();
 504 }
 505
 506
 507 ubyte[RG32Hash.ByteSize] RG32HashOf(T) (const(T)[] data) nothrow @trusted @nogc if (T.sizeof > 1) {
 508   RG32Hash h;
 509   h.put((cast(const(ubyte)*)data.ptr)[0..data.length*T.sizeof]);
 510   return h.finish();
 511 }
 512
 513
 514 version(rg32_test) {
 515   enum xhash = RG32HashOf("Alice & Miriel");
 516   static assert(cast(string)xhash == x"ebcd82ad5b21cc5ac6ca1f707faad10fe047963aa9e5cb35150a8bf2120bee4a");
 517 }
 518
 519
 520 version(rg32_test) void main () {
 521   static immutable string xres = x"ebcd82ad5b21cc5ac6ca1f707faad10fe047963aa9e5cb35150a8bf2120bee4a";
 522   auto hash = RG32HashOf("Alice & Miriel");
 523   { import core.stdc.stdio; foreach (ubyte b; hash[]) printf("%02x", b); printf("\n"); }
 524   assert(hash[] == cast(const(ubyte)[])xres);
 525 }