{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE FlexibleInstances   #-}
{-# LANGUAGE ScopedTypeVariables #-}

module HaskellWorks.Data.BalancedParens.Internal.Broadword.FindUnmatchedCloseFar.Word8
  ( findUnmatchedCloseFar
  ) where

import Data.Int
import Data.Word
import HaskellWorks.Data.Bits.BitWise
import HaskellWorks.Data.Bits.Broadword.Word8
import HaskellWorks.Data.Int.Narrow
import HaskellWorks.Data.Int.Widen

muk1 :: Word8
muk1 :: Word8
muk1 = Word8
0x33
{-# INLINE muk1 #-}

muk2 :: Word8
muk2 :: Word8
muk2 = Word8
0x0f
{-# INLINE muk2 #-}

-- | Find the position of the first unmatch parenthesis.
--
-- This is the broadword implementation of 'HaskellWorks.Data.BalancedParens.Internal.Slow.Word8.findCloseFor'.
--
-- See [Broadword Implementation of Parenthesis Queries](https://arxiv.org/pdf/1301.5468.pdf), Sebastiano Vigna, 2013
findUnmatchedCloseFar :: Word64 -> Word64 -> Word8 -> Word64
findUnmatchedCloseFar :: Word64 -> Word64 -> Word8 -> Word64
findUnmatchedCloseFar Word64
c Word64
p Word8
w =
  --  Keys:
  --    * k1: Level of sub-words of size 2 = 1 .<. 1
  --    * k2: Level of sub-words of size 4 = 1 .<. 2
  --    * k3: Level of sub-words of size 8 = 1 .<. 3
  --    * o: Open count
  --    * c: Close count
  --    * e: Excess
  --    * L: Left half of sub-word
  --    * R: Right half of sub-word
  --    * b: deficit at position whole-word mask
  --    * m: deficit at position sub-word mask
  --    * pa: position accumulator
  --    * sa: shift accumulator
  --    * h: high sub-block close parens count
  --    * f: far sub-block close parens count
  let x :: Word8
x     = Word8
w Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64
p                                                                           in
  let wsz :: Int8
wsz   = Int8
8 :: Int8                                                                         in
  let k1 :: Word64
k1    = Word64
1                                                                                 in
  let k2 :: Word64
k2    = Word64
2                                                                                 in
  let k3 :: Word64
k3    = Word64
3                                                                                 in
  let mask3 :: Word8
mask3 = (Word8
1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. (Word64
1 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
k3)) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
1                                                            in
  let mask2 :: Word8
mask2 = (Word8
1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. (Word64
1 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
k2)) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
1                                                            in
  let mask1 :: Word8
mask1 = (Word8
1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. (Word64
1 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
k1)) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
1                                                            in
  let t64k1 :: Word64
t64k1 = Word64
1 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
k1 :: Word64                                                                in
  let t64k2 :: Word64
t64k2 = Word64
1 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
k2 :: Word64                                                                in
  let t8k1 :: Word8
t8k1  = Word8
1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
k1 :: Word8                                                                 in
  let t8k2 :: Word8
t8k2  = Word8
1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
k2 :: Word8                                                                 in
  let t8k3 :: Word8
t8k3  = Word8
1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
k3 :: Word8                                                                 in

  let b0 :: Word8
b0    =      Word8
x Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
0x55                                                                   in
  let b1 :: Word8
b1    =    ( Word8
x Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
0xaa) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64
1                                                            in
  let ll :: Word8
ll    =   (Word8
b0  Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.^. Word8
b1  ) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
b1                                                           in
  let ok1 :: Word8
ok1   = ( (Word8
b0  Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
b1  )           Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
1) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
ll                                          in
  let ck1 :: Word8
ck1   = (((Word8
b0  Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
b1  ) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.^. Word8
0x55) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
1) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
ll                                          in

  let eok1 :: Word8
eok1  =   Word8
ok1 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&.  Word8
muk1                                                                   in
  let eck1 :: Word8
eck1  =  (Word8
ck1 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. (Word8
muk1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
t64k1)) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64
t64k1                                             in
  let ok2L :: Word8
ok2L  =  (Word8
ok1 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. (Word8
muk1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
t64k1)) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64
t64k1                                             in
  let ok2R :: Word8
ok2R  = Int -> Word8 -> Word8 -> Word8
kBitDiffPos Int
4 Word8
eok1 Word8
eck1                                                           in
  let ok2 :: Word8
ok2   = Word8
ok2L Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
+ Word8
ok2R                                                                       in
  let ck2 :: Word8
ck2   =  (Word8
ck1 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&.  Word8
muk1) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
+ Int -> Word8 -> Word8 -> Word8
kBitDiffPos Int
4 Word8
eck1 Word8
eok1                                        in

  let eok2 :: Word8
eok2  =   Word8
ok2 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&.  Word8
muk2                                                                   in
  let eck2 :: Word8
eck2  =  (Word8
ck2 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. (Word8
muk2 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
t64k2)) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64
t64k2                                             in
  let ok3L :: Word8
ok3L  =  (Word8
ok2 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. (Word8
muk2 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.<. Word64
t64k2)) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64
t64k2                                             in
  let ok3R :: Word8
ok3R  = Int -> Word8 -> Word8 -> Word8
kBitDiffPos Int
8 Word8
eok2 Word8
eck2                                                           in
  let ok3 :: Word8
ok3   = Word8
ok3L Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
+ Word8
ok3R                                                                       in
  let ck3 :: Word8
ck3   =  (Word8
ck2 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&.  Word8
muk2) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
+ Int -> Word8 -> Word8 -> Word8
kBitDiffPos Int
8 Word8
eck2 Word8
eok2                                        in

  let pak3 :: Word64
pak3  = Word64
c                                                                                 in
  let sak3 :: Word64
sak3  = Word64
0                                                                                 in

  let hk3 :: Word8
hk3   = Word8
0x08 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8 -> Word8
forall a. BitWise a => a -> a
comp (Word8
0xff Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak3)                                        in
  let fk3 :: Word8
fk3   = (Word8
ck3 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak3 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
hk3) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mask3                                     in
  let bk3 :: Word8
bk3   = ((Word64 -> Word8
forall a b. Narrow a b => a -> b
narrow Word64
pak3 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
fk3) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Int8 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int8
wsz Int8 -> Int8 -> Int8
forall a. Num a => a -> a -> a
- Int8
1)) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
1                              in
  let mk3 :: Word8
mk3   = Word8
bk3 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mask3                                                                     in
  let pbk3 :: Word64
pbk3  = Word64
pak3 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word8 -> Word64
forall a b. Widen a b => a -> b
widen (((Word8
ck3 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak3) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
hk3) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mk3)                      in
  let pck3 :: Word64
pck3  = Word64
pbk3 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word8 -> Word64
forall a b. Widen a b => a -> b
widen (((Word8
ok3 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak3) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
hk3) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mk3)                      in
  let sbk3 :: Word64
sbk3  = Word64
sak3 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word8 -> Word64
forall a b. Widen a b => a -> b
widen (Word8
t8k3 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
bk3)                                                       in

  let pak2 :: Word64
pak2  = Word64
pck3                                                                              in
  let sak2 :: Word64
sak2  = Word64
sbk3                                                                              in

  let hk2 :: Word8
hk2   = Word8
0x44 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8 -> Word8
forall a. BitWise a => a -> a
comp (Word8
0xff Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak2)                                        in
  let fk2 :: Word8
fk2   = ((Word8
ck2 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak2) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
hk2) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mask2                                   in
  let bk2 :: Word8
bk2   = ((Word64 -> Word8
forall a b. Narrow a b => a -> b
narrow Word64
pak2 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
fk2) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Int8 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int8
wsz Int8 -> Int8 -> Int8
forall a. Num a => a -> a -> a
- Int8
1)) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
1                              in
  let mk2 :: Word8
mk2   = Word8
bk2 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mask2                                                                     in
  let pbk2 :: Word64
pbk2  = Word64
pak2 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word8 -> Word64
forall a b. Widen a b => a -> b
widen (((Word8
ck2 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak2) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
hk2) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mk2)                      in
  let pck2 :: Word64
pck2  = Word64
pbk2 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word8 -> Word64
forall a b. Widen a b => a -> b
widen ( (Word8
ok2 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak2)          Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mk2)                      in
  let sbk2 :: Word64
sbk2  = Word64
sak2 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word8 -> Word64
forall a b. Widen a b => a -> b
widen (Word8
t8k2 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
bk2)                                                       in

  let pak1 :: Word64
pak1  = Word64
pck2                                                                              in
  let sak1 :: Word64
sak1  = Word64
sbk2                                                                              in

  let hk1 :: Word8
hk1   = Word8
0xaa Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8 -> Word8
forall a. BitWise a => a -> a
comp (Word8
0xff Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak1)                                        in
  let fk1 :: Word8
fk1   = ((Word8
ck1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak1) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
hk1) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mask1                                   in
  let bk1 :: Word8
bk1   = ((Word64 -> Word8
forall a b. Narrow a b => a -> b
narrow Word64
pak1 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
fk1) Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Int8 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int8
wsz Int8 -> Int8 -> Int8
forall a. Num a => a -> a -> a
- Int8
1)) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
1                              in
  let mk1 :: Word8
mk1   = Word8
bk1  Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mask1                                                                    in
  let pbk1 :: Word64
pbk1  = Word64
pak1 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word8 -> Word64
forall a b. Widen a b => a -> b
widen (((Word8
ck1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak1) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.|. Word8
hk1) Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mk1)                      in
  let pck1 :: Word64
pck1  = Word64
pbk1 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word8 -> Word64
forall a b. Widen a b => a -> b
widen ( (Word8
ok1 Word8 -> Word64 -> Word8
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sak1)          Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
mk1)                      in
  let sbk1 :: Word64
sbk1  = Word64
sak1 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word8 -> Word64
forall a b. Widen a b => a -> b
widen (Word8
t8k1 Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. Word8
bk1)                                                       in

  let rrr :: Word64
rrr   = Word64
sbk1 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
pck1 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (((Word8 -> Word64
forall a b. Widen a b => a -> b
widen Word8
x Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
sbk1) Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. ((Word64
pck1 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
1) Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. Word64
1)) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.<. Word64
1)  in

  Word64
rrr Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
p
{-# INLINE findUnmatchedCloseFar #-}