mozilla/rust — pull request #8097 by DaGenix (2013-07-28 21:12:57+00:00)
Title: Sha2 cleanups & optimization and MD5 implementation

I reworked the Sha2 code to be more readable and faster. Part of that work entailed extracting out common code having to do with buffer handling into a new struct, FixedBuffer, in the new cryptoutil.rs file. I then built an MD5 implementation using that new common code.

The first couple 3 commits in this request just move stuff around in the sha2.rs file. None of the changes here should impact functionality, but hopefully make the code a bit cleaner and easier to work with.

In the 4th commit:
* I create the FixedBuffer struct. This struct contains the logic to gather up input bytes until a full block is available. Once that full block is available, its fed into a passed in closure, which in the case of a hash function is the compression function and the buffer is then marked as empty. The existing Digest implementations tend to do a lot processing a byte at a time and tend to do more copies than necessary - the FixedBuffer class tries to do just the minimum amount of copying possible. My hope is that this struct can be used by any future Digest implementation (at least those that are block based).
* I added in a few unsafe methods to optimize some common cases - writing an integer to a [u8] and reading in an array of integers from a [u8]. These methods verify their preconditions explicitly and will cause an assert! if they are used in a manner that would corrupt memory.
* I updated the Sha2 code to make use of all this new functionality. This resulted in a nice speedup in my benchmarks.
* I greatly reduced the size of the Sha2 objects - previously they contained their entire working buffer - 80 u64s for Sha512 and 64 u32s for Sha256, even though they are only needed for calculation by the compression function; with this change I allocate those larger buffers on the stack in the compression function.

In the 5th commit, I rewrite the compression functions used by Sha2. Not a major change - I inlined the message schedule calculation into the same loop as the rest of the compression function. This results in a nice speedup as I believe it lets LLVM optimize the method better.

The 6th commit just adds a few new functions to cryptoutil.rs to work with little-endian values

The 7th commit makes use of those new functions to implement MD5. This implementation unrolls the entire compression loop which mirrors implementations in other languages - Crypto++ and Bouncy Castle.

In the 8th commit, I update the Digest trait to use default methods and get rid of the the DigestUtil trait now that default methods seem to be working better.

Outside of the #tests, I also tested the Sha2 and MD5 implementations by generating a few thousand random inputs of up to 10MB in size, calculated the digests using these implementations and Java's implementations and compared them.

Performance Measurements:

Benchmarks:

Before making any updates, the Sha2 performance was:

test sha2::bench::sha256_10 ... bench: 104 ns/iter (+/- 3) = 96 MB/s
test sha2::bench::sha256_1k ... bench: 10476 ns/iter (+/- 918) = 97 MB/s
test sha2::bench::sha256_64k ... bench: 671398 ns/iter (+/- 9934) = 97 MB/s
test sha2::bench::sha512_10 ... bench: 86 ns/iter (+/- 6) = 116 MB/s
test sha2::bench::sha512_1k ... bench: 6114 ns/iter (+/- 50) = 167 MB/s
test sha2::bench::sha512_64k ... bench: 393582 ns/iter (+/- 22549) = 166 MB/s

After the changes in #4, the performance improved to:

test sha2::bench::sha256_10 ... bench: 101 ns/iter (+/- 7) = 99 MB/s
test sha2::bench::sha256_1k ... bench: 7736 ns/iter (+/- 177) = 132 MB/s
test sha2::bench::sha256_64k ... bench: 492327 ns/iter (+/- 12650) = 133 MB/s
test sha2::bench::sha512_10 ... bench: 72 ns/iter (+/- 2) = 138 MB/s
test sha2::bench::sha512_1k ... bench: 5004 ns/iter (+/- 935) = 204 MB/s
test sha2::bench::sha512_64k ... bench: 316444 ns/iter (+/- 8554) = 207 MB/s

After the changes in #5, the performance improved further to:

test sha2::bench::sha256_10 ... bench: 87 ns/iter (+/- 1) = 114 MB/s
test sha2::bench::sha256_1k ... bench: 6509 ns/iter (+/- 98) = 157 MB/s
test sha2::bench::sha256_64k ... bench: 414015 ns/iter (+/- 11395) = 158 MB/s
test sha2::bench::sha512_10 ... bench: 64 ns/iter (+/- 1) = 156 MB/s
test sha2::bench::sha512_1k ... bench: 4135 ns/iter (+/- 48) = 247 MB/s
test sha2::bench::sha512_64k ... bench: 262115 ns/iter (+/- 17540) = 250 MB/s

MD5 performance:

test md5::bench::md5_10 ... bench: 53 ns/iter (+/- 1) = 188 MB/s
test md5::bench::md5_1k ... bench: 2857 ns/iter (+/- 185) = 358 MB/s
test md5::bench::md5_64k ... bench: 181389 ns/iter (+/- 4870) = 361 MB/s

Cycle counts:

Sha512 performance on my machine is: 11.5 cycles / byte. Intel [1], has a Sha512 implementation that achieves 9.4 cycles / byte using the SSE instructions (the AVX implementation is slightly faster, but, only runs on Haswell processors, I think). Assuming that that is the best possible performance, there really isn't all that much more room for optimization without resorting to assembly. I'm not sure what optimized C implementations generally achieve.

Sha256 performance on my machine is: 17.6 cycles / byte. Intel [2] achieved roughly 13.8 cycles / byte in their singled threaded SSE implementation. Like Sha512, I think this puts the Sha256 implementation pretty close to the limit on how efficient it can be without resorting to assembly.

MD5 performance is: 7.6 cycles / byte. According to https://en.wikipedia.org/wiki/SHA-2, the best MD5 implementations are around 4.5 - 6 cycles / byte. So, at 7.6 cycles / byte, the implementation is in that neighborhood. Wikipedia doesn't mention exactly what those implementations are, but I suspect they are done hand optimized assembly.

[1] - http://www.intel.com/content/www/us/en/intelligent-systems/intel-technology/fast-sha512-implementations-ia-processors-paper.html

[2] - http://www.intel.com/content/www/us/en/intelligent-systems/intel-technology/sha-256-implementations-paper.html