import qualified Data.ByteString as B
import qualified Data.ByteString.Lazy as BL
compress2 ::
UArray (Word8,Word8) Word8 ->
UArray Int Word8 ->
UArray Int Word8 ->
Int ->
UArray Int Word8
compress2 sbox buf0 buf1 sboxalt = compress sbox buf sboxalt where
(beg0,end0) = bounds buf0
(beg1,end1) = bounds buf1
len = end0 + end1 + 2 - beg0 - beg1
buf = listArray (0,len-1) (elems buf0 ++ elems buf1)
compress3 ::
UArray (Word8,Word8) Word8 ->
UArray Int Word8 ->
UArray Int Word8 ->
UArray Int Word8 ->
Int ->
UArray Int Word8
compress3 sbox buf0 buf1 buf2 sboxalt = compress sbox buf sboxalt where
(beg0,end0) = bounds buf0
(beg1,end1) = bounds buf1
(beg2,end2) = bounds buf2
len = end0 + end1 + end2 + 3 - beg0 - beg1 - beg2
buf = listArray (0,len-1) (elems buf0 ++ elems buf1 ++ elems buf2)
data Twistree = Twistree
{ sbox :: UArray (Word8,Word8) Word8
} deriving Show
compressPairs :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> [UArray Int Word8]
compressPairs _ [] = []
compressPairs _ [x] = [x]
compressPairs sbox (x:y:xs) = ((compress2 sbox x y 0) : compressPairs sbox xs)
hashPairs :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> UArray Int Word8
hashPairs _ [] = undefined -- can't happen, there's always at least exp(4)
hashPairs _ [x] = x
hashPairs sbox x = hashPairs sbox (compressPairs sbox x)
compressTriples :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> [UArray Int Word8]
compressTriples _ [] = []
compressTriples _ [x] = [x]
compressTriples sbox [x,y] = [compress2 sbox x y 1]
compressTriples sbox (x:y:z:xs) = ((compress3 sbox x y z 1) : compressTriples sbox xs)
hashTriples :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> UArray Int Word8
hashTriples _ [] = undefined -- can't happen, there's always at least exp(4)
hashTriples _ [x] = x
hashTriples sbox x = hashTriples sbox (compressTriples sbox x)
linearTwistree = Twistree linearSbox
-- | Creates a Twistree with the given key.
-- To convert a String to a ByteString, put "- utf8-string" in your
-- package.yaml dependencies, import Data.ByteString.UTF8, and use
-- fromString.
keyedTwistree :: B.ByteString -> Twistree
keyedTwistree key = Twistree sbox where
sbox = sboxes key
hash :: Twistree -> BL.ByteString -> UArray Int Word8
hash twistree stream = par h2 $ par h3 $ compress2 (sbox twistree) h2 h3 2 where
blocks = blockize stream
h2 = hashPairs (sbox twistree) (exp4_2adic : blocks)
h3 = hashTriples (sbox twistree) (exp4_base2 : blocks)
This code takes a lazy ByteString, which in this program is read from a file but could come from elsewhere, and hashes it. The hash
function computes h2
and h3
in parallel, because they both consume the ByteString, then calls compress2
once they're both finished.
I'd like to make this more parallel. The compress2
and compress3
operations take 289 and 763 µs, respectively, on my box, and the program spends 42.5% and 56.0% of the time in them and only 1.4% blockizing the input. Can you suggest ways to do this?
The code repo is at https://github.com/phma/wring-twistree .