jchuff.c

JPEG Image compression using IJG standards followed

 */

INLINE
LOCAL(boolean)
emit_bits (working_state * state, unsigned int code, int size)
/* Emit some bits; return TRUE if successful, FALSE if must suspend */
{
  /* This routine is heavily used, so it's worth coding tightly. */
  register INT32 put_buffer = (INT32) code;
  register int put_bits = state->cur.put_bits;

  /* if size is 0, caller used an invalid Huffman table entry */
  if (size == 0){
	ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE);
  }

  put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
  
  put_bits += size;		/* new number of bits in buffer */
  
  put_buffer <<= 24 - put_bits; /* align incoming bits */

  put_buffer |= state->cur.put_buffer; /* and merge with old buffer contents */
  
  while (put_bits >= 8) {           /* put_buffer > 16 bits ?*/
    int c = (int) ((put_buffer >> 16) & 0xFF);
    
    emit_byte(state, c, return FALSE);
    if (c == 0xFF) {		/* need to stuff a zero byte? */
      emit_byte(state, 0, return FALSE);
    }
    put_buffer <<= 8;
    put_bits -= 8;
  }

  state->cur.put_buffer = put_buffer; /* update state variables */
  state->cur.put_bits = put_bits;

  return TRUE;
}


LOCAL(boolean)
flush_bits (working_state * state)
{
  if (! emit_bits(state, 0x7F, 7)) /* fill any partial byte with ones */
    return FALSE;
  state->cur.put_buffer = 0;	/* and reset bit-buffer to empty */
  state->cur.put_bits = 0;
  return TRUE;
}


/* Encode a single block's worth of coefficients */

LOCAL(boolean)
encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val,
		  c_derived_tbl *dctbl, c_derived_tbl *actbl)
{
  register int temp, temp2;
  register int nbits;
  register int k, r, i;
  extern boolean lossless_codec;

  /************************************************************/ 
  /* Encode the DC coefficient difference per section F.1.2.1 */
  /************************************************************/
  
  temp = temp2 = block[0] - last_dc_val;

  if (temp < 0) {
    temp = -temp;		/* temp is abs value of input */
    /* For a negative input, want temp2 = bitwise complement of abs(input) */
    /* This code assumes we are on a two's complement machine */
    temp2--;
  }
  
  /* Find the number of bits needed for the magnitude of the coefficient */
  nbits = 0;
  while (temp) {
    nbits++;
    temp >>= 1;
  }

  //take statistics of the binDCT  coef.
  bindct_dc_cnt[nbits]++;

  /* JIE 07/03/00, In lossless binDCT, the binDCT MAX_COEF_BITS should be augued by 3 bits, as there is no scaling coef */
  if ((!lossless_codec) && (nbits > (MAX_COEF_BITS+1))) {
	ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);
  } else if ((lossless_codec) && (nbits > (MAX_COEF_BITS+3+1))) {
    ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);
  }

  /* Emit the Huffman-coded symbol for the number of bits */
  if (! emit_bits(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits]))
    return FALSE;

  /* Emit that number of bits of the value, if positive, */
  /* or the complement of its magnitude, if negative. */
  if (nbits)			/* emit_bits rejects calls with size 0 */
    if (! emit_bits(state, (unsigned int) temp2, nbits))
      return FALSE;

  /************************************************************/
  /* Encode the AC coefficients per section F.1.2.2 */
  /************************************************************/
  
  r = 0;			/* r = run length of zeros */
  
  for (k = 1; k < DCTSIZE2; k++) {
    if ((temp = block[jpeg_natural_order[k]]) == 0) {
      r++;
    } else {

      /* if run length > 15, must emit special run-length-16 codes (0xF0) */
      while (r > 15) {

		if (! emit_bits(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0]))
		  return FALSE;
		r -= 16;
      }

    temp2 = temp;
    if (temp < 0) {
	  temp = -temp;		/* temp is abs value of input */
	  /* This code assumes we are on a two's complement machine */
	  temp2--;
    }
      
    /* Find the number of bits needed for the magnitude of the coefficient */
    nbits = 1;		/* there must be at least one 1 bit */
    while ((temp >>= 1))
	  nbits++;

      /* Check for out-of-range coefficient values */
	  /*      if (nbits > MAX_COEF_BITS)
			  ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);*/

      /* JIE 07/03/00, In lossless binDCT, the binDCT MAX_COEF_BITS should be augued by 3 bits, coz no scaling coef */
	  if ((FALSE == lossless_codec) && (nbits > MAX_COEF_BITS)) {
		ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);
	  } else if ((TRUE == lossless_codec) && (nbits > MAX_COEF_BITS+3)) {
		ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);
	  }
  
      /* Emit Huffman symbol for run length / number of bits */

	  /* Jie: 07/03/00 */
	  /* this is the index of the table as shown in the P&M book, p192. */
	  /* it's the combination of the runs of zeros and the category of the terminated non-zero coefficient. */
	  /* To support lossless binDCT, the table should be augumented by at least 3 columns, i.e., 3 more mag. categories. */
	  /* the category number is actually the number of bits to represent the values in the category. */

      i = (r << 4) + nbits;

	  bindct_ac_cnt[i]++;

	  //	  fprintf(stderr,"%d, %d\n", r, nbits);

      if (! emit_bits(state, actbl->ehufco[i], actbl->ehufsi[i]))
		return FALSE;

      /* Emit that number of bits of the value, if positive, */
      /* or the complement of its magnitude, if negative. */
      if (! emit_bits(state, (unsigned int) temp2, nbits))
		return FALSE;
      
      r = 0;
    }
  }

  /* If the last coef(s) were zero, emit an end-of-block code */
  if (r > 0) {

    if (! emit_bits(state, actbl->ehufco[0], actbl->ehufsi[0]))
      return FALSE;
  }

  return TRUE;
}


/*
 * Emit a restart marker & resynchronize predictions.
 */

LOCAL(boolean)
emit_restart (working_state * state, int restart_num)
{
  int ci;

  if (! flush_bits(state))
    return FALSE;

  emit_byte(state, 0xFF, return FALSE);
  emit_byte(state, JPEG_RST0 + restart_num, return FALSE);

  /* Re-initialize DC predictions to 0 */
  for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
    state->cur.last_dc_val[ci] = 0;

  /* The restart counter is not updated until we successfully write the MCU. */

  return TRUE;
}


/*
 * Encode and output one MCU's worth of Huffman-compressed coefficients.
 */

METHODDEF(boolean)
encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
{
  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
  working_state state;
  int blkn, ci;
  jpeg_component_info * compptr;

  /* Load up working state */
  state.next_output_byte = cinfo->dest->next_output_byte;
  state.free_in_buffer = cinfo->dest->free_in_buffer;
  ASSIGN_STATE(state.cur, entropy->saved);
  state.cinfo = cinfo;

  /* Emit restart marker if needed */
  if (cinfo->restart_interval) {
    if (entropy->restarts_to_go == 0)
      if (! emit_restart(&state, entropy->next_restart_num))
	return FALSE;
  }

  /* Encode the MCU data blocks */
  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
    ci = cinfo->MCU_membership[blkn];
    compptr = cinfo->cur_comp_info[ci];
    if (! encode_one_block(&state,
			   MCU_data[blkn][0], state.cur.last_dc_val[ci],
			   entropy->dc_derived_tbls[compptr->dc_tbl_no],
			   entropy->ac_derived_tbls[compptr->ac_tbl_no]))
      return FALSE;
    /* Update last_dc_val */
    state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
  }

  /* Completed MCU, so update state */
  cinfo->dest->next_output_byte = state.next_output_byte;
  cinfo->dest->free_in_buffer = state.free_in_buffer;
  ASSIGN_STATE(entropy->saved, state.cur);

  /* Update restart-interval state too */
  if (cinfo->restart_interval) {
    if (entropy->restarts_to_go == 0) {
      entropy->restarts_to_go = cinfo->restart_interval;
      entropy->next_restart_num++;
      entropy->next_restart_num &= 7;
    }
    entropy->restarts_to_go--;
  }

  return TRUE;
}


/*
 * Finish up at the end of a Huffman-compressed scan.
 */

METHODDEF(void)
finish_pass_huff (j_compress_ptr cinfo)
{
  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
  working_state state;

  /* Load up working state ... flush_bits needs it */
  state.next_output_byte = cinfo->dest->next_output_byte;
  state.free_in_buffer = cinfo->dest->free_in_buffer;
  ASSIGN_STATE(state.cur, entropy->saved);
  state.cinfo = cinfo;

  /* Flush out the last data */
  if (! flush_bits(&state))
    ERREXIT(cinfo, JERR_CANT_SUSPEND);

  /* Update state */
  cinfo->dest->next_output_byte = state.next_output_byte;
  cinfo->dest->free_in_buffer = state.free_in_buffer;
  ASSIGN_STATE(entropy->saved, state.cur);
}


/*
 * Huffman coding optimization.
 *
 * We first scan the supplied data and count the number of uses of each symbol
 * that is to be Huffman-coded. (This process MUST agree with the code above.)
 * Then we build a Huffman coding tree for the observed counts.
 * Symbols which are not needed at all for the particular image are not
 * assigned any code, which saves space in the DHT marker as well as in
 * the compressed data.
 */

#ifdef ENTROPY_OPT_SUPPORTED


/* Process a single block's worth of coefficients */

LOCAL(void)
htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val,
		 long dc_counts[], long ac_counts[])
{
  extern boolean lossless_codec;
  register int temp;
  register int nbits;
  register int k, r;

  /************************************************************/
  /* Encode the DC coefficient difference per section F.1.2.1 */
  /************************************************************/

  temp = block[0] - last_dc_val;
  if (temp < 0)
    temp = -temp;
  
  /* Find the number of bits needed for the magnitude of the coefficient */
  nbits = 0;
  while (temp) {
    nbits++;
    temp >>= 1;