#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
#define F(x,y,z) (((x) & (y)) | ((~(x)) & (z)))
#define G(x,y,z) (((x) & (z)) | ((y) & (~(z))))
#define H(x,y,z) ((x) ^ (y) ^ (z))
#define I(x,y,z) ((y) ^ ((x) | (~(z))))
#define md5_s1_0 7
#define md5_s1_1 12
#define md5_s1_2 17
#define md5_s1_3 22
#define md5_s2_0 5
#define md5_s2_1 9
#define md5_s2_2 14
#define md5_s2_3 20
#define md5_s3_0 4
#define md5_s3_1 11
#define md5_s3_2 16
#define md5_s3_3 23
#define md5_s4_0 6
#define md5_s4_1 10
#define md5_s4_2 15
#define md5_s4_3 21

int __attribute__((__always_inline__)) md5_hash(unsigned char *message, unsigned int mlength, unsigned char input[16]);
int inline __fastcall do_next_sequence(char *sequence, int charset_length, int length);

int main(int argc, char *argv[])
{
    int x, len, t, nlen;
    clock_t start,end;
    float dif;
    int loops = 0;
    unsigned char *sequence;
    unsigned char *message;
    char charset[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', \
                        'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',\
                         'w', 'x', 'y', 'z'};  // lower_alpha

    unsigned char digest[16];
	unsigned char raw_inhash[16];
	
	if( argc < 3 )
        return 1;
    
    len = atoi( argv[2] );
    if((len%64) == 0) { 
        nlen = len + 64; 
    }else{ 
        nlen = len + (64 - (len%64)); 
    } 
    uint8_t paddedMessage[nlen+1];
    sequence = (char *)malloc( len );
    message = (char *)malloc( len );
    memset(sequence, 0, len);
    
    for(t = 0; t < 16; t++)
    {
        sscanf(&argv[1][t*2], "%2x", (raw_inhash + t));
    }
    
    memset(&paddedMessage[len], 0, nlen-len); 
    paddedMessage[len] = 0x80; 
    ((uint32_t*)&paddedMessage[nlen - 8])[0] = len * 8; 
    ((uint32_t*)&paddedMessage[nlen - 8])[1] = 0; 
    
    start = clock();
    while( do_next_sequence(sequence, sizeof(charset), len) )
    {
        for(x = len - 1; x >= 0; x--)
        {
             message[x] = charset[(unsigned char)sequence[x]];
        }
        message[len] = 0;
        
        loops++;
        memcpy(paddedMessage, message, len);
        if( md5_hash( paddedMessage, nlen, raw_inhash ) )
        {
            end = clock();
            dif = (end - start);
            dif /= CLOCKS_PER_SEC;
            printf("Collision Found!: %s is : %s\n  Cracking took: %.2lfs\n  Average h/s: %.2f h/s\n", argv[1], message, dif, (loops / dif));
            system("pause");
            return 0;
        }
    }
    puts("No collision Found\n");
    system("pause");
    return 1;
}

int inline __fastcall do_next_sequence(char *sequence, int charset_length, int length)
{
   int x;
   for(x = 0; sequence[x] == (charset_length-1); ++x)
   {
      if(x == (length-1))
      {
         return 0;
      }
      sequence[x] = 0;
   }
   ++sequence[x];
   return 1;
}

int __attribute__((__always_inline__)) md5_hash(unsigned char *message, unsigned int mlength, unsigned char input[16])
{
    uint32_t AA, BB, CC, DD;
    uint32_t *X; 
    uint32_t A, B, C, D; 
    uint32_t i;

    AA = 0x67452301;
    BB = 0xefcdab89;
    CC = 0x98badcfe;
    DD = 0x10325476;

    for(i = 0; i < (mlength / 64); ++i) 
    { 
        A = AA; 
        B = BB; 
        C = CC; 
        D = DD; 

        X = (uint32_t *)&message[i * 64];

        /// round one (unrolled) 
        A = B + ROTATE_LEFT((A + F(B, C, D) + X[ 0] + 0xd76aa478),  7); 
        D = A + ROTATE_LEFT((D + F(A, B, C) + X[ 1] + 0xe8c7b756), 12); 
        C = D + ROTATE_LEFT((C + F(D, A, B) + X[ 2] + 0x242070db), 17); 
        B = C + ROTATE_LEFT((B + F(C, D, A) + X[ 3] + 0xc1bdceee), 22); 
        A = B + ROTATE_LEFT((A + F(B, C, D) + X[ 4] + 0xf57c0faf),  7); 
        D = A + ROTATE_LEFT((D + F(A, B, C) + X[ 5] + 0x4787c62a), 12); 
        C = D + ROTATE_LEFT((C + F(D, A, B) + X[ 6] + 0xa8304613), 17); 
        B = C + ROTATE_LEFT((B + F(C, D, A) + X[ 7] + 0xfd469501), 22); 
        A = B + ROTATE_LEFT((A + F(B, C, D) + X[ 8] + 0x698098d8),  7); 
        D = A + ROTATE_LEFT((D + F(A, B, C) + X[ 9] + 0x8b44f7af), 12); 
        C = D + ROTATE_LEFT((C + F(D, A, B) + X[10] + 0xffff5bb1), 17); 
        B = C + ROTATE_LEFT((B + F(C, D, A) + X[11] + 0x895cd7be), 22); 
        A = B + ROTATE_LEFT((A + F(B, C, D) + X[12] + 0x6b901122),  7); 
        D = A + ROTATE_LEFT((D + F(A, B, C) + X[13] + 0xfd987193), 12); 
        C = D + ROTATE_LEFT((C + F(D, A, B) + X[14] + 0xa679438e), 17); 
        B = C + ROTATE_LEFT((B + F(C, D, A) + X[15] + 0x49b40821), 22); 
        /// round two (unrolled) 
        A = B + ROTATE_LEFT((A + G(B, C, D) + X[ 1] + 0xf61e2562),  5); 
        D = A + ROTATE_LEFT((D + G(A, B, C) + X[ 6] + 0xc040b340),  9); 
        C = D + ROTATE_LEFT((C + G(D, A, B) + X[11] + 0x265e5a51), 14); 
        B = C + ROTATE_LEFT((B + G(C, D, A) + X[ 0] + 0xe9b6c7aa), 20); 
        A = B + ROTATE_LEFT((A + G(B, C, D) + X[ 5] + 0xd62f105d),  5); 
        D = A + ROTATE_LEFT((D + G(A, B, C) + X[10] + 0x02441453),  9); 
        C = D + ROTATE_LEFT((C + G(D, A, B) + X[15] + 0xd8a1e681), 14); 
        B = C + ROTATE_LEFT((B + G(C, D, A) + X[ 4] + 0xe7d3fbc8), 20); 
        A = B + ROTATE_LEFT((A + G(B, C, D) + X[ 9] + 0x21e1cde6),  5); 
        D = A + ROTATE_LEFT((D + G(A, B, C) + X[14] + 0xc33707d6),  9); 
        C = D + ROTATE_LEFT((C + G(D, A, B) + X[ 3] + 0xf4d50d87), 14); 
        B = C + ROTATE_LEFT((B + G(C, D, A) + X[ 8] + 0x455a14ed), 20); 
        A = B + ROTATE_LEFT((A + G(B, C, D) + X[13] + 0xa9e3e905),  5); 
        D = A + ROTATE_LEFT((D + G(A, B, C) + X[ 2] + 0xfcefa3f8),  9); 
        C = D + ROTATE_LEFT((C + G(D, A, B) + X[ 7] + 0x676f02d9), 14); 
        B = C + ROTATE_LEFT((B + G(C, D, A) + X[12] + 0x8d2a4c8a), 20); 
        /// round three (unrolled) 
        A = B + ROTATE_LEFT((A + H(B, C, D) + X[ 5] + 0xfffa3942),  4); 
        D = A + ROTATE_LEFT((D + H(A, B, C) + X[ 8] + 0x8771f681), 11); 
        C = D + ROTATE_LEFT((C + H(D, A, B) + X[11] + 0x6d9d6122), 16); 
        B = C + ROTATE_LEFT((B + H(C, D, A) + X[14] + 0xfde5380c), 23); 
        A = B + ROTATE_LEFT((A + H(B, C, D) + X[ 1] + 0xa4beea44),  4); 
        D = A + ROTATE_LEFT((D + H(A, B, C) + X[ 4] + 0x4bdecfa9), 11); 
        C = D + ROTATE_LEFT((C + H(D, A, B) + X[ 7] + 0xf6bb4b60), 16); 
        B = C + ROTATE_LEFT((B + H(C, D, A) + X[10] + 0xbebfbc70), 23); 
        A = B + ROTATE_LEFT((A + H(B, C, D) + X[13] + 0x289b7ec6),  4); 
        D = A + ROTATE_LEFT((D + H(A, B, C) + X[ 0] + 0xeaa127fa), 11); 
        C = D + ROTATE_LEFT((C + H(D, A, B) + X[ 3] + 0xd4ef3085), 16); 
        B = C + ROTATE_LEFT((B + H(C, D, A) + X[ 6] + 0x04881d05), 23); 
        A = B + ROTATE_LEFT((A + H(B, C, D) + X[ 9] + 0xd9d4d039),  4); 
        D = A + ROTATE_LEFT((D + H(A, B, C) + X[12] + 0xe6db99e5), 11); 
        C = D + ROTATE_LEFT((C + H(D, A, B) + X[15] + 0x1fa27cf8), 16); 
        B = C + ROTATE_LEFT((B + H(C, D, A) + X[ 2] + 0xc4ac5665), 23); 
        /// round four (unrolled) 
        A = B + ROTATE_LEFT((A + I(B, C, D) + X[ 0] + 0xf4292244),  6); 
        D = A + ROTATE_LEFT((D + I(A, B, C) + X[ 7] + 0x432aff97), 10); 
        C = D + ROTATE_LEFT((C + I(D, A, B) + X[14] + 0xab9423a7), 15); 
        B = C + ROTATE_LEFT((B + I(C, D, A) + X[ 5] + 0xfc93a039), 21); 
        A = B + ROTATE_LEFT((A + I(B, C, D) + X[12] + 0x655b59c3),  6); 
        D = A + ROTATE_LEFT((D + I(A, B, C) + X[ 3] + 0x8f0ccc92), 10); 
        C = D + ROTATE_LEFT((C + I(D, A, B) + X[10] + 0xffeff47d), 15); 
        B = C + ROTATE_LEFT((B + I(C, D, A) + X[ 1] + 0x85845dd1), 21); 
        A = B + ROTATE_LEFT((A + I(B, C, D) + X[ 8] + 0x6fa87e4f),  6); 
        D = A + ROTATE_LEFT((D + I(A, B, C) + X[15] + 0xfe2ce6e0), 10); 
        C = D + ROTATE_LEFT((C + I(D, A, B) + X[ 6] + 0xa3014314), 15); 
        B = C + ROTATE_LEFT((B + I(C, D, A) + X[13] + 0x4e0811a1), 21); 
        A = B + ROTATE_LEFT((A + I(B, C, D) + X[ 4] + 0xf7537e82),  6); 
        D = A + ROTATE_LEFT((D + I(A, B, C) + X[11] + 0xbd3af235), 10); 
        C = D + ROTATE_LEFT((C + I(D, A, B) + X[ 2] + 0x2ad7d2bb), 15); 
        B = C + ROTATE_LEFT((B + I(C, D, A) + X[ 9] + 0xeb86d391), 21); 

        AA += A; 
        BB += B; 
        CC += C; 
        DD += D; 
    }

   if((*(unsigned long *)(input) == (AA)) &&
   (*(unsigned long *)(input+4) == (BB)) &&
   (*(unsigned long *)(input+8) == (CC)) &&
   (*(unsigned long *)(input+12) == (DD)))
       return 1;
   return 0;
}