#pragma ident "@(#)cgpcompress.c	1.22 98/09/09 SMI"

/*
 * Copyright (c) 1997 by Sun Microsystems, Inc.
 * All Rights Reserved
 */

/******************************************************************************
 * cgpcompress.c
 *
 * This file contains all the routines to compress a command stream.
 *
 *  List of functions in this file:
 *	cgpColorStats
 *	cgpCompressStream
 *	cgpGenerateTableEntries
 *	getLeftRightBits
 *	cgpNormalStats
 *	cgpProcessSetState
 *	cgpVtxStats
 *
 *****************************************************************************/

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

#include "cgpi.h"
#include "cgpstream.h"
#include "cgpcompress.h"
#include "cgpbuildbuffer.h"

/* functions only used in this routine */
static CGvoid cgpProcessColorQuant(CGPsetquant *);
static CGvoid cgpProcessGeomQuant(CGPsetquant *);
static CGvoid cgpProcessNormalQuant(CGPsetquant *);
static CGvoid cgpProcessSetState(CGPsetstate *);
static CGvoid cgpVtxStats(CGPvertex *);
static CGvoid cgpColorStats(CGPsetcolor *);
static CGvoid cgpNormalStats(CGPsetnormal *);
static CGvoid cgpGenerateTableEntries(CGPstats[512] , CGuint *);

/* globals to this file */

/* [2] - relative/absolute */
/* [16] - data size */
/* [15] - shift amount */
/*
 * computed as abs*272 + size * 16 + shift
 */
static CGPstats vtxStats[544];
static CGPstats colorStats[544];

/* [2]  - relative/absolute */
/* [12] - data size         */
/* [11]  - shift amount      */
/*
 * computed as abs*156 + size * 12 + shift
 */
static CGPstats normalStats[312];

static CGuint numGeomTableEntries;
static CGuint numColorTableEntries;
static CGuint numNormalTableEntries;

static short curGeomQuant;        /* current quantization levels */
static short curColorQuant;
static short curNormalQuant;

static CGuint curState;                /* holds vtx state info */

static CGPsetnormal normalBuff[16];    /* holds mesh buffer push info */
static CGPsetcolor  colorBuff[16];
static CGint        meshIdx;           /* current place to write in both */

static CGint oldFlags;
static CGint oldOct;
static CGint oldSext;
static CGint oldU;
static CGint oldV;
static CGint oldR;
static CGint oldG;
static CGint oldB;
static CGint oldA;

/*******************
 * cgpcompressStream
 *
 *  Main routine called to take a data stream and generate the most
 *  efficient compressed data and the needed huffman table entries and
 *  huffman tags.
 *
 *  Input:
 *    CGPcommandstream* streamHdr	- stream to compress and insert
 *					  the SetTable entries
 *
 *  Output:
 *    None.
 *
 */

CGvoid
cgpCompressStream(CGPcommandstream *streamHdr, CGint geomQuant,
   CGint colorQuant, CGint normQuant)
{
    CGPcommandstream *curCmd;
    CGuint i;

    CGint curVtxHuffmanEntry;
    CGint curColorHuffmanEntry;
    CGint curNormalHuffmanEntry;
    int colorHuffmanTable[(CGP_NUM_TABLE_ENTRIES+1)];
    int normalHuffmanTable[(CGP_NUM_TABLE_ENTRIES+1)];
    CGPtabledata vtxTableData[(CGP_NUM_TABLE_ENTRIES+1)];
    CGPtabledata colorTableData[(CGP_NUM_TABLE_ENTRIES+1)];
    CGPtabledata normalTableData[(CGP_NUM_TABLE_ENTRIES+1)];
    CGint curSize;
    CGint curShift;
    CGint abs;
    CGint size, shift;
    CGint numTableEntries;
    CGPsettable *tbl;

    curGeomQuant = geomQuant;
    curColorQuant = colorQuant;
    curNormalQuant = normQuant; 
    meshIdx = 0;
    curState = CGP_STATE_USE_MBR_N | CGP_STATE_USE_MBR_C;
    curCmd = streamHdr;
    curCmd++;   /* first command is always CMD_SET_TABLE */
    numGeomTableEntries = numColorTableEntries = numNormalTableEntries = 0;

    /* clear all stats structures */
    memset(vtxStats, 0, sizeof(CGPstats) * 544);
    memset(colorStats, 0, sizeof(CGPstats) * 544);
    memset(normalStats, 0, sizeof(CGPstats) * 312);

    /* initialize this for normal processing - will force first normal */
    /* to be absolute.  */
    oldFlags = -1;
    /* first pass get data heuristics */
    while (curCmd->dataType != CGP_STREAM_CMD_NULL)
    {
        switch (curCmd->dataType)
        {
            case CGP_STREAM_CMD_VTX:
                cgpVtxStats((CGPvertex *)curCmd->data);

                if (curState & CGP_STATE_BNV)
                {
                    /* next command must be a set normal */
                    curCmd++;
                    cgpNormalStats((CGPsetnormal *)curCmd->data);
                    curState |= CGP_STATE_USE_MBR_N;
                }
                if (curState & CGP_STATE_BCV)
                {
                    /* next command must be a set color */
                    curCmd++;
                    cgpColorStats((CGPsetcolor *)curCmd->data);
                    curState |= CGP_STATE_USE_MBR_C;
                }

                if (curState & CGP_STATE_PUSH)
                {
                    curState &= ~CGP_STATE_PUSH;
                    meshIdx++;
                    meshIdx &= 0xf;
                }

                break;

            case CGP_STREAM_CMD_SET_STATE:

                /* update curState for vertex processing */
                cgpProcessSetState((CGPsetstate *)curCmd->data);

                /* reset mesh buffer state */
                curState |= CGP_STATE_USE_MBR_N | CGP_STATE_USE_MBR_C;

                break;

            case CGP_STREAM_CMD_SET_COLOR:
                /* if next command is a mesh buffer reference don't */
                /*  send down color from the mesh buffer           */
                curState &= ~CGP_STATE_USE_MBR_C;

                cgpColorStats((CGPsetcolor *)curCmd->data);
            break;

            case CGP_STREAM_CMD_SET_NORMAL:
                /* if next command is a mesh buffer reference don't */
                /*  send down normal from the mesh buffer           */
                curState &= ~CGP_STATE_USE_MBR_N;

                cgpNormalStats((CGPsetnormal *)curCmd->data);
                break;

            case CGP_STREAM_CMD_MBR:

                /* update any current info */
                if (curState & CGP_STATE_BNV)
                {
                    if (curState & CGP_STATE_USE_MBR_N)
                    {
                        CGPmbr *mbr = (CGPmbr *)curCmd->data; 
			CGuint idx = mbr->mbRef;

                        idx = CGP_GET_POINT_HDR_REF_NUMBER(idx);
                        idx = (meshIdx - idx) & 0xf;

                        oldOct = normalBuff[idx].oct;
                        oldSext = normalBuff[idx].sext;
                        oldU = normalBuff[idx].u;
                        oldV = normalBuff[idx].v;
                        oldFlags = normalBuff[idx].flags;
                    }
                    else
                        curState |= CGP_STATE_USE_MBR_N;
                }

                if (curState & CGP_STATE_BCV)
                {
                    if (curState & CGP_STATE_USE_MBR_C)
                    {
                        CGPmbr *mbr = (CGPmbr *)curCmd->data; 
			CGuint idx = mbr->mbRef;

                        idx = CGP_GET_POINT_HDR_REF_NUMBER(idx);
                        idx = (meshIdx - idx) & 0xf;

                        oldR = colorBuff[idx].ir;
                        oldG = colorBuff[idx].ig;
                        oldB = colorBuff[idx].ib;

                        if (curState & CGP_STATE_CAP)
                            oldA = colorBuff[idx].ia;
                    }
                }
                else
                    curState |= CGP_STATE_USE_MBR_C;

                break;

            case CGP_STREAM_CMD_SET_QUANT_GEOM:
                cgpProcessGeomQuant((CGPsetquant *)curCmd->data);
                break;

            case CGP_STREAM_CMD_SET_QUANT_COLOR:
                cgpProcessColorQuant((CGPsetquant *)curCmd->data);
                break;

            case CGP_STREAM_CMD_SET_QUANT_NORMAL:
                cgpProcessNormalQuant((CGPsetquant *)curCmd->data);
                break;

            default:
                fprintf(stderr, "cgpCompressStream: unknown command\n");
        }

        /* advance to next command */
        curCmd++;
    }

    /* ensure all entries can fit in huffman table */
    /* TODO - these should start by expanding the larger size */
    /*   not the smallest                                     */
    cgpGenerateTableEntries(vtxStats, &numGeomTableEntries);
    cgpGenerateTableEntries(colorStats, &numColorTableEntries);

    /* assign stats tables to array used by huffman */
    curVtxHuffmanEntry = 1;
    curColorHuffmanEntry = 1;
    curNormalHuffmanEntry = 1;
    memset((char*) vtxTableData, 0, sizeof(CGPtabledata));
    memset((char*) colorTableData, 0, sizeof(CGPtabledata));
    memset((char*) normalTableData, 0, sizeof(CGPtabledata));

    for (abs = 0; abs < 2; abs++)
        for (size = 1; size < 17; size++)
            for (shift = 0; shift < 16; shift++)
    {
        CGint curIdx = 272 * abs + size * 16 + shift;

        if (vtxStats[curIdx].count)
        {
            vtxTableData[curVtxHuffmanEntry].len = size;
            vtxTableData[curVtxHuffmanEntry].shift = shift;
            vtxTableData[curVtxHuffmanEntry].abs = abs;
            vtxTableData[curVtxHuffmanEntry].freq = vtxStats[curIdx].count;
            vtxTableData[curVtxHuffmanEntry].merge = -1;
            vtxTableData[curVtxHuffmanEntry].amerge = -1;
            vtxStats[curIdx].huffmanTablePos = curVtxHuffmanEntry++;
        }

        if (colorStats[curIdx].count)
        {
            colorTableData[curColorHuffmanEntry].len = size;
            colorTableData[curColorHuffmanEntry].shift = shift;
            colorTableData[curColorHuffmanEntry].abs = abs;
            colorTableData[curColorHuffmanEntry].freq =
                                                 colorStats[curIdx].count;
            colorTableData[curColorHuffmanEntry].merge = -1;
            colorTableData[curColorHuffmanEntry].amerge = -1;
            colorStats[curIdx].huffmanTablePos = curColorHuffmanEntry++;
        }
    }


    for (abs = 0; abs < 2; abs++)
        for (size = 1; size < 13; size++)
            for (shift = 0; shift < 12; shift++)
    {
        CGint curIdx;

        /* relative entries can only be 9 bits in size */
        if (abs == 0 && size > 9)
            continue;

        curIdx = 156 * abs + size * 12 + shift;

        if (normalStats[curIdx].count)
        {
            normalTableData[curNormalHuffmanEntry].len = size;
            normalTableData[curNormalHuffmanEntry].shift = shift;
            normalTableData[curNormalHuffmanEntry].abs = abs;
            normalTableData[curNormalHuffmanEntry].freq = 
                normalStats[curIdx].count;
            normalTableData[curNormalHuffmanEntry].merge = -1;
            normalTableData[curNormalHuffmanEntry].amerge = -1;
            normalStats[curIdx].huffmanTablePos = curNormalHuffmanEntry++;
        }
    }

    if (curVtxHuffmanEntry > 1)
        cgpCompHuffman(vtxTableData, curVtxHuffmanEntry);

    if (curColorHuffmanEntry > 1)
        cgpCompHuffman(colorTableData, curColorHuffmanEntry);

    if (curNormalHuffmanEntry > 1)
        cgpCompHuffman(normalTableData, curNormalHuffmanEntry);

    /* go through table entries and ensure that the tag + data sending */
    /* is at least 6 bits                                              */

    /* look at position entries */
    for (i = 1; i < curVtxHuffmanEntry; i++)
    {
        if (vtxTableData[i].merge == -1)
        {
            /* minimum length and huffcode is 6 bits */
            if ((USE_AFB) && (vtxTableData[i].huffCodeSize +
               (vtxTableData[i].len - vtxTableData[i].shift) < 6))
            { 
                /* it doesn't fit, now need to find a way to expand */
                CGint diff = 6 - vtxTableData[i].huffCodeSize -
                       (vtxTableData[i].len - vtxTableData[i].shift);

                /* reduce the shift amount */
                if (vtxTableData[i].shift > diff)
                {
                    vtxTableData[i].shift -= diff;
                    diff = 0;
                }
                else
                {
                    diff -= vtxTableData[i].shift;
                    vtxTableData[i].shift = 0;
                }

                /* if any remaining, add to the length */
                if (diff)
                {
                    vtxTableData[i].len += diff;
                    if (vtxTableData[i].len > 16)
                        printf("Error extending pos huffman table entries\n");
                }
            }
        }
    }


    /* look at normal entries */
    for (i = 1; i < curNormalHuffmanEntry; i++)
    {
        if (!normalTableData[i].abs && normalTableData[i].merge == -1)
        {
            /* minimum length and huffcode is 6 bits */
            if ((USE_AFB) && (normalTableData[i].huffCodeSize +
               (normalTableData[i].len - normalTableData[i].shift) < 6))
            {
                /* it doesn't fit, now need to find a way to expand */
                CGint diff = 6 - normalTableData[i].huffCodeSize -
                       (normalTableData[i].len - normalTableData[i].shift);

                /* reduce the shift amount */
                if (normalTableData[i].shift > diff)
                {
                    normalTableData[i].shift -= diff;
                    diff = 0;
                }
                else
                {
                    diff -= normalTableData[i].shift;
                    normalTableData[i].shift = 0;
                }

                /* if any remaining, add to the length */
                if (diff)
                {
                    normalTableData[i].len += diff;
                    if (normalTableData[i].len > 18)
                        printf("Error extending norm huffman table entries\n");
                }
            }
        }
    }

    /* look at color entries */
    for (i = 1; i < curColorHuffmanEntry; i++)
    {
        if (colorTableData[i].merge == -1)
        {
            /* minimum length and huffcode is 6 bits */
            if ((USE_AFB) && (colorTableData[i].huffCodeSize +
               (colorTableData[i].len - colorTableData[i].shift) < 6))
            {
                /* it doesn't fit, now need to find a way to expand */
                CGint diff = 6 - colorTableData[i].huffCodeSize -
                       (colorTableData[i].len - colorTableData[i].shift);

                /* reduce the shift amount */
                if (colorTableData[i].shift > diff)
                {
                    colorTableData[i].shift -= diff;
                    diff = 0;
                }
                else
                {
                    diff -= colorTableData[i].shift;
                    colorTableData[i].shift = 0;
                }

                /* if any remaining, add to the length */
                if (diff)
                {
                    colorTableData[i].len += diff;
                    if (colorTableData[i].len > 16)
                        printf("Error extending color huffman table entries\n");
                }
            }
        }
    }

    /* pass two - assign huffman tags and final size & shift values */
    curState = 0;
    curCmd = streamHdr;
    curCmd++;

    while (curCmd->dataType != CGP_STREAM_CMD_NULL)
    {
        switch (curCmd->dataType)
        {
            case CGP_STREAM_CMD_VTX:
            {
                CGPvertex *vtx = (CGPvertex *)curCmd->data;
                CGint idx;

                curSize = size = ((CGPvertex*)curCmd->data)->geomLen;
                curShift = shift = ((CGPvertex*)curCmd->data)->geomShift;

                if (((CGPvertex*)curCmd->data)->header &
                          CGP_POINT_HDR_GEOMETRY_ABSOLUTE)
                    abs = 1;
                else
                    abs = 0;

                /* if this position was expanded follow links to final entry */
                while(vtxStats[abs*272 + curSize*16 + curShift].overrideSize)
                {
                    idx = abs * 272 + curSize * 16 + curShift;
                    curSize = vtxStats[idx].overrideSize;
                    curShift = vtxStats[idx].overrideShift;
                }

                /* get final index */
                idx = abs * 272 + curSize * 16 + curShift;

                /* see if this entry was pushed to create an entry */
                /* for the opposite abs/rel type                   */
                if (abs != vtxTableData[vtxStats[idx].huffmanTablePos].abs)
                    idx = vtxTableData[vtxStats[idx].huffmanTablePos].amerge;
                else
                /* now make sure huffman table generation didn't merge */
                if (vtxTableData[vtxStats[idx].huffmanTablePos].merge != -1)
                    idx = vtxTableData[vtxStats[idx].huffmanTablePos].merge;
                else
                    idx = vtxStats[idx].huffmanTablePos;

                /* assign (possibly) new code */
                vtx->geomLen = vtxTableData[idx].len;
                vtx->geomShift = vtxTableData[idx].shift;

                ((CGPvertex*)curCmd->data)->header &=
                             ~CGP_POINT_HDR_GEOMETRY_ABSOLUTE;

                if (vtxTableData[idx].abs)
                    ((CGPvertex*)curCmd->data)->header |=
                              CGP_POINT_HDR_GEOMETRY_ABSOLUTE;

                vtx->geomTag = vtxTableData[idx].huffCode;
                vtx->geomTagLen = vtxTableData[idx].huffCodeSize;

                if (curState & CGP_STATE_BNV)
                {
                    CGint idx;
                    CGPsetnormal *normal;

                    curCmd++;
                    normal = (CGPsetnormal*)curCmd->data;

                    curSize = size = normal->normalLen;
                    curShift = shift = normal->normalShift;
                    if (normal->flags & CGP_SET_NORMAL_FLAG_SPECIAL ||
                        normal->flags & CGP_SET_NORMAL_FLAG_ABSOLUTE)
                        abs = 1;
                    else
                        abs = 0;

                    /* if this position was expanded follow links to */
                    /* final entry */
                    while(normalStats[abs*156 + curSize*12 + curShift].overrideSize)
                    {
                        idx = abs * 156 + curSize * 12 + curShift;
                        curSize = normalStats[idx].overrideSize;
                        curShift = normalStats[idx].overrideShift;
                    }

                    /* get final index */
                    idx = abs * 156 + curSize * 12 + curShift;

                    /* see if this entry was pushed to create an entry */
                    /* for the opposite abs/rel type                   */
                    if (abs != normalTableData[
                        normalStats[idx].huffmanTablePos].abs)
                        idx = normalTableData[
                          normalStats[idx].huffmanTablePos].amerge;
                    else
                    /* now make sure huffman table generation didn't merge */
                    if (normalTableData[normalStats[idx].huffmanTablePos].merge
                        != -1)
                        idx =
                         normalTableData[normalStats[idx].huffmanTablePos].merge;
                    else
                        idx = normalStats[idx].huffmanTablePos;

                    /* assign (possibly) new code */
                    normal->normalLen = normalTableData[idx].len;
                    normal->normalShift = normalTableData[idx].shift;

                    normal->normalTag = normalTableData[idx].huffCode;
                    normal->normalTagLen = normalTableData[idx].huffCodeSize;
                }

                if (curState & CGP_STATE_BCV)
                {
                    /* TODO - make this a function - used twice */
                    CGint idx;
                    CGPsetcolor *color;

                    curCmd++;
                    color = (CGPsetcolor *)curCmd->data;

                    curSize = size = color->colorLen;
                    curShift = shift = color->colorShift;
                    abs = color->absolute;

                    /* if this position was expanded follow links to */
                    /* final entry */
                    while(colorStats[abs*272 + curSize*16 + curShift].overrideSize)
                    {
                        idx = abs * 272 + curSize * 16 + curShift;
                        curSize = colorStats[idx].overrideSize;
                        curShift = colorStats[idx].overrideShift;
                    }

                    /* get final index */
                    idx = abs * 272 + curSize * 16 + curShift;

                    /* see if this entry was pushed to create an entry */
                    /* for the opposite abs/rel type                   */
                    if (abs != colorTableData[
                        colorStats[idx].huffmanTablePos].abs)
                        idx = colorTableData[
                          colorStats[idx].huffmanTablePos].amerge;
                    else
                    /* now make sure huffman table generation didn't merge */
                    if (colorTableData[colorStats[idx].huffmanTablePos].merge
                        != -1)
                        idx =
                         colorTableData[colorStats[idx].huffmanTablePos].merge;
                    else
                        idx = colorStats[idx].huffmanTablePos;

                    /* assign (possibly) new code */
                    color->colorLen = colorTableData[idx].len;
                    color->colorShift = colorTableData[idx].shift;

                    color->colorTag = colorTableData[idx].huffCode;
                    color->colorTagLen = colorTableData[idx].huffCodeSize;
                }
            }
            break;

            case CGP_STREAM_CMD_SET_STATE:

                /* update curState for vertex processing */
                cgpProcessSetState((CGPsetstate *)curCmd->data);

            break;

            case CGP_STREAM_CMD_SET_COLOR:
            {
                CGint idx;
                CGPsetcolor *color = (CGPsetcolor *)curCmd->data;

                curSize = size = color->colorLen;
                curShift = shift = color->colorShift;
                abs = color->absolute;

                /* if this position was expanded follow links to */
                /* final entry */
                while(colorStats[abs*272 + curSize*16 + curShift].overrideSize)
                {
                    idx = abs * 272 + curSize * 16 + curShift;
                    curSize = colorStats[idx].overrideSize;
                    curShift = colorStats[idx].overrideShift;
                }

                /* get final index */
                idx = abs * 272 + curSize * 16 + curShift;

                /* see if this entry was pushed to create an entry */
                /* for the opposite abs/rel type                   */
                if (abs != colorTableData[
                    colorStats[idx].huffmanTablePos].abs)
                    idx = colorTableData[
                      colorStats[idx].huffmanTablePos].amerge;
                else
                /* now make sure huffman table generation didn't merge */
                if (colorTableData[colorStats[idx].huffmanTablePos].merge
                    != -1)
                    idx =
                     colorTableData[colorStats[idx].huffmanTablePos].merge;
                else
                    idx = colorStats[idx].huffmanTablePos;

                /* assign (possibly) new code */
                color->colorLen = colorTableData[idx].len;
                color->colorShift = colorTableData[idx].shift;

                color->colorTag = colorTableData[idx].huffCode;
                color->colorTagLen = colorTableData[idx].huffCodeSize;

            }
            break;

            case CGP_STREAM_CMD_SET_NORMAL:
            {
                CGint idx;
                CGPsetnormal *normal;

                normal = (CGPsetnormal*)curCmd->data;

                curSize = size = normal->normalLen;
                curShift = shift = normal->normalShift;
                if (normal->flags & CGP_SET_NORMAL_FLAG_SPECIAL ||
                    normal->flags & CGP_SET_NORMAL_FLAG_ABSOLUTE)
                    abs = 1;
                else
                    abs = 0;

                /* if this position was expanded follow links to */
                /* final entry */
                while(normalStats[abs*156 + curSize*12 + curShift].overrideSize)
                {
                    idx = abs * 156 + curSize * 12 + curShift;
                    curSize = normalStats[idx].overrideSize;
                    curShift = normalStats[idx].overrideShift;
                }

                /* get final index */
                idx = abs * 156 + curSize * 12 + curShift;

                /* see if this entry was pushed to create an entry */
                /* for the opposite abs/rel type                   */
                if (abs != normalTableData[
                    normalStats[idx].huffmanTablePos].abs)
                    idx = normalTableData[
                      normalStats[idx].huffmanTablePos].amerge;
                else
                /* now make sure huffman table generation didn't merge */
                if (normalTableData[normalStats[idx].huffmanTablePos].merge
                    != -1)
                    idx =
                     normalTableData[normalStats[idx].huffmanTablePos].merge;
                else
                    idx = normalStats[idx].huffmanTablePos;

                /* assign (possibly) new code */
                normal->normalLen = normalTableData[idx].len;
                normal->normalShift = normalTableData[idx].shift;

                normal->normalTag = normalTableData[idx].huffCode;
                normal->normalTagLen = normalTableData[idx].huffCodeSize;
            }
            break;

            case CGP_STREAM_CMD_MBR:
                /* just skip over - nothing to compress */
                break;

            case CGP_STREAM_CMD_SET_QUANT_GEOM:
                cgpProcessGeomQuant((CGPsetquant *)curCmd->data);
                break;

            case CGP_STREAM_CMD_SET_QUANT_COLOR:
                cgpProcessColorQuant((CGPsetquant *)curCmd->data);
                break;

            case CGP_STREAM_CMD_SET_QUANT_NORMAL:
                cgpProcessNormalQuant((CGPsetquant *)curCmd->data);
                break;


            default:
                fprintf(stderr, "cgpCompressStream: unknown command\n");
        }

        /* advance to next command */
        curCmd++;
    }

    /* add set table entries */
    curCmd = streamHdr;

    /* count number of valid table entries */
    numTableEntries = 0;
    for (i = 1; i < curVtxHuffmanEntry; i++)
        if (vtxTableData[i].merge == -1)
            numTableEntries++;

    for (i = 1; i < curColorHuffmanEntry; i++)
        if (colorTableData[i].merge == -1)
            numTableEntries++;

    for (i = 1; i < curNormalHuffmanEntry; i++)
        if (normalTableData[i].merge == -1)
            numTableEntries++;

    /* the set table command holds all set table entries for this buffer */
    tbl = curCmd->data =
        (CGPsettable *) malloc(sizeof(CGPsettable) * numTableEntries);

    /* fill in position entries */
    for (i = 1; i < curVtxHuffmanEntry; i++)
    {
        if (vtxTableData[i].merge == -1)
        {
            tbl->dataLen = vtxTableData[i].len;
            tbl->shift = vtxTableData[i].shift;
            tbl->abs = vtxTableData[i].abs;
            tbl->table = CGP_STREAM_TABLE_POS;
            tbl->address = (0x40 >> (6 - vtxTableData[i].huffCodeSize)) |
                vtxTableData[i].huffCode;

            numTableEntries--;
            if (numTableEntries)
            {
                CGPsettable *tmp = tbl;
                tbl++;
                tmp->nextTableElement = tbl;
            }
            else
                tbl->nextTableElement = NULL;
        }
    }

    /* fill in normal entries */
    for (i = 1; i < curNormalHuffmanEntry; i++)
    {
        if (normalTableData[i].merge == -1)
        {
            if (normalTableData[i].abs)
                tbl->abs = 1;
            else
                tbl->abs = 0;

            tbl->table = CGP_STREAM_TABLE_NORMAL;
            tbl->address = (0x40 >> (6 - normalTableData[i].huffCodeSize)) |
                normalTableData[i].huffCode;
            tbl->dataLen = normalTableData[i].len;
            tbl->shift = normalTableData[i].shift;

            numTableEntries--;
            if (numTableEntries)
            {
                CGPsettable *tmp = tbl;
                tbl++;
                tmp->nextTableElement = tbl;
            }
            else
                tbl->nextTableElement = NULL;
        }
    }

    /* fill in color entries */
    for (i = 1; i < curColorHuffmanEntry; i++)
    {
        if (colorTableData[i].merge == -1)
        {
            tbl->dataLen = colorTableData[i].len;
            tbl->shift = colorTableData[i].shift;
            tbl->abs = colorTableData[i].abs;
            tbl->table = CGP_STREAM_TABLE_COLOR;
            tbl->address = (0x40 >> (6 - colorTableData[i].huffCodeSize)) |
                colorTableData[i].huffCode;

            numTableEntries--;
            if (numTableEntries)
            {
                CGPsettable *tmp = tbl;
                tbl++;
                tmp->nextTableElement = tbl;
            }
            else
                tbl->nextTableElement = NULL;
        }
    }
}


/*******************
 * cgpProcessSetState
 *
 * Updates the curState value to the new state.  This state holds
 * whether alpha is present in color and if color/normals are being sent
 * with each vertex.
 *
 *  Input:
 *    CGPsetstate*	setState
 *
 *  Output:
 *    None.
 *
 * Modifies the curState global variable
 *
 */

static CGvoid
cgpProcessSetState(CGPsetstate *setState)
{
    curState = 0;

    if (setState->state & CGP_CMD_SET_STATE_CAP)
        curState |= CGP_STATE_CAP;

    if (setState->state & CGP_CMD_SET_STATE_BCV)
        curState |= CGP_STATE_BCV;

    if (setState->state & CGP_CMD_SET_STATE_BNV)
        curState |= CGP_STATE_BNV;

}


/*******************
 * cgpProcessGeomQuant
 *
 * Processes the geometry quantization instruction by setting the
 * global curGeomQuant to this value.
 *
 *  Input:
 *    CGPsetQuant*	quant
 *
 *  Output:
 *    None.
 *
 */

static CGvoid
cgpProcessGeomQuant(CGPsetquant *setQuant)
{
    curGeomQuant = setQuant->quant;
}

/*******************
 * cgpProcessColorQuant
 *
 * Processes the color quantization instruction by setting the
 * global curColorQuant to this value.
 *
 *  Input:
 *    CGPsetQuant*      quant
 *
 *  Output:
 *    None.
 *
 */

static CGvoid
cgpProcessColorQuant(CGPsetquant *setQuant)
{
    curColorQuant = setQuant->quant;
}


/*******************
 * cgpProcessNormalQuant
 *
 * Processes the normal quantization instruction by setting the
 * global curNormalQuant to this value.
 *
 *  Input:
 *    CGPsetQuant       quant
 *
 *  Output:
 *    None.
 *
 */

static CGvoid
cgpProcessNormalQuant(CGPsetquant *setQuant)
{
    curNormalQuant = setQuant->quant;
}


/*******************
 * cgpGetLeftRightBits
 *
 * Finds the first one bit in the number from the right and the first
 * 1 for positive numbers, or 0 for negative numbers, starting from the
 * left.
 *
 *  Input:
 *    CGint	num		- the number to scan
 *
 *  Output:
 *    CGint*	leftBit		- bit position of left digit
 *    CGint*	rightBit	- bit position of right most 1 
 *    None.
 *
 */

static CGvoid
cgpGetLeftRightBits(CGint num, CGint *leftBit, CGint *rightBit)
{
    CGint i;
    CGint searchBit = (num & 0x8000) >> 15;

    /* skip over sign bit */
    for (i = 14; i > 0; i--)
        if (((num >> i) & 0x1) != searchBit)
            break;

    /* need extra bit for sign bit */
    *leftBit = i + 1;

    for (i = 0; i < 15; i++)
        if ((num & (1 << i)) != 0)
            break;

    *rightBit = i;
}


static CGvoid
cgpGetNormLeftRightBits(CGint num, CGint *leftBit, CGint *rightBit)
{
    CGint i;
    CGint searchBit = (num & 0x8000) >> 15;  /* grab a sign bit */

    /* skip over sign bit */
    for (i = 8; i > 0; i--)
        if (((num >> i) & 0x1) != searchBit)
            break;

    /* need extra bit for sign bit */
    *leftBit = i + 1;

    for (i = 0; i < 8; i++)
        if ((num & (1 << i)) != 0)
            break;

    *rightBit = i;
}

/*******************
 * cgpVtxStats
 *
 * Counts the frequency of each different size and shift combo for 
 * the vertex compression.  This info is used to generate the huffman
 * table.
 *
 *  Input:
 *    CGPvertex*	vtx
 *
 *  Output:
 *    None.
 *
 */

static CGvoid
cgpVtxStats(CGPvertex *vtx)
{
    CGint right, minRight;
    CGint left, maxLeft;
    CGint size, shift;
    CGint abs;

    if (vtx->header & CGP_POINT_HDR_PUSH)
        curState |= CGP_STATE_PUSH;

    /* 0's are tricky - just want them to be whatever is */
    /*  needed for the rest of the data */
    if (vtx->ix != 0)
        cgpGetLeftRightBits(vtx->ix, &maxLeft, &minRight);
    else
    {
        maxLeft = 0;
        minRight = 16;
    }

    if (vtx->iy != 0)
    {
        cgpGetLeftRightBits(vtx->iy, &left, &right);
        if (right < minRight)
            minRight = right;
        if (left > maxLeft)
            maxLeft = left;
    }

    if (vtx->iz != 0)
    {
        cgpGetLeftRightBits(vtx->iz, &left, &right);
        if (right < minRight)
            minRight = right;
        if (left > maxLeft)
            maxLeft = left;
    }

    /* if ix == iy == iz == 0 set to smallest value */
    if (vtx->ix == 0 && vtx->iy == 0 && vtx->iz == 0)
    {
        size = 1;
        shift = 0;
    }
    else
    {
        size = maxLeft + 1;
        shift = minRight;
    }

    if (vtx->header & CGP_POINT_HDR_GEOMETRY_ABSOLUTE)
        abs = 1;
    else
        abs = 0;

    if (vtxStats[abs * 272 + size * 16 + shift].count++ == 0)
    {
        numGeomTableEntries++;
    }
    
    /* for now load in best case compression */
    vtx->geomLen = size;
    vtx->geomShift = shift;
}


/*******************
 * cgpColorStats
 *
 * Counts the frequency of each different size and shift combo for 
 * the color compression.  This info is used to generate the huffman
 * table.
 *
 *  Input:
 *    CGPsetcolor*        color
 *
 *  Output:
 *    None.
 *
 */

static CGvoid
cgpColorStats(CGPsetcolor *color)
{
    CGint right, minRight;
    CGint left, maxLeft;
    CGint size, shift;

    /* 0's are tricky - just want them to be whatever is */
    /*  needed for the rest of the data */
    if (color->ir != 0)
        cgpGetLeftRightBits(color->ir, &maxLeft, &minRight);
    else
    {
        maxLeft = 0;
        minRight = 16;
    }

    if (color->ig != 0)
    {
        cgpGetLeftRightBits(color->ig, &left, &right);
        if (right < minRight)
            minRight = right;
        if (left > maxLeft)
            maxLeft = left;
    }

    if (color->ib != 0)
    {
        cgpGetLeftRightBits(color->ib, &left, &right);
        if (right < minRight)
            minRight = right;
        if (left > maxLeft)
            maxLeft = left;
    }


    if (curState & CGP_STATE_CAP)
    {
        if (color->ia != 0)
        {
            cgpGetLeftRightBits(color->ia, &left, &right);
            if (right < minRight)
                minRight = right;
            if (left > maxLeft)
                maxLeft = left;
        }
    }
    else
        color->ia = 0;

    /* if ir == ig == ib == ia == 0, set to min data needed */
    if (color->ir == 0 && color->ig == 0 &&
        color->ib == 0 && color->ia == 0)
    {
        size = 1;
        shift = 0;
    } 
    else
    {
        /* size is +1 */
        size = maxLeft + 1;
        shift = minRight;
    }

    if (colorStats[color->absolute * 272 + size * 16 + shift].count++ == 0)
    {
        numColorTableEntries++;
    }

    /* for now load in best case compression */
    color->colorLen = size;
    color->colorShift = shift;

    oldR = color->ir;
    oldG = color->ig;
    oldB = color->ib;

    if (curState & CGP_STATE_CAP)
        oldA = color->ia;

    if (curState & CGP_STATE_PUSH)
    {
        colorBuff[meshIdx].ir = oldR;
        colorBuff[meshIdx].ig = oldG;
        colorBuff[meshIdx].ib = oldB;

        if (curState & CGP_STATE_CAP)
            colorBuff[meshIdx].ia = oldA;
    }
}



/*******************
 * cgpNormalStats
 *
 * Generates the index normal and counts the frequency of each
 * different size delta. This info is used to generate the huffman
 * table.
 *
 *  Input:
 *    CGPsetnormal*        normal
 *
 *  Output:
 *    None.
 *
 */

static void
cgpNormalStats(CGPsetnormal *normal)
{
    /* see if a relative u,v can be used */
    if (!(normal->flags & CGP_SET_NORMAL_FLAG_ABSOLUTE ||
        normal->flags & CGP_SET_NORMAL_FLAG_SPECIAL  ||
        oldFlags & CGP_SET_NORMAL_FLAG_SPECIAL ||
        oldOct != normal->oct ||
        oldSext != normal->sext))
    {
        CGint du, dv;
        CGint maxLeft, minRight, left, right;
        CGint size, shift;
        CGint entrySize = curNormalQuant / 2;

        du = normal->u - oldU;
        dv = normal->v - oldV;

        /* 0's are tricky - just want them to be whatever is */
        /* needed for the rest of the data                   */
        if (du != 0)
            cgpGetNormLeftRightBits(du, &maxLeft, &minRight);
        else
        {
            maxLeft = 0;
            minRight = 18;
        }

        if (dv != 0)
        {
            cgpGetNormLeftRightBits(dv, &left, &right);
            if (right < minRight)
                minRight = right;
            if (left > maxLeft)
                maxLeft = left;
        }

        /* if du == dv == 0, set to minimum bits needed */
        if (du == 0 && dv == 0)
        {
            size = 1;
            shift = 0;
        }
        else
        {
            size = maxLeft + 1;
            shift = minRight;
        }

        /* quantize deltas */
        if (size - shift > entrySize)
            shift += ((size - shift) - entrySize);
        
        oldFlags = normal->flags;
        oldU = normal->u;
        oldV = normal->v;

        normal->u = du;
        normal->v = dv;

        normal->normalLen = size;
        normal->normalShift = shift;

        if (normalStats[size * 12 + shift].count++ == 0)
           numNormalTableEntries++;
    }
    else
    {
        oldOct = normal->oct;
        oldSext = normal->sext;
        normal->flags |= CGP_SET_NORMAL_FLAG_ABSOLUTE;
        oldFlags = normal->flags;
        oldU = normal->u;
        oldV = normal->v;

        if (normalStats[156 + normal->normalLen * 12 + normal->normalShift].count++ == 0)
           numNormalTableEntries++;
    }

    if (curState & CGP_STATE_PUSH)
    {
        normalBuff[meshIdx].u = oldU;
        normalBuff[meshIdx].v = oldV;
        normalBuff[meshIdx].sext = oldSext;
        normalBuff[meshIdx].oct = oldOct;
        normalBuff[meshIdx].flags = oldFlags;
    }
}


/*******************
 * cgpGenerateTableEntries
 *
 * If there are a lot of potential huffman table entries then most huffman
 * tags will be greater than 6 bits.  This routine tries to prevent this
 * from happening by combining neighbors together.  The desired number of
 * potential huffman table entries is CGP_NUM_ENTRIES.  This routine will
 * go through the list of table entries and increse the size and shift amounts
 * by 1 looking for entries to merge.
 *
 *  Input:
 *    CGPstats		stats[544]	- holds the stats to collapse
 *    Cguint            numEntries	- number of entries
 *
 *  Output:
 *    Cguint            numEntries	- final number of entries
 *
 */

static CGvoid
cgpGenerateTableEntries(CGPstats stats[544], CGuint *numEntries)
{
    CGint shift, size;
    CGint abs, expandSize, collapseShift;
    CGuint curEntries = *numEntries;

    /* that was easy */
    if (*numEntries < CGP_NUM_ENTRIES)
        return;

    expandSize = 1;
    collapseShift = 1;

    while (curEntries > CGP_NUM_ENTRIES)
    {
        for (size = 1; size < 17; size ++)
            for (shift = 0; shift < size; shift++)
            {
                /* check for shift neighbors */
                if (shift - collapseShift >= 0)
                {
                    CGint sizeIdx = size * 16;
                    if (stats[sizeIdx + shift].count)
                    {
                        if (stats[sizeIdx + (shift - collapseShift)].count)
                        {
                            stats[sizeIdx + (shift - collapseShift)].count +=
                                stats[sizeIdx + shift].count;
                            stats[sizeIdx + shift].overrideSize = size;
                            stats[sizeIdx + shift].overrideShift = 
                                shift - collapseShift;
                            stats[sizeIdx + shift].count = 0;

                            curEntries--;
                            if (curEntries <= CGP_NUM_ENTRIES)
                                goto Done;
                        }
                    }

                    /* the absolute case */ 
                    sizeIdx += 272;
                    if (stats[sizeIdx + shift].count)
                    {
                        if (stats[sizeIdx + (shift - collapseShift)].count)
                        {
                            stats[sizeIdx + (shift - collapseShift)].count +=
                                stats[sizeIdx + shift].count;
                            stats[sizeIdx + shift].overrideSize = size;
                            stats[sizeIdx + shift].overrideShift = 
                                shift - collapseShift;
                            stats[sizeIdx + shift].count = 0;

                            curEntries--;
                            if (curEntries <= CGP_NUM_ENTRIES)
                                goto Done;
                        }
                    }
                }

                /* check for size neighbors */
                if (size + expandSize <= 16)
                {
                    if (stats[size * 16 + shift].count)
                    {
                        if (stats[(size + expandSize)  * 16 + shift].count)
                        {
                            stats[(size + expandSize) * 16 + shift].count +=
                                stats[size * 16 + shift].count;
                            stats[size * 16 + shift].overrideSize =
                                size + expandSize;
                            stats[size * 16 + shift].overrideShift = shift;
                            stats[size * 16 + shift].count = 0;

                            curEntries--;
                            if (curEntries <= CGP_NUM_ENTRIES)
                                goto Done;
                        }
                    }

                    /* the absolute case */
                    if (stats[272 + size * 16 + shift].count)
                    {
                        if (stats[272 + (size + expandSize)  * 16
                                                          + shift].count)
                        {
                            stats[272 + (size + expandSize) * 16
                                  + shift].count +=
                                stats[272 + size * 16 + shift].count;
                            stats[272 + size * 16 + shift].overrideSize =
                                size + expandSize;
                            stats[272 + size * 16 + shift].overrideShift =
                                shift;
                            stats[272 + size * 16 + shift].count = 0;

                            curEntries--;
                            if (curEntries <= CGP_NUM_ENTRIES)
                                goto Done;
                        }
                    }
                }
            }

        /* current expansion values aren't enough, increase and try again */
        expandSize++;
        collapseShift++;
    }

Done:

    /* update with new value */
    *numEntries = curEntries;
}
