jcarith.c

JPEG压缩和解压程序和一些相关的说明文档 内容比较全

/* This programe is reedited by Fujian Shi([e-mail])
 *from the code programmed by  Guido Vollbeding <[e-mail]>.
 * jcarith.c
 *
 * It can only acomplesh simple arithmetic coding.
 */

#include "commondecls.h"


#define RIGHT_SHIFT(x,shft) x>=0 ? x>>shft : -((-x)>>shft)

/* We use a compact representation with 1 byte per statistics bin,
 * thus the numbers directly represent byte sizes.
 * This 1 byte per statistics bin contains the meaning of the MPS
 * (more probable symbol) in the highest bit (mask 0x80), and the
 * index into the probability estimation state machine table
 * in the lower bits (mask 0x7F).
 */



/* NOTE: Uncomment the following #define if you want to use the
 * given formula for calculating the AC conditioning parameter Kx
 * for spectral selection progressive coding in section G.1.3.2
 * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
 * Although the spec and P&M authors claim that this "has proven
 * to give good results for 8 bit precision samples", I'm not
 * convinced yet that this is really beneficial.
 * Early tests gave only very marginal compression enhancements
 * (a few - around 5 or so - bytes even for very large files),
 * which would turn out rather negative if we'd suppress the
 * DAC (Define Arithmetic Conditioning) marker segments for
 * the default parameters in the future.
 * Note that currently the marker writing module emits 12-byte
 * DAC segments for a full-component scan in a color image.
 * This is not worth worrying about IMHO. However, since the
 * spec defines the default values to be used if the tables
 * are omitted (unlike Huffman tables, which are required
 * anyway), one might optimize this behaviour in the future,
 * and then it would be disadvantageous to use custom tables if
 * they don't provide sufficient gain to exceed the DAC size.
 *
 * On the other hand, I'd consider it as a reasonable result
 * that the conditioning has no significant influence on the
 * compression performance. This means that the basic
 * statistical model is already rather stable.
 *
 * Thus, at the moment, we use the default conditioning values
 * anyway, and do not use the custom formula.
 *
 * IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
 * We assume that int right shift is unsigned if INT32 right shift is,
 * which should be safe.
 */





/*
 * Finish up at the end of an arithmetic-compressed scan.
 */

void
flush_bits (j_compress_ptr cinfo)
{
  arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
  INT32 temp;

  /* Section D.1.8: Termination of encoding */

  /* Find the e->c in the coding interval with the largest
   * number of trailing zero bits */
  if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c)
    e->c = temp + 0x8000L;
  else
    e->c = temp;
  /* Send remaining bytes to output */
  e->c <<= e->ct;
  if (e->c & 0xF8000000L) {
    /* One final overflow has to be handled */
    if (e->buffer >= 0) {
      if (e->zc)
	do emit_byte(cinfo,0x00);
	while (--e->zc);
      emit_byte(cinfo,e->buffer + 1);
      if (e->buffer + 1 == 0xFF)
	emit_byte(cinfo,0x00);
    }
    e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
    e->sc = 0;
  } else {
    if (e->buffer == 0)
      ++e->zc;
    else if (e->buffer >= 0) {
      if (e->zc)
	do emit_byte(cinfo,0x00);
	while (--e->zc);
      emit_byte(cinfo,e->buffer);
    }
    if (e->sc) {
      if (e->zc)
	do emit_byte(cinfo,0x00);
	while (--e->zc);
      do {
	emit_byte(cinfo,0xFF);
	emit_byte(cinfo,0x00);
      } while (--e->sc);
    }
  }
  /* Output final bytes only if they are not 0x00 */
  if (e->c & 0x7FFF800L) {
    if (e->zc)  /* output final pending zero bytes */
      do emit_byte(cinfo,0x00);
      while (--e->zc);
    emit_byte(cinfo,(e->c >> 19) & 0xFF);
    if (((e->c >> 19) & 0xFF) == 0xFF)
      emit_byte(cinfo,0x00);
    if (e->c & 0x7F800L) {
      emit_byte(cinfo,(e->c >> 11) & 0xFF);
      if (((e->c >> 11) & 0xFF) == 0xFF)
	emit_byte(cinfo,0x00);
    }
  }
}


/*
 * The core arithmetic encoding routine (common in JPEG and JBIG).
 * This needs to go as fast as possible.
 * Machine-dependent optimization facilities
 * are not utilized in this portable implementation.
 * However, this code should be fairly efficient and
 * may be a good base for further optimizations anyway.
 *
 * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
 *
 * Note: I've added full "Pacman" termination support to the
 * byte output routines, which is equivalent to the optional
 * Discard_final_zeros procedure (Figure D.15) in the spec.
 * Thus, we always produce the shortest possible output
 * stream compliant to the spec (no trailing zero bytes,
 * except for FF stuffing).
 *
 * I've also introduced a new scheme for accessing
 * the probability estimation state machine table,
 * derived from Markus Kuhn's JBIG implementation.
 */

void
arith_encode (j_compress_ptr cinfo, unsigned char *st, int val) 
{
  extern const INT32 jaritab[];
  register arith_entropy_ptr e = cinfo->entropy;
  register unsigned char nl, nm;
  register INT32 qe, temp;
  register int sv;

  /* Fetch values from our compact representation of Table D.2:
   * Qe values and probability estimation state machine
   */
  sv = *st;
  qe = jaritab[sv & 0x7F];	/* => Qe_Value */
  nl = qe & 0xFF; qe >>= 8;	/* Next_Index_LPS + Switch_MPS */
  nm = qe & 0xFF; qe >>= 8;	/* Next_Index_MPS */

  /* Encode & estimation procedures per sections D.1.4 & D.1.5 */
  e->a -= qe;
  if (val != ((sv >> 7) & (0x00000001))) {
    /* Encode the less probable symbol */
    if (e->a >= qe) {
      /* If the interval size (qe) for the less probable symbol (LPS)
       * is larger than the interval size for the MPS, then exchange
       * the two symbols for coding efficiency, otherwise code the LPS
       * as usual: */
      e->c += e->a;
      e->a = qe;
    }
    *st = (sv & 0x80) ^ nl;	/* Estimate_after_LPS */
  } else {
    /* Encode the more probable symbol */
    if (e->a >= 0x8000L)
      return;  /* A >= 0x8000 -> ready, no renormalization required */
    if (e->a < qe) {
      /* If the interval size (qe) for the less probable symbol (LPS)
       * is larger than the interval size for the MPS, then exchange
       * the two symbols for coding efficiency: ,it is equal to code 
       * the LPS.*/
      e->c += e->a;
      e->a = qe;
    }
    *st = (sv & 0x80) ^ nm ;	/* Estimate_after_MPS ,no change of the sense of the MPS*/
  }

  /* Renormalization & data output per section D.1.6 */
  do {
    e->a <<= 1;
    e->c <<= 1;
    if (--e->ct == 0) {
      /* The followning is the byte_out programe.*/
      /* Another byte is ready for output */
      temp = e->c >> 19;
      if (temp > 0xFF) {
	/*Handle overflow over all stacked 0xFF bytes */
	if (e->buffer >= 0) {
	  
	   emit_byte(cinfo,e->buffer + 1);
	  if (e->buffer + 1 == 0xFF)
	  emit_byte(cinfo,0x00); 
	}
	/*e->zc += e->sc;*/  /* carry-over converts stacked 0xFF bytes to 0x00 and output them*/
	while(e->sc-->0)
	  emit_byte(cinfo,0X00);
	e->sc = 0;
	/* Note: The 3 spacer bits in the C register guarantee
	 * that the new buffer byte can't be 0xFF here
	 * (see page 160 in the P&M JPEG book). */
	e->buffer = temp & 0xFF;  /* new output byte, might overflow later */
      } else if (temp == 0xFF) {
	++e->sc;  /* stack 0xFF byte (which might overflow later) */
      } else {
	/* Output all stacked 0xFF bytes, they will not overflow any more */
	
         if (e->buffer >= 0) {
           emit_byte(cinfo,e->buffer);
	   if (e->sc) {
	     while (e->sc--) {
	       emit_byte(cinfo,0xFF);
	       emit_byte(cinfo,0x00);
	     } 
	    e->sc=0;
	    }
	   
        } 
        e->buffer = temp & 0xFF;  /* new output byte (can still overflow) */
      }
      e->c &= 0x7FFFFL;
      e->ct = 8;
    }
  } while (e->a < 0x8000L);
  
}

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

void
encode_row (j_compress_ptr cinfo,JSAMPROW row,int i)
{
  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
  unsigned char * st;
  unsigned char context_a=0;
  int num,ci, tbl, k, ke;
  int v, v2, m,last_val=0,Rc=0,predic_val;


  entropy->context=0;
  /* Encode the MCU data blocks */
  for (num = 0; num < cinfo->image_width; num++) {
    
    /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */


    /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
    st =entropy->dc_stats + entropy->context*5+entropy->context_b[num];

    /*predic_val=last_val+((entropy->val_b[num]-Rc)>>1);*/
    /*predic_val=RIGHT_SHIFT(last_val+entropy->val_b[num],1);*/
    v=get_errval(cinfo,last_val,entropy->val_b[num],Rc,entropy->val_b[num+1],row+num);
    /* if (i==0)
       printf("row[%d]:%x  v=%d\n",num,row[num],v);*/
    /*v=row[num]-predic_val;*/
    /* Figure F.4: Encode_DC_DIFF */
    if ((v ) == 0) {
      arith_encode(cinfo, st, 0);
      entropy->context = 0;	                /* zero diff category */
      
    } else {
      
      arith_encode(cinfo, st, 1);
      /* Figure F.6: Encoding nonzero value v */
      /* Figure F.7: Encoding the sign of v */
      if (v > 0) {
	st +=1;
	arith_encode(cinfo, st, 0);	/* Table F.4: SS = S0 + 1 */
	st += 1;			/* Table F.4: SP = S0 + 2 */
	entropy->context = 4;	                /* small positive diff category */
      } else {
	st +=1;
	v = -v;
	arith_encode(cinfo, st, 1);	/* Table F.4: SS = S0 + 1 */
	st += 2;			/* Table F.4: SN = S0 + 3 */
	entropy->context = 8;	                /* small negative diff category */
      }
      /* Figure F.8: Encoding the magnitude category of v */
      m = 0;
      if (v -= 1) {
        arith_encode(cinfo, st, 1);
        m = 1;
        v2 = v;
        if ( entropy->context_b[num]>8 )
	  st=entropy->dc_stats+129;
	else
	  st = entropy->dc_stats + 100; /* Table H.3: X1 = X1_context(Db)*/
	    /*st=entropy->dc_stats+20;*/
	 while (v2 >>= 1) {
	   arith_encode(cinfo, st, 1);
	   m <<= 1;
	   st += 1;
	}
      }
      arith_encode(cinfo, st, 0);
      
      /* v -=1;
       *m=1;
       *if (v>m){
       *arith_encode(cinfo,st,1);
       *if ( entropy->context_b[num]>8 )
       *  st=entropy->dc_stats+129;
       * else
       *  st = entropy->dc_stats + 100; * Table H.3: X1 = X1_context(Db)*
       *m=2;
       * while (v>=m){
	*  arith_encode (cinfo,st,1);
	 * m <<=1;
	  *st +=1;
	*}
      *}
      *arith_encode (cinfo,st,0);*/
      
      /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
      if ((m) < (int) (((INT32) 1 << cinfo->arith_dc_L) >> 1))
	entropy->context = 0;	        /* zero diff category */
      else if ((m) > (int) (((INT32) 1 << cinfo->arith_dc_U)>>1 ))
	entropy->context += 8;	        /* large diff category */
      /* Figure F.9: Encoding the magnitude bit pattern of v */
      st += 14;
      while (m >>= 1)
	arith_encode(cinfo, st, (m & v) ? 1 : 0);
    }
    entropy->context_b[num]=entropy->context;
    Rc=entropy->val_b[num];
    last_val=entropy->val_b[num]=row[num];
  }
    
}