zerotree.c

零数源码

/*
 *
 * DLWIC
 *
 * (c) Joonas Lehtinen ([e-mail]), TUCS, 1998
 *
 */

#include "gwic.h"

/* Zerotree coding, decoding and stop condition */

/* Continue scanning */
int maxbytes;
int stop_immediately;
int cc() 
{
  extern long BytesOutQM;     /* Number of bytes written at encoding stage */

  if (!stop_immediately && maxbytes > BytesOutQM) {
    code_bit(1,SCONT);
    return 1;
  } else {
    if (stop_immediately) return 0;
    code_bit(0,SCONT);
    stop_immediately = 1;
  }
  return 0;
}

void scancode(U32 *coeff, int x, int y, heap2d *h, int n, int l,int fx,
	  int fy,int lw,int lh)
{
  int hv = *(*(h->lines + y)+x);
  int state;
  U32 *p;
  U32 nthbit = 1 << (n-1);
  int ch,cv,cd;

  if (cc()) {

    state = SNEWSIG + l;
    if (l && (*(*(h->lines + fy)+fx) == n)) state += 16;

    if (hv >= n) { /* There is something worth coding on this bitlevel n */
      if (hv == n) 
	code_bit(1,state);

      if (l) {
	/* Not on the top of pyramids */

	p = h->width * y + coeff + x;
	ch = *p; cd = *(p+lw); cv = *(p+lw-lh*h->width);
	
	/* HORIZONTAL */
	if ((ch&MASK) < (nthbit<<1)) {
	  state  = SORISIGH + l;
	  if ((cd&MASK) >= (nthbit<<1) || (cv&MASK) >= (nthbit<<1)) state +=16;
	  code_bit((ch&MASK)>=nthbit?1:0,state);
	  if ((ch&MASK) >= nthbit) {
	    code_bit(ch&SIGN?1:0,SSIGN);
	  }
	} else 
	  code_bit(ch&nthbit?1:0,SBIT);
	
	/* DIAGONAL */
	if ((cd&MASK) < (nthbit<<1)) {
	  state  = SORISIGD + l;
	  if ((ch&MASK) >= nthbit || (cv&MASK) >= (nthbit<<1)) state +=16;
	  code_bit((cd&MASK)>=nthbit?1:0,state);
	  if ((cd&MASK) >= nthbit) 
	    code_bit(cd&SIGN?1:0,SSIGN);
	} else 
	  code_bit(cd&nthbit?1:0,SBIT);

	
	/* VERTICAL */
	if ((cv&MASK) < (nthbit<<1)) {
	  state  = SORISIGV + l;
	  if ((ch&MASK) >= nthbit || (cd&MASK) >= nthbit) state +=16;
	  code_bit((cv&MASK)>=nthbit?1:0,state);
	  if ((cv&MASK) >= nthbit) 
	    code_bit(cv&SIGN?1:0,SSIGN);
	} else 
	  code_bit(cv&nthbit?1:0,SBIT);
	
	if ((y<<1)<h->height) {
	  scancode(coeff,x<<1,y<<1,h,n,l+1,x,y,lw<<1,lh<<1);
	  scancode(coeff,(x<<1)+1,y<<1,h,n,l+1,x,y,lw<<1,lh<<1);
	  scancode(coeff,x<<1,(y<<1)+1,h,n,l+1,x,y,lw<<1,lh<<1);
	  scancode(coeff,(x<<1)+1,(y<<1)+1,h,n,l+1,x,y,lw<<1,lh<<1);
	}
      } else {
	/* Top of the pyramids */

	p = h->width * y + coeff + x;
	ch = *p; 
	
	if ((ch&MASK) < (nthbit<<1)) {
	  code_bit((ch&MASK)>=nthbit?1:0,STOPLEVEL);
	  if ((ch&MASK) >= nthbit) 
	    code_bit(ch&SIGN?1:0,SSIGN);
	} else 
	  code_bit(ch&nthbit?1:0,SBIT);

	scancode(coeff,x,y+lh,h,n,1,x,y,lw,lh);
      }
    } else code_bit(0,state);
  }
}

/* Continue scanning */
int cdc()
{
  if (stop_immediately) return 0;
  if (!decode_bit(SCONT)) {
    stop_immediately = 1;
    return 0;
  }
  return 1;
}

void scandecode(U32 *coeff, int x, int y, heap2d *h, int n, 
		int l,int fx, int fy,int lw,int lh)
{
  int hv = *(*(h->lines + y)+x);
  int state;
  U32 *p;
  U32 nthbit = 1 << (n-1);
  int ch,cv,cd;
  int ib=0;

  if (cdc()) {

    if (!hv) { /* There is something worth coding on this bitlevel n */
      state = SNEWSIG + l;
      if (l && (*(*(h->lines + fy)+fx) == n)) state += 16;
      ib = decode_bit(state);
    }

    if (ib) hv = *(*(h->lines + y)+x) = n;

    if (hv) {
      /* Scan children */
      if (l) {

	p = h->width * y + coeff + x;
	ch = *p; cd = *(p+lw); cv = *(p+lw-lh*h->width);

	/* HORIZONTAL */
	if (ch)
	  *p = ch = (ch&(~nthbit)) | (decode_bit(SBIT) ? nthbit : 0) | (nthbit>>1);
	else {
	  state  = SORISIGH + l;
	  if ((cd&MASK) >= (nthbit<<1) || (cv&MASK) >= (nthbit<<1)) state +=16;
	  if (decode_bit(state)) 
	    *p = ch = (decode_bit(SSIGN) ? SIGN : 0) | nthbit | (nthbit>>1);
	}
	/* DIAGONAL */
	if (cd)
	  *(p+lw) = cd = (cd&(~nthbit)) | (decode_bit(SBIT) ? nthbit : 0) | (nthbit>>1);
	else {
	  state  = SORISIGD + l;
	  if ((ch&MASK) >= nthbit || (cv&MASK) >= (nthbit<<1)) state +=16;
	  if(decode_bit(state)) 
	    *(p+lw) = cd = (decode_bit(SSIGN) ? SIGN : 0) | nthbit | (nthbit>>1);
	}

	/* VERTICAL */
	if (cv)
	  *(p+lw-lh*h->width) = cv = (cv&(~nthbit)) | (decode_bit(SBIT) ? nthbit : 0) | (nthbit>>1);
	else {
	  state  = SORISIGV + l;
	  if ((ch&MASK) >= nthbit || (cd&MASK) >= nthbit) state +=16;
	  if(decode_bit(state)) 
	    *(p+lw-lh*h->width) = cv = (decode_bit(SSIGN) ? SIGN : 0) | nthbit | (nthbit>>1);
	}

	if ((y<<1)<h->height) {
	  scandecode(coeff,x<<1,y<<1,h,n,l+1,x,y,lw<<1,lh<<1);
	  scandecode(coeff,(x<<1)+1,y<<1,h,n,l+1,x,y,lw<<1,lh<<1);
	  scandecode(coeff,x<<1,(y<<1)+1,h,n,l+1,x,y,lw<<1,lh<<1);
	  scandecode(coeff,(x<<1)+1,(y<<1)+1,h,n,l+1,x,y,lw<<1,lh<<1);
	}
      } else {
	p = h->width * y + coeff + x;
	ch = *p; 

	/* TOPLEVEL */
	if (ch)
	  *p = ch = (ch&(~nthbit)) | (decode_bit(SBIT) ? nthbit : 0) | (nthbit>>1);
	else 
	  if(decode_bit(STOPLEVEL)) 
	    *p = ch = (decode_bit(SSIGN) ? SIGN : 0) | nthbit | (nthbit>>1);
    
	scandecode(coeff,x,y+lh,h,n,1,x,y,lw,lh);
      }
    } 
  }
}

void zerotree_code(U32 *coeff, int width, int height, int levels, 
		   int mbytes,  heap2d *heap, 
		   int real_image_area)
{
  int w,h,i,j,n;

  stop_immediately = 0;

  w = width >> levels;
  h = height >> levels;
  maxbytes = mbytes;
  
  n = heap->max;

  for(;n>0 && !stop_immediately; n--) 
    for (j=0; j<h && !stop_immediately; j++) 
      for (i=0; i<w && !stop_immediately; i++) 
	scancode(coeff,i,j,heap,n,0,-1,-1,w,h);
}

U32 *zerotree_decode(int width, int height, int levels, int n)
{
  U32 *coeff, *p;
  int w,h,i,j;
  heap2d *heap;
  stop_immediately = 0;

  MALLOC(coeff,width*height*sizeof(U32));
  
  for(p=coeff, i=width*height; i; i--) *p++ = 0;

  heap = gen_2d_heap(coeff, width, height, levels);  
  w = width >> levels;
  h = height >> levels;
  
  for(;n>0 && !stop_immediately; n--) 
    for (j=0; j<h && !stop_immediately; j++) 
      for (i=0; i<w && !stop_immediately; i++) 
	scandecode(coeff,i,j,heap,n,0,-1,-1,w,h);

  free(heap);
  
  return coeff;
}