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