Loading...
Searching...
No Matches
Hash.cpp
/*
* Copyright (C) 2010 Regents of the University of Michigan
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include "Hash.h"
#include <ctype.h>
// ********************************************************
//
// This code is based on the original by Robert Jenkins.
//
// http://burtleburtle.net/bob/hash/doobs.html
//
// ********************************************************
#define MIX_INTEGERS(a,b,c) \
{ \
a -= b; a -= c; a ^= (c>>13); \
b -= c; b -= a; b ^= (a<<8); \
c -= a; c -= b; c ^= (b>>13); \
a -= b; a -= c; a ^= (c>>12); \
b -= c; b -= a; b ^= (a<<16); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>3); \
b -= c; b -= a; b ^= (a<<10); \
c -= a; c -= b; c ^= (b>>15); \
}
#define ui (unsigned int)
unsigned int hash(const unsigned char * key, unsigned int length, unsigned int initval)
{
unsigned int a = 0x9e3779b9;
unsigned int b = 0x9e3779b9;
unsigned int c = initval;
unsigned int len = length;
/*---------------------------------------- handle most of the key */
while (len >= 12)
{
a += (key[0] +(ui(key[1])<<8) +(ui(key[2])<<16) +(ui(key[3])<<24));
b += (key[4] +(ui(key[5])<<8) +(ui(key[6])<<16) +(ui(key[7])<<24));
c += (key[8] +(ui(key[9])<<8) +(ui(key[10])<<16)+(ui(key[11])<<24));
MIX_INTEGERS(a,b,c);
key += 12;
len -= 12;
}
/*------------------------------------- handle the last 11 bytes */
c += length;
switch (len) /* all the case statements fall through */
{
case 11:
c+=(ui(key[10])<<24);
case 10:
c+=(ui(key[9])<<16);
case 9 :
c+=(ui(key[8])<<8);
/* the first byte of c is reserved for the length */
case 8 :
b+=(ui(key[7])<<24);
case 7 :
b+=(ui(key[6])<<16);
case 6 :
b+=(ui(key[5])<<8);
case 5 :
b+=key[4];
case 4 :
a+=(ui(key[3])<<24);
case 3 :
a+=(ui(key[2])<<16);
case 2 :
a+=(ui(key[1])<<8);
case 1 :
a+=key[0];
/* case 0: nothing left to add */
}
MIX_INTEGERS(a,b,c);
/*-------------------------------------------- report the result */
return c;
}
unsigned int hash_no_case(const unsigned char * key, unsigned int length, unsigned int initval)
{
unsigned int a = 0x9e3779b9;
unsigned int b = 0x9e3779b9;
unsigned int c = initval;
unsigned int len = length;
/*---------------------------------------- handle most of the key */
while (len >= 12)
{
a += (toupper(key[0]) +(ui(toupper(key[1]))<<8) +(ui(toupper(key[2]))<<16) +(ui(toupper(key[3]))<<24));
b += (toupper(key[4]) +(ui(toupper(key[5]))<<8) +(ui(toupper(key[6]))<<16) +(ui(toupper(key[7]))<<24));
c += (toupper(key[8]) +(ui(toupper(key[9]))<<8) +(ui(toupper(key[10]))<<16)+(ui(toupper(key[11]))<<24));
MIX_INTEGERS(a,b,c);
key += 12;
len -= 12;
}
/*------------------------------------- handle the last 11 bytes */
c += length;
switch (len) /* all the case statements fall through */
{
case 11:
c+=(ui(toupper(key[10]))<<24);
case 10:
c+=(ui(toupper(key[9]))<<16);
case 9 :
c+=(ui(toupper(key[8]))<<8);
/* the first byte of c is reserved for the length */
case 8 :
b+=(ui(toupper(key[7]))<<24);
case 7 :
b+=(ui(toupper(key[6]))<<16);
case 6 :
b+=(ui(toupper(key[5]))<<8);
case 5 :
b+=toupper(key[4]);
case 4 :
a+=(ui(toupper(key[3]))<<24);
case 3 :
a+=(ui(toupper(key[2]))<<16);
case 2 :
a+=(ui(toupper(key[1]))<<8);
case 1 :
a+=toupper(key[0]);
/* case 0: nothing left to add */
}
MIX_INTEGERS(a,b,c);
/*-------------------------------------------- report the result */
return c;
}