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