fs/reiserfs/hashes.c

0001
0002 /*
0003  * Keyed 32-bit hash function using TEA in a Davis-Meyer function
0004  *   H0 = Key
0005  *   Hi = E Mi(Hi-1) + Hi-1
0006  *
0007  * (see Applied Cryptography, 2nd edition, p448).
0008  *
0009  * Jeremy Fitzhardinge <jeremy@zip.com.au> 1998
0010  *
0011  * Jeremy has agreed to the contents of reiserfs/README. -Hans
0012  * Yura's function is added (04/07/2000)
0013  */
0014
0015 #include <linux/kernel.h>
0016 #include "reiserfs.h"
0017 #include <asm/types.h>
0018
0019 #define DELTA 0x9E3779B9
0020 #define FULLROUNDS 10       /* 32 is overkill, 16 is strong crypto */
0021 #define PARTROUNDS 6        /* 6 gets complete mixing */
0022
0023 /* a, b, c, d - data; h0, h1 - accumulated hash */
0024 #define TEACORE(rounds)                         \
0025     do {                                \
0026         u32 sum = 0;                        \
0027         int n = rounds;                     \
0028         u32 b0, b1;                     \
0029                                     \
0030         b0 = h0;                        \
0031         b1 = h1;                        \
0032                                     \
0033         do                          \
0034         {                           \
0035             sum += DELTA;                   \
0036             b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); \
0037             b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); \
0038         } while(--n);                       \
0039                                     \
0040         h0 += b0;                       \
0041         h1 += b1;                       \
0042     } while(0)
0043
0044 u32 keyed_hash(const signed char *msg, int len)
0045 {
0046     u32 k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3 };
0047
0048     u32 h0 = k[0], h1 = k[1];
0049     u32 a, b, c, d;
0050     u32 pad;
0051     int i;
0052
0053     /*      assert(len >= 0 && len < 256); */
0054
0055     pad = (u32) len | ((u32) len << 8);
0056     pad |= pad << 16;
0057
0058     while (len >= 16) {
0059         a = (u32) msg[0] |
0060             (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24;
0061         b = (u32) msg[4] |
0062             (u32) msg[5] << 8 | (u32) msg[6] << 16 | (u32) msg[7] << 24;
0063         c = (u32) msg[8] |
0064             (u32) msg[9] << 8 |
0065             (u32) msg[10] << 16 | (u32) msg[11] << 24;
0066         d = (u32) msg[12] |
0067             (u32) msg[13] << 8 |
0068             (u32) msg[14] << 16 | (u32) msg[15] << 24;
0069
0070         TEACORE(PARTROUNDS);
0071
0072         len -= 16;
0073         msg += 16;
0074     }
0075
0076     if (len >= 12) {
0077         a = (u32) msg[0] |
0078             (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24;
0079         b = (u32) msg[4] |
0080             (u32) msg[5] << 8 | (u32) msg[6] << 16 | (u32) msg[7] << 24;
0081         c = (u32) msg[8] |
0082             (u32) msg[9] << 8 |
0083             (u32) msg[10] << 16 | (u32) msg[11] << 24;
0084
0085         d = pad;
0086         for (i = 12; i < len; i++) {
0087             d <<= 8;
0088             d |= msg[i];
0089         }
0090     } else if (len >= 8) {
0091         a = (u32) msg[0] |
0092             (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24;
0093         b = (u32) msg[4] |
0094             (u32) msg[5] << 8 | (u32) msg[6] << 16 | (u32) msg[7] << 24;
0095
0096         c = d = pad;
0097         for (i = 8; i < len; i++) {
0098             c <<= 8;
0099             c |= msg[i];
0100         }
0101     } else if (len >= 4) {
0102         a = (u32) msg[0] |
0103             (u32) msg[1] << 8 | (u32) msg[2] << 16 | (u32) msg[3] << 24;
0104
0105         b = c = d = pad;
0106         for (i = 4; i < len; i++) {
0107             b <<= 8;
0108             b |= msg[i];
0109         }
0110     } else {
0111         a = b = c = d = pad;
0112         for (i = 0; i < len; i++) {
0113             a <<= 8;
0114             a |= msg[i];
0115         }
0116     }
0117
0118     TEACORE(FULLROUNDS);
0119
0120 /*  return 0;*/
0121     return h0 ^ h1;
0122 }
0123
0124 /*
0125  * What follows in this file is copyright 2000 by Hans Reiser, and the
0126  * licensing of what follows is governed by reiserfs/README
0127  */
0128 u32 yura_hash(const signed char *msg, int len)
0129 {
0130     int j, pow;
0131     u32 a, c;
0132     int i;
0133
0134     for (pow = 1, i = 1; i < len; i++)
0135         pow = pow * 10;
0136
0137     if (len == 1)
0138         a = msg[0] - 48;
0139     else
0140         a = (msg[0] - 48) * pow;
0141
0142     for (i = 1; i < len; i++) {
0143         c = msg[i] - 48;
0144         for (pow = 1, j = i; j < len - 1; j++)
0145             pow = pow * 10;
0146         a = a + c * pow;
0147     }
0148
0149     for (; i < 40; i++) {
0150         c = '0' - 48;
0151         for (pow = 1, j = i; j < len - 1; j++)
0152             pow = pow * 10;
0153         a = a + c * pow;
0154     }
0155
0156     for (; i < 256; i++) {
0157         c = i;
0158         for (pow = 1, j = i; j < len - 1; j++)
0159             pow = pow * 10;
0160         a = a + c * pow;
0161     }
0162
0163     a = a << 7;
0164     return a;
0165 }
0166
0167 u32 r5_hash(const signed char *msg, int len)
0168 {
0169     u32 a = 0;
0170     while (*msg) {
0171         a += *msg << 4;
0172         a += *msg >> 4;
0173         a *= 11;
0174         msg++;
0175     }
0176     return a;
0177 }