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   uint64_t val;
43   int name;
44 } HeapElem;
45 
46  static void heap_sift(HeapElem *h, int root, int size)
47 {
48  while (root * 2 + 1 < size) {
49  int child = root * 2 + 1;
50  if (child < size - 1 && h[child].val > h[child+1].val)
51  child++;
52  if (h[root].val > h[child].val) {
53  FFSWAP(HeapElem, h[root], h[child]);
54  root = child;
55  } else
56  break;
57  }
58 }
59 
60  int ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats, int stats_size, int skip0)
61 {
62  HeapElem *h = av_malloc_array(sizeof(*h), stats_size);
63  int *up = av_malloc_array(sizeof(*up) * 2, stats_size);
64  uint8_t *len = av_malloc_array(sizeof(*len) * 2, stats_size);
65  uint16_t *map= av_malloc_array(sizeof(*map), stats_size);
66  int offset, i, next;
67  int size = 0;
68  int ret = 0;
69 
70  if (!h || !up || !len || !map) {
71  ret = AVERROR(ENOMEM);
72  goto end;
73  }
74 
75  for (i = 0; i<stats_size; i++) {
76  dst[i] = 255;
77  if (stats[i] || !skip0)
78  map[size++] = i;
79  }
80 
81  for (offset = 1; ; offset <<= 1) {
82  for (i=0; i < size; i++) {
83  h[i].name = i;
84  h[i].val = (stats[map[i]] << 14) + offset;
85  }
86  for (i = size / 2 - 1; i >= 0; i--)
87  heap_sift(h, i, size);
88 
89  for (next = size; next < size * 2 - 1; next++) {
90  // merge the two smallest entries, and put it back in the heap
91  uint64_t min1v = h[0].val;
92  up[h[0].name] = next;
93  h[0].val = INT64_MAX;
94  heap_sift(h, 0, size);
95  up[h[0].name] = next;
96  h[0].name = next;
97  h[0].val += min1v;
98  heap_sift(h, 0, size);
99  }
100 
101  len[2 * size - 2] = 0;
102  for (i = 2 * size - 3; i >= size; i--)
103  len[i] = len[up[i]] + 1;
104  for (i = 0; i < size; i++) {
105  dst[map[i]] = len[up[i]] + 1;
106  if (dst[map[i]] >= 32) break;
107  }
108  if (i==size) break;
109  }
110 end:
111  av_free(h);
112  av_free(up);
113  av_free(len);
114  av_free(map);
115  return ret;
116 }
117 
118  static void get_tree_codes(uint32_t *bits, int16_t *lens, uint8_t *xlat,
119  Node *nodes, int node,
120  uint32_t pfx, int pl, int *pos, int no_zero_count)
121 {
122  int s;
123 
124  s = nodes[node].sym;
125  if (s != HNODE || (no_zero_count && !nodes[node].count)) {
126  bits[*pos] = pfx;
127  lens[*pos] = pl;
128  xlat[*pos] = s;
129  (*pos)++;
130  } else {
131  pfx <<= 1;
132  pl++;
133  get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl,
134  pos, no_zero_count);
135  pfx |= 1;
136  get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0 + 1, pfx, pl,
137  pos, no_zero_count);
138  }
139 }
140 
141  static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits)
142 {
143  int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT);
144  uint32_t bits[256];
145  int16_t lens[256];
146  uint8_t xlat[256];
147  int pos = 0;
148 
149  get_tree_codes(bits, lens, xlat, nodes, head, 0, 0,
150  &pos, no_zero_count);
151  return ff_init_vlc_sparse(vlc, nb_bits, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0);
152 }
153 
154 
155 /**
156  * nodes size must be 2*nb_codes
157  * first nb_codes nodes.count must be set
158  */
159  int ff_huff_build_tree(void *logctx, VLC *vlc, int nb_codes, int nb_bits,
160  Node *nodes, HuffCmp cmp, int flags)
161 {
162  int i, j;
163  int cur_node;
164  int64_t sum = 0;
165 
166  for (i = 0; i < nb_codes; i++) {
167  nodes[i].sym = i;
168  nodes[i].n0 = -2;
169  sum += nodes[i].count;
170  }
171 
172  if (sum >> 31) {
173  av_log(logctx, AV_LOG_ERROR,
174  "Too high symbol frequencies. "
175  "Tree construction is not possible\n");
176  return -1;
177  }
178  AV_QSORT(nodes, nb_codes, Node, cmp);
179  cur_node = nb_codes;
180  nodes[nb_codes*2-1].count = 0;
181  for (i = 0; i < nb_codes * 2 - 1; i += 2) {
182  uint32_t cur_count = nodes[i].count + nodes[i+1].count;
183  // find correct place to insert new node, and
184  // make space for the new node while at it
185  for(j = cur_node; j > i + 2; j--){
186  if(cur_count > nodes[j-1].count ||
187  (cur_count == nodes[j-1].count &&
188  !(flags & FF_HUFFMAN_FLAG_HNODE_FIRST)))
189  break;
190  nodes[j] = nodes[j - 1];
191  }
192  nodes[j].sym = HNODE;
193  nodes[j].count = cur_count;
194  nodes[j].n0 = i;
195  cur_node++;
196  }
197  if (build_huff_tree(vlc, nodes, nb_codes * 2 - 2, flags, nb_bits) < 0) {
198  av_log(logctx, AV_LOG_ERROR, "Error building tree\n");
199  return -1;
200  }
201  return 0;
202 }
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:916
stats
static void stats(AVPacket *const *in, int n_in, unsigned *_max, unsigned *_sum)
Definition: vp9_superframe_bsf.c:34
HeapElem::val
uint64_t val
Definition: huffman.c:42
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:46
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:180
s
#define s(width, name)
Definition: cbs_vp9.c:256
bits
uint8_t bits
Definition: vp3data.h:141
build_huff_tree
static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits)
Definition: huffman.c:141
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:259
HNODE
#define HNODE
Definition: huffman.c:39
HeapElem::name
int name
Definition: huffman.c:43
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:60
error.h
qsort.h
size
int size
Definition: twinvq_data.h:10344
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:269
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
ff_init_vlc_sparse
int ff_init_vlc_sparse(VLC *vlc, 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: vlc.c:272
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:31
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:159
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:412
HuffCmp
int(* HuffCmp)(const void *va, const void *vb)
Definition: huffman.h:43
VLC
Definition: vlc.h:31
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:33
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:118
vlc.h
flags
#define flags(name, subs,...)
Definition: cbs_av1.c:561
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:2038
FF_HUFFMAN_FLAG_HNODE_FIRST
#define FF_HUFFMAN_FLAG_HNODE_FIRST
Definition: huffman.h:39
Generated on Wed Aug 24 2022 21:41:28 for FFmpeg by   doxygen 1.8.17

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