#include "system/xmath.h"
#include "system/xstdlib.h"
#include "system/xstdio.h"
#include "misc/col.h"

#define MAXNODES 256*1024
#define MAXCOLORS 65536
#define TREEDEPTH 0

typedef struct s_NODE NODE;
typedef struct s_NODES NODES;
typedef struct s_CUBE CUBE;

struct s_NODE
{
	NODE *prev,*child[8];

	BYTE id,level,census;
	BYTE mr,mg,mb;

	DWORD colors,unique;
	DWORD red,green,blue;
};

struct s_NODES
{
	NODES *next;

	NODE nodes[2048];
};

struct s_CUBE
{
	NODE *rootnode,*nextnode;
	NODES *nodequeue;

	RGB color;
	RGB *cmap;

	DWORD depth;
	DWORD colors;
	DWORD pruning_threshold,next_pruning_threshold;
	DWORD distance;

	DWORD shift[8];
	DWORD nodes,freenodes;
	DWORD colnum;
};

static CUBE cube;

static int buildtree24( RGB *color, int colors);
static int buildtree32( RGBA *color, int colors);
static void reduce( NODE *node);
static void reducetree( DWORD colors);
static void closestcolor( NODE *node);
static int initcube( int incolors, int outcolors, int treedepth,int adjust);
static NODE *initnode(DWORD id, DWORD level, NODE *prev, DWORD mr, DWORD mg, DWORD mb);
static void prunechild( NODE *node);
static void prunelevel( NODE *node);

/* ######################################################################### */

static int buildtree24( RGB *color, int colors)
{
	NODE *node;
	DWORD level,id;
	int bisect;
	int i;

	for (i=0; i<colors; i++)
	{

		// Check tree size for overflow
		if (cube.nodes > MAXNODES)
		{
			prunelevel( cube.rootnode);
			cube.depth--;
		}

    // Start at the root and descend the color cube tree
		node = cube.rootnode;

    for (level=1; level<=cube.depth; level++)
    {
			id = ( (color->r > node->mr)?1:0) | ( (color->g > node->mg)?2:0) | ( (color->b > node->mb)?4:0);

			if ( node->child[id] == NULL)
			{
				node->census |= 1 << id;

				bisect =  (1 << (8-level)) >> 1;

				node->child[id] = initnode(id, level, node, node->mr+( (id & 1)? bisect : -bisect), node->mg+( (id & 2)? bisect : -bisect), node->mb+( (id & 4)? bisect : -bisect));

				if (node->child[id] == NULL)
					return FALSE;

				if (level == cube.depth)
					cube.colors++;
			}

			// Record the number of colors represented by this node
			// Shift by level in the color description tree.

      node = node->child[id];
      node->colors += 1 << cube.shift[level];
    }

    // Increment unique color count and sum RGB values for this leaf for later
    // derivation of the mean cube color.

    node->unique++;
    node->red += color->r;
    node->green += color->g;
    node->blue += color->b;
    color++;
  }
	return( TRUE);
}

/* ######################################################################### */

static int buildtree32( RGBA *color, int colors)
{
	NODE *node;
	DWORD level,id;
	int bisect;
	int i;

	for (i=0; i<colors; i++)
	{

		// Check tree size for overflow
		if (cube.nodes > MAXNODES)
		{
			prunelevel( cube.rootnode);
			cube.depth--;
		}

    // Start at the root and descend the color cube tree
		node = cube.rootnode;

    for (level=1; level<=cube.depth; level++)
    {
			id = ( (color->r > node->mr)?1:0) | ( (color->g > node->mg)?2:0) | ( (color->b > node->mb)?4:0);

			if ( node->child[id] == NULL)
			{
				node->census |= 1 << id;

				bisect =  (1 << (8-level)) >> 1;

				node->child[id] = initnode(id, level, node, node->mr+( (id & 1)? bisect : -bisect), node->mg+( (id & 2)? bisect : -bisect), node->mb+( (id & 4)? bisect : -bisect));

				if (node->child[id] == NULL)
					return FALSE;

				if (level == cube.depth)
					cube.colors++;
			}

			// Record the number of colors represented by this node
			// Shift by level in the color description tree.

      node = node->child[id];
      node->colors += 1 << cube.shift[level];
    }

    // Increment unique color count and sum RGB values for this leaf for later
    // derivation of the mean cube color.

    node->unique++;
    node->red += color->r;
    node->green += color->g;
    node->blue += color->b;
    color++;
  }
	return( TRUE);
}

/* ######################################################################### */

static void colormap( NODE *node)
{
	DWORD id;

  // Traverse any children.

  if ( node->census != 0)
	{
    for (id=0; id < 8; id++)
		{
      if ( node->census & (1 << id))
        colormap( node->child[id]);
		}
	}

	if ( node->unique != 0)
  {
  	// Colormap entry is defined by the mean color in this cube.
    cube.cmap[ cube.colors].r = ((node->red + (node->unique >> 1))/node->unique);
    cube.cmap[ cube.colors].g = ((node->green + (node->unique >> 1))/node->unique);
    cube.cmap[ cube.colors].b = ((node->blue + (node->unique >> 1))/node->unique);
    node->colors = cube.colors++;
  }

}
/* ######################################################################### */

static void buildpalette( RGB *palette)
{
  cube.cmap = palette;
  cube.colors = 0;
  colormap( cube.rootnode);
}

/* ######################################################################### */

static void reduce( NODE *node)
{
	DWORD id;

  // Traverse any children

  if ( node->census != 0)
	{
    for ( id=0; id<8; id++)
		{
      if ( node->census & (1 << id))
        reduce(node->child[id]);
		}
	}
	if ( node->colors <= cube.pruning_threshold)
	{
    prunechild( node);
	}
  else
  {
    // Find minimum pruning threshold
    if ( node->unique > 0)
      cube.colors++;
    if ( node->colors < cube.next_pruning_threshold)
      cube.next_pruning_threshold = node->colors;
  }
}

/* ######################################################################### */

static void reducetree( DWORD colors)
{
  cube.next_pruning_threshold = 1;

  while( cube.colors > colors)
  {
    cube.pruning_threshold = cube.next_pruning_threshold;
    cube.next_pruning_threshold = cube.rootnode->colors - 1;
    cube.colors = 0;
    reduce( cube.rootnode);
  }
}

/* ######################################################################### */

static void closestcolor( NODE *node)
{
	DWORD id;

  // Traverse any children

  if ( node->census != 0)
	{
    for ( id=0; id<8; id++)
    {
		  if ( node->census & (1 << id))
        closestcolor( node->child[id]);
		}
	}
	if (node->unique != 0)
  {
		RGB *color;
		DWORD rdelta,gdelta,bdelta,delta;

    // Determine if this color is "closest".

    color = cube.cmap + node->colors;
/*
    dred = color->r - cube.color.r + 255;
    dgreen = color->g - cube.color.g + 255;
    dblue = color->b - cube.color.b + 255;
    distance = dred * dred + dgreen * dgreen + dblue * dblue;
    if (distance < cube.distance)
    {
      cube.distance = distance;
      cube.colnum = node->colors;
    }
*/
		rdelta = abs( color->r - cube.color.r);
		gdelta = abs( color->g - cube.color.g);
		bdelta = abs( color->b - cube.color.b);

		delta = rdelta;
		if (gdelta > delta) delta = gdelta;
		if (bdelta > delta) delta = bdelta;

		if (delta < cube.distance)
		{
			cube.distance = delta;
			cube.colnum = node->colors;
		}


	}
}
/* ######################################################################### */

static int initcube( int incolors, int outcolors, int treedepth,int adjust)
{
	DWORD bits, level, maxshift;
	char c = 1;

  // Initialize tree to describe color cube.  Depth is: Log4(colormap size)+2;

  cube.nodequeue = NULL;
  cube.nodes = 0;
  cube.freenodes = 0;
  if (treedepth == 0)
  {
    for ( treedepth=1; outcolors!=0; treedepth++)
      outcolors >>= 2;
    if (treedepth > adjust)
      treedepth -= adjust;
  }
  cube.depth = treedepth;
  if ( cube.depth > 8)
    cube.depth = 8;
  if ( cube.depth < 2)
    cube.depth = 2;

  // Initialize the shift values.
  for ( bits=0; c!='\0'; bits++)
    c <<= 1;
  for ( maxshift=sizeof(DWORD)*bits; incolors!=0; maxshift--)
    incolors >>= 1;
  for ( level=0; level<=cube.depth; level++)
  {
    cube.shift[level] = maxshift;
    if (maxshift != 0)
      maxshift--;
  }

  // Initialize root node.
  cube.rootnode = initnode(0 , 0, NULL, 128, 128, 128);
  if (cube.rootnode == NULL)
		return( FALSE);

  cube.rootnode->prev = cube.rootnode;
  cube.rootnode->colors = ~0;
  cube.colors = 0;

	return( TRUE);
}

/* ######################################################################### */

static NODE *initnode(DWORD id, DWORD level, NODE *prev, DWORD mr, DWORD mg, DWORD mb)
{
	NODE *node;
	int i;

	if (cube.freenodes == 0)
	{
		NODES *nodes;

		if ( (nodes = (NODES *)xmalloc( sizeof(NODES))) == NULL)
			return( NULL);

		nodes->next = cube.nodequeue;
		cube.nodequeue = nodes;
		cube.nextnode = nodes->nodes;
		cube.freenodes = 2048;
	}

  cube.nodes++;
  cube.freenodes--;

  node = cube.nextnode++;
  node->prev = prev;

  for (i=0; i<8; i++)
    node->child[i] = NULL;

  node->id = id;
  node->level = level;
  node->census = 0;
  node->mr = mr;
  node->mg = mg;
  node->mb = mb;
  node->colors = 0;
  node->unique = 0;
  node->red = 0;
  node->green = 0;
  node->blue = 0;

  return( node);
}

/* ######################################################################### */

static void prunechild( NODE *node)
{
	NODE *prev;

  // Merge color statistics into parent

  prev = node->prev;
  prev->census &= ~(1 << node->id);
  prev->unique += node->unique;
  prev->red += node->red;
  prev->green += node->green;
  prev->blue += node->blue;
	cube.nodes--;
}

/* ######################################################################### */

static void prunelevel( NODE *node)
{
	int id;

  // Traverse any children.

  if ( node->census != 0)
	{
    for ( id=0; id<8; id++)
		{
      if ( node->census & (1 << id))
        prunelevel( node->child[id]);
		}
	}
  if ( node->level == cube.depth)
    prunechild( node);
}

/* ######################################################################### */

int findcolor( RGB *palette, RGB color)
{
	int i,best;
	register int rdelta,gdelta,bdelta,delta;
	int bestdelta = 256 * 3;

	for( i=1; i<255; i++)
	{
		rdelta = abs( palette[i].r - color.r);
		gdelta = abs( palette[i].g - color.g);
		bdelta = abs( palette[i].b - color.b);

		delta = rdelta;
		if (gdelta > delta) delta = gdelta;
		if (bdelta > delta) delta = bdelta;

		if (delta < bestdelta)
		{
			bestdelta = delta;
			best = i;
		}
	}
	return( best);
}

/* ######################################################################### */

void remapdata( RGB *palette, RGB *imgpal, BYTE *imgdata, int width, int height)
{
	char remap[256];
	int i;

	for( i=0; i<256; i++)
		remap[i] = findcolor( palette, imgpal[i]);

	for(i=0; i<256; i++)
		imgpal[i] = palette[i];

	for(i=0; i<(width * height); i++)
		imgdata[i] = remap[imgdata[i]];

}

/* ######################################################################### */

int convert24to8( RGB *palette, RGB *image24, BYTE *image8, DWORD size)
{
	NODES *nodes;
	NODE *node;
	DWORD id;
	DWORD i;

  // Reduce the number of colors in the continuous tone image

  if ( !initcube( size, 256, TREEDEPTH, 1))
		return( FALSE);
	if ( !buildtree24( image24, size))
		return( FALSE);
  reducetree( 254);

	buildpalette( palette);

	for( i=0; i<size; i++)
  {
    // Identify the deepest node containing the pixel's color.

    node = cube.rootnode;

		while(1)
    {
      id = (image24->r > node->mr ?1:0) | (image24->g > node->mg ?1:0) << 1 | (image24->b > node->mb ?1:0) << 2;
      if( (node->census & (1 << id)) == 0)
        break;
      node = node->child[id];
    }
    // Find closest color among siblings and their children.

    cube.color.r = image24->r;
    cube.color.g = image24->g;
    cube.color.b = image24->b;
    cube.distance = (DWORD) (~0);
    closestcolor(node->prev);
    *image8 = cube.colnum;

    image24++;
    image8++;
	}

  do
  {
    nodes = cube.nodequeue->next;
    xfree( cube.nodequeue);
    cube.nodequeue = nodes;
  } while ( cube.nodequeue != NULL);

	return( TRUE);
}

/* ######################################################################### */

int convert32to8( RGB *palette, RGBA *image32, BYTE *image8, DWORD size)
{
	NODES *nodes;
	NODE *node;
	DWORD id;
	DWORD i;

  // Reduce the number of colors in the continuous tone image

  if ( !initcube( size, 256, TREEDEPTH, 1))
		return( FALSE);
	if ( !buildtree32( image32, size))
		return( FALSE);
  reducetree( 254);

	buildpalette( palette);

	for( i=0; i<size; i++)
  {
    // Identify the deepest node containing the pixel's color.

    node = cube.rootnode;

		while(1)
    {
      id = (image32->r > node->mr ?1:0) | (image32->g > node->mg ?1:0) << 1 | (image32->b > node->mb ?1:0) << 2;
      if( (node->census & (1 << id)) == 0)
        break;
      node = node->child[id];
    }
    // Find closest color among siblings and their children.

    cube.color.r = image32->r;
    cube.color.g = image32->g;
    cube.color.b = image32->b;
    cube.distance = (DWORD) (~0);
    closestcolor(node->prev);
    *image8 = cube.colnum;

    image32++;
    image8++;
	}

  do
  {
    nodes = cube.nodequeue->next;
    xfree( cube.nodequeue);
    cube.nodequeue = nodes;
  } while ( cube.nodequeue != NULL);

	return( TRUE);
}

/* ######################################################################### */

int makepalette( RGB *palette, RGB *list, int colors)
{
	NODES *nodes;

  // Reduce the number of colors in the continuous tone image

  if ( !initcube( colors, 256, TREEDEPTH, 1))
		return( FALSE);
	if ( !buildtree24( list, colors))
		return( FALSE);
	reducetree( 254);

	buildpalette( &palette[1]);

  do
  {
    nodes = cube.nodequeue->next;
    xfree( cube.nodequeue);
    cube.nodequeue = nodes;
  } while ( cube.nodequeue != NULL);

	return( TRUE);
}

/* ######################################################################### */

int makelighttab( BYTE *lighttab, RGB *palette, RGB ambient, RGB light)
{
	NODES *nodes;
	NODE *node;
	DWORD id;
	RGB *color;
	RGB *rgbtab;
	BYTE *lightnum;
	float r,g,b,radd,gadd,badd;
	int col;
	int i,j;

  if( (rgbtab = (RGB *)xmalloc( LIGHTLEVELS * 256 * sizeof(RGB))) == NULL)
		return( FALSE);

  radd = ((float)(light.r-ambient.r)*2)/LIGHTLEVELS;
	r = ((float)ambient.r - 128)*2;
  gadd = ((float)(light.g-ambient.g)*2)/LIGHTLEVELS;
	g = ((float)ambient.g - 128)*2;
  badd = ((float)(light.b-ambient.b)*2)/LIGHTLEVELS;
	b = ((float)ambient.b - 128)*2;

	for (j=0; j<LIGHTLEVELS; j++)
	{
		for (i=0; i<256; i++)
		{
			col = palette[i].r + (int)r;
			if ( col > 255)
        rgbtab[(j << 8) + i].r = 255;
			else if ( col < 0)
        rgbtab[(j << 8) + i].r = 0;
			else
        rgbtab[(j << 8) + i].r = col;

			col = palette[i].g + (int)g;
			if ( col > 255)
        rgbtab[(j << 8) + i].g = 255;
			else if ( col < 0)
        rgbtab[(j << 8) + i].g = 0;
			else
        rgbtab[(j << 8) + i].g = col;

			col = palette[i].b + (int)b;
			if ( col > 255)
        rgbtab[(j << 8) + i].b = 255;
			else if ( col < 0)
        rgbtab[(j << 8) + i].b = 0;
			else
        rgbtab[(j << 8) + i].b = col;

		}
		r+=radd;
		g+=gadd;
		b+=badd;
	}

  if ( !initcube( LIGHTLEVELS * 256, 256, TREEDEPTH, 1))
		return( FALSE);
	if ( !buildtree24( rgbtab, LIGHTLEVELS * 256))
		return( FALSE);
	reducetree( 254);
	buildpalette( &palette[1]);

  radd = ((float)(light.r-ambient.r)*2)/LIGHTLEVELS;
	r = ((float)ambient.r - 128)*2;
  gadd = ((float)(light.g-ambient.g)*2)/LIGHTLEVELS;
	g = ((float)ambient.g - 128)*2;
  badd = ((float)(light.b-ambient.b)*2)/LIGHTLEVELS;
	b = ((float)ambient.b - 128)*2;

	for (j=0; j<LIGHTLEVELS; j++)
	{
		for (i=0; i<256; i++)
		{
			col = palette[i].r + (int)r;
			if ( col > 255)
        rgbtab[(j << 8) + i].r = 255;
			else if ( col < 0)
        rgbtab[(j << 8) + i].r = 0;
			else
        rgbtab[(j << 8) + i].r = col;

			col = palette[i].g + (int)g;
			if ( col > 255)
        rgbtab[(j << 8) + i].g = 255;
			else if ( col < 0)
        rgbtab[(j << 8) + i].g = 0;
			else
        rgbtab[(j << 8) + i].g = col;

			col = palette[i].b + (int)b;
			if ( col > 255)
        rgbtab[(j << 8) + i].b = 255;
			else if ( col < 0)
        rgbtab[(j << 8) + i].b = 0;
			else
        rgbtab[(j << 8) + i].b = col;

		}
		r+=radd;
		g+=gadd;
		b+=badd;
	}

	color = rgbtab;
	lightnum = lighttab;

	for( i=0; i<(LIGHTLEVELS * 256); i++)
  {
    // Identify the deepest node containing the pixel's color.

    node = cube.rootnode;

		while(1)
    {
      id = (color->r > node->mr ?1:0) | (color->g > node->mg ?1:0) << 1 | (color->b > node->mb ?1:0) << 2;
      if( (node->census & (1 << id)) == 0)
        break;
      node = node->child[id];
    }
    // Find closest color among siblings and their children.

    cube.color.r = color->r;
    cube.color.g = color->g;
    cube.color.b = color->b;
    cube.distance = (DWORD) (~0);
    closestcolor(node->prev);
    *lightnum = cube.colnum;

    color++;
    lightnum++;
	}

  do
  {
    nodes = cube.nodequeue->next;
    xfree( cube.nodequeue);
    cube.nodequeue = nodes;
  } while ( cube.nodequeue != NULL);

	return( TRUE);
}

/* ######################################################################### */

int maketranstab( BYTE *transtab, RGB *palette, float left, float right)
{
	NODES *nodes;
	NODE *node;
	DWORD id;
	RGB *color;
	RGB *rgbtab;
	BYTE *transnum;
  int i,j,col;

	if( (rgbtab = (RGB *)xmalloc( 256 * 256 * sizeof(RGB))) == NULL)
		return( FALSE);

	for (i=0; i<256; i++)
	{
		for (j=0; j<256; j++)
		{
      col = (int)((((float)palette[i].r * left) + ((float)palette[j].r * right)) / 100);
      if ( col > 255)
        col = 255;
      else if ( col < 0)
        col = 0;
      rgbtab[(i << 8) + j].r = col;
      col = (int)((((float)palette[i].g * left) + ((float)palette[j].g * right)) / 100);
      if ( col > 255)
        col = 255;
      else if ( col < 0)
        col = 0;
      rgbtab[(i << 8) + j].g = col;
      col = (int)((((float)palette[i].b * left) + ((float)palette[j].b * right)) / 100);
      if ( col > 255)
        col = 255;
      else if ( col < 0)
        col = 0;
      rgbtab[(i << 8) + j].b = col;
		}
	}

  // Reduce the number of colors in the continuous tone image

  if ( !initcube( 256 * 256, 256, TREEDEPTH, 1))
		return( FALSE);
	if ( !buildtree24( rgbtab, 256 * 256))
		return( FALSE);
	reducetree( 254);
	buildpalette( &palette[1]);

	for (i=0; i<256; i++)
	{
		for (j=0; j<256; j++)
		{
      col = (int)((((float)palette[i].r * left) + ((float)palette[j].r * right)) / 100);
      if ( col > 255)
        col = 255;
      else if ( col < 0)
        col = 0;
      rgbtab[(i << 8) + j].r = col;
      col = (int)((((float)palette[i].g * left) + ((float)palette[j].g * right)) / 100);
      if ( col > 255)
        col = 255;
      else if ( col < 0)
        col = 0;
      rgbtab[(i << 8) + j].g = col;
      col = (int)((((float)palette[i].b * left) + ((float)palette[j].b * right)) / 100);
      if ( col > 255)
        col = 255;
      else if ( col < 0)
        col = 0;
      rgbtab[(i << 8) + j].b = col;
		}
	}

	color = rgbtab;
	transnum = transtab;

	for( i=0; i<(256 * 256); i++)
  {
    // Identify the deepest node containing the pixel's color.

    node = cube.rootnode;

		while(1)
    {
      id = (color->r > node->mr ?1:0) | (color->g > node->mg ?1:0) << 1 | (color->b > node->mb ?1:0) << 2;
      if( (node->census & (1 << id)) == 0)
        break;
      node = node->child[id];
    }
    // Find closest color among siblings and their children.

    cube.color.r = color->r;
    cube.color.g = color->g;
    cube.color.b = color->b;
    cube.distance = (DWORD) (~0);
    closestcolor(node->prev);
    *transnum = cube.colnum + 1;

    color++;
    transnum++;
	}

  do
  {
    nodes = cube.nodequeue->next;
    xfree( cube.nodequeue);
    cube.nodequeue = nodes;
  } while ( cube.nodequeue != NULL);

	xfree( rgbtab);

	return( TRUE);
}

/* ######################################################################### */

static int _lighttabs;
static struct
{
	BYTE *lighttab;
	RGB ambient,light;
} _lighttab[256];
static int _transtabs;
static struct
{
	BYTE *transtab;
	float left,right;
} _transtab[256];

int inittab()
{
	_lighttabs = 0;
	_transtabs = 0;
	return( TRUE);
}

int addlighttab( BYTE *lighttab, RGB ambient, RGB light)
{
	_lighttab[ _lighttabs].lighttab = lighttab;
	_lighttab[ _lighttabs].ambient = ambient;
	_lighttab[ _lighttabs].light = light;
	_lighttabs++;
	return( TRUE);
}

int addtranstab( BYTE *transtab, float left, float right)
{
	_transtab[ _transtabs].transtab = transtab;
	_transtab[ _transtabs].left = left;
	_transtab[ _transtabs].right = right;
	_transtabs++;
	return( TRUE);
}

static void buildlighttab( RGB *palette, RGB *rgbtab)
{
	RGB *rgb;
	float r,g,b,radd,gadd,badd;
	int i,j,k,col;

	rgb = rgbtab;

	for( i=0; i<_lighttabs; i++)
	{
		radd = ((float)(_lighttab[i].light.r-_lighttab[i].ambient.r)*2)/LIGHTLEVELS;
		r = ((float)_lighttab[i].ambient.r - 128)*2;
	  gadd = ((float)(_lighttab[i].light.g-_lighttab[i].ambient.g)*2)/LIGHTLEVELS;
		g = ((float)_lighttab[i].ambient.g - 128)*2;
	  badd = ((float)(_lighttab[i].light.b-_lighttab[i].ambient.b)*2)/LIGHTLEVELS;
		b = ((float)_lighttab[i].ambient.b - 128)*2;

		for( j=0; j<LIGHTLEVELS; j++)
		{
			for (k=0; k<256; k++)
			{
				col = palette[k].r + (int)r;
				if ( col > 255)
	        rgb->r = 255;
				else if ( col < 0)
	        rgb->r = 0;
				else
	        rgb->r = col;

				col = palette[k].g + (int)g;
				if ( col > 255)
	        rgb->g = 255;
				else if ( col < 0)
	        rgb->g = 0;
				else
	        rgb->g = col;

				col = palette[k].b + (int)b;
				if ( col > 255)
	        rgb->b = 255;
				else if ( col < 0)
	        rgb->b = 0;
				else
	        rgb->b = col;

				rgb++;
			}
			r+=radd;
			g+=gadd;
			b+=badd;
		}
	}
}

static void buildtranstab( RGB *palette, RGB *rgbtab)
{
	RGB *rgb;
	int i,j,k,col;

	rgb = rgbtab;


	for (i=0; i<_transtabs; i++)
	{
		for (j=0; j<256; j++)
		{
			for (k=0; k<256; k++)
			{
				col = (int)((((float)palette[j].r * _transtab[i].left) + ((float)palette[k].r * _transtab[i].right)) / 100);
				if ( col > 255)
		      rgb->r = 255;
				else if ( col < 0)
		      rgb->r = 0;
				else
		      rgb->r = col;

				col = (int)((((float)palette[j].g * _transtab[i].left) + ((float)palette[k].g * _transtab[i].right)) / 100);
				if ( col > 255)
		      rgb->g = 255;
				else if ( col < 0)
		      rgb->g = 0;
				else
		      rgb->g = col;

				col = (int)((((float)palette[j].b * _transtab[i].left) + ((float)palette[k].b * _transtab[i].right)) / 100);
				if ( col > 255)
		      rgb->b = 255;
				else if ( col < 0)
		      rgb->b = 0;
				else
		      rgb->b = col;

				rgb++;
			}
		}
	}
}

int maketab( RGB *palette)
{
	NODES *nodes;
	NODE *node;
	DWORD id;
	RGB *rgb, *rgbtab;
	BYTE *tab;
	int i,j,colors;


	colors = (LIGHTLEVELS * 256 * _lighttabs);
	if( colors != 0)
	{
    if( (rgbtab = (RGB *)xmalloc( sizeof(RGB) * colors)) == NULL)
			return( FALSE);
		buildlighttab( palette, rgbtab);
    if ( !initcube( colors, 256, TREEDEPTH, 1))
		{
			xfree( rgbtab);
			return( FALSE);
		}
		if ( !buildtree24( rgbtab, colors))
		{
			xfree( rgbtab);
			return( FALSE);
		}
		reducetree( 254);
		buildpalette( &palette[1]);
		xfree( rgbtab);
	}

	colors = (256 * 256 * _transtabs);
	if( colors != 0)
	{
    if( (rgbtab = (RGB *)xmalloc( sizeof(RGB) * colors)) == NULL)
			return( FALSE);
		buildtranstab( palette, rgbtab);
    if ( !initcube( colors, 256, TREEDEPTH, 1))
		{
			xfree( rgbtab);
			return( FALSE);
		}
		if ( !buildtree24( rgbtab, colors))
		{
			xfree( rgbtab);
			return( FALSE);
		}
		reducetree( 254);
		buildpalette( &palette[1]);
		xfree( rgbtab);
	}

	colors = (LIGHTLEVELS * 256 * _lighttabs) + (256 * 256 * _transtabs);
  if( (rgbtab = (RGB *)xmalloc( sizeof(RGB) * colors)) == NULL)
		return( FALSE);

	buildlighttab( palette, &rgbtab[ 0]);
	buildtranstab( palette, &rgbtab[ (LIGHTLEVELS * 256 * _lighttabs)]);

	rgb = rgbtab;

	for( i=0; i<_lighttabs; i++)
	{
		tab = _lighttab[ i].lighttab;
		for( j=0; j<(LIGHTLEVELS * 256); j++)
	  {
	    node = cube.rootnode;

			while(1)
	    {
	      id = (rgb->r > node->mr ?1:0) | (rgb->g > node->mg ?1:0) << 1 | (rgb->b > node->mb ?1:0) << 2;
	      if( (node->census & (1 << id)) == 0)
	        break;
	      node = node->child[id];
	    }

	    cube.color.r = rgb->r;
	    cube.color.g = rgb->g;
	    cube.color.b = rgb->b;
	    cube.distance = (DWORD) (~0);
	    closestcolor(node->prev);
	    *(tab++) = cube.colnum + 1;
	    rgb++;
		}
	}

	for( i=0; i<_transtabs; i++)
	{
		tab = _transtab[ i].transtab;
		for( j=0; j<(256 * 256); j++)
	  {
	    node = cube.rootnode;

			while(1)
	    {
	      id = (rgb->r > node->mr ?1:0) | (rgb->g > node->mg ?1:0) << 1 | (rgb->b > node->mb ?1:0) << 2;
	      if( (node->census & (1 << id)) == 0)
	        break;
	      node = node->child[id];
	    }

	    cube.color.r = rgb->r;
	    cube.color.g = rgb->g;
	    cube.color.b = rgb->b;
	    cube.distance = (DWORD) (~0);
	    closestcolor(node->prev);
	    *(tab++) = cube.colnum + 1;
	    rgb++;
		}
	}

  do
  {
    nodes = cube.nodequeue->next;
    xfree( cube.nodequeue);
    cube.nodequeue = nodes;
  } while ( cube.nodequeue != NULL);

	return( TRUE);
}



