#include #include #include #include #include #include "tsc.c" #include "md5.c" #define MD5_DIGEST_LENGTH 16 #define USE_ROUGH //#define TESTING //#define SINGLERUN //#define PEDANTIC #ifndef BENCH_VAL #define BENCH_VAL 8000000 #endif /* With MSF 11, we may miss 10's, but we don't have the false positives. * But we only get ~1110K/s instead of the ~1115K/s we get with MSF 8. Whahuh? */ #define MSF 8 #if BYTE_ORDER == LITTLE_ENDIAN #define BE_BYTE_INDEX(i) (i^3) #define LE_BYTE_INDEX(i) (i) #elif BYTE_ORDER == BIG_ENDIAN #define BE_BYTE_INDEX(i) (i) #define LE_BYTE_INDEX(i) (i^3) #else #error Unknown endianness #endif unsigned char tbl[512]; md5_state_t global_md5; #if 0 __inline__ void MD5(unsigned char *input, unsigned int input_len, unsigned char *out) { md5_init(&global_md5); md5_append(&global_md5, (const md5_byte_t *)input, input_len); md5_finish(&global_md5, out); } #endif void raw_MD5_64(unsigned char* input, unsigned char* digest) { /* initialize what we need in the md5_state_t */ global_md5.abcd[0] = 0x67452301; global_md5.abcd[1] = 0xefcdab89; global_md5.abcd[2] = 0x98badcfe; global_md5.abcd[3] = 0x10325476; /* process the fixed-sized input, pre-padded with the length */ md5_process(&global_md5, input); /* and finally store the digest * TODO: convert straight to hex? */ unsigned int i; for (i = 0; i < 16; ++i) { memcpy(digest, tbl + ((unsigned char*)(global_md5.abcd))[LE_BYTE_INDEX(i)] * 2, 2); digest += 2; } } #ifndef TIGER #include "srandomdev.c" #endif #include "lcs.c" #include "lcs_sse.c" /* timing functions */ struct timeval stopwatch_start; struct timeval stopwatch_stop; void start_stopwatch() { gettimeofday(&stopwatch_start, NULL); } unsigned long stop_stopwatch() { int seconds, usecs; gettimeofday(&stopwatch_stop, NULL); seconds = stopwatch_stop.tv_sec - stopwatch_start.tv_sec; usecs = stopwatch_stop.tv_usec - stopwatch_start.tv_usec; if (usecs < 0) { seconds -= 1; usecs += 1000000; } return seconds * 1000000 + usecs; } const char *hexchar = "0123456789abcdef"; unsigned char desttohex[64]; unsigned char test_input[] = { // 0x00, 0x04, 0x89, 0x4e, 0xf8, 0x11, 0x06, 0xbf, 0x87, 0xe3, 0x35, 0x6f, 0x68, 0xa5, 0xfa, 0xb3, // 0xcf, 0xa2, 0x0e, 0x2a, 0xda, 0xfc, 0x8e, 0x06, 0x66, 0x7b, 0x99, 0xa4, 0x06, 0x21, 0x95, 0x63, /* Eli's standard */ 0x22, 0x2b, 0x5b, 0x3c, 0xf7, 0xb9, 0xc2, 0x65, 0xc0, 0x4d, 0xab, 0x6d, 0xc6, 0xb9, 0x56, 0xeb, // 0xc4, 0x48, 0x13, 0xf8, 0x8e, 0xff, 0xd3, 0x03, 0x4f, 0x22, 0x0b, 0xe7, 0xe5, 0xe3, 0x35, 0xa0, /* One that fails with FALSE NEGATIVE2 when using non-byteswapped sse lcs */ /* 0xee, 0xf5, 0x67, 0x7f, 0x61, 0x88, 0xcb, 0xea, 0x8f, 0x21, 0x13, 0x85, 0x1f, 0xac, 0x4d, 0xab */ }; unsigned char input_raw[MD5_DIGEST_LENGTH]; unsigned char input_hex[64] __attribute__((aligned(64))); /* Writes hexadecimal form of argument to desttohex, no terminating null * character. */ void tohex(unsigned char *md5val) { unsigned char *c = desttohex; unsigned int i; for(i=0; i> 4]; *ct++ = hexchar[(x & 0xf)]; } desttohex[32] = '\0'; for (x=0; x<64; x++) { input_hex[x] = '\0'; } input_hex[32] = 0x80; // start of md5 pad input_hex[57] = 0x01; // hardcoded length of 256 bits int n; unsigned int i = 0; unsigned int matches_found = 0; unsigned int possible_matches = 0; printf("%p %p %p\n", desttohex, input_hex, tbl); /* Generate a random start point */ #ifdef TESTING memcpy(input_raw, test_input, MD5_DIGEST_LENGTH); #else srandomdev(); for(i=0; i<16; i++) { input_raw[i] = random() & 0xff; } i = 0; #endif tohex(input_raw); memcpy((char *)input_hex, (char *)desttohex, 32); printf("Starting at "); print_input_hex(); printf("\n"); fflush(stdout); #ifdef TIMINGS unsigned long long t0, t1; #endif /* Loop */ start_stopwatch(); while (1) { #ifdef TIMINGS t0 = rdtsc(); #endif raw_MD5_64(input_hex, desttohex); #ifdef TIMINGS t1 = rdtsc(); if (i % 1000000 == 0) printf("md5=%llu\n", (t1-t0-63)); #endif #ifdef USE_PRE_LCS int pre_n = lcs_upper_bound((uint32_t*)input_raw, (uint32_t*)global_md5.abcd); if (pre_n >= MSF) { #endif #ifdef USE_ROUGH #ifdef TIMINGS t0 = rdtsc(); #endif #ifdef USE_LCS4 n = lcs_32_rough(input_hex, desttohex); #else n = lcs_32_rough((uint32_t*)input_raw, (uint32_t*)global_md5.abcd); #endif #ifdef TIMINGS t1 = rdtsc(); if (i % 1000000 == 0) printf("rough=%llu\n", (t1-t0-63)); #endif /* Based on testing, the 'rough' match may undercount by up to 6 * characters (for an int32-based implementation). It now returns * 1/4th the length of the match it found, so it will return >0 if * there is a match of 7 or greater, and sometimes return >0 if there * is a match of 4 or greater. */ if (n > 0) { possible_matches++; #ifdef TIMINGS t0 = rdtsc(); #endif n = lcs_uchar_32_32(input_hex, desttohex); /* get the exact number */ #ifdef TIMINGS t1 = rdtsc(); #endif if (n >= MSF) { #ifndef SINGLERUN #ifdef TIMINGS printf("full=%llu\n", (t1-t0-63)); #endif print_input_hex(); printf(" %s %d\n", desttohex, n); fflush(stdout); #endif matches_found++; #ifdef PEDANTIC } else { n = lcs_uchar_32_32(input_hex, desttohex); if(n >= MSF) { print_input_hex(); printf(" %d FALSE NEGATIVE1\n", n); } #endif } #ifdef PEDANTIC } else { n = lcs_uchar_32_32(input_hex, desttohex); if(n >= MSF) { printf("%s %d FALSE NEGATIVE2\n", input_hex, n); } #endif } #else n = lcs_32(input_hex, desttohex); if (n >= MSF) { print_input_hex(); printf(" %s %d\n", desttohex, n); fflush(stdout); } #endif #ifdef USE_PRE_LCS } #endif /* keep us updated on speed */ i++; if (i == BENCH_VAL) { unsigned long elapsed = stop_stopwatch(); printf("Benchmark: %dK/s (found %d matches and %d false matches in %d processed)\n", (int) ((float)BENCH_VAL * 1000 / elapsed), matches_found, possible_matches - matches_found, i); #ifdef SINGLERUN printf("%d processed in %ld us\n", BENCH_VAL, elapsed); #endif fflush(stdout); /* don't include the time it takes us to print out the benchmark */ start_stopwatch(); i = 0; matches_found = 0; possible_matches = 0; #ifdef SINGLERUN return 0; #endif } inc_input(); } return 0; }