Beefy Boxes and Bandwidth Generously Provided by pair Networks DiBona
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re^2: The golf course looks great, my swing feels good, I like my chances (Part III)

by eyepopslikeamosquito (Canon)
on May 06, 2009 at 21:49 UTC ( #762408=note: print w/ replies, xml ) Need Help??


in reply to Re: The golf course looks great, my swing feels good, I like my chances (Part III)
in thread The golf course looks great, my swing feels good, I like my chances (Part III)

Glad you enjoyed it! I found the whole thing surreal/hilarious while it was running, especially when I thought about how I'd go if this game had a one week time limit like the good ol' traditional Perl golf games.

It didn't run continuously for six months though. The search program could be run in pieces, as indicated by the C source code below, and running four copies of it simultaneously on a quad core machine helped (as I said, the required search is fundamentally highly parallelizable). Note that this C code handles the md5("M".magic-string) case. Small changes allow it to also be used for the md5(magic-string."M") case. Any suggestions for performance improvements to this C code are very welcome.

Oh, and after running this searcher and saving its stdout, I ran another small PHP program to confirm C/PHP md5 compatibility and to search for possible hits by applying the mod operator.

/* findmin6k.c For asm version (copy m5_win32.obj from openssl crypto/md5/asm direc +tory) and build with: cl /W3 /O2 findmin6k.c m5_win32.obj (windows) gcc -Wall -O3 -o findmin6k findmin6k.c mx86-elf.o (32-bit Linux +) gcc -Wall -O3 -o findmin6k findmin6k.c md5-x86_64.o (64-bit Linux +) Will likely need a C version to work with NVIDIA graphics card CUDA. For a pure C version, just write a C version of md5_block_asm_data_o +rder() and link with that. For example: cl /W3 /O2 findmin6k.c m5_ssl_le.c cl /W3 /O2 findmin6k.c m5_nsa_le.c For now, assume 32-bit int and little endian (_le). Example run on Unix: nohup nice ./findmin6k 65 66 48 160 >6k-65-1.tmp 2>err1.tmp & nohup nice ./findmin6k 65 66 160 256 >6k-65-2.tmp 2>err2.tmp & */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> static void test_endian() { int i; char sStrTmp[64]; int iIntSize = (int)sizeof(int); int iLongSize = (int)sizeof(long); union { unsigned long l; char c[sizeof(long)]; } u; printf("sizeof(int)=%d\nsizeof(long)=%d\nsizeof(size_t)=%d\n", iIntSize, iLongSize, (int)sizeof(size_t)); if (iLongSize > 4) { u.l = (0x08070605L << 32) | 0x04030201L; } else { u.l = 0x04030201L; } memset(sStrTmp, 0, sizeof(sStrTmp)); for (i = 0; i < iLongSize; ++i) { sprintf(sStrTmp+i, "%c", u.c[i]+'0'); } printf("byteorder=%s (1234=little-endian, 4321=big-endian)\n", sStr +Tmp); } /* Uncomment next line to use openssl asm version of md5_block_asm_dat +a_order() */ #define MY_ASM 1 #define MD5_LONG unsigned int typedef struct MD5state_st { MD5_LONG A,B,C,D; } MD5_CTX; #ifdef __cplusplus extern "C" { #endif #ifdef MY_ASM void md5_block_asm_data_order(MD5_CTX*, const void*, size_t); #else void md5_block_asm_data_order(MD5_CTX*, const void*); #endif #ifdef __cplusplus } #endif /* -------------------------------------------------------------- */ #define HI_SENTINEL 1000000000 static int my_md5(const unsigned char* inbuf) { int outi = 0; int nib; MD5_CTX mdContext; #ifdef MY_ASM mdContext.A = 0x67452301; mdContext.B = 0xefcdab89; mdContext.C = 0x98badcfe; mdContext.D = 0x10325476; md5_block_asm_data_order(&mdContext, inbuf, 1); #else md5_block_asm_data_order(&mdContext, inbuf); #endif /* 1st byte */ nib = (unsigned char)((mdContext.A >> 4) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)(mdContext.A & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 2nd byte */ nib = (unsigned char)((mdContext.A >> 12) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.A >> 8) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 3rd byte */ nib = (unsigned char)((mdContext.A >> 20) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.A >> 16) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 4th byte */ nib = (unsigned char)((mdContext.A >> 28) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.A >> 24) & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; /* 5th byte */ nib = (unsigned char)((mdContext.B >> 4) & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; nib = (unsigned char)(mdContext.B & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; /* 6th byte */ nib = (unsigned char)((mdContext.B >> 12) & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.B >> 8) & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; /* 7th byte */ nib = (unsigned char)((mdContext.B >> 20) & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.B >> 16) & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; /* 8th byte */ nib = (unsigned char)((mdContext.B >> 28) & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.B >> 24) & 0xF); if (nib > 9) return outi; if (outi > 9999999) return HI_SENTINEL; outi = outi * 10 + nib; #if 0 /* XXX: very unlikely to matter (only diabolicals like 0000000000000 +00999a) */ /* 9th byte */ nib = (unsigned char)((mdContext.C >> 4) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)(mdContext.C & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 10th byte */ nib = (unsigned char)((mdContext.C >> 12) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.C >> 8) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 11th byte */ nib = (unsigned char)((mdContext.C >> 20) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.C >> 16) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 12th byte */ nib = (unsigned char)((mdContext.C >> 28) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.C >> 24) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 13th byte */ nib = (unsigned char)((mdContext.D >> 4) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)(mdContext.D & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 14th byte */ nib = (unsigned char)((mdContext.D >> 12) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.D >> 8) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 15th byte */ nib = (unsigned char)((mdContext.D >> 20) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.D >> 16) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; /* 16th byte */ nib = (unsigned char)((mdContext.D >> 28) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; nib = (unsigned char)((mdContext.D >> 24) & 0xF); if (nib > 9) return outi; outi = outi * 10 + nib; #endif return outi; } #define M_TARG 999 #define D_TARG 499 #define C_TARG 99 #define L_TARG 49 #define X_TARG 9 #define V_TARG 4 #define I_TARG 0 #define SEARCH_WIDTH 6 #define H_LEN (SEARCH_WIDTH+1) #define MD5_CBLOCK 64 static void do_one(int start_val, int end_val, int start_val_2, int en +d_val_2) { unsigned char m_buf[MD5_CBLOCK]; unsigned char d_buf[MD5_CBLOCK]; unsigned char c_buf[MD5_CBLOCK]; unsigned char l_buf[MD5_CBLOCK]; unsigned char x_buf[MD5_CBLOCK]; unsigned char v_buf[MD5_CBLOCK]; unsigned char i_buf[MD5_CBLOCK]; unsigned char n_buf[MD5_CBLOCK]; int nmiss = 0; int nsent = 0; int q1 = 0; int q2 = 0; int q3 = 0; int q4 = 0; int q5 = 0; int q6 = 0; int m_char = 'M'; int d_char = 'D'; int c_char = 'C'; int l_char = 'L'; int x_char = 'X'; int v_char = 'V'; int i_char = 'I'; int n_char = 10; int m5 = 0; int d5 = 0; int c5 = 0; int l5 = 0; int x5 = 0; int v5 = 0; int i5 = 0; int n5 = 0; time_t tstart = time(NULL); clock_t cstart = clock(); time_t tend; clock_t cend; memset(m_buf, 0, MD5_CBLOCK); memset(d_buf, 0, MD5_CBLOCK); memset(c_buf, 0, MD5_CBLOCK); memset(l_buf, 0, MD5_CBLOCK); memset(x_buf, 0, MD5_CBLOCK); memset(v_buf, 0, MD5_CBLOCK); memset(i_buf, 0, MD5_CBLOCK); memset(n_buf, 0, MD5_CBLOCK); m_buf[H_LEN] = 0x80; d_buf[H_LEN] = 0x80; c_buf[H_LEN] = 0x80; l_buf[H_LEN] = 0x80; x_buf[H_LEN] = 0x80; v_buf[H_LEN] = 0x80; i_buf[H_LEN] = 0x80; n_buf[H_LEN] = 0x80; m_buf[MD5_CBLOCK-8] = H_LEN * 8; d_buf[MD5_CBLOCK-8] = H_LEN * 8; c_buf[MD5_CBLOCK-8] = H_LEN * 8; l_buf[MD5_CBLOCK-8] = H_LEN * 8; x_buf[MD5_CBLOCK-8] = H_LEN * 8; v_buf[MD5_CBLOCK-8] = H_LEN * 8; i_buf[MD5_CBLOCK-8] = H_LEN * 8; n_buf[MD5_CBLOCK-8] = H_LEN * 8; m_buf[0] = m_char; d_buf[0] = d_char; c_buf[0] = c_char; l_buf[0] = l_char; x_buf[0] = x_char; v_buf[0] = v_char; i_buf[0] = i_char; n_buf[0] = n_char; for (q1 = start_val; q1 < end_val; ++q1) { if (q1==91 || q1==92 || q1==93 || q1==94 || q1==96 || q1==123 || q1==124 || q1==125 || q1==126) continue; m_buf[1] = q1; d_buf[1] = q1; c_buf[1] = q1; l_buf[1] = q1; x_buf[1] = q1; v_buf[1] = q1; i_buf[1] = q1; n_buf[1] = q1; for (q2 = start_val_2; q2 < end_val_2; ++q2) { if (q2==91 || q2==92 || q2==93 || q2==94 || q2==96 || q2==123 || q2==124 || q2==125 || q2==126 || q2==58 || q2==59 || q2==60 || q2==61 || q2==62 || q2==63 + || q2==64) continue; m_buf[2] = q2; d_buf[2] = q2; c_buf[2] = q2; l_buf[2] = q2; x_buf[2] = q2; v_buf[2] = q2; i_buf[2] = q2; n_buf[2] = q2; fprintf(stderr, "%d %d\n", q1, q2); for (q3 = 48; q3 < 256; ++q3) { if (q3==91 || q3==92 || q3==93 || q3==94 || q3==96 || q3==123 || q3==124 || q3==125 || q3==126 || q3==58 || q3==59 || q3==60 || q3==61 || q3==62 || q3== +63 || q3==64) continue; m_buf[3] = q3; d_buf[3] = q3; c_buf[3] = q3; l_buf[3] = q3; x_buf[3] = q3; v_buf[3] = q3; i_buf[3] = q3; n_buf[3] = q3; for (q4 = 48; q4 < 256; ++q4) { if (q4==91 || q4==92 || q4==93 || q4==94 || q4==96 || q4==123 || q4==124 || q4==125 || q4==126 || q4==58 || q4==59 || q4==60 || q4==61 || q4==62 || q4 +==63 || q4==64) continue; m_buf[4] = q4; d_buf[4] = q4; c_buf[4] = q4; l_buf[4] = q4; x_buf[4] = q4; v_buf[4] = q4; i_buf[4] = q4; n_buf[4] = q4; for (q5 = 48; q5 < 256; ++q5) { if (q5==91 || q5==92 || q5==93 || q5==94 || q5==96 || q5==123 || q5==124 || q5==125 || q5==126 || q5==58 || q5==59 || q5==60 || q5==61 || q5==62 || +q5==63 || q5==64) continue; m_buf[5] = q5; d_buf[5] = q5; c_buf[5] = q5; l_buf[5] = q5; x_buf[5] = q5; v_buf[5] = q5; i_buf[5] = q5; n_buf[5] = q5; for (q6 = 48; q6 < 256; ++q6) { if (q6==91 || q6==92 || q6==93 || q6==94 || q6==96 || q6==123 || q6==124 || q6==125 || q6==126 || q6==58 || q6==59 || q6==60 || q6==61 || q6==62 | +| q6==63 || q6==64) continue; m_buf[6] = q6; d_buf[6] = q6; c_buf[6] = q6; l_buf[6] = q6; x_buf[6] = q6; v_buf[6] = q6; i_buf[6] = q6; n_buf[6] = q6; nmiss = 0; m5 = my_md5(m_buf); if (m5 == 0) continue; if (m5 != M_TARG) { if (m5 <= M_TARG+M_TARG) continue; ++nmiss; } d5 = my_md5(d_buf); if (d5 == 0) continue; if (d5 != D_TARG) { if (d5 <= M_TARG+D_TARG) continue; ++nmiss; } c5 = my_md5(c_buf); if (c5 == 0) continue; if (c5 != C_TARG) { if (c5 <= M_TARG+C_TARG) continue; ++nmiss; } if (nmiss > 2) continue; l5 = my_md5(l_buf); if (l5 == 0) continue; if (l5 != L_TARG) { if (l5 <= M_TARG+L_TARG) continue; ++nmiss; } if (nmiss > 2) continue; x5 = my_md5(x_buf); if (x5 != X_TARG) { if (x5 <= M_TARG+X_TARG) continue; ++nmiss; } if (nmiss > 2) continue; v5 = my_md5(v_buf); if (v5 != V_TARG) { if (v5 <= M_TARG+V_TARG) continue; ++nmiss; } if (nmiss > 2) continue; i5 = my_md5(i_buf); if (i5 != I_TARG) { if (i5 <= M_TARG+I_TARG) continue; ++nmiss; } if (nmiss > 2) continue; n5 = my_md5(n_buf); nsent = 0; if (m5 == HI_SENTINEL) { m5 += 1000; ++nsent; } if (d5 == HI_SENTINEL) { d5 += 500; ++nsent; } if (c5 == HI_SENTINEL) { c5 += 100; ++nsent; } if (l5 == HI_SENTINEL) { l5 += 50; ++nsent; } if (x5 == HI_SENTINEL) { x5 += 10; ++nsent; } if (v5 == HI_SENTINEL) { v5 += 5; ++nsent; } if (i5 == HI_SENTINEL) { i5 += 1; ++nsent; } if (n5 == HI_SENTINEL) { ++nsent; } printf("N %d nsent=%d: %d %d %d %d %d %d: %d %d %d %d %d + %d %d %d\n", nmiss, nsent, q1, q2, q3, q4, q5, q6, m5, d5, c5, l5, +x5, v5, i5, n5); fflush(stdout); if (m5==d5 || m5==c5 || m5==l5 || m5==x5 || m5==v5 || m5 +==i5) continue; if (d5==c5 || d5==l5 || d5==x5 || d5==v5 || d5==i5) cont +inue; if (c5==l5 || c5==x5 || c5==v5 || c5==i5) continue; if (l5==x5 || l5==v5 || l5==i5) continue; if (x5==v5 || x5==i5) continue; if (v5==i5) continue; printf("N %d: %d %d %d %d %d %d; %d %d %d %d %d %d %d %d +\n", nmiss, q1, q2, q3, q4, q5, q6, m5, d5, c5, l5, x5, v5, + i5, n5); fflush(stdout); } } } } } } tend = time(NULL); cend = clock(); printf("(wall clock time:%ld secs, cpu time:%.2f units)\n", (long) (difftime(tend, tstart)+0.5), (double) (cend-cstart) / (double)CLOCKS_PER_SEC); } int main(int argc, char* argv[]) { int start_val = 65; int end_val = 256; int start_val_2 = 48; int end_val_2 = 256; if (argc > 2) { start_val = atoi(argv[1]); end_val = atoi(argv[2]); if (argc == 5) { start_val_2 = atoi(argv[3]); end_val_2 = atoi(argv[4]); } } printf("start: %d %d, %d %d\n", start_val, end_val, start_val_2, end +_val_2); test_endian(); fflush(stdout); do_one(start_val, end_val, start_val_2, end_val_2); return 0; }


Comment on Re^2: The golf course looks great, my swing feels good, I like my chances (Part III)
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://762408]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2014-04-21 05:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (491 votes), past polls