SHA-1, SHA-256, SHA-384, SHA-512... DONE!
Completed, the SHA family of hashes are. They were quite interesting and really not as complicated as I was originally fearing. The single hardest part was dealing with the unsigned addition.
While implementing SHA-1 I was faced with needing unsigned addition in my signed integer world. I resorted to some assembly just to add two numbers. The rest of the algorithm was pretty straight forward. I was pleased with the coding, then became horrified at the performance. The first implementation was on an order of 10x slower than .NET. I had to think for a minute, then remembered I wasn't utilizing all of VB's compiling powers at all. I hadn't taken advantage of the Integer overflow checks being off. I couldn't use that optimization while working in the IDE, so I left the original version in to keep the proof-of-concept, if you will. To make sure my tests remain accurate, as well.
For the first time in VBCorLib I had a routine for the IDE and one for compiled runtime environments. Once I fully engaged all the optimization tricks the routine quickened up considerably. At the end I had the SHA-1 routine running only about 50% slower than .NET.
SHA-256 was basically the same thing as SHA-1. It just needs to work on more data at once. The final result was about 75% slower than .NET. That's pretty good.
The SHA-512 implementation had me for a bit. I needed to perform 64-bit addition. I tried using Currency along with some assembly. I could still do all the bitwise operations in VB. I did some testing for the speed of using Currency in bitwise intensive situations. Umm, not really the best solution. I then decided to maintain individual Hi and Lo 32-bit segments of each variable. All I had to do was double all the variables! Ok, so using that technique and some assembly for adding, I got an implementation working. Fired up a quick speed test and there it was... 4 seconds to hash 10megs. It took .NET 460ms. I hadn't done the native implementation because of the 64-bit math, shifting and rotating. I decided to do it anyways for as much as I could. I even figured out how to add 64-bits and detect the overflow of the lower 32-bits so I didn't need any assembly. I unrolled all the functions and put the raw code right into the core loops. Lots of duplication for handling 64-bit shifting, 64-bit rotating, and 64-bit addition. In the end it was all worth it. That same speed test decreased to 560ms. 80% the speed of .NET's native 64-bit handling. Pretty good day!
-Kelly
While implementing SHA-1 I was faced with needing unsigned addition in my signed integer world. I resorted to some assembly just to add two numbers. The rest of the algorithm was pretty straight forward. I was pleased with the coding, then became horrified at the performance. The first implementation was on an order of 10x slower than .NET. I had to think for a minute, then remembered I wasn't utilizing all of VB's compiling powers at all. I hadn't taken advantage of the Integer overflow checks being off. I couldn't use that optimization while working in the IDE, so I left the original version in to keep the proof-of-concept, if you will. To make sure my tests remain accurate, as well.
For the first time in VBCorLib I had a routine for the IDE and one for compiled runtime environments. Once I fully engaged all the optimization tricks the routine quickened up considerably. At the end I had the SHA-1 routine running only about 50% slower than .NET.
SHA-256 was basically the same thing as SHA-1. It just needs to work on more data at once. The final result was about 75% slower than .NET. That's pretty good.
The SHA-512 implementation had me for a bit. I needed to perform 64-bit addition. I tried using Currency along with some assembly. I could still do all the bitwise operations in VB. I did some testing for the speed of using Currency in bitwise intensive situations. Umm, not really the best solution. I then decided to maintain individual Hi and Lo 32-bit segments of each variable. All I had to do was double all the variables! Ok, so using that technique and some assembly for adding, I got an implementation working. Fired up a quick speed test and there it was... 4 seconds to hash 10megs. It took .NET 460ms. I hadn't done the native implementation because of the 64-bit math, shifting and rotating. I decided to do it anyways for as much as I could. I even figured out how to add 64-bits and detect the overflow of the lower 32-bits so I didn't need any assembly. I unrolled all the functions and put the raw code right into the core loops. Lots of duplication for handling 64-bit shifting, 64-bit rotating, and 64-bit addition. In the end it was all worth it. That same speed test decreased to 560ms. 80% the speed of .NET's native 64-bit handling. Pretty good day!
-Kelly
posted by Kelly Ethridge at
9/04/2006 06:39:00 PM
1 Comments:
Thanks for progress report, it's really interesting. I really envy your persistence and am looking forward for the next release.
Alex
By
Anonymous, at 9/07/2006 3:33 AM
Post a Comment
<< Home