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