/* pbm color utility library
**
** Copyright (C) 1988 by Jef Poskanzer.
**
** Permission to use, copy, modify, and distribute this software and its
** documentation for any purpose and without fee is hereby granted, provided
** that the above copyright notice appear in all copies and that both that
** copyright notice and this permission notice appear in supporting
** documentation.  This software is provided "as is" without express or
** implied warranty.
*/

/* modified by Günther Röhrich */
/* WARNING: This file is not for use with normal pbm programs */

/* support functions for the ppm color stuff */

#include "ppm.h"
#include "ppm2AGA.h"
#include "libpbm.h"
#include "libppm.h"
#include "libpgm.h"


#define HASH_SIZE 20023

#ifdef PPM_PACKCOLORS
#define ppm_hashpixel(p) ( ( (int) (p) & 0x7fffffff ) % HASH_SIZE )
#else /*PPM_PACKCOLORS*/
#define ppm_hashpixel(p) ( ( ( (long) (PPM_GETR(p)>>cluster) * 33023\
 + (long) (PPM_GETG(p)>>cluster) * 30013 +\
 ((long) PPM_GETB(p)>>cluster) * 27011 ) & 0x7fffffff ) % HASH_SIZE )

#endif /*PPM_PACKCOLORS*/

#define C_EQUAL(p,q) ( ((p).r>>cluster==(q).r>>cluster) &&\
((p).g>>cluster==(q).g>>cluster) && ((p).b>>cluster==(q).b>>cluster) )

extern int AbortCheck(void);

typedef struct box* box_vector;

struct box
    {
    int ind;
    int colors;
    int sum;
    };

static int
redcompare( ch1, ch2 )
    colorhist_vector ch1, ch2;
    {
    return (int) PPM_GETR( ch1->color ) - (int) PPM_GETR( ch2->color );
    }

static int
greencompare( ch1, ch2 )
    colorhist_vector ch1, ch2;
    {
    return (int) PPM_GETG( ch1->color ) - (int) PPM_GETG( ch2->color );
    }

static int
bluecompare( ch1, ch2 )
    colorhist_vector ch1, ch2;
    {
    return (int) PPM_GETB( ch1->color ) - (int) PPM_GETB( ch2->color );
    }

static int
sumcompare( b1, b2 )
    box_vector b1, b2;
    {
    return b2->sum - b1->sum;
    }

colorhist_vector
ppm_fcomputecolorhist(FILE *pixels, int cols, int rows,
                  int maxcolors, int *colorsP, int ColorShift, int cluster)
    {
    colorhash_table cht;
    colorhist_vector chv;

    cht = ppm_fcomputecolorhash( pixels, cols, rows, maxcolors,
                                 colorsP, ColorShift, cluster);
    if ( cht == (colorhash_table) 0 )
	return (colorhist_vector) 0;
    chv = ppm_fcolorhashtocolorhist( cht, maxcolors, cluster);
    ppm_freecolorhash( cht );
    return chv;
    }


colorhash_table
ppm_fcomputecolorhash(FILE *pixels, int cols, int rows, 
                      int maxcolors, int *colorsP, int ColorShift, int cluster)
  {
    colorhash_table cht;
    register pixel* pP;
    colorhist_list chl;
    int col, row, hash;

    cht = ppm_alloccolorhash( );
    *colorsP = 0;

    /* Go through the entire image, building a hash table of colors. */
    for ( row = 0; row < rows; ++row )
    {
      if(AbortCheck())
      {
        ppm_freecolorhash(cht);
        pm_error("^C\n");
      }
      for ( col = 0, pP = next_pixrow(pixels, row, ColorShift); col < cols; ++col, ++pP )
      {            
        hash = ppm_hashpixel( *pP );
	for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
	  if ( C_EQUAL( chl->ch.color, *pP ) ) break;
	if ( chl != (colorhist_list) 0 )
          ++(chl->ch.value);
	else
	{
	  if ( ++(*colorsP) > maxcolors )
	  {
	    ppm_freecolorhash( cht );
	    return (colorhash_table) 0;
	  }
	  chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
	  if ( chl == 0 )
          {
            ppm_freecolorhash(cht);
	    pm_error( "out of memory computing hash table\n" );
          }
	  chl->ch.color = *pP;
	  chl->ch.value = 1;
	  chl->next = cht[hash];
	  cht[hash] = chl;
	}
      }
    }
    return cht;
  }

colorhash_table
ppm_alloccolorhash( )
    {
    colorhash_table cht;
    int i;

    cht = (colorhash_table) malloc( HASH_SIZE * sizeof(colorhist_list) );
    if ( cht == 0 )
	pm_error( "out of memory allocating hash table\n" );

    for ( i = 0; i < HASH_SIZE; ++i )
	cht[i] = (colorhist_list) 0;

    return cht;
    }

colorhist_vector
ppm_fcolorhashtocolorhist(colorhash_table cht,int  maxcolors,int cluster)
    {
    colorhist_vector chv;
    colorhist_list chl;
    int i, j;

    /* Now collate the hash table into a simple colorhist array. */
    chv = (colorhist_vector) malloc( maxcolors * sizeof(struct colorhist_item) );
    /* (Leave room for expansion by caller.) */
    if ( chv == (colorhist_vector) 0 )
        {
        ppm_freecolorhash(cht);
	pm_error( "out of memory generating histogram\n" );
        }

    /* Loop through the hash table. */
    j = 0;
    for ( i = 0; i < HASH_SIZE; ++i )
	for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chl->next )
	    {
	    /* Add the new entry. */
	    chv[j] = chl->ch;
	    ++j;
	    }

    /* All done. */
    return chv;
    }

void
ppm_freecolorhist( chv )
    colorhist_vector chv;
    {
    free( (char*) chv );
    }

void
ppm_freecolorhash( cht )
    colorhash_table cht;
    {
    int i;
    colorhist_list chl, chlnext;

    for ( i = 0; i < HASH_SIZE; ++i )
	for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chlnext )
	    {
	    chlnext = chl->next;
	    free( (char*) chl );
	    }
    free( (char*) cht );
    }



int
ppm_lookupcolor( cht, colorP )
    colorhash_table cht;
    pixel* colorP;
    {
    int hash;
    colorhist_list chl;
    int cluster = 0;

    hash = ppm_hashpixel( *colorP );
    for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
	if ( PPM_EQUAL( chl->ch.color, *colorP ) )
	    return chl->ch.value;

    return -1;
    }

int
ppm_addtocolorhash( cht, colorP, value )
    colorhash_table cht;
    pixel* colorP;
    int value;
    {
    register int hash;
    register colorhist_list chl;
    int cluster = 0;

    chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
    if ( chl == 0 )
	return -1;
    hash = ppm_hashpixel( *colorP );
    chl->ch.color = *colorP;
    chl->ch.value = value;
    chl->next = cht[hash];
    cht[hash] = chl;
    return 0;
    }


/*
** Here is the fun part, the median-cut colormap generator.  This is based
** on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
** Display", SIGGRAPH '82 Proceedings, page 297.
*/

colorhist_vector
mediancut( colorhist_vector chv, int colors, int sum, pixval maxval, int newcolors )
    {
    colorhist_vector colormap;
    box_vector bv;
    register int bi, i;
    int boxes;

    bv = (box_vector) malloc( sizeof(struct box) * newcolors );
    colormap =
	(colorhist_vector) malloc( sizeof(struct colorhist_item) * newcolors );
    if ( bv == (box_vector) 0 || colormap == (colorhist_vector) 0 )
	pm_error( "out of memory" );
    for ( i = 0; i < newcolors; ++i )
	PPM_ASSIGN( colormap[i].color, 0, 0, 0 );

    /*
    ** Set up the initial box.
    */
    bv[0].ind = 0;
    bv[0].colors = colors;
    bv[0].sum = sum;
    boxes = 1;

    /*
    ** Main loop: split boxes until we have enough.
    */
    while ( boxes < newcolors )
	{
	register int indx, clrs;
	int sm;
	register int minr, maxr, ming, maxg, minb, maxb, v;
	int halfsum, lowersum;

	/*
	** Find the first splittable box.
	*/
	for ( bi = 0; bi < boxes; ++bi )
	    if ( bv[bi].colors >= 2 )
		break;
	if ( bi == boxes )
	    break;	/* ran out of colors! */
	indx = bv[bi].ind;
	clrs = bv[bi].colors;
	sm = bv[bi].sum;

	/*
	** Go through the box finding the minimum and maximum of each
	** component - the boundaries of the box.
	*/
	minr = maxr = PPM_GETR( chv[indx].color );
	ming = maxg = PPM_GETG( chv[indx].color );
	minb = maxb = PPM_GETB( chv[indx].color );
	for ( i = 1; i < clrs; ++i )
	    {
	    v = PPM_GETR( chv[indx + i].color );
	    if ( v < minr ) minr = v;
	    if ( v > maxr ) maxr = v;
	    v = PPM_GETG( chv[indx + i].color );
	    if ( v < ming ) ming = v;
	    if ( v > maxg ) maxg = v;
	    v = PPM_GETB( chv[indx + i].color );
	    if ( v < minb ) minb = v;
	    if ( v > maxb ) maxb = v;
	    }

	/*
	** Find the largest dimension, and sort by that component.  I have
	** included two methods for determining the "largest" dimension;
	** first by simply comparing the range in RGB space, and second
	** by transforming into luminosities before the comparison.  You
	** can switch which method is used by switching the commenting on
	** the LARGE_ defines at the beginning of this source file.
	*/
#ifdef LARGE_NORM
	if ( maxr - minr >= maxg - ming && maxr - minr >= maxb - minb )
	    qsort(
		(char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
		redcompare );
	else if ( maxg - ming >= maxb - minb )
	    qsort(
		(char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
		greencompare );
	else
	    qsort(
		(char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
		bluecompare );
#endif /*LARGE_NORM*/
#ifdef LARGE_LUM
	{
	pixel p;
	float rl, gl, bl;

	PPM_ASSIGN(p, maxr - minr, 0, 0);
	rl = PPM_LUMIN(p);
	PPM_ASSIGN(p, 0, maxg - ming, 0);
	gl = PPM_LUMIN(p);
	PPM_ASSIGN(p, 0, 0, maxb - minb);
	bl = PPM_LUMIN(p);

	if ( rl >= gl && rl >= bl )
	    qsort(
		(char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
		redcompare );
	else if ( gl >= bl )
	    qsort(
		(char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
		greencompare );
	else
	    qsort(
		(char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
		bluecompare );
	}
#endif /*LARGE_LUM*/
	
	/*
	** Now find the median based on the counts, so that about half the
	** pixels (not colors, pixels) are in each subdivision.
	*/
	lowersum = chv[indx].value;
	halfsum = sm / 2;
	for ( i = 1; i < clrs - 1; ++i )
	    {
	    if ( lowersum >= halfsum )
		break;
	    lowersum += chv[indx + i].value;
	    }

	/*
	** Split the box, and sort to bring the biggest boxes to the top.
	*/
	bv[bi].colors = i;
	bv[bi].sum = lowersum;
	bv[boxes].ind = indx + i;
	bv[boxes].colors = clrs - i;
	bv[boxes].sum = sm - lowersum;
	++boxes;
	qsort( (char*) bv, boxes, sizeof(struct box), sumcompare );
	}

    /*
    ** Ok, we've got enough boxes.  Now choose a representative color for
    ** each box.  There are a number of possible ways to make this choice.
    ** One would be to choose the center of the box; this ignores any structure
    ** within the boxes.  Another method would be to average all the colors in
    ** the box - this is the method specified in Heckbert's paper.  A third
    ** method is to average all the pixels in the box.  You can switch which
    ** method is used by switching the commenting on the REP_ defines at
    ** the beginning of this source file.
    */
    for ( bi = 0; bi < boxes; ++bi )
	{
#ifdef REP_CENTER_BOX
	register int indx = bv[bi].ind;
	register int clrs = bv[bi].colors;
	register int minr, maxr, ming, maxg, minb, maxb, v;

	minr = maxr = PPM_GETR( chv[indx].color );
	ming = maxg = PPM_GETG( chv[indx].color );
	minb = maxb = PPM_GETB( chv[indx].color );
	for ( i = 1; i < clrs; ++i )
	    {
	    v = PPM_GETR( chv[indx + i].color );
	    minr = min( minr, v );
	    maxr = max( maxr, v );
	    v = PPM_GETG( chv[indx + i].color );
	    ming = min( ming, v );
	    maxg = max( maxg, v );
	    v = PPM_GETB( chv[indx + i].color );
	    minb = min( minb, v );
	    maxb = max( maxb, v );
	    }
	PPM_ASSIGN(
	    colormap[bi].color, ( minr + maxr ) / 2, ( ming + maxg ) / 2,
	    ( minb + maxb ) / 2 );
#endif /*REP_CENTER_BOX*/
#ifdef REP_AVERAGE_COLORS
	register int indx = bv[bi].ind;
	register int clrs = bv[bi].colors;
	register long r = 0, g = 0, b = 0;

	for ( i = 0; i < clrs; ++i )
	    {
	    r += PPM_GETR( chv[indx + i].color );
	    g += PPM_GETG( chv[indx + i].color );
	    b += PPM_GETB( chv[indx + i].color );
	    }
	r = r / clrs;
	g = g / clrs;
	b = b / clrs;
	PPM_ASSIGN( colormap[bi].color, r, g, b );
#endif /*REP_AVERAGE_COLORS*/
#ifdef REP_AVERAGE_PIXELS
	register int indx = bv[bi].ind;
	register int clrs = bv[bi].colors;
	register long r = 0, g = 0, b = 0, sum = 0;

	for ( i = 0; i < clrs; ++i )
	    {
	    r += PPM_GETR( chv[indx + i].color ) * chv[indx + i].value;
	    g += PPM_GETG( chv[indx + i].color ) * chv[indx + i].value;
	    b += PPM_GETB( chv[indx + i].color ) * chv[indx + i].value;
	    sum += chv[indx + i].value;
	    }
	r = r / sum;
	if ( r > maxval ) r = maxval;	/* avoid math errors */
	g = g / sum;
	if ( g > maxval ) g = maxval;
	b = b / sum;
	if ( b > maxval ) b = maxval;
	PPM_ASSIGN( colormap[bi].color, r, g, b );
#endif /*REP_AVERAGE_PIXELS*/
	}

    /*
    ** All done.
    */
    return colormap;
    }