00001
00023 #include "avcodec.h"
00024 #include "bitstream.h"
00025 #include "huffman.h"
00026
00027
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)
00032 {
00033 int s;
00034
00035 s = nodes[node].sym;
00036 if(s != HNODE || !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 pfx |= 1;
00046 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0+1, pfx, pl, pos);
00047 }
00048 }
00049
00050 static int build_huff_tree(VLC *vlc, Node *nodes, int head)
00051 {
00052 uint32_t bits[256];
00053 int16_t lens[256];
00054 uint8_t xlat[256];
00055 int pos = 0;
00056
00057 get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, &pos);
00058 return init_vlc_sparse(vlc, 9, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0);
00059 }
00060
00061
00066 int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes,
00067 Node *nodes, huff_cmp_t cmp, int hnode_first)
00068 {
00069 int i, j;
00070 int cur_node;
00071 int64_t sum = 0;
00072
00073 for(i = 0; i < nb_codes; i++){
00074 nodes[i].sym = i;
00075 nodes[i].n0 = -2;
00076 sum += nodes[i].count;
00077 }
00078
00079 if(sum >> 31) {
00080 av_log(avctx, AV_LOG_ERROR, "Too high symbol frequencies. Tree construction is not possible\n");
00081 return -1;
00082 }
00083 qsort(nodes, nb_codes, sizeof(Node), cmp);
00084 cur_node = nb_codes;
00085 nodes[nb_codes*2-1].count = 0;
00086 for(i = 0; i < nb_codes*2-1; i += 2){
00087 nodes[cur_node].sym = HNODE;
00088 nodes[cur_node].count = nodes[i].count + nodes[i+1].count;
00089 nodes[cur_node].n0 = i;
00090 for(j = cur_node; j > 0; j--){
00091 if(nodes[j].count > nodes[j-1].count ||
00092 (nodes[j].count == nodes[j-1].count &&
00093 (!hnode_first || nodes[j].n0==j-1 || nodes[j].n0==j-2 ||
00094 (nodes[j].sym!=HNODE && nodes[j-1].sym!=HNODE))))
00095 break;
00096 FFSWAP(Node, nodes[j], nodes[j-1]);
00097 }
00098 cur_node++;
00099 }
00100 if(build_huff_tree(vlc, nodes, nb_codes*2-2) < 0){
00101 av_log(avctx, AV_LOG_ERROR, "Error building tree\n");
00102 return -1;
00103 }
00104 return 0;
00105 }