Main Page | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Data Fields | Globals

jchuff.c File Reference

#include "jinclude.h"
#include "jpeglib.h"
#include "jchuff.h"

Include dependency graph for jchuff.c:

Include dependency graph

Go to the source code of this file.

Data Structures

struct  huff_entropy_encoder
struct  savable_state
struct  working_state

Defines

#define ASSIGN_STATE(dest, src)   ((dest) = (src))
#define emit_byte(state, val, action)
#define JPEG_INTERNALS
#define MAX_CLEN   32

Typedefs

typedef huff_entropy_encoderhuff_entropy_ptr

Functions

LOCAL boolean dump_buffer (working_state *state)
INLINE LOCAL boolean emit_bits (working_state *state, unsigned int code, int size)
LOCAL boolean emit_restart (working_state *state, int restart_num)
METHODDEF boolean encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
METHODDEF boolean encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
LOCAL boolean encode_one_block (working_state *state, JCOEFPTR block, int last_dc_val, c_derived_tbl *dctbl, c_derived_tbl *actbl)
METHODDEF void finish_pass_gather (j_compress_ptr cinfo)
METHODDEF void finish_pass_huff (j_compress_ptr cinfo)
LOCAL boolean flush_bits (working_state *state)
LOCAL void htest_one_block (JCOEFPTR block, int last_dc_val, long dc_counts[], long ac_counts[])
GLOBAL void jinit_huff_encoder (j_compress_ptr cinfo)
GLOBAL void jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[])
GLOBAL void jpeg_make_c_derived_tbl (j_compress_ptr cinfo, JHUFF_TBL *htbl, c_derived_tbl **pdtbl)
METHODDEF void finish_pass_huff JPP ((j_compress_ptr cinfo))
METHODDEF boolean encode_mcu_huff JPP ((j_compress_ptr cinfo, JBLOCKROW *MCU_data))
METHODDEF void start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)


Define Documentation

#define ASSIGN_STATE dest,
src   )     ((dest) = (src))
 

Definition at line 41 of file jchuff.c.

Referenced by decode_mcu(), encode_mcu_huff(), and finish_pass_huff().

#define emit_byte state,
val,
action   ) 
 

Value:

{ *(state)->next_output_byte++ = (JOCTET) (val);  \
      if (--(state)->free_in_buffer == 0)  \
        if (! dump_buffer(state))  \
          { action; } }

Definition at line 239 of file jchuff.c.

Referenced by emit_2bytes(), emit_adobe_app14(), emit_bits(), emit_dac(), emit_dht(), emit_dqt(), emit_jfif_app0(), emit_marker(), emit_restart(), emit_sof(), emit_sos(), and write_any_marker().

#define JPEG_INTERNALS
 

Definition at line 17 of file jchuff.c.

#define MAX_CLEN   32
 

Referenced by jpeg_gen_optimal_table().


Typedef Documentation

typedef huff_entropy_encoder* huff_entropy_ptr
 

Definition at line 74 of file jchuff.c.

Referenced by decode_mcu(), encode_mcu_gather(), encode_mcu_huff(), finish_pass_gather(), finish_pass_huff(), jinit_huff_decoder(), jinit_huff_encoder(), process_restart(), start_pass_huff(), and start_pass_huff_decoder().


Function Documentation

LOCAL boolean dump_buffer working_state state  ) 
 

Definition at line 247 of file jchuff.c.

References working_state::cinfo, jpeg_compress_struct::dest, jpeg_destination_mgr::free_in_buffer, working_state::free_in_buffer, jpeg_destination_mgr::next_output_byte, working_state::next_output_byte, and state.

00249 {
00250   struct jpeg_destination_mgr * dest = state->cinfo->dest;
00251 
00252   if (! (*dest->empty_output_buffer) (state->cinfo))
00253     return FALSE;
00254   /* After a successful buffer dump, must reset buffer pointers */
00255   state->next_output_byte = dest->next_output_byte;
00256   state->free_in_buffer = dest->free_in_buffer;
00257   return TRUE;
00258 }

INLINE LOCAL boolean emit_bits working_state state,
unsigned int  code,
int  size
 

Definition at line 271 of file jchuff.c.

References c, working_state::cinfo, working_state::cur, emit_byte, ERREXIT, FALSE, INT32, JERR_HUFF_MISSING_CODE, savable_state::put_bits, savable_state::put_buffer, and state.

00273 {
00274   /* This routine is heavily used, so it's worth coding tightly. */
00275   register INT32 put_buffer = (INT32) code;
00276   register int put_bits = state->cur.put_bits;
00277 
00278   /* if size is 0, caller used an invalid Huffman table entry */
00279   if (size == 0)
00280     ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE);
00281 
00282   put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
00283   
00284   put_bits += size;     /* new number of bits in buffer */
00285   
00286   put_buffer <<= 24 - put_bits; /* align incoming bits */
00287 
00288   put_buffer |= state->cur.put_buffer; /* and merge with old buffer contents */
00289   
00290   while (put_bits >= 8) {
00291     int c = (int) ((put_buffer >> 16) & 0xFF);
00292     
00293     emit_byte(state, c, return FALSE);
00294     if (c == 0xFF) {        /* need to stuff a zero byte? */
00295       emit_byte(state, 0, return FALSE);
00296     }
00297     put_buffer <<= 8;
00298     put_bits -= 8;
00299   }
00300 
00301   state->cur.put_buffer = put_buffer; /* update state variables */
00302   state->cur.put_bits = put_bits;
00303 
00304   return TRUE;
00305 }

LOCAL boolean emit_restart working_state state,
int  restart_num
 

Definition at line 412 of file jchuff.c.

References working_state::cinfo, jpeg_compress_struct::comps_in_scan, working_state::cur, emit_byte, FALSE, flush_bits(), JPEG_RST0, savable_state::last_dc_val, and state.

00413 {
00414   int ci;
00415 
00416   if (! flush_bits(state))
00417     return FALSE;
00418 
00419   emit_byte(state, 0xFF, return FALSE);
00420   emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
00421 
00422   /* Re-initialize DC predictions to 0 */
00423   for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
00424     state->cur.last_dc_val[ci] = 0;
00425 
00426   /* The restart counter is not updated until we successfully write the MCU. */
00427 
00428   return TRUE;
00429 }

Here is the call graph for this function:

METHODDEF boolean encode_mcu_gather j_compress_ptr  cinfo,
JBLOCKROW MCU_data
 

Definition at line 605 of file jchuff.c.

References huff_entropy_encoder::ac_count_ptrs, jpeg_component_info::ac_tbl_no, jpeg_compress_struct::blocks_in_MCU, jpeg_compress_struct::comps_in_scan, jpeg_compress_struct::cur_comp_info, huff_entropy_encoder::dc_count_ptrs, jpeg_component_info::dc_tbl_no, jpeg_compress_struct::entropy, htest_one_block(), huff_entropy_ptr, j_compress_ptr, savable_state::last_dc_val, jpeg_compress_struct::MCU_membership, jpeg_compress_struct::restart_interval, huff_entropy_encoder::restarts_to_go, and huff_entropy_encoder::saved.

00606 {
00607   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00608   int blkn, ci;
00609   jpeg_component_info * compptr;
00610 
00611   /* Take care of restart intervals if needed */
00612   if (cinfo->restart_interval) {
00613     if (entropy->restarts_to_go == 0) {
00614       /* Re-initialize DC predictions to 0 */
00615       for (ci = 0; ci < cinfo->comps_in_scan; ci++)
00616     entropy->saved.last_dc_val[ci] = 0;
00617       /* Update restart state */
00618       entropy->restarts_to_go = cinfo->restart_interval;
00619     }
00620     entropy->restarts_to_go--;
00621   }
00622 
00623   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
00624     ci = cinfo->MCU_membership[blkn];
00625     compptr = cinfo->cur_comp_info[ci];
00626     htest_one_block(MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
00627             entropy->dc_count_ptrs[compptr->dc_tbl_no],
00628             entropy->ac_count_ptrs[compptr->ac_tbl_no]);
00629     entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
00630   }
00631 
00632   return TRUE;
00633 }

Here is the call graph for this function:

METHODDEF boolean encode_mcu_huff j_compress_ptr  cinfo,
JBLOCKROW MCU_data
 

Definition at line 437 of file jchuff.c.

References huff_entropy_encoder::ac_derived_tbls, jpeg_component_info::ac_tbl_no, ASSIGN_STATE, jpeg_compress_struct::blocks_in_MCU, working_state::cinfo, working_state::cur, jpeg_compress_struct::cur_comp_info, huff_entropy_encoder::dc_derived_tbls, jpeg_component_info::dc_tbl_no, jpeg_compress_struct::dest, emit_restart(), encode_one_block(), jpeg_compress_struct::entropy, jpeg_destination_mgr::free_in_buffer, working_state::free_in_buffer, huff_entropy_ptr, j_compress_ptr, savable_state::last_dc_val, jpeg_compress_struct::MCU_membership, jpeg_destination_mgr::next_output_byte, working_state::next_output_byte, huff_entropy_encoder::next_restart_num, jpeg_compress_struct::restart_interval, huff_entropy_encoder::restarts_to_go, huff_entropy_encoder::saved, and state.

00438 {
00439   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00440   working_state state;
00441   int blkn, ci;
00442   jpeg_component_info * compptr;
00443 
00444   /* Load up working state */
00445   state.next_output_byte = cinfo->dest->next_output_byte;
00446   state.free_in_buffer = cinfo->dest->free_in_buffer;
00447   ASSIGN_STATE(state.cur, entropy->saved);
00448   state.cinfo = cinfo;
00449 
00450   /* Emit restart marker if needed */
00451   if (cinfo->restart_interval) {
00452     if (entropy->restarts_to_go == 0)
00453       if (! emit_restart(&state, entropy->next_restart_num))
00454     return FALSE;
00455   }
00456 
00457   /* Encode the MCU data blocks */
00458   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
00459     ci = cinfo->MCU_membership[blkn];
00460     compptr = cinfo->cur_comp_info[ci];
00461     if (! encode_one_block(&state,
00462                MCU_data[blkn][0], state.cur.last_dc_val[ci],
00463                entropy->dc_derived_tbls[compptr->dc_tbl_no],
00464                entropy->ac_derived_tbls[compptr->ac_tbl_no]))
00465       return FALSE;
00466     /* Update last_dc_val */
00467     state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
00468   }
00469 
00470   /* Completed MCU, so update state */
00471   cinfo->dest->next_output_byte = state.next_output_byte;
00472   cinfo->dest->free_in_buffer = state.free_in_buffer;
00473   ASSIGN_STATE(entropy->saved, state.cur);
00474 
00475   /* Update restart-interval state too */
00476   if (cinfo->restart_interval) {
00477     if (entropy->restarts_to_go == 0) {
00478       entropy->restarts_to_go = cinfo->restart_interval;
00479       entropy->next_restart_num++;
00480       entropy->next_restart_num &= 7;
00481     }
00482     entropy->restarts_to_go--;
00483   }
00484 
00485   return TRUE;
00486 }

Here is the call graph for this function:

LOCAL boolean encode_one_block working_state state,
JCOEFPTR  block,
int  last_dc_val,
c_derived_tbl dctbl,
c_derived_tbl actbl
 

Definition at line 322 of file jchuff.c.

References c_derived_tbl::ehufco, c_derived_tbl::ehufsi, emit_bits(), i, jpeg_natural_order, k, r, and state.

Referenced by encode_mcu_huff().

00324 {
00325   register int temp, temp2;
00326   register int nbits;
00327   register int k, r, i;
00328   
00329   /* Encode the DC coefficient difference per section F.1.2.1 */
00330   
00331   temp = temp2 = block[0] - last_dc_val;
00332 
00333   if (temp < 0) {
00334     temp = -temp;       /* temp is abs value of input */
00335     /* For a negative input, want temp2 = bitwise complement of abs(input) */
00336     /* This code assumes we are on a two's complement machine */
00337     temp2--;
00338   }
00339   
00340   /* Find the number of bits needed for the magnitude of the coefficient */
00341   nbits = 0;
00342   while (temp) {
00343     nbits++;
00344     temp >>= 1;
00345   }
00346   
00347   /* Emit the Huffman-coded symbol for the number of bits */
00348   if (! emit_bits(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits]))
00349     return FALSE;
00350 
00351   /* Emit that number of bits of the value, if positive, */
00352   /* or the complement of its magnitude, if negative. */
00353   if (nbits)            /* emit_bits rejects calls with size 0 */
00354     if (! emit_bits(state, (unsigned int) temp2, nbits))
00355       return FALSE;
00356 
00357   /* Encode the AC coefficients per section F.1.2.2 */
00358   
00359   r = 0;            /* r = run length of zeros */
00360   
00361   for (k = 1; k < DCTSIZE2; k++) {
00362     if ((temp = block[jpeg_natural_order[k]]) == 0) {
00363       r++;
00364     } else {
00365       /* if run length > 15, must emit special run-length-16 codes (0xF0) */
00366       while (r > 15) {
00367     if (! emit_bits(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0]))
00368       return FALSE;
00369     r -= 16;
00370       }
00371 
00372       temp2 = temp;
00373       if (temp < 0) {
00374     temp = -temp;       /* temp is abs value of input */
00375     /* This code assumes we are on a two's complement machine */
00376     temp2--;
00377       }
00378       
00379       /* Find the number of bits needed for the magnitude of the coefficient */
00380       nbits = 1;        /* there must be at least one 1 bit */
00381       while ((temp >>= 1))
00382     nbits++;
00383       
00384       /* Emit Huffman symbol for run length / number of bits */
00385       i = (r << 4) + nbits;
00386       if (! emit_bits(state, actbl->ehufco[i], actbl->ehufsi[i]))
00387     return FALSE;
00388 
00389       /* Emit that number of bits of the value, if positive, */
00390       /* or the complement of its magnitude, if negative. */
00391       if (! emit_bits(state, (unsigned int) temp2, nbits))
00392     return FALSE;
00393       
00394       r = 0;
00395     }
00396   }
00397 
00398   /* If the last coef(s) were zero, emit an end-of-block code */
00399   if (r > 0)
00400     if (! emit_bits(state, actbl->ehufco[0], actbl->ehufsi[0]))
00401       return FALSE;
00402 
00403   return TRUE;
00404 }

Here is the call graph for this function:

METHODDEF void finish_pass_gather j_compress_ptr  cinfo  ) 
 

Definition at line 783 of file jchuff.c.

References huff_entropy_encoder::ac_count_ptrs, jpeg_compress_struct::ac_huff_tbl_ptrs, jpeg_component_info::ac_tbl_no, jpeg_compress_struct::comps_in_scan, jpeg_compress_struct::cur_comp_info, huff_entropy_encoder::dc_count_ptrs, jpeg_compress_struct::dc_huff_tbl_ptrs, jpeg_component_info::dc_tbl_no, jpeg_compress_struct::entropy, huff_entropy_ptr, j_common_ptr, j_compress_ptr, jpeg_alloc_huff_table(), jpeg_gen_optimal_table(), MEMZERO, and SIZEOF.

00784 {
00785   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00786   int ci, dctbl, actbl;
00787   jpeg_component_info * compptr;
00788   JHUFF_TBL **htblptr;
00789   boolean did_dc[NUM_HUFF_TBLS];
00790   boolean did_ac[NUM_HUFF_TBLS];
00791 
00792   /* It's important not to apply jpeg_gen_optimal_table more than once
00793    * per table, because it clobbers the input frequency counts!
00794    */
00795   MEMZERO(did_dc, SIZEOF(did_dc));
00796   MEMZERO(did_ac, SIZEOF(did_ac));
00797 
00798   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
00799     compptr = cinfo->cur_comp_info[ci];
00800     dctbl = compptr->dc_tbl_no;
00801     actbl = compptr->ac_tbl_no;
00802     if (! did_dc[dctbl]) {
00803       htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
00804       if (*htblptr == NULL)
00805     *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
00806       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]);
00807       did_dc[dctbl] = TRUE;
00808     }
00809     if (! did_ac[actbl]) {
00810       htblptr = & cinfo->ac_huff_tbl_ptrs[actbl];
00811       if (*htblptr == NULL)
00812     *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
00813       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]);
00814       did_ac[actbl] = TRUE;
00815     }
00816   }
00817 }

Here is the call graph for this function:

METHODDEF void finish_pass_huff j_compress_ptr  cinfo  ) 
 

Definition at line 494 of file jchuff.c.

References ASSIGN_STATE, working_state::cinfo, working_state::cur, jpeg_compress_struct::dest, jpeg_compress_struct::entropy, ERREXIT, flush_bits(), jpeg_destination_mgr::free_in_buffer, working_state::free_in_buffer, huff_entropy_ptr, j_compress_ptr, jpeg_destination_mgr::next_output_byte, working_state::next_output_byte, huff_entropy_encoder::saved, and state.

00495 {
00496   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00497   working_state state;
00498 
00499   /* Load up working state ... flush_bits needs it */
00500   state.next_output_byte = cinfo->dest->next_output_byte;
00501   state.free_in_buffer = cinfo->dest->free_in_buffer;
00502   ASSIGN_STATE(state.cur, entropy->saved);
00503   state.cinfo = cinfo;
00504 
00505   /* Flush out the last data */
00506   if (! flush_bits(&state))
00507     ERREXIT(cinfo, JERR_CANT_SUSPEND);
00508 
00509   /* Update state */
00510   cinfo->dest->next_output_byte = state.next_output_byte;
00511   cinfo->dest->free_in_buffer = state.free_in_buffer;
00512   ASSIGN_STATE(entropy->saved, state.cur);
00513 }

Here is the call graph for this function:

LOCAL boolean flush_bits working_state state  ) 
 

Definition at line 309 of file jchuff.c.

References working_state::cur, emit_bits(), savable_state::put_bits, savable_state::put_buffer, and state.

00310 {
00311   if (! emit_bits(state, 0x7F, 7)) /* fill any partial byte with ones */
00312     return FALSE;
00313   state->cur.put_buffer = 0;    /* and reset bit-buffer to empty */
00314   state->cur.put_bits = 0;
00315   return TRUE;
00316 }

Here is the call graph for this function:

LOCAL void htest_one_block JCOEFPTR  block,
int  last_dc_val,
long  dc_counts[],
long  ac_counts[]
 

Definition at line 540 of file jchuff.c.

References jpeg_natural_order, k, and r.

Referenced by encode_mcu_gather().

00542 {
00543   register int temp;
00544   register int nbits;
00545   register int k, r;
00546   
00547   /* Encode the DC coefficient difference per section F.1.2.1 */
00548   
00549   temp = block[0] - last_dc_val;
00550   if (temp < 0)
00551     temp = -temp;
00552   
00553   /* Find the number of bits needed for the magnitude of the coefficient */
00554   nbits = 0;
00555   while (temp) {
00556     nbits++;
00557     temp >>= 1;
00558   }
00559 
00560   /* Count the Huffman symbol for the number of bits */
00561   dc_counts[nbits]++;
00562   
00563   /* Encode the AC coefficients per section F.1.2.2 */
00564   
00565   r = 0;            /* r = run length of zeros */
00566   
00567   for (k = 1; k < DCTSIZE2; k++) {
00568     if ((temp = block[jpeg_natural_order[k]]) == 0) {
00569       r++;
00570     } else {
00571       /* if run length > 15, must emit special run-length-16 codes (0xF0) */
00572       while (r > 15) {
00573     ac_counts[0xF0]++;
00574     r -= 16;
00575       }
00576       
00577       /* Find the number of bits needed for the magnitude of the coefficient */
00578       if (temp < 0)
00579     temp = -temp;
00580       
00581       /* Find the number of bits needed for the magnitude of the coefficient */
00582       nbits = 1;        /* there must be at least one 1 bit */
00583       while ((temp >>= 1))
00584     nbits++;
00585       
00586       /* Count Huffman symbol for run length / number of bits */
00587       ac_counts[(r << 4) + nbits]++;
00588       
00589       r = 0;
00590     }
00591   }
00592 
00593   /* If the last coef(s) were zero, emit an end-of-block code */
00594   if (r > 0)
00595     ac_counts[0]++;
00596 }

GLOBAL void jinit_huff_encoder j_compress_ptr  cinfo  ) 
 

Definition at line 828 of file jchuff.c.

References huff_entropy_encoder::ac_count_ptrs, huff_entropy_encoder::ac_derived_tbls, huff_entropy_encoder::dc_count_ptrs, huff_entropy_encoder::dc_derived_tbls, jpeg_compress_struct::entropy, huff_entropy_ptr, i, j_common_ptr, j_compress_ptr, huff_entropy_encoder::pub, and SIZEOF.

Referenced by jinit_compress_master(), and transencode_master_selection().

00829 {
00830   huff_entropy_ptr entropy;
00831   int i;
00832 
00833   entropy = (huff_entropy_ptr)
00834     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
00835                 SIZEOF(huff_entropy_encoder));
00836   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
00837   entropy->pub.start_pass = start_pass_huff;
00838 
00839   /* Mark tables unallocated */
00840   for (i = 0; i < NUM_HUFF_TBLS; i++) {
00841     entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
00842 #ifdef ENTROPY_OPT_SUPPORTED
00843     entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;
00844 #endif
00845   }
00846 }

GLOBAL void jpeg_gen_optimal_table j_compress_ptr  cinfo,
JHUFF_TBL htbl,
long  freq[]
 

Definition at line 642 of file jchuff.c.

References JHUFF_TBL::bits, bits, ERREXIT, JHUFF_TBL::huffval, i, j, j_compress_ptr, JERR_HUFF_CLEN_OVERFLOW, MAX_CLEN, MEMCOPY, MEMZERO, p, JHUFF_TBL::sent_table, SIZEOF, UINT8, and v.

Referenced by finish_pass_gather(), and finish_pass_gather_phuff().

00643 {
00644 #define MAX_CLEN 32     /* assumed maximum initial code length */
00645   UINT8 bits[MAX_CLEN+1];   /* bits[k] = # of symbols with code length k */
00646   int codesize[257];        /* codesize[k] = code length of symbol k */
00647   int others[257];      /* next symbol in current branch of tree */
00648   int c1, c2;
00649   int p, i, j;
00650   long v;
00651 
00652   /* This algorithm is explained in section K.2 of the JPEG standard */
00653 
00654   MEMZERO(bits, SIZEOF(bits));
00655   MEMZERO(codesize, SIZEOF(codesize));
00656   for (i = 0; i < 257; i++)
00657     others[i] = -1;     /* init links to empty */
00658   
00659   freq[256] = 1;        /* make sure there is a nonzero count */
00660   /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
00661    * that no real symbol is given code-value of all ones, because 256
00662    * will be placed in the largest codeword category.
00663    */
00664 
00665   /* Huffman's basic algorithm to assign optimal code lengths to symbols */
00666 
00667   for (;;) {
00668     /* Find the smallest nonzero frequency, set c1 = its symbol */
00669     /* In case of ties, take the larger symbol number */
00670     c1 = -1;
00671     v = 1000000000L;
00672     for (i = 0; i <= 256; i++) {
00673       if (freq[i] && freq[i] <= v) {
00674     v = freq[i];
00675     c1 = i;
00676       }
00677     }
00678 
00679     /* Find the next smallest nonzero frequency, set c2 = its symbol */
00680     /* In case of ties, take the larger symbol number */
00681     c2 = -1;
00682     v = 1000000000L;
00683     for (i = 0; i <= 256; i++) {
00684       if (freq[i] && freq[i] <= v && i != c1) {
00685     v = freq[i];
00686     c2 = i;
00687       }
00688     }
00689 
00690     /* Done if we've merged everything into one frequency */
00691     if (c2 < 0)
00692       break;
00693     
00694     /* Else merge the two counts/trees */
00695     freq[c1] += freq[c2];
00696     freq[c2] = 0;
00697 
00698     /* Increment the codesize of everything in c1's tree branch */
00699     codesize[c1]++;
00700     while (others[c1] >= 0) {
00701       c1 = others[c1];
00702       codesize[c1]++;
00703     }
00704     
00705     others[c1] = c2;        /* chain c2 onto c1's tree branch */
00706     
00707     /* Increment the codesize of everything in c2's tree branch */
00708     codesize[c2]++;
00709     while (others[c2] >= 0) {
00710       c2 = others[c2];
00711       codesize[c2]++;
00712     }
00713   }
00714 
00715   /* Now count the number of symbols of each code length */
00716   for (i = 0; i <= 256; i++) {
00717     if (codesize[i]) {
00718       /* The JPEG standard seems to think that this can't happen, */
00719       /* but I'm paranoid... */
00720       if (codesize[i] > MAX_CLEN)
00721     ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW);
00722 
00723       bits[codesize[i]]++;
00724     }
00725   }
00726 
00727   /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
00728    * Huffman procedure assigned any such lengths, we must adjust the coding.
00729    * Here is what the JPEG spec says about how this next bit works:
00730    * Since symbols are paired for the longest Huffman code, the symbols are
00731    * removed from this length category two at a time.  The prefix for the pair
00732    * (which is one bit shorter) is allocated to one of the pair; then,
00733    * skipping the BITS entry for that prefix length, a code word from the next
00734    * shortest nonzero BITS entry is converted into a prefix for two code words
00735    * one bit longer.
00736    */
00737   
00738   for (i = MAX_CLEN; i > 16; i--) {
00739     while (bits[i] > 0) {
00740       j = i - 2;        /* find length of new prefix to be used */
00741       while (bits[j] == 0)
00742     j--;
00743       
00744       bits[i] -= 2;     /* remove two symbols */
00745       bits[i-1]++;      /* one goes in this length */
00746       bits[j+1] += 2;       /* two new symbols in this length */
00747       bits[j]--;        /* symbol of this length is now a prefix */
00748     }
00749   }
00750 
00751   /* Remove the count for the pseudo-symbol 256 from the largest codelength */
00752   while (bits[i] == 0)      /* find largest codelength still in use */
00753     i--;
00754   bits[i]--;
00755   
00756   /* Return final symbol counts (only for lengths 0..16) */
00757   MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits));
00758   
00759   /* Return a list of the symbols sorted by code length */
00760   /* It's not real clear to me why we don't need to consider the codelength
00761    * changes made above, but the JPEG spec seems to think this works.
00762    */
00763   p = 0;
00764   for (i = 1; i <= MAX_CLEN; i++) {
00765     for (j = 0; j <= 255; j++) {
00766       if (codesize[j] == i) {
00767     htbl->huffval[p] = (UINT8) j;
00768     p++;
00769       }
00770     }
00771   }
00772 
00773   /* Set sent_table FALSE so updated table will be written to JPEG file. */
00774   htbl->sent_table = FALSE;
00775 }

GLOBAL void jpeg_make_c_derived_tbl j_compress_ptr  cinfo,
JHUFF_TBL htbl,
c_derived_tbl **  pdtbl
 

Definition at line 179 of file jchuff.c.

References JHUFF_TBL::bits, code, c_derived_tbl::ehufco, c_derived_tbl::ehufsi, JHUFF_TBL::huffval, i, j_common_ptr, j_compress_ptr, l, MEMZERO, p, and SIZEOF.

Referenced by start_pass_huff(), and start_pass_phuff().

00181 {
00182   c_derived_tbl *dtbl;
00183   int p, i, l, lastp, si;
00184   char huffsize[257];
00185   unsigned int huffcode[257];
00186   unsigned int code;
00187 
00188   /* Allocate a workspace if we haven't already done so. */
00189   if (*pdtbl == NULL)
00190     *pdtbl = (c_derived_tbl *)
00191       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
00192                   SIZEOF(c_derived_tbl));
00193   dtbl = *pdtbl;
00194   
00195   /* Figure C.1: make table of Huffman code length for each symbol */
00196   /* Note that this is in code-length order. */
00197 
00198   p = 0;
00199   for (l = 1; l <= 16; l++) {
00200     for (i = 1; i <= (int) htbl->bits[l]; i++)
00201       huffsize[p++] = (char) l;
00202   }
00203   huffsize[p] = 0;
00204   lastp = p;
00205   
00206   /* Figure C.2: generate the codes themselves */
00207   /* Note that this is in code-length order. */
00208   
00209   code = 0;
00210   si = huffsize[0];
00211   p = 0;
00212   while (huffsize[p]) {
00213     while (((int) huffsize[p]) == si) {
00214       huffcode[p++] = code;
00215       code++;
00216     }
00217     code <<= 1;
00218     si++;
00219   }
00220   
00221   /* Figure C.3: generate encoding tables */
00222   /* These are code and size indexed by symbol value */
00223 
00224   /* Set any codeless symbols to have code length 0;
00225    * this allows emit_bits to detect any attempt to emit such symbols.
00226    */
00227   MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi));
00228 
00229   for (p = 0; p < lastp; p++) {
00230     dtbl->ehufco[htbl->huffval[p]] = huffcode[p];
00231     dtbl->ehufsi[htbl->huffval[p]] = huffsize[p];
00232   }
00233 }

EXTERN void jpeg_abort_compress JPP (j_compress_ptr cinfo)   ) 
 

METHODDEF boolean encode_mcu_AC_refine JPP (j_compress_ptr cinfo, JBLOCKROW *MCU_data)   ) 
 

METHODDEF void start_pass_huff j_compress_ptr  cinfo,
boolean  gather_statistics
 

Definition at line 106 of file jchuff.c.

References huff_entropy_encoder::ac_count_ptrs, huff_entropy_encoder::ac_derived_tbls, jpeg_compress_struct::ac_huff_tbl_ptrs, jpeg_component_info::ac_tbl_no, jpeg_compress_struct::comps_in_scan, jpeg_compress_struct::cur_comp_info, huff_entropy_encoder::dc_count_ptrs, huff_entropy_encoder::dc_derived_tbls, jpeg_compress_struct::dc_huff_tbl_ptrs, jpeg_component_info::dc_tbl_no, jpeg_compress_struct::entropy, ERREXIT, ERREXIT1, huff_entropy_ptr, j_common_ptr, j_compress_ptr, JERR_NO_HUFF_TABLE, JERR_NOT_COMPILED, jpeg_make_c_derived_tbl(), savable_state::last_dc_val, MEMZERO, huff_entropy_encoder::next_restart_num, NULL, NUM_HUFF_TBLS, huff_entropy_encoder::pub, savable_state::put_bits, savable_state::put_buffer, jpeg_compress_struct::restart_interval, huff_entropy_encoder::restarts_to_go, huff_entropy_encoder::saved, and SIZEOF.

00107 {
00108   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00109   int ci, dctbl, actbl;
00110   jpeg_component_info * compptr;
00111 
00112   if (gather_statistics) {
00113 #ifdef ENTROPY_OPT_SUPPORTED
00114     entropy->pub.encode_mcu = encode_mcu_gather;
00115     entropy->pub.finish_pass = finish_pass_gather;
00116 #else
00117     ERREXIT(cinfo, JERR_NOT_COMPILED);
00118 #endif
00119   } else {
00120     entropy->pub.encode_mcu = encode_mcu_huff;
00121     entropy->pub.finish_pass = finish_pass_huff;
00122   }
00123 
00124   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
00125     compptr = cinfo->cur_comp_info[ci];
00126     dctbl = compptr->dc_tbl_no;
00127     actbl = compptr->ac_tbl_no;
00128     /* Make sure requested tables are present */
00129     /* (In gather mode, tables need not be allocated yet) */
00130     if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS ||
00131     (cinfo->dc_huff_tbl_ptrs[dctbl] == NULL && !gather_statistics))
00132       ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
00133     if (actbl < 0 || actbl >= NUM_HUFF_TBLS ||
00134     (cinfo->ac_huff_tbl_ptrs[actbl] == NULL && !gather_statistics))
00135       ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
00136     if (gather_statistics) {
00137 #ifdef ENTROPY_OPT_SUPPORTED
00138       /* Allocate and zero the statistics tables */
00139       /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
00140       if (entropy->dc_count_ptrs[dctbl] == NULL)
00141     entropy->dc_count_ptrs[dctbl] = (long *)
00142       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
00143                       257 * SIZEOF(long));
00144       MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * SIZEOF(long));
00145       if (entropy->ac_count_ptrs[actbl] == NULL)
00146     entropy->ac_count_ptrs[actbl] = (long *)
00147       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
00148                       257 * SIZEOF(long));
00149       MEMZERO(entropy->ac_count_ptrs[actbl], 257 * SIZEOF(long));
00150 #endif
00151     } else {
00152       /* Compute derived values for Huffman tables */
00153       /* We may do this more than once for a table, but it's not expensive */
00154       jpeg_make_c_derived_tbl(cinfo, cinfo->dc_huff_tbl_ptrs[dctbl],
00155                   & entropy->dc_derived_tbls[dctbl]);
00156       jpeg_make_c_derived_tbl(cinfo, cinfo->ac_huff_tbl_ptrs[actbl],
00157                   & entropy->ac_derived_tbls[actbl]);
00158     }
00159     /* Initialize DC predictions to 0 */
00160     entropy->saved.last_dc_val[ci] = 0;
00161   }
00162 
00163   /* Initialize bit buffer to empty */
00164   entropy->saved.put_buffer = 0;
00165   entropy->saved.put_bits = 0;
00166 
00167   /* Initialize restart stuff */
00168   entropy->restarts_to_go = cinfo->restart_interval;
00169   entropy->next_restart_num = 0;
00170 }

Here is the call graph for this function:


Generated on Thu Aug 25 14:00:29 2005 for Quake III Arena by  doxygen 1.3.9.1