"Fossies" - the Fresh Open Source Software Archive

Member "reiserfsprogs-3.6.25/reiserfscore/hashes.c" (27 Aug 2013, 4134 Bytes) of archive /linux/misc/reiserfsprogs-3.6.25.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hashes.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.6.24_vs_3.6.25.

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