huffman.cpp

《Visual C++视频/音频开发实用工程案例精选》一书的源代码

	{2,1},{0,127},{0,233},{8,1},{4,1},{2,1},{0,158},{0,204},{2,1},{0,248},
	{0,143},{4,1},{2,1},{0,219},{0,189},{2,1},{0,234},{0,249},{16,1},{8,1},
	{4,1},{2,1},{0,159},{0,220},{2,1},{0,205},{0,235},{4,1},{2,1},{0,190},
	{0,250},{2,1},{0,175},{0,221},{14,1},{6,1},{4,1},{2,1},{0,236},{0,206},
	{0,251},{4,1},{2,1},{0,191},{0,237},{2,1},{0,222},{0,252},{6,1},{4,1},
	{2,1},{0,207},{0,253},{0,238},{4,1},{2,1},{0,223},{0,254},{2,1},{0,239},
	{0,255},
};
unsigned char ValTab16[511][2] = {
	{2,1},{0,0},{6,1},{2,1},{0,16},{2,1},{0,1},{0,17},{42,1},{8,1},
	{4,1},{2,1},{0,32},{0,2},{2,1},{0,33},{0,18},{10,1},{6,1},{2,1},
	{0,34},{2,1},{0,48},{0,3},{2,1},{0,49},{0,19},{10,1},{4,1},{2,1},
	{0,50},{0,35},{4,1},{2,1},{0,64},{0,4},{0,65},{6,1},{2,1},{0,20},
	{2,1},{0,51},{0,66},{4,1},{2,1},{0,36},{0,80},{2,1},{0,67},{0,52},
	{138,1},{40,1},{16,1},{6,1},{4,1},{2,1},{0,5},{0,21},{0,81},{4,1},
	{2,1},{0,82},{0,37},{4,1},{2,1},{0,68},{0,53},{0,83},{10,1},{6,1},
	{4,1},{2,1},{0,96},{0,6},{0,97},{2,1},{0,22},{0,98},{8,1},{4,1},
	{2,1},{0,38},{0,84},{2,1},{0,69},{0,99},{4,1},{2,1},{0,54},{0,112},
	{0,113},{40,1},{18,1},{8,1},{2,1},{0,23},{2,1},{0,7},{2,1},{0,85},
	{0,100},{4,1},{2,1},{0,114},{0,39},{4,1},{2,1},{0,70},{0,101},{0,115},
	{10,1},{6,1},{2,1},{0,55},{2,1},{0,86},{0,8},{2,1},{0,128},{0,129},
	{6,1},{2,1},{0,24},{2,1},{0,116},{0,71},{2,1},{0,130},{2,1},{0,40},
	{0,102},{24,1},{14,1},{8,1},{4,1},{2,1},{0,131},{0,56},{2,1},{0,117},
	{0,132},{4,1},{2,1},{0,72},{0,144},{0,145},{6,1},{2,1},{0,25},{2,1},
	{0,9},{0,118},{2,1},{0,146},{0,41},{14,1},{8,1},{4,1},{2,1},{0,133},
	{0,88},{2,1},{0,147},{0,57},{4,1},{2,1},{0,160},{0,10},{0,26},{8,1},
	{2,1},{0,162},{2,1},{0,103},{2,1},{0,87},{0,73},{6,1},{2,1},{0,148},
	{2,1},{0,119},{0,134},{2,1},{0,161},{2,1},{0,104},{0,149},{220,1},{126,1},
	{50,1},{26,1},{12,1},{6,1},{2,1},{0,42},{2,1},{0,89},{0,58},{2,1},
	{0,163},{2,1},{0,135},{0,120},{8,1},{4,1},{2,1},{0,164},{0,74},{2,1},
	{0,150},{0,105},{4,1},{2,1},{0,176},{0,11},{0,177},{10,1},{4,1},{2,1},
	{0,27},{0,178},{2,1},{0,43},{2,1},{0,165},{0,90},{6,1},{2,1},{0,179},
	{2,1},{0,166},{0,106},{4,1},{2,1},{0,180},{0,75},{2,1},{0,12},{0,193},
	{30,1},{14,1},{6,1},{4,1},{2,1},{0,181},{0,194},{0,44},{4,1},{2,1},
	{0,167},{0,195},{2,1},{0,107},{0,196},{8,1},{2,1},{0,29},{4,1},{2,1},
	{0,136},{0,151},{0,59},{4,1},{2,1},{0,209},{0,210},{2,1},{0,45},{0,211},
	{18,1},{6,1},{4,1},{2,1},{0,30},{0,46},{0,226},{6,1},{4,1},{2,1},
	{0,121},{0,152},{0,192},{2,1},{0,28},{2,1},{0,137},{0,91},{14,1},{6,1},
	{2,1},{0,60},{2,1},{0,122},{0,182},{4,1},{2,1},{0,76},{0,153},{2,1},
	{0,168},{0,138},{6,1},{2,1},{0,13},{2,1},{0,197},{0,92},{4,1},{2,1},
	{0,61},{0,198},{2,1},{0,108},{0,154},{88,1},{86,1},{36,1},{16,1},{8,1},
	{4,1},{2,1},{0,139},{0,77},{2,1},{0,199},{0,124},{4,1},{2,1},{0,213},
	{0,93},{2,1},{0,224},{0,14},{8,1},{2,1},{0,227},{4,1},{2,1},{0,208},
	{0,183},{0,123},{6,1},{4,1},{2,1},{0,169},{0,184},{0,212},{2,1},{0,225},
	{2,1},{0,170},{0,185},{24,1},{10,1},{6,1},{4,1},{2,1},{0,155},{0,214},
	{0,109},{2,1},{0,62},{0,200},{6,1},{4,1},{2,1},{0,140},{0,228},{0,78},
	{4,1},{2,1},{0,215},{0,229},{2,1},{0,186},{0,171},{12,1},{4,1},{2,1},
	{0,156},{0,230},{4,1},{2,1},{0,110},{0,216},{2,1},{0,141},{0,187},{8,1},
	{4,1},{2,1},{0,231},{0,157},{2,1},{0,232},{0,142},{4,1},{2,1},{0,203},
	{0,188},{0,158},{0,241},{2,1},{0,31},{2,1},{0,15},{0,47},{66,1},{56,1},
	{2,1},{0,242},{52,1},{50,1},{20,1},{8,1},{2,1},{0,189},{2,1},{0,94},
	{2,1},{0,125},{0,201},{6,1},{2,1},{0,202},{2,1},{0,172},{0,126},{4,1},
	{2,1},{0,218},{0,173},{0,204},{10,1},{6,1},{2,1},{0,174},{2,1},{0,219},
	{0,220},{2,1},{0,205},{0,190},{6,1},{4,1},{2,1},{0,235},{0,237},{0,238},
	{6,1},{4,1},{2,1},{0,217},{0,234},{0,233},{2,1},{0,222},{4,1},{2,1},
	{0,221},{0,236},{0,206},{0,63},{0,240},{4,1},{2,1},{0,243},{0,244},{2,1},
	{0,79},{2,1},{0,245},{0,95},{10,1},{2,1},{0,255},{4,1},{2,1},{0,246},
	{0,111},{2,1},{0,247},{0,127},{12,1},{6,1},{2,1},{0,143},{2,1},{0,248},
	{0,249},{4,1},{2,1},{0,159},{0,250},{0,175},{8,1},{4,1},{2,1},{0,251},
	{0,191},{2,1},{0,252},{0,207},{4,1},{2,1},{0,253},{0,223},{2,1},{0,254},
	{0,239},
};
unsigned char ValTab24[512][2] = {
	{60,1},{8,1},{4,1},{2,1},{0,0},{0,16},{2,1},{0,1},{0,17},{14,1},
	{6,1},{4,1},{2,1},{0,32},{0,2},{0,33},{2,1},{0,18},{2,1},{0,34},
	{2,1},{0,48},{0,3},{14,1},{4,1},{2,1},{0,49},{0,19},{4,1},{2,1},
	{0,50},{0,35},{4,1},{2,1},{0,64},{0,4},{0,65},{8,1},{4,1},{2,1},
	{0,20},{0,51},{2,1},{0,66},{0,36},{6,1},{4,1},{2,1},{0,67},{0,52},
	{0,81},{6,1},{4,1},{2,1},{0,80},{0,5},{0,21},{2,1},{0,82},{0,37},
	{250,1},{98,1},{34,1},{18,1},{10,1},{4,1},{2,1},{0,68},{0,83},{2,1},
	{0,53},{2,1},{0,96},{0,6},{4,1},{2,1},{0,97},{0,22},{2,1},{0,98},
	{0,38},{8,1},{4,1},{2,1},{0,84},{0,69},{2,1},{0,99},{0,54},{4,1},
	{2,1},{0,113},{0,85},{2,1},{0,100},{0,70},{32,1},{14,1},{6,1},{2,1},
	{0,114},{2,1},{0,39},{0,55},{2,1},{0,115},{4,1},{2,1},{0,112},{0,7},
	{0,23},{10,1},{4,1},{2,1},{0,101},{0,86},{4,1},{2,1},{0,128},{0,8},
	{0,129},{4,1},{2,1},{0,116},{0,71},{2,1},{0,24},{0,130},{16,1},{8,1},
	{4,1},{2,1},{0,40},{0,102},{2,1},{0,131},{0,56},{4,1},{2,1},{0,117},
	{0,87},{2,1},{0,132},{0,72},{8,1},{4,1},{2,1},{0,145},{0,25},{2,1},
	{0,146},{0,118},{4,1},{2,1},{0,103},{0,41},{2,1},{0,133},{0,88},{92,1},
	{34,1},{16,1},{8,1},{4,1},{2,1},{0,147},{0,57},{2,1},{0,148},{0,73},
	{4,1},{2,1},{0,119},{0,134},{2,1},{0,104},{0,161},{8,1},{4,1},{2,1},
	{0,162},{0,42},{2,1},{0,149},{0,89},{4,1},{2,1},{0,163},{0,58},{2,1},
	{0,135},{2,1},{0,120},{0,74},{22,1},{12,1},{4,1},{2,1},{0,164},{0,150},
	{4,1},{2,1},{0,105},{0,177},{2,1},{0,27},{0,165},{6,1},{2,1},{0,178},
	{2,1},{0,90},{0,43},{2,1},{0,136},{0,179},{16,1},{10,1},{6,1},{2,1},
	{0,144},{2,1},{0,9},{0,160},{2,1},{0,151},{0,121},{4,1},{2,1},{0,166},
	{0,106},{0,180},{12,1},{6,1},{2,1},{0,26},{2,1},{0,10},{0,176},{2,1},
	{0,59},{2,1},{0,11},{0,192},{4,1},{2,1},{0,75},{0,193},{2,1},{0,152},
	{0,137},{67,1},{34,1},{16,1},{8,1},{4,1},{2,1},{0,28},{0,181},{2,1},
	{0,91},{0,194},{4,1},{2,1},{0,44},{0,167},{2,1},{0,122},{0,195},{10,1},
	{6,1},{2,1},{0,60},{2,1},{0,12},{0,208},{2,1},{0,182},{0,107},{4,1},
	{2,1},{0,196},{0,76},{2,1},{0,153},{0,168},{16,1},{8,1},{4,1},{2,1},
	{0,138},{0,197},{2,1},{0,92},{0,209},{4,1},{2,1},{0,183},{0,123},{2,1},
	{0,29},{0,210},{9,1},{4,1},{2,1},{0,45},{0,211},{2,1},{0,61},{0,198},
	{85,250},{4,1},{2,1},{0,108},{0,169},{2,1},{0,154},{0,212},{32,1},{16,1},
	{8,1},{4,1},{2,1},{0,184},{0,139},{2,1},{0,77},{0,199},{4,1},{2,1},
	{0,124},{0,213},{2,1},{0,93},{0,225},{8,1},{4,1},{2,1},{0,30},{0,226},
	{2,1},{0,170},{0,185},{4,1},{2,1},{0,155},{0,227},{2,1},{0,214},{0,109},
	{20,1},{10,1},{6,1},{2,1},{0,62},{2,1},{0,46},{0,78},{2,1},{0,200},
	{0,140},{4,1},{2,1},{0,228},{0,215},{4,1},{2,1},{0,125},{0,171},{0,229},
	{10,1},{4,1},{2,1},{0,186},{0,94},{2,1},{0,201},{2,1},{0,156},{0,110},
	{8,1},{2,1},{0,230},{2,1},{0,13},{2,1},{0,224},{0,14},{4,1},{2,1},
	{0,216},{0,141},{2,1},{0,187},{0,202},{74,1},{2,1},{0,255},{64,1},{58,1},
	{32,1},{16,1},{8,1},{4,1},{2,1},{0,172},{0,231},{2,1},{0,126},{0,217},
	{4,1},{2,1},{0,157},{0,232},{2,1},{0,142},{0,203},{8,1},{4,1},{2,1},
	{0,188},{0,218},{2,1},{0,173},{0,233},{4,1},{2,1},{0,158},{0,204},{2,1},
	{0,219},{0,189},{16,1},{8,1},{4,1},{2,1},{0,234},{0,174},{2,1},{0,220},
	{0,205},{4,1},{2,1},{0,235},{0,190},{2,1},{0,221},{0,236},{8,1},{4,1},
	{2,1},{0,206},{0,237},{2,1},{0,222},{0,238},{0,15},{4,1},{2,1},{0,240},
	{0,31},{0,241},{4,1},{2,1},{0,242},{0,47},{2,1},{0,243},{0,63},{18,1},
	{8,1},{4,1},{2,1},{0,244},{0,79},{2,1},{0,245},{0,95},{4,1},{2,1},
	{0,246},{0,111},{2,1},{0,247},{2,1},{0,127},{0,143},{10,1},{4,1},{2,1},
	{0,248},{0,249},{4,1},{2,1},{0,159},{0,175},{0,250},{8,1},{4,1},{2,1},
	{0,251},{0,191},{2,1},{0,252},{0,207},{4,1},{2,1},{0,253},{0,223},{2,1},
	{0,254},{0,239},
};
unsigned char ValTab32[31][2] = {
	{2,1},{0,0},{8,1},{4,1},{2,1},{0,8},{0,4},{2,1},{0,1},{0,2},
	{8,1},{4,1},{2,1},{0,12},{0,10},{2,1},{0,3},{0,6},{6,1},{2,1},
	{0,9},{2,1},{0,5},{0,7},{4,1},{2,1},{0,14},{0,13},{2,1},{0,15},
	{0,11},
};
unsigned char ValTab33[31][2] = {
	{16,1},{8,1},{4,1},{2,1},{0,0},{0,1},{2,1},{0,2},{0,3},{4,1},
	{2,1},{0,4},{0,5},{2,1},{0,6},{0,7},{8,1},{4,1},{2,1},{0,8},
	{0,9},{2,1},{0,10},{0,11},{4,1},{2,1},{0,12},{0,13},{2,1},{0,14},
	{0,15},
};

// array of all huffcodtable headers
// 0..31 Huffman code table 0..31
// 32,33 count1-tables
extern struct huffcodetab ht[HTN] = {
	{"0",0,0,0,0,-1,NULL,NULL,ValTab0,0},
	{"1",2,2,0,0,-1,NULL,NULL,ValTab1,7},
	{"2",3,3,0,0,-1,NULL,NULL,ValTab2,17},
	{"3",3,3,0,0,-1,NULL,NULL,ValTab3,17},
	{"4",0,0,0,0,-1,NULL,NULL,ValTab4,0},
	{"5",4,4,0,0,-1,NULL,NULL,ValTab5,31},
	{"6",4,4,0,0,-1,NULL,NULL,ValTab6,31},
	{"7",6,6,0,0,-1,NULL,NULL,ValTab7,71},
	{"8",6,6,0,0,-1,NULL,NULL,ValTab8,71},
	{"9",6,6,0,0,-1,NULL,NULL,ValTab9,71},
	{"10",8,8,0,0,-1,NULL,NULL,ValTab10,127},
	{"11",8,8,0,0,-1,NULL,NULL,ValTab11,127},
	{"12",8,8,0,0,-1,NULL,NULL,ValTab12,127},
	{"13",16,16,0,0,-1,NULL,NULL,ValTab13,511},
	{"14",0,0,0,0,-1,NULL,NULL,ValTab14,0},
	{"15",16,16,0,0,-1,NULL,NULL,ValTab15,511},
	{"16",16,16,1,1,-1,NULL,NULL,ValTab16,511},
	{"17",16,16,2,3,16,NULL,NULL,ValTab16,511},
	{"18",16,16,3,7,16,NULL,NULL,ValTab16,511},
	{"19",16,16,4,15,16,NULL,NULL,ValTab16,511},
	{"20",16,16,6,63,16,NULL,NULL,ValTab16,511},
	{"21",16,16,8,255,16,NULL,NULL,ValTab16,511},
	{"22",16,16,10,1023,16,NULL,NULL,ValTab16,511},
	{"23",16,16,13,8191,16,NULL,NULL,ValTab16,511},
	{"24",16,16,4,15,-1,NULL,NULL,ValTab24,512},
	{"25",16,16,5,31,24,NULL,NULL,ValTab24,512},
	{"26",16,16,6,63,24,NULL,NULL,ValTab24,512},
	{"27",16,16,7,127,24,NULL,NULL,ValTab24,512},
	{"28",16,16,8,255,24,NULL,NULL,ValTab24,512},
	{"29",16,16,9,511,24,NULL,NULL,ValTab24,512},
	{"30",16,16,11,2047,24,NULL,NULL,ValTab24,512},
	{"31",16,16,13,8191,24,NULL,NULL,ValTab24,512},
	{"32",1,16,0,0,-1,NULL,NULL,ValTab32,31},
	{"33",1,16,0,0,-1,NULL,NULL,ValTab33,31},
};

// do the huffman-decoding
// note! for counta,countb -the 4 bit value is returned in y,
// discard x
int32 huffman_decoder(struct huffcodetab *h, int32 *x, int32 *y, int32 *v,
							 int32 *w, Bit_Reserve *br)
{
  HUFFBITS level;
  int32 point = 0;
  int32 error = 1;
  level     = dmask;

  if (h->val == NULL) return 2;

  /* table 0 needs no bits */
  if ( h->treelen == 0)
  {  *x = *y = 0;
	  return 0;
  }

  /* Lookup in Huffman table. */

  do {
	 if (h->val[point][0]==0) {   /*end of tree*/
		*x = h->val[point][1] >> 4;
		*y = h->val[point][1] & 0xf;

		error = 0;
		break;
	 }
	 if (br->hget1bit()) {
		while (h->val[point][1] >= MXOFF) point += h->val[point][1];
		point += h->val[point][1];
	 }
	 else {
		while (h->val[point][0] >= MXOFF) point += h->val[point][0];
		point += h->val[point][0];
	 }
	 level >>= 1;
  } while (level  || (point < ht->treelen) );

  // Check for error.

/*  if (error) { // set x and y to a medium value as a simple concealment
	 printf("Illegal Huffman code in data.\n");
	 *x = (h->xlen-1 << 1);
	 *y = (h->ylen-1 << 1);
  } */

  /* Process sign encodings for quadruples tables. */

  if (h->tablename[0] == '3'
		&& (h->tablename[1] == '2' || h->tablename[1] == '3')) {
	  *v = (*y>>3) & 1;
	  *w = (*y>>2) & 1;
	  *x = (*y>>1) & 1;
	  *y = *y & 1;

	  /* v, w, x and y are reversed in the bitstream.
		  switch them around to make test bistream work. */

	  if (*v)
  		  if (br->hget1bit()) *v = -*v;
	  if (*w)
		  if (br->hget1bit()) *w = -*w;
	  if (*x)
		  if (br->hget1bit()) *x = -*x;
	  if (*y)
		  if (br->hget1bit()) *y = -*y;
  } else {

	 // Process sign and escape encodings for dual tables.

		// x and y are reversed in the test bitstream.
		//	Reverse x and y here to make test bitstream work.

	  if (h->linbits)
		 if ((h->xlen-1) == *x)
			*x += br->hgetbits(h->linbits);
	  if (*x)
		  if (br->hget1bit()) *x = -*x;
	  if (h->linbits)
		 if ((h->ylen-1) == *y)
			*y += br->hgetbits(h->linbits);
	  if (*y)
		  if (br->hget1bit()) *y = -*y;
	  }

  return error;
}