1 /*
2 * jchuff.c
3 *
4 * Copyright (C) 1991-1994, Thomas G. Lane.
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 Huffman entropy encoding routines.
9 *
10 * Much of the complexity here has to do with supporting output suspension.
11 * If the data destination module demands suspension, we want to be able to
12 * back up to the start of the current MCU. To do this, we copy state
13 * variables into local working storage, and update them back to the
14 * permanent JPEG objects only upon successful completion of an MCU.
15 */
16
17 #define JPEG_INTERNALS
18 #include "jinclude.h"
19 #include "jpeglib.h"
20
21
22 /* Derived data constructed for each Huffman table */
23
24 typedef struct {
25 unsigned int ehufco[256]; /* code for each symbol */
26 char ehufsi[256]; /* length of code for each symbol */
27 /* If no code has been allocated for a symbol S, ehufsi[S] contains 0 */
28 } C_DERIVED_TBL;
29
30 /* Expanded entropy encoder object for Huffman encoding.
31 *
32 * The savable_state subrecord contains fields that change within an MCU,
33 * but must not be updated permanently until we complete the MCU.
34 */
35
36 typedef struct {
37 INT32 put_buffer; /* current bit-accumulation buffer */
38 int put_bits; /* # of bits now in it */
39 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
40 } savable_state;
41
42 /* This macro is to work around compilers with missing or broken
43 * structure assignment. You'll need to fix this code if you have
44 * such a compiler and you change MAX_COMPS_IN_SCAN.
45 */
46
47 #ifndef NO_STRUCT_ASSIGN
48 #define ASSIGN_STATE(dest,src) ((dest) = (src))
49 #else
50 #if MAX_COMPS_IN_SCAN == 4
51 #define ASSIGN_STATE(dest,src) \
52 ((dest).put_buffer = (src).put_buffer, \
53 (dest).put_bits = (src).put_bits, \
54 (dest).last_dc_val[0] = (src).last_dc_val[0], \
55 (dest).last_dc_val[1] = (src).last_dc_val[1], \
56 (dest).last_dc_val[2] = (src).last_dc_val[2], \
57 (dest).last_dc_val[3] = (src).last_dc_val[3])
58 #endif
59 #endif
60
61
62 typedef struct {
63 struct jpeg_entropy_encoder pub; /* public fields */
64
65 savable_state saved; /* Bit buffer & DC state at start of MCU */
66
67 /* These fields are NOT loaded into local working state. */
68 unsigned int restarts_to_go; /* MCUs left in this restart interval */
69 int next_restart_num; /* next restart number to write (0-7) */
70
71 /* Pointers to derived tables (these workspaces have image lifespan) */
72 C_DERIVED_TBL * dc_derived_tbls[NUM_HUFF_TBLS];
73 C_DERIVED_TBL * ac_derived_tbls[NUM_HUFF_TBLS];
74
75 #ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */
76 long * dc_count_ptrs[NUM_HUFF_TBLS];
77 long * ac_count_ptrs[NUM_HUFF_TBLS];
78 #endif
79 } huff_entropy_encoder;
80
81 typedef huff_entropy_encoder * huff_entropy_ptr;
82
83 /* Working state while writing an MCU.
84 * This struct contains all the fields that are needed by subroutines.
85 */
86
87 typedef struct {
88 JOCTET * next_output_byte; /* => next byte to write in buffer */
89 size_t free_in_buffer; /* # of byte spaces remaining in buffer */
90 savable_state cur; /* Current bit buffer & DC state */
91 j_compress_ptr cinfo; /* dump_buffer needs access to this */
92 } working_state;
93
94
95 /* Forward declarations */
96 METHODDEF boolean encode_mcu_huff JPP((j_compress_ptr cinfo,
97 JBLOCKROW *MCU_data));
98 METHODDEF void finish_pass_huff JPP((j_compress_ptr cinfo));
99 #ifdef ENTROPY_OPT_SUPPORTED
100 METHODDEF boolean encode_mcu_gather JPP((j_compress_ptr cinfo,
101 JBLOCKROW *MCU_data));
102 METHODDEF void finish_pass_gather JPP((j_compress_ptr cinfo));
103 #endif
104 LOCAL void fix_huff_tbl JPP((j_compress_ptr cinfo, JHUFF_TBL * htbl,
105 C_DERIVED_TBL ** pdtbl));
106
107
108 /*
109 * Initialize for a Huffman-compressed scan.
110 * If gather_statistics is TRUE, we do not output anything during the scan,
111 * just count the Huffman symbols used and generate Huffman code tables.
112 */
113
114 METHODDEF void
start_pass_huff(j_compress_ptr cinfo,boolean gather_statistics)115 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
116 {
117 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
118 int ci, dctbl, actbl;
119 jpeg_component_info * compptr;
120
121 if (gather_statistics) {
122 #ifdef ENTROPY_OPT_SUPPORTED
123 entropy->pub.encode_mcu = encode_mcu_gather;
124 entropy->pub.finish_pass = finish_pass_gather;
125 #else
126 ERREXIT(cinfo, JERR_NOT_COMPILED);
127 #endif
128 } else {
129 entropy->pub.encode_mcu = encode_mcu_huff;
130 entropy->pub.finish_pass = finish_pass_huff;
131 }
132
133 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
134 compptr = cinfo->cur_comp_info[ci];
135 dctbl = compptr->dc_tbl_no;
136 actbl = compptr->ac_tbl_no;
137 /* Make sure requested tables are present */
138 /* (In gather mode, tables need not be allocated yet) */
139 if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS ||
140 (cinfo->dc_huff_tbl_ptrs[dctbl] == NULL && !gather_statistics))
141 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
142 if (actbl < 0 || actbl >= NUM_HUFF_TBLS ||
143 (cinfo->ac_huff_tbl_ptrs[actbl] == NULL && !gather_statistics))
144 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
145 if (gather_statistics) {
146 #ifdef ENTROPY_OPT_SUPPORTED
147 /* Allocate and zero the statistics tables */
148 /* Note that gen_huff_coding expects 257 entries in each table! */
149 if (entropy->dc_count_ptrs[dctbl] == NULL)
150 entropy->dc_count_ptrs[dctbl] = (long *)
151 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
152 257 * SIZEOF(long));
153 MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * SIZEOF(long));
154 if (entropy->ac_count_ptrs[actbl] == NULL)
155 entropy->ac_count_ptrs[actbl] = (long *)
156 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
157 257 * SIZEOF(long));
158 MEMZERO(entropy->ac_count_ptrs[actbl], 257 * SIZEOF(long));
159 #endif
160 } else {
161 /* Compute derived values for Huffman tables */
162 /* We may do this more than once for a table, but it's not expensive */
163 fix_huff_tbl(cinfo, cinfo->dc_huff_tbl_ptrs[dctbl],
164 & entropy->dc_derived_tbls[dctbl]);
165 fix_huff_tbl(cinfo, cinfo->ac_huff_tbl_ptrs[actbl],
166 & entropy->ac_derived_tbls[actbl]);
167 }
168 /* Initialize DC predictions to 0 */
169 entropy->saved.last_dc_val[ci] = 0;
170 }
171
172 /* Initialize bit buffer to empty */
173 entropy->saved.put_buffer = 0;
174 entropy->saved.put_bits = 0;
175
176 /* Initialize restart stuff */
177 entropy->restarts_to_go = cinfo->restart_interval;
178 entropy->next_restart_num = 0;
179 }
180
181
182 LOCAL void
fix_huff_tbl(j_compress_ptr cinfo,JHUFF_TBL * htbl,C_DERIVED_TBL ** pdtbl)183 fix_huff_tbl (j_compress_ptr cinfo, JHUFF_TBL * htbl, C_DERIVED_TBL ** pdtbl)
184 /* Compute the derived values for a Huffman table */
185 {
186 C_DERIVED_TBL *dtbl;
187 int p, i, l, lastp, si;
188 char huffsize[257];
189 unsigned int huffcode[257];
190 unsigned int code;
191
192 /* Allocate a workspace if we haven't already done so. */
193 if (*pdtbl == NULL)
194 *pdtbl = (C_DERIVED_TBL *)
195 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
196 SIZEOF(C_DERIVED_TBL));
197 dtbl = *pdtbl;
198
199 /* Figure C.1: make table of Huffman code length for each symbol */
200 /* Note that this is in code-length order. */
201
202 p = 0;
203 for (l = 1; l <= 16; l++) {
204 for (i = 1; i <= (int) htbl->bits[l]; i++)
205 huffsize[p++] = (char) l;
206 }
207 huffsize[p] = 0;
208 lastp = p;
209
210 /* Figure C.2: generate the codes themselves */
211 /* Note that this is in code-length order. */
212
213 code = 0;
214 si = huffsize[0];
215 p = 0;
216 while (huffsize[p]) {
217 while (((int) huffsize[p]) == si) {
218 huffcode[p++] = code;
219 code++;
220 }
221 code <<= 1;
222 si++;
223 }
224
225 /* Figure C.3: generate encoding tables */
226 /* These are code and size indexed by symbol value */
227
228 /* Set any codeless symbols to have code length 0;
229 * this allows emit_bits to detect any attempt to emit such symbols.
230 */
231 MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi));
232
233 for (p = 0; p < lastp; p++) {
234 dtbl->ehufco[htbl->huffval[p]] = huffcode[p];
235 dtbl->ehufsi[htbl->huffval[p]] = huffsize[p];
236 }
237 }
238
239
240 /* Outputting bytes to the file */
241
242 /* Emit a byte, taking 'action' if must suspend. */
243 #define emit_byte(state,val,action) \
244 { *(state)->next_output_byte++ = (JOCTET) (val); \
245 if (--(state)->free_in_buffer == 0) \
246 if (! dump_buffer(state)) \
247 { action; } }
248
249
250 LOCAL boolean
dump_buffer(working_state * state)251 dump_buffer (working_state * state)
252 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
253 {
254 struct jpeg_destination_mgr * dest = state->cinfo->dest;
255
256 if (! (*dest->empty_output_buffer) (state->cinfo))
257 return FALSE;
258 /* After a successful buffer dump, must reset buffer pointers */
259 state->next_output_byte = dest->next_output_byte;
260 state->free_in_buffer = dest->free_in_buffer;
261 return TRUE;
262 }
263
264
265 /* Outputting bits to the file */
266
267 /* Only the right 24 bits of put_buffer are used; the valid bits are
268 * left-justified in this part. At most 16 bits can be passed to emit_bits
269 * in one call, and we never retain more than 7 bits in put_buffer
270 * between calls, so 24 bits are sufficient.
271 */
272
273 INLINE
274 LOCAL boolean
emit_bits(working_state * state,unsigned int code,int size)275 emit_bits (working_state * state, unsigned int code, int size)
276 /* Emit some bits; return TRUE if successful, FALSE if must suspend */
277 {
278 /* This routine is heavily used, so it's worth coding tightly. */
279 register INT32 put_buffer = (INT32) code;
280 register int put_bits = state->cur.put_bits;
281
282 /* if size is 0, caller used an invalid Huffman table entry */
283 if (size == 0)
284 ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE);
285
286 put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
287
288 put_bits += size; /* new number of bits in buffer */
289
290 put_buffer <<= 24 - put_bits; /* align incoming bits */
291
292 put_buffer |= state->cur.put_buffer; /* and merge with old buffer contents */
293
294 while (put_bits >= 8) {
295 int c = (int) ((put_buffer >> 16) & 0xFF);
296
297 emit_byte(state, c, return FALSE);
298 if (c == 0xFF) { /* need to stuff a zero byte? */
299 emit_byte(state, 0, return FALSE);
300 }
301 put_buffer <<= 8;
302 put_bits -= 8;
303 }
304
305 state->cur.put_buffer = put_buffer; /* update state variables */
306 state->cur.put_bits = put_bits;
307
308 return TRUE;
309 }
310
311
312 LOCAL boolean
flush_bits(working_state * state)313 flush_bits (working_state * state)
314 {
315 if (! emit_bits(state, 0x7F, 7)) /* fill any partial byte with ones */
316 return FALSE;
317 state->cur.put_buffer = 0; /* and reset bit-buffer to empty */
318 state->cur.put_bits = 0;
319 return TRUE;
320 }
321
322
323 /* Encode a single block's worth of coefficients */
324
325 LOCAL boolean
encode_one_block(working_state * state,JCOEFPTR block,int last_dc_val,C_DERIVED_TBL * dctbl,C_DERIVED_TBL * actbl)326 encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val,
327 C_DERIVED_TBL *dctbl, C_DERIVED_TBL *actbl)
328 {
329 register int temp, temp2;
330 register int nbits;
331 register int k, r, i;
332
333 /* Encode the DC coefficient difference per section F.1.2.1 */
334
335 temp = temp2 = block[0] - last_dc_val;
336
337 if (temp < 0) {
338 temp = -temp; /* temp is abs value of input */
339 /* For a negative input, want temp2 = bitwise complement of abs(input) */
340 /* This code assumes we are on a two's complement machine */
341 temp2--;
342 }
343
344 /* Find the number of bits needed for the magnitude of the coefficient */
345 nbits = 0;
346 while (temp) {
347 nbits++;
348 temp >>= 1;
349 }
350
351 /* Emit the Huffman-coded symbol for the number of bits */
352 if (! emit_bits(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits]))
353 return FALSE;
354
355 /* Emit that number of bits of the value, if positive, */
356 /* or the complement of its magnitude, if negative. */
357 if (nbits) /* emit_bits rejects calls with size 0 */
358 if (! emit_bits(state, (unsigned int) temp2, nbits))
359 return FALSE;
360
361 /* Encode the AC coefficients per section F.1.2.2 */
362
363 r = 0; /* r = run length of zeros */
364
365 for (k = 1; k < DCTSIZE2; k++) {
366 if ((temp = block[k]) == 0) {
367 r++;
368 } else {
369 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
370 while (r > 15) {
371 if (! emit_bits(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0]))
372 return FALSE;
373 r -= 16;
374 }
375
376 temp2 = temp;
377 if (temp < 0) {
378 temp = -temp; /* temp is abs value of input */
379 /* This code assumes we are on a two's complement machine */
380 temp2--;
381 }
382
383 /* Find the number of bits needed for the magnitude of the coefficient */
384 nbits = 1; /* there must be at least one 1 bit */
385 while ((temp >>= 1))
386 nbits++;
387
388 /* Emit Huffman symbol for run length / number of bits */
389 i = (r << 4) + nbits;
390 if (! emit_bits(state, actbl->ehufco[i], actbl->ehufsi[i]))
391 return FALSE;
392
393 /* Emit that number of bits of the value, if positive, */
394 /* or the complement of its magnitude, if negative. */
395 if (! emit_bits(state, (unsigned int) temp2, nbits))
396 return FALSE;
397
398 r = 0;
399 }
400 }
401
402 /* If the last coef(s) were zero, emit an end-of-block code */
403 if (r > 0)
404 if (! emit_bits(state, actbl->ehufco[0], actbl->ehufsi[0]))
405 return FALSE;
406
407 return TRUE;
408 }
409
410
411 /*
412 * Emit a restart marker & resynchronize predictions.
413 */
414
415 LOCAL boolean
emit_restart(working_state * state,int restart_num)416 emit_restart (working_state * state, int restart_num)
417 {
418 int ci;
419
420 if (! flush_bits(state))
421 return FALSE;
422
423 emit_byte(state, 0xFF, return FALSE);
424 emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
425
426 /* Re-initialize DC predictions to 0 */
427 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
428 state->cur.last_dc_val[ci] = 0;
429
430 /* The restart counter is not updated until we successfully write the MCU. */
431
432 return TRUE;
433 }
434
435
436 /*
437 * Encode and output one MCU's worth of Huffman-compressed coefficients.
438 */
439
440 METHODDEF boolean
encode_mcu_huff(j_compress_ptr cinfo,JBLOCKROW * MCU_data)441 encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
442 {
443 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
444 working_state state;
445 int blkn, ci;
446 jpeg_component_info * compptr;
447
448 /* Load up working state */
449 state.next_output_byte = cinfo->dest->next_output_byte;
450 state.free_in_buffer = cinfo->dest->free_in_buffer;
451 ASSIGN_STATE(state.cur, entropy->saved);
452 state.cinfo = cinfo;
453
454 /* Emit restart marker if needed */
455 if (cinfo->restart_interval) {
456 if (entropy->restarts_to_go == 0)
457 if (! emit_restart(&state, entropy->next_restart_num))
458 return FALSE;
459 }
460
461 /* Encode the MCU data blocks */
462 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
463 ci = cinfo->MCU_membership[blkn];
464 compptr = cinfo->cur_comp_info[ci];
465 if (! encode_one_block(&state,
466 MCU_data[blkn][0], state.cur.last_dc_val[ci],
467 entropy->dc_derived_tbls[compptr->dc_tbl_no],
468 entropy->ac_derived_tbls[compptr->ac_tbl_no]))
469 return FALSE;
470 /* Update last_dc_val */
471 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
472 }
473
474 /* Completed MCU, so update state */
475 cinfo->dest->next_output_byte = state.next_output_byte;
476 cinfo->dest->free_in_buffer = state.free_in_buffer;
477 ASSIGN_STATE(entropy->saved, state.cur);
478
479 /* Update restart-interval state too */
480 if (cinfo->restart_interval) {
481 if (entropy->restarts_to_go == 0) {
482 entropy->restarts_to_go = cinfo->restart_interval;
483 entropy->next_restart_num++;
484 entropy->next_restart_num &= 7;
485 }
486 entropy->restarts_to_go--;
487 }
488
489 return TRUE;
490 }
491
492
493 /*
494 * Finish up at the end of a Huffman-compressed scan.
495 */
496
497 METHODDEF void
finish_pass_huff(j_compress_ptr cinfo)498 finish_pass_huff (j_compress_ptr cinfo)
499 {
500 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
501 working_state state;
502
503 /* Load up working state ... flush_bits needs it */
504 state.next_output_byte = cinfo->dest->next_output_byte;
505 state.free_in_buffer = cinfo->dest->free_in_buffer;
506 ASSIGN_STATE(state.cur, entropy->saved);
507 state.cinfo = cinfo;
508
509 /* Flush out the last data */
510 if (! flush_bits(&state))
511 ERREXIT(cinfo, JERR_CANT_SUSPEND);
512
513 /* Update state */
514 cinfo->dest->next_output_byte = state.next_output_byte;
515 cinfo->dest->free_in_buffer = state.free_in_buffer;
516 ASSIGN_STATE(entropy->saved, state.cur);
517 }
518
519
520 /*
521 * Huffman coding optimization.
522 *
523 * This actually is optimization, in the sense that we find the best possible
524 * Huffman table(s) for the given data. We first scan the supplied data and
525 * count the number of uses of each symbol that is to be Huffman-coded.
526 * (This process must agree with the code above.) Then we build an
527 * optimal Huffman coding tree for the observed counts.
528 *
529 * The JPEG standard requires Huffman codes to be no more than 16 bits long.
530 * If some symbols have a very small but nonzero probability, the Huffman tree
531 * must be adjusted to meet the code length restriction. We currently use
532 * the adjustment method suggested in the JPEG spec. This method is *not*
533 * optimal; it may not choose the best possible limited-length code. But
534 * since the symbols involved are infrequently used, it's not clear that
535 * going to extra trouble is worthwhile.
536 */
537
538 #ifdef ENTROPY_OPT_SUPPORTED
539
540
541 /* Process a single block's worth of coefficients */
542
543 LOCAL void
htest_one_block(JCOEFPTR block,int last_dc_val,long dc_counts[],long ac_counts[])544 htest_one_block (JCOEFPTR block, int last_dc_val,
545 long dc_counts[], long ac_counts[])
546 {
547 register int temp;
548 register int nbits;
549 register int k, r;
550
551 /* Encode the DC coefficient difference per section F.1.2.1 */
552
553 temp = block[0] - last_dc_val;
554 if (temp < 0)
555 temp = -temp;
556
557 /* Find the number of bits needed for the magnitude of the coefficient */
558 nbits = 0;
559 while (temp) {
560 nbits++;
561 temp >>= 1;
562 }
563
564 /* Count the Huffman symbol for the number of bits */
565 dc_counts[nbits]++;
566
567 /* Encode the AC coefficients per section F.1.2.2 */
568
569 r = 0; /* r = run length of zeros */
570
571 for (k = 1; k < DCTSIZE2; k++) {
572 if ((temp = block[k]) == 0) {
573 r++;
574 } else {
575 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
576 while (r > 15) {
577 ac_counts[0xF0]++;
578 r -= 16;
579 }
580
581 /* Find the number of bits needed for the magnitude of the coefficient */
582 if (temp < 0)
583 temp = -temp;
584
585 /* Find the number of bits needed for the magnitude of the coefficient */
586 nbits = 1; /* there must be at least one 1 bit */
587 while ((temp >>= 1))
588 nbits++;
589
590 /* Count Huffman symbol for run length / number of bits */
591 ac_counts[(r << 4) + nbits]++;
592
593 r = 0;
594 }
595 }
596
597 /* If the last coef(s) were zero, emit an end-of-block code */
598 if (r > 0)
599 ac_counts[0]++;
600 }
601
602
603 /*
604 * Trial-encode one MCU's worth of Huffman-compressed coefficients.
605 * No data is actually output, so no suspension return is possible.
606 */
607
608 METHODDEF boolean
encode_mcu_gather(j_compress_ptr cinfo,JBLOCKROW * MCU_data)609 encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
610 {
611 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
612 int blkn, ci;
613 jpeg_component_info * compptr;
614
615 /* Take care of restart intervals if needed */
616 if (cinfo->restart_interval) {
617 if (entropy->restarts_to_go == 0) {
618 /* Re-initialize DC predictions to 0 */
619 for (ci = 0; ci < cinfo->comps_in_scan; ci++)
620 entropy->saved.last_dc_val[ci] = 0;
621 /* Update restart state */
622 entropy->restarts_to_go = cinfo->restart_interval;
623 }
624 entropy->restarts_to_go--;
625 }
626
627 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
628 ci = cinfo->MCU_membership[blkn];
629 compptr = cinfo->cur_comp_info[ci];
630 htest_one_block(MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
631 entropy->dc_count_ptrs[compptr->dc_tbl_no],
632 entropy->ac_count_ptrs[compptr->ac_tbl_no]);
633 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
634 }
635
636 return TRUE;
637 }
638
639
640 /* Generate the optimal coding for the given counts, initialize htbl */
641
642 LOCAL void
gen_huff_coding(j_compress_ptr cinfo,JHUFF_TBL * htbl,long freq[])643 gen_huff_coding (j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[])
644 {
645 #define MAX_CLEN 32 /* assumed maximum initial code length */
646 UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */
647 int codesize[257]; /* codesize[k] = code length of symbol k */
648 int others[257]; /* next symbol in current branch of tree */
649 int c1, c2;
650 int p, i, j;
651 long v;
652
653 /* This algorithm is explained in section K.2 of the JPEG standard */
654
655 MEMZERO(bits, SIZEOF(bits));
656 MEMZERO(codesize, SIZEOF(codesize));
657 for (i = 0; i < 257; i++)
658 others[i] = -1; /* init links to empty */
659
660 freq[256] = 1; /* make sure there is a nonzero count */
661 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
662 * that no real symbol is given code-value of all ones, because 256
663 * will be placed in the largest codeword category.
664 */
665
666 /* Huffman's basic algorithm to assign optimal code lengths to symbols */
667
668 for (;;) {
669 /* Find the smallest nonzero frequency, set c1 = its symbol */
670 /* In case of ties, take the larger symbol number */
671 c1 = -1;
672 v = 1000000000L;
673 for (i = 0; i <= 256; i++) {
674 if (freq[i] && freq[i] <= v) {
675 v = freq[i];
676 c1 = i;
677 }
678 }
679
680 /* Find the next smallest nonzero frequency, set c2 = its symbol */
681 /* In case of ties, take the larger symbol number */
682 c2 = -1;
683 v = 1000000000L;
684 for (i = 0; i <= 256; i++) {
685 if (freq[i] && freq[i] <= v && i != c1) {
686 v = freq[i];
687 c2 = i;
688 }
689 }
690
691 /* Done if we've merged everything into one frequency */
692 if (c2 < 0)
693 break;
694
695 /* Else merge the two counts/trees */
696 freq[c1] += freq[c2];
697 freq[c2] = 0;
698
699 /* Increment the codesize of everything in c1's tree branch */
700 codesize[c1]++;
701 while (others[c1] >= 0) {
702 c1 = others[c1];
703 codesize[c1]++;
704 }
705
706 others[c1] = c2; /* chain c2 onto c1's tree branch */
707
708 /* Increment the codesize of everything in c2's tree branch */
709 codesize[c2]++;
710 while (others[c2] >= 0) {
711 c2 = others[c2];
712 codesize[c2]++;
713 }
714 }
715
716 /* Now count the number of symbols of each code length */
717 for (i = 0; i <= 256; i++) {
718 if (codesize[i]) {
719 /* The JPEG standard seems to think that this can't happen, */
720 /* but I'm paranoid... */
721 if (codesize[i] > MAX_CLEN)
722 ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW);
723
724 bits[codesize[i]]++;
725 }
726 }
727
728 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
729 * Huffman procedure assigned any such lengths, we must adjust the coding.
730 * Here is what the JPEG spec says about how this next bit works:
731 * Since symbols are paired for the longest Huffman code, the symbols are
732 * removed from this length category two at a time. The prefix for the pair
733 * (which is one bit shorter) is allocated to one of the pair; then,
734 * skipping the BITS entry for that prefix length, a code word from the next
735 * shortest nonzero BITS entry is converted into a prefix for two code words
736 * one bit longer.
737 */
738
739 for (i = MAX_CLEN; i > 16; i--) {
740 while (bits[i] > 0) {
741 j = i - 2; /* find length of new prefix to be used */
742 while (bits[j] == 0)
743 j--;
744
745 bits[i] -= 2; /* remove two symbols */
746 bits[i-1]++; /* one goes in this length */
747 bits[j+1] += 2; /* two new symbols in this length */
748 bits[j]--; /* symbol of this length is now a prefix */
749 }
750 }
751
752 /* Remove the count for the pseudo-symbol 256 from the largest codelength */
753 while (bits[i] == 0) /* find largest codelength still in use */
754 i--;
755 bits[i]--;
756
757 /* Return final symbol counts (only for lengths 0..16) */
758 MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits));
759
760 /* Return a list of the symbols sorted by code length */
761 /* It's not real clear to me why we don't need to consider the codelength
762 * changes made above, but the JPEG spec seems to think this works.
763 */
764 p = 0;
765 for (i = 1; i <= MAX_CLEN; i++) {
766 for (j = 0; j <= 255; j++) {
767 if (codesize[j] == i) {
768 htbl->huffval[p] = (UINT8) j;
769 p++;
770 }
771 }
772 }
773
774 /* Set sent_table FALSE so updated table will be written to JPEG file. */
775 htbl->sent_table = FALSE;
776 }
777
778
779 /*
780 * Finish up a statistics-gathering pass and create the new Huffman tables.
781 */
782
783 METHODDEF void
finish_pass_gather(j_compress_ptr cinfo)784 finish_pass_gather (j_compress_ptr cinfo)
785 {
786 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
787 int ci, dctbl, actbl;
788 jpeg_component_info * compptr;
789 JHUFF_TBL **htblptr;
790 boolean did_dc[NUM_HUFF_TBLS];
791 boolean did_ac[NUM_HUFF_TBLS];
792
793 /* It's important not to apply gen_huff_coding more than once per table,
794 * because it clobbers the input frequency counts!
795 */
796 MEMZERO(did_dc, SIZEOF(did_dc));
797 MEMZERO(did_ac, SIZEOF(did_ac));
798
799 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
800 compptr = cinfo->cur_comp_info[ci];
801 dctbl = compptr->dc_tbl_no;
802 actbl = compptr->ac_tbl_no;
803 if (! did_dc[dctbl]) {
804 htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
805 if (*htblptr == NULL)
806 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
807 gen_huff_coding(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]);
808 did_dc[dctbl] = TRUE;
809 }
810 if (! did_ac[actbl]) {
811 htblptr = & cinfo->ac_huff_tbl_ptrs[actbl];
812 if (*htblptr == NULL)
813 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
814 gen_huff_coding(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]);
815 did_ac[actbl] = TRUE;
816 }
817 }
818 }
819
820
821 #endif /* ENTROPY_OPT_SUPPORTED */
822
823
824 /*
825 * Module initialization routine for Huffman entropy encoding.
826 */
827
828 GLOBAL void
jinit_huff_encoder(j_compress_ptr cinfo)829 jinit_huff_encoder (j_compress_ptr cinfo)
830 {
831 huff_entropy_ptr entropy;
832 int i;
833
834 entropy = (huff_entropy_ptr)
835 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
836 SIZEOF(huff_entropy_encoder));
837 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
838 entropy->pub.start_pass = start_pass_huff;
839
840 /* Mark tables unallocated */
841 for (i = 0; i < NUM_HUFF_TBLS; i++) {
842 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
843 #ifdef ENTROPY_OPT_SUPPORTED
844 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;
845 #endif
846 }
847 }
848