{-# LANGUAGE BangPatterns #-}
module Data.ByteString.Lazy.Search.KarpRabin (
indicesOfAny
) where
import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L
import Data.ByteString.Unsafe (unsafeIndex)
import qualified Data.IntMap as IM
import Data.Array
import Data.Array.Base (unsafeAt)
import Data.Word (Word8)
import Data.Int (Int64)
import Data.Bits
import Data.List (foldl')
{-# INLINE indicesOfAny #-}
indicesOfAny :: [S.ByteString]
-> L.ByteString
-> [(Int64,[Int])]
indicesOfAny :: [ByteString] -> ByteString -> [(Int64, [Int])]
indicesOfAny [ByteString]
pats
| [ByteString] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [ByteString]
nepats = [(Int64, [Int])] -> ByteString -> [(Int64, [Int])]
forall a b. a -> b -> a
const []
| Bool
otherwise = [ByteString] -> [ByteString] -> [(Int64, [Int])]
lazyMatcher [ByteString]
nepats ([ByteString] -> [(Int64, [Int])])
-> (ByteString -> [ByteString]) -> ByteString -> [(Int64, [Int])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ByteString -> [ByteString]
L.toChunks
where
nepats :: [ByteString]
nepats = (ByteString -> Bool) -> [ByteString] -> [ByteString]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (ByteString -> Bool) -> ByteString -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ByteString -> Bool
S.null) [ByteString]
pats
{-# INLINE rehash1 #-}
rehash1 :: Int -> Int -> Word8 -> Word8 -> Int
rehash1 :: Int -> Int -> Word8 -> Word8 -> Int
rehash1 Int
out Int
h Word8
o Word8
n =
(Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
out)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n
{-# INLINE rehash2 #-}
rehash2 :: Int -> Int -> Word8 -> Word8 -> Int
rehash2 :: Int -> Int -> Word8 -> Word8 -> Int
rehash2 Int
out Int
h Word8
o Word8
n =
(Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
out)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n
{-# INLINE rehash3 #-}
rehash3 :: Int -> Int -> Word8 -> Word8 -> Int
rehash3 :: Int -> Int -> Word8 -> Word8 -> Int
rehash3 Int
out Int
h Word8
o Word8
n =
(Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
3 Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
out)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n
{-# INLINE rehash4 #-}
rehash4 :: Int -> Int -> Word8 -> Word8 -> Int
rehash4 :: Int -> Int -> Word8 -> Word8 -> Int
rehash4 Int
out Int
h Word8
o Word8
n =
(Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
4 Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
out)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n
lazyMatcher :: [S.ByteString] -> [S.ByteString] -> [(Int64,[Int])]
lazyMatcher :: [ByteString] -> [ByteString] -> [(Int64, [Int])]
lazyMatcher [ByteString]
pats = Int -> Int -> ByteString -> [ByteString] -> [(Int64, [Int])]
forall {t}.
Num t =>
Int -> Int -> ByteString -> [ByteString] -> [(t, [Int])]
search Int
0 Int
hLen ByteString
S.empty
where
!hLen :: Int
hLen = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum (Int
32 Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: (ByteString -> Int) -> [ByteString] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map ByteString -> Int
S.length [ByteString]
pats)
!shDi :: Int
shDi = case Int
32 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
hLen of
Int
q | Int
q Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
4 -> Int
q
| Bool
otherwise -> Int
4
!outS :: Int
outS = Int
shDiInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
hLen
!patNum :: Int
patNum = [ByteString] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [ByteString]
pats
!patArr :: Array Int ByteString
patArr = (Int, Int) -> [ByteString] -> Array Int ByteString
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Int
0, Int
patNum Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [ByteString]
pats
{-# INLINE rehash #-}
rehash :: Int -> Word8 -> Word8 -> Int
rehash :: Int -> Word8 -> Word8 -> Int
rehash = case Int
shDi of
Int
1 -> Int -> Int -> Word8 -> Word8 -> Int
rehash1 Int
hLen
Int
2 -> Int -> Int -> Word8 -> Word8 -> Int
rehash2 Int
outS
Int
3 -> Int -> Int -> Word8 -> Word8 -> Int
rehash3 Int
outS
Int
_ -> Int -> Int -> Word8 -> Word8 -> Int
rehash4 Int
outS
hash :: S.ByteString -> Int
hash :: ByteString -> Int
hash = (Int -> Word8 -> Int) -> Int -> ByteString -> Int
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
S.foldl' (\Int
h Word8
w -> (Int
h Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
shDi) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w) Int
0 (ByteString -> Int)
-> (ByteString -> ByteString) -> ByteString -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> ByteString -> ByteString
S.take Int
hLen
!hashMap :: IntMap [Int]
hashMap =
(IntMap [Int] -> (Int, Int) -> IntMap [Int])
-> IntMap [Int] -> [(Int, Int)] -> IntMap [Int]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntMap [Int]
mp (Int
h,Int
i) -> ([Int] -> [Int] -> [Int])
-> Int -> [Int] -> IntMap [Int] -> IntMap [Int]
forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
IM.insertWith (([Int] -> [Int] -> [Int]) -> [Int] -> [Int] -> [Int]
forall a b c. (a -> b -> c) -> b -> a -> c
flip [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
(++)) Int
h [Int
i] IntMap [Int]
mp) IntMap [Int]
forall a. IntMap a
IM.empty ([(Int, Int)] -> IntMap [Int]) -> [(Int, Int)] -> IntMap [Int]
forall a b. (a -> b) -> a -> b
$
[Int] -> [Int] -> [(Int, Int)]
forall a b. [a] -> [b] -> [(a, b)]
zip ((ByteString -> Int) -> [ByteString] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map ByteString -> Int
hash [ByteString]
pats) [Int
0 :: Int .. ]
search :: Int -> Int -> ByteString -> [ByteString] -> [(t, [Int])]
search Int
_ Int
_ ByteString
_ [] = []
search !Int
h !Int
rm !ByteString
prev (!ByteString
str : [ByteString]
rest)
| Int
strLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
rm =
let !h' :: Int
h' = (Int -> Word8 -> Int) -> Int -> ByteString -> Int
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
S.foldl' (\Int
o Word8
w -> (Int
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w) Int
h ByteString
str
!prev' :: ByteString
prev' = ByteString -> ByteString -> ByteString
S.append ByteString
prev ByteString
str
in Int -> Int -> ByteString -> [ByteString] -> [(t, [Int])]
search Int
h' (Int
rm Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
strLen) ByteString
prev' [ByteString]
rest
| Bool
otherwise =
let !h' :: Int
h' = (Int -> Word8 -> Int) -> Int -> ByteString -> Int
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
S.foldl' (\Int
o Word8
w -> (Int
o Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w) Int
h
(Int -> ByteString -> ByteString
S.take Int
rm ByteString
str)
in if ByteString -> Bool
S.null ByteString
prev
then t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
forall {t}.
Num t =>
t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
0 [ByteString]
rest ByteString
str Int
h'
else t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
forall {t}.
Num t =>
t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
past t
0 [ByteString]
rest ByteString
prev Int
0 ByteString
str Int
rm Int
h'
where
!strLen :: Int
strLen = ByteString -> Int
S.length ByteString
str
noPast :: t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast !t
prior [ByteString]
rest !ByteString
str Int
hsh = Int -> Int -> [(t, [Int])]
go Int
hsh Int
0
where
!strLen :: Int
strLen = ByteString -> Int
S.length ByteString
str
!maxIdx :: Int
maxIdx = Int
strLen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
hLen
{-# INLINE strAt #-}
strAt :: Int -> Word8
strAt !Int
i = ByteString -> Int -> Word8
unsafeIndex ByteString
str Int
i
go :: Int -> Int -> [(t, [Int])]
go !Int
h Int
sI =
case Int -> IntMap [Int] -> Maybe [Int]
forall a. Int -> IntMap a -> Maybe a
IM.lookup Int
h IntMap [Int]
hashMap of
Maybe [Int]
Nothing ->
if Int
sI Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
maxIdx
then case [ByteString]
rest of
[] -> []
(ByteString
nxt : [ByteString]
more) ->
let !h' :: Int
h' = Int -> Word8 -> Word8 -> Int
rehash Int
h (Int -> Word8
strAt Int
sI) (ByteString -> Int -> Word8
unsafeIndex ByteString
nxt Int
0)
!prior' :: t
prior' = t
prior t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
strLen
!prev :: ByteString
prev = Int -> ByteString -> ByteString
S.drop (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) ByteString
str
in if Int
hLen Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1
then t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
prior' [ByteString]
more ByteString
nxt Int
h'
else t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
past t
prior' [ByteString]
more ByteString
prev Int
0 ByteString
nxt Int
1 Int
h'
else Int -> Int -> [(t, [Int])]
go (Int -> Word8 -> Word8 -> Int
rehash Int
h (Int -> Word8
strAt Int
sI) (Int -> Word8
strAt (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
hLen))) (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
Just [Int]
ps ->
let !rst :: ByteString
rst = Int -> ByteString -> ByteString
S.drop Int
sI ByteString
str
!rLen :: Int
rLen = Int
strLen Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
sI
{-# INLINE hd #-}
hd :: Word8
hd = Int -> Word8
strAt Int
sI
{-# INLINE more #-}
more :: [(t, [Int])]
more =
if Int
sI Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
maxIdx
then case [ByteString]
rest of
[] -> []
(ByteString
nxt : [ByteString]
fut) ->
let !h' :: Int
h' = Int -> Word8 -> Word8 -> Int
rehash Int
h Word8
hd (ByteString -> Int -> Word8
unsafeIndex ByteString
nxt Int
0)
!prior' :: t
prior' = t
prior t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
strLen
in if Int
hLen Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1
then t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
prior' [ByteString]
fut ByteString
nxt Int
h'
else t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
past t
prior' [ByteString]
fut ByteString
rst Int
1 ByteString
nxt Int
1 Int
h'
else Int -> Int -> [(t, [Int])]
go (Int -> Word8 -> Word8 -> Int
rehash Int
h Word8
hd (Int -> Word8
strAt (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
hLen))) (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
okay :: ByteString -> Bool
okay ByteString
bs
| Int
rLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< ByteString -> Int
S.length ByteString
bs = ByteString -> ByteString -> Bool
S.isPrefixOf ByteString
rst ByteString
bs Bool -> Bool -> Bool
&&
ByteString -> [ByteString] -> Bool
checkFut (Int -> ByteString -> ByteString
S.drop Int
rLen ByteString
bs) [ByteString]
rest
| Bool
otherwise = ByteString -> ByteString -> Bool
S.isPrefixOf ByteString
bs ByteString
rst
in case (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (ByteString -> Bool
okay (ByteString -> Bool) -> (Int -> ByteString) -> Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Array Int ByteString
patArr Array Int ByteString -> Int -> ByteString
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt`)) [Int]
ps of
[] -> [(t, [Int])]
more
[Int]
qs -> Int -> [(t, [Int])] -> [(t, [Int])]
seq ([Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
qs) ([(t, [Int])] -> [(t, [Int])]) -> [(t, [Int])] -> [(t, [Int])]
forall a b. (a -> b) -> a -> b
$
(t
prior t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
sI,[Int]
qs) (t, [Int]) -> [(t, [Int])] -> [(t, [Int])]
forall a. a -> [a] -> [a]
: [(t, [Int])]
more
past :: t
-> [ByteString]
-> ByteString
-> Int
-> ByteString
-> Int
-> Int
-> [(t, [Int])]
past !t
prior [ByteString]
rest !ByteString
prev !Int
pI !ByteString
str !Int
sI !Int
hsh
| Int
strLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
4040 =
let !prior' :: t
prior' = t
prior t -> t -> t
forall a. Num a => a -> a -> a
- t
1 t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
sI Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
hLen)
!curr :: ByteString
curr = ByteString -> ByteString -> ByteString
S.append (Int -> ByteString -> ByteString
S.drop Int
pI ByteString
prev) ByteString
str
in t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
prior' [ByteString]
rest ByteString
curr Int
hsh
| Bool
otherwise = Int -> Int -> Int -> [(t, [Int])]
go Int
hsh Int
pI Int
sI
where
!strLen :: Int
strLen = ByteString -> Int
S.length ByteString
str
{-# INLINE strAt #-}
strAt :: Int -> Word8
strAt !Int
i = ByteString -> Int -> Word8
unsafeIndex ByteString
str Int
i
{-# INLINE prevAt #-}
prevAt :: Int -> Word8
prevAt !Int
i = ByteString -> Int -> Word8
unsafeIndex ByteString
prev Int
i
go :: Int -> Int -> Int -> [(t, [Int])]
go !Int
h !Int
p !Int
s
| Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hLen = t -> [ByteString] -> ByteString -> Int -> [(t, [Int])]
noPast t
prior [ByteString]
rest ByteString
str Int
h
| Bool
otherwise =
case Int -> IntMap [Int] -> Maybe [Int]
forall a. Int -> IntMap a -> Maybe a
IM.lookup Int
h IntMap [Int]
hashMap of
Maybe [Int]
Nothing ->
let {-# INLINE h' #-}
h' :: Int
h' = Int -> Word8 -> Word8 -> Int
rehash Int
h (Int -> Word8
prevAt Int
p) (Int -> Word8
strAt Int
s)
in Int -> Int -> Int -> [(t, [Int])]
go Int
h' (Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
Just [Int]
ps ->
let !prst :: ByteString
prst = Int -> ByteString -> ByteString
S.drop Int
p ByteString
prev
{-# INLINE more #-}
more :: [(t, [Int])]
more = Int -> Int -> Int -> [(t, [Int])]
go (Int -> Word8 -> Word8 -> Int
rehash Int
h (Int -> Word8
prevAt Int
p) (Int -> Word8
strAt Int
s)) (Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
okay :: ByteString -> Bool
okay ByteString
bs = ByteString -> [ByteString] -> Bool
checkFut ByteString
bs (ByteString
prst ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: ByteString
str ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: [ByteString]
rest)
in case (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (ByteString -> Bool
okay (ByteString -> Bool) -> (Int -> ByteString) -> Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Array Int ByteString -> Int -> ByteString
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
unsafeAt Array Int ByteString
patArr)) [Int]
ps of
[] -> [(t, [Int])]
more
[Int]
qs -> Int -> [(t, [Int])] -> [(t, [Int])]
seq ([Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
qs) ([(t, [Int])] -> [(t, [Int])]) -> [(t, [Int])] -> [(t, [Int])]
forall a b. (a -> b) -> a -> b
$
(t
prior t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
hLen), [Int]
qs) (t, [Int]) -> [(t, [Int])] -> [(t, [Int])]
forall a. a -> [a] -> [a]
: [(t, [Int])]
more
{-# INLINE checkFut #-}
checkFut :: S.ByteString -> [S.ByteString] -> Bool
checkFut :: ByteString -> [ByteString] -> Bool
checkFut ByteString
_ [] = Bool
False
checkFut !ByteString
bs (!ByteString
h : [ByteString]
t)
| Int
hLen Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< ByteString -> Int
S.length ByteString
bs = ByteString -> ByteString -> Bool
S.isPrefixOf ByteString
h ByteString
bs Bool -> Bool -> Bool
&& ByteString -> [ByteString] -> Bool
checkFut (Int -> ByteString -> ByteString
S.drop Int
hLen ByteString
bs) [ByteString]
t
| Bool
otherwise = ByteString -> ByteString -> Bool
S.isPrefixOf ByteString
bs ByteString
h
where
!hLen :: Int
hLen = ByteString -> Int
S.length ByteString
h