3 { This file contains declarations for Huffman entropy decoding routines
4 that are shared between the sequential decoder (jdhuff.c) and the
5 progressive decoder (jdphuff.c). No other modules need to see these. }
7 { This file contains Huffman entropy decoding routines.
9 Much of the complexity here has to do with supporting input suspension.
10 If the data source module demands suspension, we want to be able to back
11 up to the start of the current MCU. To do this, we copy state variables
12 into local working storage, and update them back to the permanent
13 storage only upon successful completion of an MCU. }
15 { Original: jdhuff.h+jdhuff.c; Copyright (C) 1991-1997, Thomas G. Lane. }
19 interface
21 {$I imjconfig.inc}
23 uses
24 imjmorecfg,
25 imjinclude,
26 imjdeferr,
27 imjerror,
28 imjutils,
29 imjpeglib;
32 { Declarations shared with jdphuff.c }
36 { Derived data constructed for each Huffman table }
38 const
41 type
44 { Basic tables: (element [0] of each array is unused) }
46 { (maxcode[17] is a sentinel to ensure jpeg_huff_decode terminates) }
48 { valoffset[k] = huffval[] index of 1st symbol of code length k, less
49 the smallest code of length k; so given a code of length k, the
50 corresponding symbol is huffval[code + valoffset[k]] }
52 { Link to public Huffman table (needed only in jpeg_huff_decode) }
55 { Lookahead tables: indexed by the next HUFF_LOOKAHEAD bits of
56 the input data stream. If the next Huffman code is no more
57 than HUFF_LOOKAHEAD bits long, we can obtain its length and
58 the corresponding symbol directly from these tables. }
61 { # bits, or 0 if too long }
63 { symbol, or unused }
66 { Fetching the next N bits from the input stream is a time-critical operation
67 for the Huffman decoders. We implement it with a combination of inline
68 macros and out-of-line subroutines. Note that N (the number of bits
69 demanded at one time) never exceeds 15 for JPEG use.
71 We read source bytes into get_buffer and dole out bits as needed.
72 If get_buffer already contains enough bits, they are fetched in-line
73 by the macros CHECK_BIT_BUFFER and GET_BITS. When there aren't enough
74 bits, jpeg_fill_bit_buffer is called; it will attempt to fill get_buffer
75 as full as possible (not just to the number of bits needed; this
76 prefetching reduces the overhead cost of calling jpeg_fill_bit_buffer).
77 Note that jpeg_fill_bit_buffer may return FALSE to indicate suspension.
78 On TRUE return, jpeg_fill_bit_buffer guarantees that get_buffer contains
79 at least the requested number of bits --- dummy zeroes are inserted if
80 necessary. }
83 type
85 const
88 { If long is > 32 bits on your machine, and shifting/masking longs is
89 reasonably fast, making bit_buf_type be long and setting BIT_BUF_SIZE
90 appropriately should be a win. Unfortunately we can't define the size
91 with something like #define BIT_BUF_SIZE (sizeof(bit_buf_type)*8)
92 because not all machines measure sizeof in 8-bit bytes. }
94 type
100 type
102 { Bitreading working state within an MCU }
103 { current data source location }
104 { We need a copy, rather than munging the original, in case of suspension }
107 { Bit input buffer --- note these values are kept in register variables,
108 not in this struct, inside the inner loops. }
112 { Pointer needed by jpeg_fill_bit_buffer }
116 { Module initialization routine for Huffman entropy decoding. }
118 {GLOBAL}
121 {GLOBAL}
128 { Compute the derived values for a Huffman table.
129 Note this is also used by jdphuff.c. }
131 {GLOBAL}
137 { Load up the bit buffer to a depth of at least nbits }
144 implementation
146 {$IFDEF MACRO}
148 { Macros to declare and load/save bitread local variables. }
149 {$define BITREAD_STATE_VARS}
154 {$define BITREAD_LOAD_STATE(cinfop,permstate)}
161 {$define BITREAD_SAVE_STATE(cinfop,permstate) }
168 { These macros provide the in-line portion of bit fetching.
169 Use CHECK_BIT_BUFFER to ensure there are N bits in get_buffer
170 before using GET_BITS, PEEK_BITS, or DROP_BITS.
171 The variables get_buffer and bits_left are assumed to be locals,
172 but the state struct might not be (jpeg_huff_decode needs this).
173 CHECK_BIT_BUFFER(state,n,action);
174 Ensure there are N bits in get_buffer; if suspend, take action.
175 val = GET_BITS(n);
176 Fetch next N bits.
177 val = PEEK_BITS(n);
178 Fetch next N bits without removing them from the buffer.
179 DROP_BITS(n);
180 Discard next N bits.
181 The value N should be a simple variable, not an expression, because it
182 is evaluated multiple times. }
185 {$define CHECK_BIT_BUFFER(state,nbits,action)}
187 begin
189 begin
190 action;
191 exit;
198 {$define GET_BITS(nbits)}
202 {$define PEEK_BITS(nbits)}
205 {$define DROP_BITS(nbits)}
211 { Code for extracting next Huffman-coded symbol from input bit stream.
212 Again, this is time-critical and we make the main paths be macros.
214 We use a lookahead table to process codes of up to HUFF_LOOKAHEAD bits
215 without looping. Usually, more than 95% of the Huffman codes will be 8
216 or fewer bits long. The few overlength codes are handled with a loop,
217 which need not be inline code.
219 Notes about the HUFF_DECODE macro:
220 1. Near the end of the data segment, we may fail to get enough bits
221 for a lookahead. In that case, we do it the hard way.
222 2. If the lookahead table contains no entry, the next code must be
223 more than HUFF_LOOKAHEAD bits long.
224 3. jpeg_huff_decode returns -1 if forced to suspend. }
231 var
233 begin
235 begin
237 begin
239 exit;
244 begin
249 {look := PEEK_BITS(HUFF_LOOKAHEAD);}
255 begin
256 {DROP_BITS(nb);}
260 end
261 else
262 begin
264 slowlabel:
267 begin
269 exit;
279 { Expanded entropy decoder object for Huffman decoding.
281 The savable_state subrecord contains fields that change within an MCU,
282 but must not be updated permanently until we complete the MCU. }
284 type
290 type
295 { These fields are loaded into local variables at start of each MCU.
296 In case of suspension, we exit WITHOUT updating them. }
301 { These fields are NOT loaded into local working state. }
304 { Pointers to derived tables (these workspaces have image lifespan) }
308 { Precalculated info set up by start_pass for use in decode_mcu: }
310 { Pointers to derived tables to be used for each block within an MCU }
313 { Whether we care about the DC and AC coefficient values for each block }
320 { Initialize for a Huffman-compressed scan. }
322 {METHODDEF}
324 var
328 begin
331 { Check that the scan parameters Ss, Se, Ah/Al are OK for sequential JPEG.
332 This ought to be an error condition, but we make it a warning because
333 there are some baseline files out there with all zeroes in these bytes. }
340 begin
344 { Compute derived values for Huffman tables }
345 { We may do this more than once for a table, but it's not expensive }
350 { Initialize DC predictions to 0 }
354 { Precalculate decoding info for each block in an MCU of this scan }
356 begin
359 { Precalculate which table to use for each block }
362 { Decide whether we really care about the coefficient values }
364 begin
366 { we don't need the ACs if producing a 1/8th-size image }
368 end
369 else
370 begin
376 { Initialize bitread state variables }
381 { Initialize restart counter }
386 { Compute the derived values for a Huffman table.
387 This routine also performs some validation checks on the table.
389 Note this is also used by jdphuff.c. }
391 {GLOBAL}
396 var
404 var
406 begin
407 { Note that huffsize[] and huffcode[] are filled in code-length order,
408 paralleling the order of the symbols themselves in htbl^.huffval[]. }
410 { Find the input Huffman table }
415 else
420 { Allocate a workspace if we haven't already done so. }
428 { Figure C.1: make table of Huffman code length for each symbol }
432 begin
437 begin
446 { Figure C.2: generate the codes themselves }
447 { We also validate that the counts represent a legal Huffman code tree. }
453 begin
455 begin
460 { code is now 1 more than the last code used for codelength si; but
461 it must still fit in si bits, since no code is allowed to be all ones. }
470 { Figure F.15: generate decoding tables for bit-sequential decoding }
474 begin
476 begin
477 { valoffset[l] = huffval[] index of 1st symbol of code length l,
478 minus the minimum code of length l }
483 end
484 else
485 begin
491 { Compute lookahead tables to speed up decoding.
492 First we set all the table entries to 0, indicating "too long";
493 then we iterate through the Huffman codes that are short enough and
494 fill in all the entries that correspond to bit sequences starting
495 with that code. }
501 begin
503 begin
504 { l := current code's length, p := its index in huffcode[] & huffval[]. }
505 { Generate left-justified code followed by all possible bit sequences }
508 begin
517 { Validate symbols as being reasonable.
518 For AC tables, we make no check, but accept all byte values 0..255.
519 For DC tables, we require the symbols to be in range 0..15.
520 (Tighter bounds could be applied depending on the data depth and mode,
521 but this is sufficient to ensure safe decoding.) }
524 begin
526 begin
535 { Out-of-line code for bit fetching (shared with jdphuff.c).
536 See jdhuff.h for info about usage.
537 Note: current values of get_buffer and bits_left are passed as parameters,
538 but are returned in the corresponding fields of the state struct.
540 On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
541 of get_buffer to be used. (On machines with wider words, an even larger
542 buffer could be used.) However, on some machines 32-bit shifts are
543 quite slow and take time proportional to the number of places shifted.
544 (This is true with most PC compilers, for instance.) In this case it may
545 be a win to set MIN_GET_BITS to the minimum value of 15. This reduces the
546 average shift distance at the cost of more calls to jpeg_fill_bit_buffer. }
548 {$ifdef SLOW_SHIFT_32}
549 const
551 {$else}
552 const
554 {$endif}
557 {GLOBAL}
562 label
563 no_more_bytes;
564 { Load up the bit buffer to a depth of at least nbits }
565 var
566 { Copy heavily used state fields into locals (hopefully registers) }
569 var
571 var
573 begin
578 { Attempt to load at least MIN_GET_BITS bits into get_buffer. }
579 { (It is assumed that no request will be for more than that many bits.) }
580 { We fail to do so only if we hit a marker or are forced to suspend. }
583 begin
585 begin
586 { Attempt to read a byte }
588 begin
590 begin
592 exit;
602 { If it's $FF, check and discard stuffed zero byte }
604 begin
605 { Loop here to discard any padding FF's on terminating marker,
606 so that we can save a valid unread_marker value. NOTE: we will
607 accept multiple FF's followed by a 0 as meaning a single FF data
608 byte. This data pattern is not valid according to the standard. }
610 repeat
612 begin
614 begin
616 exit;
627 begin
628 { Found FF/00, which represents an FF data byte }
630 end
631 else
632 begin
633 { Oops, it's actually a marker indicating end of compressed data.
634 Save the marker code for later use.
635 Fine point: it might appear that we should save the marker into
636 bitread working state, not straight into permanent state. But
637 once we have hit a marker, we cannot need to suspend within the
638 current MCU, because we will read no more bytes from the data
639 source. So it is OK to update permanent state right away. }
642 { See if we need to insert some fake zero bits. }
647 { OK, load c into get_buffer }
651 end
652 else
653 begin
654 no_more_bytes:
655 { We get here if we've read the marker that terminates the compressed
656 data segment. There should be enough bits in the buffer register
657 to satisfy the request; if so, no problem. }
660 begin
661 { Uh-oh. Report corrupted data to user and stuff zeroes into
662 the data stream, so that we can produce some kind of image.
663 We use a nonvolatile flag to ensure that only one warning message
664 appears per data segment. }
667 begin
671 { Fill the buffer with zero bits }
677 { Unload the local registers }
687 { Out-of-line code for Huffman code decoding.
688 See jdhuff.h for info about usage. }
690 {GLOBAL}
696 var
699 begin
702 { HUFF_DECODE has determined that the code is at least min_bits }
703 { bits long, so fetch that many bits in one swoop. }
705 {CHECK_BIT_BUFFER(state, l, return -1);}
707 begin
709 begin
711 exit;
717 {code := GET_BITS(l);}
721 { Collect the rest of the Huffman code one bit at a time. }
722 { This is per Figure F.16 in the JPEG spec. }
725 begin
727 {CHECK_BIT_BUFFER(state, 1, return -1);}
729 begin
731 begin
733 exit;
739 {code := code or GET_BITS(1);}
746 { Unload the local registers }
750 { With garbage input we may reach the sentinel value l := 17. }
753 begin
756 exit;
763 { Figure F.12: extend sign bit.
764 On some machines, a shift and add will be faster than a table lookup. }
766 {$ifdef AVOID_TABLES}
770 {$else}
772 {$define HUFF_EXTEND(x,s)
773 if (x < extend_test[s]) then
774 := x + extend_offset[s]
775 else
776 x;}
778 const
783 const
793 { Check for a restart marker & resynchronize decoder.
794 Returns FALSE if must suspend. }
796 {LOCAL}
798 var
801 begin
804 { Throw away any unused bits remaining in bit buffer; }
805 { include any full bytes in next_marker's count of discarded bytes }
809 { Advance past the RSTn marker }
811 begin
813 exit;
816 { Re-initialize DC predictions to 0 }
820 { Reset restart counter }
823 { Reset out-of-data flag, unless read_restart_marker left us smack up
824 against a marker. In that case we will end up treating the next data
825 segment as empty, and we can avoid producing bogus output pixels by
826 leaving the flag set. }
835 { Decode and return one MCU's worth of Huffman-compressed coefficients.
836 The coefficients are reordered from zigzag order into natural array order,
837 but are not dequantized.
839 The i'th block of the MCU is stored into the block pointed to by
840 MCU_data[i]. WE ASSUME THIS AREA HAS BEEN ZEROED BY THE CALLER.
841 (Wholesale zeroing is usually a little faster than retail...)
843 Returns FALSE if data source requested suspension. In that case no
844 changes have been made to permanent state. (Exception: some output
845 coefficients may already have been assigned. This is harmless for
846 this module, since we'll just re-assign them on the next call.) }
848 {METHODDEF}
851 label
853 var
858 {BITREAD_STATE_VARS}
866 var
868 begin
871 { Process restart marker if needed; may have to suspend }
873 begin
876 begin
878 exit;
882 { If we've run out of data, just leave the MCU set to zeroes.
883 This way, we return uniform gray for the remainder of the segment. }
886 begin
888 { Load up working state }
889 {BITREAD_LOAD_STATE(cinfo,entropy^.bitstate);}
896 {ASSIGN_STATE(state, entropy^.saved);}
899 { Outer loop handles each block in the MCU }
902 begin
907 { Decode a single block's worth of coefficients }
909 { Section F.2.2.1: decode the DC coefficient difference }
910 {HUFF_DECODE(s, br_state, dctbl, return FALSE, label1);}
912 begin
914 begin
916 exit;
921 begin
926 {look := PEEK_BITS(HUFF_LOOKAHEAD);}
932 begin
933 {DROP_BITS(nb);}
937 end
938 else
939 begin
941 label1:
944 begin
946 exit;
953 begin
954 {CHECK_BIT_BUFFER(br_state, s, return FALSE);}
956 begin
958 begin
960 exit;
966 {r := GET_BITS(s);}
970 {s := HUFF_EXTEND(r, s);}
973 else
978 begin
979 { Convert DC difference to actual value, update last_dc_val }
983 { Output the DC coefficient (assumes jpeg_natural_order[0] := 0) }
988 begin
990 { Section F.2.2.2: decode the AC coefficients }
991 { Since zeroes are skipped, output area must be cleared beforehand }
994 begin
995 {HUFF_DECODE(s, br_state, actbl, return FALSE, label2);}
997 begin
999 begin
1001 exit;
1006 begin
1011 {look := PEEK_BITS(HUFF_LOOKAHEAD);}
1017 begin
1018 {DROP_BITS(nb);}
1022 end
1023 else
1024 begin
1026 label2:
1029 begin
1031 exit;
1041 begin
1043 {CHECK_BIT_BUFFER(br_state, s, return FALSE);}
1045 begin
1047 begin
1049 exit;
1055 {r := GET_BITS(s);}
1059 {s := HUFF_EXTEND(r, s);}
1062 else
1064 { Output coefficient in natural (dezigzagged) order.
1065 Note: the extra entries in jpeg_natural_order[] will save us
1066 if k >= DCTSIZE2, which could happen if the data is corrupted. }
1069 end
1070 else
1071 begin
1073 break;
1078 end
1079 else
1080 begin
1082 { Section F.2.2.2: decode the AC coefficients }
1083 { In this path we just discard the values }
1086 begin
1087 {HUFF_DECODE(s, br_state, actbl, return FALSE, label3);}
1089 begin
1091 begin
1093 exit;
1098 begin
1103 {look := PEEK_BITS(HUFF_LOOKAHEAD);}
1109 begin
1110 {DROP_BITS(nb);}
1114 end
1115 else
1116 begin
1118 label3:
1121 begin
1123 exit;
1133 begin
1135 {CHECK_BIT_BUFFER(br_state, s, return FALSE);}
1137 begin
1139 begin
1141 exit;
1147 {DROP_BITS(s);}
1149 end
1150 else
1151 begin
1153 break;
1162 { Completed MCU, so update state }
1163 {BITREAD_SAVE_STATE(cinfo,entropy^.bitstate);}
1169 {ASSIGN_STATE(entropy^.saved, state);}
1174 { Account for restart interval (no-op if not using restarts) }
1181 { Module initialization routine for Huffman entropy decoding. }
1183 {GLOBAL}
1185 var
1188 begin
1196 { Mark tables unallocated }
1198 begin