2 * Common bit I/O utils.
4 * Extracted 2009 from mplayer 2009-02-10 libavcodec/bitstream.c.
6 * Copyright (c) 2000, 2001 Fabrice Bellard
7 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
8 * alternative bitstream reader & writer by Michael Niedermayer <michaelni@gmx.at>
9 * Copyright (C) 2009 Andre Noll <maan@tuebingen.mpg.de>
11 * Licensed under the GNU Lesser General Public License. see file COPYING.LIB.
14 /** \file bitstream.c Bitstream API for the wma decoder. */
22 #include "portable_io.h"
23 #include "bitstream.h"
25 static inline uint32_t get_data(const void *table
, int i
, int size
)
27 const uint8_t *ptr
= (const uint8_t *)table
+ i
* size
;
32 v
= *(const uint8_t *)ptr
;
35 v
= *(const uint16_t *)ptr
;
38 v
= *(const uint32_t *)ptr
;
44 static void alloc_table(struct vlc
*vlc
, int size
)
46 vlc
->table_size
+= size
;
47 if (vlc
->table_size
> vlc
->table_allocated
) {
48 vlc
->table_allocated
+= (1 << vlc
->bits
);
49 vlc
->table
= arr_realloc(vlc
->table
, vlc
->table_allocated
,
54 static int build_table(struct vlc
*vlc
, int table_nb_bits
, int nb_codes
,
55 const void *bits
, const void *codes
, int codes_size
,
56 uint32_t code_prefix
, int n_prefix
)
58 int i
, j
, k
, n
, table_size
, table_index
, nb
, n1
, idx
;
62 table_size
= 1 << table_nb_bits
;
63 table_index
= vlc
->table_size
;
64 alloc_table(vlc
, table_size
);
65 table
= &vlc
->table
[table_index
];
67 for (i
= 0; i
< table_size
; i
++) {
68 table
[i
][1] = 0; /* bits */
69 table
[i
][0] = -1; /* codes */
72 /* map codes and compute auxiliary table sizes */
73 for (i
= 0; i
< nb_codes
; i
++) {
74 n
= get_data(bits
, i
, 1);
75 /* we accept tables with holes */
79 code
= get_data(codes
, i
, codes_size
);
80 /* if code matches the prefix, it is in the table */
81 if ((code
>> n
) != code_prefix
)
83 if (n
<= table_nb_bits
) {
84 /* no need to add another table */
85 j
= (code
<< (table_nb_bits
- n
)) & (table_size
- 1);
86 nb
= 1 << (table_nb_bits
- n
);
87 for (k
= 0; k
< nb
; k
++) {
88 assert(table
[j
][1] == 0); /* incorrect code */
89 table
[j
][1] = n
; /* bits */
95 j
= (code
>> n
) & ((1 << table_nb_bits
) - 1);
96 /* compute table size */
97 n1
= -table
[j
][1]; /* bits */
100 table
[j
][1] = -n1
; /* bits */
104 /* fill auxiliary tables recursively */
105 for (i
= 0; i
< table_size
; i
++) {
106 n
= table
[i
][1]; /* bits */
109 if (n
> table_nb_bits
) {
111 table
[i
][1] = -n
; /* bits */
113 idx
= build_table(vlc
, n
, nb_codes
, bits
, codes
,
114 codes_size
, (code_prefix
<< table_nb_bits
) | i
,
115 n_prefix
+ table_nb_bits
);
116 /* vlc->table might have changed */
117 table
= &vlc
->table
[table_index
];
118 table
[i
][0] = idx
; /* code */
125 * Build VLC decoding tables suitable for use with get_vlc().
127 * \param vlc The structure to be initialized.
128 * \param nb_bits Set the decoding table size (2^nb_bits) entries.
129 * \param nb_codes Number of vlc codes.
130 * \param bits Table which gives the size (in bits) of each vlc code.
131 * \param codes Table which gives the bit pattern of of each vlc code.
132 * \param codes_size The number of bytes of each entry of the \a codes tables.
134 * The bigger \a nb_bits is, the faster is the decoding. But it should not be
135 * too big to save memory and L1 cache. '9' is a good compromise.
137 * The wrap and size parameters allow to use any memory configuration and
138 * types (byte/word/long) to store the bits and codes tables.
140 void init_vlc(struct vlc
*vlc
, int nb_bits
, int nb_codes
, const void *bits
,
141 const void *codes
, int codes_size
)
143 PARA_INFO_LOG("nb_codes: %d\n", nb_codes
);
146 vlc
->table_allocated
= 0;
148 build_table(vlc
, nb_bits
, nb_codes
, bits
, codes
, codes_size
, 0, 0);
152 * Deallocate all resources of a VLC table.
154 * \param vlc Pointer to an initialized vlc structure.
156 * The table given by \a vlc must have been initialized earlier via \ref
159 void free_vlc(struct vlc
*vlc
)
167 * \param gbc The getbit context structure.
168 * \param vlc The vlc tables to use.
170 * \return The vlc code.
172 int get_vlc(struct getbit_context
*gbc
, const struct vlc
*vlc
)
174 int n
, idx
, nb_bits
, code
;
176 idx
= show_bits(gbc
, vlc
->bits
);
177 code
= vlc
->table
[idx
][0];
178 n
= vlc
->table
[idx
][1];
180 skip_bits(gbc
, vlc
->bits
);
182 idx
= show_bits(gbc
, nb_bits
) + code
;
183 code
= vlc
->table
[idx
][0];
184 n
= vlc
->table
[idx
][1];
186 skip_bits(gbc
, nb_bits
);
188 idx
= show_bits(gbc
, nb_bits
) + code
;
189 code
= vlc
->table
[idx
][0];
190 n
= vlc
->table
[idx
][1];
194 return code
>= 0? code
: -E_VLC
;