CacheHashUtils.cpp (4904B)
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