/*
 *
 * File:	p24to8.c
 * Project:	libpict 1.1
 * Date:	Fri, May 19, 1995
 * (c) SPDsoft 1992-95
 *
 */
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "pict.h"
#include "p24to8.h"

#ifndef __STDC__
#define const
#endif

static	int     r_mask,g_mask,b_mask;
static	int     n_bits_drop;
static	int     n_bits_left;

static	int     *colors;
static	int     n_colors;
static	int     *histogram;
static	int     h_size;
static	int	image_H,image_W;
static	byte    *lookup;

#define MAX_CT_SIZE	256

static	byte   c_map[MAX_CT_SIZE][3];

static	int	ct_size;
static	COLOR_RECT	*rect_list;
static	int		n_rects;

#ifdef  __STDC__
	Pict	pict_24_to_8_gray(Pict, int);
	Pict	pict_24_to_8_optimal(Pict, int);
	Pict	pict_24_to_8_chan(Pict, int, int);
#else   /* __STDC__ */
	Pict	pict_24_to_8_gray();
	Pict	pict_24_to_8_optimal();
	Pict	pict_24_to_8_chan();
#endif  /* __STDC__ */


#ifdef  __STDC__
Pict	pict_24_to_8(Pict pict_24,int mode, int bits, int num_colors)
#else   /* __STDC__ */
Pict	pict_24_to_8(pict_24,mode,bits,num_colors)
	Pict pict_24;int mode,bits,num_colors;
#endif  /* __STDC__ */
{
	Pict	pict_8;

	ct_size = num_colors > 256 ? 256 : num_colors ;

	switch(mode)
	{
		case GRAYSCALE:
			pict_8 = pict_24_to_8_gray(pict_24, bits);
			break;
		case OPTIMAL:
			pict_8 = pict_24_to_8_optimal(pict_24, bits);
			break;
		case M_ALPHA:
		case R_CHAN:
		case G_CHAN:
		case B_CHAN:
			pict_8 = pict_24_to_8_chan(pict_24, bits,mode);
			break;
		default:
			fprintf(stderr,"Modo de conversion desconocido\n");
			exit(1);
	}

	return pict_8;
}

#ifdef  __STDC__
Pict	pict_24_to_8_chan(Pict pict_24, int bits, int chan)
#else   /* __STDC__ */
Pict	pict_24_to_8_chan(pict_24,bits,chan)
	Pict pict_24;int bits,chan;
#endif  /* __STDC__ */
{
	Pict	pict_8;
	int	i,j;
	size_t	size;
	byte	r,g,b,a,*idx;

	pict_8 = (Pict)malloc(sizeof(PictStruct));
	pict_8->file_mode = P_WRITE;
	pict_8->clr_mode = M_MONO;
	pict_8->image_H = pict_height(pict_24);
	pict_8->image_W = pict_width(pict_24);

	size = (size_t)pict_8->image_W*(size_t)pict_8->image_H;
	pict_8->pixels = (byte *)malloc(size);

	idx = pict_8->pixels;
	for (j=0;j<pict_8->image_H;j++)
		for (i=0;i<pict_8->image_W;i++)
		{
			pict_pixel_rgba(pict_24,j,i,&r,&g,&b,&a);
			switch(chan)
			{
				case M_ALPHA:
					*idx++ = (ct_size-1)*(a/(double)255);
					break;
				case R_CHAN:
					*idx++ = (ct_size-1)*(r/(double)255);
					break;
				case G_CHAN:
					*idx++ = (ct_size-1)*(g/(double)255);
					break;
				case B_CHAN:
					*idx++ = (ct_size-1)*(b/(double)255);
					break;
			}
		}

	for (i=0; i<ct_size; i++)
	{
		if (chan==M_ALPHA||chan==R_CHAN)
			pict_8->map[i][0] = 255*(i/(double)(ct_size-1));
		else
			pict_8->map[i][0] = 0;
		if (chan==M_ALPHA||chan==G_CHAN)
			pict_8->map[i][1] = 255*(i/(double)(ct_size-1));
		else
			pict_8->map[i][1] = 0;
		if (chan==M_ALPHA||chan==B_CHAN)
			pict_8->map[i][2] = 255*(i/(double)(ct_size-1));
		else
			pict_8->map[i][2] = 0;
	}

	return pict_8;
}

#ifdef  __STDC__
Pict	pict_24_to_8_gray(Pict pict_24, int bits)
#else   /* __STDC__ */
Pict	pict_24_to_8_gray(pict_24,bits)
	Pict pict_24;int bits;
#endif  /* __STDC__ */
{
	Pict	pict_8;
	int	i,j;
	size_t	size;
	byte	r,g,b,a,*idx;

	pict_8 = (Pict)malloc(sizeof(PictStruct));
	pict_8->file_mode = P_WRITE;
	pict_8->clr_mode = M_MONO;
	pict_8->image_H = pict_height(pict_24);
	pict_8->image_W = pict_width(pict_24);

	size = (size_t)pict_8->image_W*(size_t)pict_8->image_H;
	pict_8->pixels = (byte *)malloc(size);

	if (pict_24->clr_mode==M_MONO && ct_size == 256)
	{
		memcpy((void *)pict_8->pixels,
			(void *)pict_24->pixels,(size_t)size);
		return pict_8;
	}

	idx = pict_8->pixels;
	for (j=0;j<pict_8->image_H;j++)
		for (i=0;i<pict_8->image_W;i++)
		{
			pict_pixel_rgba(pict_24,j,i,&r,&g,&b,&a);
			*idx++ = (byte)(ct_size-1)*
							((0.299*r + 0.587*g + 0.114*b)/(double)255);
		}

	for (i=0; i<ct_size; i++)
		for (j=0; j<3; j++)
			pict_8->map[i][j] = 255*(i/(double)(ct_size-1));

	return pict_8;
}

#ifdef  __STDC__
Pict	pict_24_to_8_optimal(Pict pict_24, int bits)
#else   /* __STDC__ */
Pict	pict_24_to_8_optimal(pict_24,bits)
	Pict pict_24;int bits;
#endif  /* __STDC__ */
{
	COLOR_RECT	*r1,*r2,*r3;
	Pict		pict_8;

	init_all(bits);

	calc_hist(pict_24,histogram);

	test_hist(histogram);

	n_colors = num_diff_colors(histogram);
	select_colors(histogram);

	if (n_colors<=ct_size)
	{
		build_table_1(colors);
	}
	else
	{
		rect_list = new_rect();
		init_list(rect_list,histogram,colors);
		do
		{
			head(&rect_list,&r1);
			if (r1->width>0)
			{
				split_rect(r1,&r2,&r3);
				insert(&rect_list,r2);
				insert(&rect_list,r3);
			}
			else
				append(&rect_list,r1);
		}
		while (n_rects<ct_size);
		build_table_2();
	}

	pict_8 = save_8bits(pict_24);
	free(histogram);
/*	free(lookup);*/
	free(colors);

	return pict_8;
}

/******************************************************************************/

#ifdef  __STDC__
void	init_all(int n)
#else   /* __STDC__ */
void	init_all( n)
	int n;
#endif  /* __STDC__ */
{
	register int	*h,i;

	n_bits_left = n;
	n_bits_drop = 8-n;
	h_size = 1<<(3*n_bits_left);

	if ( (histogram=(int *)malloc((size_t)h_size*sizeof(int))) == NULL )
		mem_out();
		
	for (h=histogram; h<histogram+h_size; *h++ = 0);

	for (i=0,r_mask=0;i<n_bits_left;i++) r_mask = (r_mask<<1)|1;
	r_mask <<= 2*n_bits_left;
	for (i=0,g_mask=0;i<n_bits_left;i++) g_mask = (g_mask<<1)|1;
	g_mask <<= n_bits_left;
	for (i=0,b_mask=0;i<n_bits_left;i++) b_mask = (b_mask<<1)|1;
}

/******************************************************************************/

#ifdef  __STDC__
void	calc_hist(Pict pict,int *h)
#else   /* __STDC__ */
void	calc_hist(pict,h)
	Pict pict; int *h;
#endif  /* __STDC__ */
{
	byte	r,g,b,a;
	int	color;
	int	i,j;

	image_H = pict_height(pict);
	image_W = pict_width(pict);

	for (j=0; j<image_H; j++)
	{
		for (i=0; i<image_W; i++)
		{
			pict_pixel_rgba(pict,j,i,&r,&g,&b,&a);
			color = ((((r)>>n_bits_drop) << 2*n_bits_left) |
				 (((g)>>n_bits_drop) << n_bits_left) |
				 (((b)>>n_bits_drop)));
			h[color]++;
		}
	}
}

/******************************************************************************/

#ifdef  __STDC__
void	test_hist(int *h)
#else   /* __STDC__ */
void	test_hist(h)
	int *h;
#endif  /* __STDC__ */
{
	register int	i;
	register long	sum = 0;

	for (i=0; i<h_size; i++) sum += *h++;
	if (sum!=image_H*image_W)
	{
		fprintf(stderr,"Error en test_hist\n");
		exit(1);
	}
}

/******************************************************************************/

#ifdef  __STDC__
int	num_diff_colors(int *h)
#else   /* __STDC__ */
int	num_diff_colors(h)
	int *h;
#endif  /* __STDC__ */
{
	register int	i,n=0;

	for (i=0;i<h_size;i++) if (*h++ != 0) n++;

	return n;
}

/******************************************************************************/

#ifdef  __STDC__
void	select_colors(int *h)
#else   /* __STDC__ */
void	select_colors(h)
	int *h;
#endif  /* __STDC__ */
{
	register int	i,*c;

	if ( (colors=(int *)malloc(n_colors*sizeof(int))) == NULL ) mem_out();

	c = colors;
	for (i=0; i<h_size; i++)
		if (*h++) *c++ = i;
}

/******************************************************************************/

#ifdef  __STDC__
void	build_table_1(int *c)
#else   /* __STDC__ */
void	build_table_1(c)
	int *c;
#endif  /* __STDC__ */
{
	register int	i;
	int	icolor;
	
	lookup = (byte *)histogram;

	icolor = (1<<n_bits_left)-1;
	for (i=0; i<n_colors; i++,c++)
	{
		c_map[i][0] = 255*((double)RED(*c)/(double)icolor);
		c_map[i][1] = 255*((double)GREEN(*c)/(double)icolor);
		c_map[i][2] = 255*((double)BLUE(*c)/(double)icolor);
		lookup[*c]=i;
	}
	icolor = i;
	for(; i<ct_size; i++)
	{
		c_map[i][0] =
		c_map[i][1] =
		c_map[i][2] = (byte)255*(i-icolor)/(ct_size-icolor);
	}
}

/******************************************************************************/

COLOR_RECT *new_rect()
{
	COLOR_RECT	*p;

	if ( (p=(COLOR_RECT *)malloc(sizeof(COLOR_RECT))) == NULL ) mem_out();
	p->next = NULL;

	return p;
}

/******************************************************************************/

#ifdef  __STDC__
void	init_list(COLOR_RECT *list,int *h,int *c)
#else   /* __STDC__ */
void	init_list(list,h,c)
	COLOR_RECT *list;int *h,*c;
#endif  /* __STDC__ */
{
	register int	i;
	register long	sum;

	list->first=0;
	list->last=n_colors-1;

	for (i=0,sum=0; i<n_colors; i++) sum+= h[*c++];
	list->hist_sum = sum;
	find_min_max(list);

	n_rects=1;
}

/******************************************************************************/

#ifdef  __STDC__
void	head(COLOR_RECT **list,COLOR_RECT **head_ptr)
#else   /* __STDC__ */
void	head(list,head_ptr)
	COLOR_RECT **list,**head_ptr;
#endif  /* __STDC__ */
{
	*head_ptr = *list;
	*list = (*list)->next;
	n_rects--;
}

/******************************************************************************/

#ifdef  __STDC__
void	insert(COLOR_RECT **list,COLOR_RECT *new)
#else   /* __STDC__ */
void	insert(list,new)
	COLOR_RECT **list,*new;
#endif  /* __STDC__ */
{
	register COLOR_RECT	**ele,*next;

	if (new->width == 0)
	{
		append(list,new);
		return;
	}

	ele = list;
	while (*ele != NULL)
	{
		if ((*ele)->hist_sum < new->hist_sum) break;
		ele = &((*ele)->next);
	}
	next = *ele;
	*ele = new;
	(*ele)->next = next;

	n_rects++;
}

/******************************************************************************/

#ifdef  __STDC__
void	append(COLOR_RECT **list,COLOR_RECT *ele)
#else   /* __STDC__ */
void	append(list,ele)
	COLOR_RECT **list,*ele;
#endif  /* __STDC__ */
{
	register COLOR_RECT	**last;

	last = list;
	while (*last != NULL) last = &((*last)->next);
	*last = ele;
	(*last)->next = NULL;

	n_rects++;
}

/******************************************************************************/

#ifdef  __STDC__
void	split_rect(COLOR_RECT *crect,COLOR_RECT **r1,COLOR_RECT **r2)
#else   /* __STDC__ */
void	split_rect(crect,r1,r2)
	COLOR_RECT *crect,**r1,**r2;
#endif  /* __STDC__ */
{
	int	half;
	long	sum;
	COLOR_RECT *r;

	sort_list(colors,crect->first,crect->last,crect->widest);
	if (crect->width == 1)
	{
		half = crect->first;
		sum = histogram[colors[crect->first]];
	}
	else
	{
		half = find_half(colors,histogram,
				 crect->first,crect->last,
				 crect->widest,
				 crect->hist_sum/2,&sum);
	}

	*r2 = new_rect();

	r = *r2;
	r->first = half+1;
	r->last  = crect->last;
	r->hist_sum = crect->hist_sum-sum;
	find_min_max(r);

	*r1 = crect;
	r = *r1;
	r->last  = half;
	r->hist_sum = sum;
	find_min_max(r);
}

/******************************************************************************/

#ifdef  __STDC__
int	comp_r(const void *a,const void *b)
#else   /* __STDC__ */
int	comp_r(a,b)
	const void *a,*b;
#endif  /* __STDC__ */
{
	return RED(*((int *)a))-RED(*((int *)b));
}

/******************************************************************************/

#ifdef  __STDC__
int	comp_g(const void *a,const void *b)
#else   /* __STDC__ */
int	comp_g(a,b)
	const void *a,*b;
#endif  /* __STDC__ */
{
	return GREEN(*((int *)a))-GREEN(*((int *)b));
}

/******************************************************************************/

#ifdef  __STDC__
int	comp_b(const void *a,const void *b)
#else   /* __STDC__ */
int	comp_b(a,b)
	const void *a,*b;
#endif  /* __STDC__ */
{
	return BLUE(*((int *)a)) - BLUE(*((int *)b));
}

/******************************************************************************/

#ifdef  __STDC__
void	sort_list(int *list,long from,long to,byte cual)
#else   /* __STDC__ */
void	sort_list(list,from,to,cual)
	int *list;long from,to;byte cual;
#endif  /* __STDC__ */
{
	if (from>=to) return;
	switch(cual)
	{
		case 0:	qsort((void *)&list[from],to-from+1,sizeof(int),comp_r);
			break;
		case 1:	qsort((void *)&list[from],to-from+1,sizeof(int),comp_g);
			break;
		case 2:	qsort((void *)&list[from],to-from+1,sizeof(int),comp_b);
			break;
		default: fprintf(stderr,"Error: widest fuera de rango.\n");
			 exit(1);
	}
}

/******************************************************************************/

#ifdef  __STDC__
int	find_half(
			int	*c,
			int	*h,
			long	from,
			long	to,
			byte	idx,
			long	sum2,
			long	*s1)
#else   /* __STDC__ */
int	find_half(c,h,from,to,idx,sum2,s1)
	int	*c,*h;
	long	from,to;
	byte	idx;
	long	sum2,*s1;
#endif  /* __STDC__ */
{
	int	i,half,up,down;
	long	sum;
	int	r,g,b;

	half = from;
	sum2 -= h[c[half]];
	while (half<to-1 && sum2>0) sum2 -= h[c[++half]];

	switch(idx)
	{
		case 0: r = RED(c[half]);
			for (up=half; up<to-1 && RED(c[up])==r; up++);
			for (down=half; down>from && RED(c[down])==r; down--);
			break;
		case 1: g = GREEN(c[half]);
			for (up=half; up<to-1 && GREEN(c[up])==g; up++);
			for (down=half; down>from && GREEN(c[down])==g; down--);
			break;
		case 2: b = BLUE(c[half]);
			for (up=half; up<to-1 && BLUE(c[up])==b; up++);
			for (down=half; down>from && BLUE(c[down])==b; down--);
			break;
		default:
			fprintf(stderr,"IDX desconocido para dividir\n");
			exit(1);
	}
	if ( (up-half)<(half-down) ) half = up;
	else half = down;
	for (i=from,sum=0; i<=half; i++) sum += h[c[i]];
	*s1 = sum;
	return half;
}

/******************************************************************************/

#ifdef  __STDC__
void	find_min_max(COLOR_RECT *crect)
#else   /* __STDC__ */
void	find_min_max(crect)
	COLOR_RECT *crect;
#endif  /* __STDC__ */
{

	register int	*c;
	register byte	maxr,maxg,maxb;
	register byte	minr,ming,minb;
	register byte 	r,g,b;
	short	wr,wg,wb;

	maxr = maxg = maxb = 0;
	minr = ming = minb = 255;

	for (c=colors+crect->first; c<=colors+crect->last; c++)
	{
		r = RED(*c);
		g = GREEN(*c);
		b = BLUE(*c);
		maxr = MAX(maxr,r);
		maxg = MAX(maxg,g);
		maxb = MAX(maxb,b);
		minr = MIN(minr,r);
		ming = MIN(ming,g);
		minb = MIN(minb,b);
	}

	crect->r_min = minr;
	crect->g_min = ming;
	crect->b_min = minb;
	crect->r_max = maxr;
	crect->g_max = maxg;
	crect->b_max = maxb;

	wr = maxr - minr;
	wg = maxg - ming;
	wb = maxb - minb;

	if (wr>=wg)
	{
		if (wr>=wb) crect->widest = 0,crect->width = wr;
		else	    crect->widest = 2,crect->width = wb;
	}
	else
	{
		if (wg>=wb) crect->widest = 1,crect->width = wg;
		else	    crect->widest = 2,crect->width = wb;
	}
}

/******************************************************************************/

#ifdef  __STDC__
void	average_color(COLOR_RECT *crect,int *h,int *c)
#else   /* __STDC__ */
void	average_color(crect,h,c)
	COLOR_RECT *crect;int *h,*c;
#endif  /* __STDC__ */
{
	register float	r,g,b;
	register int	i;

	r = g = b = 0.0;
	c += crect->first;
	for (i=crect->first; i<=crect->last; i++,c++)
	{
		r += RED(*c)*h[*c];
		g += GREEN(*c)*h[*c];
		b += BLUE(*c)*h[*c];
	}
	crect->r = r/(float)crect->hist_sum;
	crect->g = g/(float)crect->hist_sum;
	crect->b = b/(float)crect->hist_sum;
}

/******************************************************************************/

void	build_table_2()
{
	COLOR_RECT *l;
	byte	r,g,b;
	double	 fr,fg,fb;
	int	 i,icolor,rgb;

	icolor = (1<<n_bits_left)-1;
	for (l=rect_list,i=0; l!=NULL; l=l->next,i++)
	{
		average_color(l,histogram,colors);
		fr = l->r/(float)icolor;
		fg = l->g/(float)icolor;
		fb = l->b/(float)icolor;
		if (fr>=1.0) r=255;
		else if (fr<=0.0) r=0;
		else r = (byte)(255*fr);
		if (fg>=1.0) g=255;
		else if (fg<=0.0) g=0;
		else g = (byte)(255*fg);
		if (fb>=1.0) b=255;
		else if (fb<=0.0) b=0;
		else b = (byte)(255*fb);
		c_map[i][0] = r;
		c_map[i][1] = g;
		c_map[i][2] = b;
	}

	lookup = (byte *)histogram;

	for (l=rect_list,icolor=0; l!=NULL; l=l->next,icolor++)
	{
		for (r=l->r_min;r<=l->r_max;r++)
		{
			for (g=l->g_min;g<=l->g_max;g++)
			{
				for (b=l->b_min;b<=l->b_max;b++)
				{
				 	rgb = ((r << 2*n_bits_left) |
					(g <<   n_bits_left) | (b));
					lookup[rgb]=icolor;
				}
			}
		}
	}
}

/******************************************************************************/

#ifdef  __STDC__
Pict	save_8bits(Pict pict_24)
#else   /* __STDC__ */
Pict	save_8bits(pict_24)
	Pict pict_24;
#endif  /* __STDC__ */
{
	Pict	f8;
	int	i,j;
	int	icolor;
	byte	r,g,b,a,*idx;
/*	byte	*pix;*/

	f8 = (Pict)malloc(sizeof(PictStruct));
	f8->file_mode = P_WRITE;
	f8->clr_mode = M_RGB8;
	f8->n_comp = 1;
	f8->image_H = pict_height(pict_24);
	f8->image_W = pict_width(pict_24);

	f8->pixels = (byte *)calloc((size_t)f8->image_W,(size_t)f8->image_H);
	idx = f8->pixels;
/*	pix = pict_pixels(pict_24);*/

	for (j=0;j<f8->image_H;j++)
	{
		for (i=0;i<f8->image_W;i++)
		{
/*			r = *pix++;*/
/*			g = *pix++;*/
/*			b = *pix++;*/
			pict_pixel_rgba(pict_24,j,i,&r,&g,&b,&a);
			icolor = (((r)>>n_bits_drop)<<2*n_bits_left) |
				 (((g)>>n_bits_drop)<<  n_bits_left) |
				  ((b)>>n_bits_drop);
			*idx++ = lookup[icolor];
/*			if (pict_24->clr_mode==M_RGBA32) pix++;*/
		}
	}

	for (i=0; i<ct_size; i++)
		for (j=0; j<3; j++)
			f8->map[i][j] = c_map[i][j];

	return f8;
}

/******************************************************************************/

void	mem_out()
{
	fprintf(stderr,"Error de reserva de memoria.\n");
	exit(1);
}