{-# LANGUAGE DataKinds #-}
{-# LANGUAGE MagicHash #-}

module Data.ByteString.RollingHash where

import qualified Data.ByteString as B
import GHC.Exts
import GHC.TypeLits
import GHC.Word

import Data.RollingHash

{- | @rollingHash == rollingHashWith 2047@

>>> import qualified Data.ByteString.Char8 as C
>>> rollingHash $ C.pack "abc"
406650978
>>> rollingHashWith @2047 $ C.pack "abc"
406650978
-}
rollingHash :: B.ByteString -> RollingHash 2047
rollingHash :: ByteString -> RollingHash 2047
rollingHash = Int -> RollingHash 2047
forall (b :: Nat). Int -> RollingHash b
RollingHash (Int -> RollingHash 2047)
-> (ByteString -> Int) -> ByteString -> RollingHash 2047
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Word8 -> Int) -> Int -> ByteString -> Int
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
B.foldl' Int -> Word8 -> Int
step Int
0
  where
    m# :: Int#
m# = Int#
0x1fffffffffffffff#
    step :: Int -> Word8 -> Int
step (I# Int#
acc#) (W8# Word8#
w8#) =
      case Int# -> Int# -> Int#
uncheckedIShiftRL# Int#
acc# Int#
50#
        Int# -> Int# -> Int#
+# Int# -> Int# -> Int#
andI# (Int# -> Int# -> Int#
uncheckedIShiftL# Int#
acc# Int#
11#) Int#
m#
        Int# -> Int# -> Int#
-# Int#
acc#
        Int# -> Int# -> Int#
+# Word# -> Int#
word2Int# (Word8# -> Word#
word8ToWord# Word8#
w8#) of
        Int#
qr# -> case Int#
qr# Int# -> Int# -> Int#
<# Int#
0# of
          Int#
b# -> Int# -> Int
I# (Int#
qr# Int# -> Int# -> Int#
-# Int#
b# Int# -> Int# -> Int#
+# Int# -> Int# -> Int#
uncheckedIShiftL# Int#
b# Int#
61#)

{- | @b@ should be a primitive root of (@2^61-1@)

>>> import qualified Data.ByteString.Char8 as C
>>> isPrimitiveRootRH 123
True
>>> rollingHashWith @123 $ C.pack "abc"
1479666
-}
rollingHashWith :: forall b. (KnownNat b) => B.ByteString -> RollingHash b
rollingHashWith :: forall (b :: Nat). KnownNat b => ByteString -> RollingHash b
rollingHashWith = (RollingHash b -> Word8 -> RollingHash b)
-> RollingHash b -> ByteString -> RollingHash b
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
B.foldl' (\RollingHash b
acc Word8
w -> RollingHash b
acc RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
* RollingHash b
forall {b :: Nat}. RollingHash b
base RollingHash b -> RollingHash b -> RollingHash b
forall a. Num a => a -> a -> a
+ Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w)) RollingHash b
0
  where
    base :: RollingHash b
base = Int -> RollingHash b
forall (b :: Nat). Int -> RollingHash b
RollingHash (Integer -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Nat). KnownNat n => Proxy# n -> Integer
natVal' @b Proxy# b
forall {k} (a :: k). Proxy# a
proxy#))