git.sesse.net Git - ffmpeg/blob - libavcodec/huffman.c

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