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