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 #if !defined(_huffdec_H) 19 # define _huffdec_H (1) 20 # include "huffman.h" 21 # include "bitpack.h" 22 23 24 25 typedef struct oc_huff_node oc_huff_node; 26 27 /*A node in the Huffman tree. 28 Instead of storing every branching in the tree, subtrees can be collapsed 29 into one node, with a table of size 1<<nbits pointing directly to its 30 descedents nbits levels down. 31 This allows more than one bit to be read at a time, and avoids following all 32 the intermediate branches with next to no increased code complexity once 33 the collapsed tree has been built. 34 We do _not_ require that a subtree be complete to be collapsed, but instead 35 store duplicate pointers in the table, and record the actual depth of the 36 node below its parent. 37 This tells us the number of bits to advance the stream after reaching it. 38 39 This turns out to be equivalent to the method described in \cite{Hash95}, 40 without the requirement that codewords be sorted by length. 41 If the codewords were sorted by length (so-called ``canonical-codes''), they 42 could be decoded much faster via either Lindell and Moffat's approach or 43 Hashemian's Condensed Huffman Code approach, the latter of which has an 44 extremely small memory footprint. 45 We can't use Choueka et al.'s finite state machine approach, which is 46 extremely fast, because we can't allow multiple symbols to be output at a 47 time; the codebook can and does change between symbols. 48 It also has very large memory requirements, which impairs cache coherency. 49 50 @ARTICLE{Hash95, 51 author="Reza Hashemian", 52 title="Memory Efficient and High-Speed Search {Huffman} Coding", 53 journal="{IEEE} Transactions on Communications", 54 volume=43, 55 number=10, 56 pages="2576--2581", 57 month=Oct, 58 year=1995 59 }*/ 60 struct oc_huff_node{ 61 /*The number of bits of the code needed to descend through this node. 62 0 indicates a leaf node. 63 Otherwise there are 1<<nbits nodes in the nodes table, which can be 64 indexed by reading nbits bits from the stream.*/ 65 unsigned char nbits; 66 /*The value of a token stored in a leaf node. 67 The value in non-leaf nodes is undefined.*/ 68 unsigned char token; 69 /*The depth of the current node, relative to its parent in the collapsed 70 tree. 71 This can be less than its parent's nbits value, in which case there are 72 1<<nbits-depth copies of this node in the table, and the bitstream should 73 only be advanced depth bits after reaching this node.*/ 74 unsigned char depth; 75 /*The table of child nodes. 76 The ACTUAL size of this array is 1<<nbits, despite what the declaration 77 below claims. 78 The exception is that for leaf nodes the size is 0.*/ 79 oc_huff_node *nodes[2]; 80 }; 81 82 83 84 int oc_huff_trees_unpack(oc_pack_buf *_opb, 85 oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]); 86 int oc_huff_trees_copy(oc_huff_node *_dst[TH_NHUFFMAN_TABLES], 87 const oc_huff_node *const _src[TH_NHUFFMAN_TABLES]); 88 void oc_huff_trees_clear(oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]); 89 int oc_huff_token_decode(oc_pack_buf *_opb,const oc_huff_node *_node); 90 91 92 #endif 93