178 lines · c
1 2/*3 * Keyed 32-bit hash function using TEA in a Davis-Meyer function4 * H0 = Key5 * Hi = E Mi(Hi-1) + Hi-16 *7 * (see Applied Cryptography, 2nd edition, p448).8 *9 * Jeremy Fitzhardinge <jeremy@zip.com.au> 199810 *11 * Jeremy has agreed to the contents of reiserfs/README. -Hans12 * 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 0x9E3779B920#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 44u32 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 the126 * licensing of what follows is governed by reiserfs/README127 */128u32 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 else140 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 167u32 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