1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/netwerk/cache2/CacheHashUtils.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,192 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#include "CacheHashUtils.h"
1.9 +
1.10 +#include "plstr.h"
1.11 +
1.12 +namespace mozilla {
1.13 +namespace net {
1.14 +
1.15 +/**
1.16 + * CacheHash::Hash(const char * key, uint32_t initval)
1.17 + *
1.18 + * See http://burtleburtle.net/bob/hash/evahash.html for more information
1.19 + * about this hash function.
1.20 + *
1.21 + * This algorithm is used to check the data integrity.
1.22 + */
1.23 +
1.24 +static inline void hashmix(uint32_t& a, uint32_t& b, uint32_t& c)
1.25 +{
1.26 + a -= b; a -= c; a ^= (c>>13);
1.27 + b -= c; b -= a; b ^= (a<<8);
1.28 + c -= a; c -= b; c ^= (b>>13);
1.29 + a -= b; a -= c; a ^= (c>>12);
1.30 + b -= c; b -= a; b ^= (a<<16);
1.31 + c -= a; c -= b; c ^= (b>>5);
1.32 + a -= b; a -= c; a ^= (c>>3);
1.33 + b -= c; b -= a; b ^= (a<<10);
1.34 + c -= a; c -= b; c ^= (b>>15);
1.35 +}
1.36 +
1.37 +CacheHash::Hash32_t
1.38 +CacheHash::Hash(const char *aData, uint32_t aSize, uint32_t aInitval)
1.39 +{
1.40 + const uint8_t *k = reinterpret_cast<const uint8_t*>(aData);
1.41 + uint32_t a, b, c, len;
1.42 +
1.43 +// length = PL_strlen(key);
1.44 + /* Set up the internal state */
1.45 + len = aSize;
1.46 + a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
1.47 + c = aInitval; /* variable initialization of internal state */
1.48 +
1.49 + /*---------------------------------------- handle most of the key */
1.50 + while (len >= 12)
1.51 + {
1.52 + a += k[0] + (uint32_t(k[1])<<8) + (uint32_t(k[2])<<16) + (uint32_t(k[3])<<24);
1.53 + b += k[4] + (uint32_t(k[5])<<8) + (uint32_t(k[6])<<16) + (uint32_t(k[7])<<24);
1.54 + c += k[8] + (uint32_t(k[9])<<8) + (uint32_t(k[10])<<16) + (uint32_t(k[11])<<24);
1.55 + hashmix(a, b, c);
1.56 + k += 12; len -= 12;
1.57 + }
1.58 +
1.59 + /*------------------------------------- handle the last 11 bytes */
1.60 + c += aSize;
1.61 + switch(len) { /* all the case statements fall through */
1.62 + case 11: c += (uint32_t(k[10])<<24);
1.63 + case 10: c += (uint32_t(k[9])<<16);
1.64 + case 9 : c += (uint32_t(k[8])<<8);
1.65 + /* the low-order byte of c is reserved for the length */
1.66 + case 8 : b += (uint32_t(k[7])<<24);
1.67 + case 7 : b += (uint32_t(k[6])<<16);
1.68 + case 6 : b += (uint32_t(k[5])<<8);
1.69 + case 5 : b += k[4];
1.70 + case 4 : a += (uint32_t(k[3])<<24);
1.71 + case 3 : a += (uint32_t(k[2])<<16);
1.72 + case 2 : a += (uint32_t(k[1])<<8);
1.73 + case 1 : a += k[0];
1.74 + /* case 0: nothing left to add */
1.75 + }
1.76 + hashmix(a, b, c);
1.77 +
1.78 + return c;
1.79 +}
1.80 +
1.81 +CacheHash::Hash16_t
1.82 +CacheHash::Hash16(const char *aData, uint32_t aSize, uint32_t aInitval)
1.83 +{
1.84 + Hash32_t hash = Hash(aData, aSize, aInitval);
1.85 + return (hash & 0xFFFF);
1.86 +}
1.87 +
1.88 +NS_IMPL_ISUPPORTS0(CacheHash)
1.89 +
1.90 +CacheHash::CacheHash(uint32_t aInitval)
1.91 + : mA(0x9e3779b9)
1.92 + , mB(0x9e3779b9)
1.93 + , mC(aInitval)
1.94 + , mPos(0)
1.95 + , mBuf(0)
1.96 + , mBufPos(0)
1.97 + , mLength(0)
1.98 + , mFinalized(false)
1.99 +{}
1.100 +
1.101 +void
1.102 +CacheHash::Feed(uint32_t aVal, uint8_t aLen)
1.103 +{
1.104 + switch (mPos) {
1.105 + case 0:
1.106 + mA += aVal;
1.107 + mPos ++;
1.108 + break;
1.109 +
1.110 + case 1:
1.111 + mB += aVal;
1.112 + mPos ++;
1.113 + break;
1.114 +
1.115 + case 2:
1.116 + mPos = 0;
1.117 + if (aLen == 4) {
1.118 + mC += aVal;
1.119 + hashmix(mA, mB, mC);
1.120 + }
1.121 + else {
1.122 + mC += aVal << 8;
1.123 + }
1.124 + }
1.125 +
1.126 + mLength += aLen;
1.127 +}
1.128 +
1.129 +void
1.130 +CacheHash::Update(const char *aData, uint32_t aLen)
1.131 +{
1.132 + const uint8_t *data = reinterpret_cast<const uint8_t*>(aData);
1.133 +
1.134 + MOZ_ASSERT(!mFinalized);
1.135 +
1.136 + if (mBufPos) {
1.137 + while (mBufPos != 4 && aLen) {
1.138 + mBuf += uint32_t(*data) << 8*mBufPos;
1.139 + data++;
1.140 + mBufPos++;
1.141 + aLen--;
1.142 + }
1.143 +
1.144 + if (mBufPos == 4) {
1.145 + mBufPos = 0;
1.146 + Feed(mBuf);
1.147 + mBuf = 0;
1.148 + }
1.149 + }
1.150 +
1.151 + if (!aLen)
1.152 + return;
1.153 +
1.154 + while (aLen >= 4) {
1.155 + Feed(data[0] + (uint32_t(data[1]) << 8) + (uint32_t(data[2]) << 16) +
1.156 + (uint32_t(data[3]) << 24));
1.157 + data += 4;
1.158 + aLen -= 4;
1.159 + }
1.160 +
1.161 + switch (aLen) {
1.162 + case 3: mBuf += data[2] << 16;
1.163 + case 2: mBuf += data[1] << 8;
1.164 + case 1: mBuf += data[0];
1.165 + }
1.166 +
1.167 + mBufPos = aLen;
1.168 +}
1.169 +
1.170 +CacheHash::Hash32_t
1.171 +CacheHash::GetHash()
1.172 +{
1.173 + if (!mFinalized)
1.174 + {
1.175 + if (mBufPos) {
1.176 + Feed(mBuf, mBufPos);
1.177 + }
1.178 + mC += mLength;
1.179 + hashmix(mA, mB, mC);
1.180 + mFinalized = true;
1.181 + }
1.182 +
1.183 + return mC;
1.184 +}
1.185 +
1.186 +CacheHash::Hash16_t
1.187 +CacheHash::GetHash16()
1.188 +{
1.189 + Hash32_t hash = GetHash();
1.190 + return (hash & 0xFFFF);
1.191 +}
1.192 +
1.193 +} // net
1.194 +} // mozilla
1.195 +
