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