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