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 // Modified by Ingo Weinhold (bonefish), Jan. 2003: 16 // Fixed r5_hash() and added key_offset_for_name(). 17 18 // 19 // keyed_hash 20 // yura_hash 21 // r5_hash 22 // 23 24 #include "hashes.h" 25 #include "reiserfs.h" 26 27 #define DELTA 0x9E3779B9 28 #define FULLROUNDS 10 /* 32 is overkill, 16 is strong crypto */ 29 #define PARTROUNDS 6 /* 6 gets complete mixing */ 30 31 /* a, b, c, d - data; h0, h1 - accumulated hash */ 32 #define TEACORE(rounds) \ 33 do { \ 34 uint32 sum = 0; \ 35 int n = rounds; \ 36 uint32 b0, b1; \ 37 \ 38 b0 = h0; \ 39 b1 = h1; \ 40 \ 41 do \ 42 { \ 43 sum += DELTA; \ 44 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); \ 45 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); \ 46 } while(--n); \ 47 \ 48 h0 += b0; \ 49 h1 += b1; \ 50 } while(0) 51 52 53 uint32 keyed_hash(const signed char *msg, int len) 54 { 55 uint32 k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3}; 56 57 uint32 h0 = k[0], h1 = k[1]; 58 uint32 a, b, c, d; 59 uint32 pad; 60 int i; 61 62 63 // assert(len >= 0 && len < 256); 64 65 pad = (uint32)len | ((uint32)len << 8); 66 pad |= pad << 16; 67 68 while(len >= 16) 69 { 70 a = (uint32)msg[ 0] | 71 (uint32)msg[ 1] << 8 | 72 (uint32)msg[ 2] << 16| 73 (uint32)msg[ 3] << 24; 74 b = (uint32)msg[ 4] | 75 (uint32)msg[ 5] << 8 | 76 (uint32)msg[ 6] << 16| 77 (uint32)msg[ 7] << 24; 78 c = (uint32)msg[ 8] | 79 (uint32)msg[ 9] << 8 | 80 (uint32)msg[10] << 16| 81 (uint32)msg[11] << 24; 82 d = (uint32)msg[12] | 83 (uint32)msg[13] << 8 | 84 (uint32)msg[14] << 16| 85 (uint32)msg[15] << 24; 86 87 TEACORE(PARTROUNDS); 88 89 len -= 16; 90 msg += 16; 91 } 92 93 if (len >= 12) 94 { 95 //assert(len < 16); 96 if (len >= 16) 97 *(int *)0 = 0; 98 99 a = (uint32)msg[ 0] | 100 (uint32)msg[ 1] << 8 | 101 (uint32)msg[ 2] << 16| 102 (uint32)msg[ 3] << 24; 103 b = (uint32)msg[ 4] | 104 (uint32)msg[ 5] << 8 | 105 (uint32)msg[ 6] << 16| 106 (uint32)msg[ 7] << 24; 107 c = (uint32)msg[ 8] | 108 (uint32)msg[ 9] << 8 | 109 (uint32)msg[10] << 16| 110 (uint32)msg[11] << 24; 111 112 d = pad; 113 for(i = 12; i < len; i++) 114 { 115 d <<= 8; 116 d |= msg[i]; 117 } 118 } 119 else if (len >= 8) 120 { 121 //assert(len < 12); 122 if (len >= 12) 123 *(int *)0 = 0; 124 a = (uint32)msg[ 0] | 125 (uint32)msg[ 1] << 8 | 126 (uint32)msg[ 2] << 16| 127 (uint32)msg[ 3] << 24; 128 b = (uint32)msg[ 4] | 129 (uint32)msg[ 5] << 8 | 130 (uint32)msg[ 6] << 16| 131 (uint32)msg[ 7] << 24; 132 133 c = d = pad; 134 for(i = 8; i < len; i++) 135 { 136 c <<= 8; 137 c |= msg[i]; 138 } 139 } 140 else if (len >= 4) 141 { 142 //assert(len < 8); 143 if (len >= 8) 144 *(int *)0 = 0; 145 a = (uint32)msg[ 0] | 146 (uint32)msg[ 1] << 8 | 147 (uint32)msg[ 2] << 16| 148 (uint32)msg[ 3] << 24; 149 150 b = c = d = pad; 151 for(i = 4; i < len; i++) 152 { 153 b <<= 8; 154 b |= msg[i]; 155 } 156 } 157 else 158 { 159 //assert(len < 4); 160 if (len >= 4) 161 *(int *)0 = 0; 162 a = b = c = d = pad; 163 for(i = 0; i < len; i++) 164 { 165 a <<= 8; 166 a |= msg[i]; 167 } 168 } 169 170 TEACORE(FULLROUNDS); 171 172 /* return 0;*/ 173 return h0^h1; 174 } 175 176 /* What follows in this file is copyright 2000 by Hans Reiser, and the 177 * licensing of what follows is governed by reiserfs/README */ 178 179 uint32 yura_hash (const signed char *msg, int len) 180 { 181 int j, pow; 182 uint32 a, c; 183 int i; 184 185 for (pow=1,i=1; i < len; i++) pow = pow * 10; 186 187 if (len == 1) 188 a = msg[0]-48; 189 else 190 a = (msg[0] - 48) * pow; 191 192 for (i=1; i < len; i++) { 193 c = msg[i] - 48; 194 for (pow=1,j=i; j < len-1; j++) pow = pow * 10; 195 a = a + c * pow; 196 } 197 198 for (; i < 40; i++) { 199 c = '0' - 48; 200 for (pow=1,j=i; j < len-1; j++) pow = pow * 10; 201 a = a + c * pow; 202 } 203 204 for (; i < 256; i++) { 205 c = i; 206 for (pow=1,j=i; j < len-1; j++) pow = pow * 10; 207 a = a + c * pow; 208 } 209 210 a = a << 7; 211 return a; 212 } 213 214 uint32 r5_hash (const signed char *msg, int len) 215 { 216 uint32 a=0; 217 // bonefish: len was ignored 218 // while(*msg) { 219 while(len--) { 220 a += *msg << 4; 221 a += *msg >> 4; 222 a *= 11; 223 msg++; 224 } 225 return a; 226 } 227 228 229 // bonefish: 230 // from reiserfs_fs.h: 231 /* hash value occupies bits from 7 up to 30 */ 232 #define GET_HASH_VALUE(offset) ((offset) & 0x7fffff80LL) 233 #define MAX_GENERATION_NUMBER 127 234 235 // bonefish: 236 // derived from name.c: get_third_component() 237 uint32 238 key_offset_for_name(hash_function_t hash, const char *name, int len) 239 { 240 uint32 res; 241 242 if (!len || (len == 1 && name[0] == '.')) 243 return DOT_OFFSET; 244 if (len == 2 && name[0] == '.' && name[1] == '.') 245 return DOT_DOT_OFFSET; 246 247 res = (*hash)((const signed char*)name, len); 248 249 // take bits from 7-th to 30-th including both bounds 250 res = GET_HASH_VALUE(res); 251 if (res == 0) 252 // needed to have no names before "." and ".." those have hash 253 // value == 0 and generation conters 1 and 2 accordingly 254 res = 128; 255 return res + MAX_GENERATION_NUMBER; 256 } 257 258