1 /*
2 Copyright (c) 2007-2009, The Musepack Development Team
3 All rights reserved.
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are
7 met:
8
9 * Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11
12 * Redistributions in binary form must reproduce the above
13 copyright notice, this list of conditions and the following
14 disclaimer in the documentation and/or other materials provided
15 with the distribution.
16
17 * Neither the name of the The Musepack Development Team nor the
18 names of its contributors may be used to endorse or promote
19 products derived from this software without specific prior
20 written permission.
21
22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 */
34
35 #include "mpcdec.h"
36 #include "internal.h"
37 #include "huffman.h"
38 #include "mpc_bits_reader.h"
39
40 const mpc_uint32_t Cnk[MAX_ENUM / 2][MAX_ENUM] =
41 {
42 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31},
43 {0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465},
44 {0, 0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540, 1771, 2024, 2300, 2600, 2925, 3276, 3654, 4060, 4495},
45 {0, 0, 0, 0, 1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465},
46 {0, 0, 0, 0, 0, 1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188, 8568, 11628, 15504, 20349, 26334, 33649, 42504, 53130, 65780, 80730, 98280, 118755, 142506, 169911},
47 {0, 0, 0, 0, 0, 0, 1, 7, 28, 84, 210, 462, 924, 1716, 3003, 5005, 8008, 12376, 18564, 27132, 38760, 54264, 74613, 100947, 134596, 177100, 230230, 296010, 376740, 475020, 593775, 736281},
48 {0, 0, 0, 0, 0, 0, 0, 1, 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, 19448, 31824, 50388, 77520, 116280, 170544, 245157, 346104, 480700, 657800, 888030, 1184040, 1560780, 2035800, 2629575},
49 {0, 0, 0, 0, 0, 0, 0, 0, 1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, 43758, 75582, 125970, 203490, 319770, 490314, 735471, 1081575, 1562275, 2220075, 3108105, 4292145, 5852925, 7888725},
50 {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92378, 167960, 293930, 497420, 817190, 1307504, 2042975, 3124550, 4686825, 6906900, 10015005, 14307150, 20160075},
51 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 11, 66, 286, 1001, 3003, 8008, 19448, 43758, 92378, 184756, 352716, 646646, 1144066, 1961256, 3268760, 5311735, 8436285, 13123110, 20030010, 30045015, 44352165},
52 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12, 78, 364, 1365, 4368, 12376, 31824, 75582, 167960, 352716, 705432, 1352078, 2496144, 4457400, 7726160, 13037895, 21474180, 34597290, 54627300, 84672315},
53 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 13, 91, 455, 1820, 6188, 18564, 50388, 125970, 293930, 646646, 1352078, 2704156, 5200300, 9657700, 17383860, 30421755, 51895935, 86493225, 141120525},
54 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 14, 105, 560, 2380, 8568, 27132, 77520, 203490, 497420, 1144066, 2496144, 5200300, 10400600, 20058300, 37442160, 67863915, 119759850, 206253075},
55 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 15, 120, 680, 3060, 11628, 38760, 116280, 319770, 817190, 1961256, 4457400, 9657700, 20058300, 40116600, 77558760, 145422675, 265182525},
56 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 16, 136, 816, 3876, 15504, 54264, 170544, 490314, 1307504, 3268760, 7726160, 17383860, 37442160, 77558760, 155117520, 300540195},
57 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 17, 153, 969, 4845, 20349, 74613, 245157, 735471, 2042975, 5311735, 13037895, 30421755, 67863915, 145422675, 300540195}
58 };
59
60 const mpc_uint8_t Cnk_len[MAX_ENUM / 2][MAX_ENUM] =
61 {
62 {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5},
63 {0, 0, 2, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9},
64 {0, 0, 0, 2, 4, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13},
65 {0, 0, 0, 0, 3, 4, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16},
66 {0, 0, 0, 0, 0, 3, 5, 6, 7, 8, 9, 10, 11, 11, 12, 13, 13, 14, 14, 14, 15, 15, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18},
67 {0, 0, 0, 0, 0, 0, 3, 5, 7, 8, 9, 10, 11, 12, 13, 13, 14, 15, 15, 16, 16, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20},
68 {0, 0, 0, 0, 0, 0, 0, 3, 6, 7, 9, 10, 11, 12, 13, 14, 15, 15, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 21, 22, 22},
69 {0, 0, 0, 0, 0, 0, 0, 0, 4, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 23, 23, 24},
70 {0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 6, 8, 10, 11, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 21, 22, 23, 23, 24, 24, 25, 25},
71 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 7, 9, 10, 12, 13, 15, 16, 17, 18, 19, 20, 21, 21, 22, 23, 24, 24, 25, 25, 26, 26},
72 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 7, 9, 11, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 23, 24, 25, 26, 26, 27, 27},
73 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 7, 9, 11, 13, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 25, 26, 27, 28, 28},
74 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 7, 10, 12, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 27, 28, 29},
75 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 7, 10, 12, 14, 16, 17, 19, 20, 21, 23, 24, 25, 26, 27, 28, 28, 29},
76 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 8, 10, 12, 14, 16, 18, 19, 21, 22, 23, 25, 26, 27, 28, 29, 30},
77 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 8, 10, 13, 15, 17, 18, 20, 21, 23, 24, 25, 27, 28, 29, 30}
78
79 };
80
81 const mpc_uint32_t Cnk_lost[MAX_ENUM / 2][MAX_ENUM] =
82 {
83 {0, 0, 1, 0, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
84 {0, 0, 1, 2, 6, 1, 11, 4, 28, 19, 9, 62, 50, 37, 23, 8, 120, 103, 85, 66, 46, 25, 3, 236, 212, 187, 161, 134, 106, 77, 47, 16},
85 {0, 0, 0, 0, 6, 12, 29, 8, 44, 8, 91, 36, 226, 148, 57, 464, 344, 208, 55, 908, 718, 508, 277, 24, 1796, 1496, 1171, 820, 442, 36, 3697, 3232},
86 {0, 0, 0, 0, 3, 1, 29, 58, 2, 46, 182, 17, 309, 23, 683, 228, 1716, 1036, 220, 3347, 2207, 877, 7529, 5758, 3734, 1434, 15218, 12293, 9017, 5363, 1303, 29576},
87 {0, 0, 0, 0, 0, 2, 11, 8, 2, 4, 50, 232, 761, 46, 1093, 3824, 2004, 7816, 4756, 880, 12419, 6434, 31887, 23032, 12406, 65292, 50342, 32792, 12317, 119638, 92233, 60768},
88 {0, 0, 0, 0, 0, 0, 1, 4, 44, 46, 50, 100, 332, 1093, 3187, 184, 4008, 14204, 5636, 26776, 11272, 56459, 30125, 127548, 85044, 31914, 228278, 147548, 49268, 454801, 312295, 142384},
89 {0, 0, 0, 0, 0, 0, 0, 0, 28, 8, 182, 232, 332, 664, 1757, 4944, 13320, 944, 15148, 53552, 14792, 91600, 16987, 178184, 43588, 390776, 160546, 913112, 536372, 61352, 1564729, 828448},
90 {0, 0, 0, 0, 0, 0, 0, 0, 7, 19, 91, 17, 761, 1093, 1757, 3514, 8458, 21778, 55490, 5102, 58654, 204518, 33974, 313105, 1015577, 534877, 1974229, 1086199, 4096463, 2535683, 499883, 6258916},
91 {0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 9, 36, 309, 46, 3187, 4944, 8458, 16916, 38694, 94184, 230358, 26868, 231386, 789648, 54177, 1069754, 3701783, 1481708, 6762211, 2470066, 13394357, 5505632},
92 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 62, 226, 23, 1093, 184, 13320, 21778, 38694, 77388, 171572, 401930, 953086, 135896, 925544, 3076873, 8340931, 3654106, 13524422, 3509417, 22756699, 2596624},
93 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 50, 148, 683, 3824, 4008, 944, 55490, 94184, 171572, 343144, 745074, 1698160, 3931208, 662448, 3739321, 12080252, 32511574, 12481564, 49545413, 5193248},
94 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 37, 57, 228, 2004, 14204, 15148, 5102, 230358, 401930, 745074, 1490148, 3188308, 7119516, 16170572, 3132677, 15212929, 47724503, 127314931, 42642616},
95 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 23, 464, 1716, 7816, 5636, 53552, 58654, 26868, 953086, 1698160, 3188308, 6376616, 13496132, 29666704, 66353813, 14457878, 62182381, 189497312},
96 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 344, 1036, 4756, 26776, 14792, 204518, 231386, 135896, 3931208, 7119516, 13496132, 26992264, 56658968, 123012781, 3252931, 65435312},
97 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 120, 208, 220, 880, 11272, 91600, 33974, 789648, 925544, 662448, 16170572, 29666704, 56658968, 113317936, 236330717, 508019104},
98 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 103, 55, 3347, 12419, 56459, 16987, 313105, 54177, 3076873, 3739321, 3132677, 66353813, 123012781, 236330717}
99 };
100
101 static const mpc_uint8_t log2_tab[32] =
102 { 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6};
103
104 static const mpc_uint8_t log2_lost[32] =
105 { 0, 1, 0, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 31};
106
mpc_bits_golomb_dec(mpc_bits_reader * r,const mpc_uint_t k)107 mpc_int32_t mpc_bits_golomb_dec(mpc_bits_reader * r, const mpc_uint_t k)
108 {
109 unsigned int l = 0;
110 unsigned int code = r->buff[0] & ((1 << r->count) - 1);
111
112 while( code == 0 ) {
113 l += r->count;
114 r->buff++;
115 code = r->buff[0];
116 r->count = 8;
117 }
118
119 while( ((1 << (r->count - 1)) & code) == 0 ) {
120 l++;
121 r->count--;
122 }
123 r->count--;
124
125 while( r->count < k ) {
126 r->buff++;
127 r->count += 8;
128 code = (code << 8) | r->buff[0];
129 }
130
131 r->count -= k;
132
133 return (l << k) | ((code >> r->count) & ((1 << k) - 1));
134 }
135
mpc_bits_log_dec(mpc_bits_reader * r,mpc_uint_t max)136 mpc_uint32_t mpc_bits_log_dec(mpc_bits_reader * r, mpc_uint_t max)
137 {
138 mpc_uint32_t value = 0;
139 if (max == 0)
140 return 0;
141 if (log2_tab[max - 1] > 1)
142 value = mpc_bits_read(r, log2_tab[max - 1] - 1);
143 if (value >= log2_lost[max - 1])
144 value = ((value << 1) | mpc_bits_read(r, 1)) - log2_lost[max - 1];
145 return value;
146 }
147
mpc_bits_get_size(mpc_bits_reader * r,mpc_uint64_t * p_size)148 unsigned int mpc_bits_get_size(mpc_bits_reader * r, mpc_uint64_t * p_size)
149 {
150 unsigned char tmp;
151 mpc_uint64_t size = 0;
152 unsigned int ret = 0;
153
154 do {
155 tmp = mpc_bits_read(r, 8);
156 size = (size << 7) | (tmp & 0x7F);
157 ret++;
158 } while((tmp & 0x80));
159
160 *p_size = size;
161 return ret;
162 }
163
mpc_bits_get_block(mpc_bits_reader * r,mpc_block * p_block)164 int mpc_bits_get_block(mpc_bits_reader * r, mpc_block * p_block)
165 {
166 int size = 2;
167
168 p_block->size = 0;
169 p_block->key[0] = mpc_bits_read(r, 8);
170 p_block->key[1] = mpc_bits_read(r, 8);
171
172 size += mpc_bits_get_size(r, &(p_block->size));
173
174 if (p_block->size >= size) // check if the block size doesn't conflict with the header size
175 p_block->size -= size;
176
177 return size;
178 }
179
180
181
182