/****************************************************************************
* $Id: zerotree.c,v 1.2 2006-11-22 12:58:13+01 rolf Exp rolf $
*****************************************************************************/
/*
  ZeroTree7:
	- 16-bit arithmetics:
		TreeBits (bit number) instead of TreeMax !!!
	- signed wavelet coefficients
	- cutting output at the desired compression rate
	- incl. support for entropy calculation by coding
	  selected blocks, introduced
	- Z.BitNo runs from 32..1
	- Changed order in Vertical Tree
		H:      1   x   2
                3       4
        V:      1       2
                x
                3       4
        D:      1       2
                    x
                3       4
	- Changed coder initialization
        X-node: LIP, H/V/D-nodes: LIP,LIS-A
      ( zerotree5.c had a single super-node: LIS-A )

    - All nodes in 4+er blocks

  Build a real ZeroTree from image blocks:
    * image = A*2^N x B*2^N = A*B blocks
    * block = 2^N x 2^N

    +--------------------------------------+
    | image = 3x4 blocks                   |
    |                                      |
    |                                      |
    |          +-------+                   |
    |          | block |                   |
    |          |       |                   |
    |          |2^Nx2^N|                   |
    |          +-------+                   |
    |                                      |
    |                                      |
    |                                      |
    +--------------------------------------+

  NOTE: There is no quantizer before this compression.
  Therefore the S+P wavelet scaling must be applied during
  built of the Zero-Tree.
  Therefore we need LONG INT arithmetics.

  +-------+-------+---------------+-------------------------------+
  |       |       |               |                               |
  |LLLLLL |LLLLHL |               |                               |
  |  *8   |  *4   |               |                               |
  +-------+-------+     LLHL      |                               |
  |       |       |      *2       |                               |
  |LLLLLH |LLLLHH |               |                               |
  |  *4   |  *2   |               |                               |
  +-------+-------+---------------+              HL               |
  |               |               |              *1               |
  |               |               |                               |
  |               |               |                               |
  |     LLLH      |     LLHH      |                               |
  |      *2       |      *1       |                               |
  |               |               |                               |
  |               |               |                               |
  +---------------+---------------+-------------------------------+
  |                               |                               |
  |                               |                               |
  |                               |                               |
  |                               |                               |
  |                               |                               |
  |                               |                               |
  |                               |                               |
  |              LH               |              HH               |
  |              *1               |              /2               |
  |                               |                               |
  |                               |                               |
  |                               |                               |
  |                               |                               |
  |                               |                               |
  |                               |                               |
  +-------------------------------+-------------------------------+

Changes:
	Oct 20, 2000:
	- One malloc for all pixels instead of one maaloc per pixel

*/

#define ZT_ONE_ALLOC		/* one memory allocation instead of a million */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "defines.h"
#include "bitstm.h"

#include "zerotree.h"

#undef ZT_DEBUG

struct {
    size_t			BlockSize;  /* Block size in pixel = 2^N */
    size_t			LineSize;   /* Image line size (offset between lines) = B*blkSize */
    sWord			*Dest;	    /* Destination address */
    sWord			*Src;	    /* Source address */
    ztree_func		*User;	    /* User function: put or get pixel */
    int				BitNo;	    /* Currently coded bit no. */
	int				TreeBits;	/* starting bit for zerotree */

	/* support for truncating output bitstream */
	size_t			BitSize;	/* number of remaining bits in output/input */

#ifdef ZT_ONE_ALLOC
	ztreeNodePtr	MemPtr;		/* Allocated memory */
	ztreeNodePtr	AllocPtr;	/* current allocater pointer */
#endif

#ifdef ZT_DEBUG
    char			*Msg;	    /* Messages for debugging */
    ztreeNodePtr	Node;	    /* current node for debugging */
#endif
} Z;

/******************************************************************/
/* General procedures                                             */
/******************************************************************/
static size_t offset( size_t x, size_t y )
{
    return ( y*Z.LineSize + x);
}

static uWord Max( sWord a, sWord b )
{
    return (a > b) ? a : b;
}
static int numBits( unsigned long x )
{
	int n=0;
	while( x > 0 ) {
		n++;
		x /= 2;
	}
	return n;
}
static unsigned bitMask( int bitNo )
{
	bitNo--;	/* BitNo = 1..32 */
	if( bitNo < 0 )
		return 0;
	if( bitNo > 15 )
		return 0;
	return (1 << bitNo);
}
/******************************************************************/
/* ZeroTree: build a real ZeroTree in memory from image data      */
/******************************************************************/
static void getSrc( ztreeNodePtr node, size_t x, size_t y, int shift )
{
    sWord i;

	node->Shift = shift;

    if( Z.Src == NULL )
		return;

    i = Z.Src[offset(x,y)];
    node->Sign  = ( i < 0 );
    node->Value = abs(i);
}
static void putDest( ztreeNodePtr node, size_t x, size_t y )
{
    Z.Dest[offset(x,y)] = node->Sign ? (-(sWord)node->Value) : (sWord)node->Value;
}

void ztree_list( ztreeNodePtr node, int level )
{
    int i;
    if( node != NULL )
		for( i=0; i<4; i++, node++ ) {
			printf("%*s#%p Sign=%d Value=%4d Shift=%d TreeBits=%d Mode=%1d TreeMode=%1d =>#%p\n",
				4*level, "", node, node->Sign, node->Value, node->Shift, node->TreeBits, node->Mode, node->TreeMode, node->Child );
			ztree_list( node->Child, level+1 );
		}
}

/******************************************************************/
/* ZeroTree: Memory allocation                                    */
/******************************************************************/
static void *allocMem( size_t size )
{
	void *ptr;

    ptr = malloc(size);
    if( ptr == NULL ) {
		perror("ZeroTree: cannot allocate memory");
		exit(1);
    }
    memset(ptr, 0, size );  /* init memory to NULL !!! */
    return ptr;
}

#ifdef ZT_ONE_ALLOC

static ztreeNodePtr allocNode( void )	/* allocate n=4 nodes */
{
	ztreeNodePtr result = Z.AllocPtr;
	Z.AllocPtr += 4;
	return result;
}

#else

static ztreeNodePtr allocNode( void )	/* allocate n=4 nodes */
{
    return (ztreeNodePtr) allocMem(4*sizeof(ztreeNode));
}
static void freeNode( ztreeNodePtr node )
{		/* free array of n=4 nodes */
    int i;
    ztreeNodePtr ptr;

    if( node != NULL ) {
		for( i=0, ptr=node; i<4; i++, ptr++ )
			freeNode(ptr->Child);
		free(node);
    }
}

#endif

/******************************************************************/
/* ZeroTree: Calculate the number of used bits for a tree         */
/******************************************************************/
static int calcTreeBits( ztreeNodePtr node )
{
    int i;
    sWord max;
    sWord valBits;

    if( node == NULL )
		return 0;

    max = 0;
    for( i=0; i<4; i++, node++ ) {
		node->TreeBits = calcTreeBits( node->Child );
		max = Max( max, node->TreeBits );
		valBits = numBits(node->Value) + node->Shift;
		max = Max( max, valBits );	/* max incl. Value,Tree */
    }
    return max;
}

/******************************************************************/
/* ZeroTree: Build Tree, filling Value, Shift, TreeBits           */
/******************************************************************/
static ztreeNodePtr buildHorizontal( size_t x, size_t y, size_t step, int shift )
{
    ztreeNodePtr node = allocNode();

    getSrc( node+0, x-step, y,        shift );
    getSrc( node+1, x+step, y,        shift );
    getSrc( node+2, x-step, y+2*step, shift );
    getSrc( node+3, x+step, y+2*step, shift );

    if( step > 1 ) {
		node[0].Child = buildHorizontal( x-step, y,        step/2, shift-1 );
		node[1].Child = buildHorizontal( x+step, y,        step/2, shift-1 );
		node[2].Child = buildHorizontal( x-step, y+2*step, step/2, shift-1 );
		node[3].Child = buildHorizontal( x+step, y+2*step, step/2, shift-1 );
    }
    return node;
}
static ztreeNodePtr buildVertical( size_t x, size_t y, size_t step, int shift )
{
    ztreeNodePtr node = allocNode();

    getSrc( node+0, x,        y-step, shift );
    getSrc( node+1, x+2*step, y-step, shift );
    getSrc( node+2, x,        y+step, shift );
    getSrc( node+3, x+2*step, y+step, shift );

    if( step > 1 ) {
		node[0].Child = buildVertical( x,        y-step, step/2, shift-1 );
		node[1].Child = buildVertical( x+2*step, y-step, step/2, shift-1 );
		node[2].Child = buildVertical( x,        y+step, step/2, shift-1 );
		node[3].Child = buildVertical( x+2*step, y+step, step/2, shift-1 );
    }
    return node;
}
static ztreeNodePtr buildDiagonal( size_t x, size_t y, size_t step, int shift )
{
    ztreeNodePtr node = allocNode();

    getSrc( node+0, x-step, y-step, shift );
    getSrc( node+1, x+step, y-step, shift );
    getSrc( node+2, x-step, y+step, shift );
    getSrc( node+3, x+step, y+step, shift );

    if( step > 1 ) {
		node[0].Child = buildDiagonal( x-step, y-step, step/2, shift-1 );
		node[1].Child = buildDiagonal( x+step, y-step, step/2, shift-1 );
		node[2].Child = buildDiagonal( x-step, y+step, step/2, shift-1 );
		node[3].Child = buildDiagonal( x+step, y+step, step/2, shift-1 );
    }
    return node;
}

static void undoHorizontal( ztreeNodePtr node, size_t x, size_t y, size_t step )
{
    if( node == NULL )
		return;

    putDest( node+0, x-step, y );
    putDest( node+1, x+step, y );
    putDest( node+2, x-step, y+2*step );
    putDest( node+3, x+step, y+2*step );

    undoHorizontal( node[0].Child, x-step, y,        step/2 );
    undoHorizontal( node[1].Child, x+step, y,        step/2 );
    undoHorizontal( node[2].Child, x-step, y+2*step, step/2 );
    undoHorizontal( node[3].Child, x+step, y+2*step, step/2 );
}
static void undoVertical( ztreeNodePtr node, size_t x, size_t y, size_t step )
{
    if( node == NULL )
		return;

    putDest( node+0, x,        y-step );
    putDest( node+1, x+2*step, y-step );
    putDest( node+2, x,        y+step );
    putDest( node+3, x+2*step, y+step );

    undoVertical( node[0].Child, x,        y-step, step/2 );
    undoVertical( node[1].Child, x+2*step, y-step, step/2 );
    undoVertical( node[2].Child, x,        y+step, step/2 );
    undoVertical( node[3].Child, x+2*step, y+step, step/2 );
}
static void undoDiagonal( ztreeNodePtr node, size_t x, size_t y, size_t step )
{
    if( node == NULL )
		return;

    putDest( node+0, x-step, y-step );
    putDest( node+1, x+step, y-step );
    putDest( node+2, x-step, y+step );
    putDest( node+3, x+step, y+step );

    undoDiagonal( node[0].Child, x-step, y-step, step/2 );
    undoDiagonal( node[1].Child, x+step, y-step, step/2 );
    undoDiagonal( node[2].Child, x-step, y+step, step/2 );
    undoDiagonal( node[3].Child, x+step, y+step, step/2 );
}

/*
build a new Zero-Tree from image (src),
src==NULL builds an empty Zero-Tree filled with 0 values (before decoding)
*/
ztreeNodePtr ztree_build( sWord *src, size_t blockSize, size_t lineSize )
{
    ztreeNodePtr node;	/* 4-node containing *,Horizontal,Vertical,Diagonal subtrees */
    size_t        step;
    int           shift;

#ifdef ZT_ONE_ALLOC
	Z.AllocPtr = Z.MemPtr = allocMem(blockSize * blockSize * sizeof(ztreeNode));
#endif
    node = allocNode();

    Z.Src   = src;
    Z.BlockSize = blockSize;
    Z.LineSize  = lineSize;
    step = blockSize/2;

	shift = numBits( blockSize );

    getSrc(  node+0, 0,    0,    shift );
    getSrc(  node+1, step, 0,    shift-1 );
    getSrc(  node+2, 0,    step, shift-1 );
    getSrc(  node+3, step, step, shift-2 );

    if( step >= 2 ) {
		node[0].Child = NULL;
		node[1].Child = buildHorizontal( step, 0,    step/2, shift-2 );
		node[2].Child = buildVertical  (    0, step, step/2, shift-2 );
		node[3].Child = buildDiagonal  ( step, step, step/2, shift-3 );
    }

    Z.TreeBits = calcTreeBits( node );
#ifdef xZT_DEBUG
    ztree_list( node, 0 );
#endif
    return node;
}

void ztree_undo( ztreeNodePtr node, sWord *dest, size_t blockSize, size_t lineSize )
{
    size_t        step;

    Z.Dest  = dest;
    Z.BlockSize = blockSize;
    Z.LineSize  = lineSize;
    step = blockSize/2;

    putDest(  node+0, 0,    0 );
    putDest(  node+1, step, 0 );
    putDest(  node+2, 0,    step );
    putDest(  node+3, step, step );

    if( step >= 2 ) {
		undoHorizontal( node[1].Child, step, 0,    step/2 );
		undoVertical  ( node[2].Child, 0,    step, step/2 );
		undoDiagonal  ( node[3].Child, step, step, step/2 );
    }
}

/******************************************************************/
/* bitwise in/out                                                 */
/******************************************************************/
static unsigned outBit( unsigned n ) {
#ifdef ZT_DEBUG
	char ch = Z.BitSize ? ( n ? '1' : '0' ) : 'x';
    printf("%-7s: <%c> #%p Sign=%d Value=%d Shift=%d TreeBits=%d Mode=%d TreeMode=%d =>#%p\n",
		Z.Msg, ch, Z.Node, Z.Node->Sign, Z.Node->Value, Z.Node->Shift, Z.Node->TreeBits, Z.Node->Mode, Z.Node->TreeMode, Z.Node->Child);
#endif
	if( Z.BitSize ) {
		bsPutBit( (Word)(n!=0) );
		Z.BitSize--;
	}
    return n;
}
static unsigned inputBit( void ) {
    bsWord bit = 0;
#ifdef ZT_DEBUG
	char ch = Z.BitSize ? '?' : 'x';
#endif

	if( Z.BitSize ) {
		bsGetBit(&bit, 1);
		Z.BitSize--;
	}

#ifdef ZT_DEBUG
	if( ch=='?') ch = ( bit ? '1' : '0' );
    printf("%-7s: <%c> #%p Sign=%d Value=%d Shift=%d TreeBits=%d Mode=%d TreeMode=%d =>#%p\n",
		Z.Msg, ch, Z.Node, Z.Node->Sign, Z.Node->Value, Z.Node->Shift, Z.Node->TreeBits, Z.Node->Mode, Z.Node->TreeMode, Z.Node->Child);
#endif
    return bit;
}

/******************************************************************/
/* code a ZeroTree to bitstream                                   */
/******************************************************************/

/* code LIP: List of Insignificant Pixels */
static void codeLIP( ztreeNodePtr node )
{
    int i;
	unsigned mask;

    if( node == NULL ) return;

    for( i=0; i<4; i++, node++ ) {
		if( node->Mode == ztLIP ) {
#ifdef ZT_DEBUG
			Z.Msg  = "codeLIP", Z.Node = node;
#endif
			mask = bitMask(Z.BitNo - node->Shift);
			if( mask ) {
				if( outBit(node->Value >= mask) ) {
					outBit(node->Sign);
					node->Mode = ztLSPR;
				}
			}
		}
		if( node->TreeMode != 0 ) {
			codeLIP( node->Child );
		}
    }
}

static void codeLSP( ztreeNodePtr node )
{
    int i;
	unsigned mask;

    if( node == NULL ) return;

    for( i=0; i<4; i++, node++ ) {
		if( node->Mode == ztLSP ) {
#ifdef ZT_DEBUG
			Z.Msg  = "codeLSP", Z.Node = node;
#endif
			mask = bitMask(Z.BitNo - node->Shift);
			if( mask ) {
				outBit(node->Value & mask);
			}
		} else if( node->Mode == ztLSPR ) {
			node->Mode = ztLSP;		/* MSB has implicitly been output, process only at next step */
		}
		if( node->TreeMode != 0 ) {
			codeLSP( node->Child );
		}
    }
}

/* check if there are direct offsprings */
static void codeValues( ztreeNodePtr node )
{
    int i;
	unsigned mask;

    if( node == NULL ) return;

    for( i=0; i<4; i++, node++ ) {
#ifdef ZT_DEBUG
		Z.Msg  = "codeVal", Z.Node = node;
#endif
		mask = bitMask(Z.BitNo - node->Shift);
		if( mask ) {
			if( outBit(node->Value >= mask) ) {
				outBit(node->Sign);
				node->Mode = ztLSPR;
			} else {
				node->Mode = ztLIP;
			}
		}
    }
}

/*  check if there are direct offsprings
used for LIS_A -> LIS_B
*/
static int hasChilds( ztreeNodePtr node )
{
    int   i, nChilds=0;	    /* number of descendants */

    if( node == NULL ) 	return 0;

    for( i=0; i<4; i++, node++ ) {
		nChilds += ( node->Child != NULL );
	}

    return nChilds;
}

/*  check if there are direct offsprings
used for LIS_A -> LIS_B
*/
static int codeLIS_B( ztreeNodePtr node )
{
    int	  i;
	sWord maxBits = 0;

    ztreeNodePtr  nd;

    for( i=0, nd=node; i<4; i++, nd++ ) {
		maxBits = Max( nd->TreeBits, maxBits );
	}
#ifdef ZT_DEBUG
    printf("LIS_B: maxBits = %d\n", maxBits);
    Z.Msg  = "codeL-B", Z.Node = node;
#endif

    if( outBit( maxBits >= Z.BitNo ) ) {
		for( i=0, nd=node; i<4; i++, nd++ ) {
			nd->TreeMode = (nd->Child == 0) ? 0 : ztLIS_A;
		}
		return 1;
    } else {
		return 0;
	}
}

/* code LIS: List of Insignificant Sets(Trees) */
static void codeLIS( ztreeNodePtr node )
{
    int i;
    if( node == NULL ) return;

    for( i=0; i<4; i++, node++ ) {
		if( node->TreeMode == 0 )
			continue;
		if( node->TreeMode == ztLIS_A ) {
#ifdef ZT_DEBUG
			Z.Msg  = "codeL-A", Z.Node = node;
#endif
			if( outBit(node->TreeBits >= Z.BitNo) ) {
				codeValues(node->Child);
				if( hasChilds(node->Child) ) {	/* add grand childs to LIS */
					node->TreeMode = ztLIS_B;	/* not in LIS, but must be handled (!=0) */
				} else {
					node->TreeMode = ztLSS;
				}
			}
		}
		if( node->TreeMode == ztLIS_B ) {
			if( codeLIS_B(node->Child) ) {
				node->TreeMode = ztLSS;
			}
		}
		codeLIS( node->Child );
    }
}

/******************************************************************/
/* decode a ZeroTree to bitstream                            */
/******************************************************************/
/* decode LIP: List of Insignificant Pixels */
static void decodeLIP( ztreeNodePtr node )
{
    int i;
	unsigned mask;

    if( node == NULL ) return;

    for( i=0; i<4; i++, node++ ) {
		if( node->Mode == ztLIP ) {
#ifdef ZT_DEBUG
			Z.Msg  = "decoLIP", Z.Node = node;
#endif
			mask = bitMask(Z.BitNo - node->Shift);
			if( mask ) {
				if( inputBit() ) {
					node->Value |= mask;
					node->Sign = inputBit();
					node->Mode = ztLSPR;
				}
			}
		}
		if( node->TreeMode != 0 )
			decodeLIP( node->Child );
    }
}

static void decodeLSP( ztreeNodePtr node )
{
    int i;
	unsigned mask;

    if( node == NULL ) return;

    for( i=0; i<4; i++, node++ ) {
		if( node->Mode == ztLSP ) {
#ifdef ZT_DEBUG
			Z.Msg  = "decoLSP", Z.Node = node;
#endif
			mask = bitMask(Z.BitNo - node->Shift);
			if( mask ) {
				if( inputBit() ) {
					node->Value |= mask;
				}
			}
		} else if( node->Mode == ztLSPR ) {
			node->Mode = ztLSP;		/* MSB has implicitly been output, process only at next step */
		}
		if( node->TreeMode != 0 ) {
			decodeLSP( node->Child );
		}
    }
}

/* check if there are direct offsprings */
static void decodeValues( ztreeNodePtr node )
{
    int i;
	unsigned mask;

    if( node == NULL ) return;

    for( i=0; i<4; i++, node++ ) {
#ifdef ZT_DEBUG
		Z.Msg  = "decoVal", Z.Node = node;
#endif
		mask = bitMask(Z.BitNo - node->Shift);
		if( mask ) {
			if( inputBit() ) {
				node->Value |= mask;
				node->Sign = inputBit();
				node->Mode = ztLSPR;
			} else {
				node->Mode = ztLIP;
			}
		}
    }
}

/*  check if there are direct offsprings
used for LIS_A -> LIS_B
*/
static int decodeLIS_B( ztreeNodePtr node )
{
    int	    i;
    ztreeNodePtr  nd;

#ifdef ZT_DEBUG
    printf("LIS_B: \n");
    Z.Msg  = "decoL-B", Z.Node = node;
#endif
    if( inputBit() ) {
		for( i=0, nd=node; i<4; i++, nd++ ) {
			nd->TreeMode = (nd->Child == 0) ? 0 : ztLIS_A;
		}
		return 1;
    } else {
		return 0;
	}

}

/* decode LIS: List of Insignificant Sets(Trees) */
static void decodeLIS( ztreeNodePtr node )
{
    int i;
    if( node == NULL ) return;

    for( i=0; i<4; i++, node++ ) {
		if( node->TreeMode == 0 )
			continue;
		if( node->TreeMode == ztLIS_A ) {
#ifdef ZT_DEBUG
			Z.Msg  = "decoL-A", Z.Node = node;
#endif
			if( inputBit() ) {
				decodeValues(node->Child);
				if( hasChilds(node->Child) ) {	/* add grand childs to LIS */
					node->TreeMode = ztLIS_B;	/* not in LIS, but must be handled (!=0) */
				} else {
					node->TreeMode = ztLSS;
				}
			}
 		}
		if( node->TreeMode == ztLIS_B ) {
			if( decodeLIS_B(node->Child) ) {
				node->TreeMode = ztLSS;
			}
		}
		decodeLIS( node->Child );
    }
}


/******************************************************************/
/* public: code/decode a ZeroTree to bitstream                    */
/******************************************************************/

void ztree_init_tree ( ztreeNodePtr node )
{
	int	i;
	for( i=0; i<4; i++, node++ ) {
		node->Mode = ztLIP;
		node->TreeMode = (i==0) ? 0: ztLIS_A;
	}
}

int ztree_code( ztreeNodePtr tree, size_t size )
{
    int			codeStep;
    int			NumBlock = -1;
    int			TreeSignificant = 0;

#ifdef ZT_SHOW_BITPLANE
	int shown = 0;
#endif

	NumBlock++;
    if( tree == NULL ) return -1;

	ztree_init_tree( tree );

    Z.BitNo = Z.TreeBits;
	bsPutWord( (Word)Z.TreeBits, 0x0010 );	/* 5 bits TreeBits */

	codeStep = (Z.BitNo - 1) * 3;		/* max. number of steps */
	Z.BitSize = size-5;				/* size in bits incl. 5 bits TreeBits */

#ifdef ZT_DEBUG
    ztree_list( tree, 0 );
#endif

    while( Z.BitNo > 0 ) {
#ifdef ZT_DEBUG
		printf("#%-4d BitNo=%d\n", NumBlock, Z.BitNo );
#endif
		codeLIP(tree);
		if ( Z.BitSize == 0 ) {
			break;
		}
		codeStep--;

		if( ! TreeSignificant ) {		/* This trick saves us a few bits on Tree startup */
			TreeSignificant = codeLIS_B(tree);
		}
		if( TreeSignificant ) {		/* This trick saves us a few bits on Tree startup */
			codeLIS(tree);
		}
		if ( Z.BitSize == 0 ) {
			break;
		}
		codeStep--;

		codeLSP(tree);
		if ( Z.BitSize == 0 ) {
			break;
		}
		codeStep--;

#ifdef ZT_DEBUG
		if( tree->TreeMode != ztLIS_A ) {
			ztree_list( tree, 0 );
		}
#endif
		Z.BitNo--;
    }

	return codeStep;
}

int ztree_decode( ztreeNodePtr tree, size_t size )
{
	int		codeStep;
	bsWord	numBits;
	int		TreeSignificant = 0;

    if( tree == NULL ) return -1;

	ztree_init_tree( tree );

	bsGetWord( &numBits, 0x0010 );	/* 5 bits TreeBits */
	Z.BitNo = numBits;
	codeStep = (Z.BitNo - 1) * 3;	/* max. number of steps */
	Z.BitSize = size-5;				/* size in bits incl. 5 bits TreeBits */

    while( Z.BitNo > 0 ) {
#ifdef ZT_DEBUG
		printf("BitNo=%d\n", Z.BitNo );
#endif
		decodeLIP(tree);
		if ( Z.BitSize == 0 ) {
			break;
		}
		codeStep--;

		if( ! TreeSignificant ) {		/* This trick saves us a few bits on Tree startup */
			TreeSignificant = decodeLIS_B(tree);
		}
		if( TreeSignificant ) {		/* This trick saves us a few bits on Tree startup */
			decodeLIS(tree);
		}
		if ( Z.BitSize == 0 ) {
			break;
		}
		codeStep--;

		decodeLSP(tree);
		if ( Z.BitSize == 0 ) {
			break;
		}
		codeStep--;

#ifdef ZT_DEBUG
		if( tree->TreeMode != ztLIS_A ) {
			ztree_list( tree, 0 );
		}
#endif
		Z.BitNo--;
    }
#ifdef ZT_DEBUG
    ztree_list( tree, 0 );
#endif

	return codeStep;
}

void ztree_free( ztreeNodePtr tree )
{
#ifdef ZT_ONE_ALLOC
	free(Z.MemPtr);
	Z.AllocPtr = Z.MemPtr = NULL;
#else
    freeNode( tree );
#endif
}
