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