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