Subversion Repositories mb-jpeg

/*-----------------------------------------*/
/* File : tree_vld.c, utilities for jfif view */
/* Author : Pierre Guerrier, march 1998	   */
/*-----------------------------------------*/
 
#include <stdlib.h>
#include <stdio.h>
 
 
/*--------------------------------------*/
/* private huffman.c defines and macros */
/*--------------------------------------*/
 
/* Number of HTable words sacrificed to bookkeeping: */
#define GLOB_SIZE		32
 
/* Memory size of HTables: */
#define MAX_SIZE(hclass)		((hclass)?384:64)
 
/* Available cells, top of storage: */
#define MAX_CELLS(hclass)	(MAX_SIZE(hclass) - GLOB_SIZE)
 
/* for Huffman tree descent */
/* lower 8 bits are for value/left son */
 
#define GOOD_NODE_FLAG		0x100
#define GOOD_LEAF_FLAG		0x200
#define BAD_LEAF_FLAG		0x300
#define SPECIAL_FLAG		0x000
#define HUFF_FLAG_MSK		0x300
 
#define HUFF_FLAG(c)		((c) & HUFF_FLAG_MSK)
#define HUFF_VALUE(c)		((unsigned char)( (c) & (~HUFF_FLAG_MSK) ))
 
 
/*--------------------------------------*/
/* some static structures for storage	*/
/*--------------------------------------*/
 
static unsigned int	DC_Table0[MAX_SIZE(DC_CLASS)],
			DC_Table1[MAX_SIZE(DC_CLASS)];
 
static unsigned int	AC_Table0[MAX_SIZE(AC_CLASS)],
			AC_Table1[MAX_SIZE(AC_CLASS)];
 
static unsigned int    *HTable[4] = {
  				      &DC_Table0[0], &DC_Table1[0],
				      &AC_Table0[0], &AC_Table1[0]
				    };
 
 
/*----------------------------------------------------------*/
/* Loading of Huffman table, with leaves drop ability	    */
/*----------------------------------------------------------*/
 
int load_huff_tables(FILE *fi)
{
  char aux;
  int size, hclass, id;
  int LeavesN, NodesN, CellsN;
  int MaxDepth, i, k, done;
  int NextCellPt;	/* where shall we put next cell */
  int NextLevelPt;	/* where shall node point to */
  unsigned int flag;
 
  size = get_size(fi); /* this is the tables' size */
 
  size -= 2;
 
  while (size>0) {
 
    aux = fgetc(fi);
    hclass = first_quad(aux);	/* AC or DC */
    id = second_quad(aux);	/* table no */
    if (id>1) {
      fprintf(stderr, "\tERROR:\tBad HTable identity %d!\n",id);
      return -1;
    }
    id = HUFF_ID(hclass, id);
    if (verbose)
      fprintf(stderr, "\tINFO:\tLoading Table %d\n", id);
    size--;
    CellsN = NodesN = 1;      /* the root one */
    LeavesN = 0;
 
    for (i=0; i<MAX_CELLS(hclass); i++)
      HTable[id][i] = SPECIAL_FLAG;	/* secure memory with crash value */
 
    /* first load the sizes of code elements */
    /* and compute contents of each tree level */
    /* Adress	Content		*/
    /* Top		Leaves 0	*/
    /* Top-1	Nodes  0	*/
    /* ......	.......		*/
    /* Top-2k	Leaves k	*/
    /* Top-2k-1	Nodes  k	*/
 
    MaxDepth = 0;
    for (i=0; i<16; i++) {
      LeavesN = HTable[id][MAX_SIZE(hclass)-2*i-1] = fgetc(fi);
      CellsN = 2*NodesN; /* nodes is old */
      NodesN = HTable[id][MAX_SIZE(hclass)-2*i-2] = CellsN-LeavesN;
      if (LeavesN) MaxDepth = i;
    }
    size-=16;
 
    /* build root at address 0, then deeper levels at */
    /* increasing addresses until MAX_CELLS reached */
 
    HTable[id][0] = 1 | GOOD_NODE_FLAG;		/* points to cell _2_ ! */
    /* we give up address one to keep left brothers on even adresses */
    NextCellPt = 2;
    i = 0;		/* this is actually length 1 */
 
    done = 0;
 
    while (i<= MaxDepth) {
 
      /* then load leaves for other levels */
      LeavesN = HTable[id][MAX_SIZE(hclass)-2*i-1];
      for (k = 0; k<LeavesN; k++)
	if (!done) {
	  HTable[id][NextCellPt++] = fgetc(fi) | GOOD_LEAF_FLAG;
	  if (NextCellPt >= MAX_CELLS(hclass)) {
	    done = 1;
	    fprintf(stderr, "\tWARNING:\tTruncating Table at depth %d\n", i+1);
	  }
	}
	else fgetc(fi);	/* throw it away, just to keep file sync */
      size -= LeavesN;
 
      if (done || (i == MaxDepth)) { i++; continue; }
      /* skip useless node building */
 
      /* then build nodes at that level */
      NodesN = HTable[id][MAX_SIZE(hclass)-2*i-2];
 
      NextLevelPt = NextCellPt+NodesN;
      for (k = 0; k<NodesN; k++) {
	if (NextCellPt >= MAX_CELLS(hclass)) { done = 1; break; }
 
	flag = ((NextLevelPt|1) >=
		MAX_CELLS(hclass)) ? BAD_LEAF_FLAG : GOOD_NODE_FLAG;
	/* we OR by 1 to check even right brother within range */
	HTable[id][NextCellPt++] = (NextLevelPt/2) | flag;
	NextLevelPt += 2;
      }
 
      i++;	/* now for next level */
    }	/* nothing left to read from file after maxdepth */
 
    if (verbose)
      fprintf(stderr, "\tINFO:\tUsing %d words of table memory\n", NextCellPt);
 
    /*
      -- this is useful for displaying the uploaded tree --
      for(i=0; i<NextCellPt; i++) {
      switch (HUFF_FLAG(HTable[id][i])) {
      case GOOD_NODE_FLAG:
      fprintf(stderr, "Cell %X: Node to %X and %X\n", i,
      HUFF_VALUE(HTable[id][i])*2,
      HUFF_VALUE(HTable[id][i])*2 +1);
      break;
      case GOOD_LEAF_FLAG:
      fprintf(stderr, "Cell %X: Leaf with value %X\n", i,
      HUFF_VALUE(HTable[id][i]) );
      break;
      case SPECIAL_FLAG:
      fprintf(stderr, "Cell %X: Special flag\n", i);
      break;
      case BAD_LEAF_FLAG:
      fprintf(stderr, "Cell %X: Bad leaf\n", i);
      break;
      }
      }
      */
 
  }	/* loop on tables */
  return 0;
}
 
/*-----------------------------------*/
/* extract a single symbol from file */
/* using specified huffman table ... */
/*-----------------------------------*/
 
unsigned char
get_symbol(FILE *fi, int select)
{
  int cellPt;
 
  cellPt = 0; /* this is the root cell */
 
  while (HUFF_FLAG(HTable[select][cellPt]) == GOOD_NODE_FLAG)
    cellPt = get_one_bit(fi) | (HUFF_VALUE(HTable[select][cellPt])<<1);
 
  switch (HUFF_FLAG(HTable[select][cellPt])) {
  case SPECIAL_FLAG:
    fprintf(stderr, "%ld:\tERROR:\tFound forbidden Huffman symbol !\n",
	    ftell(fi));
    aborted_stream(fi, fo);
    break;
 
  case GOOD_LEAF_FLAG:
    return HUFF_VALUE(HTable[select][cellPt]);
    break;
 
  case BAD_LEAF_FLAG:
    /* how do we fall back in case of truncated tree ? */
    /* suggest we send an EOB and warn */
    fprintf(stderr, "%ld:\tWARNING:\tFalling out of truncated tree !\n",
	    ftell(fi));
    return 0;
    break;
 
  default:
    break;
  }
  return 0;
}