michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "CacheHashUtils.h"
michael@0: 
michael@0: #include "plstr.h"
michael@0: 
michael@0: namespace mozilla {
michael@0: namespace net {
michael@0: 
michael@0: /**
michael@0:  *  CacheHash::Hash(const char * key, uint32_t initval)
michael@0:  *
michael@0:  *  See http://burtleburtle.net/bob/hash/evahash.html for more information
michael@0:  *  about this hash function.
michael@0:  *
michael@0:  *  This algorithm is used to check the data integrity.
michael@0:  */
michael@0: 
michael@0: static inline void hashmix(uint32_t& a, uint32_t& b, uint32_t& c)
michael@0: {
michael@0:   a -= b; a -= c; a ^= (c>>13);
michael@0:   b -= c; b -= a; b ^= (a<<8);
michael@0:   c -= a; c -= b; c ^= (b>>13);
michael@0:   a -= b; a -= c; a ^= (c>>12);
michael@0:   b -= c; b -= a; b ^= (a<<16);
michael@0:   c -= a; c -= b; c ^= (b>>5);
michael@0:   a -= b; a -= c; a ^= (c>>3);
michael@0:   b -= c; b -= a; b ^= (a<<10);
michael@0:   c -= a; c -= b; c ^= (b>>15);
michael@0: }
michael@0: 
michael@0: CacheHash::Hash32_t
michael@0: CacheHash::Hash(const char *aData, uint32_t aSize, uint32_t aInitval)
michael@0: {
michael@0:   const uint8_t *k = reinterpret_cast<const uint8_t*>(aData);
michael@0:   uint32_t a, b, c, len;
michael@0: 
michael@0: //  length = PL_strlen(key);
michael@0:   /* Set up the internal state */
michael@0:   len = aSize;
michael@0:   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
michael@0:   c = aInitval;        /* variable initialization of internal state */
michael@0: 
michael@0:   /*---------------------------------------- handle most of the key */
michael@0:   while (len >= 12)
michael@0:   {
michael@0:     a += k[0] + (uint32_t(k[1])<<8) + (uint32_t(k[2])<<16) + (uint32_t(k[3])<<24);
michael@0:     b += k[4] + (uint32_t(k[5])<<8) + (uint32_t(k[6])<<16) + (uint32_t(k[7])<<24);
michael@0:     c += k[8] + (uint32_t(k[9])<<8) + (uint32_t(k[10])<<16) + (uint32_t(k[11])<<24);
michael@0:     hashmix(a, b, c);
michael@0:     k += 12; len -= 12;
michael@0:   }
michael@0: 
michael@0:   /*------------------------------------- handle the last 11 bytes */
michael@0:   c += aSize;
michael@0:   switch(len) {              /* all the case statements fall through */
michael@0:     case 11: c += (uint32_t(k[10])<<24);
michael@0:     case 10: c += (uint32_t(k[9])<<16);
michael@0:     case 9 : c += (uint32_t(k[8])<<8);
michael@0:     /* the low-order byte of c is reserved for the length */
michael@0:     case 8 : b += (uint32_t(k[7])<<24);
michael@0:     case 7 : b += (uint32_t(k[6])<<16);
michael@0:     case 6 : b += (uint32_t(k[5])<<8);
michael@0:     case 5 : b += k[4];
michael@0:     case 4 : a += (uint32_t(k[3])<<24);
michael@0:     case 3 : a += (uint32_t(k[2])<<16);
michael@0:     case 2 : a += (uint32_t(k[1])<<8);
michael@0:     case 1 : a += k[0];
michael@0:     /* case 0: nothing left to add */
michael@0:   }
michael@0:   hashmix(a, b, c);
michael@0: 
michael@0:   return c;
michael@0: }
michael@0: 
michael@0: CacheHash::Hash16_t
michael@0: CacheHash::Hash16(const char *aData, uint32_t aSize, uint32_t aInitval)
michael@0: {
michael@0:   Hash32_t hash = Hash(aData, aSize, aInitval);
michael@0:   return (hash & 0xFFFF);
michael@0: }
michael@0: 
michael@0: NS_IMPL_ISUPPORTS0(CacheHash)
michael@0: 
michael@0: CacheHash::CacheHash(uint32_t aInitval)
michael@0:   : mA(0x9e3779b9)
michael@0:   , mB(0x9e3779b9)
michael@0:   , mC(aInitval)
michael@0:   , mPos(0)
michael@0:   , mBuf(0)
michael@0:   , mBufPos(0)
michael@0:   , mLength(0)
michael@0:   , mFinalized(false)
michael@0: {}
michael@0: 
michael@0: void
michael@0: CacheHash::Feed(uint32_t aVal, uint8_t aLen)
michael@0: {
michael@0:   switch (mPos) {
michael@0:   case 0:
michael@0:     mA += aVal;
michael@0:     mPos ++;
michael@0:     break;
michael@0: 
michael@0:   case 1:
michael@0:     mB += aVal;
michael@0:     mPos ++;
michael@0:     break;
michael@0: 
michael@0:   case 2:
michael@0:     mPos = 0;
michael@0:     if (aLen == 4) {
michael@0:       mC += aVal;
michael@0:       hashmix(mA, mB, mC);
michael@0:     }
michael@0:     else {
michael@0:       mC += aVal << 8;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   mLength += aLen;
michael@0: }
michael@0: 
michael@0: void
michael@0: CacheHash::Update(const char *aData, uint32_t aLen)
michael@0: {
michael@0:   const uint8_t *data = reinterpret_cast<const uint8_t*>(aData);
michael@0: 
michael@0:   MOZ_ASSERT(!mFinalized);
michael@0: 
michael@0:   if (mBufPos) {
michael@0:     while (mBufPos != 4 && aLen) {
michael@0:       mBuf += uint32_t(*data) << 8*mBufPos;
michael@0:       data++;
michael@0:       mBufPos++;
michael@0:       aLen--;
michael@0:     }
michael@0: 
michael@0:     if (mBufPos == 4) {
michael@0:       mBufPos = 0;
michael@0:       Feed(mBuf);
michael@0:       mBuf = 0;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (!aLen)
michael@0:     return;
michael@0: 
michael@0:   while (aLen >= 4) {
michael@0:     Feed(data[0] + (uint32_t(data[1]) << 8) + (uint32_t(data[2]) << 16) +
michael@0:          (uint32_t(data[3]) << 24));
michael@0:     data += 4;
michael@0:     aLen -= 4;
michael@0:   }
michael@0: 
michael@0:   switch (aLen) {
michael@0:     case 3: mBuf += data[2] << 16;
michael@0:     case 2: mBuf += data[1] << 8;
michael@0:     case 1: mBuf += data[0];
michael@0:   }
michael@0: 
michael@0:   mBufPos = aLen;
michael@0: }
michael@0: 
michael@0: CacheHash::Hash32_t
michael@0: CacheHash::GetHash()
michael@0: {
michael@0:   if (!mFinalized)
michael@0:   {
michael@0:     if (mBufPos) {
michael@0:       Feed(mBuf, mBufPos);
michael@0:     }
michael@0:     mC += mLength;
michael@0:     hashmix(mA, mB, mC);
michael@0:     mFinalized = true;
michael@0:   }
michael@0: 
michael@0:   return mC;
michael@0: }
michael@0: 
michael@0: CacheHash::Hash16_t
michael@0: CacheHash::GetHash16()
michael@0: {
michael@0:   Hash32_t hash = GetHash();
michael@0:   return (hash & 0xFFFF);
michael@0: }
michael@0: 
michael@0: } // net
michael@0: } // mozilla
michael@0: