The Tor Browser: netwerk/cache2/CacheHashUtils.cpp@6474c204b198

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     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/. */

     5 #include "CacheHashUtils.h"

     7 #include "plstr.h"

     9 namespace mozilla {

    10 namespace net {

    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  */

    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 }

    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;

    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 */

    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   }

    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);

    75   return c;

    76 }

    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 }

    85 NS_IMPL_ISUPPORTS0(CacheHash)

    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 {}

    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;

   107   case 1:

   108     mB += aVal;

   109     mPos ++;

   110     break;

   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   }

   123   mLength += aLen;

   124 }

   126 void

   127 CacheHash::Update(const char *aData, uint32_t aLen)

   128 {

   129   const uint8_t *data = reinterpret_cast<const uint8_t*>(aData);

   131   MOZ_ASSERT(!mFinalized);

   133   if (mBufPos) {

   134     while (mBufPos != 4 && aLen) {

   135       mBuf += uint32_t(*data) << 8*mBufPos;

   136       data++;

   137       mBufPos++;

   138       aLen--;

   139     }

   141     if (mBufPos == 4) {

   142       mBufPos = 0;

   143       Feed(mBuf);

   144       mBuf = 0;

   145     }

   146   }

   148   if (!aLen)

   149     return;

   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   }

   158   switch (aLen) {

   159     case 3: mBuf += data[2] << 16;

   160     case 2: mBuf += data[1] << 8;

   161     case 1: mBuf += data[0];

   162   }

   164   mBufPos = aLen;

   165 }

   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   }

   180   return mC;

   181 }

   183 CacheHash::Hash16_t

   184 CacheHash::GetHash16()

   185 {

   186   Hash32_t hash = GetHash();

   187   return (hash & 0xFFFF);

   188 }

   190 } // net

   191 } // mozilla

The Tor Browser / file revision