{-# LANGUAGE BangPatterns, OverloadedStrings #-}

module Network.HPACK.Huffman.Decode (
  -- * Huffman decoding
    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(..))

----------------------------------------------------------------

-- | Huffman decoding.
type HuffmanDecoding = ReadBuffer -> Int -> IO ByteString

----------------------------------------------------------------

data Pin = EndOfString
         | Forward {-# UNPACK #-} !Word8 -- node no.
         | GoBack  {-# UNPACK #-} !Word8 -- node no.
                   {-# UNPACK #-} !Word8 -- a decoded value
         | GoBack2 {-# UNPACK #-} !Word8 -- node no.
                   {-# UNPACK #-} !Word8 -- a decoded value
                   {-# UNPACK #-} !Word8 -- a decoded value
         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

----------------------------------------------------------------

-- | Huffman decoding.
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]
  ]