3 { This file contains Huffman entropy encoding routines for progressive JPEG.
5 We do not support output suspension in this module, since the library
6 currently does not allow multiple-scan files to be written with output
7 suspension. }
9 { Original: jcphuff.c; Copyright (C) 1995-1997, Thomas G. Lane. }
11 interface
13 {$I imjconfig.inc}
15 uses
16 imjmorecfg,
17 imjinclude,
18 imjpeglib,
19 imjdeferr,
20 imjerror,
21 imjutils,
22 imjcomapi,
25 { Module initialization routine for progressive Huffman entropy encoding. }
27 {GLOBAL}
30 implementation
32 { Expanded entropy encoder object for progressive Huffman encoding. }
33 type
38 { Mode flag: TRUE for optimization, FALSE for actual data output }
41 { Bit-level coding status.
42 next_output_byte/free_in_buffer are local copies of cinfo^.dest fields.}
50 { Coding status for DC components }
52 { last DC coef for each component }
54 { Coding status for AC components }
59 { packing correction bits tightly would save some space but cost time... }
64 { Pointers to derived tables (these workspaces have image lifespan).
65 Since any one scan codes only DC or only AC, we only need one set
66 of tables, not one for DC and one for AC. }
70 { Statistics tables for optimization; again, one set is enough }
75 { MAX_CORR_BITS is the number of bits the AC refinement correction-bit
76 buffer can hold. Larger sizes may slightly improve compression, but
77 1000 is already well into the realm of overkill.
78 The minimum safe size is 64 bits. }
80 const
84 { Forward declarations }
85 {METHODDEF}
89 {METHODDEF}
93 {METHODDEF}
97 {METHODDEF}
102 {METHODDEF}
105 {METHODDEF}
109 { Initialize for a Huffman-compressed scan using progressive JPEG. }
111 {METHODDEF}
114 var
119 begin
128 { We assume jcmaster.c already validated the scan parameters. }
130 { Select execution routines }
132 begin
135 else
137 end
138 else
139 begin
142 else
143 begin
145 { AC refinement needs a correction bit buffer }
154 else
157 { Only DC coefficients may be interleaved, so cinfo^.comps_in_scan = 1
158 for AC coefficients. }
161 begin
163 { Initialize DC predictions to 0 }
165 { Get table index }
167 begin
169 continue;
171 end
172 else
173 begin
178 begin
179 { Check for invalid table index }
180 { (make_c_derived_tbl does this in the other path) }
183 { Allocate and zero the statistics tables }
184 { Note that jpeg_gen_optimal_table expects 257 entries in each table! }
190 end else
191 begin
192 { Compute derived values for Huffman table }
193 { We may do this more than once for a table, but it's not expensive }
199 { Initialize AC stuff }
203 { Initialize bit buffer to empty }
207 { Initialize restart stuff }
215 {LOCAL}
217 { Empty the output buffer; we do not support suspension in this module. }
218 var
220 begin
225 { After a successful buffer dump, must reset buffer pointers }
231 { Outputting bits to the file }
233 { Only the right 24 bits of put_buffer are used; the valid bits are
234 left-justified in this part. At most 16 bits can be passed to emit_bits
235 in one call, and we never retain more than 7 bits in put_buffer
236 between calls, so 24 bits are sufficient. }
239 {LOCAL}
243 { Emit some bits, unless we are in gather mode }
244 var
247 var
249 begin
250 { This routine is heavily used, so it's worth coding tightly. }
254 { if size is 0, caller used an invalid Huffman table entry }
262 { mask off any extra bits in code }
269 { and merge with old buffer contents }
272 begin
275 {emit_byte(entropy, c);}
276 { Outputting bytes to the file.
277 NB: these must be called only when actually outputting,
278 that is, entropy^.gather_statistics = FALSE. }
279 { Emit a byte }
288 {emit_byte(entropy, 0);}
304 {LOCAL}
306 begin
312 { Emit (or just count) a Huffman symbol. }
315 {LOCAL}
319 var
321 begin
324 else
325 begin
332 { Emit bits from a correction bit buffer. }
334 {LOCAL}
338 var
340 begin
346 begin
354 { Emit any pending EOBRUN symbol. }
356 {LOCAL}
358 var
360 begin
367 begin
372 { safety check: shouldn't happen given limited correction-bit buffer }
382 { Emit any buffered correction bits }
389 { Emit a restart marker & resynchronize predictions. }
391 {LOCAL}
394 var
396 begin
400 begin
402 {emit_byte(entropy, $FF);}
403 { Outputting bytes to the file.
404 NB: these must be called only when actually outputting,
405 that is, entropy^.gather_statistics = FALSE. }
413 {emit_byte(entropy, JPEG_RST0 + restart_num);}
422 begin
423 { Re-initialize DC predictions to 0 }
426 end
427 else
428 begin
429 { Re-initialize all AC-related fields to 0 }
436 { MCU encoding for DC initial scan (either spectral selection,
437 or first pass of successive approximation). }
439 {METHODDEF}
442 var
451 begin
458 { Emit restart marker if needed }
463 { Encode the MCU data blocks }
465 begin
470 { Compute the DC value after the required point transform by Al.
471 This is simply an arithmetic right shift. }
473 {temp2 := IRIGHT_SHIFT( int(block^[0]), Al);}
474 {IRIGHT_SHIFT_IS_UNSIGNED}
478 else
482 { DC differences are figured on the point-transformed values. }
486 { Encode the DC coefficient difference per section G.1.2.1 }
489 begin
491 { For a negative input, want temp2 := bitwise complement of abs(input) }
492 { This code assumes we are on a two's complement machine }
496 { Find the number of bits needed for the magnitude of the coefficient }
499 begin
504 { Check for out-of-range coefficient values.
505 Since we're encoding a difference, the range limit is twice as much. }
510 { Count/emit the Huffman-coded symbol for the number of bits }
513 { Emit that number of bits of the value, if positive, }
514 { or the complement of its magnitude, if negative. }
522 { Update restart-interval state too }
524 begin
526 begin
539 { MCU encoding for AC initial scan (either spectral selection,
540 or first pass of successive approximation). }
542 {METHODDEF}
545 var
553 begin
561 { Emit restart marker if needed }
566 { Encode the MCU data block }
569 { Encode the AC coefficients per section G.1.2.2, fig. G.3 }
574 begin
577 begin
579 continue;
581 { We must apply the point transform by Al. For AC coefficients this
582 is an integer division with rounding towards 0. To do this portably
583 in C, we shift after obtaining the absolute value; so the code is
584 interwoven with finding the abs value (temp) and output bits (temp2). }
587 begin
590 { For a negative coef, want temp2 := bitwise complement of abs(coef) }
592 end
593 else
594 begin
598 { Watch out for case that nonzero coef is zero after point transform }
600 begin
602 continue;
605 { Emit any pending EOBRUN }
608 { if run length > 15, must emit special run-length-16 codes ($F0) }
610 begin
615 { Find the number of bits needed for the magnitude of the coefficient }
617 repeat
622 { Check for out-of-range coefficient values }
626 { Count/emit Huffman symbol for run length / number of bits }
629 { Emit that number of bits of the value, if positive, }
630 { or the complement of its magnitude, if negative. }
646 { Update restart-interval state too }
648 begin
650 begin
663 { MCU encoding for DC successive approximation refinement scan.
664 Note: we assume such scans can be multi-component, although the spec
665 is not very clear on the point. }
667 {METHODDEF}
670 var
676 begin
683 { Emit restart marker if needed }
688 { Encode the MCU data blocks }
690 begin
693 { We simply emit the Al'th bit of the DC coefficient value. }
701 { Update restart-interval state too }
703 begin
705 begin
718 { MCU encoding for AC successive approximation refinement scan. }
720 {METHODDEF}
724 var
735 begin
743 { Emit restart marker if needed }
748 { Encode the MCU data block }
751 { It is convenient to make a pre-pass to determine the transformed
752 coefficients' absolute values and the EOB position. }
756 begin
758 { We must apply the point transform by Al. For AC coefficients this
759 is an integer division with rounding towards 0. To do this portably
760 in C, we shift after obtaining the absolute value. }
770 { Encode the AC coefficients per section G.1.2.3, fig. G.7 }
775 { Append bits to buffer }
778 begin
781 begin
783 continue;
786 { Emit any required ZRLs, but not if they can be folded into EOB }
788 begin
789 { emit any pending EOBRUN and the BE correction bits }
791 { Emit ZRL }
794 { Emit buffered correction bits that must be associated with ZRL }
800 { If the coef was previously nonzero, it only needs a correction bit.
801 NOTE: a straight translation of the spec's figure G.7 would suggest
802 that we also need to test r > 15. But if r > 15, we can only get here
803 if k > EOB, which implies that this coefficient is not 1. }
805 begin
806 { The correction bit is the next bit of the absolute value. }
809 continue;
812 { Emit any pending EOBRUN and the BE correction bits }
815 { Count/emit Huffman symbol for run length / number of bits }
818 { Emit output bit for newly-nonzero coef }
821 else
825 { Emit buffered correction bits that must be associated with this code }
836 { We force out the EOB if we risk either:
837 1. overflow of the EOB counter;
838 2. overflow of the correction bit buffer during the next MCU. }
848 { Update restart-interval state too }
850 begin
852 begin
865 { Finish up at the end of a Huffman-compressed progressive scan. }
867 {METHODDEF}
869 var
871 begin
877 { Flush out any buffered data }
886 { Finish up a statistics-gathering pass and create the new Huffman tables. }
888 {METHODDEF}
890 var
897 begin
901 { Flush out buffered data (all we care about is counting the EOB symbol) }
906 { It's important not to apply jpeg_gen_optimal_table more than once
907 per table, because it clobbers the input frequency counts! }
912 begin
915 begin
917 continue;
919 end
920 else
921 begin
925 begin
928 else
939 { Module initialization routine for progressive Huffman entropy encoding. }
941 {GLOBAL}
943 var
946 begin
953 { Mark tables unallocated }
955 begin