EngineYard Programming Contest July 2009
C
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.
.gitignore
README
eypc.c

README

ABOUT

`eypc` is a program to work on the EngineYard Programming Contest:
http://www.engineyard.com/blog/2009/programming-contest-win-iphone-3gs-2k-cloud-credit/

The main purpose of the program is find a hash that is as similar to the hash
of a predetermined string. Essentially this is random luck, but the more
strings you can run through the more 'lottery tickets' you get. This program
does a couple things to optimize performance.

1) The input keys are not copied around. They are all stored in a single
array, and an array of indexes iterate through them. (a)

2) Rather than doing multiple Updates to the SHA digest for keys that change
infrequently, a single update is performed only when necessary. (a)

3) A 'slug' is appended to the end of the 12 keys. An array of 'slugs' is
built in advance, and these strings are iterated over without reinitializing
the SHA1 structure.

(a) Optimizations 1 and 2 each doubled performance, but optimization 3 causes
the code for 1 and 2 to run so infrequently that their current contribution is 
minimal. For reference, running with 1 and 2 was about 30% slower than running
with 1, 2, and 3.

On a Pentium M 2.0ghz laptop this will work on just over 1 million hashs per
second.

Thank you to Chris Ruvolo for the code reviews, testing, and figuring out
why hamming_distance was all messed up.


BUILD

I have only built this on x86 machines, but it builds on OpenBSD, OS X, and
Linux.

gcc eypc.c -lssl -lcrypto -o eypc -O3 -funroll-loops -DPRODUCTION

Do this then do `time eypc` for benchmarking.

gcc eypc.c -lssl -lcrypto -o eypc -O3 -funroll-loops -DPRODUCTION -DTIMETEST