huffc.c

来自「很好的JPEG图象解码器,基于VC环境开发。」· C语言 代码 · 共 1,551 行 · 第 1/3 页

 *
 * HuffEncoderTerm --
 *
 *	Finish up at the end of a Huffman-compressed scan.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Any remaing bits are flushed.
 *
 *--------------------------------------------------------------
 */
void 
HuffEncoderTerm ()
{
    /*
     * Flush out the last data
     */
    FlushBits ();
    FlushBytes ();
}

/*
 *--------------------------------------------------------------
 *
 * Huffman coding optimization.
 *
 * This actually is optimization, in the sense that we find the
 * best possible Huffman table(s) for the given data. We first
 * scan the supplied data and count the number of uses of each
 * category symbol that is to be Huffman-coded. (This process 
 * must agree with the code above.)  Then we build an optimal
 * Huffman coding tree for the observed counts.
 *
 *--------------------------------------------------------------
 */

/*
 *--------------------------------------------------------------
 *
 * GenHuffCoding --
 *
 * 	Generate the optimal coding for the given counts. 
 *	This algorithm is explained in section K.2 of the
 *	JPEG standard. 
 *
 * Results:
 *      htbl->bits and htbl->huffval are costructed.
 *
 * Side effects:
 *      None.
 *
 *--------------------------------------------------------------
 */
void
GenHuffCoding (htbl, freq)
  HuffmanTable *htbl;
  long freq[];
{
#define MAX_CLEN 32     	/* assumed maximum initial code length */
  Uchar bits[MAX_CLEN+1];	/* bits[k] = # of symbols with code length k */
  short codesize[257];		/* codesize[k] = code length of symbol k */
  short others[257];		/* next symbol in current branch of tree */
  int c1, c2;
  int p, i, j;
  long v;

  MEMSET((void *)(bits), 0, sizeof(bits));
  MEMSET((void *)(codesize), 0, sizeof(codesize));
  for (i = 0; i < 257; i++)
      others[i] = -1;		/* init links to empty */

  /* 
   * Including the pseudo-symbol 256 in the Huffman procedure guarantees
   * that no real symbol is given code-value of all ones, because 256
   * will be placed in the largest codeword category.
   */
  freq[256] = 1;		/* make sure there is a nonzero count */

  /*
   * Huffman's basic algorithm to assign optimal code lengths to symbols 
   */
  for (;;) {

    /*
     * Find the smallest nonzero frequency, set c1 = its symbol.
     * In case of ties, take the larger symbol number.
     */
    c1 = -1;
    v = 1000000000L;
    for (i = 0; i <= 256; i++) {
      if (freq[i] && freq[i] <= v) {
	v = freq[i];
	c1 = i;
      }
    }

    /*
     * Find the next smallest nonzero frequency, set c2 = its symbol.
     * In case of ties, take the larger symbol number.
     */
    c2 = -1;
    v = 1000000000L;
    for (i = 0; i <= 256; i++) {
      if (freq[i] && freq[i] <= v && i != c1) {
	v = freq[i];
	c2 = i;
      }
    }

    /*
     * Done if we've merged everything into one frequency.
     */
    if (c2 < 0)
      break;
    
    /*
     * Else merge the two counts/trees.
     */
    freq[c1] += freq[c2];
    freq[c2] = 0;

    /*
     * Increment the codesize of everything in c1's tree branch.
     */
    codesize[c1]++;
    while (others[c1] >= 0) {
      c1 = others[c1];
      codesize[c1]++;
    }
    
    /*
     * chain c2 onto c1's tree branch 
     */
    others[c1] = c2;
    
    /*
     * Increment the codesize of everything in c2's tree branch.
     */
    codesize[c2]++;
    while (others[c2] >= 0) {
          c2 = others[c2];
          codesize[c2]++;
    }
  }

  /*
   * Now count the number of symbols of each code length.
   */
  for (i = 0; i <= 256; i++) {
    if (codesize[i]) {

      /*
       * The JPEG standard seems to think that this can't happen,
       * but I'm paranoid...
       */
      if (codesize[i] > MAX_CLEN) {
	fprintf(stderr, "Huffman code size table overflow: codesize[%d]=%d\n",
                i,codesize[i]);
        exit(-1);
      }

      bits[codesize[i]]++;
    }
  }

  /* 
   * JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
   * Huffman procedure assigned any such lengths, we must adjust the coding.
   * Here is what the JPEG spec says about how this next bit works:
   * Since symbols are paired for the longest Huffman code, the symbols are
   * removed from this length category two at a time.  The prefix for the pair
   * (which is one bit shorter) is allocated to one of the pair; then,
   * skipping the BITS entry for that prefix length, a code word from the next
   * shortest nonzero BITS entry is converted into a prefix for two code words
   * one bit longer.
   */
  
  for (i = MAX_CLEN; i > 16; i--) {
    while (bits[i] > 0) {
      j = i - 2;		/* find length of new prefix to be used */
      while (bits[j] == 0)
	j--;
      
      bits[i] -= 2;		/* remove two symbols */
      bits[i-1]++;		/* one goes in this length */
      bits[j+1] += 2;		/* two new symbols in this length */
      bits[j]--;		/* symbol of this length is now a prefix */
    }
  }

  /*
   * Remove the count for the pseudo-symbol 256 from
   * the largest codelength.
   */
  while (bits[i] == 0)		/* find largest codelength still in use */
    i--;
  bits[i]--;
  
  /*
   * Return final symbol counts (only for lengths 0..16).
   */
  MEMCPY((htbl->bits),(bits),sizeof(htbl->bits));
  
  /*
   * Return a list of the symbols sorted by code length. 
   * It's not real clear to me why we don't need to consider the codelength
   * changes made above, but the JPEG spec seems to think this works.
   */
  p = 0;
  for (i = 1; i <= MAX_CLEN; i++) {
    for (j = 0; j <= 255; j++) {
      if (codesize[j] == i) {
	htbl->huffval[p] = (Uchar) j;
	p++;
      }
    }
  }
}

/*
 *--------------------------------------------------------------
 *
 * AllPredCountOneDiff --
 *
 *      Count this difference value in all 7 frequency counting 
 *	tables. This function is called when processing the first
 *      row and first column of the image. Pixels in the first row
 *	always use the left neighbors or (1<Pr-Pt-1) as predictors;  
 *      and pixels in the first column always use the upper neighbors.
 *      So, these pixels's difference values are the same for all 
 *	seven PSVs. Thus, we compute this value once and count it
 *	for all PSVs.  
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      value is counted in all global counting tables,
 *	i.e. freqCountPtrs.
 *
 *--------------------------------------------------------------
 */
void
AllPredCountOneDiff(value,tblNo)
     int value;
     int tblNo;
{
    register int temp, temp2;
    register short nbits,i;

    /*
     * Encode the DC coefficient difference per section F.1.2.1
     */
    temp = temp2 = value;
    if (temp < 0) {
        temp = -temp;
        /*
         * 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;
    if (temp) {
        while (temp >= 256) {
            nbits += 8;
            temp >>= 8;
        }
        nbits += numBitsTable[temp&0xff];
    }

    freqCountPtrs[0][tblNo][nbits]++;
    freqCountPtrs[1][tblNo][nbits]++;
    freqCountPtrs[2][tblNo][nbits]++;
    freqCountPtrs[3][tblNo][nbits]++;
    freqCountPtrs[4][tblNo][nbits]++;
    freqCountPtrs[5][tblNo][nbits]++;
    freqCountPtrs[6][tblNo][nbits]++;
}

#ifdef DEBUG

/*
 *--------------------------------------------------------------
 *
 * CountOneDiff --
 *
 *      Count the difference value in countTable.
 *
 * Results:
 *      diff is counted in countTable.
 *
 * Side effects:
 *      None. 
 *
 *--------------------------------------------------------------
 */
void
CountOneDiff(diff, countTable)
     int diff;
     long countTable[];
{
    register int temp, temp2;
    register short nbits;

    /*
     * Encode the DC coefficient difference per section F.1.2.1
     */
    temp = temp2 = diff;
    if (temp < 0) {
        temp = -temp;
        /*
         * 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;
    if (temp) {
        while (temp >= 256) {
            nbits += 8;
            temp >>= 8;
        }
        nbits += numBitsTable[temp&0xff];
    }
    countTable[nbits]++;
}

/*
 *--------------------------------------------------------------
 *
 * AllPredCountOneComp --
 *
 *      The sample, curRowBuf[col][curComp], is counted in the
 *	frequency counting tables, freqCountPts, of the 7 PSVs.        
 *
 * Results:
 *      None.
 *
 * Side effects:
 *	curRowBuf[col][curComp] is counted in freqCountPtrs[i][tblNo]
 *	for i=0 to 6. 
 *
 *--------------------------------------------------------------
 */
void
AllPredCountOneComp(col,curComp,tblNo,curRowBuf,prevRowBuf)
    int col,curComp,tblNo;
    MCU *curRowBuf,*prevRowBuf;
{
    register int left,upper,diag,leftcol,r,curValue;

    leftcol=col-1;
    upper=prevRowBuf[col][curComp];
    left=curRowBuf[leftcol][curComp];
    diag=prevRowBuf[leftcol][curComp];
    curValue=curRowBuf[col][curComp];
    /* predictor 1 */
    r = curValue - left;
    CountOneDiff(r,freqCountPtrs[0][tblNo]);

    /* predictor 2 */
    r = curValue - upper;
    CountOneDiff(r,freqCountPtrs[1][tblNo]);

    /* predictor 3 */
    r = curValue - diag;
    CountOneDiff(r,freqCountPtrs[2][tblNo]);

    /* predictor 4 */
    r = curValue - (left+upper-diag);
    CountOneDiff(r,freqCountPtrs[3][tblNo]);

    /* predictor 5 */
    r = curValue - (left+((upper-diag)>>1));
    CountOneDiff(r,freqCountPtrs[4][tblNo]);

    /* predictor 6 */
    r = curValue - (upper+((left-diag)>>1));
    CountOneDiff(r,freqCountPtrs[5][tblNo]);

    /* predictor 7 */
    r = curValue - ((left+upper)>>1);
    CountOneDiff(r,freqCountPtrs[6][tblNo]);
}

#else /* DEBUG */

/*
 *--------------------------------------------------------------
 *
 * CountOneDiff (macro) --
 *
 *      Count the difference value in countTable.
 *
 * Results:
 *      diff is counted in countTable.
 *
 * Side effects:
 *      None. 
 *
 *--------------------------------------------------------------
 */
#define CountOneDiff(diff, countTable){				\
    register int temp, temp2;					\
    register short nbits;					\
								\
    temp = temp2 = diff;					\
    if (temp < 0) {						\
        temp = -temp;						\
        temp2--;						\
    }								\
								\
    nbits=0;							\
    if (temp) {							\
        while (temp >= 256) {					\
            nbits += 8;						\
            temp >>= 8;						\
        }							\
        nbits += numBitsTable[temp&0xff];			\
    }								\
    countTable[nbits]++;					\
}

/*
 *--------------------------------------------------------------
 *
 * AllPredCountOneComp (macro) --
 *
 *      The sample, curRowBuf[col][curComp], is counted in the
 *	frequency counting tables, freqCountPts, of the 7 PSVs.        
 *
 * Results:
 *      None.
 *
 * Side effects:
 *	curRowBuf[col][curComp] is counted in freqCountPtrs[i][tblNo]
 *	for i=0 to 6. 
 *
 *--------------------------------------------------------------
 */
#define AllPredCountOneComp(col,curComp,tblNo,curRowBuf,prevRowBuf) {	\
    register int left,upper,diag,leftcol,r,curValue;			\
									\
    leftcol=col-1;							\
    upper=prevRowBuf[col][curComp];					\
    left=curRowBuf[leftcol][curComp];					\
    diag=prevRowBuf[leftcol][curComp];					\
    curValue=curRowBuf[col][curComp];					\
    /* predictor 1 */							\
    r = curValue - left;						\
    CountOneDiff(r,freqCountPtrs[0][tblNo]);				\
    /* predictor 2 */							\
    r = curValue - upper;						\
    CountOneDiff(r,freqCountPtrs[1][tblNo]);				\
    /* predictor 3 */							\
    r = curValue - diag;						\
    CountOneDiff(r,freqCountPtrs[2][tblNo]);				\
    /* predictor 4 */							\
    r = curValue - (left+upper-diag);					\
    CountOneDiff(r,freqCountPtrs[3][tblNo]);				\
    /* predictor 5 */							\
    r = curValue - (left+((upper-diag)>>1));				\
    CountOneDiff(r,freqCountPtrs[4][tblNo]);				\
    /* predictor 6 */							\
    r = curValue - (upper+((left-diag)>>1));				\
    CountOneDiff(r,freqCountPtrs[5][tblNo]);				\
    /* predictor 7 */							\
    r = curValue - ((left+upper)>>1);					\
    CountOneDiff(r,freqCountPtrs[6][tblNo]);				\
}

#endif /*else DEBUG*/

/*
 *--------------------------------------------------------------
 *
 * FreqCountSelValueSet --
 *
 *      Count the times each category symbol occurs in this
 *	image for each PSV in the psvSet.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The freqCountPtrs[i] has counted all category 
 *	symbols appeared in the image, where i is a
 *      element in psvSet.        
 *
 *--------------------------------------------------------------
 */
void 
FreqCountSelValueSet(cPtr)
    CompressInfo * cPtr;
{
    register short curComp,ci,tblNo ;
    register int col,row;
    register JpegComponentInfo *compptr;
    register int r,i,curCountTblNo;
    int numCOL,numROW,compsInScan;
    int Pr,Pt,Ss;
    int predictor;
    MCU *prevRowBuf,*curRowBuf;