Rust solution to the fall 2014 University of Mississippi ACM hashing competition

acmhash.rs

// Michael Macias <[email protected]>
// created 2014-10-02, updated 2014-10-13
// rust 0.12.0
// MIT license (http://opensource.org/licenses/MIT)
//
// acmhash.rs is a Rust solution to the fall 2014 University of Mississippi
// ACM hashing competition (http://micha.elwillia.ms/). The goal is to find
// an input so that the SHA-256 cryptographic hash function produces a digest
// with the most leading zeros. For example, the word "mismatchment" has 4
// leading zeros.
//
//     $ echo -n "mismatchment" | shasum -a 256
//     0000bb6ede9f29a01d35e15320229aa0fbd73cf8eb8bc0aac80d6a97fba63fee  -
//
// This solution is multithreaded. Each independent worker is seeded with a
// random alphanumeric string, which is "incremented" every step
// (see `#test_next_word`). If a digest has more leading zeros than previously
// known, it is printed to the screen and automatically submitted to the
// competition server. Don't forget to to change `API_KEY`, else you'll be
// hashing for me!
//
// Usage
//
//     $ rustc --opt-level 3 acmhash.rs
//     $ ./acmhash
//
// Tests and Benchmarks
//
//     $ rustc --opt-level 3 --test acmhash.rs
//     $ ./acmhash
//     $ ./acmhash --bench

extern crate rustc;

// Rust's SHA-256 implementation is intended for internal use only by the
// compiler itself, but we're going to use it anyway!
use rustc::util::sha2::{Sha256, Digest};
use std::io::{IoResult, TcpStream};
use std::rand::{task_rng, Rng};
use std::os;

static VERSION: &'static str = "0.4.4";

static HOSTNAME: &'static str = "micha.elwillia.ms";
static PORT: u16 = 80;
static API_KEY: &'static str = "0b6de5206fab768ea3e5788bef473928";

static MIN_MAX_ZEROS: uint = 4;
static DATA_LENGTH: uint = 16;

fn count_leading_zeros(digest: &[u8]) -> uint {
    let mut count = 0u;

    for &b in digest.iter() {
        // Note that a right shift is unnecessary here. The least significant
        // nibble will already be zeroed by the mask.
        if b & 0xf0 > 0u8 { break; }
        count += 1;
        if b & 0x0f > 0u8 { break; }
        count += 1;
    }

    count
}

// Though we could save a couple of comparisons by cycling through printable
// ASCII characters (' ' through '~'), we only use an alphanumeric subset to
// prevent having to URL encode the data for submission.
fn next_char(c: char) -> char {
    match c {
        '9' => 'a', // carry
        'Z' => '0',
        'z' => 'A',
        _ => ((c as u8) + 1) as char
    }
}

// Unsafe code, oh no! `String#as_mut_vec()` cannot guarantee modifications
// to the byte array will result in a valid UTF-8 string. Given that we
// only cycle through alphanumeric characters (see `#next_char`), we should
// be okay.
fn next_word(word: &mut String) {
    unsafe {
        let bytes = word.as_mut_vec();

        for b in bytes.iter_mut().rev() {
            let c = next_char(*b as char);
            *b = c as u8;
            if c != 'a' { break; }
        }
    }
}

// Instead of using `Digest#result_str` to get the digest as a hexadecimal
// string, we save from having to do that encoding by using the raw digest.
fn sha256(input: &str, output: &mut [u8]) {
    let mut sha = Sha256::new();
    sha.input_str(input);
    sha.result(output);
}

// Rust doesn't include an HTTP library in std. We could try shelling out to
// cURL (see `io::process::Command`), binding to libcurl, or including an
// external library, but to make things simple, we use a raw TCP socket to send
// an HTTP header instead.
fn submit(attempt: &String) -> IoResult<()> {
    let request = format!(
        "POST /attempt?attempt={}&key={} HTTP/1.0\r\n\
        Accept: */*\r\n\
        Connection: close\r\n\
        Content-Length: 0\r\n\
        Host: {}\r\n\
        User-Agent: acmhash/{}\r\n\
        \r\n",
        attempt, API_KEY, HOSTNAME, VERSION);

    let mut stream = try!(TcpStream::connect(HOSTNAME, PORT));
    try!(stream.write(request.as_bytes()));

    // No need to explicitly close the socket because of Rust's ownership
    // system, woohoo!
    //
    // See http://blog.skylight.io/rust-means-never-having-to-close-a-socket/

    Ok(())
}

fn worker() {
    let mut max_zeros = MIN_MAX_ZEROS;

    // `data` and `digest` are mutable buffers to prevent having to allocate
    // new objects every iteration.
    let mut data: String = task_rng().gen_ascii_chars().take(DATA_LENGTH).collect();
    let mut digest = [0u8, ..32];

    loop {
        sha256(data.as_slice(), digest);
        let zeros = count_leading_zeros(digest);

        if zeros > max_zeros {
            println!("{} => {}", data, zeros);

            max_zeros = zeros;

            match submit(&data) {
                Ok(_) => { /* noop */ },
                Err(e) => println!("error: {}", e)
            }
        }

        next_word(&mut data);
    }
}

fn main() {
    let n_workers = os::num_cpus();

    for _ in range(0u, n_workers) {
        spawn(worker);
    }
}

#[cfg(test)]
mod tests {
    extern crate test;

    use super::{count_leading_zeros, next_word, sha256};
    use self::test::Bencher;

    #[test]
    fn test_count_leading_zeros() {
        let bytes = [0x00, 0x00, 0x0f, 0xf0];
        let count = count_leading_zeros(bytes);
        assert!(count == 5);
    }

    #[test]
    fn test_next_word() {
        let examples = ["bar", "xyz", "XYZ", "999"];
        let expected = ["bas", "xyA", "XY0", "aaa"];

        for (i, example) in examples.iter().enumerate() {
            let mut s = example.to_string();
            next_word(&mut s);
            assert!(s.as_slice() == expected[i]);
        }
    }

    #[test]
    fn test_sha256() {
        let input = "The quick brown fox jumps over the lazy dog.";

        let mut actual = [0u8, ..32];
        sha256(input, actual);

        let expected = [0xef, 0x53, 0x7f, 0x25, 0xc8, 0x95, 0xbf, 0xa7,
                        0x82, 0x52, 0x65, 0x29, 0xa9, 0xb6, 0x3d, 0x97,
                        0xaa, 0x63, 0x15, 0x64, 0xd5, 0xd7, 0x89, 0xc2,
                        0xb7, 0x65, 0x44, 0x8c, 0x86, 0x35, 0xfb, 0x6c];

        assert!(actual == expected);
    }

    #[bench]
    fn bench_worker(b: &mut Bencher) {
        let mut max_zeros = 0;
        let mut data = "B5yFZOben5YwPU0N".to_string();
        let mut digest = [0u8, ..32];

        b.iter(|| {
            sha256(data.as_slice(), digest);
            let zeros = count_leading_zeros(digest);
            if zeros > max_zeros { max_zeros = zeros; }
            next_word(&mut data);
        });
    }
}