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