FFmpeg: libavcodec/vlc.c Source File

FFmpeg

[フレーム]

libavcodec

vlc.c

Go to the documentation of this file.

1 /*

2 * API for creating VLC trees

6 *

7 * This file is part of FFmpeg.

8 *

9 * FFmpeg is free software; you can redistribute it and/or

10 * modify it under the terms of the GNU Lesser General Public

11 * License as published by the Free Software Foundation; either

12 * version 2.1 of the License, or (at your option) any later version.

13 *

14 * FFmpeg is distributed in the hope that it will be useful,

15 * but WITHOUT ANY WARRANTY; without even the implied warranty of

16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

17 * Lesser General Public License for more details.

18 *

19 * You should have received a copy of the GNU Lesser General Public

20 * License along with FFmpeg; if not, write to the Free Software

21 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

22 */

24 #include <inttypes.h>

25 #include <stdint.h>

26 #include <stdlib.h>

27 #include <string.h>

29 #include "libavutil/attributes.h"

30 #include "libavutil/avassert.h"

31 #include "libavutil/error.h"

32 #include "libavutil/internal.h"

33 #include "libavutil/log.h"

34 #include "libavutil/macros.h"

35 #include "libavutil/mem.h"

36 #include "libavutil/qsort.h"

37 #include "libavutil/reverse.h"

38 #include "vlc.h"

40 #define GET_DATA(v, table, i, wrap, size) \

41 { \

42 const uint8_t *ptr = (const uint8_t *)table + i * wrap; \

43 switch(size) { \

44 case 1: \

45 v = *(const uint8_t *)ptr; \

46 break; \

47 case 2: \

48 v = *(const uint16_t *)ptr; \

49 break; \

50 case 4: \

51 default: \

52 av_assert1(size == 4); \

53 v = *(const uint32_t *)ptr; \

54 break; \

55 } \

56 }

59 static int alloc_table(VLC *vlc, int size, int use_static)

60 {

61 int index = vlc->table_size;

63 vlc->table_size += size;

64 if (vlc->table_size > vlc->table_allocated) {

65 if (use_static)

66 abort(); // cannot do anything, init_vlc() is used with too little memory

67 vlc->table_allocated += (1 << vlc->bits);

68 vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(*vlc->table));

69 if (!vlc->table) {

70 vlc->table_allocated = 0;

71 vlc->table_size = 0;

72 return AVERROR(ENOMEM);

73 }

74 memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(*vlc->table) << vlc->bits);

75 }

76 return index;

77 }

79 #define LOCALBUF_ELEMS 1500 // the maximum currently needed is 1296 by rv34

81 static av_always_inline uint32_t bitswap_32(uint32_t x)

82 {

83 return (uint32_t)ff_reverse[ x & 0xFF] << 24 |

84 (uint32_t)ff_reverse[(x >> 8) & 0xFF] << 16 |

85 (uint32_t)ff_reverse[(x >> 16) & 0xFF] << 8 |

86 (uint32_t)ff_reverse[ x >> 24];

87 }

89 typedef struct VLCcode {

90 uint8_t bits;

91 VLCBaseType symbol;

92 /** codeword, with the first bit-to-be-read in the msb

93 * (even if intended for a little-endian bitstream reader) */

94 uint32_t code;

95 } VLCcode;

97 static int vlc_common_init(VLC *vlc, int nb_bits, int nb_codes,

98 VLCcode **buf, int flags)

99 {

100 vlc->bits = nb_bits;

101 vlc->table_size = 0;

102 if (flags & INIT_VLC_USE_NEW_STATIC) {

103 av_assert0(nb_codes <= LOCALBUF_ELEMS);

104 } else {

105 vlc->table = NULL;

106 vlc->table_allocated = 0;

107 }

108 if (nb_codes > LOCALBUF_ELEMS) {

109 *buf = av_malloc_array(nb_codes, sizeof(VLCcode));

110 if (!*buf)

111 return AVERROR(ENOMEM);

112 }

113

114 return 0;

115 }

116

117 static int compare_vlcspec(const void *a, const void *b)

118 {

119 const VLCcode *sa = a, *sb = b;

120 return (sa->code >> 1) - (sb->code >> 1);

121 }

122

123 /**

124 * Build VLC decoding tables suitable for use with get_vlc().

125 *

126 * @param vlc the context to be initialized

127 *

128 * @param table_nb_bits max length of vlc codes to store directly in this table

129 * (Longer codes are delegated to subtables.)

130 *

131 * @param nb_codes number of elements in codes[]

132 *

133 * @param codes descriptions of the vlc codes

134 * These must be ordered such that codes going into the same subtable are contiguous.

135 * Sorting by VLCcode.code is sufficient, though not necessary.

136 */

137 static int build_table(VLC *vlc, int table_nb_bits, int nb_codes,

138 VLCcode *codes, int flags)

139 {

140 int table_size, table_index;

141 VLCElem *table;

142

143 if (table_nb_bits > 30)

144 return AVERROR(EINVAL);

145 table_size = 1 << table_nb_bits;

146 table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC);

147 ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size);

148 if (table_index < 0)

149 return table_index;

150 table = &vlc->table[table_index];

151

152 /* first pass: map codes and compute auxiliary table sizes */

153 for (int i = 0; i < nb_codes; i++) {

154 int n = codes[i].bits;

155 uint32_t code = codes[i].code;

156 int symbol = codes[i].symbol;

157 ff_dlog(NULL, "i=%d n=%d code=0x%"PRIx32"\n", i, n, code);

158 if (n <= table_nb_bits) {

159 /* no need to add another table */

160 int j = code >> (32 - table_nb_bits);

161 int nb = 1 << (table_nb_bits - n);

162 int inc = 1;

163

164 if (flags & INIT_VLC_OUTPUT_LE) {

165 j = bitswap_32(code);

166 inc = 1 << n;

167 }

168 for (int k = 0; k < nb; k++) {

169 int bits = table[j].len;

170 int oldsym = table[j].sym;

171 ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n);

172 if ((bits || oldsym) && (bits != n || oldsym != symbol)) {

173 av_log(NULL, AV_LOG_ERROR, "incorrect codes\n");

174 return AVERROR_INVALIDDATA;

175 }

176 table[j].len = n;

177 table[j].sym = symbol;

178 j += inc;

179 }

180 } else {

181 /* fill auxiliary table recursively */

182 uint32_t code_prefix;

183 int index, subtable_bits, j, k;

184

185 n -= table_nb_bits;

186 code_prefix = code >> (32 - table_nb_bits);

187 subtable_bits = n;

188 codes[i].bits = n;

189 codes[i].code = code << table_nb_bits;

190 for (k = i + 1; k < nb_codes; k++) {

191 n = codes[k].bits - table_nb_bits;

192 if (n <= 0)

193 break;

194 code = codes[k].code;

195 if (code >> (32 - table_nb_bits) != code_prefix)

196 break;

197 codes[k].bits = n;

198 codes[k].code = code << table_nb_bits;

199 subtable_bits = FFMAX(subtable_bits, n);

200 }

201 subtable_bits = FFMIN(subtable_bits, table_nb_bits);

202 j = (flags & INIT_VLC_OUTPUT_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix;

203 table[j].len = -subtable_bits;

204 ff_dlog(NULL, "%4x: n=%d (subtable)\n",

205 j, codes[i].bits + table_nb_bits);

206 index = build_table(vlc, subtable_bits, k-i, codes+i, flags);

207 if (index < 0)

208 return index;

209 /* note: realloc has been done, so reload tables */

210 table = &vlc->table[table_index];

211 table[j].sym = index;

212 if (table[j].sym != index) {

213 avpriv_request_sample(NULL, "strange codes");

214 return AVERROR_PATCHWELCOME;

215 }

216 i = k-1;

217 }

218 }

219

220 for (int i = 0; i < table_size; i++) {

221 if (table[i].len == 0)

222 table[i].sym = -1;

223 }

224

225 return table_index;

226 }

227

228 static int vlc_common_end(VLC *vlc, int nb_bits, int nb_codes, VLCcode *codes,

229 int flags, VLCcode localbuf[LOCALBUF_ELEMS])

230 {

231 int ret = build_table(vlc, nb_bits, nb_codes, codes, flags);

232

233 if (flags & INIT_VLC_USE_NEW_STATIC) {

234 if (vlc->table_size != vlc->table_allocated &&

235 !(flags & (INIT_VLC_STATIC_OVERLONG & ~INIT_VLC_USE_NEW_STATIC)))

236 av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated);

237 av_assert0(ret >= 0);

238 } else {

239 if (codes != localbuf)

240 av_free(codes);

241 if (ret < 0) {

242 av_freep(&vlc->table);

243 return ret;

244 }

245 }

246 return 0;

247 }

248

249 /* Build VLC decoding tables suitable for use with get_vlc().

250

251 'nb_bits' sets the decoding table size (2^nb_bits) entries. The

252 bigger it is, the faster is the decoding. But it should not be too

253 big to save memory and L1 cache. '9' is a good compromise.

254

255 'nb_codes' : number of vlcs codes

256

257 'bits' : table which gives the size (in bits) of each vlc code.

258

259 'codes' : table which gives the bit pattern of of each vlc code.

260

261 'symbols' : table which gives the values to be returned from get_vlc().

262

263 'xxx_wrap' : give the number of bytes between each entry of the

264 'bits' or 'codes' tables.

265

266 'xxx_size' : gives the number of bytes of each entry of the 'bits'

267 or 'codes' tables. Currently 1,2 and 4 are supported.

268

269 'wrap' and 'size' make it possible to use any memory configuration and types

270 (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables.

271 */

272 int ff_init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes,

273 const void *bits, int bits_wrap, int bits_size,

274 const void *codes, int codes_wrap, int codes_size,

275 const void *symbols, int symbols_wrap, int symbols_size,

276 int flags)

277 {

278 VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf;

279 int j, ret;

280

281 ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags);

282 if (ret < 0)

283 return ret;

284

285 av_assert0(symbols_size <= 2 || !symbols);

286 j = 0;

287 #define COPY(condition)\

288 for (int i = 0; i < nb_codes; i++) { \

289 unsigned len; \

290 GET_DATA(len, bits, i, bits_wrap, bits_size); \

291 if (!(condition)) \

292 continue; \

293 if (len > 3*nb_bits || len > 32) { \

294 av_log(NULL, AV_LOG_ERROR, "Too long VLC (%u) in init_vlc\n", len);\

295 if (buf != localbuf) \

296 av_free(buf); \

297 return AVERROR(EINVAL); \

298 } \

299 buf[j].bits = len; \

300 GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \

301 if (buf[j].code >= (1LL<<buf[j].bits)) { \

302 av_log(NULL, AV_LOG_ERROR, "Invalid code %"PRIx32" for %d in " \

303 "init_vlc\n", buf[j].code, i); \

304 if (buf != localbuf) \

305 av_free(buf); \

306 return AVERROR(EINVAL); \

307 } \

308 if (flags & INIT_VLC_INPUT_LE) \

309 buf[j].code = bitswap_32(buf[j].code); \

310 else \

311 buf[j].code <<= 32 - buf[j].bits; \

312 if (symbols) \

313 GET_DATA(buf[j].symbol, symbols, i, symbols_wrap, symbols_size) \

314 else \

315 buf[j].symbol = i; \

316 j++; \

317 }

318 COPY(len > nb_bits);

319 // qsort is the slowest part of init_vlc, and could probably be improved or avoided

320 AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);

321 COPY(len && len <= nb_bits);

322 nb_codes = j;

323

324 return vlc_common_end(vlc, nb_bits, nb_codes, buf,

325 flags, localbuf);

326 }

327

328 int ff_init_vlc_from_lengths(VLC *vlc, int nb_bits, int nb_codes,

329 const int8_t *lens, int lens_wrap,

330 const void *symbols, int symbols_wrap, int symbols_size,

331 int offset, int flags, void *logctx)

332 {

333 VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf;

334 uint64_t code;

335 int ret, j, len_max = FFMIN(32, 3 * nb_bits);

336

337 ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags);

338 if (ret < 0)

339 return ret;

340

341 j = code = 0;

342 for (int i = 0; i < nb_codes; i++, lens += lens_wrap) {

343 int len = *lens;

344 if (len > 0) {

345 unsigned sym;

346

347 buf[j].bits = len;

348 if (symbols)

349 GET_DATA(sym, symbols, i, symbols_wrap, symbols_size)

350 else

351 sym = i;

352 buf[j].symbol = sym + offset;

353 buf[j++].code = code;

354 } else if (len < 0) {

355 len = -len;

356 } else

357 continue;

358 if (len > len_max || code & ((1U << (32 - len)) - 1)) {

359 av_log(logctx, AV_LOG_ERROR, "Invalid VLC (length %u)\n", len);

360 goto fail;

361 }

362 code += 1U << (32 - len);

363 if (code > UINT32_MAX + 1ULL) {

364 av_log(logctx, AV_LOG_ERROR, "Overdetermined VLC tree\n");

365 goto fail;

366 }

367 }

368 return vlc_common_end(vlc, nb_bits, j, buf, flags, localbuf);

369 fail:

370 if (buf != localbuf)

371 av_free(buf);

372 return AVERROR_INVALIDDATA;

373 }

374

375 void ff_free_vlc(VLC *vlc)

376 {

377 av_freep(&vlc->table);

378 }

VLCcode::symbol

VLCBaseType symbol

Definition: vlc.c:91

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

INIT_VLC_OUTPUT_LE

#define INIT_VLC_OUTPUT_LE

Definition: vlc.h:98

vlc_common_init

static int vlc_common_init(VLC *vlc, int nb_bits, int nb_codes, VLCcode **buf, int flags)

Definition: vlc.c:97

#define b

Definition: input.c:41

ff_reverse

const uint8_t ff_reverse[256]

Definition: reverse.c:23

table

static const uint16_t table[]

Definition: prosumer.c:205

reverse.h

FFMAX

#define FFMAX(a, b)

Definition: macros.h:47

vlc_common_end

static int vlc_common_end(VLC *vlc, int nb_bits, int nb_codes, VLCcode *codes, int flags, VLCcode localbuf[LOCALBUF_ELEMS])

Definition: vlc.c:228

macros.h

fail

#define fail()

Definition: checkasm.h:134

avassert.h

AV_LOG_ERROR

#define AV_LOG_ERROR

Something went wrong and cannot losslessly be recovered.

Definition: log.h:180

bitswap_32

static av_always_inline uint32_t bitswap_32(uint32_t x)

Definition: vlc.c:81

bits

uint8_t bits

Definition: vp3data.h:128

LOCALBUF_ELEMS

#define LOCALBUF_ELEMS

Definition: vlc.c:79

av_assert0

#define av_assert0(cond)

assert() equivalent, that is always enabled.

Definition: avassert.h:37

build_table

static int build_table(VLC *vlc, int table_nb_bits, int nb_codes, VLCcode *codes, int flags)

Build VLC decoding tables suitable for use with get_vlc().

Definition: vlc.c:137

COPY

#define COPY(condition)

av_realloc_f

#define av_realloc_f(p, o, n)

Definition: tableprint_vlc.h:32

GET_DATA

#define GET_DATA(v, table, i, wrap, size)

Definition: vlc.c:40

NULL

#define NULL

Definition: coverity.c:32

AVERROR_PATCHWELCOME

#define AVERROR_PATCHWELCOME

Not yet implemented in FFmpeg, patches welcome.

Definition: error.h:64

ff_init_vlc_from_lengths

int ff_init_vlc_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:328

INIT_VLC_USE_NEW_STATIC

#define INIT_VLC_USE_NEW_STATIC

Definition: vlc.h:100

index

int index

Definition: gxfenc.c:89

error.h

VLCcode

Definition: vlc.c:89

ff_dlog

#define ff_dlog(a,...)

Definition: tableprint_vlc.h:28

VLC::table_allocated

int table_allocated

Definition: vlc.h:34

qsort.h

compare_vlcspec

static int compare_vlcspec(const void *a, const void *b)

Definition: vlc.c:117

size

int size

Definition: twinvq_data.h:10344

VLCElem

Definition: vlc.h:27

The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a

Definition: undefined.txt:41

code_prefix

static const unsigned code_prefix[]

Definition: qdmc.c:79

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

attributes.h

log.h

#define i(width, name, range_min, range_max)

Definition: cbs_h2645.c:269

code

and forward the test the status of outputs and forward it to the corresponding return FFERROR_NOT_READY If the filters stores internally one or a few frame for some it can consider them to be part of the FIFO and delay acknowledging a status change accordingly Example code

Definition: filter_design.txt:178

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

internal.h

av_malloc_array

#define av_malloc_array(a, b)

Definition: tableprint_vlc.h:31

VLCcode::bits

uint8_t bits

Definition: vlc.c:90

av_always_inline

#define av_always_inline

Definition: attributes.h:49

FFMIN