[Haskell-cafe] sha1 implementation thats "only" 12 times slower then C

[Anatoly Yakovenko]

---------- Forwarded message ----------
From: Anatoly Yakovenko <aeyakovenko at gmail.com>
Date: Jul 14, 2007 11:09 AM
Subject: Re: Your SHA1
To: Dominic Steinitz <dominic.steinitz at blueyonder.co.uk>


> > 1. Very good.

Thanks, it was a fun experiment.

> > 2. It has type hash::BS.ByteString -> IO [Word] but hash is a pure function.
> > Can this be changed?

you can call it safely with unsafePerformIO, I do a lot of hacks to
get the performance, like casting a C ptr from a bytestring to a word
array, but each call to hash should have no side effects.

> > 3. I haven't tried but I assume it only runs with ghc and not hugs? I guess if
> > point 1 could be addressed then we could put it in the crypto library (assuming
> > you are happy with this) with some sort of conditional flag to use your code if
> > the library is being built for ghc but to use the slow version for other
> > compilers / interpreters.

i would be surprised if this ran on hugs, i havent tried.  Also, i
haven't verified that my implementation is correct, as far as the sha1
algorithm is concerned.  the complexity is the same, so if there any
bugs in the math they can be easily fixed without making it slower.

> > On a more discursive note, I still don't think we have found the holy grail
> > here: idiomatic functional programming (probably not using StorableArray and
> > unsafeRead and unsafeWrite) and lightning fast speed.

yea, i agree, i am doing a lot of ugly hacks to get things going
faster.  Actually i think the "cleaner" approach would be to use Harpy
extension and do the math with x86 assembly :).  This way its at least
straight forward, cause right now, i was just randomly changing
strictness and unboxing things so ghc generates the fastest code, but
a different haskell compiler would have completely different results.

> > Dominic.
> >
> > PS I noticed you have:
> >
> > splitByN::Int -> BS.ByteString -> [BS.ByteString]
> > splitByN nn ll = st : (if (BS.null en) then [] else (splitByN nn en))
> >    where
> >       (st,en) = BS.splitAt nn ll
> >
> > It's a function I often use:
> >
> > splitByN n =
> >    unfoldr k
> >       where
> >          k [] = Nothing
> >          k p = Just (splitAt n p)
> >
> > Maybe it should be a standard part of List and ByteString?

yea i agree, i've seen a couple other implementations as well.  seems
like its something that should be in Prelude and ByteString.

Anatoly