// 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