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