FFmpeg
huffman.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2006 Konstantin Shishkov
3  * Copyright (c) 2007 Loren Merritt
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 
22 /**
23  * @file
24  * huffman tree builder and VLC generator
25  */
26 
27 #include <stdint.h>
28 
29 #include "libavutil/qsort.h"
30 #include "libavutil/common.h"
31 
32 #include "avcodec.h"
33 #include "huffman.h"
34 #include "vlc.h"
35 
36 /* symbol for Huffman tree node */
37 #define HNODE -1
38 
39 typedef struct HeapElem {
40  uint64_t val;
41  int name;
42 } HeapElem;
43 
44 static void heap_sift(HeapElem *h, int root, int size)
45 {
46  while (root * 2 + 1 < size) {
47  int child = root * 2 + 1;
48  if (child < size - 1 && h[child].val > h[child+1].val)
49  child++;
50  if (h[root].val > h[child].val) {
51  FFSWAP(HeapElem, h[root], h[child]);
52  root = child;
53  } else
54  break;
55  }
56 }
57 
58 int ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats, int stats_size, int skip0)
59 {
60  HeapElem *h = av_malloc_array(sizeof(*h), stats_size);
61  int *up = av_malloc_array(sizeof(*up) * 2, stats_size);
62  uint8_t *len = av_malloc_array(sizeof(*len) * 2, stats_size);
63  uint16_t *map= av_malloc_array(sizeof(*map), stats_size);
64  int offset, i, next;
65  int size = 0;
66  int ret = 0;
67 
68  if (!h || !up || !len || !map) {
69  ret = AVERROR(ENOMEM);
70  goto end;
71  }
72 
73  for (i = 0; i<stats_size; i++) {
74  dst[i] = 255;
75  if (stats[i] || !skip0)
76  map[size++] = i;
77  }
78 
79  for (offset = 1; ; offset <<= 1) {
80  for (i=0; i < size; i++) {
81  h[i].name = i;
82  h[i].val = (stats[map[i]] << 14) + offset;
83  }
84  for (i = size / 2 - 1; i >= 0; i--)
85  heap_sift(h, i, size);
86 
87  for (next = size; next < size * 2 - 1; next++) {
88  // merge the two smallest entries, and put it back in the heap
89  uint64_t min1v = h[0].val;
90  up[h[0].name] = next;
91  h[0].val = INT64_MAX;
92  heap_sift(h, 0, size);
93  up[h[0].name] = next;
94  h[0].name = next;
95  h[0].val += min1v;
96  heap_sift(h, 0, size);
97  }
98 
99  len[2 * size - 2] = 0;
100  for (i = 2 * size - 3; i >= size; i--)
101  len[i] = len[up[i]] + 1;
102  for (i = 0; i < size; i++) {
103  dst[map[i]] = len[up[i]] + 1;
104  if (dst[map[i]] >= 32) break;
105  }
106  if (i==size) break;
107  }
108 end:
109  av_free(h);
110  av_free(up);
111  av_free(len);
112  av_free(map);
113  return ret;
114 }
115 
116 static void get_tree_codes(uint32_t *bits, int16_t *lens, uint8_t *xlat,
117  Node *nodes, int node,
118  uint32_t pfx, int pl, int *pos, int no_zero_count)
119 {
120  int s;
121 
122  s = nodes[node].sym;
123  if (s != HNODE || (no_zero_count && !nodes[node].count)) {
124  bits[*pos] = pfx;
125  lens[*pos] = pl;
126  xlat[*pos] = s;
127  (*pos)++;
128  } else {
129  pfx <<= 1;
130  pl++;
131  get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl,
132  pos, no_zero_count);
133  pfx |= 1;
134  get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0 + 1, pfx, pl,
135  pos, no_zero_count);
136  }
137 }
138 
139 static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits)
140 {
141  int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT);
142  uint32_t bits[256];
143  int16_t lens[256];
144  uint8_t xlat[256];
145  int pos = 0;
146 
147  get_tree_codes(bits, lens, xlat, nodes, head, 0, 0,
148  &pos, no_zero_count);
149  return ff_init_vlc_sparse(vlc, nb_bits, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0);
150 }
151 
152 
153 /**
154  * nodes size must be 2*nb_codes
155  * first nb_codes nodes.count must be set
156  */
157 int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, int nb_bits,
158  Node *nodes, HuffCmp cmp, int flags)
159 {
160  int i, j;
161  int cur_node;
162  int64_t sum = 0;
163 
164  for (i = 0; i < nb_codes; i++) {
165  nodes[i].sym = i;
166  nodes[i].n0 = -2;
167  sum += nodes[i].count;
168  }
169 
170  if (sum >> 31) {
171  av_log(avctx, AV_LOG_ERROR,
172  "Too high symbol frequencies. "
173  "Tree construction is not possible\n");
174  return -1;
175  }
176  AV_QSORT(nodes, nb_codes, Node, cmp);
177  cur_node = nb_codes;
178  nodes[nb_codes*2-1].count = 0;
179  for (i = 0; i < nb_codes * 2 - 1; i += 2) {
180  uint32_t cur_count = nodes[i].count + nodes[i+1].count;
181  // find correct place to insert new node, and
182  // make space for the new node while at it
183  for(j = cur_node; j > i + 2; j--){
184  if(cur_count > nodes[j-1].count ||
185  (cur_count == nodes[j-1].count &&
187  break;
188  nodes[j] = nodes[j - 1];
189  }
190  nodes[j].sym = HNODE;
191  nodes[j].count = cur_count;
192  nodes[j].n0 = i;
193  cur_node++;
194  }
195  if (build_huff_tree(vlc, nodes, nb_codes * 2 - 2, flags, nb_bits) < 0) {
196  av_log(avctx, AV_LOG_ERROR, "Error building tree\n");
197  return -1;
198  }
199  return 0;
200 }
child
AVS_FilterInfo AVS_Value child
Definition: avisynth_c.h:808
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
FFSWAP
#define FFSWAP(type, a, b)
Definition: common.h:99
Node
Definition: agm.c:913
stats
static void stats(AVPacket *const *in, int n_in, unsigned *_max, unsigned *_sum)
Definition: vp9_superframe_bsf.c:33
count
void INT64 INT64 count
Definition: avisynth_c.h:767
end
static av_cold int end(AVCodecContext *avctx)
Definition: avrndec.c:90
HeapElem::val
uint64_t val
Definition: huffman.c:40
FF_HUFFMAN_FLAG_ZERO_COUNT
#define FF_HUFFMAN_FLAG_ZERO_COUNT
Definition: huffman.h:39
heap_sift
static void heap_sift(HeapElem *h, int root, int size)
Definition: huffman.c:44
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
s
#define s(width, name)
Definition: cbs_vp9.c:257
bits
uint8_t bits
Definition: vp3data.h:202
build_huff_tree
static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits)
Definition: huffman.c:139
cmp
static av_always_inline int cmp(MpegEncContext *s, const int x, const int y, const int subx, const int suby, const int size, const int h, int ref_index, int src_index, me_cmp_func cmp_func, me_cmp_func chroma_cmp_func, const int flags)
compares a block (either a full macroblock or a partition thereof) against a proposed motion-compensa...
Definition: motion_est.c:260
HNODE
#define HNODE
Definition: huffman.c:37
HeapElem::name
int name
Definition: huffman.c:41
ff_huff_gen_len_table
int ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats, int stats_size, int skip0)
Definition: huffman.c:58
ff_init_vlc_sparse
int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes, const void *bits, int bits_wrap, int bits_size, const void *codes, int codes_wrap, int codes_size, const void *symbols, int symbols_wrap, int symbols_size, int flags)
Definition: bitstream.c:273
qsort.h
size
int size
Definition: twinvq_data.h:11134
val
const char const char void * val
Definition: avisynth_c.h:863
HeapElem
Definition: huffman.c:39
offset
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf offset
Definition: writing_filters.txt:86
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
AV_QSORT
#define AV_QSORT(p, num, type, cmp)
Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input t...
Definition: qsort.h:33
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:32
common.h
uint8_t
uint8_t
Definition: audio_convert.c:194
len
int len
Definition: vorbis_enc_data.h:452
avcodec.h
ret
ret
Definition: filter_design.txt:187
Node::n0
int16_t n0
Definition: huffman.h:34
HuffCmp
int(* HuffCmp)(const void *va, const void *vb)
Definition: huffman.h:42
AVCodecContext
main external API structure.
Definition: avcodec.h:1565
VLC
Definition: vlc.h:26
huffman.h
Node::sym
int16_t sym
Definition: huffman.h:33
map
const VDPAUPixFmtMap * map
Definition: hwcontext_vdpau.c:85
av_free
#define av_free(p)
Definition: tableprint_vlc.h:34
get_tree_codes
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)
Definition: huffman.c:116
vlc.h
flags
#define flags(name, subs,...)
Definition: cbs_av1.c:565
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:28
Node::count
uint32_t count
Definition: huffman.h:35
h
h
Definition: vp9dsp_template.c:2038
ff_huff_build_tree
int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, int nb_bits, Node *nodes, HuffCmp cmp, int flags)
nodes size must be 2*nb_codes first nb_codes nodes.count must be set
Definition: huffman.c:157
FF_HUFFMAN_FLAG_HNODE_FIRST
#define FF_HUFFMAN_FLAG_HNODE_FIRST
Definition: huffman.h:38