/*
   This was based on details from chapter 6 of the manuscript
   "Applied Cryptanalysis" by Mark Stamp and Richard M. Low,
   January 25, 2006.  Some functions here were refactored from
   http://www.ietf.org/rfc/rfc1321.txt.
   
   Tom Austin and Ying Zhang.
 */

#include <stdio.h>
#include <string.h>

//0 turns debug mode off, 1 turns it on, 2 turns on display of hex values as well.
#define DEBUG 0

//Initialization values.
#define IV_A 0x67452301
#define IV_B 0xefcdab89
#define IV_C 0x98badcfe
#define IV_D 0x10325476

//represents one quarter of a block
// (this is as big of an int as we can get).
typedef unsigned long int UINT4;

//method declarations needed.
static void Encode (unsigned char*, UINT4*, unsigned int);


//the value of the hash, in little-endian format.
typedef struct
{
  unsigned char digest[16];
} HASHVAL;

/* Utility to print the hash value */
static void printHashVal(HASHVAL* hv)
{
  int i=0;
  for (i=0; i<16; i++)
    printf ("%02x", hv->digest[i]);
  printf("\n");
}

/*
  Utility to compare two hash values.
  Returns -1 if they are equal, and the
  index of the differing byte otherwise
 */
static int compareHashVals(HASHVAL* hv1, HASHVAL* hv2)
{
  int i=0;
  for (i = 0; i < 16; i++)
    if (hv1->digest[i] != hv2->digest[i]) return i;
  else return -1;
}

/* Utility to print a little-endian byte array in hexadecimal. */
static void printHex(unsigned char val[], int length)
{
  unsigned int i;
  printf("\n\thex:");
  for (i = 0; i < length; i++)
    printf ("%02x", val[i]);
  printf("\n");  
}

/*
   Rotates bits n positions to the left.
   Assumes blocks are 32 bits.
 */
static int rotateBitsLeft(UINT4 x, int n)
{
  int shiftResult = x << n;
  int spillOver = x >> (32-n);
  return shiftResult | spillOver;
}

/* Basic MD5 functions */
int F(UINT4 a, UINT4 b, UINT4 c) { return (a & b) | (~a & c); }
int G(UINT4 a, UINT4 b, UINT4 c) { return (a & c) | (b & ~c); }
int H(UINT4 a, UINT4 b, UINT4 c) { return a ^ b ^ c; }
int I(UINT4 a, UINT4 b, UINT4 c) { return b ^ (a | ~c); }

/*
   Round 0 of the transformation
 */
static void round0(UINT4 *a, UINT4 *b, UINT4 *c, UINT4 *d, UINT4 x[16])
{
  int i, j;
  int k[]={ 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
            0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
            0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
            0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 };
  for (i=0; i<4; i++)
  {
    j = 4 * i;
    *a = *b + rotateBitsLeft((*a + F(*b,*c,*d) + x[j] + k[j]), 7);
    *d = *a + rotateBitsLeft((*d + F(*a,*b,*c) + x[j+1] + k[j+1]), 12);
    *c = *d + rotateBitsLeft((*c + F(*d,*a,*b) + x[j+2] + k[j+2]), 17);
    *b = *c + rotateBitsLeft((*b + F(*c,*d,*a) + x[j+3] + k[j+3]), 22);
  }
}

/*
   Round 1 of the transformation
 */
static void round1(UINT4 *a, UINT4 *b, UINT4 *c, UINT4 *d, UINT4 x[16])
{
  int i, j, xInd;
  int k[]={ 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
            0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
            0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
            0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a };
            
  //The block of x we need starts at one and increments
  // by 5 each step.
  xInd=1;
  for (i=0; i<4; i++)
  {
    j = 4 * i;
    *a = *b + rotateBitsLeft((*a + G(*b,*c,*d) + x[xInd] + k[j]), 5);
    xInd = (xInd + 5) % 16;
    *d = *a + rotateBitsLeft((*d + G(*a,*b,*c) + x[xInd] + k[j+1]), 9);
    xInd = (xInd + 5) % 16;
    *c = *d + rotateBitsLeft((*c + G(*d,*a,*b) + x[xInd] + k[j+2]), 14);
    xInd = (xInd + 5) % 16;
    *b = *c + rotateBitsLeft((*b + G(*c,*d,*a) + x[xInd] + k[j+3]), 20);
    xInd = (xInd + 5) % 16;
  }
}


/*
   Round 2 of the transformation
 */
static void round2(UINT4 *a, UINT4 *b, UINT4 *c, UINT4 *d, UINT4 x[16])
{
  int i, j, xInd;
  int k[]={ 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
            0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
            0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
            0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 };
  
  //The block of x we need starts at 5 and increments
  // by 3 each step.
  xInd=5;
  for (i=0; i<4; i++)
  {
    j = 4 * i;
    *a = *b + rotateBitsLeft((*a + H(*b,*c,*d) + x[xInd] + k[j]), 4);
    xInd = (xInd + 3) % 16;
    *d = *a + rotateBitsLeft((*d + H(*a,*b,*c) + x[xInd] + k[j+1]), 11);
    xInd = (xInd + 3) % 16;
    *c = *d + rotateBitsLeft((*c + H(*d,*a,*b) + x[xInd] + k[j+2]), 16);
    xInd = (xInd + 3) % 16;
    *b = *c + rotateBitsLeft((*b + H(*c,*d,*a) + x[xInd] + k[j+3]), 23);
    xInd = (xInd + 3) % 16;
  }
}

/*
   Round 3 of the transformation
 */
static void round3(UINT4 *a, UINT4 *b, UINT4 *c, UINT4 *d, UINT4 x[16])
{
  int i, j, xInd;
  int k[]={ 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
            0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
            0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
            0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 };

  //The block of x we need starts at 0 and increments
  // by 7 each step.
  xInd=0;
  for (i=0; i<4; i++)
  {
    j = 4 * i;
    *a = *b + rotateBitsLeft((*a + I(*b,*c,*d) + x[xInd] + k[j]), 6);
    xInd = (xInd + 7) % 16;
    *d = *a + rotateBitsLeft((*d + I(*a,*b,*c) + x[xInd] + k[j+1]), 10);
    xInd = (xInd + 7) % 16;
    *c = *d + rotateBitsLeft((*c + I(*d,*a,*b) + x[xInd] + k[j+2]), 15);
    xInd = (xInd + 7) % 16;
    *b = *c + rotateBitsLeft((*b + I(*c,*d,*a) + x[xInd] + k[j+3]), 21);
    xInd = (xInd + 7) % 16;
  }
}

/* Encodes input (UINT4) into output (unsigned char). Assumes len is
  a multiple of 4.  This converts the big-endian UINT4s to little-endian
  byte arrays.
  Note that this was taken mostly as-is from the reference implementation.
*/
static void Encode (unsigned char *output, UINT4 *input, unsigned int len)
{
  unsigned int i, j;

  for (i = 0, j = 0; j < len; i++, j += 4) {
    output[j] = (unsigned char)(input[i] & 0xff);
    output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
    output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
    output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
  }
}

/* Converts input (unsigned char) into output (UINT4).
   Assumes len is a multiple of 4.
   Note that  this was taken mostly as-is from the reference implementation.
 */
static void Decode (UINT4 *output, unsigned char *input, unsigned int len)
{
  unsigned int i, j;
  
  for (i = 0, j = 0; j < len; i++, j += 4)
    output[i] = ((UINT4)input[j])
              | (((UINT4)input[j+1]) << 8)
              | (((UINT4)input[j+2]) << 16)
              | (((UINT4)input[j+3]) << 24);
}

/*
   Runs the transformation on a single 512 bit block.
 */
static void transformBlock (UINT4 *aa, UINT4 *bb, UINT4 *cc, UINT4 *dd, unsigned char block[64])
{
  UINT4 a=*aa, b=*bb, c=*cc, d=*dd, x[16];
  
  if (DEBUG>1) printHex(block,64);
  
  Decode (x, block, 64);
  
  round0(&a, &b, &c, &d, x);
  if (DEBUG) printf("  r0: %x %x %x %x \n", a, b, c, d);
  round1(&a, &b, &c, &d, x);
  if (DEBUG) printf("  r1: %x %x %x %x \n", a, b, c, d);
  round2(&a, &b, &c, &d, x);
  if (DEBUG) printf("  r2: %x %x %x %x \n", a, b, c, d);
  round3(&a, &b, &c, &d, x);
  if (DEBUG) printf("  r3: %x %x %x %x \n", a, b, c, d);

  *aa += a;
  *bb += b;
  *cc += c;
  *dd += d;
}


/* copy input to block, adding in padding and length if needed. */
void copyInputToBlock(unsigned char block[64], char *input, int len, UINT4 bitCount[2])
{
  int i,j;
  unsigned char lengthBits[8];
  
  //Copy input to block
  for (i=0; i<len; i++)
  {
    block[i]=input[i];
  }
  
  //If this is a partial block, pad it out and add the length
  if (len<56)
  {
    //1st byte of padding is 0x80 (taken from reference implementation)
    block[len]=0x80;
    //rest of padding is zero
    for (i=len+1; i<56; i++)
    {
      block[i]=0;
    }
    
    //append bit length of message as 64-bit little-endian integer to message
    Encode (lengthBits, bitCount, 8);
    for (j=0; j<8; i++,j++)
    {
      block[i] = lengthBits[j];
    }
  }
  //if we are 56 bits or more, but not a full block, pad out, but the length
  // (along with more padding) will be on the next block.
  else if (len<64)
  {
    //1st byte of padding is 0x80 (taken from reference implementation)
    block[len]=0x80;
    //rest of padding is zero
    for (i=len+1; i<64; i++)
    {
      block[i]=0;
    }
  }
}

/* Used to pad out the last block and add the length, if
   the block only has padding plus the bit count.
 */
void padFinal(unsigned char block[64], UINT4 bitCount[2])
{
  int i,j;
  unsigned char lengthBits[8];
  
  //Continue padding
  for (i=0; i<56; i++)
  {
    block[i]=0;
  }
    
  //append bit length of message as 64-bit little-endian integer to message
  Encode (lengthBits, bitCount, 8);
  for (j=0; j<8; i++,j++)
  {
    block[i] = lengthBits[j];
  }
}

/*
   Update bitCount by specified number of bytes.
 */
void updateBitCount(UINT4 bitCount[2], int numBytesRead)
{
  bitCount[0] += numBytesRead << 3;
  //deal with rollover of size
  if (bitCount[0] < (numBytesRead << 3))
    bitCount[1]++;
}

/*
   Runs the transformation on the final block (or 2, if the padding and filesize spill over).
 */
void hashFinalBlock(UINT4 *a, UINT4 *b, UINT4 *c, UINT4 *d, UINT4 bitCount[2], char* input, int len)
{
  unsigned char block[64];
  
  updateBitCount(bitCount, len);
  
  //Read the last partial block with data
  copyInputToBlock(block, input, len, bitCount);
  transformBlock(a, b, c, d, block);
  
  //If the size of the input mod 512 is greater than or equal to 448
  // then the padding and the length spill over to a new block
  if (len >= 56)
  {
    padFinal(block, bitCount);
    transformBlock(a, b, c, d, block);
  }
}

/*
   Hashes a file and prints the result.
 */
void hashFile (char *filename)
{
  HASHVAL hv;
  
  FILE *file;
  int len;
  
  //Initial values
  UINT4 a = IV_A;
  UINT4 b = IV_B;
  UINT4 c = IV_C;
  UINT4 d = IV_D;
  
  UINT4 bitCount[] = { 0, 0 };
  
  unsigned char buffer[1024];
  unsigned char block[64];
  UINT4 state[4];
  
  if ((file = fopen (filename, "rb")) == NULL)
  {
    printf ("%s can't be opened\n", filename);
    return;
  }
  
  //Read all of the full blocks possible
  while ((len = fread (buffer, 1, 64, file)) >= 64)
  {
    updateBitCount(bitCount, len);
    copyInputToBlock(block, buffer, 64, bitCount);
    transformBlock(&a, &b, &c, &d, block);
  }
  
  hashFinalBlock(&a, &b, &c, &d, bitCount, buffer, len);
  
  // Store the hash value, reversing the order of bytes
  state[0]=a;
  state[1]=b;
  state[2]=c;
  state[3]=d;
  Encode (hv.digest, state, 16);
  
  printf("MD5(%s) = ", filename);
  printHashVal(&hv);
    
  fclose (file);
}

/*
   Hashes a string and prints out the result.
 */
void hashString (char* input)
{
  HASHVAL hv;
  int len = strlen(input);
  
  //tracks our position in the input
  int index = 0;
  
  //Initial values
  UINT4 a = IV_A;
  UINT4 b = IV_B;
  UINT4 c = IV_C;
  UINT4 d = IV_D;
  
  //store the filesize, which is used as part of the final block
  // to be hashed.
  UINT4 bitCount[] = { 0, 0 };
  
  unsigned char block[64];
  UINT4 state[4];

  //Read all of the full blocks possible
  while (len - index >= 64)
  {
    copyInputToBlock(block, &input[index], 64, bitCount);
    transformBlock(&a, &b, &c, &d, block);
    index += 64;
  }
  
  //Count the bytes that won't be counted in the final block.
  updateBitCount(bitCount, index);
  
  hashFinalBlock(&a, &b, &c, &d, bitCount, &input[index], len-index);
  
  // Store the hash value, reversing the order of bytes
  state[0]=a;
  state[1]=b;
  state[2]=c;
  state[3]=d;
  Encode (hv.digest, state, 16);
  
  printf("MD5(\"%s\") = ", input);
  printHashVal(&hv);
}


/*
   Hashes a string and prints out the result.
 */
void hashBytes (unsigned char* bytes, int len)
{
  HASHVAL hv;
  
  //tracks our position in the input
  int index = 0;
  
  //Initial values
  UINT4 a = IV_A;
  UINT4 b = IV_B;
  UINT4 c = IV_C;
  UINT4 d = IV_D;
  
  //store the filesize, which is used as part of the final block
  // to be hashed.
  UINT4 bitCount[] = { 0, 0 };
  
  unsigned char block[64];
  UINT4 state[4];

  //Read all of the full blocks possible
  while (len - index >= 64)
  {
    copyInputToBlock(block, &bytes[index], 64, bitCount);
    transformBlock(&a, &b, &c, &d, block);
    index += 64;
  }
  
  //Count the bytes that won't be counted in the final block.
  updateBitCount(bitCount, index);
  
  hashFinalBlock(&a, &b, &c, &d, bitCount, &bytes[index], len-index);
  
  // Store the hash value, reversing the order of bytes
  state[0]=a;
  state[1]=b;
  state[2]=c;
  state[3]=d;
  Encode (hv.digest, state, 16);
  
  int i=0;
  printf("MD5(bytes: ");
  for (i=0; i<len; i++) printf("0x%02x ", bytes[i]);
  printf(") = ");
  printHashVal(&hv);
}

/*
  Convert two charcters 0 thru 9, A thru F and a thru f to 
  a byte in hex (stored as an unsigned char).  This was
  modified from method in Prof. Stamp's TDES.c program.
 */
unsigned char atoh(char *x)
{
    int i;
    int len=2;
    unsigned char byte = 0;
    for(i = 0; i < len; ++i)
    {
        if((x[i] >= 48) && (x[i] <= 57))
        {
            byte |= ((int)x[i] - 48) << 4*(len - i - 1);
            continue;
        }
        if((x[i] >= 65) && (x[i] <= 70))
        {
            byte |= ((int)x[i] - 55) << 4*(len - i - 1);
            continue;
        }
        if((x[i] >= 97) && (x[i] <= 102))
        {
            byte |= ((int)x[i] - 87) << 4*(len - i - 1);
            continue;
        }
        fprintf(stderr, "\nError in atoh\n\n");   
    }
    
    return(byte);
}

/*
   Converts a string representation of a byte array into a byte
   array, and then hashes that with the hashBytes function.
   The string should just be a number in hexadecimal format.
 */
void hashByteString (char* byteStr)
{
  int len = strlen(byteStr)/2;
  unsigned char bytes[len];
  
  int i, j;
  for(i=0,j=0; i<len; i++)
  {
    j = i*2;
    bytes[i] = atoh(&byteStr[j]);
  }
  
  hashBytes(bytes, len);
}

/*
   Runs the following test cases:
   
   MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
   MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
   MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
   MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
   MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
   MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
      d174ab98d277d9f5a5611c2c9f419d9f
   MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789yz") =
      1fefa3ba7ab38cb0bc655598851791dd
   MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") =
      57edf4a22be3c955ac49da2e2107b67a
      
   Also, runs 2 colliding byte arrays.
*/
static void runTests ()
{ 
  printf ("MD5 test suite:\n");
  
  hashString("");
  hashString("a");
  hashString("abc");
  hashString("message digest");
  hashString("abcdefghijklmnopqrstuvwxyz");
  hashString("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
  hashString("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789yz");
  hashString("12345678901234567890123456789012345678901234567890123456789012345678901234567890");
  
  unsigned char bytes1 [] = { 0xd1, 0x31, 0xdd, 0x02, 0xc5, 0xe6, 0xee, 0xc4,
                              0x69, 0x3d, 0x9a, 0x06, 0x98, 0xaf, 0xf9, 0x5c,
                              0x2f, 0xca, 0xb5, 0x87, 0x12, 0x46, 0x7e, 0xab,
                              0x40, 0x04, 0x58, 0x3e, 0xb8, 0xfb, 0x7f, 0x89,
                              0x55, 0xad, 0x34, 0x06, 0x09, 0xf4, 0xb3, 0x02,
                              0x83, 0xe4, 0x88, 0x83, 0x25, 0x71, 0x41, 0x5a,
                              0x08, 0x51, 0x25, 0xe8, 0xf7, 0xcd, 0xc9, 0x9f,
                              0xd9, 0x1d, 0xbd, 0xf2, 0x80, 0x37, 0x3c, 0x5b,
                              0x96, 0x0b, 0x1d, 0xd1, 0xdc, 0x41, 0x7b, 0x9c,
                              0xe4, 0xd8, 0x97, 0xf4, 0x5a, 0x65, 0x55, 0xd5,
                              0x35, 0x73, 0x9a, 0xc7, 0xf0, 0xeb, 0xfd, 0x0c,
                              0x30, 0x29, 0xf1, 0x66, 0xd1, 0x09, 0xb1, 0x8f,
                              0x75, 0x27, 0x7f, 0x79, 0x30, 0xd5, 0x5c, 0xeb,
                              0x22, 0xe8, 0xad, 0xba, 0x79, 0xcc, 0x15, 0x5c,
                              0xed, 0x74, 0xcb, 0xdd, 0x5f, 0xc5, 0xd3, 0x6d,
                              0xb1, 0x9b, 0x0a, 0xd8, 0x35, 0xcc, 0xa7, 0xe3 };
  
  //Using /**/ to mark differing bytes                          
  unsigned char bytes2 [] = { 0xd1, 0x31, 0xdd, 0x02, 0xc5, 0xe6, 0xee, 0xc4,
                              0x69, 0x3d, 0x9a, 0x06, 0x98, 0xaf, 0xf9, 0x5c,
                              0x2f, 0xca, 0xb5, /**/0x07, 0x12, 0x46, 0x7e, 0xab,
                              0x40, 0x04, 0x58, 0x3e, 0xb8, 0xfb, 0x7f, 0x89,
                              0x55, 0xad, 0x34, 0x06, 0x09, 0xf4, 0xb3, 0x02,
                              0x83, 0xe4, 0x88, 0x83, 0x25, /**/0xf1, 0x41, 0x5a,
                              0x08, 0x51, 0x25, 0xe8, 0xf7, 0xcd, 0xc9, 0x9f,
                              0xd9, 0x1d, 0xbd, /**/0x72, 0x80, 0x37, 0x3c, 0x5b,
                              0x96, 0x0b, 0x1d, 0xd1, 0xdc, 0x41, 0x7b, 0x9c,
                              0xe4, 0xd8, 0x97, 0xf4, 0x5a, 0x65, 0x55, 0xd5,
                              0x35, 0x73, 0x9a, /**/0x47, 0xf0, 0xeb, 0xfd, 0x0c,
                              0x30, 0x29, 0xf1, 0x66, 0xd1, 0x09, 0xb1, 0x8f,
                              0x75, 0x27, 0x7f, 0x79, 0x30, 0xd5, 0x5c, 0xeb,
                              0x22, 0xe8, 0xad, 0xba, 0x79, /**/0x4c, 0x15, 0x5c,
                              0xed, 0x74, 0xcb, 0xdd, 0x5f, 0xc5, 0xd3, 0x6d,
                              0xb1, 0x9b, 0x0a, /**/0x58, 0x35, 0xcc, 0xa7, 0xe3 };
  
  printf("\n\n");
  hashBytes(bytes1, 128);
  hashBytes(bytes2, 128);
}

/*
   Main.  Run with no args to see usage message.
*/
int main (int argc, char *argv[])
{
  int i;

  if (argc == 3)
  {
      if (strcmp (argv[1], "-s") == 0)
        hashString (argv[2]);
      else if (strcmp (argv[1], "-f") == 0)
        hashFile (argv[2]);
      else if (strcmp (argv[1], "-b") == 0)
        hashByteString (argv[2]);
      else goto usage;
  }
  else if (argc == 2 && strcmp (argv[1], "-test") == 0)
    runTests();
  else
  {
usage:
    printf("Usage: '%s -s <string>', to hash a string.\n", argv[0]);
    printf("       '%s -b <byteString>', to hash a hexadecimal number.\n", argv[0]);
    printf("       '%s -f <file>', to hash a file.\n", argv[0]);
    printf("       '%s -test', to run tests.\n", argv[0]);
  }
  
  return (0);
}