1{-# LANGUAGE BangPatterns, OverloadedStrings #-} 2 3module Network.HPACK.Huffman.Decode ( 4 -- * Huffman decoding 5 HuffmanDecoding 6 , decode 7 , decodeHuffman 8 ) where 9 10import Control.Exception (throwIO) 11import Data.Array (Array, listArray) 12import Data.Array.Base (unsafeAt) 13import qualified Data.ByteString as BS 14import Network.ByteOrder 15 16import Network.HPACK.Huffman.Bit 17import Network.HPACK.Huffman.Params 18import Network.HPACK.Huffman.Table 19import Network.HPACK.Huffman.Tree 20import Network.HPACK.Types (DecodeError(..)) 21 22---------------------------------------------------------------- 23 24-- | Huffman decoding. 25type HuffmanDecoding = ReadBuffer -> Int -> IO ByteString 26 27---------------------------------------------------------------- 28 29data Pin = EndOfString 30 | Forward {-# UNPACK #-} !Word8 -- node no. 31 | GoBack {-# UNPACK #-} !Word8 -- node no. 32 {-# UNPACK #-} !Word8 -- a decoded value 33 | GoBack2 {-# UNPACK #-} !Word8 -- node no. 34 {-# UNPACK #-} !Word8 -- a decoded value 35 {-# UNPACK #-} !Word8 -- a decoded value 36 deriving Show 37 38data WayStep = WayStep !(Maybe Int) !(Array Word8 Pin) 39type Way256 = Array Word8 WayStep 40 41next :: WayStep -> Word8 -> Pin 42next (WayStep _ a16) w = a16 `unsafeAt` fromIntegral w 43 44---------------------------------------------------------------- 45 46-- | Huffman decoding. 47decode :: Buffer -> BufferSize -> HuffmanDecoding 48decode buf siz rbuf len = do 49 wbuf <- newWriteBuffer buf siz 50 dec wbuf rbuf len 51 toByteString wbuf 52 53dec :: WriteBuffer -> ReadBuffer -> Int -> IO () 54dec wbuf rbuf len = go len (way256 `unsafeAt` 0) 55 where 56 go 0 way0 = case way0 of 57 WayStep Nothing _ -> throwIO IllegalEos 58 WayStep (Just i) _ 59 | i <= 8 -> return () 60 | otherwise -> throwIO TooLongEos 61 go !n !way0 = do 62 w <- read8 rbuf 63 way <- doit way0 w 64 go (n - 1) way 65 doit !way !w = case next way w of 66 EndOfString -> throwIO EosInTheMiddle 67 Forward n -> return $ way256 `unsafeAt` fromIntegral n 68 GoBack n v -> do 69 write8 wbuf v 70 return $ way256 `unsafeAt` fromIntegral n 71 GoBack2 n v1 v2 -> do 72 write8 wbuf v1 73 write8 wbuf v2 74 return $ way256 `unsafeAt` fromIntegral n 75 76decodeHuffman :: ByteString -> IO ByteString 77decodeHuffman bs = withWriteBuffer 4096 $ \wbuf -> 78 withReadBuffer bs $ \rbuf -> dec wbuf rbuf (BS.length bs) 79 80---------------------------------------------------------------- 81 82{-# NOINLINE way256 #-} 83way256 :: Way256 84way256 = construct $ toHTree huffmanTable 85 86construct :: HTree -> Way256 87construct decoder = listArray (0,255) $ map to16ways $ flatten decoder 88 where 89 to16ways x = WayStep ei a16 90 where 91 !ei = eosInfo x 92 !a16 = listArray (0,255) $ map (step decoder x Non) bits8s 93 94data Chara = Non 95 | One !Word8 96 | Two !Word8 !Word8 97 98inc :: Chara -> Word8 -> Chara 99inc Non w = One w 100inc (One v) w = Two v w 101inc _ _ = error "inc" 102 103step :: HTree -> HTree -> Chara -> [B] -> Pin 104step root (Tip _ v) x bss 105 | v == idxEos = EndOfString 106 | otherwise = let !w = fromIntegral v 107 !x' = inc x w 108 in step root root x' bss 109step _ (Bin _ n _ _) Non [] = Forward (fromIntegral n) 110step _ (Bin _ n _ _) (One w) [] = GoBack (fromIntegral n) w 111step _ (Bin _ n _ _) (Two w z) [] = GoBack2 (fromIntegral n) w z 112step root (Bin _ _ l _) mx (F:bs) = step root l mx bs 113step root (Bin _ _ _ r) mx (T:bs) = step root r mx bs 114 115bits8s :: [[B]] 116bits8s = [ 117 [F,F,F,F,F,F,F,F] 118 , [F,F,F,F,F,F,F,T] 119 , [F,F,F,F,F,F,T,F] 120 , [F,F,F,F,F,F,T,T] 121 , [F,F,F,F,F,T,F,F] 122 , [F,F,F,F,F,T,F,T] 123 , [F,F,F,F,F,T,T,F] 124 , [F,F,F,F,F,T,T,T] 125 , [F,F,F,F,T,F,F,F] 126 , [F,F,F,F,T,F,F,T] 127 , [F,F,F,F,T,F,T,F] 128 , [F,F,F,F,T,F,T,T] 129 , [F,F,F,F,T,T,F,F] 130 , [F,F,F,F,T,T,F,T] 131 , [F,F,F,F,T,T,T,F] 132 , [F,F,F,F,T,T,T,T] 133 , [F,F,F,T,F,F,F,F] 134 , [F,F,F,T,F,F,F,T] 135 , [F,F,F,T,F,F,T,F] 136 , [F,F,F,T,F,F,T,T] 137 , [F,F,F,T,F,T,F,F] 138 , [F,F,F,T,F,T,F,T] 139 , [F,F,F,T,F,T,T,F] 140 , [F,F,F,T,F,T,T,T] 141 , [F,F,F,T,T,F,F,F] 142 , [F,F,F,T,T,F,F,T] 143 , [F,F,F,T,T,F,T,F] 144 , [F,F,F,T,T,F,T,T] 145 , [F,F,F,T,T,T,F,F] 146 , [F,F,F,T,T,T,F,T] 147 , [F,F,F,T,T,T,T,F] 148 , [F,F,F,T,T,T,T,T] 149 , [F,F,T,F,F,F,F,F] 150 , [F,F,T,F,F,F,F,T] 151 , [F,F,T,F,F,F,T,F] 152 , [F,F,T,F,F,F,T,T] 153 , [F,F,T,F,F,T,F,F] 154 , [F,F,T,F,F,T,F,T] 155 , [F,F,T,F,F,T,T,F] 156 , [F,F,T,F,F,T,T,T] 157 , [F,F,T,F,T,F,F,F] 158 , [F,F,T,F,T,F,F,T] 159 , [F,F,T,F,T,F,T,F] 160 , [F,F,T,F,T,F,T,T] 161 , [F,F,T,F,T,T,F,F] 162 , [F,F,T,F,T,T,F,T] 163 , [F,F,T,F,T,T,T,F] 164 , [F,F,T,F,T,T,T,T] 165 , [F,F,T,T,F,F,F,F] 166 , [F,F,T,T,F,F,F,T] 167 , [F,F,T,T,F,F,T,F] 168 , [F,F,T,T,F,F,T,T] 169 , [F,F,T,T,F,T,F,F] 170 , [F,F,T,T,F,T,F,T] 171 , [F,F,T,T,F,T,T,F] 172 , [F,F,T,T,F,T,T,T] 173 , [F,F,T,T,T,F,F,F] 174 , [F,F,T,T,T,F,F,T] 175 , [F,F,T,T,T,F,T,F] 176 , [F,F,T,T,T,F,T,T] 177 , [F,F,T,T,T,T,F,F] 178 , [F,F,T,T,T,T,F,T] 179 , [F,F,T,T,T,T,T,F] 180 , [F,F,T,T,T,T,T,T] 181 , [F,T,F,F,F,F,F,F] 182 , [F,T,F,F,F,F,F,T] 183 , [F,T,F,F,F,F,T,F] 184 , [F,T,F,F,F,F,T,T] 185 , [F,T,F,F,F,T,F,F] 186 , [F,T,F,F,F,T,F,T] 187 , [F,T,F,F,F,T,T,F] 188 , [F,T,F,F,F,T,T,T] 189 , [F,T,F,F,T,F,F,F] 190 , [F,T,F,F,T,F,F,T] 191 , [F,T,F,F,T,F,T,F] 192 , [F,T,F,F,T,F,T,T] 193 , [F,T,F,F,T,T,F,F] 194 , [F,T,F,F,T,T,F,T] 195 , [F,T,F,F,T,T,T,F] 196 , [F,T,F,F,T,T,T,T] 197 , [F,T,F,T,F,F,F,F] 198 , [F,T,F,T,F,F,F,T] 199 , [F,T,F,T,F,F,T,F] 200 , [F,T,F,T,F,F,T,T] 201 , [F,T,F,T,F,T,F,F] 202 , [F,T,F,T,F,T,F,T] 203 , [F,T,F,T,F,T,T,F] 204 , [F,T,F,T,F,T,T,T] 205 , [F,T,F,T,T,F,F,F] 206 , [F,T,F,T,T,F,F,T] 207 , [F,T,F,T,T,F,T,F] 208 , [F,T,F,T,T,F,T,T] 209 , [F,T,F,T,T,T,F,F] 210 , [F,T,F,T,T,T,F,T] 211 , [F,T,F,T,T,T,T,F] 212 , [F,T,F,T,T,T,T,T] 213 , [F,T,T,F,F,F,F,F] 214 , [F,T,T,F,F,F,F,T] 215 , [F,T,T,F,F,F,T,F] 216 , [F,T,T,F,F,F,T,T] 217 , [F,T,T,F,F,T,F,F] 218 , [F,T,T,F,F,T,F,T] 219 , [F,T,T,F,F,T,T,F] 220 , [F,T,T,F,F,T,T,T] 221 , [F,T,T,F,T,F,F,F] 222 , [F,T,T,F,T,F,F,T] 223 , [F,T,T,F,T,F,T,F] 224 , [F,T,T,F,T,F,T,T] 225 , [F,T,T,F,T,T,F,F] 226 , [F,T,T,F,T,T,F,T] 227 , [F,T,T,F,T,T,T,F] 228 , [F,T,T,F,T,T,T,T] 229 , [F,T,T,T,F,F,F,F] 230 , [F,T,T,T,F,F,F,T] 231 , [F,T,T,T,F,F,T,F] 232 , [F,T,T,T,F,F,T,T] 233 , [F,T,T,T,F,T,F,F] 234 , [F,T,T,T,F,T,F,T] 235 , [F,T,T,T,F,T,T,F] 236 , [F,T,T,T,F,T,T,T] 237 , [F,T,T,T,T,F,F,F] 238 , [F,T,T,T,T,F,F,T] 239 , [F,T,T,T,T,F,T,F] 240 , [F,T,T,T,T,F,T,T] 241 , [F,T,T,T,T,T,F,F] 242 , [F,T,T,T,T,T,F,T] 243 , [F,T,T,T,T,T,T,F] 244 , [F,T,T,T,T,T,T,T] 245 , [T,F,F,F,F,F,F,F] 246 , [T,F,F,F,F,F,F,T] 247 , [T,F,F,F,F,F,T,F] 248 , [T,F,F,F,F,F,T,T] 249 , [T,F,F,F,F,T,F,F] 250 , [T,F,F,F,F,T,F,T] 251 , [T,F,F,F,F,T,T,F] 252 , [T,F,F,F,F,T,T,T] 253 , [T,F,F,F,T,F,F,F] 254 , [T,F,F,F,T,F,F,T] 255 , [T,F,F,F,T,F,T,F] 256 , [T,F,F,F,T,F,T,T] 257 , [T,F,F,F,T,T,F,F] 258 , [T,F,F,F,T,T,F,T] 259 , [T,F,F,F,T,T,T,F] 260 , [T,F,F,F,T,T,T,T] 261 , [T,F,F,T,F,F,F,F] 262 , [T,F,F,T,F,F,F,T] 263 , [T,F,F,T,F,F,T,F] 264 , [T,F,F,T,F,F,T,T] 265 , [T,F,F,T,F,T,F,F] 266 , [T,F,F,T,F,T,F,T] 267 , [T,F,F,T,F,T,T,F] 268 , [T,F,F,T,F,T,T,T] 269 , [T,F,F,T,T,F,F,F] 270 , [T,F,F,T,T,F,F,T] 271 , [T,F,F,T,T,F,T,F] 272 , [T,F,F,T,T,F,T,T] 273 , [T,F,F,T,T,T,F,F] 274 , [T,F,F,T,T,T,F,T] 275 , [T,F,F,T,T,T,T,F] 276 , [T,F,F,T,T,T,T,T] 277 , [T,F,T,F,F,F,F,F] 278 , [T,F,T,F,F,F,F,T] 279 , [T,F,T,F,F,F,T,F] 280 , [T,F,T,F,F,F,T,T] 281 , [T,F,T,F,F,T,F,F] 282 , [T,F,T,F,F,T,F,T] 283 , [T,F,T,F,F,T,T,F] 284 , [T,F,T,F,F,T,T,T] 285 , [T,F,T,F,T,F,F,F] 286 , [T,F,T,F,T,F,F,T] 287 , [T,F,T,F,T,F,T,F] 288 , [T,F,T,F,T,F,T,T] 289 , [T,F,T,F,T,T,F,F] 290 , [T,F,T,F,T,T,F,T] 291 , [T,F,T,F,T,T,T,F] 292 , [T,F,T,F,T,T,T,T] 293 , [T,F,T,T,F,F,F,F] 294 , [T,F,T,T,F,F,F,T] 295 , [T,F,T,T,F,F,T,F] 296 , [T,F,T,T,F,F,T,T] 297 , [T,F,T,T,F,T,F,F] 298 , [T,F,T,T,F,T,F,T] 299 , [T,F,T,T,F,T,T,F] 300 , [T,F,T,T,F,T,T,T] 301 , [T,F,T,T,T,F,F,F] 302 , [T,F,T,T,T,F,F,T] 303 , [T,F,T,T,T,F,T,F] 304 , [T,F,T,T,T,F,T,T] 305 , [T,F,T,T,T,T,F,F] 306 , [T,F,T,T,T,T,F,T] 307 , [T,F,T,T,T,T,T,F] 308 , [T,F,T,T,T,T,T,T] 309 , [T,T,F,F,F,F,F,F] 310 , [T,T,F,F,F,F,F,T] 311 , [T,T,F,F,F,F,T,F] 312 , [T,T,F,F,F,F,T,T] 313 , [T,T,F,F,F,T,F,F] 314 , [T,T,F,F,F,T,F,T] 315 , [T,T,F,F,F,T,T,F] 316 , [T,T,F,F,F,T,T,T] 317 , [T,T,F,F,T,F,F,F] 318 , [T,T,F,F,T,F,F,T] 319 , [T,T,F,F,T,F,T,F] 320 , [T,T,F,F,T,F,T,T] 321 , [T,T,F,F,T,T,F,F] 322 , [T,T,F,F,T,T,F,T] 323 , [T,T,F,F,T,T,T,F] 324 , [T,T,F,F,T,T,T,T] 325 , [T,T,F,T,F,F,F,F] 326 , [T,T,F,T,F,F,F,T] 327 , [T,T,F,T,F,F,T,F] 328 , [T,T,F,T,F,F,T,T] 329 , [T,T,F,T,F,T,F,F] 330 , [T,T,F,T,F,T,F,T] 331 , [T,T,F,T,F,T,T,F] 332 , [T,T,F,T,F,T,T,T] 333 , [T,T,F,T,T,F,F,F] 334 , [T,T,F,T,T,F,F,T] 335 , [T,T,F,T,T,F,T,F] 336 , [T,T,F,T,T,F,T,T] 337 , [T,T,F,T,T,T,F,F] 338 , [T,T,F,T,T,T,F,T] 339 , [T,T,F,T,T,T,T,F] 340 , [T,T,F,T,T,T,T,T] 341 , [T,T,T,F,F,F,F,F] 342 , [T,T,T,F,F,F,F,T] 343 , [T,T,T,F,F,F,T,F] 344 , [T,T,T,F,F,F,T,T] 345 , [T,T,T,F,F,T,F,F] 346 , [T,T,T,F,F,T,F,T] 347 , [T,T,T,F,F,T,T,F] 348 , [T,T,T,F,F,T,T,T] 349 , [T,T,T,F,T,F,F,F] 350 , [T,T,T,F,T,F,F,T] 351 , [T,T,T,F,T,F,T,F] 352 , [T,T,T,F,T,F,T,T] 353 , [T,T,T,F,T,T,F,F] 354 , [T,T,T,F,T,T,F,T] 355 , [T,T,T,F,T,T,T,F] 356 , [T,T,T,F,T,T,T,T] 357 , [T,T,T,T,F,F,F,F] 358 , [T,T,T,T,F,F,F,T] 359 , [T,T,T,T,F,F,T,F] 360 , [T,T,T,T,F,F,T,T] 361 , [T,T,T,T,F,T,F,F] 362 , [T,T,T,T,F,T,F,T] 363 , [T,T,T,T,F,T,T,F] 364 , [T,T,T,T,F,T,T,T] 365 , [T,T,T,T,T,F,F,F] 366 , [T,T,T,T,T,F,F,T] 367 , [T,T,T,T,T,F,T,F] 368 , [T,T,T,T,T,F,T,T] 369 , [T,T,T,T,T,T,F,F] 370 , [T,T,T,T,T,T,F,T] 371 , [T,T,T,T,T,T,T,F] 372 , [T,T,T,T,T,T,T,T] 373 ] 374 375