// Emacs style mode select -*- C++ -*-
//-----------------------------------------------------------------------------
//
// Copyright(C) 2009 James Haley
//
// 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 2 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, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
//--------------------------------------------------------------------------
//
// DESCRIPTION:
//
// Hash routines for data integrity and cryptographic purposes.
//
//-----------------------------------------------------------------------------
#include "z_zone.h"
#include "m_hash.h"
//
// Shared Macros
//
#define leftrotate(w, b) (((w) << (b)) | ((w) >> (32 - (b))))
//=============================================================================
//
// CRC32 - For IEEE Types
//
#define CRC32_IEEE_POLY 0xEDB88320
static uint32_t crc32_table[256];
//
// M_CRC32BuildTable
//
// Builds the polynomial table for CRC32.
//
static void M_CRC32BuildTable(void)
{
uint32_t i, j;
for(i = 0; i < 256; ++i)
{
uint32_t val = i;
for(j = 0; j < 8; ++j)
{
if(val & 1)
val = (val >> 1) ^ CRC32_IEEE_POLY;
else
val >>= 1;
}
crc32_table[i] = val;
}
}
//
// M_CRC32Initialize
//
// Builds the table if it hasn't been built yet. Doesn't do anything
// else, since CRC32 starting value has already been set properly by
// the main hash init routine.
//
static void M_CRC32Initialize(hashdata_t *hash)
{
static boolean tablebuilt = false;
// build the CRC32 table if it hasn't been built yet
if(!tablebuilt)
{
M_CRC32BuildTable();
tablebuilt = true;
}
// zero is the appropriate starting value for CRC32, so we need do nothing
// special here
}
//
// M_CRC32HashData
//
// Calculates a running CRC32 for the provided block of data.
//
static void M_CRC32HashData(hashdata_t *hash, uint8_t *data, uint32_t len)
{
uint32_t crc = hash->digest[0];
crc ^= 0xFFFFFFFF;
while(len)
{
uint8_t idx = (uint8_t)(((int)crc ^ *data++) & 0xff);
crc = crc32_table[idx] ^ (crc >> 8);
--len;
}
hash->digest[0] = crc ^ 0xFFFFFFFF;
}
static void M_CRC32WrapUp(hashdata_t *hash)
{
// Nothing required.
}
//=============================================================================
//
// Adler-32 - For Mark Adler
//
#define MOD_ADLER 65521
//
// M_Adler32Initialize
//
// Sets the digest to the starting value of 1.
//
static void M_Adler32Initialize(hashdata_t *hash)
{
hash->digest[0] = 1;
}
//
// M_Adler32HashData
//
// Calculates a running Adler32 checksum for the provided block of data.
//
static void M_Adler32HashData(hashdata_t *hash, uint8_t *data, uint32_t len)
{
uint32_t a, b, idx;
a = hash->digest[0] & 0xFFFF;
b = (hash->digest[0] >> 16) & 0xFFFF;
for(idx = 0; idx < len; ++idx)
{
a = (a + data[idx]) % MOD_ADLER;
b = (b + a) % MOD_ADLER;
}
hash->digest[0] = (b << 16) | a;
}
static void M_Adler32WrapUp(hashdata_t *data)
{
// Nothing required.
}
//=============================================================================
//
// MD5 - For Korean hax0rz ^________^ kekeke
//
// md5_r specifies per-round shift amounts
static int md5_r[64] =
{
7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
};
// md5_k specifies standard constants (precomputed)
static uint32_t md5_k[64] =
{
0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a,
0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x2441453,
0xd8a1e681, 0xe7d3fbc8, 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9,
0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92,
0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
};
//
// M_MD5ProcessBlock
//
// Called when the MD5 hash has accumulated 512 bits of input.
// This is the main block "cipher" algorithm.
//
static void M_MD5ProcessBlock(hashdata_t *hash)
{
int i;
uint32_t temp;
uint32_t work[16]; // 16-word workspace
uint32_t a, b, c, d; // current hash for chunk
uint32_t f, g;
uint8_t *message = hash->message;
// Step 1: turn the 64 bytes into 16 dwords
for(i = 0; i < 16; ++i)
{
work[i] = ((uint32_t)message[i * 4 ]);
work[i] |= ((uint32_t)message[i * 4 + 1]) << 8;
work[i] |= ((uint32_t)message[i * 4 + 2]) << 16;
work[i] |= ((uint32_t)message[i * 4 + 3]) << 24;
}
// hash for this chunk starts out as current message hash
a = hash->digest[0];
b = hash->digest[1];
c = hash->digest[2];
d = hash->digest[3];
// Step 2: compute hash
for(i = 0; i < 16; ++i)
{
f = (b & c) | (~b & d);
g = i;
temp = d;
d = c;
c = b;
b = b + leftrotate((a + f + md5_k[i] + work[g]), md5_r[i]);
a = temp;
}
for(; i < 32; ++i)
{
f = (d & b) | (~d & c);
g = (5 * i + 1) % 16;
temp = d;
d = c;
c = b;
b = b + leftrotate((a + f + md5_k[i] + work[g]), md5_r[i]);
a = temp;
}
for(; i < 48; ++i)
{
f = b ^ c ^ d;
g = (3 * i + 5) % 16;
temp = d;
d = c;
c = b;
b = b + leftrotate((a + f + md5_k[i] + work[g]), md5_r[i]);
a = temp;
}
for(; i < 64; ++i)
{
f = c ^ (b | ~d);
g = (7 * i) % 16;
temp = d;
d = c;
c = b;
b = b + leftrotate((a + f + md5_k[i] + work[g]), md5_r[i]);
a = temp;
}
// Step 4: add chunk hash to message hash
hash->digest[0] += a;
hash->digest[1] += b;
hash->digest[2] += c;
hash->digest[3] += d;
// current buffered block has been digested, so clear the index
hash->messageidx = 0;
}
//
// M_MD5Initialize
//
// Gets an MD5 hash operation ready to run
//
static void M_MD5Initialize(hashdata_t *hash)
{
// initialize the digest with the standard initialization vector
hash->digest[0] = 0x67452301;
hash->digest[1] = 0xEFCDAB89;
hash->digest[2] = 0x98BADCFE;
hash->digest[3] = 0x10325476;
}
//
// M_MD5HashData
//
// Given data, this function will buffer it in the md5hash object until
// 512 bits of input have been accumulated, and then it will compute the
// hash for that block. If data is > 512 bits, it will be processed 512
// bits at a time. Call this routine until your input is exhausted.
//
static void M_MD5HashData(hashdata_t *hash, uint8_t *data, uint32_t len)
{
if(!len || hash->gonebad)
return;
while(len--)
{
hash->message[hash->messageidx++] = *data;
// added 8 bits
hash->messagelen += 8;
// If messagelen wraps to 0, the message is too long.
// This implementation supports a maximum message length of 512 MB.
if(!hash->messagelen)
{
hash->gonebad = true;
break;
}
// when 512 bits of message is accumulated, process it
if(hash->messageidx == 64)
M_MD5ProcessBlock(hash);
++data;
}
}
//
// M_MD5WrapUp
//
// Finishes up the MD5 hash algorithm by padding the message as needed and
// completing the hash computation on any data left in the message buffer.
//
static void M_MD5WrapUp(hashdata_t *hash)
{
// The message must be padded out to an even multiple of 512 bits, and the
// padding must include an initial "1" bit followed by zeroes, and then
// wrapped up with 8 bytes representing the length of the message. However,
// this implementation uses a 32-bit length, so the first 4 bytes of the
// message length are also always zero.
// This means we need at least 9 bytes available in the buffer. If there
// are not 9 bytes available, we need to pad out the current block and then
// continue padding into a new block.
if(hash->messageidx > 64 - 9)
{
// begin the padding in the current block; add a 1 bit at the start...
hash->message[hash->messageidx++] = 0x80;
// ... and fill the rest with 0
while(hash->messageidx < 64)
hash->message[hash->messageidx++] = 0;
// we filled the current block, so process it
M_MD5ProcessBlock(hash);
// finish padding in the new block with zeroes
while(hash->messageidx <= 64 - 5)
hash->message[hash->messageidx++] = 0;
}
else
{
// we have enough room in the current block; add a 1 bit at the start...
hash->message[hash->messageidx++] = 0x80;
// .. and fill the rest with 0, up to the space needed for the msg length
while(hash->messageidx <= 64 - 5)
hash->message[hash->messageidx++] = 0;
}
// fill the remainder of the final block with the encoded length
hash->message[60] = (uint8_t)((hash->messagelen ) & 0xFF);
hash->message[61] = (uint8_t)((hash->messagelen >> 8) & 0xFF);
hash->message[62] = (uint8_t)((hash->messagelen >> 16) & 0xFF);
hash->message[63] = (uint8_t)((hash->messagelen >> 24) & 0xFF);
// process the final padded block.
M_MD5ProcessBlock(hash);
}
//=============================================================================
//
// SHA-1 - For Men in Black
//
//
// M_SHA1ProcessBlock
//
// Called when the SHA1 hash has accumulated 512 bits of input.
// This is the main block "cipher" algorithm.
//
static void M_SHA1ProcessBlock(hashdata_t *hash)
{
int i;
uint32_t temp;
uint32_t work[80]; // 80-word extension workspace
uint32_t a, b, c, d, e; // current hash for chunk
uint32_t f;
uint8_t *message = hash->message;
// Step 1: turn the 64 bytes into 16 dwords
for(i = 0; i < 16; ++i)
{
work[i] = ((uint32_t)message[i * 4 ]) << 24;
work[i] |= ((uint32_t)message[i * 4 + 1]) << 16;
work[i] |= ((uint32_t)message[i * 4 + 2]) << 8;
work[i] |= ((uint32_t)message[i * 4 + 3]);
}
// Step 2: extend the message with XOR shuffling
for(; i < 80; ++i)
{
temp = work[i - 3] ^ work[i - 8] ^ work[i - 14] ^ work[i - 16];
work[i] = leftrotate(temp, 1);
}
// hash for this chunk starts out as current message hash
a = hash->digest[0];
b = hash->digest[1];
c = hash->digest[2];
d = hash->digest[3];
e = hash->digest[4];
// Step 3: compute hash
for(i = 0; i < 20; ++i)
{
f = (b & c) | (~b & d);
temp = leftrotate(a, 5) + f + e + 0x5A827999 + work[i];
e = d;
d = c;
c = leftrotate(b, 30);
b = a;
a = temp;
}
for(; i < 40; ++i)
{
f = b ^ c ^ d;
temp = leftrotate(a, 5) + f + e + 0x6ED9EBA1 + work[i];
e = d;
d = c;
c = leftrotate(b, 30);
b = a;
a = temp;
}
for(; i < 60; ++i)
{
f = (b & c) | (b & d) | (c & d);
temp = leftrotate(a, 5) + f + e + 0x8F1BBCDC + work[i];
e = d;
d = c;
c = leftrotate(b, 30);
b = a;
a = temp;
}
for(; i < 80; ++i)
{
f = b ^ c ^ d;
temp = leftrotate(a, 5) + f + e + 0xCA62C1D6 + work[i];
e = d;
d = c;
c = leftrotate(b, 30);
b = a;
a = temp;
}
// Step 4: add chunk hash to message hash
hash->digest[0] += a;
hash->digest[1] += b;
hash->digest[2] += c;
hash->digest[3] += d;
hash->digest[4] += e;
// current buffered block has been digested, so clear the index
hash->messageidx = 0;
}
//
// M_SHA1Initialize
//
// Gets a SHA1 hash operation ready to run
//
static void M_SHA1Initialize(hashdata_t *hash)
{
// initialize the digest with the standard initialization vector
hash->digest[0] = 0x67452301;
hash->digest[1] = 0xEFCDAB89;
hash->digest[2] = 0x98BADCFE;
hash->digest[3] = 0x10325476;
hash->digest[4] = 0xC3D2E1F0;
}
//
// M_SHA1HashData
//
// Given data, this function will buffer it in the sha1hash object until
// 512 bits of input have been accumulated, and then it will compute the
// hash for that block. If data is > 512 bits, it will be processed 512
// bits at a time. Call this routine until your input is exhausted.
//
static void M_SHA1HashData(hashdata_t *hash, uint8_t *data, uint32_t len)
{
if(!len || hash->gonebad)
return;
while(len--)
{
hash->message[hash->messageidx++] = *data;
// added 8 bits
hash->messagelen += 8;
// If messagelen wraps to 0, the message is too long.
// This implementation supports a maximum message length of 512 MB.
if(!hash->messagelen)
{
hash->gonebad = true;
break;
}
// when 512 bits of message is accumulated, process it
if(hash->messageidx == 64)
M_SHA1ProcessBlock(hash);
++data;
}
}
//
// M_SHA1WrapUp
//
// Finishes up the SHA-1 hash algorithm by padding the message as needed and
// completing the hash computation on any data left in the message buffer.
//
static void M_SHA1WrapUp(hashdata_t *hash)
{
// The message must be padded out to an even multiple of 512 bits, and the
// padding must include an initial "1" bit followed by zeroes, and then
// wrapped up with 8 bytes representing the length of the message. However,
// this implementation uses a 32-bit length, so the first 4 bytes of the
// message length are also always zero.
// This means we need at least 9 bytes available in the buffer. If there
// are not 9 bytes available, we need to pad out the current block and then
// continue padding into a new block.
if(hash->messageidx > 64 - 9)
{
// begin the padding in the current block; add a 1 bit at the start...
hash->message[hash->messageidx++] = 0x80;
// ... and fill the rest with 0
while(hash->messageidx < 64)
hash->message[hash->messageidx++] = 0;
// we filled the current block, so process it
M_SHA1ProcessBlock(hash);
// finish padding in the new block with zeroes
while(hash->messageidx <= 64 - 5)
hash->message[hash->messageidx++] = 0;
}
else
{
// we have enough room in the current block; add a 1 bit at the start...
hash->message[hash->messageidx++] = 0x80;
// .. and fill the rest with 0, up to the space needed for the msg length
while(hash->messageidx <= 64 - 5)
hash->message[hash->messageidx++] = 0;
}
// fill the remainder of the final block with the encoded length
hash->message[60] = (uint8_t)((hash->messagelen >> 24) & 0xFF);
hash->message[61] = (uint8_t)((hash->messagelen >> 16) & 0xFF);
hash->message[62] = (uint8_t)((hash->messagelen >> 8) & 0xFF);
hash->message[63] = (uint8_t)((hash->messagelen ) & 0xFF);
// process the final padded block.
M_SHA1ProcessBlock(hash);
}
//=============================================================================
//
// Generic Hashing Interface
//
typedef struct hashalgorithm_s
{
void (*Initialize)(hashdata_t *);
void (*HashData)(hashdata_t *, uint8_t *, uint32_t);
void (*WrapUp)(hashdata_t *);
int numdigest;
} hashalgorithm_t;
// Algorithms - They're Grrrreat!
static hashalgorithm_t HashAlgorithms[HASH_NUMTYPES] =
{
{ M_CRC32Initialize, M_CRC32HashData, M_CRC32WrapUp, 1 }, // CRC32
{ M_Adler32Initialize, M_Adler32HashData, M_Adler32WrapUp, 1 }, // Adler-32
{ M_MD5Initialize, M_MD5HashData, M_MD5WrapUp, 4 }, // MD5
{ M_SHA1Initialize, M_SHA1HashData, M_SHA1WrapUp, 5 }, // SHA-1
};
//
// M_HashInitialize
//
// Call this to start up the hash algorithm of your choice, indicated via
// the "type" parameter.
//
void M_HashInitialize(hashdata_t *hash, hashtype_e type)
{
memset(hash, 0, sizeof(hashdata_t));
hash->type = type;
HashAlgorithms[type].Initialize(hash);
}
//
// M_HashData
//
// Call this to add the provided data to the calculation of the message
// digest. You can call this with all your data in one chunk, or call it
// repeatedly until data provided in smaller chunks is exhausted.
//
void M_HashData(hashdata_t *hash, uint8_t *data, uint32_t size)
{
HashAlgorithms[hash->type].HashData(hash, data, size);
}
//
// M_HashWrapUp
//
// Call this to end your digest calculation. Some algorithms don't
// actually require you to call this: namely, CRC32 and Adler-32.
//
void M_HashWrapUp(hashdata_t *hash)
{
HashAlgorithms[hash->type].WrapUp(data);
}
//
// M_HashCompare
//
// This routine will compare two digests. The algorithms must be the same
// or the comparison will evaluate as false.
//
boolean M_HashCompare(hashdata_t *h1, hashdata_t *h2)
{
boolean ret = false;
if(h1->type == h2->type)
{
int i, nummatch = 0;
for(i = 0; i < HashAlgorithms[h1->type].numdigest; ++i)
if(h1->digest[i] == h2->digest[i])
++nummatch;
if(nummatch == i)
ret = true;
}
return ret;
}
//=============================================================================
//
// String Digest Conversion Routines
//
// We do not resort to libc functions for the conversions to or from string,
// as printf-style functions are slow, and other string<->number conversion
// functions are often wrong when it comes to dealing with such problems as
// leading zeroes or signed-vs-unsigned issues.
//
#define HexCharToNum(c) \
(uint32_t)(((c) >= '0' && (c) <= '9') ? (c) - '0' : \
((c) >= 'a' && (c) <= 'f') ? ((c) - 'a') + 10 : \
((c) >= 'A' && (c) <= 'F') ? ((c) - 'A') + 10 : 0)
//
// M_HashStrToDigest
//
// This routine will convert a given hex string into a hash digest, regardless
// of the algorithm by which it was created.
//
void M_HashStrToDigest(hashdata_t *hash, const char *str)
{
int digestidx = 0;
int digestshift = 28;
memset(hash->digest, 0, NUMDIGEST * sizeof(*(hash->digest)));
while(*str)
{
if(digestidx >= NUMDIGEST)
return;
hash->digest[digestidx] |= (HexCharToNum(*str) << digestshift);
digestshift -= 4;
if(digestshift < 0) // step to next digest
{
++digestidx;
digestshift = 28;
}
++str;
}
}
//
// M_HashDigestToStr
//
// This routine will allocate and return a string holding the message digest
// from the hashdata object.
//
char *M_HashDigestToStr(hashdata_t *hash)
{
char *buffer, *c;
size_t size = 0;
int numdigest;
int i;
numdigest = HashAlgorithms[hash->type].numdigest;
size = (8 * numdigest + 1) * sizeof(char);
c = buffer = calloc(1, size);
for(i = 0; i < numdigest; ++i)
{
int shift;
for(shift = 28; shift >= 0; shift -= 4)
*c++ = "0123456789abcdef"[(hash->digest[i] >> shift) & 0x0F];
}
return buffer;
}
// EOF