bgmc.c
Go to the documentation of this file.
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 
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 
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 
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 
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 
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
478  // against
479  memset(*cf_lut_status, -1, sizeof(*cf_lut_status) * LUT_BUFF);
480  }
481 
482  return 0;
483 }
484 
485 
488 void ff_bgmc_end(uint8_t **cf_lut, int **cf_lut_status)
489 {
490  av_freep(cf_lut);
491  av_freep(cf_lut_status);
492 }
493 
494 
498  unsigned int *h, unsigned int *l, unsigned int *v)
499 {
500  *h = TOP_VALUE;
501  *l = 0;
502  *v = get_bits_long(gb, VALUE_BITS);
503 }
504 
505 
509 {
510  skip_bits_long(gb, -(VALUE_BITS - 2));
511 }
512 
513 
516 void ff_bgmc_decode(GetBitContext *gb, unsigned int num, int32_t *dst,
517  int delta, unsigned int sx,
518  unsigned int *h, unsigned int *l, unsigned int *v,
519  uint8_t *cf_lut, int *cf_lut_status)
520 {
521  unsigned int i;
522  uint8_t *lut = bgmc_lut_getp(cf_lut, cf_lut_status, delta);
523 
524  // read current state
525  unsigned int high = *h;
526  unsigned int low = *l;
527  unsigned int value = *v;
528 
529  lut += sx * LUT_SIZE;
530 
531  // decode num samples
532  for (i = 0; i < num; i++) {
533  unsigned int range = high - low + 1;
534  unsigned int target = (((value - low + 1) << FREQ_BITS) - 1) / range;
535  unsigned int symbol = lut[target >> (FREQ_BITS - LUT_BITS)] << delta;
536 
537  while (cf_table[sx][symbol] > target)
538  symbol += 1 << delta;
539 
540  symbol = (symbol >> delta) - 1;
541 
542  high = low + ((range * cf_table[sx][(symbol ) << delta] - (1 << FREQ_BITS)) >> FREQ_BITS);
543  low = low + ((range * cf_table[sx][(symbol + 1) << delta] ) >> FREQ_BITS);
544 
545  while (1) {
546  if (high >= HALF) {
547  if (low >= HALF) {
548  value -= HALF;
549  low -= HALF;
550  high -= HALF;
551  } else if (low >= FIRST_QTR && high < THIRD_QTR) {
552  value -= FIRST_QTR;
553  low -= FIRST_QTR;
554  high -= FIRST_QTR;
555  } else break;
556  }
557 
558  low *= 2;
559  high = 2 * high + 1;
560  value = 2 * value + get_bits1(gb);
561  }
562 
563  *dst++ = symbol;
564  }
565 
566  // save current state
567  *h = high;
568  *l = low;
569  *v = value;
570 }