lib/collisiondetect/lib/libdetectcoll.c

   1 /**************************************************************************\
   2 |
   3 |    Copyright (C) 2012 CWI
   4 |
   5 |    Contact:
   6 |    Marc Stevens
   7 |    Cryptology Group
   8 |    Centrum Wiskunde & Informatica
   9 |    P.O. Box 94079, 1090 GB Amsterdam, Netherlands
  10 |    marc@marc-stevens.nl
  11 |
  12 |  Permission is hereby granted, free of charge, to any person obtaining a copy
  13 |  of this software and associated documentation files (the "Software"), to deal
  14 |  in the Software without restriction, including without limitation the rights
  15 |  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  16 |  copies of the Software, and to permit persons to whom the Software is
  17 |  furnished to do so, subject to the following conditions:
  18 |
  19 |  The above copyright notice and this permission notice shall be included in
  20 |  all copies or substantial portions of the Software.
  21 |
  22 |  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  23 |  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  24 |  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  25 |  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  26 |  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  27 |  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  28 |  THE SOFTWARE.
  29 |
  30 \**************************************************************************/
  31
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 #include "libdetectcoll.h"
  37
  38 #define rotate_right(x,n) (((x)>>(n))|((x)<<(32-(n))))
  39 #define rotate_left(x,n)  (((x)<<(n))|((x)>>(32-(n))))
  40
  41 void swap_bytes(uint32_t val[16]) {
  42         unsigned i;
  43         for (i = 0; i < 16; ++i) {
  44                 val[i] = ((val[i]<<8)&0xFF00FF00)|((val[i]>>8)&0xFF00FF);
  45                 val[i] = (val[i]<<16) | (val[i]>>16);
  46         }
  47 }
  48
  49 const unsigned md5_wt[] =
  50         { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
  51         , 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12
  52         , 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2
  53         , 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 };
  54 #define md5_ff(b,c,d) ((d) ^ ((b) & ((c) ^ (d))))
  55 #define md5_gg(b,c,d) ((c) ^ ((d) & ((b) ^ (c))))
  56 #define md5_hh(b,c,d) ((b) ^ (c) ^ (d))
  57 #define md5_ii(b,c,d) ((c) ^ ((b) | ~(d)))
  58 #define HASHUTIL5_MD5COMPRESS_STEP(f, a, b, c, d, m, ac, rc) \
  59         a += f(b, c, d) + m + ac; a = rotate_left(a,rc); a += b;
  60 #define HASHUTIL5_MD5COMPRESS_STEP_BW(f, a, b, c, d, m, ac, rc) \
  61         a -= b; a = rotate_right(a,rc); a -= f(b,c,d) + m + ac;
  62
  63 #define sha1_f1(b,c,d) ((d)^((b)&((c)^(d))))
  64 #define sha1_f2(b,c,d) ((b)^(c)^(d))
  65 #define sha1_f3(b,c,d) (((b) & ((c)|(d))) | ((c)&(d)))
  66 #define sha1_f4(b,c,d) ((b)^(c)^(d))
  67 #define HASHCLASH_SHA1COMPRESS_ROUND1_STEP(a, b, c, d, e, m, t) \
  68         e += rotate_left(a, 5) + sha1_f1(b,c,d) + 0x5A827999 + m[t]; b = rotate_left(b, 30);
  69 #define HASHCLASH_SHA1COMPRESS_ROUND2_STEP(a, b, c, d, e, m, t) \
  70         e += rotate_left(a, 5) + sha1_f2(b,c,d) + 0x6ED9EBA1 + m[t]; b = rotate_left(b, 30);
  71 #define HASHCLASH_SHA1COMPRESS_ROUND3_STEP(a, b, c, d, e, m, t) \
  72         e += rotate_left(a, 5) + sha1_f3(b,c,d) + 0x8F1BBCDC + m[t]; b = rotate_left(b, 30);
  73 #define HASHCLASH_SHA1COMPRESS_ROUND4_STEP(a, b, c, d, e, m, t) \
  74         e += rotate_left(a, 5) + sha1_f4(b,c,d) + 0xCA62C1D6 + m[t]; b = rotate_left(b, 30);
  75 #define HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW(a, b, c, d, e, m, t) \
  76         b = rotate_right(b, 30); e -= rotate_left(a, 5) + sha1_f1(b,c,d) + 0x5A827999 + m[t];
  77 #define HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW(a, b, c, d, e, m, t) \
  78         b = rotate_right(b, 30); e -= rotate_left(a, 5) + sha1_f2(b,c,d) + 0x6ED9EBA1 + m[t];
  79 #define HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW(a, b, c, d, e, m, t) \
  80         b = rotate_right(b, 30); e -= rotate_left(a, 5) + sha1_f3(b,c,d) + 0x8F1BBCDC + m[t];
  81 #define HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW(a, b, c, d, e, m, t) \
  82         b = rotate_right(b, 30); e -= rotate_left(a, 5) + sha1_f4(b,c,d) + 0xCA62C1D6 + m[t];
  83
  84 #define STORE_STATE(i) states[(4*(i))] = a; states[(4*(i))+1] = b; states[(4*(i))+2] = c; states[(4*(i))+3] = d;
  85 #define LOAD_STATE(i)  a = states[(4*(i))]; b = states[(4*(i))+1]; c = states[(4*(i))+2]; d = states[(4*(i))+3];
  86
  87 #define SHA1_STORE_STATE(i) states[(5*(i))] = a; states[(5*(i))+1] = b; states[(5*(i))+2] = c; states[(5*(i))+3] = d; states[(5*(i))+4] = e;
  88 #define SHA1_LOAD_STATE(i)  a = states[(4*(i))]; b = states[(4*(i))+1]; c = states[(4*(i))+2]; d = states[(4*(i))+3]; e = states[(5*(i))+4];
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99 void sha1compress_me(const uint32_t block[16], uint32_t me[80]) {
 100         unsigned i;
 101         if ( (const uint32_t*)(block) != (const uint32_t*)(me) )
 102                 memcpy(me, block, 64);
 103         for (i = 16; i < 80; ++i)
 104                 me[i]=rotate_left(me[i-3] ^ me[i-8] ^ me[i-14] ^ me[i-16], 1);
 105 }
 106
 107 void sha1compress_states(uint32_t ihv[5], const uint32_t me[80], uint32_t states[81*5]) {
 108         uint32_t a = ihv[0], b = ihv[1], c = ihv[2], d = ihv[3], e = ihv[4];
 109
 110         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( a, b, c, d, e, me,  0 );
 111         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( e, a, b, c, d, me,  1 );
 112         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( d, e, a, b, c, me,  2 );
 113         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( c, d, e, a, b, me,  3 );
 114         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( b, c, d, e, a, me,  4 );
 115         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( a, b, c, d, e, me,  5 );
 116         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( e, a, b, c, d, me,  6 );
 117         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( d, e, a, b, c, me,  7 );
 118         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( c, d, e, a, b, me,  8 );
 119         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( b, c, d, e, a, me,  9 );
 120         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( a, b, c, d, e, me, 10 );
 121         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( e, a, b, c, d, me, 11 );
 122         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( d, e, a, b, c, me, 12 );
 123         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( c, d, e, a, b, me, 13 );
 124         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( b, c, d, e, a, me, 14 );
 125         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( a, b, c, d, e, me, 15 );
 126         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( e, a, b, c, d, me, 16 );
 127         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( d, e, a, b, c, me, 17 );
 128         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( c, d, e, a, b, me, 18 );
 129         HASHCLASH_SHA1COMPRESS_ROUND1_STEP( b, c, d, e, a, me, 19 );
 130
 131 //      SHA1_STORE_STATE(20);
 132         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( a, b, c, d, e, me, 20 );
 133 //      SHA1_STORE_STATE(21);
 134         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( e, a, b, c, d, me, 21 );
 135 //      SHA1_STORE_STATE(22);
 136         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( d, e, a, b, c, me, 22 );
 137 //      SHA1_STORE_STATE(23);
 138         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( c, d, e, a, b, me, 23 );
 139 //      SHA1_STORE_STATE(24);
 140         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( b, c, d, e, a, me, 24 );
 141 //      SHA1_STORE_STATE(25);
 142         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( a, b, c, d, e, me, 25 );
 143 //      SHA1_STORE_STATE(26);
 144         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( e, a, b, c, d, me, 26 );
 145 //      SHA1_STORE_STATE(27);
 146         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( d, e, a, b, c, me, 27 );
 147 //      SHA1_STORE_STATE(28);
 148         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( c, d, e, a, b, me, 28 );
 149 //      SHA1_STORE_STATE(29);
 150         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( b, c, d, e, a, me, 29 );
 151 //      SHA1_STORE_STATE(30);
 152         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( a, b, c, d, e, me, 30 );
 153 //      SHA1_STORE_STATE(31);
 154         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( e, a, b, c, d, me, 31 );
 155 //      SHA1_STORE_STATE(32);
 156         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( d, e, a, b, c, me, 32 );
 157 //      SHA1_STORE_STATE(33);
 158         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( c, d, e, a, b, me, 33 );
 159 //      SHA1_STORE_STATE(34);
 160         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( b, c, d, e, a, me, 34 );
 161 //      SHA1_STORE_STATE(35);
 162         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( a, b, c, d, e, me, 35 );
 163 //      SHA1_STORE_STATE(36);
 164         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( e, a, b, c, d, me, 36 );
 165 //      SHA1_STORE_STATE(37);
 166         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( d, e, a, b, c, me, 37 );
 167 //      SHA1_STORE_STATE(38);
 168         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( c, d, e, a, b, me, 38 );
 169 //      SHA1_STORE_STATE(39);
 170         HASHCLASH_SHA1COMPRESS_ROUND2_STEP( b, c, d, e, a, me, 39 );
 171
 172 //      SHA1_STORE_STATE(40);
 173         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( a, b, c, d, e, me, 40 );
 174 //      SHA1_STORE_STATE(41);
 175         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( e, a, b, c, d, me, 41 );
 176 //      SHA1_STORE_STATE(42);
 177         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( d, e, a, b, c, me, 42 );
 178 //      SHA1_STORE_STATE(43);
 179         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( c, d, e, a, b, me, 43 );
 180 //      SHA1_STORE_STATE(44);
 181         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( b, c, d, e, a, me, 44 );
 182 //      SHA1_STORE_STATE(45);
 183         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( a, b, c, d, e, me, 45 );
 184 //      SHA1_STORE_STATE(46);
 185         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( e, a, b, c, d, me, 46 );
 186 //      SHA1_STORE_STATE(47);
 187         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( d, e, a, b, c, me, 47 );
 188 //      SHA1_STORE_STATE(48);
 189         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( c, d, e, a, b, me, 48 );
 190 //      SHA1_STORE_STATE(49);
 191         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( b, c, d, e, a, me, 49 );
 192 //      SHA1_STORE_STATE(50);
 193         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( a, b, c, d, e, me, 50 );
 194 //      SHA1_STORE_STATE(51);
 195         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( e, a, b, c, d, me, 51 );
 196 //      SHA1_STORE_STATE(52);
 197         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( d, e, a, b, c, me, 52 );
 198 //      SHA1_STORE_STATE(53);
 199         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( c, d, e, a, b, me, 53 );
 200 //      SHA1_STORE_STATE(54);
 201         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( b, c, d, e, a, me, 54 );
 202 //      SHA1_STORE_STATE(55);
 203         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( a, b, c, d, e, me, 55 );
 204 //      SHA1_STORE_STATE(56);
 205         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( e, a, b, c, d, me, 56 );
 206 //      SHA1_STORE_STATE(57);
 207         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( d, e, a, b, c, me, 57 );
 208 //      SHA1_STORE_STATE(58);
 209         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( c, d, e, a, b, me, 58 );
 210         SHA1_STORE_STATE(59);
 211         HASHCLASH_SHA1COMPRESS_ROUND3_STEP( b, c, d, e, a, me, 59 );
 212
 213         SHA1_STORE_STATE(60);
 214         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( a, b, c, d, e, me, 60 );
 215         SHA1_STORE_STATE(61);
 216         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( e, a, b, c, d, me, 61 );
 217         SHA1_STORE_STATE(62);
 218         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( d, e, a, b, c, me, 62 );
 219         SHA1_STORE_STATE(63);
 220         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( c, d, e, a, b, me, 63 );
 221         SHA1_STORE_STATE(64);
 222         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( b, c, d, e, a, me, 64 );
 223         SHA1_STORE_STATE(65);
 224         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( a, b, c, d, e, me, 65 );
 225         SHA1_STORE_STATE(66);
 226         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( e, a, b, c, d, me, 66 );
 227         SHA1_STORE_STATE(67);
 228         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( d, e, a, b, c, me, 67 );
 229         SHA1_STORE_STATE(68);
 230         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( c, d, e, a, b, me, 68 );
 231         SHA1_STORE_STATE(69);
 232         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( b, c, d, e, a, me, 69 );
 233         SHA1_STORE_STATE(70);
 234         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( a, b, c, d, e, me, 70 );
 235         SHA1_STORE_STATE(71);
 236         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( e, a, b, c, d, me, 71 );
 237         SHA1_STORE_STATE(72);
 238         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( d, e, a, b, c, me, 72 );
 239         SHA1_STORE_STATE(73);
 240         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( c, d, e, a, b, me, 73 );
 241 //      SHA1_STORE_STATE(74);
 242         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( b, c, d, e, a, me, 74 );
 243 //      SHA1_STORE_STATE(75);
 244         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( a, b, c, d, e, me, 75 );
 245 //      SHA1_STORE_STATE(76);
 246         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( e, a, b, c, d, me, 76 );
 247 //      SHA1_STORE_STATE(77);
 248         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( d, e, a, b, c, me, 77 );
 249 //      SHA1_STORE_STATE(78);
 250         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( c, d, e, a, b, me, 78 );
 251 //      SHA1_STORE_STATE(79);
 252         HASHCLASH_SHA1COMPRESS_ROUND4_STEP( b, c, d, e, a, me, 79 );
 253 //      SHA1_STORE_STATE(80);
 254
 255         ihv[0] += a; ihv[1] += b; ihv[2] += c; ihv[3] += d; ihv[4] += e;
 256 }
 257
 258 int sha1recompress_fast(unsigned t, uint32_t ihv[5], const uint32_t me[80], const uint32_t state[5], const uint32_t rihv[5]) {
 259         uint32_t a = state[0], b = state[1], c = state[2], d = state[3], e = state[4];
 260         switch (t) {
 261                 case 79: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( b, c, d, e, a, me, 79 );
 262                 case 78: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( c, d, e, a, b, me, 78 );
 263                 case 77: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( d, e, a, b, c, me, 77 );
 264                 case 76: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( e, a, b, c, d, me, 76 );
 265                 case 75: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( a, b, c, d, e, me, 75 );
 266                 case 74: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( b, c, d, e, a, me, 74 );
 267                 case 73: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( c, d, e, a, b, me, 73 );
 268                 case 72: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( d, e, a, b, c, me, 72 );
 269                 case 71: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( e, a, b, c, d, me, 71 );
 270                 case 70: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( a, b, c, d, e, me, 70 );
 271                 case 69: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( b, c, d, e, a, me, 69 );
 272                 case 68: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( c, d, e, a, b, me, 68 );
 273                 case 67: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( d, e, a, b, c, me, 67 );
 274                 case 66: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( e, a, b, c, d, me, 66 );
 275                 case 65: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( a, b, c, d, e, me, 65 );
 276                 case 64: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( b, c, d, e, a, me, 64 );
 277                 case 63: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( c, d, e, a, b, me, 63 );
 278                 case 62: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( d, e, a, b, c, me, 62 );
 279                 case 61: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( e, a, b, c, d, me, 61 );
 280                 case 60: HASHCLASH_SHA1COMPRESS_ROUND4_STEP_BW( a, b, c, d, e, me, 60 );
 281                 case 59: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( b, c, d, e, a, me, 59 );
 282                 case 58: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( c, d, e, a, b, me, 58 );
 283                 case 57: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( d, e, a, b, c, me, 57 );
 284                 case 56: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( e, a, b, c, d, me, 56 );
 285                 case 55: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( a, b, c, d, e, me, 55 );
 286                 case 54: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( b, c, d, e, a, me, 54 );
 287                 case 53: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( c, d, e, a, b, me, 53 );
 288                 case 52: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( d, e, a, b, c, me, 52 );
 289                 case 51: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( e, a, b, c, d, me, 51 );
 290                 case 50: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( a, b, c, d, e, me, 50 );
 291                 case 49: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( b, c, d, e, a, me, 49 );
 292                 case 48: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( c, d, e, a, b, me, 48 );
 293                 case 47: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( d, e, a, b, c, me, 47 );
 294                 case 46: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( e, a, b, c, d, me, 46 );
 295                 case 45: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( a, b, c, d, e, me, 45 );
 296                 case 44: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( b, c, d, e, a, me, 44 );
 297                 case 43: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( c, d, e, a, b, me, 43 );
 298                 case 42: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( d, e, a, b, c, me, 42 );
 299                 case 41: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( e, a, b, c, d, me, 41 );
 300                 case 40: HASHCLASH_SHA1COMPRESS_ROUND3_STEP_BW( a, b, c, d, e, me, 40 );
 301                 case 39: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( b, c, d, e, a, me, 39 );
 302                 case 38: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( c, d, e, a, b, me, 38 );
 303                 case 37: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( d, e, a, b, c, me, 37 );
 304                 case 36: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( e, a, b, c, d, me, 36 );
 305                 case 35: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( a, b, c, d, e, me, 35 );
 306                 case 34: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( b, c, d, e, a, me, 34 );
 307                 case 33: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( c, d, e, a, b, me, 33 );
 308                 case 32: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( d, e, a, b, c, me, 32 );
 309                 case 31: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( e, a, b, c, d, me, 31 );
 310                 case 30: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( a, b, c, d, e, me, 30 );
 311                 case 29: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( b, c, d, e, a, me, 29 );
 312                 case 28: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( c, d, e, a, b, me, 28 );
 313                 case 27: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( d, e, a, b, c, me, 27 );
 314                 case 26: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( e, a, b, c, d, me, 26 );
 315                 case 25: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( a, b, c, d, e, me, 25 );
 316                 case 24: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( b, c, d, e, a, me, 24 );
 317                 case 23: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( c, d, e, a, b, me, 23 );
 318                 case 22: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( d, e, a, b, c, me, 22 );
 319                 case 21: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( e, a, b, c, d, me, 21 );
 320                 case 20: HASHCLASH_SHA1COMPRESS_ROUND2_STEP_BW( a, b, c, d, e, me, 20 );
 321                 case 19: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( b, c, d, e, a, me, 19 );
 322                 case 18: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( c, d, e, a, b, me, 18 );
 323                 case 17: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( d, e, a, b, c, me, 17 );
 324                 case 16: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( e, a, b, c, d, me, 16 );
 325                 case 15: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( a, b, c, d, e, me, 15 );
 326                 case 14: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( b, c, d, e, a, me, 14 );
 327                 case 13: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( c, d, e, a, b, me, 13 );
 328                 case 12: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( d, e, a, b, c, me, 12 );
 329                 case 11: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( e, a, b, c, d, me, 11 );
 330                 case 10: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( a, b, c, d, e, me, 10 );
 331                 case 9: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( b, c, d, e, a, me,  9 );
 332                 case 8: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( c, d, e, a, b, me,  8 );
 333                 case 7: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( d, e, a, b, c, me,  7 );
 334                 case 6: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( e, a, b, c, d, me,  6 );
 335                 case 5: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( a, b, c, d, e, me,  5 );
 336                 case 4: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( b, c, d, e, a, me,  4 );
 337                 case 3: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( c, d, e, a, b, me,  3 );
 338                 case 2: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( d, e, a, b, c, me,  2 );
 339                 case 1: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( e, a, b, c, d, me,  1 );
 340                 case 0: HASHCLASH_SHA1COMPRESS_ROUND1_STEP_BW( a, b, c, d, e, me,  0 );
 341         }
 342         ihv[0] = a; ihv[1] = b; ihv[2] = c; ihv[3] = d; ihv[4] = e;
 343         a = state[0]; b = state[1]; c = state[2]; d = state[3]; e = state[4];
 344
 345         switch (t+1) {
 346                 case 0: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( a, b, c, d, e, me,  0 );
 347                 case 1: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( e, a, b, c, d, me,  1 );
 348                 case 2: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( d, e, a, b, c, me,  2 );
 349                 case 3: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( c, d, e, a, b, me,  3 );
 350                 case 4: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( b, c, d, e, a, me,  4 );
 351                 case 5: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( a, b, c, d, e, me,  5 );
 352                 case 6: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( e, a, b, c, d, me,  6 );
 353                 case 7: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( d, e, a, b, c, me,  7 );
 354                 case 8: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( c, d, e, a, b, me,  8 );
 355                 case 9: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( b, c, d, e, a, me,  9 );
 356                 case 10: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( a, b, c, d, e, me, 10 );
 357                 case 11: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( e, a, b, c, d, me, 11 );
 358                 case 12: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( d, e, a, b, c, me, 12 );
 359                 case 13: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( c, d, e, a, b, me, 13 );
 360                 case 14: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( b, c, d, e, a, me, 14 );
 361                 case 15: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( a, b, c, d, e, me, 15 );
 362                 case 16: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( e, a, b, c, d, me, 16 );
 363                 case 17: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( d, e, a, b, c, me, 17 );
 364                 case 18: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( c, d, e, a, b, me, 18 );
 365                 case 19: HASHCLASH_SHA1COMPRESS_ROUND1_STEP( b, c, d, e, a, me, 19 );
 366                 case 20: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( a, b, c, d, e, me, 20 );
 367                 case 21: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( e, a, b, c, d, me, 21 );
 368                 case 22: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( d, e, a, b, c, me, 22 );
 369                 case 23: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( c, d, e, a, b, me, 23 );
 370                 case 24: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( b, c, d, e, a, me, 24 );
 371                 case 25: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( a, b, c, d, e, me, 25 );
 372                 case 26: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( e, a, b, c, d, me, 26 );
 373                 case 27: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( d, e, a, b, c, me, 27 );
 374                 case 28: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( c, d, e, a, b, me, 28 );
 375                 case 29: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( b, c, d, e, a, me, 29 );
 376                 case 30: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( a, b, c, d, e, me, 30 );
 377                 case 31: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( e, a, b, c, d, me, 31 );
 378                 case 32: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( d, e, a, b, c, me, 32 );
 379                 case 33: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( c, d, e, a, b, me, 33 );
 380                 case 34: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( b, c, d, e, a, me, 34 );
 381                 case 35: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( a, b, c, d, e, me, 35 );
 382                 case 36: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( e, a, b, c, d, me, 36 );
 383                 case 37: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( d, e, a, b, c, me, 37 );
 384                 case 38: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( c, d, e, a, b, me, 38 );
 385                 case 39: HASHCLASH_SHA1COMPRESS_ROUND2_STEP( b, c, d, e, a, me, 39 );
 386                 case 40: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( a, b, c, d, e, me, 40 );
 387                 case 41: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( e, a, b, c, d, me, 41 );
 388                 case 42: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( d, e, a, b, c, me, 42 );
 389                 case 43: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( c, d, e, a, b, me, 43 );
 390                 case 44: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( b, c, d, e, a, me, 44 );
 391                 case 45: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( a, b, c, d, e, me, 45 );
 392                 case 46: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( e, a, b, c, d, me, 46 );
 393                 case 47: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( d, e, a, b, c, me, 47 );
 394                 case 48: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( c, d, e, a, b, me, 48 );
 395                 case 49: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( b, c, d, e, a, me, 49 );
 396                 case 50: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( a, b, c, d, e, me, 50 );
 397                 case 51: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( e, a, b, c, d, me, 51 );
 398                 case 52: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( d, e, a, b, c, me, 52 );
 399                 case 53: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( c, d, e, a, b, me, 53 );
 400                 case 54: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( b, c, d, e, a, me, 54 );
 401                 case 55: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( a, b, c, d, e, me, 55 );
 402                 case 56: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( e, a, b, c, d, me, 56 );
 403                 case 57: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( d, e, a, b, c, me, 57 );
 404                 case 58: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( c, d, e, a, b, me, 58 );
 405                 case 59: HASHCLASH_SHA1COMPRESS_ROUND3_STEP( b, c, d, e, a, me, 59 );
 406                 case 60: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( a, b, c, d, e, me, 60 );
 407                 case 61: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( e, a, b, c, d, me, 61 );
 408                 case 62: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( d, e, a, b, c, me, 62 );
 409                 case 63: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( c, d, e, a, b, me, 63 );
 410                 case 64: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( b, c, d, e, a, me, 64 );
 411                 case 65: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( a, b, c, d, e, me, 65 );
 412                 case 66: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( e, a, b, c, d, me, 66 );
 413                 case 67: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( d, e, a, b, c, me, 67 );
 414                 case 68: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( c, d, e, a, b, me, 68 );
 415                 case 69: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( b, c, d, e, a, me, 69 );
 416                 case 70: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( a, b, c, d, e, me, 70 );
 417                 case 71: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( e, a, b, c, d, me, 71 );
 418                 case 72: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( d, e, a, b, c, me, 72 );
 419                 case 73: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( c, d, e, a, b, me, 73 );
 420                 case 74: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( b, c, d, e, a, me, 74 );
 421                 case 75: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( a, b, c, d, e, me, 75 );
 422                 case 76: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( e, a, b, c, d, me, 76 );
 423                 case 77: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( d, e, a, b, c, me, 77 );
 424                 case 78: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( c, d, e, a, b, me, 78 );
 425                 case 79: HASHCLASH_SHA1COMPRESS_ROUND4_STEP( b, c, d, e, a, me, 79 );
 426         }
 427         return (rihv[0] == ihv[0]+a && rihv[1] == ihv[1]+b && rihv[2] == ihv[2]+c && rihv[3] == ihv[3]+d && rihv[4] == ihv[4]+e);
 428 }
 429
 430 typedef struct {
 431         int dvtype;
 432         int dvK;
 433         int dvB;
 434 } sha1_dv_t;
 435 sha1_dv_t sha1_dvs[] = {
 436         { 1, 46, 0 },
 437         { 1, 47, 0 },
 438         { 1, 48, 0 },
 439         { 1, 49, 0 },
 440         { 1, 50, 0 },
 441         { 1, 51, 0 },
 442         { 1, 48, 2 },
 443         { 1, 49, 2 },
 444         { 1, 50, 2 },
 445         { 2, 45, 0 },
 446         { 2, 46, 0 },
 447         { 2, 47, 0 },
 448         { 2, 48, 0 },
 449         { 2, 49, 0 },
 450         { 2, 50, 0 },
 451         { 2, 51, 0 },
 452         { 2, 52, 0 },
 453         { 2, 53, 0 },
 454         { 2, 54, 0 },
 455         { 2, 56 ,0 },
 456         { 2, 57, 0 },
 457         { 2, 58, 0 },
 458         { 0, 0, 0} // end of table marker
 459 };
 460
 461 const uint32_t sha1_dv_xm_table[][80] = {
 462 {  0x2c000010, 0xf4000014, 0xb4000008, 0x08000000, 0x9800000c, 0xd8000010, 0x08000010, 0xb8000010, 0x98000000, 0x60000000, 0x00000008, 0xc0000000, 0x90000014, 0x10000010, 0xb8000014, 0x28000000, 0x20000010, 0x48000000, 0x08000018, 0x60000000, 0x90000010, 0xf0000010, 0x90000008, 0xc0000000, 0x90000010, 0xf0000010, 0xb0000008, 0x40000000, 0x90000000, 0xf0000010, 0x90000018, 0x60000000, 0x90000010, 0x90000010, 0x90000000, 0x80000000, 0x00000010, 0xa0000000, 0x20000000, 0xa0000000, 0x20000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x20000000, 0x00000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000040, 0x40000002, 0x80000004, 0x80000080, 0x80000006, 0x00000049, 0x00000103, 0x80000009, 0x80000012, 0x80000202, 0x00000018, 0x00000164, 0x00000408, 0x800000e6, 0x8000004c},
 463 {  0xc8000010, 0x2c000010, 0xf4000014, 0xb4000008, 0x08000000, 0x9800000c, 0xd8000010, 0x08000010, 0xb8000010, 0x98000000, 0x60000000, 0x00000008, 0xc0000000, 0x90000014, 0x10000010, 0xb8000014, 0x28000000, 0x20000010, 0x48000000, 0x08000018, 0x60000000, 0x90000010, 0xf0000010, 0x90000008, 0xc0000000, 0x90000010, 0xf0000010, 0xb0000008, 0x40000000, 0x90000000, 0xf0000010, 0x90000018, 0x60000000, 0x90000010, 0x90000010, 0x90000000, 0x80000000, 0x00000010, 0xa0000000, 0x20000000, 0xa0000000, 0x20000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x20000000, 0x00000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000040, 0x40000002, 0x80000004, 0x80000080, 0x80000006, 0x00000049, 0x00000103, 0x80000009, 0x80000012, 0x80000202, 0x00000018, 0x00000164, 0x00000408, 0x800000e6},
 464 {  0xb800000a, 0xc8000010, 0x2c000010, 0xf4000014, 0xb4000008, 0x08000000, 0x9800000c, 0xd8000010, 0x08000010, 0xb8000010, 0x98000000, 0x60000000, 0x00000008, 0xc0000000, 0x90000014, 0x10000010, 0xb8000014, 0x28000000, 0x20000010, 0x48000000, 0x08000018, 0x60000000, 0x90000010, 0xf0000010, 0x90000008, 0xc0000000, 0x90000010, 0xf0000010, 0xb0000008, 0x40000000, 0x90000000, 0xf0000010, 0x90000018, 0x60000000, 0x90000010, 0x90000010, 0x90000000, 0x80000000, 0x00000010, 0xa0000000, 0x20000000, 0xa0000000, 0x20000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x20000000, 0x00000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000040, 0x40000002, 0x80000004, 0x80000080, 0x80000006, 0x00000049, 0x00000103, 0x80000009, 0x80000012, 0x80000202, 0x00000018, 0x00000164, 0x00000408},
 465 {  0x18000000, 0xb800000a, 0xc8000010, 0x2c000010, 0xf4000014, 0xb4000008, 0x08000000, 0x9800000c, 0xd8000010, 0x08000010, 0xb8000010, 0x98000000, 0x60000000, 0x00000008, 0xc0000000, 0x90000014, 0x10000010, 0xb8000014, 0x28000000, 0x20000010, 0x48000000, 0x08000018, 0x60000000, 0x90000010, 0xf0000010, 0x90000008, 0xc0000000, 0x90000010, 0xf0000010, 0xb0000008, 0x40000000, 0x90000000, 0xf0000010, 0x90000018, 0x60000000, 0x90000010, 0x90000010, 0x90000000, 0x80000000, 0x00000010, 0xa0000000, 0x20000000, 0xa0000000, 0x20000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x20000000, 0x00000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000040, 0x40000002, 0x80000004, 0x80000080, 0x80000006, 0x00000049, 0x00000103, 0x80000009, 0x80000012, 0x80000202, 0x00000018, 0x00000164},
 466 {  0x0800000c, 0x18000000, 0xb800000a, 0xc8000010, 0x2c000010, 0xf4000014, 0xb4000008, 0x08000000, 0x9800000c, 0xd8000010, 0x08000010, 0xb8000010, 0x98000000, 0x60000000, 0x00000008, 0xc0000000, 0x90000014, 0x10000010, 0xb8000014, 0x28000000, 0x20000010, 0x48000000, 0x08000018, 0x60000000, 0x90000010, 0xf0000010, 0x90000008, 0xc0000000, 0x90000010, 0xf0000010, 0xb0000008, 0x40000000, 0x90000000, 0xf0000010, 0x90000018, 0x60000000, 0x90000010, 0x90000010, 0x90000000, 0x80000000, 0x00000010, 0xa0000000, 0x20000000, 0xa0000000, 0x20000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x20000000, 0x00000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000040, 0x40000002, 0x80000004, 0x80000080, 0x80000006, 0x00000049, 0x00000103, 0x80000009, 0x80000012, 0x80000202, 0x00000018},
 467 {  0xe8000000, 0x0800000c, 0x18000000, 0xb800000a, 0xc8000010, 0x2c000010, 0xf4000014, 0xb4000008, 0x08000000, 0x9800000c, 0xd8000010, 0x08000010, 0xb8000010, 0x98000000, 0x60000000, 0x00000008, 0xc0000000, 0x90000014, 0x10000010, 0xb8000014, 0x28000000, 0x20000010, 0x48000000, 0x08000018, 0x60000000, 0x90000010, 0xf0000010, 0x90000008, 0xc0000000, 0x90000010, 0xf0000010, 0xb0000008, 0x40000000, 0x90000000, 0xf0000010, 0x90000018, 0x60000000, 0x90000010, 0x90000010, 0x90000000, 0x80000000, 0x00000010, 0xa0000000, 0x20000000, 0xa0000000, 0x20000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x20000000, 0x00000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000040, 0x40000002, 0x80000004, 0x80000080, 0x80000006, 0x00000049, 0x00000103, 0x80000009, 0x80000012, 0x80000202},
 468 {  0xe000002a, 0x20000043, 0xb0000040, 0xd0000053, 0xd0000022, 0x20000000, 0x60000032, 0x60000043, 0x20000040, 0xe0000042, 0x60000002, 0x80000001, 0x00000020, 0x00000003, 0x40000052, 0x40000040, 0xe0000052, 0xa0000000, 0x80000040, 0x20000001, 0x20000060, 0x80000001, 0x40000042, 0xc0000043, 0x40000022, 0x00000003, 0x40000042, 0xc0000043, 0xc0000022, 0x00000001, 0x40000002, 0xc0000043, 0x40000062, 0x80000001, 0x40000042, 0x40000042, 0x40000002, 0x00000002, 0x00000040, 0x80000002, 0x80000000, 0x80000002, 0x80000040, 0x00000000, 0x80000040, 0x80000000, 0x00000040, 0x80000000, 0x00000040, 0x80000002, 0x00000000, 0x80000000, 0x80000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000004, 0x00000080, 0x00000004, 0x00000009, 0x00000101, 0x00000009, 0x00000012, 0x00000202, 0x0000001a, 0x00000124, 0x0000040c, 0x00000026, 0x0000004a, 0x0000080a, 0x00000060, 0x00000590, 0x00001020},
 469 {  0x60000000, 0xe000002a, 0x20000043, 0xb0000040, 0xd0000053, 0xd0000022, 0x20000000, 0x60000032, 0x60000043, 0x20000040, 0xe0000042, 0x60000002, 0x80000001, 0x00000020, 0x00000003, 0x40000052, 0x40000040, 0xe0000052, 0xa0000000, 0x80000040, 0x20000001, 0x20000060, 0x80000001, 0x40000042, 0xc0000043, 0x40000022, 0x00000003, 0x40000042, 0xc0000043, 0xc0000022, 0x00000001, 0x40000002, 0xc0000043, 0x40000062, 0x80000001, 0x40000042, 0x40000042, 0x40000002, 0x00000002, 0x00000040, 0x80000002, 0x80000000, 0x80000002, 0x80000040, 0x00000000, 0x80000040, 0x80000000, 0x00000040, 0x80000000, 0x00000040, 0x80000002, 0x00000000, 0x80000000, 0x80000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000004, 0x00000080, 0x00000004, 0x00000009, 0x00000101, 0x00000009, 0x00000012, 0x00000202, 0x0000001a, 0x00000124, 0x0000040c, 0x00000026, 0x0000004a, 0x0000080a, 0x00000060, 0x00000590},
 470 {  0x20000030, 0x60000000, 0xe000002a, 0x20000043, 0xb0000040, 0xd0000053, 0xd0000022, 0x20000000, 0x60000032, 0x60000043, 0x20000040, 0xe0000042, 0x60000002, 0x80000001, 0x00000020, 0x00000003, 0x40000052, 0x40000040, 0xe0000052, 0xa0000000, 0x80000040, 0x20000001, 0x20000060, 0x80000001, 0x40000042, 0xc0000043, 0x40000022, 0x00000003, 0x40000042, 0xc0000043, 0xc0000022, 0x00000001, 0x40000002, 0xc0000043, 0x40000062, 0x80000001, 0x40000042, 0x40000042, 0x40000002, 0x00000002, 0x00000040, 0x80000002, 0x80000000, 0x80000002, 0x80000040, 0x00000000, 0x80000040, 0x80000000, 0x00000040, 0x80000000, 0x00000040, 0x80000002, 0x00000000, 0x80000000, 0x80000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000004, 0x00000080, 0x00000004, 0x00000009, 0x00000101, 0x00000009, 0x00000012, 0x00000202, 0x0000001a, 0x00000124, 0x0000040c, 0x00000026, 0x0000004a, 0x0000080a, 0x00000060},
 471 {  0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089, 0x00000014, 0x8000024b, 0x0000011b, 0x8000016d, 0x8000041a, 0x000002e4, 0x80000054, 0x00000967},
 472 {  0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089, 0x00000014, 0x8000024b, 0x0000011b, 0x8000016d, 0x8000041a, 0x000002e4, 0x80000054},
 473 {  0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089, 0x00000014, 0x8000024b, 0x0000011b, 0x8000016d, 0x8000041a, 0x000002e4},
 474 {  0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089, 0x00000014, 0x8000024b, 0x0000011b, 0x8000016d, 0x8000041a},
 475 {  0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089, 0x00000014, 0x8000024b, 0x0000011b, 0x8000016d},
 476 {  0xb400001c, 0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089, 0x00000014, 0x8000024b, 0x0000011b},
 477 {  0xc0000010, 0xb400001c, 0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089, 0x00000014, 0x8000024b},
 478 {  0x0c000002, 0xc0000010, 0xb400001c, 0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089, 0x00000014},
 479 {  0xcc000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107, 0x00000089},
 480 {  0x0400001c, 0xcc000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046, 0x4000004b, 0x80000107},
 481 {  0x2600001a, 0x00000010, 0x0400001c, 0xcc000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082, 0xc0000046},
 482 {  0x26000014, 0x2600001a, 0x00000010, 0x0400001c, 0xcc000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005, 0xc0000082},
 483 {  0x2400001c, 0x26000014, 0x2600001a, 0x00000010, 0x0400001c, 0xcc000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x3c000004, 0xbc00001a, 0x20000010, 0x2400001c, 0xec000014, 0x0c000002, 0xc0000010, 0xb400001c, 0x2c000004, 0xbc000018, 0xb0000010, 0x0000000c, 0xb8000010, 0x08000018, 0x78000010, 0x08000014, 0x70000010, 0xb800001c, 0xe8000000, 0xb0000004, 0x58000010, 0xb000000c, 0x48000000, 0xb0000000, 0xb8000010, 0x98000010, 0xa0000000, 0x00000000, 0x00000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0x20000000, 0x00000010, 0x60000000, 0x00000018, 0xe0000000, 0x90000000, 0x30000010, 0xb0000000, 0x20000000, 0x20000000, 0xa0000000, 0x00000010, 0x80000000, 0x20000000, 0x20000000, 0x20000000, 0x80000000, 0x00000010, 0x00000000, 0x20000010, 0xa0000000, 0x00000000, 0x20000000, 0x20000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x00000020, 0x00000001, 0x40000002, 0x40000041, 0x40000022, 0x80000005}
 484 };
 485
 486 void gen_sha1_dv_xm_tables() {
 487         int i,j,K,B;
 488         uint32_t xm[80];
 489         for (i = 0; sha1_dvs[i].dvtype != 0; ++i) {
 490                 K = sha1_dvs[i].dvK;
 491                 B = sha1_dvs[i].dvB;
 492                 for (j = 0; j < 80; ++j)
 493                         xm[j] = 0;
 494                 switch (sha1_dvs[i].dvtype) {
 495                 case 1:
 496                         xm[K+0] = (1<<4);
 497                         xm[K+1] = (1<<29)|(1<<31);
 498                         xm[K+3] = (1<<29);
 499                         xm[K+4] = (1<<29);
 500                         xm[K+15] = (1<<0);
 501                         break;
 502                 case 2:
 503                         xm[K+0] = (1<<29);
 504                         xm[K+1] = (1<<31);
 505                         xm[K+2] = (1<<4);
 506                         xm[K+4] = (1<<4)|(1<<29);
 507                         xm[K+5] = (1<<29)|(1<<31);
 508                         xm[K+7] = (1<<29);
 509                         xm[K+8] = (1<<29);
 510                         xm[K+15] = (1<<0);
 511                         break;
 512                 default:
 513                         printf("huh?!?");
 514                         exit(1);
 515                 }
 516                 if (B)
 517                         for (j = 0; j < 16; ++j)
 518                                 xm[K+j] = rotate_left(xm[K+j],B);
 519                 for (j = K+16; j < 80; ++j)
 520                         xm[j]=rotate_left(xm[j-3] ^ xm[j-8] ^ xm[j-14] ^ xm[j-16], 1);
 521                 for (j = K-1; j >= 0; --j)
 522                         xm[j+16-16]=rotate_right(xm[j+16-0],1) ^ xm[j+16-3] ^ xm[j+16-8] ^ xm[j+16-14];
 523 #if 0
 524 // generate tables
 525                 printf("{");
 526                 for (j = 0; j < 80; ++j)
 527                         printf("%s 0x%08x", (j==0)?" ":",", xm[j]);
 528                 printf("},\n");
 529 #else
 530 // verify tables
 531                 for (j = 0; j < 80; ++j)
 532                         if (xm[j] != sha1_dv_xm_table[i][j]) {
 533 #ifdef VERBOSE_COLLDETECT
 534                                 printf("mismatch: %d %d\n", i, j);
 535 #endif
 536                                 exit(0);
 537                         }
 538 #endif
 539         }
 540 }
 541
 542 void print_sha1_coll(uint64_t total, const uint32_t ihv1[5], const uint32_t block1[16], const uint32_t ihv2[5], const uint32_t block2[16], const char* DV) {
 543         unsigned i;
 544         printf("Found collision in block %llu using DV %s:\n   dm: ", (long long unsigned int)((total>>6)-1), DV);
 545         for (i = 0; i < 16; ++i)
 546                 if (block2[i]-block1[i])
 547                         printf("dm%d=%08x ", i, block2[i]-block1[i]);
 548         printf("\n   ihv1=");
 549         for (i = 0; i < 5; ++i)
 550                 printf("%08x", ihv1[i]);
 551         printf("\n   ihv2=");
 552         for (i = 0; i < 5; ++i)
 553                 printf("%08x", ihv2[i]);
 554         printf("\n");
 555 }
 556
 557 char dv_string[10];
 558 void sha1_process(SHA1_CTX* ctx, const uint32_t block[16]) {
 559         unsigned i,j,t;
 560         ctx->ihv1[0] = ctx->ihv[0];
 561         ctx->ihv1[1] = ctx->ihv[1];
 562         ctx->ihv1[2] = ctx->ihv[2];
 563         ctx->ihv1[3] = ctx->ihv[3];
 564         ctx->ihv1[4] = ctx->ihv[4];
 565         sha1compress_me(block, ctx->m1);
 566         sha1compress_states(ctx->ihv, ctx->m1, ctx->states);
 567         for (i = 0; sha1_dvs[i].dvtype != 0; ++i) {
 568                 t = sha1_dvs[i].dvK+13;
 569                 for (j = 0; j < 80; ++j)
 570                         ctx->m2[j] = ctx->m1[j] ^ sha1_dv_xm_table[i][j];
 571                 if (sha1recompress_fast(t, ctx->ihv2, ctx->m2, ctx->states+((t+1)*5), ctx->ihv)) {
 572 #ifdef VERBOSE_COLLDETECT
 573                         sprintf(dv_string, "%s(%d,%d)", sha1_dvs[i].dvtype==1?"I":"II", sha1_dvs[i].dvK, sha1_dvs[i].dvB);
 574                         print_sha1_coll(ctx->total, ctx->ihv1, ctx->m1, ctx->ihv2, ctx->m2, dv_string);
 575 #endif
 576                         ctx->found_collision = 1;
 577                         if (ctx->safe_hash) {
 578                                 sha1compress_states(ctx->ihv, ctx->m1, ctx->states);
 579                                 sha1compress_states(ctx->ihv, ctx->m1, ctx->states);
 580                         }
 581                 }
 582 #ifdef DETECT_REDUCED_SHA_COLLISION // to verify SHA-1 collision detection code with collisions for reduced-step SHA-1
 583                 if (ctx->ihv1[0]==ctx->ihv2[0] && ctx->ihv1[1]==ctx->ihv2[1] && ctx->ihv1[2]==ctx->ihv2[2] && ctx->ihv1[3]==ctx->ihv2[3] && ctx->ihv1[4]==ctx->ihv2[4]) {
 584 #ifdef VERBOSE_COLLDETECT
 585                         printf("Partial collision found\n");
 586                         sprintf(dv_string, "%s(%d,%d)", sha1_dvs[i].dvtype==1?"I":"II", sha1_dvs[i].dvK, sha1_dvs[i].dvB);
 587                         print_sha1_coll(ctx->total, ctx->ihv1, ctx->m1, ctx->ihv2, ctx->m2, dv_string);
 588 #endif
 589                 }
 590 #endif
 591         }
 592 }
 593
 594 void SHA1Init(SHA1_CTX* ctx) {
 595         static const union { unsigned char bytes[4]; uint32_t value; } endianness = { { 0, 1, 2, 3 } };
 596         static const uint32_t littleendian = 0x03020100;
 597         ctx->total = 0;
 598         ctx->ihv[0] = 0x67452301;
 599         ctx->ihv[1] = 0xEFCDAB89;
 600         ctx->ihv[2] = 0x98BADCFE;
 601         ctx->ihv[3] = 0x10325476;
 602         ctx->ihv[4] = 0xC3D2E1F0;
 603         ctx->found_collision = 0;
 604         ctx->safe_hash = 1;
 605         ctx->bigendian = (endianness.value != littleendian);
 606         gen_sha1_dv_xm_tables(); // verify or construct sha1_dv_xm_table from sha1_dvs
 607 }
 608 void SHA1Init_unsafe(SHA1_CTX* ctx) {
 609         static const union { unsigned char bytes[4]; uint32_t value; } endianness = { { 0, 1, 2, 3 } };
 610         static const uint32_t littleendian = 0x03020100;
 611         ctx->total = 0;
 612         ctx->ihv[0] = 0x67452301;
 613         ctx->ihv[1] = 0xEFCDAB89;
 614         ctx->ihv[2] = 0x98BADCFE;
 615         ctx->ihv[3] = 0x10325476;
 616         ctx->ihv[4] = 0xC3D2E1F0;
 617         ctx->found_collision = 0;
 618         ctx->safe_hash = 0;
 619         ctx->bigendian = (endianness.value != littleendian);
 620 }
 621
 622 void SHA1Update(SHA1_CTX* ctx, const char* buf, unsigned len) {
 623         unsigned left, fill;
 624         if (ctx == NULL) exit(1);
 625         if (len == 0) return;
 626         if (buf == NULL) exit(1);
 627
 628         left = ctx->total&63;
 629         fill = 64 - left;
 630
 631         if (left && len >= fill) {
 632                 ctx->total += fill;
 633
 634                 memcpy(ctx->buffer + left, buf, fill);
 635                 if (!ctx->bigendian)
 636                         swap_bytes((uint32_t*)(ctx->buffer));
 637                 sha1_process(ctx, (uint32_t*)(ctx->buffer));
 638                 buf += fill;
 639                 len -= fill;
 640                 left = 0;
 641         }
 642         while (len >= 64) {
 643                 ctx->total += 64;
 644                 if (!ctx->bigendian) {
 645                         memcpy(ctx->buffer, buf, 64);
 646                         swap_bytes((uint32_t*)(ctx->buffer));
 647                         sha1_process(ctx, (uint32_t*)(ctx->buffer));
 648                 } else
 649                         sha1_process(ctx, (uint32_t*)(buf));
 650                 buf += 64;
 651                 len -= 64;
 652         }
 653         if (len > 0) {
 654                 ctx->total += len;
 655                 memcpy(ctx->buffer + left, buf, len);
 656         }
 657 }
 658
 659 static const unsigned char sha1_padding[64] =
 660 {
 661  0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 662     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 663     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 664     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 665 };
 666
 667 int SHA1Final(unsigned char output[20], SHA1_CTX *ctx)
 668 {
 669         uint32_t last = ctx->total&63;
 670         uint32_t padn = (last < 56) ? (56-last) : (120-last);
 671         SHA1Update(ctx, (const char*)(sha1_padding), padn);
 672         ctx->total -= padn;
 673         ctx->total <<= 3;
 674         ctx->buffer[56] = (unsigned char)(ctx->total>>56);
 675         ctx->buffer[57] = (unsigned char)(ctx->total>>48);
 676         ctx->buffer[58] = (unsigned char)(ctx->total>>40);
 677         ctx->buffer[59] = (unsigned char)(ctx->total>>32);
 678         ctx->buffer[60] = (unsigned char)(ctx->total>>24);
 679         ctx->buffer[61] = (unsigned char)(ctx->total>>16);
 680         ctx->buffer[62] = (unsigned char)(ctx->total>>8);
 681         ctx->buffer[63] = (unsigned char)(ctx->total);
 682         if (!ctx->bigendian)
 683                 swap_bytes((uint32_t*)(ctx->buffer));
 684         sha1_process(ctx, (uint32_t*)(ctx->buffer));
 685         output[0] = (unsigned char)(ctx->ihv[0]>>24);
 686         output[1] = (unsigned char)(ctx->ihv[0]>>16);
 687         output[2] = (unsigned char)(ctx->ihv[0]>>8);
 688         output[3] = (unsigned char)(ctx->ihv[0]);
 689         output[4] = (unsigned char)(ctx->ihv[1]>>24);
 690         output[5] = (unsigned char)(ctx->ihv[1]>>16);
 691         output[6] = (unsigned char)(ctx->ihv[1]>>8);
 692         output[7] = (unsigned char)(ctx->ihv[1]);
 693         output[8] = (unsigned char)(ctx->ihv[2]>>24);
 694         output[9] = (unsigned char)(ctx->ihv[2]>>16);
 695         output[10] = (unsigned char)(ctx->ihv[2]>>8);
 696         output[11] = (unsigned char)(ctx->ihv[2]);
 697         output[12] = (unsigned char)(ctx->ihv[3]>>24);
 698         output[13] = (unsigned char)(ctx->ihv[3]>>16);
 699         output[14] = (unsigned char)(ctx->ihv[3]>>8);
 700         output[15] = (unsigned char)(ctx->ihv[3]);
 701         output[16] = (unsigned char)(ctx->ihv[4]>>24);
 702         output[17] = (unsigned char)(ctx->ihv[4]>>16);
 703         output[18] = (unsigned char)(ctx->ihv[4]>>8);
 704         output[19] = (unsigned char)(ctx->ihv[4]);
 705         return ctx->found_collision;
 706 }
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743 void md5compress_states(uint32_t ihv[4], const uint32_t block[16], uint32_t states[260])
 744 {
 745         uint32_t a = ihv[0]; uint32_t b = ihv[1]; uint32_t c = ihv[2]; uint32_t d = ihv[3];
 746
 747 //      STORE_STATE(0);
 748         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, a, b, c, d, block[ 0], 0xd76aa478,  7);
 749 //      STORE_STATE(1);
 750         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, d, a, b, c, block[ 1], 0xe8c7b756, 12);
 751 //      STORE_STATE(2);
 752         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, c, d, a, b, block[ 2], 0x242070db, 17);
 753 //      STORE_STATE(3);
 754         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, b, c, d, a, block[ 3], 0xc1bdceee, 22);
 755 //      STORE_STATE(4);
 756         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, a, b, c, d, block[ 4], 0xf57c0faf,  7);
 757 //      STORE_STATE(5);
 758         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, d, a, b, c, block[ 5], 0x4787c62a, 12);
 759 //      STORE_STATE(6);
 760         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, c, d, a, b, block[ 6], 0xa8304613, 17);
 761 //      STORE_STATE(7);
 762         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, b, c, d, a, block[ 7], 0xfd469501, 22);
 763 //      STORE_STATE(8);
 764         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, a, b, c, d, block[ 8], 0x698098d8,  7);
 765 //      STORE_STATE(9);
 766         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, d, a, b, c, block[ 9], 0x8b44f7af, 12);
 767 //      STORE_STATE(10);
 768         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, c, d, a, b, block[10], 0xffff5bb1, 17);
 769 //      STORE_STATE(11);
 770         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, b, c, d, a, block[11], 0x895cd7be, 22);
 771 //      STORE_STATE(12);
 772         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, a, b, c, d, block[12], 0x6b901122,  7);
 773 //      STORE_STATE(13);
 774         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, d, a, b, c, block[13], 0xfd987193, 12);
 775 //      STORE_STATE(14);
 776         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, c, d, a, b, block[14], 0xa679438e, 17);
 777 //      STORE_STATE(15);
 778         HASHUTIL5_MD5COMPRESS_STEP(md5_ff, b, c, d, a, block[15], 0x49b40821, 22);
 779 //      STORE_STATE(16);
 780         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, a, b, c, d, block[ 1], 0xf61e2562,  5);
 781 //      STORE_STATE(17);
 782         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, d, a, b, c, block[ 6], 0xc040b340,  9);
 783 //      STORE_STATE(18);
 784         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, c, d, a, b, block[11], 0x265e5a51, 14);
 785 //      STORE_STATE(19);
 786         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, b, c, d, a, block[ 0], 0xe9b6c7aa, 20);
 787 //      STORE_STATE(20);
 788         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, a, b, c, d, block[ 5], 0xd62f105d,  5);
 789 //      STORE_STATE(21);
 790         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, d, a, b, c, block[10], 0x02441453,  9);
 791 //      STORE_STATE(22);
 792         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, c, d, a, b, block[15], 0xd8a1e681, 14);
 793 //      STORE_STATE(23);
 794         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, b, c, d, a, block[ 4], 0xe7d3fbc8, 20);
 795 //      STORE_STATE(24);
 796         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, a, b, c, d, block[ 9], 0x21e1cde6,  5);
 797 //      STORE_STATE(25);
 798         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, d, a, b, c, block[14], 0xc33707d6,  9);
 799 //      STORE_STATE(26);
 800         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, c, d, a, b, block[ 3], 0xf4d50d87, 14);
 801 //      STORE_STATE(27);
 802         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, b, c, d, a, block[ 8], 0x455a14ed, 20);
 803 //      STORE_STATE(28);
 804         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, a, b, c, d, block[13], 0xa9e3e905,  5);
 805 //      STORE_STATE(29);
 806         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, d, a, b, c, block[ 2], 0xfcefa3f8,  9);
 807 //      STORE_STATE(30);
 808         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, c, d, a, b, block[ 7], 0x676f02d9, 14);
 809 //      STORE_STATE(31);
 810         HASHUTIL5_MD5COMPRESS_STEP(md5_gg, b, c, d, a, block[12], 0x8d2a4c8a, 20);
 811 //      STORE_STATE(32);
 812         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, a, b, c, d, block[ 5], 0xfffa3942,  4);
 813 //      STORE_STATE(33);
 814         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, d, a, b, c, block[ 8], 0x8771f681, 11);
 815 //      STORE_STATE(34);
 816         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, c, d, a, b, block[11], 0x6d9d6122, 16);
 817 //      STORE_STATE(35);
 818         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, b, c, d, a, block[14], 0xfde5380c, 23);
 819 //      STORE_STATE(36);
 820         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, a, b, c, d, block[ 1], 0xa4beea44,  4);
 821 //      STORE_STATE(37);
 822         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, d, a, b, c, block[ 4], 0x4bdecfa9, 11);
 823         STORE_STATE(38);
 824         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, c, d, a, b, block[ 7], 0xf6bb4b60, 16);
 825 //      STORE_STATE(39);
 826         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, b, c, d, a, block[10], 0xbebfbc70, 23);
 827 //      STORE_STATE(40);
 828         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, a, b, c, d, block[13], 0x289b7ec6,  4);
 829 //      STORE_STATE(41);
 830         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, d, a, b, c, block[ 0], 0xeaa127fa, 11);
 831 //      STORE_STATE(42);
 832         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, c, d, a, b, block[ 3], 0xd4ef3085, 16);
 833 //      STORE_STATE(43);
 834         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, b, c, d, a, block[ 6], 0x04881d05, 23);
 835 //      STORE_STATE(44);
 836         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, a, b, c, d, block[ 9], 0xd9d4d039,  4);
 837         STORE_STATE(45);
 838         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, d, a, b, c, block[12], 0xe6db99e5, 11);
 839 //      STORE_STATE(46);
 840         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, c, d, a, b, block[15], 0x1fa27cf8, 16);
 841 //      STORE_STATE(47);
 842         HASHUTIL5_MD5COMPRESS_STEP(md5_hh, b, c, d, a, block[ 2], 0xc4ac5665, 23);
 843 //      STORE_STATE(48);
 844         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, a, b, c, d, block[ 0], 0xf4292244,  6);
 845 //      STORE_STATE(49);
 846         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, d, a, b, c, block[ 7], 0x432aff97, 10);
 847 //      STORE_STATE(50);
 848         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, c, d, a, b, block[14], 0xab9423a7, 15);
 849         STORE_STATE(51);
 850         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, b, c, d, a, block[ 5], 0xfc93a039, 21);
 851 //      STORE_STATE(52);
 852         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, a, b, c, d, block[12], 0x655b59c3,  6);
 853 //      STORE_STATE(53);
 854         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, d, a, b, c, block[ 3], 0x8f0ccc92, 10);
 855 //      STORE_STATE(54);
 856         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, c, d, a, b, block[10], 0xffeff47d, 15);
 857 //      STORE_STATE(55);
 858         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, b, c, d, a, block[ 1], 0x85845dd1, 21);
 859 //      STORE_STATE(56);
 860         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, a, b, c, d, block[ 8], 0x6fa87e4f,  6);
 861 //      STORE_STATE(57);
 862         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, d, a, b, c, block[15], 0xfe2ce6e0, 10);
 863 //      STORE_STATE(58);
 864         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, c, d, a, b, block[ 6], 0xa3014314, 15);
 865 //      STORE_STATE(59);
 866         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, b, c, d, a, block[13], 0x4e0811a1, 21);
 867 //      STORE_STATE(60);
 868         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, a, b, c, d, block[ 4], 0xf7537e82,  6);
 869 //      STORE_STATE(61);
 870         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, d, a, b, c, block[11], 0xbd3af235, 10);
 871 //      STORE_STATE(62);
 872         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, c, d, a, b, block[ 2], 0x2ad7d2bb, 15);
 873 //      STORE_STATE(63);
 874         HASHUTIL5_MD5COMPRESS_STEP(md5_ii, b, c, d, a, block[ 9], 0xeb86d391, 21);
 875 //      STORE_STATE(64);
 876
 877         ihv[0] += a; ihv[1] += b; ihv[2] += c; ihv[3] += d;
 878 }
 879
 880 int md5recompress_fast(unsigned t, uint32_t ihv[4], const uint32_t block[16], const uint32_t state[4], const uint32_t rihv[4])
 881 {
 882         uint32_t a = state[0], b = state[1], c = state[2], d = state[3];
 883         switch (t) {
 884                 case 63: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, b, c, d, a, block[ 9], 0xeb86d391, 21);
 885                 case 62: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, c, d, a, b, block[ 2], 0x2ad7d2bb, 15);
 886                 case 61: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, d, a, b, c, block[11], 0xbd3af235, 10);
 887                 case 60: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, a, b, c, d, block[ 4], 0xf7537e82,  6);
 888                 case 59: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, b, c, d, a, block[13], 0x4e0811a1, 21);
 889                 case 58: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, c, d, a, b, block[ 6], 0xa3014314, 15);
 890                 case 57: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, d, a, b, c, block[15], 0xfe2ce6e0, 10);
 891                 case 56: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, a, b, c, d, block[ 8], 0x6fa87e4f,  6);
 892                 case 55: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, b, c, d, a, block[ 1], 0x85845dd1, 21);
 893                 case 54: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, c, d, a, b, block[10], 0xffeff47d, 15);
 894                 case 53: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, d, a, b, c, block[ 3], 0x8f0ccc92, 10);
 895                 case 52: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, a, b, c, d, block[12], 0x655b59c3,  6);
 896                 case 51: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, b, c, d, a, block[ 5], 0xfc93a039, 21);
 897                 case 50: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, c, d, a, b, block[14], 0xab9423a7, 15);
 898                 case 49: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, d, a, b, c, block[ 7], 0x432aff97, 10);
 899                 case 48: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ii, a, b, c, d, block[ 0], 0xf4292244,  6);
 900                 case 47: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, b, c, d, a, block[ 2], 0xc4ac5665, 23);
 901                 case 46: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, c, d, a, b, block[15], 0x1fa27cf8, 16);
 902                 case 45: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, d, a, b, c, block[12], 0xe6db99e5, 11);
 903                 case 44: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, a, b, c, d, block[ 9], 0xd9d4d039,  4);
 904                 case 43: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, b, c, d, a, block[ 6], 0x04881d05, 23);
 905                 case 42: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, c, d, a, b, block[ 3], 0xd4ef3085, 16);
 906                 case 41: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, d, a, b, c, block[ 0], 0xeaa127fa, 11);
 907                 case 40: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, a, b, c, d, block[13], 0x289b7ec6,  4);
 908                 case 39: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, b, c, d, a, block[10], 0xbebfbc70, 23);
 909                 case 38: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, c, d, a, b, block[ 7], 0xf6bb4b60, 16);
 910                 case 37: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, d, a, b, c, block[ 4], 0x4bdecfa9, 11);
 911                 case 36: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, a, b, c, d, block[ 1], 0xa4beea44,  4);
 912                 case 35: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, b, c, d, a, block[14], 0xfde5380c, 23);
 913                 case 34: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, c, d, a, b, block[11], 0x6d9d6122, 16);
 914                 case 33: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, d, a, b, c, block[ 8], 0x8771f681, 11);
 915                 case 32: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_hh, a, b, c, d, block[ 5], 0xfffa3942,  4);
 916                 case 31: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, b, c, d, a, block[12], 0x8d2a4c8a, 20);
 917                 case 30: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, c, d, a, b, block[ 7], 0x676f02d9, 14);
 918                 case 29: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, d, a, b, c, block[ 2], 0xfcefa3f8,  9);
 919                 case 28: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, a, b, c, d, block[13], 0xa9e3e905,  5);
 920                 case 27: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, b, c, d, a, block[ 8], 0x455a14ed, 20);
 921                 case 26: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, c, d, a, b, block[ 3], 0xf4d50d87, 14);
 922                 case 25: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, d, a, b, c, block[14], 0xc33707d6,  9);
 923                 case 24: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, a, b, c, d, block[ 9], 0x21e1cde6,  5);
 924                 case 23: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, b, c, d, a, block[ 4], 0xe7d3fbc8, 20);
 925                 case 22: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, c, d, a, b, block[15], 0xd8a1e681, 14);
 926                 case 21: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, d, a, b, c, block[10], 0x02441453,  9);
 927                 case 20: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, a, b, c, d, block[ 5], 0xd62f105d,  5);
 928                 case 19: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, b, c, d, a, block[ 0], 0xe9b6c7aa, 20);
 929                 case 18: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, c, d, a, b, block[11], 0x265e5a51, 14);
 930                 case 17: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, d, a, b, c, block[ 6], 0xc040b340,  9);
 931                 case 16: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_gg, a, b, c, d, block[ 1], 0xf61e2562,  5);
 932                 case 15: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, b, c, d, a, block[15], 0x49b40821, 22);
 933                 case 14: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, c, d, a, b, block[14], 0xa679438e, 17);
 934                 case 13: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, d, a, b, c, block[13], 0xfd987193, 12);
 935                 case 12: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, a, b, c, d, block[12], 0x6b901122,  7);
 936                 case 11: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, b, c, d, a, block[11], 0x895cd7be, 22);
 937                 case 10: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, c, d, a, b, block[10], 0xffff5bb1, 17);
 938                 case 9: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, d, a, b, c, block[ 9], 0x8b44f7af, 12);
 939                 case 8: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, a, b, c, d, block[ 8], 0x698098d8,  7);
 940                 case 7: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, b, c, d, a, block[ 7], 0xfd469501, 22);
 941                 case 6: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, c, d, a, b, block[ 6], 0xa8304613, 17);
 942                 case 5: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, d, a, b, c, block[ 5], 0x4787c62a, 12);
 943                 case 4: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, a, b, c, d, block[ 4], 0xf57c0faf,  7);
 944                 case 3: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, b, c, d, a, block[ 3], 0xc1bdceee, 22);
 945                 case 2: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, c, d, a, b, block[ 2], 0x242070db, 17);
 946                 case 1: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, d, a, b, c, block[ 1], 0xe8c7b756, 12);
 947                 case 0: HASHUTIL5_MD5COMPRESS_STEP_BW(md5_ff, a, b, c, d, block[ 0], 0xd76aa478,  7);
 948         }
 949         ihv[0] = a; ihv[1] = b; ihv[2] = c; ihv[3] = d;
 950         a = state[0]; b = state[1]; c = state[2]; d = state[3];
 951         switch (t+1) {
 952                 case 0: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, a, b, c, d, block[ 0], 0xd76aa478, 7);
 953                 case 1: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, d, a, b, c, block[ 1], 0xe8c7b756, 12);
 954                 case 2: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, c, d, a, b, block[ 2], 0x242070db, 17);
 955                 case 3: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, b, c, d, a, block[ 3], 0xc1bdceee, 22);
 956                 case 4: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, a, b, c, d, block[ 4], 0xf57c0faf, 7);
 957                 case 5: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, d, a, b, c, block[ 5], 0x4787c62a, 12);
 958                 case 6: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, c, d, a, b, block[ 6], 0xa8304613, 17);
 959                 case 7: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, b, c, d, a, block[ 7], 0xfd469501, 22);
 960                 case 8: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, a, b, c, d, block[ 8], 0x698098d8, 7);
 961                 case 9: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, d, a, b, c, block[ 9], 0x8b44f7af, 12);
 962                 case 10: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, c, d, a, b, block[10], 0xffff5bb1, 17);
 963                 case 11: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, b, c, d, a, block[11], 0x895cd7be, 22);
 964                 case 12: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, a, b, c, d, block[12], 0x6b901122, 7);
 965                 case 13: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, d, a, b, c, block[13], 0xfd987193, 12);
 966                 case 14: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, c, d, a, b, block[14], 0xa679438e, 17);
 967                 case 15: HASHUTIL5_MD5COMPRESS_STEP(md5_ff, b, c, d, a, block[15], 0x49b40821, 22);
 968                 case 16: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, a, b, c, d, block[ 1], 0xf61e2562, 5);
 969                 case 17: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, d, a, b, c, block[ 6], 0xc040b340, 9);
 970                 case 18: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, c, d, a, b, block[11], 0x265e5a51, 14);
 971                 case 19: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, b, c, d, a, block[ 0], 0xe9b6c7aa, 20);
 972                 case 20: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, a, b, c, d, block[ 5], 0xd62f105d, 5);
 973                 case 21: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, d, a, b, c, block[10], 0x02441453, 9);
 974                 case 22: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, c, d, a, b, block[15], 0xd8a1e681, 14);
 975                 case 23: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, b, c, d, a, block[ 4], 0xe7d3fbc8, 20);
 976                 case 24: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, a, b, c, d, block[ 9], 0x21e1cde6, 5);
 977                 case 25: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, d, a, b, c, block[14], 0xc33707d6, 9);
 978                 case 26: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, c, d, a, b, block[ 3], 0xf4d50d87, 14);
 979                 case 27: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, b, c, d, a, block[ 8], 0x455a14ed, 20);
 980                 case 28: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, a, b, c, d, block[13], 0xa9e3e905, 5);
 981                 case 29: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, d, a, b, c, block[ 2], 0xfcefa3f8, 9);
 982                 case 30: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, c, d, a, b, block[ 7], 0x676f02d9, 14);
 983                 case 31: HASHUTIL5_MD5COMPRESS_STEP(md5_gg, b, c, d, a, block[12], 0x8d2a4c8a, 20);
 984                 case 32: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, a, b, c, d, block[ 5], 0xfffa3942, 4);
 985                 case 33: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, d, a, b, c, block[ 8], 0x8771f681, 11);
 986                 case 34: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, c, d, a, b, block[11], 0x6d9d6122, 16);
 987                 case 35: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, b, c, d, a, block[14], 0xfde5380c, 23);
 988                 case 36: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, a, b, c, d, block[ 1], 0xa4beea44, 4);
 989                 case 37: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, d, a, b, c, block[ 4], 0x4bdecfa9, 11);
 990                 case 38: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, c, d, a, b, block[ 7], 0xf6bb4b60, 16);
 991                 case 39: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, b, c, d, a, block[10], 0xbebfbc70, 23);
 992                 case 40: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, a, b, c, d, block[13], 0x289b7ec6, 4);
 993                 case 41: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, d, a, b, c, block[ 0], 0xeaa127fa, 11);
 994                 case 42: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, c, d, a, b, block[ 3], 0xd4ef3085, 16);
 995                 case 43: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, b, c, d, a, block[ 6], 0x04881d05, 23);
 996                 case 44: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, a, b, c, d, block[ 9], 0xd9d4d039, 4);
 997                 case 45: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, d, a, b, c, block[12], 0xe6db99e5, 11);
 998                 case 46: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, c, d, a, b, block[15], 0x1fa27cf8, 16);
 999                 case 47: HASHUTIL5_MD5COMPRESS_STEP(md5_hh, b, c, d, a, block[ 2], 0xc4ac5665, 23);
1000                 case 48: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, a, b, c, d, block[ 0], 0xf4292244, 6);
1001                 case 49: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, d, a, b, c, block[ 7], 0x432aff97, 10);
1002                 case 50: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, c, d, a, b, block[14], 0xab9423a7, 15);
1003                 case 51: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, b, c, d, a, block[ 5], 0xfc93a039, 21);
1004                 case 52: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, a, b, c, d, block[12], 0x655b59c3, 6);
1005                 case 53: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, d, a, b, c, block[ 3], 0x8f0ccc92, 10);
1006                 case 54: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, c, d, a, b, block[10], 0xffeff47d, 15);
1007                 case 55: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, b, c, d, a, block[ 1], 0x85845dd1, 21);
1008                 case 56: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, a, b, c, d, block[ 8], 0x6fa87e4f, 6);
1009                 case 57: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, d, a, b, c, block[15], 0xfe2ce6e0, 10);
1010                 case 58: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, c, d, a, b, block[ 6], 0xa3014314, 15);
1011                 case 59: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, b, c, d, a, block[13], 0x4e0811a1, 21);
1012                 case 60: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, a, b, c, d, block[ 4], 0xf7537e82, 6);
1013                 case 61: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, d, a, b, c, block[11], 0xbd3af235, 10);
1014                 case 62: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, c, d, a, b, block[ 2], 0x2ad7d2bb, 15);
1015                 case 63: HASHUTIL5_MD5COMPRESS_STEP(md5_ii, b, c, d, a, block[ 9], 0xeb86d391, 21);
1016         }
1017         return (rihv[0] == ihv[0]+a && rihv[1] == ihv[1]+b && rihv[2] == ihv[2]+c && rihv[3] == ihv[3]+d);
1018 }
1019
1020 msgdiff_tuples_t msgdiff_tuples[] = {
1021         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 1u<<31, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<15, /*12*/ 0, /*13*/ 0, /*14*/ 1u<<31, /*15*/ 0 },      /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1022         { { /*0*/ 0, /*1*/ 0, /*2*/ 1<<8, /*3*/ 0, /*4*/ 1u<<31, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<15, /*12*/ 0, /*13*/ 0, /*14*/ 1u<<31, /*15*/ 0 },   /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1023         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1024         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<1, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1025         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<2, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1026         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<3, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1027         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<4, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1028         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<5, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1029         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<6, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1030         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<7, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1031         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<8, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1032         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<9, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1033         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<10, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1034         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<11, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1035         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<12, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1036         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<13, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1037         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<14, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1038         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<15, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1039         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<16, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1040         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<17, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1041         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<18, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1042         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<19, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1043         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<20, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1044         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<21, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1045         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<22, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1046         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<23, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1047         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<24, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1048         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<25, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1049         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<26, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1050         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<27, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1051         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<28, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1052         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<29, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1053         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<30, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1054         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1u<<31, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 0, /*zero*/ 1, /*msb*/ 1 },
1055         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 1<<10, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 1u<<31, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },          /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1056         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 1u<<31, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 0, /*zero*/ 1, /*msb*/ 1 },
1057         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 1<<8, /*7*/ 0, /*8*/ 0, /*9*/ 1u<<31, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 1u<<31 },       /*t*/ 37, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1058         { { /*0*/ 0, /*1*/ 0, /*2*/ 1u<<31, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 1<<27, /*10*/ 0, /*11*/ 0, /*12*/ 1u<<31, /*13*/ 0, /*14*/ 0, /*15*/ 0 },      /*t*/ 37, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1059         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 1<<20, /*5*/ 0, /*6*/ 0, /*7*/ 1u<<31, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 1u<<31, /*14*/ 0, /*15*/ 0 },      /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1060         { { /*0*/ 0, /*1*/ 0, /*2*/ 1<<8, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 37, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1061         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 1<<10, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<21, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },          /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1062         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 1<<10, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1u<<31, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },          /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1063         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 1u<<31, /*6*/ 0, /*7*/ 0, /*8*/ 1u<<31, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },          /*t*/ 44, /*negate*/ 0, /*zero*/ 1, /*msb*/ 1 },
1064         { { /*0*/ 0, /*1*/ 0, /*2*/ 1<<8, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 1u<<31, /*15*/ 0 },           /*t*/ 37, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1065         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 1u<<31, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 0, /*zero*/ 1, /*msb*/ 1 },
1066         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 1u<<31, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 0, /*zero*/ 1, /*msb*/ 1 },
1067         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 1u<<31, /*15*/ 0 },              /*t*/ 44, /*negate*/ 0, /*zero*/ 1, /*msb*/ 1 },
1068         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 1<<25, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1069         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 1<<10, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1070         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 1<<25, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1071         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1<<21, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1072         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 1<<16, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1073         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 1<<20, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1074         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 1<<8, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },               /*t*/ 50, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1075         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 1<<27, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },              /*t*/ 50, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1076         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 1<<10, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 1<<27, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },          /*t*/ 37, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1077         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 1u<<31, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 1u<<31, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },          /*t*/ 44, /*negate*/ 0, /*zero*/ 1, /*msb*/ 1 },
1078         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 1u<<31, /*9*/ 0, /*10*/ 0, /*11*/ 1<<21, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },          /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1079         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 1<<25, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 1u<<31, /*14*/ 0, /*15*/ 0 },          /*t*/ 44, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 },
1080
1081         { { /*0*/ 0, /*1*/ 0, /*2*/ 0, /*3*/ 0, /*4*/ 0, /*5*/ 0, /*6*/ 0, /*7*/ 0, /*8*/ 0, /*9*/ 0, /*10*/ 0, /*11*/ 0, /*12*/ 0, /*13*/ 0, /*14*/ 0, /*15*/ 0 },                  /*t*/ 0, /*negate*/ 1, /*zero*/ 1, /*msb*/ 1 } // end of array marker
1082 };
1083
1084 void print_coll(uint64_t total, const uint32_t ihv1[4], const uint32_t block1[16], const uint32_t ihv2[4], const uint32_t block2[16]) {
1085         unsigned i;
1086         printf("Found collision in block %llu:\n   dm: ", (long long unsigned int)((total>>6)-1));
1087         for (i = 0; i < 16; ++i)
1088                 if (block2[i]-block1[i])
1089                         printf("dm%d=%08x ", i, block2[i]-block1[i]);
1090         printf("\n   ihv1=");
1091         for (i = 0; i < 4; ++i)
1092                 printf("%08x", ihv1[i]);
1093         printf("\n   ihv2=");
1094         for (i = 0; i < 4; ++i)
1095                 printf("%08x", ihv2[i]);
1096         printf("\n");
1097 }
1098
1099 int detect_coll(const uint32_t block1[16], const uint32_t states[260], const uint32_t statesmsb[260], const uint32_t tihv[4], uint32_t ihv2[4], uint32_t block2[16]) {
1100         unsigned i,j;
1101         for (i = 0; msgdiff_tuples[i].t != 0; ++i) {
1102                 for (j = 0; j < 16; ++j)
1103                         block2[j] = block1[j] + msgdiff_tuples[i].msgdiff[j];
1104                 if (msgdiff_tuples[i].zero) {
1105                         if (md5recompress_fast(msgdiff_tuples[i].t, ihv2, block2, states+((msgdiff_tuples[i].t+1)*4), tihv))
1106                                 return 1;
1107                 }
1108                 if (msgdiff_tuples[i].msb) {
1109                         if (md5recompress_fast(msgdiff_tuples[i].t, ihv2, block2, statesmsb+((msgdiff_tuples[i].t+1)*4), tihv))
1110                                 return 1;
1111                 }
1112                 if (msgdiff_tuples[i].negate) {
1113                         for (j = 0; j < 16; ++j)
1114                                 block2[j] = block1[j] - msgdiff_tuples[i].msgdiff[j];
1115                         if (msgdiff_tuples[i].zero) {
1116                                 if (md5recompress_fast(msgdiff_tuples[i].t, ihv2, block2, states+((msgdiff_tuples[i].t+1)*4), tihv))
1117                                         return 1;
1118                         }
1119                         if (msgdiff_tuples[i].msb) {
1120                                 if (md5recompress_fast(msgdiff_tuples[i].t, ihv2, block2, statesmsb+((msgdiff_tuples[i].t+1)*4), tihv))
1121                                         return 1;
1122                         }
1123                 }
1124         }
1125         return 0;
1126 }
1127
1128 void md5_process(MD5_CTX* ctx, const uint32_t* block)
1129 {
1130         unsigned i;
1131         ctx->ihv1[0] = ctx->ihv[0];
1132         ctx->ihv1[1] = ctx->ihv[1];
1133         ctx->ihv1[2] = ctx->ihv[2];
1134         ctx->ihv1[3] = ctx->ihv[3];
1135         md5compress_states(ctx->ihv, block, ctx->states);
1136         for (i = 0; i < 260; ++i)
1137                 ctx->statesmsb[i] = ctx->states[i] + (1<<31);
1138         if (detect_coll(block, ctx->states, ctx->statesmsb, ctx->ihv, ctx->ihv2, ctx->m2)) {
1139 #ifdef VERBOSE_COLLDETECT
1140                 print_coll(ctx->total, ctx->ihv1, block, ctx->ihv2, ctx->m2);
1141 #endif
1142                 ctx->found_collision = 1;
1143                 if (ctx->safe_hash) {
1144                         // block was carefully constructed for one specific ihv-value
1145                         // update ihv once or twice more with block to break the collision property
1146                         md5compress_states(ctx->ihv, block, ctx->states);
1147                         md5compress_states(ctx->ihv, block, ctx->states);
1148                 }
1149         }
1150         // check for special den Boer & Bosselaers attack (zero difference block, differential path entirely MSB differences)
1151         if (ctx->total >= 128 && md5recompress_fast(44, ctx->ihv2, block, ctx->statesmsb+((44+1)*4), ctx->ihv)) {
1152                 if ((ctx->ihv2[0] != (ctx->ihv1[0]^(1<<31))) || (ctx->ihv2[1] != (ctx->ihv1[1]^(1<<31))) || (ctx->ihv2[2] != (ctx->ihv1[2]^(1<<31))) || (ctx->ihv2[3] != (ctx->ihv1[3]^(1<<31)))) {
1153                         // not den Boer & Bosselears attack, but regular near-collision attack
1154 #ifdef VERBOSE_COLLDETECT
1155                         print_coll(ctx->total, ctx->ihv1, block, ctx->ihv2, block);
1156 #endif
1157                         ctx->found_collision = 1;
1158                         if (ctx->safe_hash) {
1159                                 // block was carefully constructed for one specific ihv-value
1160                                 // update ihv once or twice more with block to break the collision property
1161                                 md5compress_states(ctx->ihv, block, ctx->states);
1162                                 md5compress_states(ctx->ihv, block, ctx->states);
1163                         }
1164                 } else {
1165                         // check for necessary previous collision block
1166                         for (i=0; i < 4; ++i)
1167                                 ctx->ihv1[i] = ctx->previhv[i];
1168                         md5compress_states(ctx->ihv1, ctx->prevblock, ctx->states);
1169                         for (i = 0; i < 260; ++i)
1170                                 ctx->statesmsb[i] = ctx->states[i] + (1<<31);
1171                         if (detect_coll(ctx->prevblock, ctx->states, ctx->statesmsb, ctx->ihv2, ctx->tmpihv, ctx->tmpblock)) {
1172 #ifdef VERBOSE_COLLDETECT
1173                                 print_coll(ctx->total, ctx->ihv1, block, ctx->ihv2, block);
1174                                 print_coll(ctx->total-64, ctx->previhv, ctx->prevblock, ctx->tmpihv, ctx->tmpblock);
1175 #endif
1176                                 ctx->found_collision = 1;
1177                                 if (ctx->safe_hash) {
1178                                         // block was carefully constructed for one specific ihv-value
1179                                         // update ihv once or twice more with block to break the collision property
1180                                         md5compress_states(ctx->ihv, block, ctx->states);
1181                                         md5compress_states(ctx->ihv, block, ctx->states);
1182                                 }
1183                         }
1184                 }
1185         }
1186         // need to store the last ihv and block
1187         for (i = 0; i < 4; ++i)
1188                 ctx->previhv[i] = ctx->ihv1[i];
1189         for (i = 0; i < 16; ++i)
1190                 ctx->prevblock[i] = block[i];
1191 }
1192
1193
1194
1195
1196
1197 void MD5Init(MD5_CTX* ctx) {
1198         static const union { unsigned char bytes[4]; uint32_t value; } endianness = { { 0, 1, 2, 3 } };
1199         static const uint32_t littleendian = 0x03020100;
1200         ctx->total = 0;
1201         ctx->ihv[0] = 0x67452301;
1202         ctx->ihv[1] = 0xefcdab89;
1203         ctx->ihv[2] = 0x98badcfe;
1204         ctx->ihv[3] = 0x10325476;
1205         ctx->found_collision = 0;
1206         ctx->safe_hash = 1;
1207         ctx->bigendian = (endianness.value != littleendian);
1208 }
1209 void MD5Init_unsafe(MD5_CTX* ctx) {
1210         static const union { unsigned char bytes[4]; uint32_t value; } endianness = { { 0, 1, 2, 3 } };
1211         static const uint32_t littleendian = 0x03020100;
1212         ctx->total = 0;
1213         ctx->ihv[0] = 0x67452301;
1214         ctx->ihv[1] = 0xefcdab89;
1215         ctx->ihv[2] = 0x98badcfe;
1216         ctx->ihv[3] = 0x10325476;
1217         ctx->found_collision = 0;
1218         ctx->safe_hash = 0;
1219         ctx->bigendian = (endianness.value != littleendian);
1220 }
1221
1222 void MD5Update(MD5_CTX* ctx, const char* buf, unsigned len) {
1223         unsigned left, fill;
1224         if (ctx == NULL) exit(1);
1225         if (len == 0) return;
1226         if (buf == NULL) exit(1);
1227
1228         left = ctx->total&63;
1229         fill = 64 - left;
1230
1231         if (left && len >= fill) {
1232                 ctx->total += fill;
1233
1234                 memcpy(ctx->buffer + left, buf, fill);
1235                 if (ctx->bigendian)
1236                         swap_bytes((uint32_t*)(ctx->buffer));
1237                 md5_process(ctx, (uint32_t*)(ctx->buffer));
1238                 buf += fill;
1239                 len -= fill;
1240                 left = 0;
1241         }
1242         while (len >= 64) {
1243                 ctx->total += 64;
1244                 if (ctx->bigendian) {
1245                         memcpy(ctx->buffer, buf, 64);
1246                         swap_bytes((uint32_t*)(ctx->buffer));
1247                         md5_process(ctx, (uint32_t*)(ctx->buffer));
1248                 } else
1249                         md5_process(ctx, (const uint32_t*)(buf));
1250                 buf += 64;
1251                 len -= 64;
1252         }
1253         if (len > 0) {
1254                 ctx->total += len;
1255                 memcpy(ctx->buffer + left, buf, len);
1256         }
1257 }
1258
1259 static const unsigned char md5_padding[64] =
1260 {
1261  0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1262     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1263     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1264     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
1265 };
1266
1267 int MD5Final(unsigned char output[16], MD5_CTX *ctx)
1268 {
1269         uint32_t last = ctx->total&63;
1270         uint32_t padn = (last < 56) ? (56-last) : (120-last);
1271         MD5Update(ctx, (const char*)(md5_padding), padn);
1272         ctx->total -= padn;
1273         ctx->total <<= 3;
1274         ctx->buffer[56] = (unsigned char)(ctx->total);
1275         ctx->buffer[57] = (unsigned char)(ctx->total>>8);
1276         ctx->buffer[58] = (unsigned char)(ctx->total>>16);
1277         ctx->buffer[59] = (unsigned char)(ctx->total>>24);
1278         ctx->buffer[60] = (unsigned char)(ctx->total>>32);
1279         ctx->buffer[61] = (unsigned char)(ctx->total>>40);
1280         ctx->buffer[62] = (unsigned char)(ctx->total>>48);
1281         ctx->buffer[63] = (unsigned char)(ctx->total>>56);
1282         if (ctx->bigendian)
1283                 swap_bytes((uint32_t*)(ctx->buffer));
1284         md5_process(ctx, (uint32_t*)(ctx->buffer));
1285         output[0] = (unsigned char)(ctx->ihv[0]);
1286         output[1] = (unsigned char)(ctx->ihv[0]>>8);
1287         output[2] = (unsigned char)(ctx->ihv[0]>>16);
1288         output[3] = (unsigned char)(ctx->ihv[0]>>24);
1289         output[4] = (unsigned char)(ctx->ihv[1]);
1290         output[5] = (unsigned char)(ctx->ihv[1]>>8);
1291         output[6] = (unsigned char)(ctx->ihv[1]>>16);
1292         output[7] = (unsigned char)(ctx->ihv[1]>>24);
1293         output[8] = (unsigned char)(ctx->ihv[2]);
1294         output[9] = (unsigned char)(ctx->ihv[2]>>8);
1295         output[10] = (unsigned char)(ctx->ihv[2]>>16);
1296         output[11] = (unsigned char)(ctx->ihv[2]>>24);
1297         output[12] = (unsigned char)(ctx->ihv[3]);
1298         output[13] = (unsigned char)(ctx->ihv[3]>>8);
1299         output[14] = (unsigned char)(ctx->ihv[3]>>16);
1300         output[15] = (unsigned char)(ctx->ihv[3]>>24);
1301         return ctx->found_collision;
1302 }
1303