Recently I looked for a Common Lisp implementation of the Secure Hash Algorithm - 1 and this is the only one I could find. It's from ironclad.
I remember reading in one of Douglas Hofstadter's wonderful Metamagical Themas that "Lisp is crisp." My initial impression is that this fragment of Lisp could be crisper. This could be be because I'm a newcomer to Lisp. Actually, the more I look at it the better it gets.
I've since spotted another Lisp version, but it's not very crisp either.
I think the SHA-1 algorithm is fairly straight-forward to state, if rather harder to reason mathematically about. But this Lisp implementation is a little opaque for my Lisp noobiness level of understanding.
The algorithm was designed to be implemented efficiently on a machine with 32-bit words and there is a little bit of gubbins necessary to get Lisp to do modulo 32-bit arithmetic. But it's not just that that makes this code hard for me to read.
While I only found two examples of SHA-1 in Lisp I found many examples in other languages and I discovered that Linus Torvalds recently spent some time improving the performance of the Git SHA-1 algorithm. Personally. So I thought I should take a closer look at that. Here it is.
It's interesting to compare Linus's version with this version, or even this version.
After looking at some of the many SHA-1 implementations around the web I decided to write my own version that would have these goals
2. Crisp (i.e. short and sweet).
3. Aspiring to the efficiency of Linus's version.
So here is my version, which, of course, borrows ideas from many sources
Did I achieve those goals?
The code produces correct results for all the sample data used. It is probably ready for some real-world testing. (I tested the code on GCC on OS X and MS VC 2003 on Windows. I also ran the code through Comeau C++ and Gimple Lint.)
The code doesn't get in the way of the algorithm. You could look at the FIPS 180-1 definition and look at this code and see the algorithm in the code. But is it crisp? In the end, this is a matter of taste.
The unit tests I wrote for this code are shown below. They run in ~52 seconds on my computer. If I replace my
process_bytes()function with Linus's
blk_SHA1Block()the same unit tests run in ~32 seconds - about 60% of the time required by mine. (Not forgetting how slippery a beast a benchmark is.)
There is often a balance between correctness, efficiency and lucidity. Sometimes I don't have the time or the imagination to find a good solution. In this case I spent some time trying different ideas that I thought might improve the performance of my implementation but I couldn't find any way to significantly improve the execution time while not losing the simplicity and comprehensibility of the source code.
Given that the SHA-1 algorithm isn't going to change, you're probably not going to have to work on it, so the simplicity of the source code is probably not so important. If run-time performance is important in your application you'd almost certainly be better off with Linus's code than with mine.
The code is available on github here. Thank you for reading.
UPDATE: The namespace nettle_soup came to me in the car. I thought: I like how it's common or garden and a bit quirky and no one will be using nettle_soup for a namespace so it won't clash with anyone's existing code. And lo, I was wrong; there is a library of cryptographic functions, including SHA-1, called Nettle.