Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/libjpeg/jcarith.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*
2 * jcarith.c
3 *
4 * Developed 1997-2020 by Guido Vollbeding.
5 * This file is part of the Independent JPEG Group's software.
6 * For conditions of distribution and use, see the accompanying README file.
7 *
8 * This file contains portable arithmetic entropy encoding routines for JPEG
9 * (implementing the ISO/IEC IS 10918-1 and CCITT Recommendation ITU-T T.81).
10 *
11 * Both sequential and progressive modes are supported in this single module.
12 *
13 * Suspension is not currently supported in this module.
14 */
15
16 #define JPEG_INTERNALS
17 #include "jinclude.h"
18 #include "jpeglib.h"
19
20
21 /* Expanded entropy encoder object for arithmetic encoding. */
22
23 typedef struct {
24 struct jpeg_entropy_encoder pub; /* public fields */
25
26 INT32 c; /* C register, base of coding interval, layout as in sec. D.1.3 */
27 INT32 a; /* A register, normalized size of coding interval */
28 INT32 sc; /* counter for stacked 0xFF values which might overflow */
29 INT32 zc; /* counter for pending 0x00 output values which might *
30 * be discarded at the end ("Pacman" termination) */
31 int ct; /* bit shift counter, determines when next byte will be written */
32 int buffer; /* buffer for most recent output byte != 0xFF */
33
34 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
35 int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */
36
37 unsigned int restarts_to_go; /* MCUs left in this restart interval */
38 int next_restart_num; /* next restart number to write (0-7) */
39
40 /* Pointers to statistics areas (these workspaces have image lifespan) */
41 unsigned char * dc_stats[NUM_ARITH_TBLS];
42 unsigned char * ac_stats[NUM_ARITH_TBLS];
43
44 /* Statistics bin for coding with fixed probability 0.5 */
45 unsigned char fixed_bin[4];
46 } arith_entropy_encoder;
47
48 typedef arith_entropy_encoder * arith_entropy_ptr;
49
50 /* The following two definitions specify the allocation chunk size
51 * for the statistics area.
52 * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
53 * 49 statistics bins for DC, and 245 statistics bins for AC coding.
54 *
55 * We use a compact representation with 1 byte per statistics bin,
56 * thus the numbers directly represent byte sizes.
57 * This 1 byte per statistics bin contains the meaning of the MPS
58 * (more probable symbol) in the highest bit (mask 0x80), and the
59 * index into the probability estimation state machine table
60 * in the lower bits (mask 0x7F).
61 */
62
63 #define DC_STAT_BINS 64
64 #define AC_STAT_BINS 256
65
66 /* NOTE: Uncomment the following #define if you want to use the
67 * given formula for calculating the AC conditioning parameter Kx
68 * for spectral selection progressive coding in section G.1.3.2
69 * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
70 * Although the spec and P&M authors claim that this "has proven
71 * to give good results for 8 bit precision samples", I'm not
72 * convinced yet that this is really beneficial.
73 * Early tests gave only very marginal compression enhancements
74 * (a few - around 5 or so - bytes even for very large files),
75 * which would turn out rather negative if we'd suppress the
76 * DAC (Define Arithmetic Conditioning) marker segments for
77 * the default parameters in the future.
78 * Note that currently the marker writing module emits 12-byte
79 * DAC segments for a full-component scan in a color image.
80 * This is not worth worrying about IMHO. However, since the
81 * spec defines the default values to be used if the tables
82 * are omitted (unlike Huffman tables, which are required
83 * anyway), one might optimize this behaviour in the future,
84 * and then it would be disadvantageous to use custom tables if
85 * they don't provide sufficient gain to exceed the DAC size.
86 *
87 * On the other hand, I'd consider it as a reasonable result
88 * that the conditioning has no significant influence on the
89 * compression performance. This means that the basic
90 * statistical model is already rather stable.
91 *
92 * Thus, at the moment, we use the default conditioning values
93 * anyway, and do not use the custom formula.
94 *
95 #define CALCULATE_SPECTRAL_CONDITIONING
96 */
97
98 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
99 * We assume that int right shift is unsigned if INT32 right shift is,
100 * which should be safe.
101 */
102
103 #ifdef RIGHT_SHIFT_IS_UNSIGNED
104 #define ISHIFT_TEMPS int ishift_temp;
105 #define IRIGHT_SHIFT(x,shft) \
106 ((ishift_temp = (x)) < 0 ? \
107 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
108 (ishift_temp >> (shft)))
109 #else
110 #define ISHIFT_TEMPS
111 #define IRIGHT_SHIFT(x,shft) ((x) >> (shft))
112 #endif
113
114
115 LOCAL(void)
116 emit_byte (int val, j_compress_ptr cinfo)
117 /* Write next output byte; we do not support suspension in this module. */
118 {
119 struct jpeg_destination_mgr * dest = cinfo->dest;
120
121 *dest->next_output_byte++ = (JOCTET) val;
122 if (--dest->free_in_buffer == 0)
123 if (! (*dest->empty_output_buffer) (cinfo))
124 ERREXIT(cinfo, JERR_CANT_SUSPEND);
125 }
126
127
128 /*
129 * Finish up at the end of an arithmetic-compressed scan.
130 */
131
132 METHODDEF(void)
133 finish_pass (j_compress_ptr cinfo)
134 {
135 arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
136 INT32 temp;
137
138 /* Section D.1.8: Termination of encoding */
139
140 /* Find the e->c in the coding interval with the largest
141 * number of trailing zero bits */
142 if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c)
143 e->c = temp + 0x8000L;
144 else
145 e->c = temp;
146 /* Send remaining bytes to output */
147 e->c <<= e->ct;
148 if (e->c & 0xF8000000L) {
149 /* One final overflow has to be handled */
150 if (e->buffer >= 0) {
151 if (e->zc)
152 do emit_byte(0x00, cinfo);
153 while (--e->zc);
154 emit_byte(e->buffer + 1, cinfo);
155 if (e->buffer + 1 == 0xFF)
156 emit_byte(0x00, cinfo);
157 }
158 e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */
159 e->sc = 0;
160 } else {
161 if (e->buffer == 0)
162 ++e->zc;
163 else if (e->buffer >= 0) {
164 if (e->zc)
165 do emit_byte(0x00, cinfo);
166 while (--e->zc);
167 emit_byte(e->buffer, cinfo);
168 }
169 if (e->sc) {
170 if (e->zc)
171 do emit_byte(0x00, cinfo);
172 while (--e->zc);
173 do {
174 emit_byte(0xFF, cinfo);
175 emit_byte(0x00, cinfo);
176 } while (--e->sc);
177 }
178 }
179 /* Output final bytes only if they are not 0x00 */
180 if (e->c & 0x7FFF800L) {
181 if (e->zc) /* output final pending zero bytes */
182 do emit_byte(0x00, cinfo);
183 while (--e->zc);
184 emit_byte((int) ((e->c >> 19) & 0xFF), cinfo);
185 if (((e->c >> 19) & 0xFF) == 0xFF)
186 emit_byte(0x00, cinfo);
187 if (e->c & 0x7F800L) {
188 emit_byte((int) ((e->c >> 11) & 0xFF), cinfo);
189 if (((e->c >> 11) & 0xFF) == 0xFF)
190 emit_byte(0x00, cinfo);
191 }
192 }
193 }
194
195
196 /*
197 * The core arithmetic encoding routine (common in JPEG and JBIG).
198 * This needs to go as fast as possible.
199 * Machine-dependent optimization facilities
200 * are not utilized in this portable implementation.
201 * However, this code should be fairly efficient and
202 * may be a good base for further optimizations anyway.
203 *
204 * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
205 *
206 * Note: I've added full "Pacman" termination support to the
207 * byte output routines, which is equivalent to the optional
208 * Discard_final_zeros procedure (Figure D.15) in the spec.
209 * Thus, we always produce the shortest possible output
210 * stream compliant to the spec (no trailing zero bytes,
211 * except for FF stuffing).
212 *
213 * I've also introduced a new scheme for accessing
214 * the probability estimation state machine table,
215 * derived from Markus Kuhn's JBIG implementation.
216 */
217
218 LOCAL(void)
219 arith_encode (j_compress_ptr cinfo, unsigned char *st, int val)
220 {
221 register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
222 register unsigned char nl, nm;
223 register INT32 qe, temp;
224 register int sv;
225
226 /* Fetch values from our compact representation of Table D.3(D.2):
227 * Qe values and probability estimation state machine
228 */
229 sv = *st;
230 qe = jpeg_aritab[sv & 0x7F]; /* => Qe_Value */
231 nl = qe & 0xFF; qe >>= 8; /* Next_Index_LPS + Switch_MPS */
232 nm = qe & 0xFF; qe >>= 8; /* Next_Index_MPS */
233
234 /* Encode & estimation procedures per sections D.1.4 & D.1.5 */
235 e->a -= qe;
236 if (val != (sv >> 7)) {
237 /* Encode the less probable symbol */
238 if (e->a >= qe) {
239 /* If the interval size (qe) for the less probable symbol (LPS)
240 * is larger than the interval size for the MPS, then exchange
241 * the two symbols for coding efficiency, otherwise code the LPS
242 * as usual: */
243 e->c += e->a;
244 e->a = qe;
245 }
246 *st = (sv & 0x80) ^ nl; /* Estimate_after_LPS */
247 } else {
248 /* Encode the more probable symbol */
249 if (e->a >= 0x8000L)
250 return; /* A >= 0x8000 -> ready, no renormalization required */
251 if (e->a < qe) {
252 /* If the interval size (qe) for the less probable symbol (LPS)
253 * is larger than the interval size for the MPS, then exchange
254 * the two symbols for coding efficiency: */
255 e->c += e->a;
256 e->a = qe;
257 }
258 *st = (sv & 0x80) ^ nm; /* Estimate_after_MPS */
259 }
260
261 /* Renormalization & data output per section D.1.6 */
262 do {
263 e->a <<= 1;
264 e->c <<= 1;
265 if (--e->ct == 0) {
266 /* Another byte is ready for output */
267 temp = e->c >> 19;
268 if (temp > 0xFF) {
269 /* Handle overflow over all stacked 0xFF bytes */
270 if (e->buffer >= 0) {
271 if (e->zc)
272 do emit_byte(0x00, cinfo);
273 while (--e->zc);
274 emit_byte(e->buffer + 1, cinfo);
275 if (e->buffer + 1 == 0xFF)
276 emit_byte(0x00, cinfo);
277 }
278 e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */
279 e->sc = 0;
280 /* Note: The 3 spacer bits in the C register guarantee
281 * that the new buffer byte can't be 0xFF here
282 * (see page 160 in the P&M JPEG book). */
283 /* New output byte, might overflow later */
284 e->buffer = (int) (temp & 0xFF);
285 } else if (temp == 0xFF) {
286 ++e->sc; /* stack 0xFF byte (which might overflow later) */
287 } else {
288 /* Output all stacked 0xFF bytes, they will not overflow any more */
289 if (e->buffer == 0)
290 ++e->zc;
291 else if (e->buffer >= 0) {
292 if (e->zc)
293 do emit_byte(0x00, cinfo);
294 while (--e->zc);
295 emit_byte(e->buffer, cinfo);
296 }
297 if (e->sc) {
298 if (e->zc)
299 do emit_byte(0x00, cinfo);
300 while (--e->zc);
301 do {
302 emit_byte(0xFF, cinfo);
303 emit_byte(0x00, cinfo);
304 } while (--e->sc);
305 }
306 /* New output byte (can still overflow) */
307 e->buffer = (int) (temp & 0xFF);
308 }
309 e->c &= 0x7FFFFL;
310 e->ct += 8;
311 }
312 } while (e->a < 0x8000L);
313 }
314
315
316 /*
317 * Emit a restart marker & resynchronize predictions.
318 */
319
320 LOCAL(void)
321 emit_restart (j_compress_ptr cinfo, int restart_num)
322 {
323 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
324 int ci;
325 jpeg_component_info * compptr;
326
327 finish_pass(cinfo);
328
329 emit_byte(0xFF, cinfo);
330 emit_byte(JPEG_RST0 + restart_num, cinfo);
331
332 /* Re-initialize statistics areas */
333 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
334 compptr = cinfo->cur_comp_info[ci];
335 /* DC needs no table for refinement scan */
336 if (cinfo->Ss == 0 && cinfo->Ah == 0) {
337 MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
338 /* Reset DC predictions to 0 */
339 entropy->last_dc_val[ci] = 0;
340 entropy->dc_context[ci] = 0;
341 }
342 /* AC needs no table when not present */
343 if (cinfo->Se) {
344 MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
345 }
346 }
347
348 /* Reset arithmetic encoding variables */
349 entropy->c = 0;
350 entropy->a = 0x10000L;
351 entropy->sc = 0;
352 entropy->zc = 0;
353 entropy->ct = 11;
354 entropy->buffer = -1; /* empty */
355 }
356
357
358 /*
359 * MCU encoding for DC initial scan (either spectral selection,
360 * or first pass of successive approximation).
361 */
362
363 METHODDEF(boolean)
364 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKARRAY MCU_data)
365 {
366 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
367 unsigned char *st;
368 int blkn, ci, tbl;
369 int v, v2, m;
370 ISHIFT_TEMPS
371
372 /* Emit restart marker if needed */
373 if (cinfo->restart_interval) {
374 if (entropy->restarts_to_go == 0) {
375 emit_restart(cinfo, entropy->next_restart_num);
376 entropy->restarts_to_go = cinfo->restart_interval;
377 entropy->next_restart_num++;
378 entropy->next_restart_num &= 7;
379 }
380 entropy->restarts_to_go--;
381 }
382
383 /* Encode the MCU data blocks */
384 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
385 ci = cinfo->MCU_membership[blkn];
386 tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
387
388 /* Compute the DC value after the required point transform by Al.
389 * This is simply an arithmetic right shift.
390 */
391 m = IRIGHT_SHIFT((int) (MCU_data[blkn][0][0]), cinfo->Al);
392
393 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
394
395 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
396 st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
397
398 /* Figure F.4: Encode_DC_DIFF */
399 if ((v = m - entropy->last_dc_val[ci]) == 0) {
400 arith_encode(cinfo, st, 0);
401 entropy->dc_context[ci] = 0; /* zero diff category */
402 } else {
403 entropy->last_dc_val[ci] = m;
404 arith_encode(cinfo, st, 1);
405 /* Figure F.6: Encoding nonzero value v */
406 /* Figure F.7: Encoding the sign of v */
407 if (v > 0) {
408 arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
409 st += 2; /* Table F.4: SP = S0 + 2 */
410 entropy->dc_context[ci] = 4; /* small positive diff category */
411 } else {
412 v = -v;
413 arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
414 st += 3; /* Table F.4: SN = S0 + 3 */
415 entropy->dc_context[ci] = 8; /* small negative diff category */
416 }
417 /* Figure F.8: Encoding the magnitude category of v */
418 m = 0;
419 if (v -= 1) {
420 arith_encode(cinfo, st, 1);
421 m = 1;
422 v2 = v;
423 st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
424 while (v2 >>= 1) {
425 arith_encode(cinfo, st, 1);
426 m <<= 1;
427 st += 1;
428 }
429 }
430 arith_encode(cinfo, st, 0);
431 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
432 if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
433 entropy->dc_context[ci] = 0; /* zero diff category */
434 else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
435 entropy->dc_context[ci] += 8; /* large diff category */
436 /* Figure F.9: Encoding the magnitude bit pattern of v */
437 st += 14;
438 while (m >>= 1)
439 arith_encode(cinfo, st, (m & v) ? 1 : 0);
440 }
441 }
442
443 return TRUE;
444 }
445
446
447 /*
448 * MCU encoding for AC initial scan (either spectral selection,
449 * or first pass of successive approximation).
450 */
451
452 METHODDEF(boolean)
453 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKARRAY MCU_data)
454 {
455 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
456 const int * natural_order;
457 JBLOCKROW block;
458 unsigned char *st;
459 int tbl, k, ke;
460 int v, v2, m;
461
462 /* Emit restart marker if needed */
463 if (cinfo->restart_interval) {
464 if (entropy->restarts_to_go == 0) {
465 emit_restart(cinfo, entropy->next_restart_num);
466 entropy->restarts_to_go = cinfo->restart_interval;
467 entropy->next_restart_num++;
468 entropy->next_restart_num &= 7;
469 }
470 entropy->restarts_to_go--;
471 }
472
473 natural_order = cinfo->natural_order;
474
475 /* Encode the MCU data block */
476 block = MCU_data[0];
477 tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
478
479 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
480
481 /* Establish EOB (end-of-block) index */
482 ke = cinfo->Se;
483 do {
484 /* We must apply the point transform by Al. For AC coefficients this
485 * is an integer division with rounding towards 0. To do this portably
486 * in C, we shift after obtaining the absolute value.
487 */
488 if ((v = (*block)[natural_order[ke]]) >= 0) {
489 if (v >>= cinfo->Al) break;
490 } else {
491 v = -v;
492 if (v >>= cinfo->Al) break;
493 }
494 } while (--ke);
495
496 /* Figure F.5: Encode_AC_Coefficients */
497 for (k = cinfo->Ss - 1; k < ke;) {
498 st = entropy->ac_stats[tbl] + 3 * k;
499 arith_encode(cinfo, st, 0); /* EOB decision */
500 for (;;) {
501 if ((v = (*block)[natural_order[++k]]) >= 0) {
502 if (v >>= cinfo->Al) {
503 arith_encode(cinfo, st + 1, 1);
504 arith_encode(cinfo, entropy->fixed_bin, 0);
505 break;
506 }
507 } else {
508 v = -v;
509 if (v >>= cinfo->Al) {
510 arith_encode(cinfo, st + 1, 1);
511 arith_encode(cinfo, entropy->fixed_bin, 1);
512 break;
513 }
514 }
515 arith_encode(cinfo, st + 1, 0);
516 st += 3;
517 }
518 st += 2;
519 /* Figure F.8: Encoding the magnitude category of v */
520 m = 0;
521 if (v -= 1) {
522 arith_encode(cinfo, st, 1);
523 m = 1;
524 v2 = v;
525 if (v2 >>= 1) {
526 arith_encode(cinfo, st, 1);
527 m <<= 1;
528 st = entropy->ac_stats[tbl] +
529 (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
530 while (v2 >>= 1) {
531 arith_encode(cinfo, st, 1);
532 m <<= 1;
533 st += 1;
534 }
535 }
536 }
537 arith_encode(cinfo, st, 0);
538 /* Figure F.9: Encoding the magnitude bit pattern of v */
539 st += 14;
540 while (m >>= 1)
541 arith_encode(cinfo, st, (m & v) ? 1 : 0);
542 }
543 /* Encode EOB decision only if k < cinfo->Se */
544 if (k < cinfo->Se) {
545 st = entropy->ac_stats[tbl] + 3 * k;
546 arith_encode(cinfo, st, 1);
547 }
548
549 return TRUE;
550 }
551
552
553 /*
554 * MCU encoding for DC successive approximation refinement scan.
555 * Note: we assume such scans can be multi-component,
556 * although the spec is not very clear on the point.
557 */
558
559 METHODDEF(boolean)
560 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKARRAY MCU_data)
561 {
562 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
563 unsigned char *st;
564 int Al, blkn;
565
566 /* Emit restart marker if needed */
567 if (cinfo->restart_interval) {
568 if (entropy->restarts_to_go == 0) {
569 emit_restart(cinfo, entropy->next_restart_num);
570 entropy->restarts_to_go = cinfo->restart_interval;
571 entropy->next_restart_num++;
572 entropy->next_restart_num &= 7;
573 }
574 entropy->restarts_to_go--;
575 }
576
577 st = entropy->fixed_bin; /* use fixed probability estimation */
578 Al = cinfo->Al;
579
580 /* Encode the MCU data blocks */
581 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
582 /* We simply emit the Al'th bit of the DC coefficient value. */
583 arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
584 }
585
586 return TRUE;
587 }
588
589
590 /*
591 * MCU encoding for AC successive approximation refinement scan.
592 */
593
594 METHODDEF(boolean)
595 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKARRAY MCU_data)
596 {
597 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
598 const int * natural_order;
599 JBLOCKROW block;
600 unsigned char *st;
601 int tbl, k, ke, kex;
602 int v;
603
604 /* Emit restart marker if needed */
605 if (cinfo->restart_interval) {
606 if (entropy->restarts_to_go == 0) {
607 emit_restart(cinfo, entropy->next_restart_num);
608 entropy->restarts_to_go = cinfo->restart_interval;
609 entropy->next_restart_num++;
610 entropy->next_restart_num &= 7;
611 }
612 entropy->restarts_to_go--;
613 }
614
615 natural_order = cinfo->natural_order;
616
617 /* Encode the MCU data block */
618 block = MCU_data[0];
619 tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
620
621 /* Section G.1.3.3: Encoding of AC coefficients */
622
623 /* Establish EOB (end-of-block) index */
624 ke = cinfo->Se;
625 do {
626 /* We must apply the point transform by Al. For AC coefficients this
627 * is an integer division with rounding towards 0. To do this portably
628 * in C, we shift after obtaining the absolute value.
629 */
630 if ((v = (*block)[natural_order[ke]]) >= 0) {
631 if (v >>= cinfo->Al) break;
632 } else {
633 v = -v;
634 if (v >>= cinfo->Al) break;
635 }
636 } while (--ke);
637
638 /* Establish EOBx (previous stage end-of-block) index */
639 for (kex = ke; kex > 0; kex--)
640 if ((v = (*block)[natural_order[kex]]) >= 0) {
641 if (v >>= cinfo->Ah) break;
642 } else {
643 v = -v;
644 if (v >>= cinfo->Ah) break;
645 }
646
647 /* Figure G.10: Encode_AC_Coefficients_SA */
648 for (k = cinfo->Ss - 1; k < ke;) {
649 st = entropy->ac_stats[tbl] + 3 * k;
650 if (k >= kex)
651 arith_encode(cinfo, st, 0); /* EOB decision */
652 for (;;) {
653 if ((v = (*block)[natural_order[++k]]) >= 0) {
654 if (v >>= cinfo->Al) {
655 if (v >> 1) /* previously nonzero coef */
656 arith_encode(cinfo, st + 2, (v & 1));
657 else { /* newly nonzero coef */
658 arith_encode(cinfo, st + 1, 1);
659 arith_encode(cinfo, entropy->fixed_bin, 0);
660 }
661 break;
662 }
663 } else {
664 v = -v;
665 if (v >>= cinfo->Al) {
666 if (v >> 1) /* previously nonzero coef */
667 arith_encode(cinfo, st + 2, (v & 1));
668 else { /* newly nonzero coef */
669 arith_encode(cinfo, st + 1, 1);
670 arith_encode(cinfo, entropy->fixed_bin, 1);
671 }
672 break;
673 }
674 }
675 arith_encode(cinfo, st + 1, 0);
676 st += 3;
677 }
678 }
679 /* Encode EOB decision only if k < cinfo->Se */
680 if (k < cinfo->Se) {
681 st = entropy->ac_stats[tbl] + 3 * k;
682 arith_encode(cinfo, st, 1);
683 }
684
685 return TRUE;
686 }
687
688
689 /*
690 * Encode and output one MCU's worth of arithmetic-compressed coefficients.
691 */
692
693 METHODDEF(boolean)
694 encode_mcu (j_compress_ptr cinfo, JBLOCKARRAY MCU_data)
695 {
696 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
697 const int * natural_order;
698 JBLOCKROW block;
699 unsigned char *st;
700 int tbl, k, ke;
701 int v, v2, m;
702 int blkn, ci;
703 jpeg_component_info * compptr;
704
705 /* Emit restart marker if needed */
706 if (cinfo->restart_interval) {
707 if (entropy->restarts_to_go == 0) {
708 emit_restart(cinfo, entropy->next_restart_num);
709 entropy->restarts_to_go = cinfo->restart_interval;
710 entropy->next_restart_num++;
711 entropy->next_restart_num &= 7;
712 }
713 entropy->restarts_to_go--;
714 }
715
716 natural_order = cinfo->natural_order;
717
718 /* Encode the MCU data blocks */
719 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
720 block = MCU_data[blkn];
721 ci = cinfo->MCU_membership[blkn];
722 compptr = cinfo->cur_comp_info[ci];
723
724 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
725
726 tbl = compptr->dc_tbl_no;
727
728 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
729 st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
730
731 /* Figure F.4: Encode_DC_DIFF */
732 if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
733 arith_encode(cinfo, st, 0);
734 entropy->dc_context[ci] = 0; /* zero diff category */
735 } else {
736 entropy->last_dc_val[ci] = (*block)[0];
737 arith_encode(cinfo, st, 1);
738 /* Figure F.6: Encoding nonzero value v */
739 /* Figure F.7: Encoding the sign of v */
740 if (v > 0) {
741 arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
742 st += 2; /* Table F.4: SP = S0 + 2 */
743 entropy->dc_context[ci] = 4; /* small positive diff category */
744 } else {
745 v = -v;
746 arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
747 st += 3; /* Table F.4: SN = S0 + 3 */
748 entropy->dc_context[ci] = 8; /* small negative diff category */
749 }
750 /* Figure F.8: Encoding the magnitude category of v */
751 m = 0;
752 if (v -= 1) {
753 arith_encode(cinfo, st, 1);
754 m = 1;
755 v2 = v;
756 st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
757 while (v2 >>= 1) {
758 arith_encode(cinfo, st, 1);
759 m <<= 1;
760 st += 1;
761 }
762 }
763 arith_encode(cinfo, st, 0);
764 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
765 if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
766 entropy->dc_context[ci] = 0; /* zero diff category */
767 else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
768 entropy->dc_context[ci] += 8; /* large diff category */
769 /* Figure F.9: Encoding the magnitude bit pattern of v */
770 st += 14;
771 while (m >>= 1)
772 arith_encode(cinfo, st, (m & v) ? 1 : 0);
773 }
774
775 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
776
777 if ((ke = cinfo->lim_Se) == 0) continue;
778 tbl = compptr->ac_tbl_no;
779
780 /* Establish EOB (end-of-block) index */
781 do {
782 if ((*block)[natural_order[ke]]) break;
783 } while (--ke);
784
785 /* Figure F.5: Encode_AC_Coefficients */
786 for (k = 0; k < ke;) {
787 st = entropy->ac_stats[tbl] + 3 * k;
788 arith_encode(cinfo, st, 0); /* EOB decision */
789 while ((v = (*block)[natural_order[++k]]) == 0) {
790 arith_encode(cinfo, st + 1, 0);
791 st += 3;
792 }
793 arith_encode(cinfo, st + 1, 1);
794 /* Figure F.6: Encoding nonzero value v */
795 /* Figure F.7: Encoding the sign of v */
796 if (v > 0) {
797 arith_encode(cinfo, entropy->fixed_bin, 0);
798 } else {
799 v = -v;
800 arith_encode(cinfo, entropy->fixed_bin, 1);
801 }
802 st += 2;
803 /* Figure F.8: Encoding the magnitude category of v */
804 m = 0;
805 if (v -= 1) {
806 arith_encode(cinfo, st, 1);
807 m = 1;
808 v2 = v;
809 if (v2 >>= 1) {
810 arith_encode(cinfo, st, 1);
811 m <<= 1;
812 st = entropy->ac_stats[tbl] +
813 (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
814 while (v2 >>= 1) {
815 arith_encode(cinfo, st, 1);
816 m <<= 1;
817 st += 1;
818 }
819 }
820 }
821 arith_encode(cinfo, st, 0);
822 /* Figure F.9: Encoding the magnitude bit pattern of v */
823 st += 14;
824 while (m >>= 1)
825 arith_encode(cinfo, st, (m & v) ? 1 : 0);
826 }
827 /* Encode EOB decision only if k < cinfo->lim_Se */
828 if (k < cinfo->lim_Se) {
829 st = entropy->ac_stats[tbl] + 3 * k;
830 arith_encode(cinfo, st, 1);
831 }
832 }
833
834 return TRUE;
835 }
836
837
838 /*
839 * Initialize for an arithmetic-compressed scan.
840 */
841
842 METHODDEF(void)
843 start_pass (j_compress_ptr cinfo, boolean gather_statistics)
844 {
845 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
846 int ci, tbl;
847 jpeg_component_info * compptr;
848
849 if (gather_statistics)
850 /* Make sure to avoid that in the master control logic!
851 * We are fully adaptive here and need no extra
852 * statistics gathering pass!
853 */
854 ERREXIT(cinfo, JERR_NOT_COMPILED);
855
856 /* We assume jcmaster.c already validated the progressive scan parameters. */
857
858 /* Select execution routines */
859 if (cinfo->progressive_mode) {
860 if (cinfo->Ah == 0) {
861 if (cinfo->Ss == 0)
862 entropy->pub.encode_mcu = encode_mcu_DC_first;
863 else
864 entropy->pub.encode_mcu = encode_mcu_AC_first;
865 } else {
866 if (cinfo->Ss == 0)
867 entropy->pub.encode_mcu = encode_mcu_DC_refine;
868 else
869 entropy->pub.encode_mcu = encode_mcu_AC_refine;
870 }
871 } else
872 entropy->pub.encode_mcu = encode_mcu;
873
874 /* Allocate & initialize requested statistics areas */
875 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
876 compptr = cinfo->cur_comp_info[ci];
877 /* DC needs no table for refinement scan */
878 if (cinfo->Ss == 0 && cinfo->Ah == 0) {
879 tbl = compptr->dc_tbl_no;
880 if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
881 ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
882 if (entropy->dc_stats[tbl] == NULL)
883 entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
884 ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
885 MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
886 /* Initialize DC predictions to 0 */
887 entropy->last_dc_val[ci] = 0;
888 entropy->dc_context[ci] = 0;
889 }
890 /* AC needs no table when not present */
891 if (cinfo->Se) {
892 tbl = compptr->ac_tbl_no;
893 if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
894 ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
895 if (entropy->ac_stats[tbl] == NULL)
896 entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
897 ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
898 MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
899 #ifdef CALCULATE_SPECTRAL_CONDITIONING
900 if (cinfo->progressive_mode)
901 /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
902 cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
903 #endif
904 }
905 }
906
907 /* Initialize arithmetic encoding variables */
908 entropy->c = 0;
909 entropy->a = 0x10000L;
910 entropy->sc = 0;
911 entropy->zc = 0;
912 entropy->ct = 11;
913 entropy->buffer = -1; /* empty */
914
915 /* Initialize restart stuff */
916 entropy->restarts_to_go = cinfo->restart_interval;
917 entropy->next_restart_num = 0;
918 }
919
920
921 /*
922 * Module initialization routine for arithmetic entropy encoding.
923 */
924
925 GLOBAL(void)
926 jinit_arith_encoder (j_compress_ptr cinfo)
927 {
928 arith_entropy_ptr entropy;
929 int i;
930
931 entropy = (arith_entropy_ptr) (*cinfo->mem->alloc_small)
932 ((j_common_ptr) cinfo, JPOOL_IMAGE, SIZEOF(arith_entropy_encoder));
933 cinfo->entropy = &entropy->pub;
934 entropy->pub.start_pass = start_pass;
935 entropy->pub.finish_pass = finish_pass;
936
937 /* Mark tables unallocated */
938 for (i = 0; i < NUM_ARITH_TBLS; i++) {
939 entropy->dc_stats[i] = NULL;
940 entropy->ac_stats[i] = NULL;
941 }
942
943 /* Initialize index for fixed probability estimation */
944 entropy->fixed_bin[0] = 113;
945 }