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