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