1 | /**************************************************************************
|
---|
2 | *
|
---|
3 | * arithcode.c -- Arithmetic coding
|
---|
4 | * Copyright (C) 1994 Alistair Moffat
|
---|
5 | *
|
---|
6 | * This program is free software; you can redistribute it and/or modify
|
---|
7 | * it under the terms of the GNU General Public License as published by
|
---|
8 | * the Free Software Foundation; either version 2 of the License, or
|
---|
9 | * (at your option) any later version.
|
---|
10 | *
|
---|
11 | * This program is distributed in the hope that it will be useful,
|
---|
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
14 | * GNU General Public License for more details.
|
---|
15 | *
|
---|
16 | * You should have received a copy of the GNU General Public License
|
---|
17 | * along with this program; if not, write to the Free Software
|
---|
18 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
---|
19 | *
|
---|
20 | *
|
---|
21 | * $Id: arithcode.c 16583 2008-07-29 10:20:36Z davidb $
|
---|
22 | *
|
---|
23 | **************************************************************************
|
---|
24 | *
|
---|
25 | * Arithmetic encoding. Taken largely from Witten, Neal, Cleary,
|
---|
26 | * CACM, 1987, p520.
|
---|
27 | * Includes bitfiddling routines.
|
---|
28 | *
|
---|
29 | **************************************************************************/
|
---|
30 |
|
---|
31 | #include "sysfuncs.h"
|
---|
32 | #include "arithcode.h"
|
---|
33 |
|
---|
34 |
|
---|
35 | FILE *arith_in, *arith_out;
|
---|
36 |
|
---|
37 | /*
|
---|
38 | $log$
|
---|
39 | */
|
---|
40 |
|
---|
41 | static char *RCSID = "$Id: arithcode.c 16583 2008-07-29 10:20:36Z davidb $";
|
---|
42 |
|
---|
43 | #undef BECAREFUL
|
---|
44 | #define INTEGRATED
|
---|
45 |
|
---|
46 |
|
---|
47 | codevalue S_low = 0, S_high = 0, S_value = 0;
|
---|
48 | long S_bitstofollow = 0;
|
---|
49 | int S_buffer = 0, S_bitstogo = 0;
|
---|
50 |
|
---|
51 | long cmpbytes = 0, rawbytes = 0;
|
---|
52 |
|
---|
53 | #ifdef INTEGRATED
|
---|
54 | long CountOfBitsOut;
|
---|
55 | #endif
|
---|
56 |
|
---|
57 |
|
---|
58 | /*==================================*/
|
---|
59 |
|
---|
60 | #define BITPLUSFOLLOW(b) \
|
---|
61 | { OUTPUTBIT((b)); \
|
---|
62 | while (bitstofollow) \
|
---|
63 | { OUTPUTBIT(!(b)); \
|
---|
64 | bitstofollow -= 1; \
|
---|
65 | } \
|
---|
66 | }
|
---|
67 |
|
---|
68 | #ifdef INTEGRATED
|
---|
69 | #define OUTPUTBIT(b) \
|
---|
70 | { buffer >>= 1; \
|
---|
71 | if (b) buffer |= 0x80; \
|
---|
72 | bitstogo -= 1; \
|
---|
73 | if (bitstogo==0) \
|
---|
74 | { putc(buffer, arith_out); \
|
---|
75 | bitstogo = 8; \
|
---|
76 | cmpbytes += 1; \
|
---|
77 | } \
|
---|
78 | CountOfBitsOut++; \
|
---|
79 | }
|
---|
80 | #else
|
---|
81 | #define OUTPUTBIT(b) \
|
---|
82 | { buffer >>= 1; \
|
---|
83 | if (b) buffer |= 0x80; \
|
---|
84 | bitstogo -= 1; \
|
---|
85 | if (bitstogo==0) \
|
---|
86 | { putc(buffer, arith_out); \
|
---|
87 | bitstogo = 8; \
|
---|
88 | cmpbytes += 1; \
|
---|
89 | } \
|
---|
90 | }
|
---|
91 | #endif
|
---|
92 |
|
---|
93 | #define ADDNEXTINPUTBIT(v) \
|
---|
94 | { if (bitstogo==0) \
|
---|
95 | { buffer = getc(arith_in); \
|
---|
96 | bitstogo = 8; \
|
---|
97 | } \
|
---|
98 | v = (v<<1)+(buffer&1); \
|
---|
99 | buffer >>= 1; \
|
---|
100 | bitstogo -=1; \
|
---|
101 | }
|
---|
102 |
|
---|
103 | /*==================================*/
|
---|
104 |
|
---|
105 | void
|
---|
106 | arithmetic_encode (lbnd, hbnd, totl)
|
---|
107 | int lbnd, hbnd, totl;
|
---|
108 | {
|
---|
109 | register codevalue low, high;
|
---|
110 |
|
---|
111 | #ifdef BECAREFUL
|
---|
112 | if (!(0 <= lbnd && lbnd < hbnd && hbnd <= totl && totl < maxfrequency))
|
---|
113 | {
|
---|
114 | fprintf (stderr, "(corrupt file) coding error: %d %d %d\n", lbnd, hbnd, totl);
|
---|
115 | abort ();
|
---|
116 | }
|
---|
117 | #endif
|
---|
118 |
|
---|
119 | {
|
---|
120 | register codevalue range;
|
---|
121 | range = S_high - S_low + 1;
|
---|
122 | high = S_low + range * hbnd / totl - 1;
|
---|
123 | low = S_low + range * lbnd / totl;
|
---|
124 | }
|
---|
125 |
|
---|
126 | {
|
---|
127 | register codevalue H;
|
---|
128 | register long bitstofollow;
|
---|
129 | register int buffer, bitstogo;
|
---|
130 |
|
---|
131 | bitstofollow = S_bitstofollow;
|
---|
132 | buffer = S_buffer;
|
---|
133 | bitstogo = S_bitstogo;
|
---|
134 | H = half;
|
---|
135 |
|
---|
136 | for (;;)
|
---|
137 | {
|
---|
138 | if (high < H)
|
---|
139 | {
|
---|
140 | BITPLUSFOLLOW (0);
|
---|
141 | }
|
---|
142 | else if (low >= H)
|
---|
143 | {
|
---|
144 | BITPLUSFOLLOW (1);
|
---|
145 | low -= H;
|
---|
146 | high -= H;
|
---|
147 | }
|
---|
148 | else if (low >= firstqtr && high < thirdqtr)
|
---|
149 | {
|
---|
150 | bitstofollow++;
|
---|
151 | low -= firstqtr;
|
---|
152 | high -= firstqtr;
|
---|
153 | }
|
---|
154 | else
|
---|
155 | break;
|
---|
156 | low += low;
|
---|
157 | high += high;
|
---|
158 | high++;
|
---|
159 | }
|
---|
160 | S_bitstofollow = bitstofollow;
|
---|
161 | S_buffer = buffer;
|
---|
162 | S_bitstogo = bitstogo;
|
---|
163 | S_low = low;
|
---|
164 | S_high = high;
|
---|
165 | }
|
---|
166 | }
|
---|
167 |
|
---|
168 | /*==================================*/
|
---|
169 |
|
---|
170 | /* Made into a macro
|
---|
171 |
|
---|
172 | codevalue
|
---|
173 | arithmetic_decode_target(totl)
|
---|
174 | register int totl;
|
---|
175 | { return (((S_value-S_low+1)*totl-1) / (S_high -S_low+1));
|
---|
176 | }
|
---|
177 | */
|
---|
178 |
|
---|
179 | /*==================================*/
|
---|
180 |
|
---|
181 | void
|
---|
182 | arithmetic_decode (lbnd, hbnd, totl)
|
---|
183 | int lbnd, hbnd, totl;
|
---|
184 | {
|
---|
185 | register codevalue low, high;
|
---|
186 |
|
---|
187 | #ifdef BECAREFUL
|
---|
188 | if (!(0 <= lbnd && lbnd < hbnd && hbnd <= totl && totl < maxfrequency))
|
---|
189 | {
|
---|
190 | fprintf (stderr, "(corrupt file) coding error: %d %d %d\n", lbnd, hbnd, totl);
|
---|
191 | abort ();
|
---|
192 | }
|
---|
193 | #endif
|
---|
194 |
|
---|
195 | {
|
---|
196 | register codevalue range;
|
---|
197 | range = S_high - S_low + 1;
|
---|
198 | high = S_low + range * hbnd / totl - 1;
|
---|
199 | low = S_low + range * lbnd / totl;
|
---|
200 | }
|
---|
201 |
|
---|
202 | {
|
---|
203 | register codevalue value, H;
|
---|
204 | register int buffer, bitstogo;
|
---|
205 |
|
---|
206 | buffer = S_buffer;
|
---|
207 | bitstogo = S_bitstogo;
|
---|
208 | H = half;
|
---|
209 | value = S_value;
|
---|
210 |
|
---|
211 | for (;;)
|
---|
212 | {
|
---|
213 | if (high < H)
|
---|
214 | { /* nothing */
|
---|
215 | }
|
---|
216 | else if (low >= H)
|
---|
217 | {
|
---|
218 | value -= H;
|
---|
219 | low -= H;
|
---|
220 | high -= H;
|
---|
221 | }
|
---|
222 | else if (low >= firstqtr && high < thirdqtr)
|
---|
223 | {
|
---|
224 | value -= firstqtr;
|
---|
225 | low -= firstqtr;
|
---|
226 | high -= firstqtr;
|
---|
227 | }
|
---|
228 | else
|
---|
229 | break;
|
---|
230 | low += low;
|
---|
231 | high += high;
|
---|
232 | high += 1;
|
---|
233 | ADDNEXTINPUTBIT (value);
|
---|
234 | }
|
---|
235 | S_buffer = buffer;
|
---|
236 | S_bitstogo = bitstogo;
|
---|
237 | S_low = low;
|
---|
238 | S_high = high;
|
---|
239 | S_value = value;
|
---|
240 | }
|
---|
241 | }
|
---|
242 |
|
---|
243 | /*==================================*/
|
---|
244 |
|
---|
245 |
|
---|
246 | static void
|
---|
247 | startoutputingbits ()
|
---|
248 | {
|
---|
249 | S_buffer = 0;
|
---|
250 | S_bitstogo = 8;
|
---|
251 | }
|
---|
252 |
|
---|
253 | static void
|
---|
254 | startinputingbits ()
|
---|
255 | {
|
---|
256 | S_buffer = 0;
|
---|
257 | S_bitstogo = 0;
|
---|
258 | }
|
---|
259 |
|
---|
260 | static void
|
---|
261 | doneoutputingbits ()
|
---|
262 | { /* write another byte if necessary */
|
---|
263 | if (S_bitstogo < 8)
|
---|
264 | {
|
---|
265 | putc (S_buffer >> S_bitstogo, arith_out);
|
---|
266 | cmpbytes += 1;
|
---|
267 | }
|
---|
268 | }
|
---|
269 |
|
---|
270 | /*==================================*/
|
---|
271 |
|
---|
272 | static void
|
---|
273 | startencoding ()
|
---|
274 | {
|
---|
275 | S_low = 0;
|
---|
276 | S_high = topvalue;
|
---|
277 | S_bitstofollow = 0;
|
---|
278 | }
|
---|
279 |
|
---|
280 | static void
|
---|
281 | startdecoding ()
|
---|
282 | {
|
---|
283 | register int i;
|
---|
284 | register int buffer, bitstogo;
|
---|
285 | S_low = 0;
|
---|
286 | S_high = topvalue;
|
---|
287 | S_value = 0;
|
---|
288 | bitstogo = S_bitstogo;
|
---|
289 | buffer = S_buffer;
|
---|
290 | for (i = 0; i < codevaluebits; i++)
|
---|
291 | ADDNEXTINPUTBIT (S_value);
|
---|
292 | S_bitstogo = bitstogo;
|
---|
293 | S_buffer = buffer;
|
---|
294 | }
|
---|
295 |
|
---|
296 | static void
|
---|
297 | doneencoding ()
|
---|
298 | {
|
---|
299 | register long bitstofollow;
|
---|
300 | register int buffer, bitstogo;
|
---|
301 | bitstofollow = S_bitstofollow;
|
---|
302 | buffer = S_buffer;
|
---|
303 | bitstogo = S_bitstogo;
|
---|
304 | bitstofollow += 1;
|
---|
305 | if (S_low < firstqtr)
|
---|
306 | {
|
---|
307 | BITPLUSFOLLOW (0);
|
---|
308 | }
|
---|
309 | else
|
---|
310 | {
|
---|
311 | BITPLUSFOLLOW (1);
|
---|
312 | }
|
---|
313 | S_bitstofollow = bitstofollow;
|
---|
314 | S_buffer = buffer;
|
---|
315 | S_bitstogo = bitstogo;
|
---|
316 | }
|
---|
317 |
|
---|
318 |
|
---|
319 |
|
---|
320 | void
|
---|
321 | EncodeGammaDist (int Off)
|
---|
322 | /* Encode Off with probability distribution derived from the Elias gamma distribution. */
|
---|
323 | {
|
---|
324 | int Len, i;
|
---|
325 |
|
---|
326 | Off++;
|
---|
327 | for (Len = 31; Len >= 0 && !(Off & (1 << Len)); Len--);
|
---|
328 |
|
---|
329 | for (i = Len; i >= 0; i--)
|
---|
330 | arithmetic_encode (0, 1, 2);
|
---|
331 | arithmetic_encode (1, 2, 2);
|
---|
332 |
|
---|
333 | for (i = Len - 1; i >= 0; i--)
|
---|
334 | if (Off & (1 << i))
|
---|
335 | arithmetic_encode (1, 2, 2);
|
---|
336 | else
|
---|
337 | arithmetic_encode (0, 1, 2);
|
---|
338 | }
|
---|
339 |
|
---|
340 |
|
---|
341 |
|
---|
342 | int
|
---|
343 | DecodeGammaDist ()
|
---|
344 | /* Decode next Off using probability distribution derived from the Elias gamma distribution. Inverse of EncodeGammaDist. */
|
---|
345 | {
|
---|
346 | int i = 1, Len = 0, bit;
|
---|
347 |
|
---|
348 | do
|
---|
349 | {
|
---|
350 | bit = arithmetic_decode_target (2) < 1 ? 0 : 1;
|
---|
351 | if (bit)
|
---|
352 | arithmetic_decode (1, 2, 2);
|
---|
353 | else
|
---|
354 | {
|
---|
355 | arithmetic_decode (0, 1, 2);
|
---|
356 | Len++;
|
---|
357 | }
|
---|
358 | }
|
---|
359 | while (!bit);
|
---|
360 |
|
---|
361 | Len--;
|
---|
362 | while (Len-- > 0)
|
---|
363 | {
|
---|
364 | bit = arithmetic_decode_target (2) < 1 ? 0 : 1;
|
---|
365 | if (bit)
|
---|
366 | arithmetic_decode (1, 2, 2);
|
---|
367 | else
|
---|
368 | arithmetic_decode (0, 1, 2);
|
---|
369 | i = (i << 1) | bit;
|
---|
370 | }
|
---|
371 | return (i - 1);
|
---|
372 | }
|
---|
373 |
|
---|
374 |
|
---|
375 |
|
---|
376 |
|
---|
377 |
|
---|
378 | void
|
---|
379 | EncodeGammaSigned (int snum, int *pos, int *neg)
|
---|
380 | {
|
---|
381 | if (snum >= 0)
|
---|
382 | arithmetic_encode (0, *pos, *pos + (*neg)), (*pos)++;
|
---|
383 | else
|
---|
384 | arithmetic_encode (*pos, *pos + (*neg), *pos + (*neg)), (*neg)++;
|
---|
385 | if (*pos + (*neg) >= maxfrequency)
|
---|
386 | {
|
---|
387 | *pos = (*pos + 1) / 2;
|
---|
388 | *neg = (*neg + 1) / 2;
|
---|
389 | }
|
---|
390 | EncodeGammaDist (abs (snum));
|
---|
391 | }
|
---|
392 |
|
---|
393 |
|
---|
394 | int
|
---|
395 | DecodeGammaSigned (int *pos, int *neg)
|
---|
396 | {
|
---|
397 | int signedpos = 1;
|
---|
398 | if (arithmetic_decode_target (*pos + (*neg)) < *pos)
|
---|
399 | arithmetic_decode (0, *pos, *pos + (*neg)), (*pos)++;
|
---|
400 | else
|
---|
401 | arithmetic_decode (*pos, *pos + (*neg), *pos + (*neg)), (*neg)++, signedpos = 0;
|
---|
402 |
|
---|
403 | if (*pos + (*neg) >= maxfrequency)
|
---|
404 | {
|
---|
405 | *pos = (*pos + 1) / 2;
|
---|
406 | *neg = (*neg + 1) / 2;
|
---|
407 | }
|
---|
408 |
|
---|
409 | if (signedpos)
|
---|
410 | return DecodeGammaDist ();
|
---|
411 | else
|
---|
412 | return (-DecodeGammaDist ());
|
---|
413 | }
|
---|
414 |
|
---|
415 |
|
---|
416 | void
|
---|
417 | InitArithEncoding (void)
|
---|
418 | {
|
---|
419 | S_low = 0, S_high = 0, S_value = 0;
|
---|
420 | S_bitstofollow = 0;
|
---|
421 | S_buffer = 0, S_bitstogo = 0;
|
---|
422 | cmpbytes = 0, rawbytes = 0;
|
---|
423 |
|
---|
424 | startoutputingbits ();
|
---|
425 | startencoding ();
|
---|
426 | }
|
---|
427 |
|
---|
428 | void
|
---|
429 | InitArithDecoding (void)
|
---|
430 | {
|
---|
431 | S_low = 0, S_high = 0, S_value = 0;
|
---|
432 | S_bitstofollow = 0;
|
---|
433 | S_buffer = 0, S_bitstogo = 0;
|
---|
434 | cmpbytes = 0, rawbytes = 0;
|
---|
435 |
|
---|
436 | startinputingbits ();
|
---|
437 | startdecoding ();
|
---|
438 | }
|
---|
439 |
|
---|
440 | void
|
---|
441 | CloseDownArithEncoding (void)
|
---|
442 | {
|
---|
443 | doneencoding ();
|
---|
444 | doneoutputingbits ();
|
---|
445 | }
|
---|
446 |
|
---|
447 | void
|
---|
448 | CloseDownArithDecoding (void)
|
---|
449 | {
|
---|
450 | }
|
---|
451 |
|
---|
452 |
|
---|
453 |
|
---|
454 |
|
---|
455 |
|
---|
456 | /* encode that famous number, 42 uses 12 bits */
|
---|
457 | void
|
---|
458 | EncodeChecksum ()
|
---|
459 | {
|
---|
460 | EncodeGammaDist (42);
|
---|
461 | }
|
---|
462 |
|
---|
463 | void
|
---|
464 | DecodeChecksum (char str[])
|
---|
465 | {
|
---|
466 | if (DecodeGammaDist () != 42)
|
---|
467 | {
|
---|
468 | fprintf (stderr, "%s: checksum error, file corrupt.\n", str);
|
---|
469 | exit (1);
|
---|
470 | }
|
---|
471 | }
|
---|