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