{-# OPTIONS_GHC-funbox-strict-fields #-}

{-# LANGUAGE BangPatterns        #-}
{-# LANGUAGE DeriveAnyClass      #-}
{-# LANGUAGE DeriveGeneric       #-}
{-# LANGUAGE MultiWayIf          #-}
{-# LANGUAGE Rank2Types          #-}
{-# LANGUAGE ScopedTypeVariables #-}

module HaskellWorks.Data.RankSelect.CsPoppy.Internal.Alpha1
    ( CsPoppyIndex(..)
    , makeCsPoppyIndex
    , makeCsPoppyBlocks
    , makeCsPoppyLayerM2
    , genCsSamples
    , rank1On
    , select1On
    ) where

import Control.DeepSeq
import Data.Word
import GHC.Generics
import HaskellWorks.Data.AtIndex
import HaskellWorks.Data.Bits.BitWise
import HaskellWorks.Data.Bits.PopCount.PopCount1
import HaskellWorks.Data.Drop
import HaskellWorks.Data.Positioning
import HaskellWorks.Data.RankSelect.Base.Rank1
import HaskellWorks.Data.RankSelect.Base.Select1
import HaskellWorks.Data.RankSelect.CsPoppy.Internal.CsInterleaved
import HaskellWorks.Data.RankSelect.CsPoppy.Internal.Lookup
import HaskellWorks.Data.RankSelect.CsPoppy.Internal.Vector

import Prelude hiding (drop)

import qualified Control.Monad.ST             as ST
import qualified Data.Vector.Storable         as DVS
import qualified Data.Vector.Storable.Mutable as DVSM

data CsPoppyIndex = CsPoppyIndex
  { CsPoppyIndex -> Vector Word64
csPoppyLayerM :: !(DVS.Vector Word64)
  , CsPoppyIndex -> Vector Word64
csPoppyLayerS :: !(DVS.Vector Word64) -- Sampling lookup of each 8192 1-bit
  } deriving (CsPoppyIndex -> CsPoppyIndex -> Bool
(CsPoppyIndex -> CsPoppyIndex -> Bool)
-> (CsPoppyIndex -> CsPoppyIndex -> Bool) -> Eq CsPoppyIndex
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: CsPoppyIndex -> CsPoppyIndex -> Bool
$c/= :: CsPoppyIndex -> CsPoppyIndex -> Bool
== :: CsPoppyIndex -> CsPoppyIndex -> Bool
$c== :: CsPoppyIndex -> CsPoppyIndex -> Bool
Eq, Int -> CsPoppyIndex -> ShowS
[CsPoppyIndex] -> ShowS
CsPoppyIndex -> String
(Int -> CsPoppyIndex -> ShowS)
-> (CsPoppyIndex -> String)
-> ([CsPoppyIndex] -> ShowS)
-> Show CsPoppyIndex
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [CsPoppyIndex] -> ShowS
$cshowList :: [CsPoppyIndex] -> ShowS
show :: CsPoppyIndex -> String
$cshow :: CsPoppyIndex -> String
showsPrec :: Int -> CsPoppyIndex -> ShowS
$cshowsPrec :: Int -> CsPoppyIndex -> ShowS
Show, CsPoppyIndex -> ()
(CsPoppyIndex -> ()) -> NFData CsPoppyIndex
forall a. (a -> ()) -> NFData a
rnf :: CsPoppyIndex -> ()
$crnf :: CsPoppyIndex -> ()
NFData, (forall x. CsPoppyIndex -> Rep CsPoppyIndex x)
-> (forall x. Rep CsPoppyIndex x -> CsPoppyIndex)
-> Generic CsPoppyIndex
forall x. Rep CsPoppyIndex x -> CsPoppyIndex
forall x. CsPoppyIndex -> Rep CsPoppyIndex x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall x. Rep CsPoppyIndex x -> CsPoppyIndex
$cfrom :: forall x. CsPoppyIndex -> Rep CsPoppyIndex x
Generic)

makeCsPoppyIndex :: DVS.Vector Word64 -> CsPoppyIndex
makeCsPoppyIndex :: Vector Word64 -> CsPoppyIndex
makeCsPoppyIndex Vector Word64
v = CsPoppyIndex :: Vector Word64 -> Vector Word64 -> CsPoppyIndex
CsPoppyIndex
  { csPoppyLayerM :: Vector Word64
csPoppyLayerM = Vector Word64
layerM
  , csPoppyLayerS :: Vector Word64
csPoppyLayerS = Vector Word64
layerS
  }
  where blocks :: Vector Word64
blocks          = Vector Word64 -> Vector Word64
makeCsPoppyBlocks Vector Word64
v
        layerM :: Vector Word64
layerM          = Vector Word64 -> Vector Word64
makeCsPoppyLayerM2 Vector Word64
blocks
        layerMPopCount :: Word64
layerMPopCount  = CsInterleaved -> Word64
getCsiTotal (Word64 -> CsInterleaved
CsInterleaved (Vector Word64 -> Word64
lastOrZero Vector Word64
layerM))
        layerS :: Vector Word64
layerS          = Word64 -> Vector Word64 -> Vector Word64
genCsSamples Word64
layerMPopCount Vector Word64
v

makeCsPoppyBlocks :: DVS.Vector Word64 -> DVS.Vector Word64
makeCsPoppyBlocks :: Vector Word64 -> Vector Word64
makeCsPoppyBlocks Vector Word64
v = Int -> (Int -> Word64) -> Vector Word64
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate (((Vector Word64 -> Int
forall a. Storable a => Vector a -> Int
DVS.length Vector Word64
v Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
8 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
8) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> Word64
genBlocks
  where e :: Int
e = Vector Word64 -> Int
forall a. Storable a => Vector a -> Int
DVS.length Vector Word64
v
        genBlocks :: Int -> Word64
        genBlocks :: Int -> Word64
genBlocks Int
u = let i :: Int
i = Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
u in if
          | (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
8 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
e -> let j :: Int
j = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
8 in
              Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
0)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+
              Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+
              Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+
              Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
3)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+
              Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
4)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+
              Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
5)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+
              Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
6)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+
              Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
7))
          | Bool
otherwise -> Vector Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 (Int -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Vector a -> Vector a
DVS.take Int
8 (Int -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Vector a -> Vector a
DVS.drop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
8) Vector Word64
v))

makeCsPoppyLayerM2 :: DVS.Vector Word64 -> DVS.Vector Word64
makeCsPoppyLayerM2 :: Vector Word64 -> Vector Word64
makeCsPoppyLayerM2 Vector Word64
blocks = Int -> (Vector Word64 -> Word64) -> Vector Word64
forall a. Storable a => Int -> (Vector a -> a) -> Vector a
DVS.constructN (((Vector Word64 -> Int
forall a. Storable a => Vector a -> Int
DVS.length Vector Word64
blocks Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
4 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
4) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Vector Word64 -> Word64
genLayer1
  where genLayer1 :: DVS.Vector Word64 -> Word64
        genLayer1 :: Vector Word64 -> Word64
genLayer1 Vector Word64
u = let ui :: Position
ui = Vector Word64 -> Position
forall v. Length v => v -> Position
end Vector Word64
u in if Position
ui Position -> Position -> Bool
forall a. Ord a => a -> a -> Bool
> Position
0 Bool -> Bool -> Bool
&& Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
+ Position
4 Position -> Position -> Bool
forall a. Ord a => a -> a -> Bool
< Vector Word64 -> Position
forall v. Length v => v -> Position
end Vector Word64
blocks
          then  let lx :: Word64
lx = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
u      (Position -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Position
ui     Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
1)) in
                let la :: Word64
la = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
blocks (Position -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
4)) in
                let lb :: Word64
lb = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
blocks (Position -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
3)) in
                let lc :: Word64
lc = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
blocks (Position -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
2)) in
                let ld :: Word64
ld = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
blocks (Position -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
1)) in
                let nx :: Word64
nx = Word64
lx Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
la Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
lb Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
lc Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
ld)                           in
                let na :: Word64
na = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
blocks (Position -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
+ Position
0)) in
                let nb :: Word64
nb = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
blocks (Position -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
+ Position
1)) in
                let nc :: Word64
nc = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
blocks (Position -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
+ Position
2)) in
                (   ( Word64
nx         Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x00000000ffffffff)
                Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. ((Word64
na Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
32) Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000003ff00000000)
                Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. ((Word64
nb Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
42) Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000ffc0000000000)
                Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. ((Word64
nc Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
52) Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x3ff0000000000000))
          else  let lx :: Word64
lx = Vector Word64 -> Word64
lastOrZero Vector Word64
u                     in
                let la :: Word64
la = Vector Word64 -> Position -> Word64
indexOrZero Vector Word64
blocks (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
4)  in
                let lb :: Word64
lb = Vector Word64 -> Position -> Word64
indexOrZero Vector Word64
blocks (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
3)  in
                let lc :: Word64
lc = Vector Word64 -> Position -> Word64
indexOrZero Vector Word64
blocks (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
2)  in
                let ld :: Word64
ld = Vector Word64 -> Position -> Word64
indexOrZero Vector Word64
blocks (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
- Position
1)  in
                let nx :: Word64
nx = Word64
lx Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
la Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
lb Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
lc Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
ld)         in
                let na :: Word64
na = Vector Word64 -> Position -> Word64
indexOrZero Vector Word64
blocks (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
+ Position
0)  in
                let nb :: Word64
nb = Vector Word64 -> Position -> Word64
indexOrZero Vector Word64
blocks (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
+ Position
1)  in
                let nc :: Word64
nc = Vector Word64 -> Position -> Word64
indexOrZero Vector Word64
blocks (Position
ui Position -> Position -> Position
forall a. Num a => a -> a -> a
* Position
4 Position -> Position -> Position
forall a. Num a => a -> a -> a
+ Position
2)  in
                (   ( Word64
nx         Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x00000000ffffffff)
                Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. ((Word64
na Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
32) Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000003ff00000000)
                Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. ((Word64
nb Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
42) Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000ffc0000000000)
                Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. ((Word64
nc Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
52) Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x3ff0000000000000))

sampleWidth :: Count
sampleWidth :: Word64
sampleWidth = Word64
8192
{-# INLINE sampleWidth #-}

genCsSamples :: Count -> DVS.Vector Word64 -> DVS.Vector Word64
genCsSamples :: Word64 -> Vector Word64 -> Vector Word64
genCsSamples Word64
pc Vector Word64
v = (forall s. ST s (MVector s Word64)) -> Vector Word64
forall a. Storable a => (forall s. ST s (MVector s a)) -> Vector a
DVS.create (Word64 -> Vector Word64 -> forall s. ST s (MVector s Word64)
genCsSamplesST Word64
pc Vector Word64
v)

genCsSamplesST :: Count -> DVS.Vector Word64 -> (forall s . ST.ST s (DVS.MVector s Word64))
genCsSamplesST :: Word64 -> Vector Word64 -> forall s. ST s (MVector s Word64)
genCsSamplesST Word64
pc Vector Word64
v = do
  MVector s Word64
u :: DVSM.MVector s Word64 <- Int -> ST s (MVector (PrimState (ST s)) Word64)
forall (m :: * -> *) a.
(PrimMonad m, Storable a) =>
Int -> m (MVector (PrimState m) a)
DVSM.unsafeNew Int
maxSize

  MVector s Word64
-> Int -> Int -> Int -> Word64 -> Word64 -> ST s (MVector s Word64)
forall s.
MVector s Word64
-> Int -> Int -> Int -> Word64 -> Word64 -> ST s (MVector s Word64)
go MVector s Word64
u Int
0 Int
0 (Vector Word64 -> Int
forall a. Storable a => Vector a -> Int
DVS.length Vector Word64
v) Word64
0 Word64
1
  where maxSize :: Int
        maxSize :: Int
maxSize = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> Int) -> Word64 -> Int
forall a b. (a -> b) -> a -> b
$ (Word64
pc Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` Word64
8192) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1
        go :: DVS.MVector s Word64 -> Int -> Int -> Int -> Count -> Count -> ST.ST s (DVS.MVector s Word64)
        go :: MVector s Word64
-> Int -> Int -> Int -> Word64 -> Word64 -> ST s (MVector s Word64)
go MVector s Word64
u Int
ui Int
vi Int
vie Word64
lpc Word64
epc | Int
vi Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
vie = do
          -- u:   Target vector
          -- ui:  Target vector index
          -- uim: Target vector end index
          -- v:   Source vector
          -- vi:  Target vector index
          -- lpc: Last pop count
          -- epc: Expectant pop count

          -- uw <- DVSM.read u ui
          let vw :: Word64
vw    = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v Int
vi  -- Source word
          let vwpc :: Word64
vwpc  = Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 Word64
vw          -- Source word pop count
          let npc :: Word64
npc   = Word64
vwpc Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
lpc            -- Next pop count

          if Word64
npc Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64
epc
            then do -- Emit a position
              let dpc :: Word64
dpc = Word64
epc Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
lpc
              let ewp :: Word64
ewp = Word64 -> Word64 -> Word64
forall v. Select1 v => v -> Word64 -> Word64
select1 Word64
vw Word64
dpc Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
vi Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
64 -- Expectant word position
              MVector (PrimState (ST s)) Word64 -> Int -> Word64 -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Storable a) =>
MVector (PrimState m) a -> Int -> a -> m ()
DVSM.unsafeWrite MVector s Word64
MVector (PrimState (ST s)) Word64
u Int
ui Word64
ewp
              MVector s Word64
-> Int -> Int -> Int -> Word64 -> Word64 -> ST s (MVector s Word64)
forall s.
MVector s Word64
-> Int -> Int -> Int -> Word64 -> Word64 -> ST s (MVector s Word64)
go MVector s Word64
u (Int
ui Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int
vi Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int
vie Word64
npc (Word64
epc Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
sampleWidth)
            else MVector s Word64
-> Int -> Int -> Int -> Word64 -> Word64 -> ST s (MVector s Word64)
forall s.
MVector s Word64
-> Int -> Int -> Int -> Word64 -> Word64 -> ST s (MVector s Word64)
go MVector s Word64
u Int
ui (Int
vi Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int
vie Word64
npc Word64
epc -- Don't emit a position this time
        go MVector s Word64
u Int
ui Int
_ Int
_ Word64
_ Word64
_ = MVector s Word64 -> ST s (MVector s Word64)
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> MVector s Word64 -> MVector s Word64
forall a s. Storable a => Int -> MVector s a -> MVector s a
DVSM.take Int
ui MVector s Word64
u)

rank1On :: DVS.Vector Word64 -> CsPoppyIndex -> Count -> Count
rank1On :: Vector Word64 -> CsPoppyIndex -> Word64 -> Word64
rank1On Vector Word64
v (CsPoppyIndex Vector Word64
layerM Vector Word64
_) Word64
p = Word64
rankPrior Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
rankInBasicBlock
  where mw :: Elem (Vector Word64)
mw  = Vector Word64
layerM Vector Word64 -> Position -> Elem (Vector Word64)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a. ToPosition a => a -> Position
toPosition (Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` Word64
2048)
        mx :: Word64
mx  =  Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x00000000ffffffff
        ma :: Word64
ma  = (Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000003ff00000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
32
        mb :: Word64
mb  = (Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000ffc0000000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
42
        mc :: Word64
mc  = (Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x3ff0000000000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
52
        q :: Word64
q   = (Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` Word64
512) Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`mod` Word64
4 -- quarter
        mi :: Word64
mi  | Word64
q Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0    = Word64
mx
            | Word64
q Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
1    = Word64
mx Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
ma
            | Word64
q Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
2    = Word64
mx Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
ma Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
mb
            | Word64
q Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
3    = Word64
mx Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
ma Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
mb Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
mc
            | Bool
otherwise = String -> Word64
forall a. HasCallStack => String -> a
error String
"Invalid interleaved entry index"
        rankPrior :: Word64
rankPrior         = Word64
mi :: Count
        rankInBasicBlock :: Word64
rankInBasicBlock  = Vector Word64 -> Word64 -> Word64
forall v. Rank1 v => v -> Word64 -> Word64
rank1 (Int -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Vector a -> Vector a
DVS.drop (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` Word64
512) Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
8) Vector Word64
v) (Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`mod` Word64
512)
{-# INLINE rank1On #-}

select1On :: DVS.Vector Word64 -> CsPoppyIndex -> Count -> Count
select1On :: Vector Word64 -> CsPoppyIndex -> Word64 -> Word64
select1On Vector Word64
_ CsPoppyIndex
_ Word64
r | Word64
r Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0  = Word64
0
select1On Vector Word64
v (CsPoppyIndex !Vector Word64
layerM !Vector Word64
layerS) Word64
r =
  let !si :: Word64
si                 = (Word64
r Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
1) Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` Word64
8192                              in
  let !spi :: Elem (Vector Word64)
spi                = Vector Word64
layerS Vector Word64 -> Position -> Elem (Vector Word64)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
si                      in
  let vBitSize :: Word64
vBitSize            = Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word64 -> Int
forall a. Storable a => Vector a -> Int
DVS.length Vector Word64
v) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
64                in
  let !spj :: Elem (Vector Word64)
spj                = Elem (Vector Word64)
-> Vector Word64 -> Position -> Elem (Vector Word64)
forall v. AtIndex v => Elem v -> v -> Position -> Elem v
atIndexOr Word64
Elem (Vector Word64)
vBitSize Vector Word64
layerS (Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
si Position -> Position -> Position
forall a. Num a => a -> a -> a
+ Position
1) in
  let !mi :: Word64
mi                 = Word64
spi Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` (Word64
512 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4)                             in
  let !mj :: Word64
mj                 = Word64
spj Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` (Word64
512 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4)                             in
  let !(!Word64
bbr, !Word64
bbi)       = Word64 -> Word64 -> Word64 -> Vector Word64 -> (Word64, Word64)
lookupLayerMFrom2 Word64
mi (Word64
mj Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1) Word64
r Vector Word64
layerM          in
  let !block :: Vector Word64
block              = Int -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Vector a -> Vector a
DVS.take Int
8 (Word64 -> Vector Word64 -> Vector Word64
forall v. Drop v => Word64 -> v -> v
drop (Word64
bbi Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
8) Vector Word64
v)                   in
  let !q :: Word64
q                  = Word64
r Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
bbr                                         in

  Vector Word64 -> Word64 -> Word64
forall v. Select1 v => v -> Word64 -> Word64
select1 Vector Word64
block Word64
q Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
bbi Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
512
{-# INLINE select1On #-}