Libav
|
00001 00023 #include "avcodec.h" 00024 #include "get_bits.h" 00025 #include "huffman.h" 00026 00027 /* symbol for Huffman tree node */ 00028 #define HNODE -1 00029 00030 00031 static void get_tree_codes(uint32_t *bits, int16_t *lens, uint8_t *xlat, Node *nodes, int node, uint32_t pfx, int pl, int *pos, int no_zero_count) 00032 { 00033 int s; 00034 00035 s = nodes[node].sym; 00036 if(s != HNODE || (no_zero_count && !nodes[node].count)){ 00037 bits[*pos] = pfx; 00038 lens[*pos] = pl; 00039 xlat[*pos] = s; 00040 (*pos)++; 00041 }else{ 00042 pfx <<= 1; 00043 pl++; 00044 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, pos, 00045 no_zero_count); 00046 pfx |= 1; 00047 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0+1, pfx, pl, pos, 00048 no_zero_count); 00049 } 00050 } 00051 00052 static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags) 00053 { 00054 int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT); 00055 uint32_t bits[256]; 00056 int16_t lens[256]; 00057 uint8_t xlat[256]; 00058 int pos = 0; 00059 00060 get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, &pos, no_zero_count); 00061 return init_vlc_sparse(vlc, 9, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0); 00062 } 00063 00064 00069 int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, 00070 Node *nodes, HuffCmp cmp, int flags) 00071 { 00072 int i, j; 00073 int cur_node; 00074 int64_t sum = 0; 00075 00076 for(i = 0; i < nb_codes; i++){ 00077 nodes[i].sym = i; 00078 nodes[i].n0 = -2; 00079 sum += nodes[i].count; 00080 } 00081 00082 if(sum >> 31) { 00083 av_log(avctx, AV_LOG_ERROR, "Too high symbol frequencies. Tree construction is not possible\n"); 00084 return -1; 00085 } 00086 qsort(nodes, nb_codes, sizeof(Node), cmp); 00087 cur_node = nb_codes; 00088 nodes[nb_codes*2-1].count = 0; 00089 for(i = 0; i < nb_codes*2-1; i += 2){ 00090 nodes[cur_node].sym = HNODE; 00091 nodes[cur_node].count = nodes[i].count + nodes[i+1].count; 00092 nodes[cur_node].n0 = i; 00093 for(j = cur_node; j > 0; j--){ 00094 if(nodes[j].count > nodes[j-1].count || 00095 (nodes[j].count == nodes[j-1].count && 00096 (!(flags & FF_HUFFMAN_FLAG_HNODE_FIRST) || 00097 nodes[j].n0==j-1 || nodes[j].n0==j-2 || 00098 (nodes[j].sym!=HNODE && nodes[j-1].sym!=HNODE)))) 00099 break; 00100 FFSWAP(Node, nodes[j], nodes[j-1]); 00101 } 00102 cur_node++; 00103 } 00104 if(build_huff_tree(vlc, nodes, nb_codes*2-2, flags) < 0){ 00105 av_log(avctx, AV_LOG_ERROR, "Error building tree\n"); 00106 return -1; 00107 } 00108 return 0; 00109 }