1 /********************************************************************
2 * *
3 * THIS FILE IS PART OF THE OggTheora SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
5 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
7 * *
8 * THE Theora SOURCE CODE IS COPYRIGHT (C) 2002-2009 *
9 * by the Xiph.Org Foundation and contributors http://www.xiph.org/ *
10 * *
11 ********************************************************************
12
13 function:
14 last mod: $Id$
15
16 ********************************************************************/
17
18 #include <stdlib.h>
19 #include <string.h>
20 #include <ogg/ogg.h>
21 #include "huffdec.h"
22 #include "decint.h"
23
24
25 /*The ANSI offsetof macro is broken on some platforms (e.g., older DECs).*/
26 #define _ogg_offsetof(_type,_field)\
27 ((size_t)((char *)&((_type *)0)->_field-(char *)0))
28
29 /*The number of internal tokens associated with each of the spec tokens.*/
30 static const unsigned char OC_DCT_TOKEN_MAP_ENTRIES[TH_NDCT_TOKENS]={
31 1,1,1,4,8,1,1,8,1,1,1,1,1,2,2,2,2,4,8,2,2,2,4,2,2,2,2,2,8,2,4,8
32 };
33
34 /*The map from external spec-defined tokens to internal tokens.
35 This is constructed so that any extra bits read with the original token value
36 can be masked off the least significant bits of its internal token index.
37 In addition, all of the tokens which require additional extra bits are placed
38 at the start of the list, and grouped by type.
39 OC_DCT_REPEAT_RUN3_TOKEN is placed first, as it is an extra-special case, so
40 giving it index 0 may simplify comparisons on some architectures.
41 These requirements require some substantial reordering.*/
42 static const unsigned char OC_DCT_TOKEN_MAP[TH_NDCT_TOKENS]={
43 /*OC_DCT_EOB1_TOKEN (0 extra bits)*/
44 15,
45 /*OC_DCT_EOB2_TOKEN (0 extra bits)*/
46 16,
47 /*OC_DCT_EOB3_TOKEN (0 extra bits)*/
48 17,
49 /*OC_DCT_REPEAT_RUN0_TOKEN (2 extra bits)*/
50 88,
51 /*OC_DCT_REPEAT_RUN1_TOKEN (3 extra bits)*/
52 80,
53 /*OC_DCT_REPEAT_RUN2_TOKEN (4 extra bits)*/
54 1,
55 /*OC_DCT_REPEAT_RUN3_TOKEN (12 extra bits)*/
56 0,
57 /*OC_DCT_SHORT_ZRL_TOKEN (3 extra bits)*/
58 48,
59 /*OC_DCT_ZRL_TOKEN (6 extra bits)*/
60 14,
61 /*OC_ONE_TOKEN (0 extra bits)*/
62 56,
63 /*OC_MINUS_ONE_TOKEN (0 extra bits)*/
64 57,
65 /*OC_TWO_TOKEN (0 extra bits)*/
66 58,
67 /*OC_MINUS_TWO_TOKEN (0 extra bits)*/
68 59,
69 /*OC_DCT_VAL_CAT2 (1 extra bit)*/
70 60,
71 62,
72 64,
73 66,
74 /*OC_DCT_VAL_CAT3 (2 extra bits)*/
75 68,
76 /*OC_DCT_VAL_CAT4 (3 extra bits)*/
77 72,
78 /*OC_DCT_VAL_CAT5 (4 extra bits)*/
79 2,
80 /*OC_DCT_VAL_CAT6 (5 extra bits)*/
81 4,
82 /*OC_DCT_VAL_CAT7 (6 extra bits)*/
83 6,
84 /*OC_DCT_VAL_CAT8 (10 extra bits)*/
85 8,
86 /*OC_DCT_RUN_CAT1A (1 extra bit)*/
87 18,
88 20,
89 22,
90 24,
91 26,
92 /*OC_DCT_RUN_CAT1B (3 extra bits)*/
93 32,
94 /*OC_DCT_RUN_CAT1C (4 extra bits)*/
95 12,
96 /*OC_DCT_RUN_CAT2A (2 extra bits)*/
97 28,
98 /*OC_DCT_RUN_CAT2B (3 extra bits)*/
99 40
100 };
101
102 /*These three functions are really part of the bitpack.c module, but
103 they are only used here.
104 Declaring local static versions so they can be inlined saves considerable
105 function call overhead.*/
106
oc_pack_refill(oc_pack_buf * _b,int _bits)107 static oc_pb_window oc_pack_refill(oc_pack_buf *_b,int _bits){
108 const unsigned char *ptr;
109 const unsigned char *stop;
110 oc_pb_window window;
111 int available;
112 window=_b->window;
113 available=_b->bits;
114 ptr=_b->ptr;
115 stop=_b->stop;
116 /*This version of _refill() doesn't bother setting eof because we won't
117 check for it after we've started decoding DCT tokens.*/
118 if(ptr>=stop)available=OC_LOTS_OF_BITS;
119 while(available<=OC_PB_WINDOW_SIZE-8){
120 available+=8;
121 window|=(oc_pb_window)*ptr++<<OC_PB_WINDOW_SIZE-available;
122 if(ptr>=stop)available=OC_LOTS_OF_BITS;
123 }
124 _b->ptr=ptr;
125 if(_bits>available)window|=*ptr>>(available&7);
126 _b->bits=available;
127 return window;
128 }
129
130
131 /*Read in bits without advancing the bit pointer.
132 Here we assume 0<=_bits&&_bits<=32.*/
oc_pack_look(oc_pack_buf * _b,int _bits)133 static long oc_pack_look(oc_pack_buf *_b,int _bits){
134 oc_pb_window window;
135 int available;
136 long result;
137 window=_b->window;
138 available=_b->bits;
139 if(_bits==0)return 0;
140 if(_bits>available)_b->window=window=oc_pack_refill(_b,_bits);
141 result=window>>OC_PB_WINDOW_SIZE-_bits;
142 return result;
143 }
144
145 /*Advance the bit pointer.*/
oc_pack_adv(oc_pack_buf * _b,int _bits)146 static void oc_pack_adv(oc_pack_buf *_b,int _bits){
147 /*We ignore the special cases for _bits==0 and _bits==32 here, since they are
148 never used actually used.
149 OC_HUFF_SLUSH (defined below) would have to be at least 27 to actually read
150 32 bits in a single go, and would require a 32 GB lookup table (assuming
151 8 byte pointers, since 4 byte pointers couldn't fit such a table).*/
152 _b->window<<=_bits;
153 _b->bits-=_bits;
154 }
155
156
157 /*The log_2 of the size of a lookup table is allowed to grow to relative to
158 the number of unique nodes it contains.
159 E.g., if OC_HUFF_SLUSH is 2, then at most 75% of the space in the tree is
160 wasted (each node will have an amortized cost of at most 20 bytes when using
161 4-byte pointers).
162 Larger numbers can decode tokens with fewer read operations, while smaller
163 numbers may save more space (requiring as little as 8 bytes amortized per
164 node, though there will be more nodes).
165 With a sample file:
166 32233473 read calls are required when no tree collapsing is done (100.0%).
167 19269269 read calls are required when OC_HUFF_SLUSH is 0 (59.8%).
168 11144969 read calls are required when OC_HUFF_SLUSH is 1 (34.6%).
169 10538563 read calls are required when OC_HUFF_SLUSH is 2 (32.7%).
170 10192578 read calls are required when OC_HUFF_SLUSH is 3 (31.6%).
171 Since a value of 1 gets us the vast majority of the speed-up with only a
172 small amount of wasted memory, this is what we use.*/
173 #define OC_HUFF_SLUSH (1)
174
175
176 /*Determines the size in bytes of a Huffman tree node that represents a
177 subtree of depth _nbits.
178 _nbits: The depth of the subtree.
179 If this is 0, the node is a leaf node.
180 Otherwise 1<<_nbits pointers are allocated for children.
181 Return: The number of bytes required to store the node.*/
oc_huff_node_size(int _nbits)182 static size_t oc_huff_node_size(int _nbits){
183 size_t size;
184 size=_ogg_offsetof(oc_huff_node,nodes);
185 if(_nbits>0)size+=sizeof(oc_huff_node *)*(1<<_nbits);
186 return size;
187 }
188
oc_huff_node_init(char ** _storage,size_t _size,int _nbits)189 static oc_huff_node *oc_huff_node_init(char **_storage,size_t _size,int _nbits){
190 oc_huff_node *ret;
191 ret=(oc_huff_node *)*_storage;
192 ret->nbits=(unsigned char)_nbits;
193 (*_storage)+=_size;
194 return ret;
195 }
196
197
198 /*Determines the size in bytes of a Huffman tree.
199 _nbits: The depth of the subtree.
200 If this is 0, the node is a leaf node.
201 Otherwise storage for 1<<_nbits pointers are added for children.
202 Return: The number of bytes required to store the tree.*/
oc_huff_tree_size(const oc_huff_node * _node)203 static size_t oc_huff_tree_size(const oc_huff_node *_node){
204 size_t size;
205 size=oc_huff_node_size(_node->nbits);
206 if(_node->nbits){
207 int nchildren;
208 int i;
209 nchildren=1<<_node->nbits;
210 for(i=0;i<nchildren;i+=1<<_node->nbits-_node->nodes[i]->depth){
211 size+=oc_huff_tree_size(_node->nodes[i]);
212 }
213 }
214 return size;
215 }
216
217
218 /*Unpacks a sub-tree from the given buffer.
219 _opb: The buffer to unpack from.
220 _binodes: The nodes to store the sub-tree in.
221 _nbinodes: The number of nodes available for the sub-tree.
222 Return: 0 on success, or a negative value on error.*/
oc_huff_tree_unpack(oc_pack_buf * _opb,oc_huff_node * _binodes,int _nbinodes)223 static int oc_huff_tree_unpack(oc_pack_buf *_opb,
224 oc_huff_node *_binodes,int _nbinodes){
225 oc_huff_node *binode;
226 long bits;
227 int nused;
228 if(_nbinodes<1)return TH_EBADHEADER;
229 binode=_binodes;
230 nused=0;
231 bits=oc_pack_read1(_opb);
232 if(oc_pack_bytes_left(_opb)<0)return TH_EBADHEADER;
233 /*Read an internal node:*/
234 if(!bits){
235 int ret;
236 nused++;
237 binode->nbits=1;
238 binode->depth=1;
239 binode->nodes[0]=_binodes+nused;
240 ret=oc_huff_tree_unpack(_opb,_binodes+nused,_nbinodes-nused);
241 if(ret>=0){
242 nused+=ret;
243 binode->nodes[1]=_binodes+nused;
244 ret=oc_huff_tree_unpack(_opb,_binodes+nused,_nbinodes-nused);
245 }
246 if(ret<0)return ret;
247 nused+=ret;
248 }
249 /*Read a leaf node:*/
250 else{
251 int ntokens;
252 int token;
253 int i;
254 bits=oc_pack_read(_opb,OC_NDCT_TOKEN_BITS);
255 if(oc_pack_bytes_left(_opb)<0)return TH_EBADHEADER;
256 /*Find out how many internal tokens we translate this external token into.*/
257 ntokens=OC_DCT_TOKEN_MAP_ENTRIES[bits];
258 if(_nbinodes<2*ntokens-1)return TH_EBADHEADER;
259 /*Fill in a complete binary tree pointing to the internal tokens.*/
260 for(i=1;i<ntokens;i<<=1){
261 int j;
262 binode=_binodes+nused;
263 nused+=i;
264 for(j=0;j<i;j++){
265 binode[j].nbits=1;
266 binode[j].depth=1;
267 binode[j].nodes[0]=_binodes+nused+2*j;
268 binode[j].nodes[1]=_binodes+nused+2*j+1;
269 }
270 }
271 /*And now the leaf nodes with those tokens.*/
272 token=OC_DCT_TOKEN_MAP[bits];
273 for(i=0;i<ntokens;i++){
274 binode=_binodes+nused++;
275 binode->nbits=0;
276 binode->depth=1;
277 binode->token=token+i;
278 }
279 }
280 return nused;
281 }
282
283 /*Finds the depth of shortest branch of the given sub-tree.
284 The tree must be binary.
285 _binode: The root of the given sub-tree.
286 _binode->nbits must be 0 or 1.
287 Return: The smallest depth of a leaf node in this sub-tree.
288 0 indicates this sub-tree is a leaf node.*/
oc_huff_tree_mindepth(oc_huff_node * _binode)289 static int oc_huff_tree_mindepth(oc_huff_node *_binode){
290 int depth0;
291 int depth1;
292 if(_binode->nbits==0)return 0;
293 depth0=oc_huff_tree_mindepth(_binode->nodes[0]);
294 depth1=oc_huff_tree_mindepth(_binode->nodes[1]);
295 return OC_MINI(depth0,depth1)+1;
296 }
297
298 /*Finds the number of internal nodes at a given depth, plus the number of
299 leaves at that depth or shallower.
300 The tree must be binary.
301 _binode: The root of the given sub-tree.
302 _binode->nbits must be 0 or 1.
303 Return: The number of entries that would be contained in a jump table of the
304 given depth.*/
oc_huff_tree_occupancy(oc_huff_node * _binode,int _depth)305 static int oc_huff_tree_occupancy(oc_huff_node *_binode,int _depth){
306 if(_binode->nbits==0||_depth<=0)return 1;
307 else{
308 return oc_huff_tree_occupancy(_binode->nodes[0],_depth-1)+
309 oc_huff_tree_occupancy(_binode->nodes[1],_depth-1);
310 }
311 }
312
313 /*Makes a copy of the given Huffman tree.
314 _node: The Huffman tree to copy.
315 Return: The copy of the Huffman tree.*/
oc_huff_tree_copy(const oc_huff_node * _node,char ** _storage)316 static oc_huff_node *oc_huff_tree_copy(const oc_huff_node *_node,
317 char **_storage){
318 oc_huff_node *ret;
319 ret=oc_huff_node_init(_storage,oc_huff_node_size(_node->nbits),_node->nbits);
320 ret->depth=_node->depth;
321 if(_node->nbits){
322 int nchildren;
323 int i;
324 int inext;
325 nchildren=1<<_node->nbits;
326 for(i=0;i<nchildren;){
327 ret->nodes[i]=oc_huff_tree_copy(_node->nodes[i],_storage);
328 inext=i+(1<<_node->nbits-ret->nodes[i]->depth);
329 while(++i<inext)ret->nodes[i]=ret->nodes[i-1];
330 }
331 }
332 else ret->token=_node->token;
333 return ret;
334 }
335
oc_huff_tree_collapse_size(oc_huff_node * _binode,int _depth)336 static size_t oc_huff_tree_collapse_size(oc_huff_node *_binode,int _depth){
337 size_t size;
338 int mindepth;
339 int depth;
340 int loccupancy;
341 int occupancy;
342 if(_binode->nbits!=0&&_depth>0){
343 return oc_huff_tree_collapse_size(_binode->nodes[0],_depth-1)+
344 oc_huff_tree_collapse_size(_binode->nodes[1],_depth-1);
345 }
346 depth=mindepth=oc_huff_tree_mindepth(_binode);
347 occupancy=1<<mindepth;
348 do{
349 loccupancy=occupancy;
350 occupancy=oc_huff_tree_occupancy(_binode,++depth);
351 }
352 while(occupancy>loccupancy&&occupancy>=1<<OC_MAXI(depth-OC_HUFF_SLUSH,0));
353 depth--;
354 size=oc_huff_node_size(depth);
355 if(depth>0){
356 size+=oc_huff_tree_collapse_size(_binode->nodes[0],depth-1);
357 size+=oc_huff_tree_collapse_size(_binode->nodes[1],depth-1);
358 }
359 return size;
360 }
361
362 static oc_huff_node *oc_huff_tree_collapse(oc_huff_node *_binode,
363 char **_storage);
364
365 /*Fills the given nodes table with all the children in the sub-tree at the
366 given depth.
367 The nodes in the sub-tree with a depth less than that stored in the table
368 are freed.
369 The sub-tree must be binary and complete up until the given depth.
370 _nodes: The nodes table to fill.
371 _binode: The root of the sub-tree to fill it with.
372 _binode->nbits must be 0 or 1.
373 _level: The current level in the table.
374 0 indicates that the current node should be stored, regardless of
375 whether it is a leaf node or an internal node.
376 _depth: The depth of the nodes to fill the table with, relative to their
377 parent.*/
oc_huff_node_fill(oc_huff_node ** _nodes,oc_huff_node * _binode,int _level,int _depth,char ** _storage)378 static void oc_huff_node_fill(oc_huff_node **_nodes,
379 oc_huff_node *_binode,int _level,int _depth,char **_storage){
380 if(_level<=0||_binode->nbits==0){
381 int i;
382 _binode->depth=(unsigned char)(_depth-_level);
383 _nodes[0]=oc_huff_tree_collapse(_binode,_storage);
384 for(i=1;i<1<<_level;i++)_nodes[i]=_nodes[0];
385 }
386 else{
387 _level--;
388 oc_huff_node_fill(_nodes,_binode->nodes[0],_level,_depth,_storage);
389 _nodes+=1<<_level;
390 oc_huff_node_fill(_nodes,_binode->nodes[1],_level,_depth,_storage);
391 }
392 }
393
394 /*Finds the largest complete sub-tree rooted at the current node and collapses
395 it into a single node.
396 This procedure is then applied recursively to all the children of that node.
397 _binode: The root of the sub-tree to collapse.
398 _binode->nbits must be 0 or 1.
399 Return: The new root of the collapsed sub-tree.*/
oc_huff_tree_collapse(oc_huff_node * _binode,char ** _storage)400 static oc_huff_node *oc_huff_tree_collapse(oc_huff_node *_binode,
401 char **_storage){
402 oc_huff_node *root;
403 size_t size;
404 int mindepth;
405 int depth;
406 int loccupancy;
407 int occupancy;
408 depth=mindepth=oc_huff_tree_mindepth(_binode);
409 occupancy=1<<mindepth;
410 do{
411 loccupancy=occupancy;
412 occupancy=oc_huff_tree_occupancy(_binode,++depth);
413 }
414 while(occupancy>loccupancy&&occupancy>=1<<OC_MAXI(depth-OC_HUFF_SLUSH,0));
415 depth--;
416 if(depth<=1)return oc_huff_tree_copy(_binode,_storage);
417 size=oc_huff_node_size(depth);
418 root=oc_huff_node_init(_storage,size,depth);
419 root->depth=_binode->depth;
420 oc_huff_node_fill(root->nodes,_binode,depth,depth,_storage);
421 return root;
422 }
423
424 /*Unpacks a set of Huffman trees, and reduces them to a collapsed
425 representation.
426 _opb: The buffer to unpack the trees from.
427 _nodes: The table to fill with the Huffman trees.
428 Return: 0 on success, or a negative value on error.*/
oc_huff_trees_unpack(oc_pack_buf * _opb,oc_huff_node * _nodes[TH_NHUFFMAN_TABLES])429 int oc_huff_trees_unpack(oc_pack_buf *_opb,
430 oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]){
431 int i;
432 for(i=0;i<TH_NHUFFMAN_TABLES;i++){
433 oc_huff_node nodes[511];
434 char *storage;
435 size_t size;
436 int ret;
437 /*Unpack the full tree into a temporary buffer.*/
438 ret=oc_huff_tree_unpack(_opb,nodes,sizeof(nodes)/sizeof(*nodes));
439 if(ret<0)return ret;
440 /*Figure out how big the collapsed tree will be.*/
441 size=oc_huff_tree_collapse_size(nodes,0);
442 storage=(char *)_ogg_calloc(1,size);
443 if(storage==NULL)return TH_EFAULT;
444 /*And collapse it.*/
445 _nodes[i]=oc_huff_tree_collapse(nodes,&storage);
446 }
447 return 0;
448 }
449
450 /*Makes a copy of the given set of Huffman trees.
451 _dst: The array to store the copy in.
452 _src: The array of trees to copy.*/
oc_huff_trees_copy(oc_huff_node * _dst[TH_NHUFFMAN_TABLES],const oc_huff_node * const _src[TH_NHUFFMAN_TABLES])453 int oc_huff_trees_copy(oc_huff_node *_dst[TH_NHUFFMAN_TABLES],
454 const oc_huff_node *const _src[TH_NHUFFMAN_TABLES]){
455 int i;
456 for(i=0;i<TH_NHUFFMAN_TABLES;i++){
457 size_t size;
458 char *storage;
459 size=oc_huff_tree_size(_src[i]);
460 storage=(char *)_ogg_calloc(1,size);
461 if(storage==NULL){
462 while(i-->0)_ogg_free(_dst[i]);
463 return TH_EFAULT;
464 }
465 _dst[i]=oc_huff_tree_copy(_src[i],&storage);
466 }
467 return 0;
468 }
469
470 /*Frees the memory used by a set of Huffman trees.
471 _nodes: The array of trees to free.*/
oc_huff_trees_clear(oc_huff_node * _nodes[TH_NHUFFMAN_TABLES])472 void oc_huff_trees_clear(oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]){
473 int i;
474 for(i=0;i<TH_NHUFFMAN_TABLES;i++)_ogg_free(_nodes[i]);
475 }
476
477 /*Unpacks a single token using the given Huffman tree.
478 _opb: The buffer to unpack the token from.
479 _node: The tree to unpack the token with.
480 Return: The token value.*/
oc_huff_token_decode(oc_pack_buf * _opb,const oc_huff_node * _node)481 int oc_huff_token_decode(oc_pack_buf *_opb,const oc_huff_node *_node){
482 long bits;
483 while(_node->nbits!=0){
484 bits=oc_pack_look(_opb,_node->nbits);
485 _node=_node->nodes[bits];
486 oc_pack_adv(_opb,_node->depth);
487 }
488 return _node->token;
489 }
490