1 2 /* 3 * Keyed 32-bit hash function using TEA in a Davis-Meyer function 4 * H0 = Key 5 * Hi = E Mi(Hi-1) + Hi-1 6 * 7 * (see Applied Cryptography, 2nd edition, p448). 8 * 9 * Jeremy Fitzhardinge <jeremy@zip.com.au> 1998 10 * 11 * Jeremy has agreed to the contents of reiserfs/README. -Hans 12 * Yura's function is added (04/07/2000) 13 */ 14 15 // 16 // keyed_hash 17 // yura_hash 18 // r5_hash 19 // 20 21 #include <linux/kernel.h> 22 #include "reiserfs.h" 23 #include <asm/types.h> 24 25 #define DELTA 0x9E3779B9 26 #define FULLROUNDS 10 /* 32 is overkill, 16 is strong crypto */ 27 #define PARTROUNDS 6 /* 6 gets complete mixing */ 28 29 /* a, b, c, d - data; h0, h1 - accumulated hash */ 30 #define TEACORE(rounds) \ 31 do { \ 32 u32 sum = 0; \ 33 int n = rounds; \ 34 u32 b0, b1; \ 35 \ 36 b0 = h0; \ 37 b1 = h1; \ 38 \ 39 do \ 40 { \ 41 sum += DELTA; \ 42 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); \ 43 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); \ 44 } while(--n); \ 45 \ 46 h0 += b0; \ 47 h1 += b1; \ 48 } while(0) 49 50 u32 keyed_hash(const signed char *msg, int len) 51 { 52 u32 k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3 }; 53 54 u32 h0 = k[0], h1 = k[1]; 55 u32 a, b, c, d; 56 u32 pad; 57 int i; 58 59 // assert(len >= 0 && len < 256); 60 61 pad = (u32) len | ((u32) len << 8); 62 pad |= pad << 16; 63 64 while (len >= 16) { 65 a = (u32) msg[0] | 66 (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24; 67 b = (u32) msg[4] | 68 (u32) msg[5] << 8 | (u32) msg[6] << 16 | (u32) msg[7] << 24; 69 c = (u32) msg[8] | 70 (u32) msg[9] << 8 | 71 (u32) msg[10] << 16 | (u32) msg[11] << 24; 72 d = (u32) msg[12] | 73 (u32) msg[13] << 8 | 74 (u32) msg[14] << 16 | (u32) msg[15] << 24; 75 76 TEACORE(PARTROUNDS); 77 78 len -= 16; 79 msg += 16; 80 } 81 82 if (len >= 12) { 83 a = (u32) msg[0] | 84 (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24; 85 b = (u32) msg[4] | 86 (u32) msg[5] << 8 | (u32) msg[6] << 16 | (u32) msg[7] << 24; 87 c = (u32) msg[8] | 88 (u32) msg[9] << 8 | 89 (u32) msg[10] << 16 | (u32) msg[11] << 24; 90 91 d = pad; 92 for (i = 12; i < len; i++) { 93 d <<= 8; 94 d |= msg[i]; 95 } 96 } else if (len >= 8) { 97 a = (u32) msg[0] | 98 (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24; 99 b = (u32) msg[4] | 100 (u32) msg[5] << 8 | (u32) msg[6] << 16 | (u32) msg[7] << 24; 101 102 c = d = pad; 103 for (i = 8; i < len; i++) { 104 c <<= 8; 105 c |= msg[i]; 106 } 107 } else if (len >= 4) { 108 a = (u32) msg[0] | 109 (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24; 110 111 b = c = d = pad; 112 for (i = 4; i < len; i++) { 113 b <<= 8; 114 b |= msg[i]; 115 } 116 } else { 117 a = b = c = d = pad; 118 for (i = 0; i < len; i++) { 119 a <<= 8; 120 a |= msg[i]; 121 } 122 } 123 124 TEACORE(FULLROUNDS); 125 126 /* return 0;*/ 127 return h0 ^ h1; 128 } 129 130 /* What follows in this file is copyright 2000 by Hans Reiser, and the 131 * licensing of what follows is governed by reiserfs/README */ 132 133 u32 yura_hash(const signed char *msg, int len) 134 { 135 int j, pow; 136 u32 a, c; 137 int i; 138 139 for (pow = 1, i = 1; i < len; i++) 140 pow = pow * 10; 141 142 if (len == 1) 143 a = msg[0] - 48; 144 else 145 a = (msg[0] - 48) * pow; 146 147 for (i = 1; i < len; i++) { 148 c = msg[i] - 48; 149 for (pow = 1, j = i; j < len - 1; j++) 150 pow = pow * 10; 151 a = a + c * pow; 152 } 153 154 for (; i < 40; i++) { 155 c = '0' - 48; 156 for (pow = 1, j = i; j < len - 1; j++) 157 pow = pow * 10; 158 a = a + c * pow; 159 } 160 161 for (; i < 256; i++) { 162 c = i; 163 for (pow = 1, j = i; j < len - 1; j++) 164 pow = pow * 10; 165 a = a + c * pow; 166 } 167 168 a = a << 7; 169 return a; 170 } 171 172 u32 r5_hash(const signed char *msg, int len) 173 { 174 u32 a = 0; 175 while (*msg) { 176 a += *msg << 4; 177 a += *msg >> 4; 178 a *= 11; 179 msg++; 180 } 181 return a; 182 } 183