{-# 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)
} 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
let vw :: Word64
vw = Vector Word64 -> Int -> Word64
forall a. Storable a => Vector a -> Int -> a
DVS.unsafeIndex Vector Word64
v Int
vi
let vwpc :: Word64
vwpc = Word64 -> Word64
forall v. PopCount1 v => v -> Word64
popCount1 Word64
vw
let npc :: Word64
npc = Word64
vwpc Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
lpc
if Word64
npc Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64
epc
then do
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
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
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
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 #-}