 /*
  * Khoros: $Id: lvgamut.c,v 1.3 1992/03/20 23:05:34 dkhoros Exp $
  */

#if !defined(lint) && !defined(SABER)
static char rcsid[] = "Khoros: $Id: lvgamut.c,v 1.3 1992/03/20 23:05:34 dkhoros Exp $";
#endif

 /*
  * $Log: lvgamut.c,v $
 * Revision 1.3  1992/03/20  23:05:34  dkhoros
 * VirtualPatch5
 *
  */

/*
 *----------------------------------------------------------------------
 *
 * Copyright 1991, University of New Mexico.  All rights reserved.
 * Permission to copy and modify this software and its documen-
 * tation only for internal use in your organization is hereby
 * granted, provided that this notice is retained thereon and
 * on all copies.  UNM makes no representations as to the sui-
 * tability and operability of this software for any purpose.
 * It is provided "as is" without express or implied warranty.
 * 
 * UNM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FIT-
 * NESS.  IN NO EVENT SHALL UNM BE LIABLE FOR ANY SPECIAL,
 * INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY OTHER DAMAGES WHAT-
 * SOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
 * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PER-
 * FORMANCE OF THIS SOFTWARE.
 * 
 * No other rights, including, for example, the right to redis-
 * tribute this software and its documentation or the right to
 * prepare derivative works, are granted unless specifically
 * provided in a separate license agreement.
 *---------------------------------------------------------------------
 */

#include "unmcopyright.h"        /* Copyright 1991 by UNM */

/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 >>>>
 >>>>         File Name: lvgamut.c
 >>>>
 >>>>      Program Name: vgamut
 >>>>
 >>>> Date Last Updated: Sat Aug 24 21:24:10 1991 
 >>>>
 >>>>          Routines: lvgamut - the library call for vgamut
 >>>>
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>   <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/


#include "vinclude.h"


/* -library_includes */
/*
*              This routine uses a modification of Heckbert's
*              median cut algorithm: Ref: P. Heckbert,
*              "Color Image Quantization for Frame Buffer Display",
*              Computer Graphics, Vol. 16, No. 3, July 1982,
*              p297.
*/

/* The following function is the hash function for indexing into the
   list of color caches */
#define f(r,g,b) (chopt[r] << 2*nchbits) | (chopt[g] << nchbits) | chopt[b]

struct color
  {
    unsigned char r;                      /* Color values */
    unsigned char g;
    unsigned char b;
    int clr;                              /* Packed color */
    int count;                            /* Pixel count */
    struct color *prev;                   /* Ptrs to previous & next color */
    struct color *next;
    struct pixel *pixlist;                /* List of pixels of this color */
    struct pixel *pixtail;                /* End of pixel list */
  };

struct pixel
  {
/* The following line replaces the next one */
    unsigned int offset;
/*    unsigned short x,y;   */                /* Location of pixel */
    struct pixel *next;                   /* Pointer to next one */
  };

/* Note: MAX_CHANLS must be of the form 2^(3*n), n an integer! */
#define MAX_CHANLS 262144                 /* Max number of hash indices */
#define MAX_CHANL_BITS 18                 /* Log base 2 of MAX_CHANLS */
int nchanls;                              /* Number of hash indices */
int nchbits;                              /* Number of bits USED for hash, per band */
struct color *chead,*ctail;               /* Composite color list */
struct color **ch,**ct;                   /* Hash index color lists */

struct box
  {
    unsigned char rmin,rmax;              /* Bounds on box */
    unsigned char gmin,gmax;
    unsigned char bmin,bmax;
    struct color *colors;                 /* List of colors in box */
    struct box *next;                     /* Next box */
    int count;                            /* Number of colors in box */
  };

struct box *boxhead,*boxtail;

struct pixel *pixpile,*pixels;            /* Pointers to pixel area */
#define pmalloc() pixpile++               /* Pixel handout function */

#define MAX_CBLOCKS 2048                  /* Max number of color blocks */
#define CNUM 2048                         /* Number of colors/block */
struct color *cblock[MAX_CBLOCKS];        /* Color block pointer array */
int cbcount,ccount;                       /* Color block count, colors/block*/

int hash;                                 /* Global hash index */
unsigned char rshift[256];                /* Shift tables */
unsigned char lshift[256];                /* Shift tables */
unsigned char chopt[256];                 /* Chop tables */

static int sort_cmaps();
/* -library_includes_end */


/****************************************************************
*
* Routine Name: lvgamut - library call for vgamut
*
* Purpose:
*    
*    Compress true 3-band (24-bit) images to N-plane pseudo color
*    
*    

* Input:
*    
*    image          pointer to xvimage structure to be processed
*    
*    ncolors        number of colors allowed in the output image
*    
*    bits           number of bits of precision  for  the  color  pre-
*                   quantization
*    
*    fraction       allocation ratio of color split  methods.  0.0  is
*                   population, 1.0 is subspace 2-norm.
*    
*    

* Output:
*    
*    image          holds the result of  the  operation.   The  output
*                   data type is the same as the input data type.
*    
*    Return Value:  1 on success, 0 on failure.
*    
*    

*
* Written By: Scott Wilson
*    
*    Jeremy Worley Fri Aug  2 11:18:33 CDT 1991
*                                            Cast operations in an abs
*                                            to signed to prevent core
*                                            dumps due to  a  weakness
*                                            in   code   generated  by
*                                            Cray's scc compiler.
*    
*    Scott Wilson, Sat Aug 24 1991           Added diagnostic  message
*                                            for  the number of colors
*                                            found in the image.
*    
*    

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


/* -library_def */
int
lvgamut(image,ncolors,bits,fraction)
struct xvimage *image;
int bits;
int ncolors;
float fraction;
/* -library_def_end */

/* -library_code */
  {
    int shift;                            /* Shift distance for precision */
    int chop;                             /* Shift distance for hash size */
    int i;

    /* Initialize variables used for fast dynamic memory handouts */
    cbcount = 0;
    ccount = 0;
    pixels = (struct pixel *)malloc(image->row_size*image->col_size*
                                     sizeof(struct pixel));
    if (pixels == NULL)
      {
        fprintf(stderr,"lvgamut: cannot allocate pixel space!\n");
        exit(0);
      }
    pixpile = pixels;

    /* Build shift and chop tables */
    nchbits = bits;
    if (nchbits > MAX_CHANL_BITS/3) nchbits = MAX_CHANL_BITS/3;
    shift = 8-bits;                   /* Get shift distance */
    chop  = bits-nchbits;             /* Get chop distance */
    if (chop < 0) chop = 0;           /* Force lower bound */
    nchanls = pow((double)2.0,(double)(3.0*nchbits)); /* Compute  number of indices */
    for (i=0; i<256; i++)
      {
        lshift[i] = i << shift;
        rshift[i] = i >> shift;
        chopt[i] = i >> chop;
      }

    load_color_list(image);            /* Make color list */
    compress_colors(&ncolors,fraction); /* Squeeze the color list */
    gamut_adjust_image(image,ncolors);       /* Make squeezed image */
    free_colors();                     /* Give back all memory */

    return(1);                         /* success, BUT other routines exit() */
  }

load_color_list(image)                 /* Build the color list */
struct xvimage *image;
  {
    register int clr;
    register struct color *pc;
    register unsigned char *p1,*p2,*p3;
    register int i,j;
    unsigned char r,g,b;
    struct color *cmalloc();
    char *malloc();

    chead = NULL;                         /* Initialize color list */
    ctail = NULL;

    /* Allocate space for hash index lists */
    
    ch = (struct color **)malloc(nchanls*sizeof(struct color *));
    ct = (struct color **)malloc(nchanls*sizeof(struct color *));
    if (ch == NULL || ct == NULL)
      {
        (void)fprintf(stderr,"lvgamut: Unable to allocate hash lists!\n");
        exit(1);
      }
    bzero(ch,nchanls*sizeof(struct color *));
    bzero(ct,nchanls*sizeof(struct color *));

    p1 = (unsigned char *)(&image->imagedata[0]);
    p2 = (unsigned char *)(&image->imagedata[image->row_size*image->col_size]);
    p3 = (unsigned char *)(&image->imagedata[2*image->row_size*image->col_size]);

    for (j=0; j<image->col_size; j++)
      {
        for (i=0; i<image->row_size; i++)
          {
            r = rshift[(int)(*p1++)];                       /* Quantize */
            g = rshift[(int)(*p2++)];
            b = rshift[(int)(*p3++)];
            /* Go update the clist */
            clr = ((int)r << 16) | ((int)g << 8) | (int)b;
            hash = f(r,g,b);
            pc = ch[hash];
            while (pc != NULL)
              {
                if (pc->clr == clr) break;
                else pc = pc->next;
              }     
            if (pc == NULL)
              {
                /* Add a color with the current values */
                pc = cmalloc();
                if (ch[hash] == NULL && ct[hash] == NULL) /* Empty color list */
                  {
                    ch[hash] = pc;
                    ct[hash] = pc;
                    pc->prev = NULL;
                    pc->next = NULL;
                  }
                else                                /* Not empty, add to head */
                  {
                    pc->prev = NULL;
                    pc->next = ch[hash];
                    ch[hash]->prev = pc;
                    ch[hash] = pc;
                  }
                pc->r = r;
                pc->g = g;
                pc->b = b;
                pc->clr = clr;
                pc->count = 1;
                pc->pixlist = pmalloc();
                pc->pixlist->next = NULL;
/* The following line replaces the next two */
                pc->pixlist->offset = j*image->row_size+i;
/*
                pc->pixlist->x = i;
                pc->pixlist->y = j;
*/
                pc->pixtail = pc->pixlist;
              }
            else
              {
                /* Update the pixel list of this color */
                pc->count++;
                pc->pixtail->next = pmalloc();
                pc->pixtail = pc->pixtail->next;
                pc->pixtail->next = NULL;
/* The following line replaces the next two */
                pc->pixtail->offset = j*image->row_size+i;
/*
                pc->pixtail->x = i;
                pc->pixtail->y = j;
*/
                if (pc != ch[hash]) gamut_head_swap(pc);
              }
          }
      }

    /* Now append all color lists together */
    for (i=0; i<nchanls; i++)
      {
        if (ch[i] != NULL)     /* If have something to add */
          {
            if (ctail != NULL) /* If main list not empty */
              {
                ctail->next = ch[i];
                ch[i]->prev = ctail;
                ctail = ct[i];
              }
            else               /* Main list is empty */
              {
                chead = ch[i];
                ctail = ct[i];
              }
          }
      }
    free(ch);
    free(ct);
    free(image->imagedata);   /* Give back this space - we'll need it */
  }

struct color *cmalloc()
  {
    /* Maintain a list of blocks of CNUM colors, allocated in chunks and then
       doled out as needed. */
    if (cbcount == 0 || ccount >= CNUM)
      {
        if (cbcount >= MAX_CBLOCKS)
          {
            fprintf(stderr,"lvgamut: too many color blocks!\n");
            fprintf(stderr, "        recompile with larger MAX_CBLOCKS");
            exit(1);
          }
        cblock[cbcount]=(struct color *)malloc(CNUM*sizeof(struct color));
        if (cblock[cbcount] == NULL)
          {
            fprintf(stderr,"lvgamut: unable to allocate color block!");
            exit(1);
          }
        cbcount++;
        ccount = 0;
      }
    return(cblock[cbcount-1]+(ccount++));
  }

gamut_head_swap(p)
register struct color *p;
  {
    register int k;

    k = f(p->r,p->g,p->b);
    /* Delete current color from list */
    if (p == ct[k])
      {
        p->prev->next = p->next;
        ct[k] = p->prev;
      }
    else
      {
        p->prev->next = p->next;
        p->next->prev = p->prev;
      }

    /* Re-insert color at head of list*/
    p->next = ch[k];
    p->prev = NULL;
    ch[k]->prev = p;
    ch[k] = p;
  }
 
compress_colors(ncolors,fraction)
int *ncolors;
float fraction;
  {
    int i,n,count,popok;
    unsigned char r,g,b,cmax;
    struct color *p1,*p2;
    register struct box *b1,*b2;
    struct box *find_biggest_box1(),*find_biggest_box2();

    /* Go find out how many colors are present in the image */
    count = 0;
    p1 = chead;
    while (p1 != NULL)
      {
        count++;
        p1 = p1->next;
      }

    /* If verbose is turned on tell how many colors were found. */
    if (khoros_verbose != 0)
      {
        (void)fprintf(stderr,"lvgamut: Image contains %d colors at the requested color precision.\n",count);
      }

    /* Now see if the user has requested more colors than exist in the
       image. Spit out a message if verbose is true. Return only the
       number of colors that actually exist. */
    if (*ncolors > count)
      {
        if (khoros_verbose != 0)
          {
            (void)fprintf(stderr,"lvgaumt: Found %d colors, user requested %d\n",count,*ncolors);
            (void)fprintf(stderr,"lvgaumt: Returning image with %d colors\n",count);
          }
        *ncolors = count;
      }

    /* Initialize box structure */
    boxhead = NULL;
    boxtail = NULL;

    /* Make first box and attach all colors to it */
    b1 = (struct box *)malloc(sizeof(struct box));
    if (b1 == NULL)
      {
        (void)fprintf(stderr,"lvgamut: Not enough memory for root box!\n");
        exit(1);
      }
    boxhead = b1;
    boxtail = b1;
    b1->colors = chead;
    gamut_set_box_bounds(b1);
    b1->next = NULL;
    
    /* Now go through and perform a median cut on the box list */
    /* until the desired number of boxes (colors) are formed. */
    popok = TRUE;
    for (i=0; i<(*ncolors)-1; i++)
      {
        /* Hunt down the biggest box */
        if (i < (*ncolors)*(1.0-fraction) && popok == TRUE) 
          {
            b1 = find_biggest_box1();  /* Population */
            if (b1 == NULL)
              {
                (void)fprintf(stderr,"lvgamut: Largest box population was 0!\n");
                exit(1);
              }
          }
        else 
          {
retry:      b1 = find_biggest_box2();                /* 2-norm */
            if (b1 == NULL)
              {
                (void)fprintf(stderr,"lvgamut: Largest box 2-norm was 0!\n");
                exit(1);
              }
          }

        /* First make new box */
        b2 = (struct box *)malloc(sizeof(struct box));
        if (b2 == NULL)
          {
            (void)fprintf(stderr,"lvgamut: Not enough memory for additional box!\n");
            exit(1);
          }
        b2->next = NULL;
        b2->colors = NULL;

        /* Copy the color bounds to the new box. */
        b2->rmax = b1->rmax; b2->gmax = b1->gmax; b2->bmax = b1->bmax;
        b2->rmin = b1->rmin; b2->gmin = b1->gmin; b2->bmin = b1->bmin;

        /* Compute boundary for splitting the color space */
        r = b1->rmax-b1->rmin;
        g = b1->gmax-b1->gmin;
        b = b1->bmax-b1->bmin;
        cmax = b; n = 3;                              /* Split on blue */
        if (g > cmax) { cmax = g; n = 2; }            /*    or on green */
        if (r > cmax) { cmax = r; n = 1; }            /*    or on red */

        /* Check to make sure that the axis being split has a legal span */
        if (popok == TRUE) /* Splitting on population */
          {
            switch(n)
              {
                case 1:
                  if (r < 2)
                    {
                      popok = FALSE;
                      free(b2);
                      goto retry;
                    }
                  break;
                case 2:
                  if (g < 2)
                    {
                      popok = FALSE;
                      free(b2);
                      goto retry;
                    }
                  break;
                case 3:
                  if (b < 2)
                    {
                      popok = FALSE;
                      free(b2);
                      goto retry;
                    }
                  break;
              }
          }
        else     /* Splitting on 2-norm */
          {
            switch(n)
              {
                case 1:
                  if (r >= 1) break;
                case 2:
                  if (g >= 1) break;
                case 3:
                  if (b >= 1) break;
                fprintf(stderr,"lvgamut: Couldn't find a splittable color subspace!\n");
                fprintf(stderr,"         Use more precision, or request less colors.\n");
                exit(1);
              }
          }

        /* Update the global boxtail pointer */
        boxtail->next = b2;
        boxtail = boxtail->next;

        /* Modify the color bounds for the original and new boxes */
        switch(n)
          {
            case 1:                              /* Splitting on red */
              b1->rmax = b1->rmin+r/2;
              b2->rmin = b2->rmax-r/2;
              break;
            case 2:                              /* Splitting on blue */
              b1->gmax = b1->gmin+g/2;
              b2->gmin = b2->gmax-g/2;
              break;
            case 3:                              /* Splitting on green */
              b1->bmax = b1->bmin+b/2;
              b2->bmin = b2->bmax-b/2;
              break;
          }

        /* Partition the color space of the first box */
        p1 = b1->colors;           /* Color list in original box */
        p2 = b2->colors;           /* End of color list in new box */
        while (p1 != NULL)
          {
            switch(n)
              {
                case 1:                          /* Splitting on red */
                  if (p1->r > b1->rmax) box_move_color(b1,b2,&p1,&p2);
                  else p1 = p1->next;
                  break;
                case 2:                          /* Splitting on green */
                  if (p1->g > b1->gmax) box_move_color(b1,b2,&p1,&p2);
                  else p1 = p1->next;
                  break;
                case 3:                          /* Splitting on blue */
                  if (p1->b > b1->bmax) box_move_color(b1,b2,&p1,&p2);
                  else p1 = p1->next;
                  break;
              }
          }

        /* Re-compute the color bounds for both boxes */
        gamut_set_box_bounds(b1);
        gamut_set_box_bounds(b2);
      }
  }

box_move_color(b1,b2,p1,p2)
register struct box *b1,*b2;
register struct color **p1,**p2;
  {
    /* Move the color p1 from box b1's color list to box b2's color list,
       which has the tail of its color list marked by o2. c1 must me left
       pointing to the next color in b1's color list, which p2 must be left
       pointing at the last color in b2's color list. */

    register struct color *c1;

    c1 = (*p1)->next;           /* Remember where "next" is. */

    /* Unlink color */
    if (b1->colors == *p1 && (*p1)->next != NULL)    /* p1 is head of color list */
      {
        b1->colors = (*p1)->next;
        (*p1)->next->prev = NULL;
      }
    else if (b1->colors == *p1 && (*p1)->next == NULL) /* p1 is only color */
      {
        b1->colors = NULL;
      }
    else if (b1->colors != *p1 && (*p1)->next == NULL) /* p1 is tail of list */
      {
        (*p1)->prev->next = NULL;
      }
    else
      {
        (*p1)->next->prev = (*p1)->prev;      /* p1 in middle of list */
        (*p1)->prev->next = (*p1)->next;
      }
    (*p1)->next = NULL;
    (*p1)->prev = NULL;

    /* Append the color to the correct place */
    if (b2->colors == NULL)                  /* Empty color list */
       {
         b2->colors = *p1;
         *p2 = *p1;
       }
    else                                     /* Non-empty color list */
      {
        (*p2)->next = *p1;
        (*p1)->prev = *p2;
        *p2 = *p1;
      }

    *p1 = c1;                   /* Regurgitate "next". */
  }

struct box *find_biggest_box1()
 {
   /* Find the box with the largest population */
   register struct box *b,*b1;
   register int max;

   b = boxhead;
   b1 = NULL;
   max = 0;
   while (b != NULL)
     {
       if (b->count > max)
         {
           max = b->count;
           b1 = b;
         }
       b = b->next;
     }
   return(b1);
 }

struct box *find_biggest_box2()
 {
   /* Find the box with the largest 2-norm */
   register struct box *b,*b1;
   register int maxnorm,norm,red,green,blue;

   b = boxhead;
   b1 = NULL;
   maxnorm = 0;
   while (b != NULL)
     {
       red = (int)(b->rmax)-(int)(b->rmin);
       green = (int)(b->gmax)-(int)(b->gmin);
       blue = (int)(b->bmax)-(int)(b->bmin);
       norm = red*red+green*green+blue*blue;
       if (norm > maxnorm)
         {
           maxnorm = norm;
           b1 = b;
         }
       b = b->next;
     }
   return(b1);
 }

gamut_set_box_bounds(b)
struct box *b;
  {
    register struct color *c;
    register int rmin,rmax,bmin,bmax,gmin,gmax;
    register int n;

    rmin = gmin = bmin = 255;
    rmax = gmax = bmax = 0;

    n = 0;
    c = b->colors;
    while (c != NULL)
      {
        if ((int)(c->r) > rmax) rmax = (int)(c->r);
        if ((int)(c->r) < rmin) rmin = (int)(c->r);
        if ((int)(c->g) > gmax) gmax = (int)(c->g);
        if ((int)(c->g) < gmin) gmin = (int)(c->g);
        if ((int)(c->b) > bmax) bmax = (int)(c->b);
        if ((int)(c->b) < bmin) bmin = (int)(c->b);
        c = c->next;
        n++;
      }

    b->rmax = rmax; b->rmin = rmin;
    b->gmax = gmax; b->gmin = gmin;
    b->bmax = bmax; b->bmin = bmin;
    b->count = n;
  }

gamut_adjust_image(image,ncolors)
struct xvimage *image;
int ncolors;
  {
    register unsigned char *d;
    register struct color *c;
    register struct pixel *p;
    register int r,g,b;
    register struct box *bp;
    register int i;

    /* Allocate space for the new image data, and attach to the header */
    d = (unsigned char *)malloc(image->row_size*image->col_size);
    image->imagedata = (char *)d;

    /* Read thru the box list stepping thru its color list and placing
       the pixels in the output image */
    i = 0;
    bp = boxhead;
    while (bp != NULL)
      {
        c = bp->colors;
        while (c != NULL)
          {
            p = c->pixlist;
            while (p != NULL)
              {
/* The following line replaces the next one */
                d[p->offset] = i;
/*
                d[p->y*image->row_size+p-x] = i;
*/
                p = p->next;
              }
            c = c->next;
          }
        bp = bp->next;
        i++;
      }
 
    /* Compute the new color for each box as the weighted average of all
       colors inside the box */
    bp = boxhead;
    while (bp != NULL)
      {
        i = r = g = b = 0;
        c = bp->colors;
        while (c != NULL)
          {
            r += c->count*(int)(c->r);
            g += c->count*(int)(c->g);
            b += c->count*(int)(c->b);
            i += c->count;
            c = c->next;
          }
        bp->rmin = (unsigned char)(r/i);
        bp->gmin = (unsigned char)(g/i);
        bp->bmin = (unsigned char)(b/i);
        bp = bp->next;
      }

    /* Build new color map */
    if (image->maps != NULL) free(image->maps);
    d = (unsigned char *)malloc((unsigned int)(3*ncolors));
    if (d == NULL)
      {
        (void)fprintf(stderr,"lvgamut: Not enough memory for RGB color maps!\n");
        exit(1);
      }
    image->maps = (char *)d;
    bp = boxhead;
    while (bp != NULL)
      {
        *d             = lshift[bp->rmin];              /* Code back to 8 bits */
        *(d+ncolors)   = lshift[bp->gmin];
        *(d+2*ncolors) = lshift[bp->bmin];
        bp = bp->next;
        d++;
      }

    image->map_storage_type = VFF_MAPTYP_1_BYTE;
    image->map_row_size = 3;
    image->map_col_size = ncolors;
    image->map_scheme = VFF_MS_ONEPERBAND;
    image->map_enable = VFF_MAP_FORCE;
    image->num_data_bands = 1;

    /* Sort the color maps and remap the data */
    sort_cmaps(image);
  }

free_colors()
  {
    /* Release all malloc()'ed items except the new colormap. */
    struct box *b,*b1;
    int i;

    free(pixels);
    for (i=0; i<cbcount; i++) free(cblock[i]);

    b = boxhead;
    while (b != NULL)
      {
        b1 = b->next;
        free((char *)b);
        b = b1;
      }
  }

static int
sort_cmaps(image)
struct xvimage *image;
  {
    /* This is a cheapo way to do this and can definately be done better,
       but it is good enough for the 1.0 release....  SRW */
    int i,j,k,nc,jold;
    unsigned int *r,*g,*b;
    unsigned char *d;
    unsigned int *list,*used,*trans,v,dark,close;
    char *malloc();

    nc = image->map_col_size;
    r = (unsigned int *)malloc(nc*sizeof(unsigned int));
    g = (unsigned int *)malloc(nc*sizeof(unsigned int));
    b = (unsigned int *)malloc(nc*sizeof(unsigned int));
    used = (unsigned int *)malloc(nc*sizeof(unsigned int));
    trans = (unsigned int *)malloc(nc*sizeof(unsigned int));
    bzero(used,nc*sizeof(int));

    d = (unsigned char *)(image->maps);
    for (i=0; i<nc; i++)
      {
        r[i] = *d;
        g[i] = *(d+nc);
        b[i] = *(d+2*nc);
        d++;
      }

    /* Find darkest color as the initial entry on the output list */
    j = 0;
    dark = r[0]+g[0]+b[0];
    for (i=1; i<nc; i++)
      {
        v = r[i]+g[i]+b[i];
        if (v < dark)
          {
            j = i;
            dark = v;
          }
      }

    /* Begin filling in the output list */
    trans[j] = 0;
    used[j] = 1;
    jold = j;
    for (i=1; i<nc; i++)
      {
        close = 256*3;
        for (k=0; k<nc; k++)
          {
            if (used[k] == 0)
              {
                v = abs((int)r[jold]-(int)r[k])+
                    abs((int)g[jold]-(int)g[k])+
                    abs((int)b[jold]-(int)b[k]);
                if (v < close)
                  {
                    close = v;
                    j = k;
                  }
              }
          }
        trans[j] = i;
        used[j] = 1;
        jold = j;
      }

    /* Remap the data */
    d = (unsigned char *)(image->imagedata);
    for (i=0; i<image->row_size*image->col_size; i++)
      {
        *d = trans[*d];
        d++;
      }
    
    /* Install the sorted maps */
    d = (unsigned char *)image->maps;
    for (i=0; i<nc; i++)
      {
        *(d+trans[i]) = r[i];
        *(d+nc+trans[i]) = g[i];
        *(d+2*nc+trans[i]) = b[i];
      }

    free(used); free(trans); free(r); free(g); free(b);
  }

/* -library_code_end */
