blob: 046e2e18d4876502f0bce0e7f064eb8b71f6b122 [file] [log] [blame]
Thomas G. Lanebc79e061995-08-02 00:00:00 +00001/*
2 * jcphuff.c
3 *
DRC5033f3e2014-05-18 18:33:44 +00004 * This file was part of the Independent JPEG Group's software:
Thomas G. Lane5ead57a1998-03-27 00:00:00 +00005 * Copyright (C) 1995-1997, Thomas G. Lane.
DRC1e32fe32015-10-14 17:32:39 -05006 * libjpeg-turbo Modifications:
7 * Copyright (C) 2015, D. R. Commander.
DRC7e3acc02015-10-10 10:25:46 -05008 * For conditions of distribution and use, see the accompanying README.ijg
9 * file.
Thomas G. Lanebc79e061995-08-02 00:00:00 +000010 *
11 * This file contains Huffman entropy encoding routines for progressive JPEG.
12 *
13 * We do not support output suspension in this module, since the library
14 * currently does not allow multiple-scan files to be written with output
15 * suspension.
16 */
17
18#define JPEG_INTERNALS
19#include "jinclude.h"
20#include "jpeglib.h"
DRCe5eaf372014-05-09 18:00:32 +000021#include "jchuff.h" /* Declarations shared with jchuff.c */
Thomas G. Lanebc79e061995-08-02 00:00:00 +000022
23#ifdef C_PROGRESSIVE_SUPPORTED
24
25/* Expanded entropy encoder object for progressive Huffman encoding. */
26
27typedef struct {
28 struct jpeg_entropy_encoder pub; /* public fields */
29
30 /* Mode flag: TRUE for optimization, FALSE for actual data output */
31 boolean gather_statistics;
32
33 /* Bit-level coding status.
34 * next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
35 */
DRCbd498032016-02-19 08:53:33 -060036 JOCTET *next_output_byte; /* => next byte to write in buffer */
DRCe5eaf372014-05-09 18:00:32 +000037 size_t free_in_buffer; /* # of byte spaces remaining in buffer */
DRCaa769fe2015-10-15 02:25:00 -050038 size_t put_buffer; /* current bit-accumulation buffer */
DRCe5eaf372014-05-09 18:00:32 +000039 int put_bits; /* # of bits now in it */
40 j_compress_ptr cinfo; /* link to cinfo (needed for dump_buffer) */
Thomas G. Lanebc79e061995-08-02 00:00:00 +000041
42 /* Coding status for DC components */
43 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
44
45 /* Coding status for AC components */
DRCe5eaf372014-05-09 18:00:32 +000046 int ac_tbl_no; /* the table number of the single component */
47 unsigned int EOBRUN; /* run length of EOBs */
48 unsigned int BE; /* # of buffered correction bits before MCU */
DRCbd498032016-02-19 08:53:33 -060049 char *bit_buffer; /* buffer for correction bits (1 per char) */
Thomas G. Lanebc79e061995-08-02 00:00:00 +000050 /* packing correction bits tightly would save some space but cost time... */
51
DRCe5eaf372014-05-09 18:00:32 +000052 unsigned int restarts_to_go; /* MCUs left in this restart interval */
53 int next_restart_num; /* next restart number to write (0-7) */
Thomas G. Lanebc79e061995-08-02 00:00:00 +000054
55 /* Pointers to derived tables (these workspaces have image lifespan).
56 * Since any one scan codes only DC or only AC, we only need one set
57 * of tables, not one for DC and one for AC.
58 */
DRCbd498032016-02-19 08:53:33 -060059 c_derived_tbl *derived_tbls[NUM_HUFF_TBLS];
Thomas G. Lanebc79e061995-08-02 00:00:00 +000060
61 /* Statistics tables for optimization; again, one set is enough */
DRCbd498032016-02-19 08:53:33 -060062 long *count_ptrs[NUM_HUFF_TBLS];
Thomas G. Lanebc79e061995-08-02 00:00:00 +000063} phuff_entropy_encoder;
64
DRCbd498032016-02-19 08:53:33 -060065typedef phuff_entropy_encoder *phuff_entropy_ptr;
Thomas G. Lanebc79e061995-08-02 00:00:00 +000066
67/* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
68 * buffer can hold. Larger sizes may slightly improve compression, but
69 * 1000 is already well into the realm of overkill.
70 * The minimum safe size is 64 bits.
71 */
72
DRCe5eaf372014-05-09 18:00:32 +000073#define MAX_CORR_BITS 1000 /* Max # of correction bits I can buffer */
Thomas G. Lanebc79e061995-08-02 00:00:00 +000074
DRC1e32fe32015-10-14 17:32:39 -050075/* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than JLONG.
76 * We assume that int right shift is unsigned if JLONG right shift is,
Thomas G. Lanebc79e061995-08-02 00:00:00 +000077 * which should be safe.
78 */
79
80#ifdef RIGHT_SHIFT_IS_UNSIGNED
DRCe5eaf372014-05-09 18:00:32 +000081#define ISHIFT_TEMPS int ishift_temp;
Thomas G. Lanebc79e061995-08-02 00:00:00 +000082#define IRIGHT_SHIFT(x,shft) \
DRCe5eaf372014-05-09 18:00:32 +000083 ((ishift_temp = (x)) < 0 ? \
84 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
85 (ishift_temp >> (shft)))
Thomas G. Lanebc79e061995-08-02 00:00:00 +000086#else
87#define ISHIFT_TEMPS
DRCe5eaf372014-05-09 18:00:32 +000088#define IRIGHT_SHIFT(x,shft) ((x) >> (shft))
Thomas G. Lanebc79e061995-08-02 00:00:00 +000089#endif
90
91/* Forward declarations */
DRCbc56b752014-05-16 10:43:44 +000092METHODDEF(boolean) encode_mcu_DC_first (j_compress_ptr cinfo,
93 JBLOCKROW *MCU_data);
94METHODDEF(boolean) encode_mcu_AC_first (j_compress_ptr cinfo,
95 JBLOCKROW *MCU_data);
96METHODDEF(boolean) encode_mcu_DC_refine (j_compress_ptr cinfo,
97 JBLOCKROW *MCU_data);
98METHODDEF(boolean) encode_mcu_AC_refine (j_compress_ptr cinfo,
99 JBLOCKROW *MCU_data);
100METHODDEF(void) finish_pass_phuff (j_compress_ptr cinfo);
101METHODDEF(void) finish_pass_gather_phuff (j_compress_ptr cinfo);
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000102
103
104/*
105 * Initialize for a Huffman-compressed scan using progressive JPEG.
106 */
107
Thomas G. Lane489583f1996-02-07 00:00:00 +0000108METHODDEF(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000109start_pass_phuff (j_compress_ptr cinfo, boolean gather_statistics)
DRCe5eaf372014-05-09 18:00:32 +0000110{
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000111 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
112 boolean is_DC_band;
113 int ci, tbl;
DRCbd498032016-02-19 08:53:33 -0600114 jpeg_component_info *compptr;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000115
116 entropy->cinfo = cinfo;
117 entropy->gather_statistics = gather_statistics;
118
119 is_DC_band = (cinfo->Ss == 0);
120
121 /* We assume jcmaster.c already validated the scan parameters. */
122
123 /* Select execution routines */
124 if (cinfo->Ah == 0) {
125 if (is_DC_band)
126 entropy->pub.encode_mcu = encode_mcu_DC_first;
127 else
128 entropy->pub.encode_mcu = encode_mcu_AC_first;
129 } else {
130 if (is_DC_band)
131 entropy->pub.encode_mcu = encode_mcu_DC_refine;
132 else {
133 entropy->pub.encode_mcu = encode_mcu_AC_refine;
134 /* AC refinement needs a correction bit buffer */
135 if (entropy->bit_buffer == NULL)
DRCe5eaf372014-05-09 18:00:32 +0000136 entropy->bit_buffer = (char *)
137 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
DRC5de454b2014-05-18 19:04:03 +0000138 MAX_CORR_BITS * sizeof(char));
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000139 }
140 }
141 if (gather_statistics)
142 entropy->pub.finish_pass = finish_pass_gather_phuff;
143 else
144 entropy->pub.finish_pass = finish_pass_phuff;
145
146 /* Only DC coefficients may be interleaved, so cinfo->comps_in_scan = 1
147 * for AC coefficients.
148 */
149 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
150 compptr = cinfo->cur_comp_info[ci];
151 /* Initialize DC predictions to 0 */
152 entropy->last_dc_val[ci] = 0;
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000153 /* Get table index */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000154 if (is_DC_band) {
DRCe5eaf372014-05-09 18:00:32 +0000155 if (cinfo->Ah != 0) /* DC refinement needs no table */
156 continue;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000157 tbl = compptr->dc_tbl_no;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000158 } else {
159 entropy->ac_tbl_no = tbl = compptr->ac_tbl_no;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000160 }
161 if (gather_statistics) {
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000162 /* Check for invalid table index */
163 /* (make_c_derived_tbl does this in the other path) */
164 if (tbl < 0 || tbl >= NUM_HUFF_TBLS)
165 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl);
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000166 /* Allocate and zero the statistics tables */
167 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
168 if (entropy->count_ptrs[tbl] == NULL)
DRCe5eaf372014-05-09 18:00:32 +0000169 entropy->count_ptrs[tbl] = (long *)
170 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
DRC5de454b2014-05-18 19:04:03 +0000171 257 * sizeof(long));
172 MEMZERO(entropy->count_ptrs[tbl], 257 * sizeof(long));
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000173 } else {
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000174 /* Compute derived values for Huffman table */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000175 /* We may do this more than once for a table, but it's not expensive */
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000176 jpeg_make_c_derived_tbl(cinfo, is_DC_band, tbl,
DRCe5eaf372014-05-09 18:00:32 +0000177 & entropy->derived_tbls[tbl]);
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000178 }
179 }
180
181 /* Initialize AC stuff */
182 entropy->EOBRUN = 0;
183 entropy->BE = 0;
184
185 /* Initialize bit buffer to empty */
186 entropy->put_buffer = 0;
187 entropy->put_bits = 0;
188
189 /* Initialize restart stuff */
190 entropy->restarts_to_go = cinfo->restart_interval;
191 entropy->next_restart_num = 0;
192}
193
194
195/* Outputting bytes to the file.
196 * NB: these must be called only when actually outputting,
197 * that is, entropy->gather_statistics == FALSE.
198 */
199
200/* Emit a byte */
201#define emit_byte(entropy,val) \
DRCe5eaf372014-05-09 18:00:32 +0000202 { *(entropy)->next_output_byte++ = (JOCTET) (val); \
203 if (--(entropy)->free_in_buffer == 0) \
204 dump_buffer(entropy); }
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000205
206
Thomas G. Lane489583f1996-02-07 00:00:00 +0000207LOCAL(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000208dump_buffer (phuff_entropy_ptr entropy)
209/* Empty the output buffer; we do not support suspension in this module. */
210{
DRCbd498032016-02-19 08:53:33 -0600211 struct jpeg_destination_mgr *dest = entropy->cinfo->dest;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000212
213 if (! (*dest->empty_output_buffer) (entropy->cinfo))
214 ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND);
215 /* After a successful buffer dump, must reset buffer pointers */
216 entropy->next_output_byte = dest->next_output_byte;
217 entropy->free_in_buffer = dest->free_in_buffer;
218}
219
220
221/* Outputting bits to the file */
222
223/* Only the right 24 bits of put_buffer are used; the valid bits are
224 * left-justified in this part. At most 16 bits can be passed to emit_bits
225 * in one call, and we never retain more than 7 bits in put_buffer
226 * between calls, so 24 bits are sufficient.
227 */
228
Thomas G. Lane489583f1996-02-07 00:00:00 +0000229LOCAL(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000230emit_bits (phuff_entropy_ptr entropy, unsigned int code, int size)
231/* Emit some bits, unless we are in gather mode */
232{
233 /* This routine is heavily used, so it's worth coding tightly. */
DRCd65e7682015-10-14 22:26:25 -0500234 register size_t put_buffer = (size_t) code;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000235 register int put_bits = entropy->put_bits;
236
237 /* if size is 0, caller used an invalid Huffman table entry */
238 if (size == 0)
239 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
240
241 if (entropy->gather_statistics)
DRCe5eaf372014-05-09 18:00:32 +0000242 return; /* do nothing if we're only getting stats */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000243
DRCaa769fe2015-10-15 02:25:00 -0500244 put_buffer &= (((size_t) 1)<<size) - 1; /* mask off any extra bits in code */
DRCe5eaf372014-05-09 18:00:32 +0000245
246 put_bits += size; /* new number of bits in buffer */
247
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000248 put_buffer <<= 24 - put_bits; /* align incoming bits */
249
250 put_buffer |= entropy->put_buffer; /* and merge with old buffer contents */
251
252 while (put_bits >= 8) {
253 int c = (int) ((put_buffer >> 16) & 0xFF);
DRCe5eaf372014-05-09 18:00:32 +0000254
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000255 emit_byte(entropy, c);
DRCe5eaf372014-05-09 18:00:32 +0000256 if (c == 0xFF) { /* need to stuff a zero byte? */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000257 emit_byte(entropy, 0);
258 }
259 put_buffer <<= 8;
260 put_bits -= 8;
261 }
262
263 entropy->put_buffer = put_buffer; /* update variables */
264 entropy->put_bits = put_bits;
265}
266
267
Thomas G. Lane489583f1996-02-07 00:00:00 +0000268LOCAL(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000269flush_bits (phuff_entropy_ptr entropy)
270{
271 emit_bits(entropy, 0x7F, 7); /* fill any partial byte with ones */
272 entropy->put_buffer = 0; /* and reset bit-buffer to empty */
273 entropy->put_bits = 0;
274}
275
276
277/*
278 * Emit (or just count) a Huffman symbol.
279 */
280
Thomas G. Lane489583f1996-02-07 00:00:00 +0000281LOCAL(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000282emit_symbol (phuff_entropy_ptr entropy, int tbl_no, int symbol)
283{
284 if (entropy->gather_statistics)
285 entropy->count_ptrs[tbl_no][symbol]++;
286 else {
DRCbd498032016-02-19 08:53:33 -0600287 c_derived_tbl *tbl = entropy->derived_tbls[tbl_no];
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000288 emit_bits(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]);
289 }
290}
291
292
293/*
294 * Emit bits from a correction bit buffer.
295 */
296
Thomas G. Lane489583f1996-02-07 00:00:00 +0000297LOCAL(void)
DRCbd498032016-02-19 08:53:33 -0600298emit_buffered_bits (phuff_entropy_ptr entropy, char *bufstart,
DRCe5eaf372014-05-09 18:00:32 +0000299 unsigned int nbits)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000300{
301 if (entropy->gather_statistics)
DRCe5eaf372014-05-09 18:00:32 +0000302 return; /* no real work */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000303
304 while (nbits > 0) {
305 emit_bits(entropy, (unsigned int) (*bufstart), 1);
306 bufstart++;
307 nbits--;
308 }
309}
310
311
312/*
313 * Emit any pending EOBRUN symbol.
314 */
315
Thomas G. Lane489583f1996-02-07 00:00:00 +0000316LOCAL(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000317emit_eobrun (phuff_entropy_ptr entropy)
318{
319 register int temp, nbits;
320
DRCe5eaf372014-05-09 18:00:32 +0000321 if (entropy->EOBRUN > 0) { /* if there is any pending EOBRUN */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000322 temp = entropy->EOBRUN;
323 nbits = 0;
324 while ((temp >>= 1))
325 nbits++;
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000326 /* safety check: shouldn't happen given limited correction-bit buffer */
327 if (nbits > 14)
328 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000329
330 emit_symbol(entropy, entropy->ac_tbl_no, nbits << 4);
331 if (nbits)
332 emit_bits(entropy, entropy->EOBRUN, nbits);
333
334 entropy->EOBRUN = 0;
335
336 /* Emit any buffered correction bits */
337 emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE);
338 entropy->BE = 0;
339 }
340}
341
342
343/*
344 * Emit a restart marker & resynchronize predictions.
345 */
346
Thomas G. Lane489583f1996-02-07 00:00:00 +0000347LOCAL(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000348emit_restart (phuff_entropy_ptr entropy, int restart_num)
349{
350 int ci;
351
352 emit_eobrun(entropy);
353
354 if (! entropy->gather_statistics) {
355 flush_bits(entropy);
356 emit_byte(entropy, 0xFF);
357 emit_byte(entropy, JPEG_RST0 + restart_num);
358 }
359
360 if (entropy->cinfo->Ss == 0) {
361 /* Re-initialize DC predictions to 0 */
362 for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++)
363 entropy->last_dc_val[ci] = 0;
364 } else {
365 /* Re-initialize all AC-related fields to 0 */
366 entropy->EOBRUN = 0;
367 entropy->BE = 0;
368 }
369}
370
371
372/*
373 * MCU encoding for DC initial scan (either spectral selection,
374 * or first pass of successive approximation).
375 */
376
Thomas G. Lane489583f1996-02-07 00:00:00 +0000377METHODDEF(boolean)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000378encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
379{
380 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
381 register int temp, temp2;
382 register int nbits;
383 int blkn, ci;
384 int Al = cinfo->Al;
385 JBLOCKROW block;
DRCbd498032016-02-19 08:53:33 -0600386 jpeg_component_info *compptr;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000387 ISHIFT_TEMPS
388
389 entropy->next_output_byte = cinfo->dest->next_output_byte;
390 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
391
392 /* Emit restart marker if needed */
393 if (cinfo->restart_interval)
394 if (entropy->restarts_to_go == 0)
395 emit_restart(entropy, entropy->next_restart_num);
396
397 /* Encode the MCU data blocks */
398 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
399 block = MCU_data[blkn];
400 ci = cinfo->MCU_membership[blkn];
401 compptr = cinfo->cur_comp_info[ci];
402
403 /* Compute the DC value after the required point transform by Al.
404 * This is simply an arithmetic right shift.
405 */
406 temp2 = IRIGHT_SHIFT((int) ((*block)[0]), Al);
407
408 /* DC differences are figured on the point-transformed values. */
409 temp = temp2 - entropy->last_dc_val[ci];
410 entropy->last_dc_val[ci] = temp2;
411
412 /* Encode the DC coefficient difference per section G.1.2.1 */
413 temp2 = temp;
414 if (temp < 0) {
DRCe5eaf372014-05-09 18:00:32 +0000415 temp = -temp; /* temp is abs value of input */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000416 /* For a negative input, want temp2 = bitwise complement of abs(input) */
417 /* This code assumes we are on a two's complement machine */
418 temp2--;
419 }
DRCe5eaf372014-05-09 18:00:32 +0000420
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000421 /* Find the number of bits needed for the magnitude of the coefficient */
422 nbits = 0;
423 while (temp) {
424 nbits++;
425 temp >>= 1;
426 }
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000427 /* Check for out-of-range coefficient values.
428 * Since we're encoding a difference, the range limit is twice as much.
429 */
430 if (nbits > MAX_COEF_BITS+1)
431 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
DRCe5eaf372014-05-09 18:00:32 +0000432
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000433 /* Count/emit the Huffman-coded symbol for the number of bits */
434 emit_symbol(entropy, compptr->dc_tbl_no, nbits);
DRCe5eaf372014-05-09 18:00:32 +0000435
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000436 /* Emit that number of bits of the value, if positive, */
437 /* or the complement of its magnitude, if negative. */
DRCe5eaf372014-05-09 18:00:32 +0000438 if (nbits) /* emit_bits rejects calls with size 0 */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000439 emit_bits(entropy, (unsigned int) temp2, nbits);
440 }
441
442 cinfo->dest->next_output_byte = entropy->next_output_byte;
443 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
444
445 /* Update restart-interval state too */
446 if (cinfo->restart_interval) {
447 if (entropy->restarts_to_go == 0) {
448 entropy->restarts_to_go = cinfo->restart_interval;
449 entropy->next_restart_num++;
450 entropy->next_restart_num &= 7;
451 }
452 entropy->restarts_to_go--;
453 }
454
455 return TRUE;
456}
457
458
459/*
460 * MCU encoding for AC initial scan (either spectral selection,
461 * or first pass of successive approximation).
462 */
463
Thomas G. Lane489583f1996-02-07 00:00:00 +0000464METHODDEF(boolean)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000465encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
466{
467 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
468 register int temp, temp2;
469 register int nbits;
470 register int r, k;
471 int Se = cinfo->Se;
472 int Al = cinfo->Al;
473 JBLOCKROW block;
474
475 entropy->next_output_byte = cinfo->dest->next_output_byte;
476 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
477
478 /* Emit restart marker if needed */
479 if (cinfo->restart_interval)
480 if (entropy->restarts_to_go == 0)
481 emit_restart(entropy, entropy->next_restart_num);
482
483 /* Encode the MCU data block */
484 block = MCU_data[0];
485
486 /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
DRCe5eaf372014-05-09 18:00:32 +0000487
488 r = 0; /* r = run length of zeros */
489
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000490 for (k = cinfo->Ss; k <= Se; k++) {
491 if ((temp = (*block)[jpeg_natural_order[k]]) == 0) {
492 r++;
493 continue;
494 }
495 /* We must apply the point transform by Al. For AC coefficients this
496 * is an integer division with rounding towards 0. To do this portably
497 * in C, we shift after obtaining the absolute value; so the code is
498 * interwoven with finding the abs value (temp) and output bits (temp2).
499 */
500 if (temp < 0) {
DRCe5eaf372014-05-09 18:00:32 +0000501 temp = -temp; /* temp is abs value of input */
502 temp >>= Al; /* apply the point transform */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000503 /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
504 temp2 = ~temp;
505 } else {
DRCe5eaf372014-05-09 18:00:32 +0000506 temp >>= Al; /* apply the point transform */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000507 temp2 = temp;
508 }
509 /* Watch out for case that nonzero coef is zero after point transform */
510 if (temp == 0) {
511 r++;
512 continue;
513 }
514
515 /* Emit any pending EOBRUN */
516 if (entropy->EOBRUN > 0)
517 emit_eobrun(entropy);
518 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
519 while (r > 15) {
520 emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
521 r -= 16;
522 }
523
524 /* Find the number of bits needed for the magnitude of the coefficient */
DRCe5eaf372014-05-09 18:00:32 +0000525 nbits = 1; /* there must be at least one 1 bit */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000526 while ((temp >>= 1))
527 nbits++;
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000528 /* Check for out-of-range coefficient values */
529 if (nbits > MAX_COEF_BITS)
530 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000531
532 /* Count/emit Huffman symbol for run length / number of bits */
533 emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits);
534
535 /* Emit that number of bits of the value, if positive, */
536 /* or the complement of its magnitude, if negative. */
537 emit_bits(entropy, (unsigned int) temp2, nbits);
538
DRCe5eaf372014-05-09 18:00:32 +0000539 r = 0; /* reset zero run length */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000540 }
541
DRCe5eaf372014-05-09 18:00:32 +0000542 if (r > 0) { /* If there are trailing zeroes, */
543 entropy->EOBRUN++; /* count an EOB */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000544 if (entropy->EOBRUN == 0x7FFF)
DRCe5eaf372014-05-09 18:00:32 +0000545 emit_eobrun(entropy); /* force it out to avoid overflow */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000546 }
547
548 cinfo->dest->next_output_byte = entropy->next_output_byte;
549 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
550
551 /* Update restart-interval state too */
552 if (cinfo->restart_interval) {
553 if (entropy->restarts_to_go == 0) {
554 entropy->restarts_to_go = cinfo->restart_interval;
555 entropy->next_restart_num++;
556 entropy->next_restart_num &= 7;
557 }
558 entropy->restarts_to_go--;
559 }
560
561 return TRUE;
562}
563
564
565/*
566 * MCU encoding for DC successive approximation refinement scan.
567 * Note: we assume such scans can be multi-component, although the spec
568 * is not very clear on the point.
569 */
570
Thomas G. Lane489583f1996-02-07 00:00:00 +0000571METHODDEF(boolean)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000572encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
573{
574 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
575 register int temp;
576 int blkn;
577 int Al = cinfo->Al;
578 JBLOCKROW block;
579
580 entropy->next_output_byte = cinfo->dest->next_output_byte;
581 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
582
583 /* Emit restart marker if needed */
584 if (cinfo->restart_interval)
585 if (entropy->restarts_to_go == 0)
586 emit_restart(entropy, entropy->next_restart_num);
587
588 /* Encode the MCU data blocks */
589 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
590 block = MCU_data[blkn];
591
592 /* We simply emit the Al'th bit of the DC coefficient value. */
593 temp = (*block)[0];
594 emit_bits(entropy, (unsigned int) (temp >> Al), 1);
595 }
596
597 cinfo->dest->next_output_byte = entropy->next_output_byte;
598 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
599
600 /* Update restart-interval state too */
601 if (cinfo->restart_interval) {
602 if (entropy->restarts_to_go == 0) {
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 return TRUE;
611}
612
613
614/*
615 * MCU encoding for AC successive approximation refinement scan.
616 */
617
Thomas G. Lane489583f1996-02-07 00:00:00 +0000618METHODDEF(boolean)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000619encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
620{
621 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
622 register int temp;
623 register int r, k;
624 int EOB;
625 char *BR_buffer;
626 unsigned int BR;
627 int Se = cinfo->Se;
628 int Al = cinfo->Al;
629 JBLOCKROW block;
630 int absvalues[DCTSIZE2];
631
632 entropy->next_output_byte = cinfo->dest->next_output_byte;
633 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
634
635 /* Emit restart marker if needed */
636 if (cinfo->restart_interval)
637 if (entropy->restarts_to_go == 0)
638 emit_restart(entropy, entropy->next_restart_num);
639
640 /* Encode the MCU data block */
641 block = MCU_data[0];
642
643 /* It is convenient to make a pre-pass to determine the transformed
644 * coefficients' absolute values and the EOB position.
645 */
646 EOB = 0;
647 for (k = cinfo->Ss; k <= Se; k++) {
648 temp = (*block)[jpeg_natural_order[k]];
649 /* We must apply the point transform by Al. For AC coefficients this
650 * is an integer division with rounding towards 0. To do this portably
651 * in C, we shift after obtaining the absolute value.
652 */
653 if (temp < 0)
DRCe5eaf372014-05-09 18:00:32 +0000654 temp = -temp; /* temp is abs value of input */
655 temp >>= Al; /* apply the point transform */
656 absvalues[k] = temp; /* save abs value for main pass */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000657 if (temp == 1)
DRCe5eaf372014-05-09 18:00:32 +0000658 EOB = k; /* EOB = index of last newly-nonzero coef */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000659 }
660
661 /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
DRCe5eaf372014-05-09 18:00:32 +0000662
663 r = 0; /* r = run length of zeros */
664 BR = 0; /* BR = count of buffered bits added now */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000665 BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */
666
667 for (k = cinfo->Ss; k <= Se; k++) {
668 if ((temp = absvalues[k]) == 0) {
669 r++;
670 continue;
671 }
672
673 /* Emit any required ZRLs, but not if they can be folded into EOB */
674 while (r > 15 && k <= EOB) {
675 /* emit any pending EOBRUN and the BE correction bits */
676 emit_eobrun(entropy);
677 /* Emit ZRL */
678 emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
679 r -= 16;
680 /* Emit buffered correction bits that must be associated with ZRL */
681 emit_buffered_bits(entropy, BR_buffer, BR);
682 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
683 BR = 0;
684 }
685
686 /* If the coef was previously nonzero, it only needs a correction bit.
687 * NOTE: a straight translation of the spec's figure G.7 would suggest
688 * that we also need to test r > 15. But if r > 15, we can only get here
689 * if k > EOB, which implies that this coefficient is not 1.
690 */
691 if (temp > 1) {
692 /* The correction bit is the next bit of the absolute value. */
693 BR_buffer[BR++] = (char) (temp & 1);
694 continue;
695 }
696
697 /* Emit any pending EOBRUN and the BE correction bits */
698 emit_eobrun(entropy);
699
700 /* Count/emit Huffman symbol for run length / number of bits */
701 emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1);
702
703 /* Emit output bit for newly-nonzero coef */
704 temp = ((*block)[jpeg_natural_order[k]] < 0) ? 0 : 1;
705 emit_bits(entropy, (unsigned int) temp, 1);
706
707 /* Emit buffered correction bits that must be associated with this code */
708 emit_buffered_bits(entropy, BR_buffer, BR);
709 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
710 BR = 0;
DRCe5eaf372014-05-09 18:00:32 +0000711 r = 0; /* reset zero run length */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000712 }
713
DRCe5eaf372014-05-09 18:00:32 +0000714 if (r > 0 || BR > 0) { /* If there are trailing zeroes, */
715 entropy->EOBRUN++; /* count an EOB */
716 entropy->BE += BR; /* concat my correction bits to older ones */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000717 /* We force out the EOB if we risk either:
718 * 1. overflow of the EOB counter;
719 * 2. overflow of the correction bit buffer during the next MCU.
720 */
721 if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1))
722 emit_eobrun(entropy);
723 }
724
725 cinfo->dest->next_output_byte = entropy->next_output_byte;
726 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
727
728 /* Update restart-interval state too */
729 if (cinfo->restart_interval) {
730 if (entropy->restarts_to_go == 0) {
731 entropy->restarts_to_go = cinfo->restart_interval;
732 entropy->next_restart_num++;
733 entropy->next_restart_num &= 7;
734 }
735 entropy->restarts_to_go--;
736 }
737
738 return TRUE;
739}
740
741
742/*
743 * Finish up at the end of a Huffman-compressed progressive scan.
744 */
745
Thomas G. Lane489583f1996-02-07 00:00:00 +0000746METHODDEF(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000747finish_pass_phuff (j_compress_ptr cinfo)
DRCe5eaf372014-05-09 18:00:32 +0000748{
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000749 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
750
751 entropy->next_output_byte = cinfo->dest->next_output_byte;
752 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
753
754 /* Flush out any buffered data */
755 emit_eobrun(entropy);
756 flush_bits(entropy);
757
758 cinfo->dest->next_output_byte = entropy->next_output_byte;
759 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
760}
761
762
763/*
764 * Finish up a statistics-gathering pass and create the new Huffman tables.
765 */
766
Thomas G. Lane489583f1996-02-07 00:00:00 +0000767METHODDEF(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000768finish_pass_gather_phuff (j_compress_ptr cinfo)
769{
770 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
771 boolean is_DC_band;
772 int ci, tbl;
DRCbd498032016-02-19 08:53:33 -0600773 jpeg_component_info *compptr;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000774 JHUFF_TBL **htblptr;
775 boolean did[NUM_HUFF_TBLS];
776
777 /* Flush out buffered data (all we care about is counting the EOB symbol) */
778 emit_eobrun(entropy);
779
780 is_DC_band = (cinfo->Ss == 0);
781
782 /* It's important not to apply jpeg_gen_optimal_table more than once
783 * per table, because it clobbers the input frequency counts!
784 */
DRC5de454b2014-05-18 19:04:03 +0000785 MEMZERO(did, sizeof(did));
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000786
787 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
788 compptr = cinfo->cur_comp_info[ci];
789 if (is_DC_band) {
DRCe5eaf372014-05-09 18:00:32 +0000790 if (cinfo->Ah != 0) /* DC refinement needs no table */
791 continue;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000792 tbl = compptr->dc_tbl_no;
793 } else {
794 tbl = compptr->ac_tbl_no;
795 }
796 if (! did[tbl]) {
797 if (is_DC_band)
798 htblptr = & cinfo->dc_huff_tbl_ptrs[tbl];
799 else
800 htblptr = & cinfo->ac_huff_tbl_ptrs[tbl];
801 if (*htblptr == NULL)
802 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
803 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[tbl]);
804 did[tbl] = TRUE;
805 }
806 }
807}
808
809
810/*
811 * Module initialization routine for progressive Huffman entropy encoding.
812 */
813
Thomas G. Lane489583f1996-02-07 00:00:00 +0000814GLOBAL(void)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000815jinit_phuff_encoder (j_compress_ptr cinfo)
816{
817 phuff_entropy_ptr entropy;
818 int i;
819
820 entropy = (phuff_entropy_ptr)
821 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
DRC5de454b2014-05-18 19:04:03 +0000822 sizeof(phuff_entropy_encoder));
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000823 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
824 entropy->pub.start_pass = start_pass_phuff;
825
826 /* Mark tables unallocated */
827 for (i = 0; i < NUM_HUFF_TBLS; i++) {
828 entropy->derived_tbls[i] = NULL;
829 entropy->count_ptrs[i] = NULL;
830 }
DRCe5eaf372014-05-09 18:00:32 +0000831 entropy->bit_buffer = NULL; /* needed only in AC refinement scan */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000832}
833
834#endif /* C_PROGRESSIVE_SUPPORTED */