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 "mozilla/BasePrincipal.h"
   8 #include "mozilla/EndianUtils.h"
   9 #include "mozilla/SHA1.h"
  10
  11 namespace mozilla::net {
  12
  13 /**
  14  *  CacheHash::Hash(const char * key, uint32_t initval)
  15  *
  16  *  See http://burtleburtle.net/bob/hash/evahash.html for more information
  17  *  about this hash function.
  18  *
  19  *  This algorithm is used to check the data integrity.
  20  */
  21
  22 static inline void hashmix(uint32_t& a, uint32_t& b, uint32_t& c) {
  23   a -= b;
  24   a -= c;
  25   a ^= (c >> 13);
  26   b -= c;
  27   b -= a;
  28   b ^= (a << 8);
  29   c -= a;
  30   c -= b;
  31   c ^= (b >> 13);
  32   a -= b;
  33   a -= c;
  34   a ^= (c >> 12);
  35   b -= c;
  36   b -= a;
  37   b ^= (a << 16);
  38   c -= a;
  39   c -= b;
  40   c ^= (b >> 5);
  41   a -= b;
  42   a -= c;
  43   a ^= (c >> 3);
  44   b -= c;
  45   b -= a;
  46   b ^= (a << 10);
  47   c -= a;
  48   c -= b;
  49   c ^= (b >> 15);
  50 }
  51
  52 CacheHash::Hash32_t CacheHash::Hash(const char* aData, uint32_t aSize,
  53                                     uint32_t aInitval) {
  54   const uint8_t* k = reinterpret_cast<const uint8_t*>(aData);
  55   uint32_t a, b, c, len;
  56
  57   /* Set up the internal state */
  58   len = aSize;
  59   a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
  60   c = aInitval;       /* variable initialization of internal state */
  61
  62   /*---------------------------------------- handle most of the key */
  63   while (len >= 12) {
  64     a += k[0] + (uint32_t(k[1]) << 8) + (uint32_t(k[2]) << 16) +
  65          (uint32_t(k[3]) << 24);
  66     b += k[4] + (uint32_t(k[5]) << 8) + (uint32_t(k[6]) << 16) +
  67          (uint32_t(k[7]) << 24);
  68     c += k[8] + (uint32_t(k[9]) << 8) + (uint32_t(k[10]) << 16) +
  69          (uint32_t(k[11]) << 24);
  70     hashmix(a, b, c);
  71     k += 12;
  72     len -= 12;
  73   }
  74
  75   /*------------------------------------- handle the last 11 bytes */
  76   c += aSize;
  77   switch (len) { /* all the case statements fall through */
  78     case 11:
  79       c += (uint32_t(k[10]) << 24);
  80       [[fallthrough]];
  81     case 10:
  82       c += (uint32_t(k[9]) << 16);
  83       [[fallthrough]];
  84     case 9:
  85       c += (uint32_t(k[8]) << 8);
  86       [[fallthrough]];
  87     /* the low-order byte of c is reserved for the length */
  88     case 8:
  89       b += (uint32_t(k[7]) << 24);
  90       [[fallthrough]];
  91     case 7:
  92       b += (uint32_t(k[6]) << 16);
  93       [[fallthrough]];
  94     case 6:
  95       b += (uint32_t(k[5]) << 8);
  96       [[fallthrough]];
  97     case 5:
  98       b += k[4];
  99       [[fallthrough]];
 100     case 4:
 101       a += (uint32_t(k[3]) << 24);
 102       [[fallthrough]];
 103     case 3:
 104       a += (uint32_t(k[2]) << 16);
 105       [[fallthrough]];
 106     case 2:
 107       a += (uint32_t(k[1]) << 8);
 108       [[fallthrough]];
 109     case 1:
 110       a += k[0];
 111       /* case 0: nothing left to add */
 112   }
 113   hashmix(a, b, c);
 114
 115   return c;
 116 }
 117
 118 CacheHash::Hash16_t CacheHash::Hash16(const char* aData, uint32_t aSize,
 119                                       uint32_t aInitval) {
 120   Hash32_t hash = Hash(aData, aSize, aInitval);
 121   return (hash & 0xFFFF);
 122 }
 123
 124 NS_IMPL_ISUPPORTS0(CacheHash)
 125
 126 CacheHash::CacheHash(uint32_t aInitval) : mC(aInitval) {}
 127
 128 void CacheHash::Feed(uint32_t aVal, uint8_t aLen) {
 129   switch (mPos) {
 130     case 0:
 131       mA += aVal;
 132       mPos++;
 133       break;
 134
 135     case 1:
 136       mB += aVal;
 137       mPos++;
 138       break;
 139
 140     case 2:
 141       mPos = 0;
 142       if (aLen == 4) {
 143         mC += aVal;
 144         hashmix(mA, mB, mC);
 145       } else {
 146         mC += aVal << 8;
 147       }
 148   }
 149
 150   mLength += aLen;
 151 }
 152
 153 void CacheHash::Update(const char* aData, uint32_t aLen) {
 154   const uint8_t* data = reinterpret_cast<const uint8_t*>(aData);
 155
 156   MOZ_ASSERT(!mFinalized);
 157
 158   if (mBufPos) {
 159     while (mBufPos != 4 && aLen) {
 160       mBuf += uint32_t(*data) << 8 * mBufPos;
 161       data++;
 162       mBufPos++;
 163       aLen--;
 164     }
 165
 166     if (mBufPos == 4) {
 167       mBufPos = 0;
 168       Feed(mBuf);
 169       mBuf = 0;
 170     }
 171   }
 172
 173   if (!aLen) return;
 174
 175   while (aLen >= 4) {
 176     Feed(data[0] + (uint32_t(data[1]) << 8) + (uint32_t(data[2]) << 16) +
 177          (uint32_t(data[3]) << 24));
 178     data += 4;
 179     aLen -= 4;
 180   }
 181
 182   switch (aLen) {
 183     case 3:
 184       mBuf += data[2] << 16;
 185       [[fallthrough]];
 186     case 2:
 187       mBuf += data[1] << 8;
 188       [[fallthrough]];
 189     case 1:
 190       mBuf += data[0];
 191   }
 192
 193   mBufPos = aLen;
 194 }
 195
 196 CacheHash::Hash32_t CacheHash::GetHash() {
 197   if (!mFinalized) {
 198     if (mBufPos) {
 199       Feed(mBuf, mBufPos);
 200     }
 201     mC += mLength;
 202     hashmix(mA, mB, mC);
 203     mFinalized = true;
 204   }
 205
 206   return mC;
 207 }
 208
 209 CacheHash::Hash16_t CacheHash::GetHash16() {
 210   Hash32_t hash = GetHash();
 211   return (hash & 0xFFFF);
 212 }
 213
 214 OriginAttrsHash GetOriginAttrsHash(const mozilla::OriginAttributes& aOA) {
 215   nsAutoCString suffix;
 216   aOA.CreateSuffix(suffix);
 217
 218   SHA1Sum sum;
 219   SHA1Sum::Hash hash;
 220   sum.update(suffix.BeginReading(), suffix.Length());
 221   sum.finish(hash);
 222
 223   return BigEndian::readUint64(&hash);
 224 }
 225
 226 }  // namespace mozilla::net