/*
 * jchuff.c
 *
 * Copyright (C) 1991, 1992, Thomas G. Lane.
 * This file is part of the Independent JPEG Group's software.
 * For conditions of distribution and use, see the accompanying README file.
 *
 * This file contains Huffman entropy encoding routines.
 * These routines are invoked via the methods entropy_encode,
 * entropy_encode_init/term, and entropy_optimize.
 */

/* Changes were made to this program by eliminating the error messages,
   because the SWDS does not suppot direct file i/o.  Christopher Chang
   Summer 1993.
*/

#include "jinclude.h"


/* Static variables to avoid passing 'round extra parameters */

static compress_info_ptr cinfo;

static INT32 huff_put_buffer;   /* current bit-accumulation buffer */
static int huff_put_bits;   /* # of bits now in it */

static char * output_buffer;    /* output buffer */
static int bytes_in_buffer;



LOCAL void
fix_huff_tbl (HUFF_TBL * htbl)
/* Compute derived values for a Huffman table */
{
  int p, i, l, lastp, si;
  char huffsize[257];
  UINT16 huffcode[257];
  UINT16 code;
  
  /* Figure C.1: make table of Huffman code length for each symbol */
  /* Note that this is in code-length order. */

  p = 0;
  for (l = 1; l <= 16; l++) {
	for (i = 1; i <= (int) htbl->bits[l]; i++)
	  huffsize[p++] = (char) l;
  }
  huffsize[p] = 0;
  lastp = p;
  
  /* Figure C.2: generate the codes themselves */
  /* Note that this is in code-length order. */
  
  code = 0;
  si = huffsize[0];
  p = 0;
  while (huffsize[p]) {
	while (((int) huffsize[p]) == si) {
	  huffcode[p++] = code;
	  code++;
	}
	code <<= 1;
	si++;
  }
  
  /* Figure C.3: generate encoding tables */
  /* These are code and size indexed by symbol value */

  /* Set any codeless symbols to have code length 0;
   * this allows emit_bits to detect any attempt to emit such symbols.
   */
  MEMZERO(htbl->ehufsi, SIZEOF(htbl->ehufsi));

  for (p = 0; p < lastp; p++) {
	htbl->ehufco[htbl->huffval[p]] = huffcode[p];
	htbl->ehufsi[htbl->huffval[p]] = huffsize[p];
  }
  
  /* We don't bother to fill in the decoding tables mincode[], maxcode[], */
  /* and valptr[], since they are not used for encoding. */
}


/* Outputting bytes to the file */

LOCAL void
flush_bytes (void)
{
  if (bytes_in_buffer)
	(*cinfo->methods->entropy_output) (cinfo, output_buffer, bytes_in_buffer);
  bytes_in_buffer = 0;
}


#define emit_byte(val)  \
  MAKESTMT( if (bytes_in_buffer >= JPEG_BUF_SIZE) \
		  flush_bytes(); \
		output_buffer[bytes_in_buffer++] = (char) (val); )



/* Outputting bits to the file */

/* Only the right 24 bits of huff_put_buffer are used; the valid bits are
 * left-justified in this part.  At most 16 bits can be passed to emit_bits
 * in one call, and we never retain more than 7 bits in huff_put_buffer
 * between calls, so 24 bits are sufficient.
 */

INLINE
LOCAL void
emit_bits (UINT16 code, int size)
{
  /* This routine is heavily used, so it's worth coding tightly. */
  register INT32 put_buffer = code;
  register int put_bits = huff_put_bits;

  /* if size is 0, caller used an invalid Huffman table entry */

/*************************DID NOT SUPPORT THIS ERROR**********************  
  if (size == 0)                       
	ERREXIT(cinfo->emethods);
		(cinfo->emethods, "Missing Huffman code table entry");
**************************************************************************/
																		 
  put_buffer &= (((INT32) 1) << size) - 1; /* Mask off any excess bits in code */
  
  put_bits += size;     /* new number of bits in buffer */
  
  put_buffer <<= 24 - put_bits; /* align incoming bits */

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

  huff_put_buffer = put_buffer; /* Update global variables */
  huff_put_bits = put_bits;
}


LOCAL void
flush_bits (void)
{
  emit_bits((UINT16) 0x7F, 7);  /* fill any partial byte with ones */
  huff_put_buffer = 0;      /* and reset bit-buffer to empty */
  huff_put_bits = 0;
}



/* Encode a single block's worth of coefficients */
/* Note that the DC coefficient has already been converted to a difference */

LOCAL void
encode_one_block (JBLOCK block, HUFF_TBL *dctbl, HUFF_TBL *actbl)
{
  register int temp, temp2;
  register int nbits;
  register int k, r, i;
  
  /* Encode the DC coefficient difference per section F.1.2.1 */
  
  temp = temp2 = block[0];

  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;
  }
  
  /* Emit the Huffman-coded symbol for the number of bits */
  emit_bits(dctbl->ehufco[nbits], dctbl->ehufsi[nbits]);

  /* 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 */
	emit_bits((UINT16) temp2, nbits);
  
  /* 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[k]) == 0) {
	  r++;
	} else {
	  /* if run length > 15, must emit special run-length-16 codes (0xF0) */
	  while (r > 15) {
	emit_bits(actbl->ehufco[0xF0], actbl->ehufsi[0xF0]);
	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++;
	  
	  /* Emit Huffman symbol for run length / number of bits */
	  i = (r << 4) + nbits;
	  emit_bits(actbl->ehufco[i], actbl->ehufsi[i]);
	  
	  /* Emit that number of bits of the value, if positive, */
	  /* or the complement of its magnitude, if negative. */
	  emit_bits((UINT16) temp2, nbits);
	  
	  r = 0;
	}
  }

  /* If the last coef(s) were zero, emit an end-of-block code */
  if (r > 0)
	emit_bits(actbl->ehufco[0], actbl->ehufsi[0]);
}



/*
 * Initialize for a Huffman-compressed scan.
 * This is invoked after writing the SOS marker.
 * The pipeline controller must establish the entropy_output method pointer
 * before calling this routine.
 */

METHODDEF void
huff_init (compress_info_ptr xinfo)
{
  short ci;
  jpeg_component_info * compptr;

  /* Initialize static variables */
  cinfo = xinfo;
  huff_put_buffer = 0;
  huff_put_bits = 0;

  /* Initialize the output buffer */
  output_buffer = (char *) (*cinfo->emethods->alloc_small)
				((size_t) JPEG_BUF_SIZE);
  bytes_in_buffer = 0;

  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
	compptr = cinfo->cur_comp_info[ci];
	/* Make sure requested tables are present */

/*******************DID NOT SUPPORT THIS ERROR MESSAGE********************
if (cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no] == NULL ||
	cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no] == NULL)
	ERREXIT(cinfo->emethods);  
***************************************************************************/      

	  /*(cinfo->emethods, "Use of undefined Huffman table");*/
	/* Compute derived values for Huffman tables */
	/* We may do this more than once for same table, but it's not a big deal */
	fix_huff_tbl(cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no]);
	fix_huff_tbl(cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
	/* Initialize DC predictions to 0 */
	cinfo->last_dc_val[ci] = 0;
  }

  /* Initialize restart stuff */
  cinfo->restarts_to_go = cinfo->restart_interval;
  cinfo->next_restart_num = 0;
}


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

LOCAL void
emit_restart (compress_info_ptr cinfo)
{
  short ci;

  flush_bits();

  emit_byte(0xFF);
  emit_byte(RST0 + cinfo->next_restart_num);

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

  /* Update restart state */
  cinfo->restarts_to_go = cinfo->restart_interval;
  cinfo->next_restart_num++;
  cinfo->next_restart_num &= 7;
}


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

METHODDEF void
huff_encode (compress_info_ptr cinfo, JBLOCK *MCU_data)
{
  short blkn, ci;
  jpeg_component_info * compptr;
  JCOEF temp;

  /* Account for restart interval, emit restart marker if needed */
  if (cinfo->restart_interval) {
	if (cinfo->restarts_to_go == 0)
	  emit_restart(cinfo);
	cinfo->restarts_to_go--;
  }

  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
	ci = cinfo->MCU_membership[blkn];
	compptr = cinfo->cur_comp_info[ci];
	/* Convert DC value to difference, update last_dc_val */
	temp = MCU_data[blkn][0];
	MCU_data[blkn][0] -= cinfo->last_dc_val[ci];
	cinfo->last_dc_val[ci] = temp;
	encode_one_block(MCU_data[blkn],
			 cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no],
			 cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  }
}


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

METHODDEF void
huff_term (compress_info_ptr cinfo)
{
  /* Flush out the last data */
  flush_bits();
  flush_bytes();
  /* Release the I/O buffer */
  (*cinfo->emethods->free_small) ((void *) output_buffer);
}