From 180950d844550cbe5cdc47a6ce4d3c5fa50d7709 Mon Sep 17 00:00:00 2001 From: Ramakrishnan Muthukrishnan <ram@rkrishnan.org> Date: Thu, 31 Dec 2015 18:58:53 +0530 Subject: [PATCH] add rolling checksum implementation --- src/Lib.hs | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/src/Lib.hs b/src/Lib.hs index 260de94..2500097 100644 --- a/src/Lib.hs +++ b/src/Lib.hs @@ -83,3 +83,10 @@ recreate f0 blockSize ins = RBlk i -> (f0blocks !! i) `mappend` go f0blocks insts RChar w -> BL.singleton w `mappend` go f0blocks insts +rollingChecksum :: Int -> Int -> BL.ByteString -> Word32 +rollingChecksum strtIdx lenBS bs = a `mod` m + ((fromIntegral b) `mod` m) * m + where a = BL.foldl (\acc x -> acc + (fromIntegral x)) 0 bs' + b = BL.foldl (\acc x -> acc + x) 0 (BL.pack wbs') + bs' = BL.take (fromIntegral lenBS) $ BL.drop (fromIntegral strtIdx) bs + m = 2^16 + wbs' = BL.zipWith (*) (BL.pack (reverse (map fromIntegral [1..(lenBS - strtIdx + 1)]))) bs' -- 2.45.2