ReactOS 0.4.15-dev-7842-g558ab78
jcarith.c
Go to the documentation of this file.
1/*
2 * jcarith.c
3 *
4 * Developed 1997-2019 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
23typedef 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];
47
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
115LOCAL(void)
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
132METHODDEF(void)
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
218LOCAL(void)
219arith_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
320LOCAL(void)
321emit_restart (j_compress_ptr cinfo, int restart_num)
322{
323 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
324 int ci;
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) {
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) {
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
363METHODDEF(boolean)
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;
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
452METHODDEF(boolean)
454{
455 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
456 const int * natural_order;
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
559METHODDEF(boolean)
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
594METHODDEF(boolean)
596{
597 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
598 const int * natural_order;
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
693METHODDEF(boolean)
695{
696 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
697 const int * natural_order;
699 unsigned char *st;
700 int tbl, k, ke;
701 int v, v2, m;
702 int blkn, ci;
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
842METHODDEF(void)
843start_pass (j_compress_ptr cinfo, boolean gather_statistics)
844{
845 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
846 int ci, tbl;
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)
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)
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
925GLOBAL(void)
927{
928 arith_entropy_ptr entropy;
929 int i;
930
931 entropy = (arith_entropy_ptr) (*cinfo->mem->alloc_small)
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}
signed int INT32
#define SIZEOF(_ar)
Definition: calc.h:97
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
const GLdouble * v
Definition: gl.h:2040
GLuint GLfloat * val
Definition: glext.h:7180
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
const GLfloat * m
Definition: glext.h:10848
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
const INT32 jpeg_aritab[113+1]
Definition: jaricom.c:31
emit_restart(j_compress_ptr cinfo, int restart_num)
Definition: jcarith.c:321
encode_mcu_AC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:453
#define ISHIFT_TEMPS
Definition: jcarith.c:110
jinit_arith_encoder(j_compress_ptr cinfo)
Definition: jcarith.c:926
encode_mcu_DC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:364
finish_pass(j_compress_ptr cinfo)
Definition: jcarith.c:133
encode_mcu_DC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:560
encode_mcu(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:694
#define AC_STAT_BINS
Definition: jcarith.c:64
#define IRIGHT_SHIFT(x, shft)
Definition: jcarith.c:111
start_pass(j_compress_ptr cinfo, boolean gather_statistics)
Definition: jcarith.c:843
emit_byte(int val, j_compress_ptr cinfo)
Definition: jcarith.c:116
arith_entropy_encoder * arith_entropy_ptr
Definition: jcarith.c:48
encode_mcu_AC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:595
#define DC_STAT_BINS
Definition: jcarith.c:63
arith_encode(j_compress_ptr cinfo, unsigned char *st, int val)
Definition: jcarith.c:219
jpeg_component_info * compptr
Definition: jdct.h:238
#define ERREXIT1(cinfo, code, p1)
Definition: jerror.h:212
char JOCTET
Definition: jmorecfg.h:167
#define LOCAL(type)
Definition: jmorecfg.h:289
#define METHODDEF(type)
Definition: jmorecfg.h:287
#define GLOBAL(type)
Definition: jmorecfg.h:291
JBLOCK FAR * JBLOCKROW
Definition: jpeglib.h:80
struct jpeg_common_struct * j_common_ptr
Definition: jpeglib.h:284
#define NUM_ARITH_TBLS
Definition: jpeglib.h:54
#define JPEG_RST0
Definition: jpeglib.h:1126
#define JPOOL_IMAGE
Definition: jpeglib.h:808
#define MAX_COMPS_IN_SCAN
Definition: jpeglib.h:55
#define e
Definition: ke_i.h:82
if(dx< 0)
Definition: linetemp.h:194
static char * dest
Definition: rtl.c:135
int k
Definition: mpi.c:3369
#define ERREXIT(msg)
Definition: rdjpgcom.c:72
static calc_node_t temp
Definition: rpn_ieee.c:38
unsigned char fixed_bin[4]
Definition: jcarith.c:45
int dc_context[MAX_COMPS_IN_SCAN]
Definition: jcarith.c:35
unsigned char * ac_stats[NUM_ARITH_TBLS]
Definition: jcarith.c:42
int last_dc_val[MAX_COMPS_IN_SCAN]
Definition: jcarith.c:34
struct jpeg_entropy_encoder pub
Definition: jcarith.c:24
unsigned int restarts_to_go
Definition: jcarith.c:37
unsigned char * dc_stats[NUM_ARITH_TBLS]
Definition: jcarith.c:41
#define MEMZERO(addr, type, size)
Definition: svc_dg.c:324
static unsigned int block
Definition: xmlmemory.c:101