Blame view
fs/reiserfs/hashes.c
3.52 KB
1da177e4c
|
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
|
10 |
* |
1da177e4c
|
11 12 13 |
* Jeremy has agreed to the contents of reiserfs/README. -Hans * Yura's function is added (04/07/2000) */ |
1da177e4c
|
14 |
#include <linux/kernel.h> |
f466c6fdb
|
15 |
#include "reiserfs.h" |
1da177e4c
|
16 |
#include <asm/types.h> |
1da177e4c
|
17 |
|
1da177e4c
|
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#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
|
42 43 |
u32 keyed_hash(const signed char *msg, int len) { |
bd4c625c0
|
44 |
u32 k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3 }; |
1da177e4c
|
45 46 47 48 49 |
u32 h0 = k[0], h1 = k[1]; u32 a, b, c, d; u32 pad; int i; |
1da177e4c
|
50 |
|
098297b27
|
51 |
/* assert(len >= 0 && len < 256); */ |
bd4c625c0
|
52 53 |
pad = (u32) len | ((u32) len << 8); |
1da177e4c
|
54 |
pad |= pad << 16; |
bd4c625c0
|
55 56 57 58 59 60 61 62 63 64 65 |
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
|
66 67 68 69 70 |
TEACORE(PARTROUNDS); len -= 16; msg += 16; } |
bd4c625c0
|
71 72 73 74 75 76 77 78 |
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
|
79 80 |
d = pad; |
bd4c625c0
|
81 |
for (i = 12; i < len; i++) { |
1da177e4c
|
82 83 84 |
d <<= 8; d |= msg[i]; } |
bd4c625c0
|
85 86 87 88 89 |
} 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
|
90 91 |
c = d = pad; |
bd4c625c0
|
92 |
for (i = 8; i < len; i++) { |
1da177e4c
|
93 94 95 |
c <<= 8; c |= msg[i]; } |
bd4c625c0
|
96 97 98 |
} else if (len >= 4) { a = (u32) msg[0] | (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24; |
1da177e4c
|
99 100 |
b = c = d = pad; |
bd4c625c0
|
101 |
for (i = 4; i < len; i++) { |
1da177e4c
|
102 103 104 |
b <<= 8; b |= msg[i]; } |
bd4c625c0
|
105 |
} else { |
1da177e4c
|
106 |
a = b = c = d = pad; |
bd4c625c0
|
107 |
for (i = 0; i < len; i++) { |
1da177e4c
|
108 109 110 111 112 113 114 115 |
a <<= 8; a |= msg[i]; } } TEACORE(FULLROUNDS); /* return 0;*/ |
bd4c625c0
|
116 |
return h0 ^ h1; |
1da177e4c
|
117 |
} |
098297b27
|
118 119 120 121 |
/* * What follows in this file is copyright 2000 by Hans Reiser, and the * licensing of what follows is governed by reiserfs/README */ |
bd4c625c0
|
122 |
u32 yura_hash(const signed char *msg, int len) |
1da177e4c
|
123 |
{ |
bd4c625c0
|
124 125 126 127 128 129 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 |
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
|
159 |
} |
bd4c625c0
|
160 |
u32 r5_hash(const signed char *msg, int len) |
1da177e4c
|
161 |
{ |
bd4c625c0
|
162 163 164 165 166 167 168 169 |
u32 a = 0; while (*msg) { a += *msg << 4; a += *msg >> 4; a *= 11; msg++; } return a; |
1da177e4c
|
170 |
} |