{-# 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 Maybe Int
_ Array Word8 Pin
a16) 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 Buffer
buf Int
siz ReadBuffer
rbuf 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 WriteBuffer
wbuf ReadBuffer
rbuf 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` Int
0)
  where
    go :: t -> WayStep -> IO ()
go t
0 WayStep
way0 = case WayStep
way0 of
        WayStep Maybe Int
Nothing  Array Word8 Pin
_ -> DecodeError -> IO ()
forall e a. Exception e => e -> IO a
throwIO DecodeError
IllegalEos
        WayStep (Just Int
i) Array Word8 Pin
_
          | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
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
- t
1) WayStep
way
    doit :: WayStep -> Word8 -> IO WayStep
doit !WayStep
way !Word8
w = case WayStep -> Word8 -> Pin
next WayStep
way Word8
w of
        Pin
EndOfString -> DecodeError -> IO WayStep
forall e a. Exception e => e -> IO a
throwIO DecodeError
EosInTheMiddle
        Forward 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  Word8
n 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 Word8
n Word8
v1 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 ByteString
bs = Int -> (WriteBuffer -> IO ()) -> IO ByteString
withWriteBuffer Int
4096 ((WriteBuffer -> IO ()) -> IO ByteString)
-> (WriteBuffer -> IO ()) -> IO ByteString
forall a b. (a -> b) -> a -> b
$ \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
$ \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 HTree
decoder = (Word8, Word8) -> [WayStep] -> Way256
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Word8
0,Word8
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 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 (Word8
0,Word8
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 Chara
Non Word8
w     = Word8 -> Chara
One Word8
w
inc (One Word8
v) Word8
w = Word8 -> Word8 -> Chara
Two Word8
v Word8
w
inc Chara
_       Word8
_ = String -> Chara
forall a. HasCallStack => String -> a
error String
"inc"

step :: HTree -> HTree -> Chara -> [B] -> Pin
step :: HTree -> HTree -> Chara -> Bits -> Pin
step HTree
root (Tip Maybe Int
_ Int
v)     Chara
x  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 HTree
_    (Bin Maybe Int
_ Int
n HTree
_ HTree
_) Chara
Non       [] = Word8 -> Pin
Forward (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)
step HTree
_    (Bin Maybe Int
_ Int
n HTree
_ HTree
_) (One Word8
w)   [] = Word8 -> Word8 -> Pin
GoBack (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n) Word8
w
step HTree
_    (Bin Maybe Int
_ Int
n HTree
_ HTree
_) (Two Word8
w 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 HTree
root (Bin Maybe Int
_ Int
_ HTree
l HTree
_) Chara
mx    (B
F:Bits
bs) = HTree -> HTree -> Chara -> Bits -> Pin
step HTree
root HTree
l Chara
mx Bits
bs
step HTree
root (Bin Maybe Int
_ Int
_ HTree
_ HTree
r) Chara
mx    (B
T: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]
  ]