The Tor Browser / file comparison
comparison: netwerk/cache2/CacheHashUtils.cpp
netwerk/cache2/CacheHashUtils.cpp
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:85f91785f086 |
|---|---|
| 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 |
