- if (fnew == BL.empty)
- then []
- else
- let (blk, blks) = BL.splitAt (fromIntegral blockSize) fnew
- sig = blockSig blk
- in
- case (lookup sig f0sigs) of
- Just (idx) -> RBlk (fromIntegral idx) : genInstructions f0sigs blockSize blks
- Nothing -> RChar (BL.head blk) :
- genInstructions f0sigs blockSize (BL.tail (blk `mappend` blks))
+ -- create two hash tables one with adler32 as key and list of block numbers as values
+ -- another with md4sum as key and block numbers as values.
+ evalState (go fnew) 0
+ where
+ go :: BL.ByteString -> State Word32 [Instruction]
+ go fnew | (fnew == BL.empty) = return []
+ | otherwise =
+ let (blk, blks) = BL.splitAt (fromIntegral blockSize) fnew
+ adlerSum = weakSig blk
+ in
+ case M.lookup adlerSum f0AdlerTable of
+ Nothing -> do
+ put adlerSum
+ is <- go (BL.tail (blk `mappend` blks))
+ return $ RChar (BL.head blk) : is
+ Just _ ->
+ let md4sum = blockSig blk
+ in
+ case M.lookup md4sum f0MD4Table of
+ Just i -> do
+ is <- go blks
+ return $ RBlk (head i) : is
+ Nothing ->
+ return [RChar (BL.head blk)]
+ f0AdlerTable = toAdlerMap f0sigs
+ f0MD4Table = toMD4Map f0sigs
+
+toAdlerMap :: [Signature] -> M.Map Adler32checksum [Int]
+toAdlerMap = foldr f M.empty
+ where f sig m = let (_, aSig, idx) = sig in M.insertWith (++) aSig [idx] m
+
+toMD4Map :: [Signature] -> M.Map Md4digest [Int]
+toMD4Map = foldr f M.empty
+ where f sig m = let (mSig, _, idx) = sig in M.insertWith (++) mSig [idx] m