• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • File List
  • Globals

libavcodec/huffman.c

Go to the documentation of this file.
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 }

Generated on Fri Sep 16 2011 17:17:37 for FFmpeg by  doxygen 1.7.1