FFmpeg: libavcodec/huffman.c Source File

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/error.h"
30 #include "libavutil/log.h"
31 #include "libavutil/macros.h"
32 #include "libavutil/mem.h"
33 #include "libavutil/qsort.h"
34 
35 #include "huffman.h"
36 #include "vlc.h"
37 
38 /* symbol for Huffman tree node */
39  #define HNODE -1
40 
41  typedef struct HeapElem {
42  union {
43   uint64_t val;
44   uint16_t dummy; // exists solely to ensure alignof(HeapElem) >= alignof(uint16_t)
45  };
46   int name;
47 } HeapElem;
48 
49  static void heap_sift(HeapElem *h, int root, int size)
50 {
51  while (root * 2 + 1 < size) {
52  int child = root * 2 + 1;
53  if (child < size - 1 && h[child].val > h[child+1].val)
54  child++;
55  if (h[root].val > h[child].val) {
56  FFSWAP(HeapElem, h[root], h[child]);
57  root = child;
58  } else
59  break;
60  }
61 }
62 
63  int ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats, int stats_size, int skip0)
64 {
65  int *up;
66  uint16_t *map;
67  uint8_t *len;
68  HeapElem *h = av_malloc_array(stats_size,
69  sizeof(*h) + 2 * sizeof(up) + 2 * sizeof(len) + sizeof(map));
70  if (!h)
71  return AVERROR(ENOMEM);
72  up = (int*)(h + stats_size);
73  // map is suitably aligned because up uses an even number of elements
74  // and alignof(uint16_t) is either 1 or 2.
75  map = (uint16_t*)(up + 2 * stats_size);
76  len = (uint8_t*)(map + stats_size);
77 
78  int offset, i, next;
79  int size = 0;
80  int ret = 0;
81 
82  for (i = 0; i<stats_size; i++) {
83  dst[i] = 255;
84  if (stats[i] || !skip0)
85  map[size++] = i;
86  }
87 
88  for (offset = 1; ; offset <<= 1) {
89  for (i=0; i < size; i++) {
90  h[i].name = i;
91  h[i].val = (stats[map[i]] << 14) + offset;
92  }
93  for (i = size / 2 - 1; i >= 0; i--)
94  heap_sift(h, i, size);
95 
96  for (next = size; next < size * 2 - 1; next++) {
97  // merge the two smallest entries, and put it back in the heap
98  uint64_t min1v = h[0].val;
99  up[h[0].name] = next;
100  h[0].val = INT64_MAX;
101  heap_sift(h, 0, size);
102  up[h[0].name] = next;
103  h[0].name = next;
104  h[0].val += min1v;
105  heap_sift(h, 0, size);
106  }
107 
108  len[2 * size - 2] = 0;
109  for (i = 2 * size - 3; i >= size; i--)
110  len[i] = len[up[i]] + 1;
111  for (i = 0; i < size; i++) {
112  dst[map[i]] = len[up[i]] + 1;
113  if (dst[map[i]] >= 32) break;
114  }
115  if (i==size) break;
116  }
117  av_free(h);
118  return ret;
119 }
120 
121  static void get_tree_codes(int8_t *lens, uint8_t *xlat,
122  Node *nodes, int node, int pl, int *pos, int no_zero_count)
123 {
124  int s;
125 
126  s = nodes[node].sym;
127  if (s != HNODE || (no_zero_count && !nodes[node].count)) {
128  lens[*pos] = pl;
129  xlat[*pos] = s;
130  (*pos)++;
131  } else {
132  pl++;
133  get_tree_codes(lens, xlat, nodes, nodes[node].n0, pl,
134  pos, no_zero_count);
135  get_tree_codes(lens, xlat, nodes, nodes[node].n0 + 1, pl,
136  pos, no_zero_count);
137  }
138 }
139 
140  static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits, void *logctx)
141 {
142  int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT);
143  int8_t lens[256];
144  uint8_t xlat[256];
145  int pos = 0;
146 
147  get_tree_codes(lens, xlat, nodes, head, 0,
148  &pos, no_zero_count);
149  return ff_vlc_init_from_lengths(vlc, nb_bits, pos, lens, 1,
150  xlat, 1, 1, 0, 0, logctx);
151 }
152 
153 
154 /**
155  * nodes size must be 2*nb_codes
156  * first nb_codes nodes.count must be set
157  */
158  int ff_huff_build_tree(void *logctx, VLC *vlc, int nb_codes, int nb_bits,
159  Node *nodes, HuffCmp cmp, int flags)
160 {
161  int i, j;
162  int cur_node;
163  int64_t sum = 0;
164 
165  for (i = 0; i < nb_codes; i++) {
166  nodes[i].sym = i;
167  nodes[i].n0 = -2;
168  sum += nodes[i].count;
169  }
170 
171  if (sum >> 31) {
172  av_log(logctx, AV_LOG_ERROR,
173  "Too high symbol frequencies. "
174  "Tree construction is not possible\n");
175  return -1;
176  }
177  AV_QSORT(nodes, nb_codes, Node, cmp);
178  cur_node = nb_codes;
179  nodes[nb_codes*2-1].count = 0;
180  for (i = 0; i < nb_codes * 2 - 1; i += 2) {
181  uint32_t cur_count = nodes[i].count + nodes[i+1].count;
182  // find correct place to insert new node, and
183  // make space for the new node while at it
184  for(j = cur_node; j > i + 2; j--){
185  if(cur_count > nodes[j-1].count ||
186  (cur_count == nodes[j-1].count &&
187  !(flags & FF_HUFFMAN_FLAG_HNODE_FIRST)))
188  break;
189  nodes[j] = nodes[j - 1];
190  }
191  nodes[j].sym = HNODE;
192  nodes[j].count = cur_count;
193  nodes[j].n0 = i;
194  cur_node++;
195  }
196  if (build_huff_tree(vlc, nodes, nb_codes * 2 - 2, flags, nb_bits, logctx) < 0) {
197  av_log(logctx, AV_LOG_ERROR, "Error building tree\n");
198  return -1;
199  }
200  return 0;
201 }
flags
const SwsFlags flags[]
Definition: swscale.c:61
ff_vlc_init_from_lengths
int ff_vlc_init_from_lengths(VLC *vlc, int nb_bits, int nb_codes, const int8_t *lens, int lens_wrap, const void *symbols, int symbols_wrap, int symbols_size, int offset, int flags, void *logctx)
Build VLC decoding tables suitable for use with get_vlc2()
Definition: vlc.c:306
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
Node
Definition: agm.c:899
int64_t
long long int64_t
Definition: coverity.c:34
HeapElem::dummy
uint16_t dummy
Definition: huffman.c:44
HeapElem::val
uint64_t val
Definition: huffman.c:43
build_huff_tree
static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits, void *logctx)
Definition: huffman.c:140
FF_HUFFMAN_FLAG_ZERO_COUNT
#define FF_HUFFMAN_FLAG_ZERO_COUNT
Definition: huffman.h:40
macros.h
val
static double val(void *priv, double ch)
Definition: aeval.c:77
heap_sift
static void heap_sift(HeapElem *h, int root, int size)
Definition: huffman.c:49
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:210
s
#define s(width, name)
Definition: cbs_vp9.c:198
HNODE
#define HNODE
Definition: huffman.c:39
HeapElem::name
int name
Definition: huffman.c:46
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:63
stats
static void stats(AVPacket *const *in, int n_in, unsigned *_max, unsigned *_sum)
Definition: vp9_superframe.c:34
error.h
qsort.h
get_tree_codes
static void get_tree_codes(int8_t *lens, uint8_t *xlat, Node *nodes, int node, int pl, int *pos, int no_zero_count)
Definition: huffman.c:121
dst
uint8_t ptrdiff_t const uint8_t ptrdiff_t int intptr_t intptr_t int int16_t * dst
Definition: dsp.h:87
size
int size
Definition: twinvq_data.h:10344
cmp
static av_always_inline int cmp(MPVEncContext *const 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:263
HeapElem
Definition: huffman.c:41
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
log.h
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:256
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
len
int len
Definition: vorbis_enc_data.h:426
ret
ret
Definition: filter_design.txt:187
ff_huff_build_tree
int ff_huff_build_tree(void *logctx, 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:158
FFSWAP
#define FFSWAP(type, a, b)
Definition: macros.h:52
Node::n0
int16_t n0
Definition: huffman.h:35
pos
unsigned int pos
Definition: spdifenc.c:414
HuffCmp
int(* HuffCmp)(const void *va, const void *vb)
Definition: huffman.h:42
VLC
Definition: vlc.h:50
huffman.h
Node::sym
int16_t sym
Definition: huffman.h:34
mem.h
map
const VDPAUPixFmtMap * map
Definition: hwcontext_vdpau.c:71
av_free
#define av_free(p)
Definition: tableprint_vlc.h:34
vlc.h
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:27
Node::count
uint32_t count
Definition: huffman.h:36
h
h
Definition: vp9dsp_template.c:2070
FF_HUFFMAN_FLAG_HNODE_FIRST
#define FF_HUFFMAN_FLAG_HNODE_FIRST
Definition: huffman.h:39
Generated on Sat Oct 18 2025 19:22:09 for FFmpeg by   doxygen 1.8.17

AltStyle によって変換されたページ (->オリジナル) /