Debian Codegraph @

src/jb2/zp.cpp

raw
1 /*
2 * zp.cpp - ZP-coder from DjVuLibre, an adaptive arithmetical binary coder
3 */
4
5 /* The DjVuLibre code is a bit reorganized, but the algorithms are the same.
6 * Z-coder was stripped.
7 */
8
9 #include "../base/mdjvucfg.h"
10 #include <minidjvu/minidjvu.h>
11 #include <stdlib.h>
12 #include "zp.h"
13
14 ZPMemoryWatcher::~ZPMemoryWatcher()
15 {
16 }
17
18
19 // NumContext {{{
20
21 enum {numcontext_first_allocation_size = 512};
22 void ZPNumContext::init()/*{{{*/
23 {
24 n = 1;
25 nodes[0].value = 0;
26 left[0] = right[0] = 0;
27 }/*}}}*/
28 ZPNumContext::ZPNumContext(int32 amin, int32 amax, ZPMemoryWatcher *w)/*{{{*/
29 : min(amin), max(amax), watcher(w)
30 {
31 assert(amin <= amax);
32 allocated = numcontext_first_allocation_size;
33 nodes = (ZPBitContext *) malloc(allocated * sizeof(ZPBitContext));
34 left = (uint16 *) malloc(allocated * sizeof(uint16));
35 right = (uint16 *) malloc(allocated * sizeof(uint16));
36 init();
37 }/*}}}*/
38 ZPNumContext::~ZPNumContext()/*{{{*/
39 {
40 free(nodes);
41 free(left);
42 free(right);
43 }/*}}}*/
44 uint16 ZPNumContext::get_left(uint16 i)/*{{{*/
45 {
46 assert(i < n);
47 uint16 r = left[i];
48 if (r) return r;
49 r = new_node();
50 left[i] = r;
51 return r;
52 }/*}}}*/
53 uint16 ZPNumContext::get_right(uint16 i)/*{{{*/
54 {
55 assert(i < n);
56 uint16 r = right[i];
57 if (r) return r;
58 r = new_node();
59 right[i] = r;
60 return r;
61 }/*}}}*/
62 uint16 ZPNumContext::new_node()/*{{{*/
63 {
64 if (n == allocated)
65 {
66 allocated <<= 1;
67 nodes = (ZPBitContext *) realloc(nodes, allocated * sizeof(*nodes));
68 left = (uint16 *) realloc(left , allocated * sizeof(*left));
69 right = (uint16 *) realloc(right, allocated * sizeof(*right));
70 }
71 nodes[n].value = 0;
72 left[n] = 0;
73 right[n] = 0;
74 if (watcher)
75 watcher->handle_allocation();
76 return n++;
77 }/*}}}*/
78 void ZPNumContext::reset()/*{{{*/
79 {
80 allocated = numcontext_first_allocation_size;
81 nodes = (ZPBitContext *) realloc(nodes, allocated * sizeof(ZPBitContext));
82 left = (uint16 *) realloc(left, allocated * sizeof(uint16));
83 right = (uint16 *) realloc(right, allocated * sizeof(uint16));
84 init();
85 }/*}}}*/
86 void ZPNumContext::set_interval(int32 new_min, int32 new_max)/*{{{*/
87 {
88 assert(new_min <= new_max);
89 min = new_min;
90 max = new_max;
91 }/*}}}*/
92
93 // NumContext }}}
94
95 // Table {{{
96
97 static signed char ZP_FFZ_table[256];
98
99 // The following tables are taken from DjVuLibre.
100
101 static uint16 ZP_p_table[256] = {
102 0x8000,0x8000,0x8000,0x6bbd,0x6bbd,0x5d45,0x5d45,0x51b9,0x51b9,0x4813,0x4813,
103 0x3fd5,0x3fd5,0x38b1,0x38b1,0x3275,0x3275,0x2cfd,0x2cfd,0x2825,0x2825,0x23ab,
104 0x23ab,0x1f87,0x1f87,0x1bbb,0x1bbb,0x1845,0x1845,0x1523,0x1523,0x1253,0x1253,
105 0x0fcf,0x0fcf,0x0d95,0x0d95,0x0b9d,0x0b9d,0x09e3,0x09e3,0x0861,0x0861,0x0711,
106 0x0711,0x05f1,0x05f1,0x04f9,0x04f9,0x0425,0x0425,0x0371,0x0371,0x02d9,0x02d9,
107 0x0259,0x0259,0x01ed,0x01ed,0x0193,0x0193,0x0149,0x0149,0x010b,0x010b,0x00d5,
108 0x00d5,0x00a5,0x00a5,0x007b,0x007b,0x0057,0x0057,0x003b,0x003b,0x0023,0x0023,
109 0x0013,0x0013,0x0007,0x0007,0x0001,0x0001,0x5695,0x24ee,0x8000,0x0d30,0x481a,
110 0x0481,0x3579,0x017a,0x24ef,0x007b,0x1978,0x0028,0x10ca,0x000d,0x0b5d,0x0034,
111 0x078a,0x00a0,0x050f,0x0117,0x0358,0x01ea,0x0234,0x0144,0x0173,0x0234,0x00f5,
112 0x0353,0x00a1,0x05c5,0x011a,0x03cf,0x01aa,0x0285,0x0286,0x01ab,0x03d3,0x011a,
113 0x05c5,0x00ba,0x08ad,0x007a,0x0ccc,0x01eb,0x1302,0x02e6,0x1b81,0x045e,0x24ef,
114 0x0690,0x2865,0x09de,0x3987,0x0dc8,0x2c99,0x10ca,0x3b5f,0x0b5d,0x5695,0x078a,
115 0x8000,0x050f,0x24ee,0x0358,0x0d30,0x0234,0x0481,0x0173,0x017a,0x00f5,0x007b,
116 0x00a1,0x0028,0x011a,0x000d,0x01aa,0x0034,0x0286,0x00a0,0x03d3,0x0117,0x05c5,
117 0x01ea,0x08ad,0x0144,0x0ccc,0x0234,0x1302,0x0353,0x1b81,0x05c5,0x24ef,0x03cf,
118 0x2b74,0x0285,0x201d,0x01ab,0x1715,0x011a,0x0fb7,0x00ba,0x0a67,0x01eb,0x06e7,
119 0x02e6,0x0496,0x045e,0x030d,0x0690,0x0206,0x09de,0x0155,0x0dc8,0x00e1,0x2b74,
120 0x0094,0x201d,0x0188,0x1715,0x0252,0x0fb7,0x0383,0x0a67,0x0547,0x06e7,0x07e2,
121 0x0496,0x0bc0,0x030d,0x1178,0x0206,0x19da,0x0155,0x24ef,0x00e1,0x320e,0x0094,
122 0x432a,0x0188,0x447d,0x0252,0x5ece,0x0383,0x8000,0x0547,0x481a,0x07e2,0x3579,
123 0x0bc0,0x24ef,0x1178,0x1978,0x19da,0x2865,0x24ef,0x3987,0x320e,0x2c99,0x432a,
124 0x3b5f,0x447d,0x5695,0x5ece,0x8000,0x8000,0x5695,0x481a,0x481a};
125
126 static uint16 ZP_m_table[256] = {
127 0x0000,0x0000,0x0000,0x10a5,0x10a5,0x1f28,0x1f28,0x2bd3,0x2bd3,0x36e3,0x36e3,
128 0x408c,0x408c,0x48fd,0x48fd,0x505d,0x505d,0x56d0,0x56d0,0x5c71,0x5c71,0x615b,
129 0x615b,0x65a5,0x65a5,0x6962,0x6962,0x6ca2,0x6ca2,0x6f74,0x6f74,0x71e6,0x71e6,
130 0x7404,0x7404,0x75d6,0x75d6,0x7768,0x7768,0x78c2,0x78c2,0x79ea,0x79ea,0x7ae7,
131 0x7ae7,0x7bbe,0x7bbe,0x7c75,0x7c75,0x7d0f,0x7d0f,0x7d91,0x7d91,0x7dfe,0x7dfe,
132 0x7e5a,0x7e5a,0x7ea6,0x7ea6,0x7ee6,0x7ee6,0x7f1a,0x7f1a,0x7f45,0x7f45,0x7f6b,
133 0x7f6b,0x7f8d,0x7f8d,0x7faa,0x7faa,0x7fc3,0x7fc3,0x7fd7,0x7fd7,0x7fe7,0x7fe7,
134 0x7ff2,0x7ff2,0x7ffa,0x7ffa,0x7fff,0x7fff,0xFFFF}; // last value is a signal
135
136 static unsigned char ZP_up_table[256] = {
137 84,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,
138 22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
139 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,
140 74,75,76,77,78,79,80,81,82,81,82,9,86,5,88,89,90,91,92,93,94,95,96,97,82,99,76,
141 101,70,103,66,105,106,107,66,109,60,111,56,69,114,65,116,61,118,57,120,53,122,
142 49,124,43,72,39,60,33,56,29,52,23,48,23,42,137,38,21,140,15,142,9,144,141,146,
143 147,148,149,150,151,152,153,154,155,70,157,66,81,62,75,58,69,54,65,50,167,44,
144 65,40,59,34,55,30,175,24,177,178,179,180,181,182,183,184,69,186,59,188,55,190,
145 51,192,47,194,41,196,37,198,199,72,201,62,203,58,205,54,207,50,209,46,211,40,
146 213,36,215,30,217,26,219,20,71,14,61,14,57,8,53,228,49,230,45,232,39,234,35,
147 138,29,24,25,240,19,22,13,16,13,10,7,244,249,10,89,230};
148
149 static unsigned char ZP_dn_table[256] = {
150 145,4,3,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,
151 19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,
152 45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,
153 71,72,73,74,75,76,77,78,79,80,85,226,6,176,143,138,141,112,135,104,133,100,129,
154 98,127,72,125,102,123,60,121,110,119,108,117,54,115,48,113,134,59,132,55,130,
155 51,128,47,126,41,62,37,66,31,54,25,50,131,46,17,40,15,136,7,32,139,172,9,170,
156 85,168,248,166,247,164,197,162,95,160,173,158,165,156,161,60,159,56,71,52,163,
157 48,59,42,171,38,169,32,53,26,47,174,193,18,191,222,189,218,187,216,185,214,61,
158 212,53,210,49,208,45,206,39,204,195,202,31,200,243,64,239,56,237,52,235,48,233,
159 44,231,38,229,34,227,28,225,22,223,16,221,220,63,8,55,224,51,2,47,87,43,246,37,
160 244,33,238,27,236,21,16,15,8,241,242,7,10,245,2,1,83,250,2,143,246};
161
162 static void init_ffz_table()/*{{{*/
163 {
164 for (int i = 0; i < 256; i++)
165 {
166 ZP_FFZ_table[i] = 0;
167 for (int j = i; j & 0x80; j <<= 1)
168 ZP_FFZ_table[i] += 1;
169 }
170 }/*}}}*/
171 static void init_tables()/*{{{*/
172 {
173 for (int i = 0; i < 256; i++)
174 {
175 if (ZP_m_table[i] == 0xFFFF)
176 {
177 for (int j = i; j < 256; j++) ZP_m_table[j] = 0;
178 break;
179 }
180 }
181 }/*}}}*/
182
183 static void init()/*{{{*/
184 {
185 init_ffz_table();
186 init_tables();
187 }/*}}}*/
188
189 // call function init() on startup
190 static struct Initer {Initer(){init();}} initer;
191
192 // Table }}}
193
194 // Encoder {{{
195
196 inline void ZPEncoder::emit_byte(unsigned char b)/*{{{*/
197 {
198 fputc(b, file);
199 }/*}}}*/
200 ZPEncoder::ZPEncoder(FILE *f)/*{{{*/
201 : file(f), a(0), nrun(0), subend(0), buffer(0xffffff),
202 delay(25), byte(0), scount(0), closed(false)
203 {
204 assert(f);
205 }/*}}}*/
206 void ZPEncoder::close()/*{{{*/
207 {
208 /* adjust subend */
209 if (subend > 0x8000)
210 subend = 0x10000;
211 else if (subend > 0)
212 subend = 0x8000;
213
214 /* zemit many mps bits */
215 while (buffer != 0xffffff || subend )
216 {
217 zemit(1 - (subend >> 15) );
218 subend = (unsigned short)(subend<<1);
219 }
220
221 /* zemit pending run */
222 outbit(1);
223 while (nrun-- > 0)
224 outbit(0);
225 nrun = 0;
226
227 /* zemit 1 until full byte */
228 while (scount > 0)
229 outbit(1);
230
231 /* prevent further emission */
232 delay = 0xff;
233
234 closed = true;
235 }/*}}}*/
236 ZPEncoder::~ZPEncoder()/*{{{*/
237 {
238 if (!closed) close();
239 }/*}}}*/
240 void ZPEncoder::outbit(Bit bit)/*{{{*/
241 {
242 if (delay > 0)
243 {
244 if (delay < 0xff) // delay=0xff suspends emission forever
245 delay -= 1;
246 }
247 else
248 {
249 /* Insert a bit */
250 byte = (byte<<1) | bit;
251
252 /* Output a byte */
253 if (++scount == 8)
254 {
255 emit_byte(byte);
256 scount = 0;
257 byte = 0;
258 }
259 }
260 }/*}}}*/
261 void ZPEncoder::zemit(Bit b)/*{{{*/
262 {
263 /* Shift new bit into 3bytes buffer */
264 buffer = (buffer << 1) + b;
265
266 /* Examine bit going out of the 3bytes buffer */
267 b = buffer >> 24;
268 buffer = buffer & 0xffffff;
269
270 /* The following lines have been changed in order to emphazise the
271 * similarity between this bit counting and the scheme of Witten, Neal & Cleary
272 * (WN&C). Corresponding changes have been made in outbit and eflush.
273 * Variable 'nrun' is similar to the 'bits_to_follow' in the W&N code.
274 */
275 switch(b)
276 {
277 /* Similar to WN&C upper renormalization */
278 case 1:
279 outbit(1);
280 while (nrun-- > 0)
281 outbit(0);
282 nrun = 0;
283 break;
284
285 /* Similar to WN&C lower renormalization */
286 case 0xff:
287 outbit(0);
288 while (nrun-- > 0)
289 outbit(1);
290 nrun = 0;
291 break;
292
293 /* Similar to WN&C central renormalization */
294 case 0:
295 nrun += 1;
296 break;
297
298 default:
299 assert(0);
300 }
301 }/*}}}*/
302
303 inline void ZPEncoder::export_bits()/*{{{*/
304 {
305 zemit(1 - (subend >> 15));
306 subend = (unsigned short) (subend << 1);
307 a = (unsigned short) (a << 1);
308 }/*}}}*/
309 void ZPEncoder::encode_mps(ZPBitContext &context, uint32 z)/*{{{*/
310 {
311 /* Adaptation */
312 if (a >= ZP_m_table[context.value])
313 context.value = ZP_up_table[context.value];
314
315 /* Code MPS */
316 a = z;
317
318 if (a >= 0x8000) export_bits();
319 }/*}}}*/
320 void ZPEncoder::encode_lps(ZPBitContext &context, uint32 z)/*{{{*/
321 {
322 /* Adaptation */
323 context.value = ZP_dn_table[context.value];
324
325 /* Code LPS */
326 z = 0x10000 - z;
327 subend += z;
328 a += z;
329
330 while (a >= 0x8000) export_bits();
331 }/*}}}*/
332 void ZPEncoder::encode_mps_simple(unsigned int z)
333 {
334 /* Code MPS */
335 a = z;
336 /* Export bits */
337 if (a >= 0x8000) export_bits();
338 }
339
340 void ZPEncoder::encode_lps_simple(unsigned int z)
341 {
342 /* Code LPS */
343 z = 0x10000 - z;
344 subend += z;
345 a += z;
346
347 /* Export bits */
348 while (a >= 0x8000) export_bits();
349 }
350 void ZPEncoder::encode(int32 n, ZPNumContext &context)/*{{{*/
351 {
352 bool negative =false;
353 int32 cutoff = 0;
354 uint32 range = 0xFFFFFFFF;
355 uint16 current_node = 0;
356 int phase = 1;
357 int32 low = context.min;
358 int32 high = context.max;
359 assert(low <= n && n <= high);
360
361 while(range != 1)
362 {
363 // encoding-specific
364 bool decision;
365 decision = n >= cutoff;
366 if (low < cutoff && cutoff <= high)
367 encode(decision, context.nodes[current_node]);
368
369 // context for new bit
370 current_node = decision
371 ? context.get_right(current_node)
372 : context.get_left (current_node);
373
374 // phase dependent part
375 switch (phase)
376 {
377 case 1:
378 negative = !decision;
379 if (negative)
380 {
381 // encoding-specific
382 n = - n - 1;
383
384 const int temp = - low - 1;
385 low = - high - 1;
386 high = temp;
387 }
388 phase = 2; cutoff = 1;
389 break;
390
391 case 2:
392 if (!decision)
393 {
394 phase = 3;
395 range = (cutoff + 1) / 2;
396 if (range == 1)
397 cutoff = 0;
398 else
399 cutoff -= range / 2;
400 }
401 else
402 {
403 cutoff += cutoff + 1;
404 }
405 break;
406
407 case 3:
408 range /= 2;
409 if (range != 1)
410 {
411 if (!decision)
412 cutoff -= range / 2;
413 else
414 cutoff += range / 2;
415 }
416 else if (!decision)
417 {
418 cutoff--;
419 }
420 break;
421 }
422 }
423 }/*}}}*/
424 void ZPEncoder::encode_without_context(Bit bit)/*{{{*/
425 {
426 assert(bit == 0 || bit == 1);
427 uint32 z = 0x8000 + (a >> 1);
428 if (bit)
429 encode_lps_simple(z);
430 else
431 encode_mps_simple(z);
432 }/*}}}*/
433 void ZPEncoder::encode(Bit bit, ZPBitContext &context) /*{{{*/
434 {
435 uint32 z = a + ZP_p_table[context.value];
436
437 assert(bit == 0 || bit == 1);
438 if (bit != (context.value & 1))
439 {
440 /* Avoid interval reversion */
441 uint32 d = 0x6000 + ((z + a) >> 2);
442 if (z > d) z = d;
443 encode_lps(context, z);
444 }
445 else if (z >= 0x8000)
446 {
447 /* Avoid interval reversion */
448 uint32 d = 0x6000 + ((z + a) >> 2);
449 if (z > d) z = d;
450 encode_mps(context, z);
451 }
452 else
453 a = z;
454 }/*}}}*/
455
456 // Encoder }}}
457
458 // Decoder {{{
459
460 inline bool ZPDecoder::next_byte(unsigned char &b)/*{{{*/
461 {
462 if (!bytes_left) return false;
463 int c = fgetc(file);
464 if (c == EOF) return false;
465 bytes_left--;
466 b = c;
467 return true;
468 }/*}}}*/
469 ZPDecoder::ZPDecoder(FILE *f, int32 len)/*{{{*/
470 : file(f), a(0), fence(0), bytes_left(len)
471 {
472 open();
473 }/*}}}*/
474 void ZPDecoder::open()/*{{{*/
475 {
476 /* Read first 16 bits of code */
477 if (!next_byte(byte))
478 byte = 0xff;
479 code = byte << 8;
480 if (!next_byte(byte))
481 byte = 0xff;
482 code = code | byte;
483
484 /* Preload buffer */
485 delay = 25;
486 scount = 0;
487 preload();
488
489 /* Compute initial fence */
490 fence = code;
491 if (code >= 0x8000)
492 fence = 0x7fff;
493 }/*}}}*/
494 void ZPDecoder::preload(void)/*{{{*/
495 {
496 while (scount<=24)
497 {
498 if (!next_byte(byte))
499 {
500 byte = 0xff;
501 delay--;
502 assert(delay);
503 }
504 buffer = (buffer<<8) | byte;
505 scount += 8;
506 }
507 }/*}}}*/
508 inline int32 ZPDecoder::ffz(uint32 x)/*{{{*/
509 {
510 return x >= 0xff00
511 ? ZP_FFZ_table[x & 0xff] + 8
512 : ZP_FFZ_table[(x >> 8) & 0xff];
513 }/*}}}*/
514 Bit ZPDecoder::decode_sub(ZPBitContext &context, uint32 z)/*{{{*/
515 {
516 /* Save bit */
517 int bit = context.value & 1;
518
519 /* Test MPS/LPS */
520 if (z > code)
521 {
522 /* LPS branch */
523 z = 0x10000 - z;
524 a += z;
525 code = code + z;
526
527 /* LPS adaptation */
528 context.value = ZP_dn_table[context.value];
529
530 /* LPS renormalization */
531 int shift = ffz(a);
532 scount -= shift;
533 a = (unsigned short) (a << shift);
534 code = (unsigned short) (code << shift) |
535 ((buffer >> scount) & ((1 << shift) - 1));
536 if (scount<16) preload();
537
538 /* Adjust fence */
539 fence = code;
540 if (code >= 0x8000)
541 fence = 0x7fff;
542 return bit ^ 1;
543 }
544 else
545 {
546 /* MPS adaptation */
547 if (a >= ZP_m_table[context.value])
548 context.value = ZP_up_table[context.value];
549
550 /* MPS renormalization */
551 scount -= 1;
552 a = (unsigned short)(z<<1);
553 code = (unsigned short)(code<<1) | ((buffer>>scount) & 1);
554 if (scount<16) preload();
555
556 /* Adjust fence */
557 fence = code;
558 if (code >= 0x8000)
559 fence = 0x7fff;
560 return bit;
561 }
562 }/*}}}*/
563 int32 ZPDecoder::decode(ZPNumContext &context)/*{{{*/
564 {
565 bool negative=false;
566 int32 cutoff = 0;
567 uint32 range = 0xFFFFFFFF;
568 uint16 current_node = 0;
569 int phase = 1;
570 int32 low = context.min;
571 int32 high = context.max;
572
573 while(range != 1)
574 {
575 // decoding-specific
576 bool decision;
577 decision = low >= cutoff ||
578 (high >= cutoff && decode(context.nodes[current_node]));
579
580 // context for new bit
581 current_node = decision
582 ? context.get_right(current_node)
583 : context.get_left (current_node);
584
585 // phase dependent part
586 switch (phase)
587 {
588 case 1:
589 negative = !decision;
590 if (negative)
591 {
592 const int temp = - low - 1;
593 low = - high - 1;
594 high = temp;
595 }
596 phase = 2; cutoff = 1;
597 break;
598
599 case 2:
600 if (!decision)
601 {
602 phase = 3;
603 range = (cutoff + 1) / 2;
604 if (range == 1)
605 cutoff = 0;
606 else
607 cutoff -= range / 2;
608 }
609 else
610 {
611 cutoff += cutoff + 1;
612 }
613 break;
614
615 case 3:
616 range /= 2;
617 if (range != 1)
618 {
619 if (!decision)
620 cutoff -= range / 2;
621 else
622 cutoff += range / 2;
623 }
624 else if (!decision)
625 {
626 cutoff--;
627 }
628 break;
629 }
630 }
631 return negative ? -cutoff-1 : cutoff;
632 }/*}}}*/
633 Bit ZPDecoder::decode_without_context()/*{{{*/
634 {
635 ZPBitContext dummy;
636 return decode_sub(dummy, 0x8000 + (a >> 1));
637 }/*}}}*/
638 Bit ZPDecoder::decode(ZPBitContext &context)/*{{{*/
639 {
640 uint32 z = a + ZP_p_table[context.value];
641 if (z <= fence)
642 {
643 a = z;
644 return context.value & 1;
645 }
646
647 /* Avoid interval reversion */
648 uint32 d = 0x6000 + ((z + a) >> 2);
649 if (z > d) z = d;
650
651 return decode_sub(context, z);
652 }/*}}}*/
653
654 // Decoder }}}