avcodec/dca: avoid using bitstream reader in a non-standard way
[ffmpeg.git] / libavcodec / bgmc.c
1 /*
2  * Block Gilbert-Moore decoder
3  * Copyright (c) 2010 Thilo Borgmann <thilo.borgmann _at_ mail.de>
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  * Block Gilbert-Moore decoder as used by MPEG-4 ALS
25  * @author Thilo Borgmann <thilo.borgmann _at_ mail.de>
26  */
27
28 #include "libavutil/attributes.h"
29 #include "bgmc.h"
30
31 #define FREQ_BITS  14                      // bits used by frequency counters
32 #define VALUE_BITS 18                      // bits used to represent the values
33 #define TOP_VALUE  ((1 << VALUE_BITS) - 1) // maximum value
34 #define FIRST_QTR  (TOP_VALUE / 4 + 1)     // first quarter of values maximum value
35 #define HALF       (2 * FIRST_QTR)         // first half of values maximum value
36 #define THIRD_QTR  (3 * FIRST_QTR)         // third quarter of values maximum value
37
38 #define LUT_BITS   (FREQ_BITS - 8)         // number of bits used to index lookup tables
39 #define LUT_SIZE   (1 << LUT_BITS)         // size of the lookup tables
40 #define LUT_BUFF   4                       // number of buffered lookup tables
41
42
43 /** Cumulative frequency tables for block Gilbert-Moore coding. */
44 static const uint16_t cf_tables_1[3][129] = {
45     {
46         16384, 16066, 15748, 15431, 15114, 14799, 14485, 14173, 13861, 13552,
47         13243, 12939, 12635, 12336, 12038, 11745, 11452, 11161, 10870, 10586,
48         10303, 10027,  9751,  9483,  9215,  8953,  8692,  8440,  8189,  7946,
49          7704,  7472,  7240,  7008,  6776,  6554,  6333,  6122,  5912,  5711,
50          5512,  5320,  5128,  4947,  4766,  4595,  4425,  4264,  4104,  3946,
51          3788,  3640,  3493,  3355,  3218,  3090,  2963,  2842,  2721,  2609,
52          2498,  2395,  2292,  2196,  2100,  2004,  1908,  1820,  1732,  1651,
53          1570,  1497,  1424,  1355,  1287,  1223,  1161,  1100,  1044,   988,
54           938,   888,   839,   790,   746,   702,   662,   623,   588,   553,
55           520,   488,   459,   431,   405,   380,   357,   334,   311,   288,
56           268,   248,   230,   213,   197,   182,   168,   154,   142,   130,
57           119,   108,    99,    90,    81,    72,    64,    56,    49,    42,
58            36,    30,    25,    20,    15,    11,     7,     3,     0
59     },
60     {
61         16384, 16080, 15776, 15473, 15170, 14868, 14567, 14268, 13970, 13674,
62         13378, 13086, 12794, 12505, 12218, 11936, 11654, 11373, 11092, 10818,
63         10544, 10276, 10008,  9749,  9490,  9236,  8982,  8737,  8492,  8256,
64          8020,  7792,  7564,  7336,  7108,  6888,  6669,  6459,  6249,  6050,
65          5852,  5660,  5468,  5286,  5104,  4931,  4760,  4598,  4436,  4275,
66          4115,  3965,  3816,  3674,  3534,  3403,  3272,  3147,  3023,  2907,
67          2792,  2684,  2577,  2476,  2375,  2274,  2173,  2079,  1986,  1897,
68          1810,  1724,  1645,  1567,  1493,  1419,  1351,  1284,  1222,  1161,
69          1105,  1050,   995,   941,   891,   842,   797,   753,   713,   673,
70           636,   599,   566,   533,   503,   473,   446,   419,   392,   365,
71           340,   316,   294,   272,   253,   234,   216,   199,   184,   169,
72           155,   142,   130,   118,   106,    95,    85,    75,    66,    57,
73            49,    41,    34,    27,    21,    15,    10,     5,     0
74     },
75     {
76         16384, 16092, 15801, 15510, 15219, 14930, 14641, 14355, 14069, 13785,
77         13501, 13219, 12938, 12661, 12384, 12112, 11841, 11571, 11301, 11037,
78         10773, 10514, 10256, 10005,  9754,  9508,  9263,  9025,  8787,  8557,
79          8327,  8103,  7879,  7655,  7431,  7215,  7000,  6792,  6585,  6387,
80          6190,  5998,  5807,  5625,  5445,  5272,  5100,  4937,  4774,  4613,
81          4452,  4301,  4150,  4007,  3865,  3731,  3597,  3469,  3341,  3218,
82          3099,  2981,  2869,  2758,  2652,  2546,  2440,  2334,  2234,  2134,
83          2041,  1949,  1864,  1779,  1699,  1620,  1547,  1474,  1407,  1340,
84          1278,  1217,  1157,  1097,  1043,   989,   940,   891,   846,   801,
85           759,   718,   680,   643,   609,   575,   543,   511,   479,   447,
86           418,   389,   363,   337,   314,   291,   270,   249,   230,   212,
87           195,   179,   164,   149,   135,   121,   108,    96,    85,    74,
88           64,     54,    45,    36,    28,    20,    13,     6,     0
89     }
90 };
91
92
93 static const uint16_t cf_tables_2[8][193] = {
94     {
95         16384, 16104, 15825, 15546, 15268, 14991, 14714, 14439, 14164, 13891,
96         13620, 13350, 13081, 12815, 12549, 12287, 12025, 11765, 11505, 11250,
97         10996, 10746, 10497, 10254, 10011,  9772,  9534,  9303,  9072,  8848,
98          8624,  8406,  8188,  7970,  7752,  7539,  7327,  7123,  6919,  6724,
99          6529,  6339,  6150,  5970,  5790,  5618,  5446,  5282,  5119,  4957,
100          4795,  4642,  4490,  4345,  4201,  4065,  3929,  3798,  3669,  3547,
101          3425,  3310,  3196,  3086,  2976,  2866,  2756,  2650,  2545,  2447,
102          2350,  2260,  2170,  2085,  2000,  1921,  1843,  1770,  1698,  1632,
103          1566,  1501,  1436,  1376,  1316,  1261,  1207,  1157,  1108,  1061,
104          1015,   973,   931,   893,   855,   819,   783,   747,   711,   677,
105           644,   614,   584,   557,   530,   505,   480,   458,   436,   416,
106           396,   378,   360,   343,   326,   310,   295,   281,   267,   255,
107           243,   232,   221,   211,   201,   192,   183,   174,   166,   158,
108           150,   142,   134,   126,   119,   112,   106,   100,    95,    90,
109            85,    80,    76,    72,    69,    66,    63,    60,    57,    54,
110            51,    48,    46,    44,    42,    40,    38,    36,    34,    33,
111            32,    31,    30,    29,    28,    27,    26,    25,    24,    23,
112            22,    21,    20,    19,    18,    17,    16,    15,    14,    13,
113            12,    11,    10,     9,     8,     7,     6,     5,     4,     3,
114             2,     1,     0
115     },
116     {
117         16384, 16116, 15849, 15582, 15316, 15050, 14785, 14521, 14257, 13995,
118         13734, 13476, 13218, 12963, 12708, 12457, 12206, 11956, 11706, 11460,
119         11215, 10975, 10735, 10500, 10265, 10034,  9803,  9579,  9355,  9136,
120          8917,  8703,  8489,  8275,  8061,  7853,  7645,  7444,  7244,  7051,
121          6858,  6671,  6484,  6305,  6127,  5956,  5785,  5622,  5459,  5298,
122          5137,  4983,  4830,  4684,  4539,  4401,  4263,  4131,  3999,  3874,
123          3750,  3632,  3515,  3401,  3287,  3173,  3059,  2949,  2840,  2737,
124          2635,  2539,  2444,  2354,  2264,  2181,  2098,  2020,  1943,  1872,
125          1801,  1731,  1661,  1596,  1532,  1472,  1412,  1357,  1303,  1251,
126          1200,  1153,  1106,  1063,  1020,   979,   938,   897,   856,   818,
127           780,   746,   712,   681,   650,   621,   592,   566,   540,   517,
128           494,   473,   452,   431,   410,   391,   373,   356,   340,   325,
129           310,   296,   282,   270,   258,   247,   236,   225,   214,   203,
130           192,   182,   172,   162,   153,   144,   136,   128,   121,   114,
131           108,   102,    97,    92,    87,    82,    77,    73,    69,    65,
132            62,    59,    56,    53,    50,    47,    45,    43,    41,    39,
133            37,    35,    33,    31,    29,    27,    26,    25,    24,    23,
134            22,    21,    20,    19,    18,    17,    16,    15,    14,    13,
135            12,    11,    10,     9,     8,     7,     6,     5,     4,     3,
136             2,     1,     0
137     },
138     {
139         16384, 16128, 15872, 15617, 15362, 15107, 14853, 14600, 14347, 14096,
140         13846, 13597, 13350, 13105, 12860, 12618, 12376, 12135, 11894, 11657,
141         11421, 11189, 10957, 10730, 10503, 10279, 10056,  9838,  9620,  9407,
142          9195,  8987,  8779,  8571,  8363,  8159,  7955,  7758,  7561,  7371,
143          7182,  6997,  6812,  6635,  6459,  6289,  6120,  5957,  5795,  5634,
144          5473,  5319,  5165,  5018,  4871,  4732,  4593,  4458,  4324,  4197,
145          4071,  3951,  3831,  3714,  3597,  3480,  3363,  3250,  3138,  3032,
146          2927,  2828,  2729,  2635,  2541,  2453,  2366,  2284,  2202,  2126,
147          2050,  1975,  1900,  1830,  1761,  1697,  1633,  1574,  1515,  1459,
148          1403,  1351,  1300,  1252,  1205,  1160,  1115,  1070,  1025,   982,
149           939,   899,   860,   824,   789,   756,   723,   693,   663,   636,
150           609,   584,   559,   535,   511,   489,   467,   447,   427,   409,
151           391,   374,   358,   343,   328,   313,   300,   287,   274,   261,
152           248,   235,   223,   211,   200,   189,   179,   169,   160,   151,
153           143,   135,   128,   121,   115,   109,   103,    97,    92,    87,
154            82,    77,    73,    69,    65,    61,    58,    55,    52,    49,
155            46,    43,    40,    37,    35,    33,    31,    29,    27,    25,
156            23,    21,    20,    19,    18,    17,    16,    15,    14,    13,
157            12,    11,    10,     9,     8,     7,     6,     5,     4,     3,
158             2,     1,     0
159     },
160     {
161         16384, 16139, 15894, 15649, 15405, 15162, 14919, 14677, 14435, 14195,
162         13955, 13717, 13479, 13243, 13008, 12775, 12542, 12310, 12079, 11851,
163         11623, 11399, 11176, 10956, 10737, 10521, 10305, 10094,  9883,  9677,
164          9471,  9268,  9065,  8862,  8659,  8459,  8260,  8067,  7874,  7688,
165          7502,  7321,  7140,  6965,  6790,  6621,  6452,  6290,  6128,  5968,
166          5808,  5655,  5503,  5356,  5209,  5069,  4929,  4794,  4660,  4532,
167          4404,  4282,  4160,  4041,  3922,  3803,  3684,  3568,  3452,  3343,
168          3234,  3131,  3029,  2931,  2833,  2741,  2649,  2563,  2477,  2396,
169          2316,  2236,  2157,  2083,  2009,  1940,  1871,  1807,  1743,  1683,
170          1623,  1567,  1511,  1459,  1407,  1357,  1307,  1257,  1207,  1159,
171          1111,  1067,  1023,   983,   943,   905,   868,   834,   800,   769,
172           738,   709,   681,   653,   625,   600,   575,   552,   529,   508,
173           487,   466,   447,   428,   410,   392,   376,   360,   344,   328,
174           313,   298,   283,   268,   255,   242,   230,   218,   207,   196,
175           186,   176,   167,   158,   150,   142,   135,   128,   121,   114,
176           108,   102,    97,    92,    87,    82,    78,    74,    70,    66,
177            62,    58,    54,    50,    47,    44,    41,    38,    35,    32,
178            30,    28,    26,    24,    22,    20,    18,    16,    14,    13,
179            12,    11,    10,     9,     8,     7,     6,     5,     4,     3,
180             2,     1,     0
181     },
182     {
183         16384, 16149, 15915, 15681, 15447, 15214, 14981, 14749, 14517, 14286,
184         14055, 13827, 13599, 13373, 13147, 12923, 12699, 12476, 12253, 12034,
185         11815, 11599, 11383, 11171, 10959, 10750, 10541, 10337, 10133,  9933,
186          9733,  9536,  9339,  9142,  8945,  8751,  8557,  8369,  8181,  7998,
187          7816,  7638,  7460,  7288,  7116,  6950,  6785,  6625,  6465,  6306,
188          6147,  5995,  5843,  5697,  5551,  5411,  5271,  5135,  5000,  4871,
189          4742,  4618,  4495,  4374,  4253,  4132,  4011,  3893,  3775,  3663,
190          3552,  3446,  3340,  3239,  3138,  3043,  2948,  2858,  2768,  2684,
191          2600,  2516,  2433,  2355,  2278,  2205,  2133,  2065,  1997,  1932,
192          1867,  1807,  1747,  1690,  1634,  1580,  1526,  1472,  1418,  1366,
193          1314,  1266,  1218,  1174,  1130,  1088,  1047,  1009,   971,   936,
194           901,   868,   836,   804,   772,   743,   714,   685,   658,   631,
195           606,   582,   559,   536,   515,   494,   475,   456,   437,   418,
196           399,   380,   362,   344,   328,   312,   297,   283,   270,   257,
197           245,   233,   222,   211,   201,   191,   181,   172,   163,   155,
198           147,   139,   132,   125,   119,   113,   107,   101,    96,    91,
199            86,    81,    76,    71,    66,    62,    58,    54,    50,    46,
200            43,    40,    37,    34,    31,    28,    26,    24,    22,    20,
201            18,    16,    14,    12,    10,     8,     6,     5,     4,     3,
202             2,     1,     0
203     },
204     {
205         16384, 16159, 15934, 15709, 15485, 15261, 15038, 14816, 14594, 14373,
206         14152, 13933, 13714, 13497, 13280, 13065, 12850, 12636, 12422, 12211,
207         12000, 11791, 11583, 11378, 11173, 10971, 10769, 10571, 10373, 10179,
208          9985,  9793,  9601,  9409,  9217,  9029,  8842,  8658,  8475,  8297,
209          8120,  7946,  7773,  7604,  7435,  7271,  7108,  6950,  6792,  6634,
210          6477,  6326,  6175,  6029,  5883,  5742,  5602,  5466,  5330,  5199,
211          5068,  4943,  4818,  4696,  4574,  4452,  4330,  4211,  4093,  3979,
212          3866,  3759,  3652,  3549,  3446,  3348,  3250,  3157,  3065,  2977,
213          2889,  2802,  2716,  2634,  2553,  2476,  2399,  2326,  2254,  2185,
214          2117,  2052,  1987,  1926,  1866,  1808,  1750,  1692,  1634,  1578,
215          1522,  1470,  1418,  1369,  1321,  1275,  1229,  1187,  1145,  1105,
216          1066,  1027,   991,   955,   919,   883,   850,   817,   786,   756,
217           728,   700,   674,   648,   624,   600,   578,   556,   534,   512,
218           490,   468,   447,   426,   407,   388,   371,   354,   338,   322,
219           307,   293,   280,   267,   255,   243,   231,   219,   209,   199,
220           189,   179,   170,   161,   153,   145,   138,   131,   124,   117,
221           111,   105,    99,    93,    87,    81,    76,    71,    66,    61,
222            57,    53,    49,    45,    42,    39,    36,    33,    30,    27,
223            24,    21,    19,    17,    15,    13,    11,     9,     7,     5,
224             3,     1,     0
225     },
226     {
227         16384, 16169, 15954, 15739, 15524, 15310, 15096, 14883, 14670, 14458,
228         14246, 14035, 13824, 13614, 13405, 13198, 12991, 12785, 12579, 12376,
229         12173, 11972, 11772, 11574, 11377, 11182, 10987, 10795, 10603, 10414,
230         10226, 10040,  9854,  9668,  9482,  9299,  9116,  8937,  8759,  8585,
231          8411,  8241,  8071,  7906,  7741,  7580,  7419,  7263,  7107,  6952,
232          6797,  6647,  6497,  6353,  6209,  6070,  5931,  5796,  5661,  5531,
233          5401,  5275,  5150,  5027,  4904,  4781,  4658,  4538,  4419,  4304,
234          4190,  4081,  3972,  3867,  3762,  3662,  3562,  3467,  3372,  3281,
235          3191,  3101,  3012,  2928,  2844,  2764,  2684,  2608,  2533,  2460,
236          2387,  2318,  2250,  2185,  2121,  2059,  1997,  1935,  1873,  1813,
237          1754,  1698,  1642,  1588,  1535,  1483,  1433,  1384,  1338,  1292,
238          1249,  1206,  1165,  1125,  1085,  1045,  1008,   971,   937,   903,
239           871,   840,   810,   780,   752,   724,   698,   672,   647,   622,
240           597,   572,   548,   524,   502,   480,   460,   440,   421,   403,
241           386,   369,   353,   337,   323,   309,   295,   281,   268,   255,
242           243,   231,   220,   209,   199,   189,   180,   171,   163,   155,
243           147,   139,   131,   123,   116,   109,   102,    95,    89,    83,
244            77,    72,    67,    62,    57,    52,    48,    44,    40,    36,
245            32,    28,    25,    22,    19,    16,    13,    10,     8,     6,
246             4,     2,     0
247     },
248     {
249         16384, 16177, 15970, 15764, 15558, 15353, 15148, 14944, 14740, 14537,
250         14334, 14132, 13930, 13729, 13529, 13330, 13131, 12933, 12735, 12539,
251         12343, 12150, 11957, 11766, 11576, 11388, 11200, 11015, 10830, 10647,
252         10465, 10285, 10105,  9925,  9745,  9568,  9391,  9218,  9045,  8876,
253          8707,  8541,  8375,  8213,  8051,  7894,  7737,  7583,  7429,  7277,
254          7125,  6977,  6830,  6687,  6544,  6406,  6268,  6133,  5998,  5868,
255          5738,  5612,  5487,  5364,  5241,  5118,  4995,  4875,  4755,  4640,
256          4525,  4414,  4304,  4198,  4092,  3990,  3888,  3790,  3693,  3600,
257          3507,  3415,  3323,  3235,  3147,  3064,  2981,  2902,  2823,  2746,
258          2670,  2594,  2522,  2450,  2382,  2314,  2248,  2182,  2116,  2050,
259          1987,  1924,  1864,  1804,  1748,  1692,  1638,  1585,  1534,  1484,
260          1437,  1390,  1346,  1302,  1258,  1215,  1174,  1133,  1095,  1057,
261          1021,   986,   952,   918,   887,   856,   827,   798,   770,   742,
262           714,   686,   659,   632,   607,   582,   559,   536,   514,   492,
263           472,   452,   433,   415,   398,   381,   364,   348,   333,   318,
264           304,   290,   277,   264,   252,   240,   229,   218,   208,   198,
265           188,   178,   168,   158,   149,   140,   132,   124,   116,   108,
266           101,    94,    87,    81,    75,    69,    64,    59,    54,    49,
267            44,    39,    35,    31,    27,    23,    19,    15,    12,     9,
268             6,     3,     0
269     }
270 };
271
272
273 static const uint16_t cf_tables_3[5][257] = {
274     {
275         16384, 16187, 15990, 15793, 15597, 15401, 15205, 15009, 14813, 14618,
276         14423, 14230, 14037, 13845, 13653, 13463, 13273, 13083, 12894, 12706,
277         12518, 12332, 12146, 11962, 11778, 11597, 11416, 11237, 11059, 10882,
278         10706, 10532, 10358, 10184, 10010,  9838,  9666,  9497,  9328,  9163,
279          8999,  8837,  8675,  8517,  8359,  8205,  8051,  7901,  7751,  7602,
280          7453,  7308,  7163,  7022,  6882,  6745,  6609,  6476,  6343,  6214,
281          6085,  5960,  5835,  5712,  5589,  5466,  5343,  5223,  5103,  4987,
282          4872,  4761,  4650,  4542,  4435,  4332,  4229,  4130,  4031,  3936,
283          3841,  3747,  3653,  3563,  3473,  3387,  3302,  3220,  3138,  3059,
284          2980,  2905,  2830,  2759,  2688,  2619,  2550,  2481,  2412,  2345,
285          2278,  2215,  2152,  2092,  2032,  1974,  1917,  1863,  1809,  1758,
286          1707,  1659,  1611,  1564,  1517,  1473,  1429,  1387,  1346,  1307,
287          1268,  1230,  1193,  1158,  1123,  1090,  1058,  1026,   994,   962,
288           930,   899,   869,   841,   813,   786,   760,   735,   710,   687,
289           664,   643,   622,   602,   582,   562,   543,   525,   507,   490,
290           473,   457,   442,   427,   412,   398,   385,   373,   361,   349,
291           337,   325,   313,   301,   290,   279,   269,   259,   249,   240,
292           231,   222,   214,   206,   199,   192,   185,   178,   171,   165,
293           159,   153,   148,   143,   138,   133,   128,   123,   119,   115,
294           111,   107,   103,    99,    95,    91,    87,    83,    80,    77,
295            74,    71,    68,    65,    63,    61,    59,    57,    55,    53,
296            51,    49,    47,    45,    43,    41,    40,    39,    38,    37,
297            36,    35,    34,    33,    32,    31,    30,    29,    28,    27,
298            26,    25,    24,    23,    22,    21,    20,    19,    18,    17,
299            16,    15,    14,    13,    12,    11,    10,     9,     8,     7,
300             6,     5,     4,     3,     2,     1,     0
301     },
302     {
303         16384, 16195, 16006, 15817, 15629, 15441, 15253, 15065, 14878, 14692,
304         14506, 14321, 14136, 13952, 13768, 13585, 13402, 13219, 13037, 12857,
305         12677, 12499, 12321, 12144, 11967, 11792, 11617, 11444, 11271, 11100,
306         10930, 10762, 10594, 10426, 10258, 10091,  9925,  9761,  9598,  9438,
307          9278,  9120,  8963,  8809,  8655,  8504,  8354,  8207,  8060,  7914,
308          7769,  7627,  7485,  7347,  7209,  7074,  6939,  6807,  6676,  6548,
309          6420,  6296,  6172,  6050,  5928,  5806,  5684,  5564,  5444,  5328,
310          5212,  5100,  4988,  4879,  4771,  4667,  4563,  4462,  4362,  4265,
311          4169,  4073,  3978,  3886,  3795,  3707,  3619,  3535,  3451,  3369,
312          3288,  3210,  3133,  3059,  2985,  2913,  2841,  2769,  2697,  2627,
313          2557,  2490,  2424,  2360,  2297,  2237,  2177,  2119,  2062,  2007,
314          1953,  1901,  1849,  1798,  1748,  1700,  1652,  1607,  1562,  1519,
315          1476,  1435,  1394,  1355,  1317,  1281,  1245,  1210,  1175,  1140,
316          1105,  1071,  1037,  1005,   973,   943,   913,   885,   857,   830,
317           804,   779,   754,   731,   708,   685,   663,   642,   621,   601,
318           581,   563,   545,   528,   511,   495,   479,   463,   448,   433,
319           419,   405,   391,   377,   364,   351,   338,   326,   314,   302,
320           291,   280,   270,   260,   251,   242,   234,   226,   218,   210,
321           202,   195,   188,   181,   174,   168,   162,   156,   150,   144,
322           139,   134,   129,   124,   119,   114,   109,   104,   100,    96,
323            92,    88,    84,    80,    77,    74,    71,    68,    65,    62,
324            59,    56,    54,    52,    50,    48,    46,    44,    42,    40,
325            38,    36,    34,    33,    32,    31,    30,    29,    28,    27,
326            26,    25,    24,    23,    22,    21,    20,    19,    18,    17,
327            16,    15,    14,    13,    12,    11,    10,     9,     8,     7,
328             6,     5,     4,     3,     2,     1,     0
329     },
330     {
331         16384, 16203, 16022, 15842, 15662, 15482, 15302, 15122, 14942, 14763,
332         14584, 14406, 14228, 14051, 13874, 13698, 13522, 13347, 13172, 12998,
333         12824, 12652, 12480, 12310, 12140, 11971, 11803, 11637, 11471, 11307,
334         11143, 10980, 10817, 10654, 10491, 10330, 10169, 10011,  9853,  9697,
335          9542,  9389,  9236,  9086,  8936,  8789,  8642,  8498,  8355,  8212,
336          8070,  7931,  7792,  7656,  7520,  7388,  7256,  7126,  6996,  6870,
337          6744,  6621,  6498,  6377,  6256,  6135,  6014,  5895,  5776,  5660,
338          5545,  5433,  5321,  5212,  5104,  4999,  4895,  4793,  4692,  4594,
339          4496,  4400,  4304,  4211,  4118,  4028,  3939,  3853,  3767,  3684,
340          3601,  3521,  3441,  3364,  3287,  3212,  3137,  3062,  2987,  2915,
341          2843,  2773,  2704,  2638,  2572,  2508,  2445,  2384,  2324,  2266,
342          2208,  2153,  2098,  2044,  1990,  1939,  1888,  1839,  1791,  1745,
343          1699,  1655,  1611,  1569,  1527,  1487,  1448,  1409,  1370,  1331,
344          1292,  1255,  1218,  1183,  1148,  1115,  1082,  1051,  1020,   990,
345           960,   932,   904,   878,   852,   826,   801,   777,   753,   731,
346           709,   687,   666,   645,   625,   605,   586,   567,   550,   533,
347           516,   499,   482,   465,   449,   433,   418,   403,   389,   375,
348           362,   349,   337,   325,   314,   303,   293,   283,   273,   263,
349           254,   245,   236,   227,   219,   211,   204,   197,   190,   183,
350           177,   171,   165,   159,   153,   147,   141,   135,   130,   125,
351           120,   115,   110,   105,   101,    97,    93,    89,    85,    81,
352            77,    74,    71,    68,    65,    62,    59,    56,    53,    51,
353            49,    47,    45,    43,    41,    39,    37,    35,    33,    31,
354            29,    27,    25,    23,    22,    21,    20,    19,    18,    17,
355            16,    15,    14,    13,    12,    11,    10,     9,     8,     7,
356             6,     5,     4,     3,     2,     1,     0
357     },
358     {
359         16384, 16210, 16036, 15863, 15690, 15517, 15344, 15172, 15000, 14828,
360         14656, 14485, 14314, 14145, 13976, 13808, 13640, 13472, 13304, 13137,
361         12970, 12804, 12639, 12475, 12312, 12149, 11987, 11827, 11667, 11508,
362         11349, 11192, 11035, 10878, 10721, 10565, 10410, 10257, 10104,  9953,
363          9802,  9654,  9506,  9359,  9213,  9070,  8927,  8787,  8647,  8508,
364          8369,  8233,  8097,  7964,  7831,  7700,  7570,  7442,  7315,  7190,
365          7065,  6943,  6821,  6701,  6581,  6461,  6341,  6223,  6105,  5990,
366          5876,  5764,  5653,  5545,  5437,  5331,  5226,  5124,  5022,  4924,
367          4826,  4729,  4632,  4538,  4444,  4353,  4262,  4174,  4087,  4002,
368          3917,  3835,  3753,  3674,  3595,  3518,  3441,  3364,  3287,  3212,
369          3138,  3066,  2995,  2926,  2858,  2792,  2726,  2662,  2599,  2538,
370          2478,  2420,  2362,  2305,  2249,  2195,  2141,  2089,  2037,  1988,
371          1939,  1891,  1844,  1799,  1754,  1711,  1668,  1626,  1584,  1542,
372          1500,  1459,  1418,  1380,  1342,  1305,  1269,  1234,  1199,  1166,
373          1133,  1102,  1071,  1041,  1012,   983,   954,   926,   899,   872,
374           847,   822,   798,   774,   751,   728,   707,   686,   666,   646,
375           627,   608,   589,   570,   552,   534,   517,   500,   484,   468,
376           453,   438,   424,   410,   397,   384,   372,   360,   348,   336,
377           325,   314,   303,   293,   283,   273,   264,   255,   246,   237,
378           229,   221,   213,   205,   197,   189,   181,   174,   167,   160,
379           154,   148,   142,   136,   131,   126,   121,   116,   111,   106,
380           101,    97,    93,    89,    85,    81,    77,    73,    70,    67,
381            64,    61,    58,    55,    52,    49,    46,    43,    40,    37,
382            35,    33,    31,    29,    27,    25,    23,    21,    19,    17,
383            16,    15,    14,    13,    12,    11,    10,     9,     8,     7,
384             6,     5,     4,     3,     2,     1,     0
385     },
386     {
387         16384, 16218, 16052, 15886, 15720, 15554, 15389, 15224, 15059, 14895,
388         14731, 14567, 14403, 14240, 14077, 13915, 13753, 13591, 13429, 13269,
389         13109, 12950, 12791, 12633, 12476, 12320, 12164, 12009, 11854, 11701,
390         11548, 11396, 11244, 11092, 10940, 10790, 10640, 10492, 10344, 10198,
391         10052,  9908,  9764,  9622,  9481,  9342,  9203,  9066,  8929,  8793,
392          8657,  8524,  8391,  8261,  8131,  8003,  7875,  7749,  7624,  7502,
393          7380,  7260,  7140,  7022,  6904,  6786,  6668,  6551,  6435,  6322,
394          6209,  6099,  5989,  5881,  5773,  5668,  5563,  5461,  5359,  5260,
395          5161,  5063,  4965,  4871,  4777,  4686,  4595,  4506,  4417,  4331,
396          4245,  4162,  4079,  3999,  3919,  3841,  3763,  3685,  3607,  3530,
397          3454,  3380,  3307,  3236,  3166,  3097,  3029,  2963,  2897,  2834,
398          2771,  2710,  2650,  2591,  2532,  2475,  2418,  2363,  2309,  2257,
399          2205,  2155,  2105,  2057,  2009,  1963,  1918,  1873,  1828,  1783,
400          1738,  1694,  1650,  1607,  1565,  1524,  1484,  1445,  1407,  1369,
401          1333,  1297,  1263,  1229,  1197,  1165,  1134,  1103,  1073,  1043,
402          1015,   987,   960,   933,   907,   882,   858,   834,   811,   788,
403           766,   744,   722,   700,   679,   658,   638,   618,   599,   581,
404           563,   545,   528,   511,   495,   480,   465,   451,   437,   423,
405           410,   397,   384,   372,   360,   348,   337,   326,   315,   305,
406           295,   285,   275,   265,   255,   245,   236,   227,   219,   211,
407           203,   195,   188,   181,   174,   167,   161,   155,   149,   143,
408           137,   131,   126,   121,   116,   111,   106,   101,    97,    93,
409            89,    85,    81,    77,    73,    69,    65,    61,    58,    55,
410            52,    49,    46,    43,    40,    37,    34,    32,    30,    28,
411            26,    24,    22,    20,    18,    16,    14,    12,    10,     8,
412             6,     5,     4,     3,     2,     1,     0
413     }
414 };
415
416
417 static const uint16_t *const cf_table[16] = {
418     cf_tables_1[0], cf_tables_1[1], cf_tables_1[2], cf_tables_2[0],
419     cf_tables_2[1], cf_tables_2[2], cf_tables_2[3], cf_tables_2[4],
420     cf_tables_2[5], cf_tables_2[6], cf_tables_2[7], cf_tables_3[0],
421     cf_tables_3[1], cf_tables_3[2], cf_tables_3[3], cf_tables_3[4]
422 };
423
424
425 /** Initialize a given lookup table using a given delta */
426 static void bgmc_lut_fillp(uint8_t *lut, int *lut_status, int delta)
427 {
428     unsigned int sx, i;
429
430     for (sx = 0; sx < 16; sx++)
431         for (i = 0; i < LUT_SIZE; i++) {
432             unsigned int target = (i + 1) << (FREQ_BITS - LUT_BITS);
433             unsigned int symbol = 1 << delta;
434
435             while (cf_table[sx][symbol] > target)
436                 symbol += 1 << delta;
437
438             *lut++ = symbol >> delta;
439         }
440
441     *lut_status = delta;
442 }
443
444
445 /** Retune the index of a suitable lookup table for a given delta */
446 static uint8_t *bgmc_lut_getp(uint8_t *lut, int *lut_status, int delta)
447 {
448     unsigned int i = av_clip(delta, 0, LUT_BUFF - 1);
449
450     lut += (i * LUT_SIZE) << 4;
451
452     if (lut_status[i] != delta)
453         bgmc_lut_fillp(lut, &lut_status[i], delta);
454
455     return lut;
456 }
457
458
459 /** Initialize the lookup table arrays */
460 av_cold int ff_bgmc_init(AVCodecContext *avctx,
461                          uint8_t **cf_lut, int **cf_lut_status)
462 {
463     *cf_lut        = av_malloc(sizeof(**cf_lut)        * LUT_BUFF * 16 * LUT_SIZE);
464     *cf_lut_status = av_malloc(sizeof(**cf_lut_status) * LUT_BUFF);
465
466     if (!*cf_lut || !*cf_lut_status) {
467         ff_bgmc_end(cf_lut, cf_lut_status);
468         av_log(avctx, AV_LOG_ERROR, "Allocating buffer memory failed.\n");
469         return AVERROR(ENOMEM);
470     } else {
471         // initialize lut_status buffer to a value never used to compare against
472         memset(*cf_lut_status, -1, sizeof(**cf_lut_status) * LUT_BUFF);
473     }
474
475     return 0;
476 }
477
478
479 /** Release the lookup table arrays */
480 av_cold void ff_bgmc_end(uint8_t **cf_lut, int **cf_lut_status)
481 {
482     av_freep(cf_lut);
483     av_freep(cf_lut_status);
484 }
485
486
487 /** Initialize decoding and reads the first value */
488 void ff_bgmc_decode_init(GetBitContext *gb, unsigned int *h,
489                          unsigned int *l, unsigned int *v)
490 {
491     *h = TOP_VALUE;
492     *l = 0;
493     *v = get_bits_long(gb, VALUE_BITS);
494 }
495
496
497 /** Finish decoding */
498 void ff_bgmc_decode_end(GetBitContext *gb)
499 {
500     skip_bits_long(gb, -(VALUE_BITS - 2));
501 }
502
503
504 /** Read and decode a block Gilbert-Moore coded symbol */
505 void ff_bgmc_decode(GetBitContext *gb, unsigned int num, int32_t *dst,
506                     int delta, unsigned int sx,
507                     unsigned int *h, unsigned int *l, unsigned int *v,
508                     uint8_t *cf_lut, int *cf_lut_status)
509 {
510     unsigned int i;
511     uint8_t *lut = bgmc_lut_getp(cf_lut, cf_lut_status, delta);
512
513     // read current state
514     unsigned int high  = *h;
515     unsigned int low   = *l;
516     unsigned int value = *v;
517
518     lut += sx * LUT_SIZE;
519
520     // decode num samples
521     for (i = 0; i < num; i++) {
522         unsigned int range  = high - low + 1;
523         unsigned int target = (((value - low + 1) << FREQ_BITS) - 1) / range;
524         unsigned int symbol = lut[target >> (FREQ_BITS - LUT_BITS)] << delta;
525
526         while (cf_table[sx][symbol] > target)
527             symbol += 1 << delta;
528
529         symbol = (symbol >> delta) - 1;
530
531         high = low + ((range * cf_table[sx][(symbol)     << delta] - (1 << FREQ_BITS)) >> FREQ_BITS);
532         low  = low + ((range * cf_table[sx][(symbol + 1) << delta])                    >> FREQ_BITS);
533
534         while (1) {
535             if (high >= HALF) {
536                 if (low >= HALF) {
537                     value -= HALF;
538                     low   -= HALF;
539                     high  -= HALF;
540                 } else if (low >= FIRST_QTR && high < THIRD_QTR) {
541                     value -= FIRST_QTR;
542                     low   -= FIRST_QTR;
543                     high  -= FIRST_QTR;
544                 } else
545                     break;
546             }
547
548             low  *= 2;
549             high  = 2 * high + 1;
550             value = 2 * value + get_bits1(gb);
551         }
552
553         *dst++ = symbol;
554     }
555
556     // save current state
557     *h = high;
558     *l = low;
559     *v = value;
560 }