?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
FS#8961 - Anti-Aliased Fonts.
[kugel-rb/myfork.git] / apps / codecs / libwavpack / words.c
blob6da716119cf8f1ddc9263899e6955c8b71667947
1 ////////////////////////////////////////////////////////////////////////////
2 // **** WAVPACK **** //
3 // Hybrid Lossless Wavefile Compressor //
4 // Copyright (c) 1998 - 2004 Conifer Software. //
5 // All Rights Reserved. //
6 ////////////////////////////////////////////////////////////////////////////
7
8 // words.c
9
10 // This module provides entropy word encoding and decoding functions using
11 // a variation on the Rice method. This was introduced in version 3.93
12 // because it allows splitting the data into a "lossy" stream and a
13 // "correction" stream in a very efficient manner and is therefore ideal
14 // for the "hybrid" mode. For 4.0, the efficiency of this method was
15 // significantly improved by moving away from the normal Rice restriction of
16 // using powers of two for the modulus divisions and now the method can be
17 // used for both hybrid and pure lossless encoding.
18
19 // Samples are divided by median probabilities at 5/7 (71.43%), 10/49 (20.41%),
20 // and 20/343 (5.83%). Each zone has 3.5 times fewer samples than the
21 // previous. Using standard Rice coding on this data would result in 1.4
22 // bits per sample average (not counting sign bit). However, there is a
23 // very simple encoding that is over 99% efficient with this data and
24 // results in about 1.22 bits per sample.
25
26 #include "wavpack.h"
27
28 #include <string.h>
29
30 //////////////////////////////// local macros /////////////////////////////////
31
32 #define LIMIT_ONES 16 // maximum consecutive 1s sent for "div" data
33
34 // these control the time constant "slow_level" which is used for hybrid mode
35 // that controls bitrate as a function of residual level (HYBRID_BITRATE).
36 #define SLS 8
37 #define SLO ((1 << (SLS - 1)))
38
39 // these control the time constant of the 3 median level breakpoints
40 #define DIV0 128 // 5/7 of samples
41 #define DIV1 64 // 10/49 of samples
42 #define DIV2 32 // 20/343 of samples
43
44 // this macro retrieves the specified median breakpoint (without frac; min = 1)
45 #define GET_MED(med) (((c->median [med]) >> 4) + 1)
46
47 // These macros update the specified median breakpoints. Note that the median
48 // is incremented when the sample is higher than the median, else decremented.
49 // They are designed so that the median will never drop below 1 and the value
50 // is essentially stationary if there are 2 increments for every 5 decrements.
51
52 #define INC_MED0() (c->median [0] += ((c->median [0] + DIV0) / DIV0) * 5)
53 #define DEC_MED0() (c->median [0] -= ((c->median [0] + (DIV0-2)) / DIV0) * 2)
54 #define INC_MED1() (c->median [1] += ((c->median [1] + DIV1) / DIV1) * 5)
55 #define DEC_MED1() (c->median [1] -= ((c->median [1] + (DIV1-2)) / DIV1) * 2)
56 #define INC_MED2() (c->median [2] += ((c->median [2] + DIV2) / DIV2) * 5)
57 #define DEC_MED2() (c->median [2] -= ((c->median [2] + (DIV2-2)) / DIV2) * 2)
58
59 #define count_bits(av) ( \
60 (av) < (1 << 8) ? nbits_table [av] : \
61 ( \
62 (av) < (1L << 16) ? nbits_table [(av) >> 8] + 8 : \
63 ((av) < (1L << 24) ? nbits_table [(av) >> 16] + 16 : nbits_table [(av) >> 24] + 24) \
64 ) \
65 )
66
67 ///////////////////////////// local table storage ////////////////////////////
68
69 const char nbits_table [] = {
70 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, // 0 - 15
71 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 16 - 31
72 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 32 - 47
73 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 48 - 63
74 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 64 - 79
75 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 80 - 95
76 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 96 - 111
77 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 112 - 127
78 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 128 - 143
79 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 144 - 159
80 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 160 - 175
81 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 176 - 191
82 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 192 - 207
83 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 208 - 223
84 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 224 - 239
85 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 // 240 - 255
86 };
87
88 static const uchar log2_table [] = {
89 0x00, 0x01, 0x03, 0x04, 0x06, 0x07, 0x09, 0x0a, 0x0b, 0x0d, 0x0e, 0x10, 0x11, 0x12, 0x14, 0x15,
90 0x16, 0x18, 0x19, 0x1a, 0x1c, 0x1d, 0x1e, 0x20, 0x21, 0x22, 0x24, 0x25, 0x26, 0x28, 0x29, 0x2a,
91 0x2c, 0x2d, 0x2e, 0x2f, 0x31, 0x32, 0x33, 0x34, 0x36, 0x37, 0x38, 0x39, 0x3b, 0x3c, 0x3d, 0x3e,
92 0x3f, 0x41, 0x42, 0x43, 0x44, 0x45, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4d, 0x4e, 0x4f, 0x50, 0x51,
93 0x52, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62, 0x63,
94 0x64, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x74, 0x75,
95 0x76, 0x77, 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 0x84, 0x85,
96 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95,
97 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
98 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 0xb0, 0xb1, 0xb2, 0xb2,
99 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc0,
100 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcb, 0xcc, 0xcd, 0xce,
101 0xcf, 0xd0, 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd8, 0xd9, 0xda, 0xdb,
102 0xdc, 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe4, 0xe5, 0xe6, 0xe7, 0xe7,
103 0xe8, 0xe9, 0xea, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xee, 0xef, 0xf0, 0xf1, 0xf1, 0xf2, 0xf3, 0xf4,
104 0xf4, 0xf5, 0xf6, 0xf7, 0xf7, 0xf8, 0xf9, 0xf9, 0xfa, 0xfb, 0xfc, 0xfc, 0xfd, 0xfe, 0xff, 0xff
105 };
106
107 static const uchar exp2_table [] = {
108 0x00, 0x01, 0x01, 0x02, 0x03, 0x03, 0x04, 0x05, 0x06, 0x06, 0x07, 0x08, 0x08, 0x09, 0x0a, 0x0b,
109 0x0b, 0x0c, 0x0d, 0x0e, 0x0e, 0x0f, 0x10, 0x10, 0x11, 0x12, 0x13, 0x13, 0x14, 0x15, 0x16, 0x16,
110 0x17, 0x18, 0x19, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1d, 0x1e, 0x1f, 0x20, 0x20, 0x21, 0x22, 0x23,
111 0x24, 0x24, 0x25, 0x26, 0x27, 0x28, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2c, 0x2d, 0x2e, 0x2f, 0x30,
112 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3a, 0x3b, 0x3c, 0x3d,
113 0x3e, 0x3f, 0x40, 0x41, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x48, 0x49, 0x4a, 0x4b,
114 0x4c, 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a,
115 0x5b, 0x5c, 0x5d, 0x5e, 0x5e, 0x5f, 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69,
116 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79,
117 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x87, 0x88, 0x89, 0x8a,
118 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 0x90, 0x91, 0x92, 0x93, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b,
119 0x9c, 0x9d, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad,
120 0xaf, 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0,
121 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc8, 0xc9, 0xca, 0xcb, 0xcd, 0xce, 0xcf, 0xd0, 0xd2, 0xd3, 0xd4,
122 0xd6, 0xd7, 0xd8, 0xd9, 0xdb, 0xdc, 0xdd, 0xde, 0xe0, 0xe1, 0xe2, 0xe4, 0xe5, 0xe6, 0xe8, 0xe9,
123 0xea, 0xec, 0xed, 0xee, 0xf0, 0xf1, 0xf2, 0xf4, 0xf5, 0xf6, 0xf8, 0xf9, 0xfa, 0xfc, 0xfd, 0xff
124 };
125
126 static const char ones_count_table [] = {
127 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
128 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
129 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
130 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,
131 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
132 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
133 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
134 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,8
135 };
136
137 ///////////////////////////// executable code ////////////////////////////////
138
139 void init_words (WavpackStream *wps)
140 {
141 CLEAR (wps->w);
142 }
143
144 static int mylog2 (unsigned int32_t avalue);
145
146 // Read the median log2 values from the specifed metadata structure, convert
147 // them back to 32-bit unsigned values and store them. If length is not
148 // exactly correct then we flag and return an error.
149
150 int read_entropy_vars (WavpackStream *wps, WavpackMetadata *wpmd)
151 {
152 uchar *byteptr = wpmd->data;
153
154 if (wpmd->byte_length != ((wps->wphdr.flags & MONO_DATA) ? 6 : 12))
155 return FALSE;
156
157 wps->w.c [0].median [0] = exp2s (byteptr [0] + (byteptr [1] << 8));
158 wps->w.c [0].median [1] = exp2s (byteptr [2] + (byteptr [3] << 8));
159 wps->w.c [0].median [2] = exp2s (byteptr [4] + (byteptr [5] << 8));
160
161 if (!(wps->wphdr.flags & MONO_DATA)) {
162 wps->w.c [1].median [0] = exp2s (byteptr [6] + (byteptr [7] << 8));
163 wps->w.c [1].median [1] = exp2s (byteptr [8] + (byteptr [9] << 8));
164 wps->w.c [1].median [2] = exp2s (byteptr [10] + (byteptr [11] << 8));
165 }
166
167 return TRUE;
168 }
169
170 // Allocates the correct space in the metadata structure and writes the
171 // current median values to it. Values are converted from 32-bit unsigned
172 // to our internal 16-bit mylog2 values, and read_entropy_vars () is called
173 // to read the values back because we must compensate for the loss through
174 // the log function.
175
176 void write_entropy_vars (WavpackStream *wps, WavpackMetadata *wpmd)
177 {
178 uchar *byteptr;
179 int temp;
180
181 byteptr = wpmd->data = wpmd->temp_data;
182 wpmd->id = ID_ENTROPY_VARS;
183
184 *byteptr++ = temp = mylog2 (wps->w.c [0].median [0]);
185 *byteptr++ = temp >> 8;
186 *byteptr++ = temp = mylog2 (wps->w.c [0].median [1]);
187 *byteptr++ = temp >> 8;
188 *byteptr++ = temp = mylog2 (wps->w.c [0].median [2]);
189 *byteptr++ = temp >> 8;
190
191 if (!(wps->wphdr.flags & MONO_FLAG)) {
192 *byteptr++ = temp = mylog2 (wps->w.c [1].median [0]);
193 *byteptr++ = temp >> 8;
194 *byteptr++ = temp = mylog2 (wps->w.c [1].median [1]);
195 *byteptr++ = temp >> 8;
196 *byteptr++ = temp = mylog2 (wps->w.c [1].median [2]);
197 *byteptr++ = temp >> 8;
198 }
199
200 wpmd->byte_length = byteptr - (uchar *) wpmd->data;
201 read_entropy_vars (wps, wpmd);
202 }
203
204 // Read the hybrid related values from the specifed metadata structure, convert
205 // them back to their internal formats and store them. The extended profile
206 // stuff is not implemented yet, so return an error if we get more data than
207 // we know what to do with.
208
209 int read_hybrid_profile (WavpackStream *wps, WavpackMetadata *wpmd)
210 {
211 uchar *byteptr = wpmd->data;
212 uchar *endptr = byteptr + wpmd->byte_length;
213
214 if (wps->wphdr.flags & HYBRID_BITRATE) {
215 wps->w.c [0].slow_level = exp2s (byteptr [0] + (byteptr [1] << 8));
216 byteptr += 2;
217
218 if (!(wps->wphdr.flags & MONO_DATA)) {
219 wps->w.c [1].slow_level = exp2s (byteptr [0] + (byteptr [1] << 8));
220 byteptr += 2;
221 }
222 }
223
224 wps->w.bitrate_acc [0] = (int32_t)(byteptr [0] + (byteptr [1] << 8)) << 16;
225 byteptr += 2;
226
227 if (!(wps->wphdr.flags & MONO_DATA)) {
228 wps->w.bitrate_acc [1] = (int32_t)(byteptr [0] + (byteptr [1] << 8)) << 16;
229 byteptr += 2;
230 }
231
232 if (byteptr < endptr) {
233 wps->w.bitrate_delta [0] = exp2s ((short)(byteptr [0] + (byteptr [1] << 8)));
234 byteptr += 2;
235
236 if (!(wps->wphdr.flags & MONO_DATA)) {
237 wps->w.bitrate_delta [1] = exp2s ((short)(byteptr [0] + (byteptr [1] << 8)));
238 byteptr += 2;
239 }
240
241 if (byteptr < endptr)
242 return FALSE;
243 }
244 else
245 wps->w.bitrate_delta [0] = wps->w.bitrate_delta [1] = 0;
246
247 return TRUE;
248 }
249
250 // This function is called during both encoding and decoding of hybrid data to
251 // update the "error_limit" variable which determines the maximum sample error
252 // allowed in the main bitstream. In the HYBRID_BITRATE mode (which is the only
253 // currently implemented) this is calculated from the slow_level values and the
254 // bitrate accumulators. Note that the bitrate accumulators can be changing.
255
256 static void update_error_limit (struct words_data *w, uint32_t flags)
257 {
258 int bitrate_0 = (w->bitrate_acc [0] += w->bitrate_delta [0]) >> 16;
259
260 if (flags & MONO_DATA) {
261 if (flags & HYBRID_BITRATE) {
262 int slow_log_0 = (w->c [0].slow_level + SLO) >> SLS;
263
264 if (slow_log_0 - bitrate_0 > -0x100)
265 w->c [0].error_limit = exp2s (slow_log_0 - bitrate_0 + 0x100);
266 else
267 w->c [0].error_limit = 0;
268 }
269 else
270 w->c [0].error_limit = exp2s (bitrate_0);
271 }
272 else {
273 int bitrate_1 = (w->bitrate_acc [1] += w->bitrate_delta [1]) >> 16;
274
275 if (flags & HYBRID_BITRATE) {
276 int slow_log_0 = (w->c [0].slow_level + SLO) >> SLS;
277 int slow_log_1 = (w->c [1].slow_level + SLO) >> SLS;
278
279 if (flags & HYBRID_BALANCE) {
280 int balance = (slow_log_1 - slow_log_0 + bitrate_1 + 1) >> 1;
281
282 if (balance > bitrate_0) {
283 bitrate_1 = bitrate_0 * 2;
284 bitrate_0 = 0;
285 }
286 else if (-balance > bitrate_0) {
287 bitrate_0 = bitrate_0 * 2;
288 bitrate_1 = 0;
289 }
290 else {
291 bitrate_1 = bitrate_0 + balance;
292 bitrate_0 = bitrate_0 - balance;
293 }
294 }
295
296 if (slow_log_0 - bitrate_0 > -0x100)
297 w->c [0].error_limit = exp2s (slow_log_0 - bitrate_0 + 0x100);
298 else
299 w->c [0].error_limit = 0;
300
301 if (slow_log_1 - bitrate_1 > -0x100)
302 w->c [1].error_limit = exp2s (slow_log_1 - bitrate_1 + 0x100);
303 else
304 w->c [1].error_limit = 0;
305 }
306 else {
307 w->c [0].error_limit = exp2s (bitrate_0);
308 w->c [1].error_limit = exp2s (bitrate_1);
309 }
310 }
311 }
312
313 static uint32_t read_code (Bitstream *bs, uint32_t maxcode);
314
315 // Read the next word from the bitstream "wvbits" and return the value. This
316 // function can be used for hybrid or lossless streams, but since an
317 // optimized version is available for lossless this function would normally
318 // be used for hybrid only. If a hybrid lossless stream is being read then
319 // the "correction" offset is written at the specified pointer. A return value
320 // of WORD_EOF indicates that the end of the bitstream was reached (all 1s) or
321 // some other error occurred.
322
323 int32_t get_words (int32_t *buffer, int nsamples, uint32_t flags,
324 struct words_data *w, Bitstream *bs)
325 {
326 register struct entropy_data *c = w->c;
327 int csamples;
328
329 if (!(flags & MONO_DATA))
330 nsamples *= 2;
331
332 for (csamples = 0; csamples < nsamples; ++csamples) {
333 uint32_t ones_count, low, mid, high;
334
335 if (!(flags & MONO_DATA))
336 c = w->c + (csamples & 1);
337
338 if (!(w->c [0].median [0] & ~1) && !w->holding_zero && !w->holding_one && !(w->c [1].median [0] & ~1)) {
339 uint32_t mask;
340 int cbits;
341
342 if (w->zeros_acc) {
343 if (--w->zeros_acc) {
344 c->slow_level -= (c->slow_level + SLO) >> SLS;
345 *buffer++ = 0;
346 continue;
347 }
348 }
349 else {
350 for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);
351
352 if (cbits == 33)
353 break;
354
355 if (cbits < 2)
356 w->zeros_acc = cbits;
357 else {
358 for (mask = 1, w->zeros_acc = 0; --cbits; mask <<= 1)
359 if (getbit (bs))
360 w->zeros_acc |= mask;
361
362 w->zeros_acc |= mask;
363 }
364
365 if (w->zeros_acc) {
366 c->slow_level -= (c->slow_level + SLO) >> SLS;
367 CLEAR (w->c [0].median);
368 CLEAR (w->c [1].median);
369 *buffer++ = 0;
370 continue;
371 }
372 }
373 }
374
375 if (w->holding_zero)
376 ones_count = w->holding_zero = 0;
377 else {
378 int next8;
379
380 if (bs->bc < 8) {
381 if (++(bs->ptr) == bs->end)
382 bs->wrap (bs);
383
384 next8 = (bs->sr |= *(bs->ptr) << bs->bc) & 0xff;
385 bs->bc += 8;
386 }
387 else
388 next8 = bs->sr & 0xff;
389
390 if (next8 == 0xff) {
391 bs->bc -= 8;
392 bs->sr >>= 8;
393
394 for (ones_count = 8; ones_count < (LIMIT_ONES + 1) && getbit (bs); ++ones_count);
395
396 if (ones_count == (LIMIT_ONES + 1))
397 break;
398
399 if (ones_count == LIMIT_ONES) {
400 uint32_t mask;
401 int cbits;
402
403 for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);
404
405 if (cbits == 33)
406 break;
407
408 if (cbits < 2)
409 ones_count = cbits;
410 else {
411 for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
412 if (getbit (bs))
413 ones_count |= mask;
414
415 ones_count |= mask;
416 }
417
418 ones_count += LIMIT_ONES;
419 }
420 }
421 else {
422 bs->bc -= (ones_count = ones_count_table [next8]) + 1;
423 bs->sr >>= ones_count + 1;
424 }
425
426 if (w->holding_one) {
427 w->holding_one = ones_count & 1;
428 ones_count = (ones_count >> 1) + 1;
429 }
430 else {
431 w->holding_one = ones_count & 1;
432 ones_count >>= 1;
433 }
434
435 w->holding_zero = ~w->holding_one & 1;
436 }
437
438 if ((flags & HYBRID_FLAG) && ((flags & MONO_DATA) || !(csamples & 1)))
439 update_error_limit (w, flags);
440
441 if (ones_count == 0) {
442 low = 0;
443 high = GET_MED (0) - 1;
444 DEC_MED0 ();
445 }
446 else {
447 low = GET_MED (0);
448 INC_MED0 ();
449
450 if (ones_count == 1) {
451 high = low + GET_MED (1) - 1;
452 DEC_MED1 ();
453 }
454 else {
455 low += GET_MED (1);
456 INC_MED1 ();
457
458 if (ones_count == 2) {
459 high = low + GET_MED (2) - 1;
460 DEC_MED2 ();
461 }
462 else {
463 low += (ones_count - 2) * GET_MED (2);
464 high = low + GET_MED (2) - 1;
465 INC_MED2 ();
466 }
467 }
468 }
469
470 mid = (high + low + 1) >> 1;
471
472 if (!c->error_limit)
473 mid = read_code (bs, high - low) + low;
474 else while (high - low > c->error_limit) {
475 if (getbit (bs))
476 mid = (high + (low = mid) + 1) >> 1;
477 else
478 mid = ((high = mid - 1) + low + 1) >> 1;
479 }
480
481 *buffer++ = getbit (bs) ? ~mid : mid;
482
483 if (flags & HYBRID_BITRATE)
484 c->slow_level = c->slow_level - ((c->slow_level + SLO) >> SLS) + mylog2 (mid);
485 }
486
487 return (flags & MONO_DATA) ? csamples : (csamples / 2);
488 }
489
490 // Read a single unsigned value from the specified bitstream with a value
491 // from 0 to maxcode. If there are exactly a power of two number of possible
492 // codes then this will read a fixed number of bits; otherwise it reads the
493 // minimum number of bits and then determines whether another bit is needed
494 // to define the code.
495
496 static uint32_t read_code (Bitstream *bs, uint32_t maxcode)
497 {
498 int bitcount = count_bits (maxcode);
499 uint32_t extras = (1L << bitcount) - maxcode - 1, code;
500
501 if (!bitcount)
502 return 0;
503
504 getbits (&code, bitcount - 1, bs);
505 code &= (1L << (bitcount - 1)) - 1;
506
507 if (code >= extras) {
508 code = (code << 1) - extras;
509
510 if (getbit (bs))
511 ++code;
512 }
513
514 return code;
515 }
516
517 void send_words (int32_t *buffer, int nsamples, uint32_t flags,
518 struct words_data *w, Bitstream *bs)
519 {
520 register struct entropy_data *c = w->c;
521
522 if (!(flags & MONO_FLAG))
523 nsamples *= 2;
524
525 while (nsamples--) {
526 int32_t value = *buffer++;
527 int sign = (value < 0) ? 1 : 0;
528 uint32_t ones_count, low, high;
529
530 if (!(flags & MONO_FLAG))
531 c = w->c + (~nsamples & 1);
532
533 if (!(w->c [0].median [0] & ~1) && !w->holding_zero && !(w->c [1].median [0] & ~1)) {
534 if (w->zeros_acc) {
535 if (value)
536 flush_word (w, bs);
537 else {
538 w->zeros_acc++;
539 continue;
540 }
541 }
542 else if (value) {
543 putbit_0 (bs);
544 }
545 else {
546 CLEAR (w->c [0].median);
547 CLEAR (w->c [1].median);
548 w->zeros_acc = 1;
549 continue;
550 }
551 }
552
553 if (sign)
554 value = ~value;
555
556 if ((unsigned int32_t) value < GET_MED (0)) {
557 ones_count = low = 0;
558 high = GET_MED (0) - 1;
559 DEC_MED0 ();
560 }
561 else {
562 low = GET_MED (0);
563 INC_MED0 ();
564
565 if (value - low < GET_MED (1)) {
566 ones_count = 1;
567 high = low + GET_MED (1) - 1;
568 DEC_MED1 ();
569 }
570 else {
571 low += GET_MED (1);
572 INC_MED1 ();
573
574 if (value - low < GET_MED (2)) {
575 ones_count = 2;
576 high = low + GET_MED (2) - 1;
577 DEC_MED2 ();
578 }
579 else {
580 ones_count = 2 + (value - low) / GET_MED (2);
581 low += (ones_count - 2) * GET_MED (2);
582 high = low + GET_MED (2) - 1;
583 INC_MED2 ();
584 }
585 }
586 }
587
588 if (w->holding_zero) {
589 if (ones_count)
590 w->holding_one++;
591
592 flush_word (w, bs);
593
594 if (ones_count) {
595 w->holding_zero = 1;
596 ones_count--;
597 }
598 else
599 w->holding_zero = 0;
600 }
601 else
602 w->holding_zero = 1;
603
604 w->holding_one = ones_count * 2;
605
606 if (high != low) {
607 uint32_t maxcode = high - low, code = value - low;
608 int bitcount = count_bits (maxcode);
609 uint32_t extras = (1L << bitcount) - maxcode - 1;
610
611 if (code < extras) {
612 w->pend_data |= code << w->pend_count;
613 w->pend_count += bitcount - 1;
614 }
615 else {
616 w->pend_data |= ((code + extras) >> 1) << w->pend_count;
617 w->pend_count += bitcount - 1;
618 w->pend_data |= ((code + extras) & 1) << w->pend_count++;
619 }
620 }
621
622 w->pend_data |= ((int32_t) sign << w->pend_count++);
623
624 if (!w->holding_zero)
625 flush_word (w, bs);
626 }
627 }
628
629 // Used by send_word() and send_word_lossless() to actually send most the
630 // accumulated data onto the bitstream. This is also called directly from
631 // clients when all words have been sent.
632
633 void flush_word (struct words_data *w, Bitstream *bs)
634 {
635 int cbits;
636
637 if (w->zeros_acc) {
638 cbits = count_bits (w->zeros_acc);
639
640 while (cbits--) {
641 putbit_1 (bs);
642 }
643
644 putbit_0 (bs);
645
646 while (w->zeros_acc > 1) {
647 putbit (w->zeros_acc & 1, bs);
648 w->zeros_acc >>= 1;
649 }
650
651 w->zeros_acc = 0;
652 }
653
654 if (w->holding_one) {
655 if (w->holding_one >= LIMIT_ONES) {
656 putbits ((1L << LIMIT_ONES) - 1, LIMIT_ONES + 1, bs);
657 w->holding_one -= LIMIT_ONES;
658 cbits = count_bits (w->holding_one);
659
660 while (cbits--) {
661 putbit_1 (bs);
662 }
663
664 putbit_0 (bs);
665
666 while (w->holding_one > 1) {
667 putbit (w->holding_one & 1, bs);
668 w->holding_one >>= 1;
669 }
670
671 w->holding_zero = 0;
672 }
673 else
674 putbits ((1L << w->holding_one) - 1, w->holding_one, bs);
675
676 w->holding_one = 0;
677 }
678
679 if (w->holding_zero) {
680 putbit_0 (bs);
681 w->holding_zero = 0;
682 }
683
684 if (w->pend_count) {
685
686 while (w->pend_count > 24) {
687 putbit (w->pend_data & 1, bs);
688 w->pend_data >>= 1;
689 w->pend_count--;
690 }
691
692 putbits (w->pend_data, w->pend_count, bs);
693 w->pend_data = w->pend_count = 0;
694 }
695 }
696
697 // The concept of a base 2 logarithm is used in many parts of WavPack. It is
698 // a way of sufficiently accurately representing 32-bit signed and unsigned
699 // values storing only 16 bits (actually fewer). It is also used in the hybrid
700 // mode for quickly comparing the relative magnitude of large values (i.e.
701 // division) and providing smooth exponentials using only addition.
702
703 // These are not strict logarithms in that they become linear around zero and
704 // can therefore represent both zero and negative values. They have 8 bits
705 // of precision and in "roundtrip" conversions the total error never exceeds 1
706 // part in 225 except for the cases of +/-115 and +/-195 (which error by 1).
707
708
709 // This function returns the log2 for the specified 32-bit unsigned value.
710 // The maximum value allowed is about 0xff800000 and returns 8447.
711
712 static int mylog2 (unsigned int32_t avalue)
713 {
714 int dbits;
715
716 if ((avalue += avalue >> 9) < (1 << 8)) {
717 dbits = nbits_table [avalue];
718 return (dbits << 8) + log2_table [(avalue << (9 - dbits)) & 0xff];
719 }
720 else {
721 if (avalue < (1L << 16))
722 dbits = nbits_table [avalue >> 8] + 8;
723 else if (avalue < (1L << 24))
724 dbits = nbits_table [avalue >> 16] + 16;
725 else
726 dbits = nbits_table [avalue >> 24] + 24;
727
728 return (dbits << 8) + log2_table [(avalue >> (dbits - 9)) & 0xff];
729 }
730 }
731
732 // This function returns the log2 for the specified 32-bit signed value.
733 // All input values are valid and the return values are in the range of
734 // +/- 8192.
735
736 int log2s (int32_t value)
737 {
738 return (value < 0) ? -mylog2 (-value) : mylog2 (value);
739 }
740
741 // This function returns the original integer represented by the supplied
742 // logarithm (at least within the provided accuracy). The log is signed,
743 // but since a full 32-bit value is returned this can be used for unsigned
744 // conversions as well (i.e. the input range is -8192 to +8447).
745
746 int32_t exp2s (int log)
747 {
748 uint32_t value;
749
750 if (log < 0)
751 return -exp2s (-log);
752
753 value = exp2_table [log & 0xff] | 0x100;
754
755 if ((log >>= 8) <= 9)
756 return value >> (9 - log);
757 else
758 return value << (log - 9);
759 }
760
761 // These two functions convert internal weights (which are normally +/-1024)
762 // to and from an 8-bit signed character version for storage in metadata. The
763 // weights are clipped here in the case that they are outside that range.
764
765 signed char store_weight (int weight)
766 {
767 if (weight > 1024)
768 weight = 1024;
769 else if (weight < -1024)
770 weight = -1024;
771
772 if (weight > 0)
773 weight -= (weight + 64) >> 7;
774
775 return (weight + 4) >> 3;
776 }
777
778 int restore_weight (signed char weight)
779 {
780 int result;
781
782 if ((result = (int) weight << 3) > 0)
783 result += (result + 64) >> 7;
784
785 return result;
786 }