netwerk/cache2/CacheHashUtils.cpp

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 #include "CacheHashUtils.h"
   6
   7 #include "plstr.h"
   8
   9 namespace mozilla {
  10 namespace net {
  11
  12 /**
  13  *  CacheHash::Hash(const char * key, uint32_t initval)
  14  *
  15  *  See http://burtleburtle.net/bob/hash/evahash.html for more information
  16  *  about this hash function.
  17  *
  18  *  This algorithm is used to check the data integrity.
  19  */
  20
  21 static inline void hashmix(uint32_t& a, uint32_t& b, uint32_t& c)
  22 {
  23   a -= b; a -= c; a ^= (c>>13);
  24   b -= c; b -= a; b ^= (a<<8);
  25   c -= a; c -= b; c ^= (b>>13);
  26   a -= b; a -= c; a ^= (c>>12);
  27   b -= c; b -= a; b ^= (a<<16);
  28   c -= a; c -= b; c ^= (b>>5);
  29   a -= b; a -= c; a ^= (c>>3);
  30   b -= c; b -= a; b ^= (a<<10);
  31   c -= a; c -= b; c ^= (b>>15);
  32 }
  33
  34 CacheHash::Hash32_t
  35 CacheHash::Hash(const char *aData, uint32_t aSize, uint32_t aInitval)
  36 {
  37   const uint8_t *k = reinterpret_cast<const uint8_t*>(aData);
  38   uint32_t a, b, c, len;
  39
  40 //  length = PL_strlen(key);
  41   /* Set up the internal state */
  42   len = aSize;
  43   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
  44   c = aInitval;        /* variable initialization of internal state */
  45
  46   /*---------------------------------------- handle most of the key */
  47   while (len >= 12)
  48   {
  49     a += k[0] + (uint32_t(k[1])<<8) + (uint32_t(k[2])<<16) + (uint32_t(k[3])<<24);
  50     b += k[4] + (uint32_t(k[5])<<8) + (uint32_t(k[6])<<16) + (uint32_t(k[7])<<24);
  51     c += k[8] + (uint32_t(k[9])<<8) + (uint32_t(k[10])<<16) + (uint32_t(k[11])<<24);
  52     hashmix(a, b, c);
  53     k += 12; len -= 12;
  54   }
  55
  56   /*------------------------------------- handle the last 11 bytes */
  57   c += aSize;
  58   switch(len) {              /* all the case statements fall through */
  59     case 11: c += (uint32_t(k[10])<<24);
  60     case 10: c += (uint32_t(k[9])<<16);
  61     case 9 : c += (uint32_t(k[8])<<8);
  62     /* the low-order byte of c is reserved for the length */
  63     case 8 : b += (uint32_t(k[7])<<24);
  64     case 7 : b += (uint32_t(k[6])<<16);
  65     case 6 : b += (uint32_t(k[5])<<8);
  66     case 5 : b += k[4];
  67     case 4 : a += (uint32_t(k[3])<<24);
  68     case 3 : a += (uint32_t(k[2])<<16);
  69     case 2 : a += (uint32_t(k[1])<<8);
  70     case 1 : a += k[0];
  71     /* case 0: nothing left to add */
  72   }
  73   hashmix(a, b, c);
  74
  75   return c;
  76 }
  77
  78 CacheHash::Hash16_t
  79 CacheHash::Hash16(const char *aData, uint32_t aSize, uint32_t aInitval)
  80 {
  81   Hash32_t hash = Hash(aData, aSize, aInitval);
  82   return (hash & 0xFFFF);
  83 }
  84
  85 NS_IMPL_ISUPPORTS0(CacheHash)
  86
  87 CacheHash::CacheHash(uint32_t aInitval)
  88   : mA(0x9e3779b9)
  89   , mB(0x9e3779b9)
  90   , mC(aInitval)
  91   , mPos(0)
  92   , mBuf(0)
  93   , mBufPos(0)
  94   , mLength(0)
  95   , mFinalized(false)
  96 {}
  97
  98 void
  99 CacheHash::Feed(uint32_t aVal, uint8_t aLen)
 100 {
 101   switch (mPos) {
 102   case 0:
 103     mA += aVal;
 104     mPos ++;
 105     break;
 106
 107   case 1:
 108     mB += aVal;
 109     mPos ++;
 110     break;
 111
 112   case 2:
 113     mPos = 0;
 114     if (aLen == 4) {
 115       mC += aVal;
 116       hashmix(mA, mB, mC);
 117     }
 118     else {
 119       mC += aVal << 8;
 120     }
 121   }
 122
 123   mLength += aLen;
 124 }
 125
 126 void
 127 CacheHash::Update(const char *aData, uint32_t aLen)
 128 {
 129   const uint8_t *data = reinterpret_cast<const uint8_t*>(aData);
 130
 131   MOZ_ASSERT(!mFinalized);
 132
 133   if (mBufPos) {
 134     while (mBufPos != 4 && aLen) {
 135       mBuf += uint32_t(*data) << 8*mBufPos;
 136       data++;
 137       mBufPos++;
 138       aLen--;
 139     }
 140
 141     if (mBufPos == 4) {
 142       mBufPos = 0;
 143       Feed(mBuf);
 144       mBuf = 0;
 145     }
 146   }
 147
 148   if (!aLen)
 149     return;
 150
 151   while (aLen >= 4) {
 152     Feed(data[0] + (uint32_t(data[1]) << 8) + (uint32_t(data[2]) << 16) +
 153          (uint32_t(data[3]) << 24));
 154     data += 4;
 155     aLen -= 4;
 156   }
 157
 158   switch (aLen) {
 159     case 3: mBuf += data[2] << 16;
 160     case 2: mBuf += data[1] << 8;
 161     case 1: mBuf += data[0];
 162   }
 163
 164   mBufPos = aLen;
 165 }
 166
 167 CacheHash::Hash32_t
 168 CacheHash::GetHash()
 169 {
 170   if (!mFinalized)
 171   {
 172     if (mBufPos) {
 173       Feed(mBuf, mBufPos);
 174     }
 175     mC += mLength;
 176     hashmix(mA, mB, mC);
 177     mFinalized = true;
 178   }
 179
 180   return mC;
 181 }
 182
 183 CacheHash::Hash16_t
 184 CacheHash::GetHash16()
 185 {
 186   Hash32_t hash = GetHash();
 187   return (hash & 0xFFFF);
 188 }
 189
 190 } // net
 191 } // mozilla
 192