1 /********************************************************************
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. *
8 * THE Theora SOURCE CODE IS COPYRIGHT (C) 2002-2007 *
9 * by the Xiph.Org Foundation http://www.xiph.org/ *
11 ********************************************************************
16 ********************************************************************/
24 /*The ANSI offsetof macro is broken on some platforms (e.g., older DECs).*/
25 #define _ogg_offsetof(_type,_field)\
26 ((size_t)((char *)&((_type *)0)->_field-(char *)0))
28 /*The log_2 of the size of a lookup table is allowed to grow to relative to
29 the number of unique nodes it contains.
30 E.g., if OC_HUFF_SLUSH is 2, then at most 75% of the space in the tree is
31 wasted (each node will have an amortized cost of at most 20 bytes when using
33 Larger numbers can decode tokens with fewer read operations, while smaller
34 numbers may save more space (requiring as little as 8 bytes amortized per
35 node, though there will be more nodes).
37 32233473 read calls are required when no tree collapsing is done (100.0%).
38 19269269 read calls are required when OC_HUFF_SLUSH is 0 (59.8%).
39 11144969 read calls are required when OC_HUFF_SLUSH is 1 (34.6%).
40 10538563 read calls are required when OC_HUFF_SLUSH is 2 (32.7%).
41 10192578 read calls are required when OC_HUFF_SLUSH is 3 (31.6%).
42 Since a value of 1 gets us the vast majority of the speed-up with only a
43 small amount of wasted memory, this is what we use.*/
44 #define OC_HUFF_SLUSH (1)
47 /*Allocates a Huffman tree node that represents a subtree of depth _nbits.
48 _nbits: The depth of the subtree.
49 If this is 0, the node is a leaf node.
50 Otherwise 1<<_nbits pointers are allocated for children.
51 Return: The newly allocated and fully initialized Huffman tree node.*/
52 static oc_huff_node
*oc_huff_node_alloc(int _nbits
){
55 size
=_ogg_offsetof(oc_huff_node
,nodes
);
56 if(_nbits
>0)size
+=sizeof(oc_huff_node
*)*(1<<_nbits
);
57 ret
=_ogg_calloc(1,size
);
58 ret
->nbits
=(unsigned char)_nbits
;
62 /*Frees a Huffman tree node allocated with oc_huf_node_alloc.
63 _node: The node to free.
65 static void oc_huff_node_free(oc_huff_node
*_node
){
69 /*Frees the memory used by a Huffman tree.
70 _node: The Huffman tree to free.
72 static void oc_huff_tree_free(oc_huff_node
*_node
){
73 if(_node
==NULL
)return;
78 nchildren
=1<<_node
->nbits
;
79 for(i
=0;i
<nchildren
;i
=inext
){
80 inext
=i
+(_node
->nodes
[i
]!=NULL
?1<<_node
->nbits
-_node
->nodes
[i
]->depth
:1);
81 oc_huff_tree_free(_node
->nodes
[i
]);
84 oc_huff_node_free(_node
);
87 /*Unpacks a sub-tree from the given buffer.
88 _opb: The buffer to unpack from.
89 _binode: The location to store a pointer to the sub-tree in.
90 _depth: The current depth of the tree.
91 This is used to prevent infinite recursion.
92 Return: 0 on success, or a negative value on error.*/
93 static int oc_huff_tree_unpack(oggpack_buffer
*_opb
,
94 oc_huff_node
**_binode
,int _depth
){
97 /*Prevent infinite recursion.*/
98 if(++_depth
>32)return TH_EBADHEADER
;
99 if(theorapackB_read1(_opb
,&bits
)<0)return TH_EBADHEADER
;
100 /*Read an internal node:*/
103 binode
=oc_huff_node_alloc(1);
104 binode
->depth
=(unsigned char)(_depth
>1);
105 ret
=oc_huff_tree_unpack(_opb
,binode
->nodes
,_depth
);
106 if(ret
>=0)ret
=oc_huff_tree_unpack(_opb
,binode
->nodes
+1,_depth
);
108 oc_huff_tree_free(binode
);
113 /*Read a leaf node:*/
115 if(theorapackB_read(_opb
,OC_NDCT_TOKEN_BITS
,&bits
)<0)return TH_EBADHEADER
;
116 binode
=oc_huff_node_alloc(0);
117 binode
->depth
=(unsigned char)(_depth
>1);
118 binode
->token
=(unsigned char)bits
;
124 /*Finds the depth of shortest branch of the given sub-tree.
125 The tree must be binary.
126 _binode: The root of the given sub-tree.
127 _binode->nbits must be 0 or 1.
128 Return: The smallest depth of a leaf node in this sub-tree.
129 0 indicates this sub-tree is a leaf node.*/
130 static int oc_huff_tree_mindepth(oc_huff_node
*_binode
){
133 if(_binode
->nbits
==0)return 0;
134 depth0
=oc_huff_tree_mindepth(_binode
->nodes
[0]);
135 depth1
=oc_huff_tree_mindepth(_binode
->nodes
[1]);
136 return OC_MINI(depth0
,depth1
)+1;
139 /*Finds the number of internal nodes at a given depth, plus the number of
140 leaves at that depth or shallower.
141 The tree must be binary.
142 _binode: The root of the given sub-tree.
143 _binode->nbits must be 0 or 1.
144 Return: The number of entries that would be contained in a jump table of the
146 static int oc_huff_tree_occupancy(oc_huff_node
*_binode
,int _depth
){
147 if(_binode
->nbits
==0||_depth
<=0)return 1;
149 return oc_huff_tree_occupancy(_binode
->nodes
[0],_depth
-1)+
150 oc_huff_tree_occupancy(_binode
->nodes
[1],_depth
-1);
154 static oc_huff_node
*oc_huff_tree_collapse(oc_huff_node
*_binode
);
156 /*Fills the given nodes table with all the children in the sub-tree at the
158 The nodes in the sub-tree with a depth less than that stored in the table
160 The sub-tree must be binary and complete up until the given depth.
161 _nodes: The nodes table to fill.
162 _binode: The root of the sub-tree to fill it with.
163 _binode->nbits must be 0 or 1.
164 _level: The current level in the table.
165 0 indicates that the current node should be stored, regardless of
166 whether it is a leaf node or an internal node.
167 _depth: The depth of the nodes to fill the table with, relative to their
169 static void oc_huff_node_fill(oc_huff_node
**_nodes
,
170 oc_huff_node
*_binode
,int _level
,int _depth
){
171 if(_level
<=0||_binode
->nbits
==0){
173 _binode
->depth
=(unsigned char)(_depth
-_level
);
174 _nodes
[0]=oc_huff_tree_collapse(_binode
);
175 for(i
=1;i
<1<<_level
;i
++)_nodes
[i
]=_nodes
[0];
179 oc_huff_node_fill(_nodes
,_binode
->nodes
[0],_level
,_depth
);
180 oc_huff_node_fill(_nodes
+(1<<_level
),_binode
->nodes
[1],_level
,_depth
);
181 oc_huff_node_free(_binode
);
185 /*Finds the largest complete sub-tree rooted at the current node and collapses
186 it into a single node.
187 This procedure is then applied recursively to all the children of that node.
188 _binode: The root of the sub-tree to collapse.
189 _binode->nbits must be 0 or 1.
190 Return: The new root of the collapsed sub-tree.*/
191 static oc_huff_node
*oc_huff_tree_collapse(oc_huff_node
*_binode
){
197 depth
=mindepth
=oc_huff_tree_mindepth(_binode
);
198 occupancy
=1<<mindepth
;
200 loccupancy
=occupancy
;
201 occupancy
=oc_huff_tree_occupancy(_binode
,++depth
);
203 while(occupancy
>loccupancy
&&occupancy
>=1<<OC_MAXI(depth
-OC_HUFF_SLUSH
,0));
205 if(depth
<=1)return _binode
;
206 root
=oc_huff_node_alloc(depth
);
207 root
->depth
=_binode
->depth
;
208 oc_huff_node_fill(root
->nodes
,_binode
,depth
,depth
);
212 /*Makes a copy of the given Huffman tree.
213 _node: The Huffman tree to copy.
214 Return: The copy of the Huffman tree.*/
215 static oc_huff_node
*oc_huff_tree_copy(const oc_huff_node
*_node
){
217 ret
=oc_huff_node_alloc(_node
->nbits
);
218 ret
->depth
=_node
->depth
;
223 nchildren
=1<<_node
->nbits
;
224 for(i
=0;i
<nchildren
;){
225 ret
->nodes
[i
]=oc_huff_tree_copy(_node
->nodes
[i
]);
226 inext
=i
+(1<<_node
->nbits
-ret
->nodes
[i
]->depth
);
227 while(++i
<inext
)ret
->nodes
[i
]=ret
->nodes
[i
-1];
230 else ret
->token
=_node
->token
;
234 /*Unpacks a set of Huffman trees, and reduces them to a collapsed
236 _opb: The buffer to unpack the trees from.
237 _nodes: The table to fill with the Huffman trees.
238 Return: 0 on success, or a negative value on error.*/
239 int oc_huff_trees_unpack(oggpack_buffer
*_opb
,
240 oc_huff_node
*_nodes
[TH_NHUFFMAN_TABLES
]){
242 for(i
=0;i
<TH_NHUFFMAN_TABLES
;i
++){
244 ret
=oc_huff_tree_unpack(_opb
,_nodes
+i
,0);
246 _nodes
[i
]=oc_huff_tree_collapse(_nodes
[i
]);
251 /*Makes a copy of the given set of Huffman trees.
252 _dst: The array to store the copy in.
253 _src: The array of trees to copy.*/
254 void oc_huff_trees_copy(oc_huff_node
*_dst
[TH_NHUFFMAN_TABLES
],
255 const oc_huff_node
*const _src
[TH_NHUFFMAN_TABLES
]){
257 for(i
=0;i
<TH_NHUFFMAN_TABLES
;i
++)_dst
[i
]=oc_huff_tree_copy(_src
[i
]);
260 /*Frees the memory used by a set of Huffman trees.
261 _nodes: The array of trees to free.*/
262 void oc_huff_trees_clear(oc_huff_node
*_nodes
[TH_NHUFFMAN_TABLES
]){
264 for(i
=0;i
<TH_NHUFFMAN_TABLES
;i
++)oc_huff_tree_free(_nodes
[i
]);
267 /*Unpacks a single token using the given Huffman tree.
268 _opb: The buffer to unpack the token from.
269 _node: The tree to unpack the token with.
270 Return: The token value.*/
271 int oc_huff_token_decode(oggpack_buffer
*_opb
,const oc_huff_node
*_node
){
273 while(_node
->nbits
!=0){
274 theorapackB_look(_opb
,_node
->nbits
,&bits
);
275 _node
=_node
->nodes
[bits
];
276 theorapackB_adv(_opb
,_node
->depth
);