0N/A * reserved comment block 0N/A * DO NOT REMOVE OR ALTER! 0N/A * Copyright (C) 1991-1997, Thomas G. Lane. 0N/A * This file is part of the Independent JPEG Group's software. 0N/A * For conditions of distribution and use, see the accompanying README file. 0N/A * This file contains Huffman entropy encoding routines. 0N/A * Much of the complexity here has to do with supporting output suspension. 0N/A * If the data destination module demands suspension, we want to be able to 0N/A * back up to the start of the current MCU. To do this, we copy state 0N/A * variables into local working storage, and update them back to the 0N/A * permanent JPEG objects only upon successful completion of an MCU. 0N/A/* Expanded entropy encoder object for Huffman encoding. 0N/A * The savable_state subrecord contains fields that change within an MCU, 0N/A * but must not be updated permanently until we complete the MCU. 0N/A/* This macro is to work around compilers with missing or broken 0N/A * structure assignment. You'll need to fix this code if you have 0N/A * such a compiler and you change MAX_COMPS_IN_SCAN. 0N/A /* These fields are NOT loaded into local working state. */ 0N/A /* Pointers to derived tables (these workspaces have image lifespan) */ 0N/A/* Working state while writing an MCU. 0N/A * This struct contains all the fields that are needed by subroutines. 0N/A/* Forward declarations */ 0N/A * Initialize for a Huffman-compressed scan. 0N/A * If gather_statistics is TRUE, we do not output anything during the scan, 0N/A * just count the Huffman symbols used and generate Huffman code tables. 0N/A /* Check for invalid table indexes */ 0N/A /* (make_c_derived_tbl does this in the other path) */ 0N/A /* Allocate and zero the statistics tables */ 0N/A /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ 0N/A /* Compute derived values for Huffman tables */ 0N/A /* We may do this more than once for a table, but it's not expensive */ 0N/A /* Initialize DC predictions to 0 */ 0N/A /* Initialize bit buffer to empty */ 0N/A /* Initialize restart stuff */ 0N/A * Compute the derived values for a Huffman table. 0N/A * This routine also performs some validation checks on the table. 0N/A /* Note that huffsize[] and huffcode[] are filled in code-length order, 0N/A * paralleling the order of the symbols themselves in htbl->huffval[]. 0N/A /* Find the input Huffman table */ 0N/A /* Allocate a workspace if we haven't already done so. */ 0N/A /* Figure C.1: make table of Huffman code length for each symbol */ 0N/A for (l =
1; l <=
16; l++) {
0N/A if (i < 0 || p + i >
256)
/* protect against table overrun */ 0N/A /* Figure C.2: generate the codes themselves */ 0N/A /* We also validate that the counts represent a legal Huffman code tree. */ 0N/A /* code is now 1 more than the last code used for codelength si; but 0N/A * it must still fit in si bits, since no code is allowed to be all ones. 0N/A /* Figure C.3: generate encoding tables */ 0N/A /* These are code and size indexed by symbol value */ 0N/A /* Set all codeless symbols to have code length 0; 0N/A * this lets us detect duplicate VAL entries here, and later 0N/A * allows emit_bits to detect any attempt to emit such symbols. 0N/A /* This is also a convenient place to check for out-of-range 0N/A * and duplicated VAL entries. We allow 0..255 for AC symbols 0N/A * but only 0..15 for DC. (We could constrain them further 0N/A * based on data depth and mode, but this seems enough.) 0N/A/* Outputting bytes to the file */ 0N/A/* Emit a byte, taking 'action' if must suspend. */ 0N/A/* Empty the output buffer; return TRUE if successful, FALSE if must suspend */ 0N/A /* After a successful buffer dump, must reset buffer pointers */ 0N/A/* Outputting bits to the file */ 0N/A/* Only the right 24 bits of put_buffer are used; the valid bits are 0N/A * left-justified in this part. At most 16 bits can be passed to emit_bits 0N/A * in one call, and we never retain more than 7 bits in put_buffer 0N/A * between calls, so 24 bits are sufficient. 0N/A/* Emit some bits; return TRUE if successful, FALSE if must suspend */ 0N/A /* This routine is heavily used, so it's worth coding tightly. */ 0N/A /* if size is 0, caller used an invalid Huffman table entry */ 0N/A if (c ==
0xFF) {
/* need to stuff a zero byte? */ 0N/A/* Encode a single block's worth of coefficients */ 0N/A register int k, r, i;
0N/A /* Encode the DC coefficient difference per section F.1.2.1 */ 0N/A /* For a negative input, want temp2 = bitwise complement of abs(input) */ 0N/A /* This code assumes we are on a two's complement machine */ 0N/A /* Find the number of bits needed for the magnitude of the coefficient */ 0N/A /* Check for out-of-range coefficient values. 0N/A * Since we're encoding a difference, the range limit is twice as much. 0N/A /* Emit the Huffman-coded symbol for the number of bits */ 0N/A /* Emit that number of bits of the value, if positive, */ 0N/A /* or the complement of its magnitude, if negative. */ 0N/A if (
nbits)
/* emit_bits rejects calls with size 0 */ 0N/A /* Encode the AC coefficients per section F.1.2.2 */ 0N/A r = 0;
/* r = run length of zeros */ 0N/A /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 0N/A /* This code assumes we are on a two's complement machine */ 0N/A /* Find the number of bits needed for the magnitude of the coefficient */ 0N/A nbits =
1;
/* there must be at least one 1 bit */ 0N/A /* Check for out-of-range coefficient values */ 0N/A /* Emit Huffman symbol for run length / number of bits */ 0N/A /* Emit that number of bits of the value, if positive, */ 0N/A /* or the complement of its magnitude, if negative. */ 0N/A /* If the last coef(s) were zero, emit an end-of-block code */ 0N/A * Emit a restart marker & resynchronize predictions. 0N/A /* Re-initialize DC predictions to 0 */ 0N/A /* The restart counter is not updated until we successfully write the MCU. */ 0N/A * Encode and output one MCU's worth of Huffman-compressed coefficients. 0N/A /* Load up working state */ 0N/A /* Emit restart marker if needed */ 0N/A /* Encode the MCU data blocks */ 0N/A /* Update last_dc_val */ 0N/A /* Completed MCU, so update state */ 0N/A /* Update restart-interval state too */ 0N/A * Finish up at the end of a Huffman-compressed scan. 0N/A /* Load up working state ... flush_bits needs it */ 0N/A /* Flush out the last data */ 0N/A * Huffman coding optimization. 0N/A * We first scan the supplied data and count the number of uses of each symbol 0N/A * that is to be Huffman-coded. (This process MUST agree with the code above.) 0N/A * Then we build a Huffman coding tree for the observed counts. 0N/A * Symbols which are not needed at all for the particular image are not 0N/A * assigned any code, which saves space in the DHT marker as well as in 0N/A * the compressed data. 0N/A/* Process a single block's worth of coefficients */ 0N/A /* Encode the DC coefficient difference per section F.1.2.1 */ 0N/A /* Find the number of bits needed for the magnitude of the coefficient */ 0N/A /* Check for out-of-range coefficient values. 0N/A * Since we're encoding a difference, the range limit is twice as much. 0N/A /* Count the Huffman symbol for the number of bits */ 0N/A /* Encode the AC coefficients per section F.1.2.2 */ 0N/A r = 0;
/* r = run length of zeros */ 0N/A /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 0N/A /* Find the number of bits needed for the magnitude of the coefficient */ 0N/A /* Find the number of bits needed for the magnitude of the coefficient */ 0N/A nbits =
1;
/* there must be at least one 1 bit */ 0N/A /* Check for out-of-range coefficient values */ 0N/A /* Count Huffman symbol for run length / number of bits */ 0N/A /* If the last coef(s) were zero, emit an end-of-block code */ 0N/A * Trial-encode one MCU's worth of Huffman-compressed coefficients. 0N/A * No data is actually output, so no suspension return is possible. 0N/A /* Take care of restart intervals if needed */ 0N/A /* Re-initialize DC predictions to 0 */ 0N/A /* Update restart state */ 0N/A * Generate the best Huffman code table for the given counts, fill htbl. 0N/A * The JPEG standard requires that no symbol be assigned a codeword of all 0N/A * one bits (so that padding bits added at the end of a compressed segment 0N/A * can't look like a valid code). Because of the canonical ordering of 0N/A * codewords, this just means that there must be an unused slot in the 0N/A * longest codeword length category. Section K.2 of the JPEG spec suggests 0N/A * reserving such a slot by pretending that symbol 256 is a valid symbol 0N/A * with count 1. In theory that's not optimal; giving it count zero but 0N/A * including it in the symbol set anyway should give a better Huffman code. 0N/A * But the theoretically better code actually seems to come out worse in 0N/A * practice, because it produces more all-ones bytes (which incur stuffed 0N/A * zero bytes in the final file). In any case the difference is tiny. 0N/A * The JPEG standard requires Huffman codes to be no more than 16 bits long. 0N/A * If some symbols have a very small but nonzero probability, the Huffman tree 0N/A * must be adjusted to meet the code length restriction. We currently use 0N/A * the adjustment method suggested in JPEG section K.2. This method is *not* 0N/A * optimal; it may not choose the best possible limited-length code. But 0N/A * typically only very-low-frequency symbols will be given less-than-optimal 0N/A * lengths, so the code is almost optimal. Experimental comparisons against 0N/A * an optimal limited-length-code algorithm indicate that the difference is 0N/A * microscopic --- usually less than a hundredth of a percent of total size. 0N/A * So the extra complexity of an optimal algorithm doesn't seem worthwhile. 0N/A#
define MAX_CLEN 32 /* assumed maximum initial code length */ 0N/A int codesize[
257];
/* codesize[k] = code length of symbol k */ 0N/A int others[
257];
/* next symbol in current branch of tree */ 0N/A /* This algorithm is explained in section K.2 of the JPEG standard */ 0N/A for (i = 0; i <
257; i++)
0N/A freq[
256] =
1;
/* make sure 256 has a nonzero count */ 0N/A /* Including the pseudo-symbol 256 in the Huffman procedure guarantees 0N/A * that no real symbol is given code-value of all ones, because 256 0N/A * will be placed last in the largest codeword category. 0N/A /* Huffman's basic algorithm to assign optimal code lengths to symbols */ 0N/A /* Find the smallest nonzero frequency, set c1 = its symbol */ 0N/A /* In case of ties, take the larger symbol number */ 0N/A for (i = 0; i <=
256; i++) {
0N/A /* Find the next smallest nonzero frequency, set c2 = its symbol */ 0N/A /* In case of ties, take the larger symbol number */ 0N/A for (i = 0; i <=
256; i++) {
0N/A /* Done if we've merged everything into one frequency */ 0N/A /* Increment the codesize of everything in c1's tree branch */ 0N/A /* Increment the codesize of everything in c2's tree branch */ 0N/A /* Now count the number of symbols of each code length */ 0N/A for (i = 0; i <=
256; i++) {
0N/A /* The JPEG standard seems to think that this can't happen, */ 0N/A /* but I'm paranoid... */ 0N/A /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure 0N/A * Huffman procedure assigned any such lengths, we must adjust the coding. 0N/A * Here is what the JPEG spec says about how this next bit works: 0N/A * Since symbols are paired for the longest Huffman code, the symbols are 0N/A * removed from this length category two at a time. The prefix for the pair 0N/A * (which is one bit shorter) is allocated to one of the pair; then, 0N/A * skipping the BITS entry for that prefix length, a code word from the next 0N/A * shortest nonzero BITS entry is converted into a prefix for two code words 0N/A j = i -
2;
/* find length of new prefix to be used */ 0N/A bits[i] -=
2;
/* remove two symbols */ 0N/A bits[i-
1]++;
/* one goes in this length */ 0N/A bits[j+
1] +=
2;
/* two new symbols in this length */ 0N/A bits[j]--;
/* symbol of this length is now a prefix */ 0N/A /* Remove the count for the pseudo-symbol 256 from the largest codelength */ 0N/A while (
bits[i] == 0)
/* find largest codelength still in use */ 0N/A /* Return final symbol counts (only for lengths 0..16) */ 0N/A /* Return a list of the symbols sorted by code length */ 0N/A /* It's not real clear to me why we don't need to consider the codelength 0N/A * changes made above, but the JPEG spec seems to think this works. 0N/A for (j = 0; j <=
255; j++) {
0N/A /* Set sent_table FALSE so updated table will be written to JPEG file. */ 0N/A * Finish up a statistics-gathering pass and create the new Huffman tables. 0N/A /* It's important not to apply jpeg_gen_optimal_table more than once 0N/A * per table, because it clobbers the input frequency counts! 0N/A#
endif /* ENTROPY_OPT_SUPPORTED */ 0N/A * Module initialization routine for Huffman entropy encoding. 0N/A /* Mark tables unallocated */