1/** 2 * @file libavcodec/huffman.c 3 * huffman tree builder and VLC generator 4 * Copyright (c) 2006 Konstantin Shishkov 5 * 6 * This file is part of FFmpeg. 7 * 8 * FFmpeg is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * FFmpeg is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with FFmpeg; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 */ 22 23#include "avcodec.h" 24#include "bitstream.h" 25#include "huffman.h" 26 27/* symbol for Huffman tree node */ 28#define HNODE -1 29 30 31static 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) 32{ 33 int s; 34 35 s = nodes[node].sym; 36 if(s != HNODE || (no_zero_count && !nodes[node].count)){ 37 bits[*pos] = pfx; 38 lens[*pos] = pl; 39 xlat[*pos] = s; 40 (*pos)++; 41 }else{ 42 pfx <<= 1; 43 pl++; 44 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, pos, 45 no_zero_count); 46 pfx |= 1; 47 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0+1, pfx, pl, pos, 48 no_zero_count); 49 } 50} 51 52static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags) 53{ 54 int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT); 55 uint32_t bits[256]; 56 int16_t lens[256]; 57 uint8_t xlat[256]; 58 int pos = 0; 59 60 get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, &pos, no_zero_count); 61 return init_vlc_sparse(vlc, 9, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0); 62} 63 64 65/** 66 * nodes size must be 2*nb_codes 67 * first nb_codes nodes.count must be set 68 */ 69int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, 70 Node *nodes, HuffCmp cmp, int flags) 71{ 72 int i, j; 73 int cur_node; 74 int64_t sum = 0; 75 76 for(i = 0; i < nb_codes; i++){ 77 nodes[i].sym = i; 78 nodes[i].n0 = -2; 79 sum += nodes[i].count; 80 } 81 82 if(sum >> 31) { 83 av_log(avctx, AV_LOG_ERROR, "Too high symbol frequencies. Tree construction is not possible\n"); 84 return -1; 85 } 86 qsort(nodes, nb_codes, sizeof(Node), cmp); 87 cur_node = nb_codes; 88 nodes[nb_codes*2-1].count = 0; 89 for(i = 0; i < nb_codes*2-1; i += 2){ 90 nodes[cur_node].sym = HNODE; 91 nodes[cur_node].count = nodes[i].count + nodes[i+1].count; 92 nodes[cur_node].n0 = i; 93 for(j = cur_node; j > 0; j--){ 94 if(nodes[j].count > nodes[j-1].count || 95 (nodes[j].count == nodes[j-1].count && 96 (!(flags & FF_HUFFMAN_FLAG_HNODE_FIRST) || 97 nodes[j].n0==j-1 || nodes[j].n0==j-2 || 98 (nodes[j].sym!=HNODE && nodes[j-1].sym!=HNODE)))) 99 break; 100 FFSWAP(Node, nodes[j], nodes[j-1]); 101 } 102 cur_node++; 103 } 104 if(build_huff_tree(vlc, nodes, nb_codes*2-2, flags) < 0){ 105 av_log(avctx, AV_LOG_ERROR, "Error building tree\n"); 106 return -1; 107 } 108 return 0; 109} 110