sys/gnu/fs/reiserfs/reiserfs_hashes.c

   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
  57 uint32_t
  58 keyed_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  * */
 160 uint32_t
 161 yura_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
 200 uint32_t
 201 r5_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 }