{-# LANGUAGE BangPatterns, OverloadedStrings #-}
module Network.HPACK.Huffman.Decode (
HuffmanDecoding
, decode
, decodeHuffman
) where
import Control.Exception (throwIO)
import Data.Array (Array, listArray)
import Data.Array.Base (unsafeAt)
import qualified Data.ByteString as BS
import Network.ByteOrder
import Network.HPACK.Huffman.Bit
import Network.HPACK.Huffman.Params
import Network.HPACK.Huffman.Table
import Network.HPACK.Huffman.Tree
import Network.HPACK.Types (DecodeError(..))
type HuffmanDecoding = ReadBuffer -> Int -> IO ByteString
data Pin = EndOfString
| Forward {-# UNPACK #-} !Word8
| GoBack {-# UNPACK #-} !Word8
{-# UNPACK #-} !Word8
| GoBack2 {-# UNPACK #-} !Word8
{-# UNPACK #-} !Word8
{-# UNPACK #-} !Word8
deriving Int -> Pin -> ShowS
[Pin] -> ShowS
Pin -> String
(Int -> Pin -> ShowS)
-> (Pin -> String) -> ([Pin] -> ShowS) -> Show Pin
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Pin] -> ShowS
$cshowList :: [Pin] -> ShowS
show :: Pin -> String
$cshow :: Pin -> String
showsPrec :: Int -> Pin -> ShowS
$cshowsPrec :: Int -> Pin -> ShowS
Show
data WayStep = WayStep !(Maybe Int) !(Array Word8 Pin)
type Way256 = Array Word8 WayStep
next :: WayStep -> Word8 -> Pin
next :: WayStep -> Word8 -> Pin
next (WayStep _ a16 :: Array Word8 Pin
a16) w :: Word8
w = Array Word8 Pin
a16 Array Word8 Pin -> Int -> Pin
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
w
decode :: Buffer -> BufferSize -> HuffmanDecoding
decode :: Buffer -> Int -> HuffmanDecoding
decode buf :: Buffer
buf siz :: Int
siz rbuf :: ReadBuffer
rbuf len :: Int
len = do
WriteBuffer
wbuf <- Buffer -> Int -> IO WriteBuffer
newWriteBuffer Buffer
buf Int
siz
WriteBuffer -> ReadBuffer -> Int -> IO ()
dec WriteBuffer
wbuf ReadBuffer
rbuf Int
len
WriteBuffer -> IO ByteString
toByteString WriteBuffer
wbuf
dec :: WriteBuffer -> ReadBuffer -> Int -> IO ()
dec :: WriteBuffer -> ReadBuffer -> Int -> IO ()
dec wbuf :: WriteBuffer
wbuf rbuf :: ReadBuffer
rbuf len :: Int
len = Int -> WayStep -> IO ()
forall t. (Eq t, Num t) => t -> WayStep -> IO ()
go Int
len (Way256
way256 Way256 -> Int -> WayStep
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` 0)
where
go :: t -> WayStep -> IO ()
go 0 way0 :: WayStep
way0 = case WayStep
way0 of
WayStep Nothing _ -> DecodeError -> IO ()
forall e a. Exception e => e -> IO a
throwIO DecodeError
IllegalEos
WayStep (Just i :: Int
i) _
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 8 -> () -> IO ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
| Bool
otherwise -> DecodeError -> IO ()
forall e a. Exception e => e -> IO a
throwIO DecodeError
TooLongEos
go !t
n !WayStep
way0 = do
Word8
w <- ReadBuffer -> IO Word8
forall a. Readable a => a -> IO Word8
read8 ReadBuffer
rbuf
WayStep
way <- WayStep -> Word8 -> IO WayStep
doit WayStep
way0 Word8
w
t -> WayStep -> IO ()
go (t
n t -> t -> t
forall a. Num a => a -> a -> a
- 1) WayStep
way
doit :: WayStep -> Word8 -> IO WayStep
doit !WayStep
way !Word8
w = case WayStep -> Word8 -> Pin
next WayStep
way Word8
w of
EndOfString -> DecodeError -> IO WayStep
forall e a. Exception e => e -> IO a
throwIO DecodeError
EosInTheMiddle
Forward n :: Word8
n -> WayStep -> IO WayStep
forall (m :: * -> *) a. Monad m => a -> m a
return (WayStep -> IO WayStep) -> WayStep -> IO WayStep
forall a b. (a -> b) -> a -> b
$ Way256
way256 Way256 -> Int -> WayStep
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n
GoBack n :: Word8
n v :: Word8
v -> do
WriteBuffer -> Word8 -> IO ()
write8 WriteBuffer
wbuf Word8
v
WayStep -> IO WayStep
forall (m :: * -> *) a. Monad m => a -> m a
return (WayStep -> IO WayStep) -> WayStep -> IO WayStep
forall a b. (a -> b) -> a -> b
$ Way256
way256 Way256 -> Int -> WayStep
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n
GoBack2 n :: Word8
n v1 :: Word8
v1 v2 :: Word8
v2 -> do
WriteBuffer -> Word8 -> IO ()
write8 WriteBuffer
wbuf Word8
v1
WriteBuffer -> Word8 -> IO ()
write8 WriteBuffer
wbuf Word8
v2
WayStep -> IO WayStep
forall (m :: * -> *) a. Monad m => a -> m a
return (WayStep -> IO WayStep) -> WayStep -> IO WayStep
forall a b. (a -> b) -> a -> b
$ Way256
way256 Way256 -> Int -> WayStep
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
n
decodeHuffman :: ByteString -> IO ByteString
decodeHuffman :: ByteString -> IO ByteString
decodeHuffman bs :: ByteString
bs = Int -> (WriteBuffer -> IO ()) -> IO ByteString
withWriteBuffer 4096 ((WriteBuffer -> IO ()) -> IO ByteString)
-> (WriteBuffer -> IO ()) -> IO ByteString
forall a b. (a -> b) -> a -> b
$ \wbuf :: WriteBuffer
wbuf ->
ByteString -> (ReadBuffer -> IO ()) -> IO ()
forall a. ByteString -> (ReadBuffer -> IO a) -> IO a
withReadBuffer ByteString
bs ((ReadBuffer -> IO ()) -> IO ()) -> (ReadBuffer -> IO ()) -> IO ()
forall a b. (a -> b) -> a -> b
$ \rbuf :: ReadBuffer
rbuf -> WriteBuffer -> ReadBuffer -> Int -> IO ()
dec WriteBuffer
wbuf ReadBuffer
rbuf (ByteString -> Int
BS.length ByteString
bs)
{-# NOINLINE way256 #-}
way256 :: Way256
way256 :: Way256
way256 = HTree -> Way256
construct (HTree -> Way256) -> HTree -> Way256
forall a b. (a -> b) -> a -> b
$ [Bits] -> HTree
toHTree [Bits]
huffmanTable
construct :: HTree -> Way256
construct :: HTree -> Way256
construct decoder :: HTree
decoder = (Word8, Word8) -> [WayStep] -> Way256
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (0,255) ([WayStep] -> Way256) -> [WayStep] -> Way256
forall a b. (a -> b) -> a -> b
$ (HTree -> WayStep) -> [HTree] -> [WayStep]
forall a b. (a -> b) -> [a] -> [b]
map HTree -> WayStep
to16ways ([HTree] -> [WayStep]) -> [HTree] -> [WayStep]
forall a b. (a -> b) -> a -> b
$ HTree -> [HTree]
flatten HTree
decoder
where
to16ways :: HTree -> WayStep
to16ways x :: HTree
x = Maybe Int -> Array Word8 Pin -> WayStep
WayStep Maybe Int
ei Array Word8 Pin
a16
where
!ei :: Maybe Int
ei = HTree -> Maybe Int
eosInfo HTree
x
!a16 :: Array Word8 Pin
a16 = (Word8, Word8) -> [Pin] -> Array Word8 Pin
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (0,255) ([Pin] -> Array Word8 Pin) -> [Pin] -> Array Word8 Pin
forall a b. (a -> b) -> a -> b
$ (Bits -> Pin) -> [Bits] -> [Pin]
forall a b. (a -> b) -> [a] -> [b]
map (HTree -> HTree -> Chara -> Bits -> Pin
step HTree
decoder HTree
x Chara
Non) [Bits]
bits8s
data Chara = Non
| One !Word8
| Two !Word8 !Word8
inc :: Chara -> Word8 -> Chara
inc :: Chara -> Word8 -> Chara
inc Non w :: Word8
w = Word8 -> Chara
One Word8
w
inc (One v :: Word8
v) w :: Word8
w = Word8 -> Word8 -> Chara
Two Word8
v Word8
w
inc _ _ = String -> Chara
forall a. HasCallStack => String -> a
error "inc"
step :: HTree -> HTree -> Chara -> [B] -> Pin
step :: HTree -> HTree -> Chara -> Bits -> Pin
step root :: HTree
root (Tip _ v :: Int
v) x :: Chara
x bss :: Bits
bss
| Int
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
idxEos = Pin
EndOfString
| Bool
otherwise = let !w :: Word8
w = Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
v
!x' :: Chara
x' = Chara -> Word8 -> Chara
inc Chara
x Word8
w
in HTree -> HTree -> Chara -> Bits -> Pin
step HTree
root HTree
root Chara
x' Bits
bss
step _ (Bin _ n :: Int
n _ _) Non [] = Word8 -> Pin
Forward (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)
step _ (Bin _ n :: Int
n _ _) (One w :: Word8
w) [] = Word8 -> Word8 -> Pin
GoBack (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n) Word8
w
step _ (Bin _ n :: Int
n _ _) (Two w :: Word8
w z :: Word8
z) [] = Word8 -> Word8 -> Word8 -> Pin
GoBack2 (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n) Word8
w Word8
z
step root :: HTree
root (Bin _ _ l :: HTree
l _) mx :: Chara
mx (F:bs :: Bits
bs) = HTree -> HTree -> Chara -> Bits -> Pin
step HTree
root HTree
l Chara
mx Bits
bs
step root :: HTree
root (Bin _ _ _ r :: HTree
r) mx :: Chara
mx (T:bs :: Bits
bs) = HTree -> HTree -> Chara -> Bits -> Pin
step HTree
root HTree
r Chara
mx Bits
bs
bits8s :: [[B]]
bits8s :: [Bits]
bits8s = [
[B
F,B
F,B
F,B
F,B
F,B
F,B
F,B
F]
, [B
F,B
F,B
F,B
F,B
F,B
F,B
F,B
T]
, [B
F,B
F,B
F,B
F,B
F,B
F,B
T,B
F]
, [B
F,B
F,B
F,B
F,B
F,B
F,B
T,B
T]
, [B
F,B
F,B
F,B
F,B
F,B
T,B
F,B
F]
, [B
F,B
F,B
F,B
F,B
F,B
T,B
F,B
T]
, [B
F,B
F,B
F,B
F,B
F,B
T,B
T,B
F]
, [B
F,B
F,B
F,B
F,B
F,B
T,B
T,B
T]
, [B
F,B
F,B
F,B
F,B
T,B
F,B
F,B
F]
, [B
F,B
F,B
F,B
F,B
T,B
F,B
F,B
T]
, [B
F,B
F,B
F,B
F,B
T,B
F,B
T,B
F]
, [B
F,B
F,B
F,B
F,B
T,B
F,B
T,B
T]
, [B
F,B
F,B
F,B
F,B
T,B
T,B
F,B
F]
, [B
F,B
F,B
F,B
F,B
T,B
T,B
F,B
T]
, [B
F,B
F,B
F,B
F,B
T,B
T,B
T,B
F]
, [B
F,B
F,B
F,B
F,B
T,B
T,B
T,B
T]
, [B
F,B
F,B
F,B
T,B
F,B
F,B
F,B
F]
, [B
F,B
F,B
F,B
T,B
F,B
F,B
F,B
T]
, [B
F,B
F,B
F,B
T,B
F,B
F,B
T,B
F]
, [B
F,B
F,B
F,B
T,B
F,B
F,B
T,B
T]
, [B
F,B
F,B
F,B
T,B
F,B
T,B
F,B
F]
, [B
F,B
F,B
F,B
T,B
F,B
T,B
F,B
T]
, [B
F,B
F,B
F,B
T,B
F,B
T,B
T,B
F]
, [B
F,B
F,B
F,B
T,B
F,B
T,B
T,B
T]
, [B
F,B
F,B
F,B
T,B
T,B
F,B
F,B
F]
, [B
F,B
F,B
F,B
T,B
T,B
F,B
F,B
T]
, [B
F,B
F,B
F,B
T,B
T,B
F,B
T,B
F]
, [B
F,B
F,B
F,B
T,B
T,B
F,B
T,B
T]
, [B
F,B
F,B
F,B
T,B
T,B
T,B
F,B
F]
, [B
F,B
F,B
F,B
T,B
T,B
T,B
F,B
T]
, [B
F,B
F,B
F,B
T,B
T,B
T,B
T,B
F]
, [B
F,B
F,B
F,B
T,B
T,B
T,B
T,B
T]
, [B
F,B
F,B
T,B
F,B
F,B
F,B
F,B
F]
, [B
F,B
F,B
T,B
F,B
F,B
F,B
F,B
T]
, [B
F,B
F,B
T,B
F,B
F,B
F,B
T,B
F]
, [B
F,B
F,B
T,B
F,B
F,B
F,B
T,B
T]
, [B
F,B
F,B
T,B
F,B
F,B
T,B
F,B
F]
, [B
F,B
F,B
T,B
F,B
F,B
T,B
F,B
T]
, [B
F,B
F,B
T,B
F,B
F,B
T,B
T,B
F]
, [B
F,B
F,B
T,B
F,B
F,B
T,B
T,B
T]
, [B
F,B
F,B
T,B
F,B
T,B
F,B
F,B
F]
, [B
F,B
F,B
T,B
F,B
T,B
F,B
F,B
T]
, [B
F,B
F,B
T,B
F,B
T,B
F,B
T,B
F]
, [B
F,B
F,B
T,B
F,B
T,B
F,B
T,B
T]
, [B
F,B
F,B
T,B
F,B
T,B
T,B
F,B
F]
, [B
F,B
F,B
T,B
F,B
T,B
T,B
F,B
T]
, [B
F,B
F,B
T,B
F,B
T,B
T,B
T,B
F]
, [B
F,B
F,B
T,B
F,B
T,B
T,B
T,B
T]
, [B
F,B
F,B
T,B
T,B
F,B
F,B
F,B
F]
, [B
F,B
F,B
T,B
T,B
F,B
F,B
F,B
T]
, [B
F,B
F,B
T,B
T,B
F,B
F,B
T,B
F]
, [B
F,B
F,B
T,B
T,B
F,B
F,B
T,B
T]
, [B
F,B
F,B
T,B
T,B
F,B
T,B
F,B
F]
, [B
F,B
F,B
T,B
T,B
F,B
T,B
F,B
T]
, [B
F,B
F,B
T,B
T,B
F,B
T,B
T,B
F]
, [B
F,B
F,B
T,B
T,B
F,B
T,B
T,B
T]
, [B
F,B
F,B
T,B
T,B
T,B
F,B
F,B
F]
, [B
F,B
F,B
T,B
T,B
T,B
F,B
F,B
T]
, [B
F,B
F,B
T,B
T,B
T,B
F,B
T,B
F]
, [B
F,B
F,B
T,B
T,B
T,B
F,B
T,B
T]
, [B
F,B
F,B
T,B
T,B
T,B
T,B
F,B
F]
, [B
F,B
F,B
T,B
T,B
T,B
T,B
F,B
T]
, [B
F,B
F,B
T,B
T,B
T,B
T,B
T,B
F]
, [B
F,B
F,B
T,B
T,B
T,B
T,B
T,B
T]
, [B
F,B
T,B
F,B
F,B
F,B
F,B
F,B
F]
, [B
F,B
T,B
F,B
F,B
F,B
F,B
F,B
T]
, [B
F,B
T,B
F,B
F,B
F,B
F,B
T,B
F]
, [B
F,B
T,B
F,B
F,B
F,B
F,B
T,B
T]
, [B
F,B
T,B
F,B
F,B
F,B
T,B
F,B
F]
, [B
F,B
T,B
F,B
F,B
F,B
T,B
F,B
T]
, [B
F,B
T,B
F,B
F,B
F,B
T,B
T,B
F]
, [B
F,B
T,B
F,B
F,B
F,B
T,B
T,B
T]
, [B
F,B
T,B
F,B
F,B
T,B
F,B
F,B
F]
, [B
F,B
T,B
F,B
F,B
T,B
F,B
F,B
T]
, [B
F,B
T,B
F,B
F,B
T,B
F,B
T,B
F]
, [B
F,B
T,B
F,B
F,B
T,B
F,B
T,B
T]
, [B
F,B
T,B
F,B
F,B
T,B
T,B
F,B
F]
, [B
F,B
T,B
F,B
F,B
T,B
T,B
F,B
T]
, [B
F,B
T,B
F,B
F,B
T,B
T,B
T,B
F]
, [B
F,B
T,B
F,B
F,B
T,B
T,B
T,B
T]
, [B
F,B
T,B
F,B
T,B
F,B
F,B
F,B
F]
, [B
F,B
T,B
F,B
T,B
F,B
F,B
F,B
T]
, [B
F,B
T,B
F,B
T,B
F,B
F,B
T,B
F]
, [B
F,B
T,B
F,B
T,B
F,B
F,B
T,B
T]
, [B
F,B
T,B
F,B
T,B
F,B
T,B
F,B
F]
, [B
F,B
T,B
F,B
T,B
F,B
T,B
F,B
T]
, [B
F,B
T,B
F,B
T,B
F,B
T,B
T,B
F]
, [B
F,B
T,B
F,B
T,B
F,B
T,B
T,B
T]
, [B
F,B
T,B
F,B
T,B
T,B
F,B
F,B
F]
, [B
F,B
T,B
F,B
T,B
T,B
F,B
F,B
T]
, [B
F,B
T,B
F,B
T,B
T,B
F,B
T,B
F]
, [B
F,B
T,B
F,B
T,B
T,B
F,B
T,B
T]
, [B
F,B
T,B
F,B
T,B
T,B
T,B
F,B
F]
, [B
F,B
T,B
F,B
T,B
T,B
T,B
F,B
T]
, [B
F,B
T,B
F,B
T,B
T,B
T,B
T,B
F]
, [B
F,B
T,B
F,B
T,B
T,B
T,B
T,B
T]
, [B
F,B
T,B
T,B
F,B
F,B
F,B
F,B
F]
, [B
F,B
T,B
T,B
F,B
F,B
F,B
F,B
T]
, [B
F,B
T,B
T,B
F,B
F,B
F,B
T,B
F]
, [B
F,B
T,B
T,B
F,B
F,B
F,B
T,B
T]
, [B
F,B
T,B
T,B
F,B
F,B
T,B
F,B
F]
, [B
F,B
T,B
T,B
F,B
F,B
T,B
F,B
T]
, [B
F,B
T,B
T,B
F,B
F,B
T,B
T,B
F]
, [B
F,B
T,B
T,B
F,B
F,B
T,B
T,B
T]
, [B
F,B
T,B
T,B
F,B
T,B
F,B
F,B
F]
, [B
F,B
T,B
T,B
F,B
T,B
F,B
F,B
T]
, [B
F,B
T,B
T,B
F,B
T,B
F,B
T,B
F]
, [B
F,B
T,B
T,B
F,B
T,B
F,B
T,B
T]
, [B
F,B
T,B
T,B
F,B
T,B
T,B
F,B
F]
, [B
F,B
T,B
T,B
F,B
T,B
T,B
F,B
T]
, [B
F,B
T,B
T,B
F,B
T,B
T,B
T,B
F]
, [B
F,B
T,B
T,B
F,B
T,B
T,B
T,B
T]
, [B
F,B
T,B
T,B
T,B
F,B
F,B
F,B
F]
, [B
F,B
T,B
T,B
T,B
F,B
F,B
F,B
T]
, [B
F,B
T,B
T,B
T,B
F,B
F,B
T,B
F]
, [B
F,B
T,B
T,B
T,B
F,B
F,B
T,B
T]
, [B
F,B
T,B
T,B
T,B
F,B
T,B
F,B
F]
, [B
F,B
T,B
T,B
T,B
F,B
T,B
F,B
T]
, [B
F,B
T,B
T,B
T,B
F,B
T,B
T,B
F]
, [B
F,B
T,B
T,B
T,B
F,B
T,B
T,B
T]
, [B
F,B
T,B
T,B
T,B
T,B
F,B
F,B
F]
, [B
F,B
T,B
T,B
T,B
T,B
F,B
F,B
T]
, [B
F,B
T,B
T,B
T,B
T,B
F,B
T,B
F]
, [B
F,B
T,B
T,B
T,B
T,B
F,B
T,B
T]
, [B
F,B
T,B
T,B
T,B
T,B
T,B
F,B
F]
, [B
F,B
T,B
T,B
T,B
T,B
T,B
F,B
T]
, [B
F,B
T,B
T,B
T,B
T,B
T,B
T,B
F]
, [B
F,B
T,B
T,B
T,B
T,B
T,B
T,B
T]
, [B
T,B
F,B
F,B
F,B
F,B
F,B
F,B
F]
, [B
T,B
F,B
F,B
F,B
F,B
F,B
F,B
T]
, [B
T,B
F,B
F,B
F,B
F,B
F,B
T,B
F]
, [B
T,B
F,B
F,B
F,B
F,B
F,B
T,B
T]
, [B
T,B
F,B
F,B
F,B
F,B
T,B
F,B
F]
, [B
T,B
F,B
F,B
F,B
F,B
T,B
F,B
T]
, [B
T,B
F,B
F,B
F,B
F,B
T,B
T,B
F]
, [B
T,B
F,B
F,B
F,B
F,B
T,B
T,B
T]
, [B
T,B
F,B
F,B
F,B
T,B
F,B
F,B
F]
, [B
T,B
F,B
F,B
F,B
T,B
F,B
F,B
T]
, [B
T,B
F,B
F,B
F,B
T,B
F,B
T,B
F]
, [B
T,B
F,B
F,B
F,B
T,B
F,B
T,B
T]
, [B
T,B
F,B
F,B
F,B
T,B
T,B
F,B
F]
, [B
T,B
F,B
F,B
F,B
T,B
T,B
F,B
T]
, [B
T,B
F,B
F,B
F,B
T,B
T,B
T,B
F]
, [B
T,B
F,B
F,B
F,B
T,B
T,B
T,B
T]
, [B
T,B
F,B
F,B
T,B
F,B
F,B
F,B
F]
, [B
T,B
F,B
F,B
T,B
F,B
F,B
F,B
T]
, [B
T,B
F,B
F,B
T,B
F,B
F,B
T,B
F]
, [B
T,B
F,B
F,B
T,B
F,B
F,B
T,B
T]
, [B
T,B
F,B
F,B
T,B
F,B
T,B
F,B
F]
, [B
T,B
F,B
F,B
T,B
F,B
T,B
F,B
T]
, [B
T,B
F,B
F,B
T,B
F,B
T,B
T,B
F]
, [B
T,B
F,B
F,B
T,B
F,B
T,B
T,B
T]
, [B
T,B
F,B
F,B
T,B
T,B
F,B
F,B
F]
, [B
T,B
F,B
F,B
T,B
T,B
F,B
F,B
T]
, [B
T,B
F,B
F,B
T,B
T,B
F,B
T,B
F]
, [B
T,B
F,B
F,B
T,B
T,B
F,B
T,B
T]
, [B
T,B
F,B
F,B
T,B
T,B
T,B
F,B
F]
, [B
T,B
F,B
F,B
T,B
T,B
T,B
F,B
T]
, [B
T,B
F,B
F,B
T,B
T,B
T,B
T,B
F]
, [B
T,B
F,B
F,B
T,B
T,B
T,B
T,B
T]
, [B
T,B
F,B
T,B
F,B
F,B
F,B
F,B
F]
, [B
T,B
F,B
T,B
F,B
F,B
F,B
F,B
T]
, [B
T,B
F,B
T,B
F,B
F,B
F,B
T,B
F]
, [B
T,B
F,B
T,B
F,B
F,B
F,B
T,B
T]
, [B
T,B
F,B
T,B
F,B
F,B
T,B
F,B
F]
, [B
T,B
F,B
T,B
F,B
F,B
T,B
F,B
T]
, [B
T,B
F,B
T,B
F,B
F,B
T,B
T,B
F]
, [B
T,B
F,B
T,B
F,B
F,B
T,B
T,B
T]
, [B
T,B
F,B
T,B
F,B
T,B
F,B
F,B
F]
, [B
T,B
F,B
T,B
F,B
T,B
F,B
F,B
T]
, [B
T,B
F,B
T,B
F,B
T,B
F,B
T,B
F]
, [B
T,B
F,B
T,B
F,B
T,B
F,B
T,B
T]
, [B
T,B
F,B
T,B
F,B
T,B
T,B
F,B
F]
, [B
T,B
F,B
T,B
F,B
T,B
T,B
F,B
T]
, [B
T,B
F,B
T,B
F,B
T,B
T,B
T,B
F]
, [B
T,B
F,B
T,B
F,B
T,B
T,B
T,B
T]
, [B
T,B
F,B
T,B
T,B
F,B
F,B
F,B
F]
, [B
T,B
F,B
T,B
T,B
F,B
F,B
F,B
T]
, [B
T,B
F,B
T,B
T,B
F,B
F,B
T,B
F]
, [B
T,B
F,B
T,B
T,B
F,B
F,B
T,B
T]
, [B
T,B
F,B
T,B
T,B
F,B
T,B
F,B
F]
, [B
T,B
F,B
T,B
T,B
F,B
T,B
F,B
T]
, [B
T,B
F,B
T,B
T,B
F,B
T,B
T,B
F]
, [B
T,B
F,B
T,B
T,B
F,B
T,B
T,B
T]
, [B
T,B
F,B
T,B
T,B
T,B
F,B
F,B
F]
, [B
T,B
F,B
T,B
T,B
T,B
F,B
F,B
T]
, [B
T,B
F,B
T,B
T,B
T,B
F,B
T,B
F]
, [B
T,B
F,B
T,B
T,B
T,B
F,B
T,B
T]
, [B
T,B
F,B
T,B
T,B
T,B
T,B
F,B
F]
, [B
T,B
F,B
T,B
T,B
T,B
T,B
F,B
T]
, [B
T,B
F,B
T,B
T,B
T,B
T,B
T,B
F]
, [B
T,B
F,B
T,B
T,B
T,B
T,B
T,B
T]
, [B
T,B
T,B
F,B
F,B
F,B
F,B
F,B
F]
, [B
T,B
T,B
F,B
F,B
F,B
F,B
F,B
T]
, [B
T,B
T,B
F,B
F,B
F,B
F,B
T,B
F]
, [B
T,B
T,B
F,B
F,B
F,B
F,B
T,B
T]
, [B
T,B
T,B
F,B
F,B
F,B
T,B
F,B
F]
, [B
T,B
T,B
F,B
F,B
F,B
T,B
F,B
T]
, [B
T,B
T,B
F,B
F,B
F,B
T,B
T,B
F]
, [B
T,B
T,B
F,B
F,B
F,B
T,B
T,B
T]
, [B
T,B
T,B
F,B
F,B
T,B
F,B
F,B
F]
, [B
T,B
T,B
F,B
F,B
T,B
F,B
F,B
T]
, [B
T,B
T,B
F,B
F,B
T,B
F,B
T,B
F]
, [B
T,B
T,B
F,B
F,B
T,B
F,B
T,B
T]
, [B
T,B
T,B
F,B
F,B
T,B
T,B
F,B
F]
, [B
T,B
T,B
F,B
F,B
T,B
T,B
F,B
T]
, [B
T,B
T,B
F,B
F,B
T,B
T,B
T,B
F]
, [B
T,B
T,B
F,B
F,B
T,B
T,B
T,B
T]
, [B
T,B
T,B
F,B
T,B
F,B
F,B
F,B
F]
, [B
T,B
T,B
F,B
T,B
F,B
F,B
F,B
T]
, [B
T,B
T,B
F,B
T,B
F,B
F,B
T,B
F]
, [B
T,B
T,B
F,B
T,B
F,B
F,B
T,B
T]
, [B
T,B
T,B
F,B
T,B
F,B
T,B
F,B
F]
, [B
T,B
T,B
F,B
T,B
F,B
T,B
F,B
T]
, [B
T,B
T,B
F,B
T,B
F,B
T,B
T,B
F]
, [B
T,B
T,B
F,B
T,B
F,B
T,B
T,B
T]
, [B
T,B
T,B
F,B
T,B
T,B
F,B
F,B
F]
, [B
T,B
T,B
F,B
T,B
T,B
F,B
F,B
T]
, [B
T,B
T,B
F,B
T,B
T,B
F,B
T,B
F]
, [B
T,B
T,B
F,B
T,B
T,B
F,B
T,B
T]
, [B
T,B
T,B
F,B
T,B
T,B
T,B
F,B
F]
, [B
T,B
T,B
F,B
T,B
T,B
T,B
F,B
T]
, [B
T,B
T,B
F,B
T,B
T,B
T,B
T,B
F]
, [B
T,B
T,B
F,B
T,B
T,B
T,B
T,B
T]
, [B
T,B
T,B
T,B
F,B
F,B
F,B
F,B
F]
, [B
T,B
T,B
T,B
F,B
F,B
F,B
F,B
T]
, [B
T,B
T,B
T,B
F,B
F,B
F,B
T,B
F]
, [B
T,B
T,B
T,B
F,B
F,B
F,B
T,B
T]
, [B
T,B
T,B
T,B
F,B
F,B
T,B
F,B
F]
, [B
T,B
T,B
T,B
F,B
F,B
T,B
F,B
T]
, [B
T,B
T,B
T,B
F,B
F,B
T,B
T,B
F]
, [B
T,B
T,B
T,B
F,B
F,B
T,B
T,B
T]
, [B
T,B
T,B
T,B
F,B
T,B
F,B
F,B
F]
, [B
T,B
T,B
T,B
F,B
T,B
F,B
F,B
T]
, [B
T,B
T,B
T,B
F,B
T,B
F,B
T,B
F]
, [B
T,B
T,B
T,B
F,B
T,B
F,B
T,B
T]
, [B
T,B
T,B
T,B
F,B
T,B
T,B
F,B
F]
, [B
T,B
T,B
T,B
F,B
T,B
T,B
F,B
T]
, [B
T,B
T,B
T,B
F,B
T,B
T,B
T,B
F]
, [B
T,B
T,B
T,B
F,B
T,B
T,B
T,B
T]
, [B
T,B
T,B
T,B
T,B
F,B
F,B
F,B
F]
, [B
T,B
T,B
T,B
T,B
F,B
F,B
F,B
T]
, [B
T,B
T,B
T,B
T,B
F,B
F,B
T,B
F]
, [B
T,B
T,B
T,B
T,B
F,B
F,B
T,B
T]
, [B
T,B
T,B
T,B
T,B
F,B
T,B
F,B
F]
, [B
T,B
T,B
T,B
T,B
F,B
T,B
F,B
T]
, [B
T,B
T,B
T,B
T,B
F,B
T,B
T,B
F]
, [B
T,B
T,B
T,B
T,B
F,B
T,B
T,B
T]
, [B
T,B
T,B
T,B
T,B
T,B
F,B
F,B
F]
, [B
T,B
T,B
T,B
T,B
T,B
F,B
F,B
T]
, [B
T,B
T,B
T,B
T,B
T,B
F,B
T,B
F]
, [B
T,B
T,B
T,B
T,B
T,B
F,B
T,B
T]
, [B
T,B
T,B
T,B
T,B
T,B
T,B
F,B
F]
, [B
T,B
T,B
T,B
T,B
T,B
T,B
F,B
T]
, [B
T,B
T,B
T,B
T,B
T,B
T,B
T,B
F]
, [B
T,B
T,B
T,B
T,B
T,B
T,B
T,B
T]
]