 /*
  * Khoros: $Id: lv1bgamut.c,v 1.3 1992/03/20 23:04:17 dkhoros Exp $
  */

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

 /*
  * $Log: lv1bgamut.c,v $
 * Revision 1.3  1992/03/20  23:04:17  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: lv1bgamut.c
 >>>>
 >>>>      Program Name: v1bgamut
 >>>>
 >>>> Date Last Updated: Sat Nov  2 17:26:27 1991 
 >>>>
 >>>>          Routines: lv1bgamut - the library call for v1bgamut
 >>>>
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>   <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/


#include "vinclude.h"


/* -library_includes */
struct color
  {
    unsigned char r;                      /* Color values */
    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
  {
    short x,y;                            /* Location of pixel */
    struct pixel *next;                   /* Pointer to next one */
  };

#define MAX_CHANLS 256                    /* Max number of hash indices */
#define MAX_CHANL_BITS 8                  /* Log base 2 of MAX_CHANLS */
int nchanls = 256;                        /* Number of hash indices */
struct color *chead,*ctail;               /* Composite color list */
struct color **ch,**ct;                   /* Hash index color lists */

struct box
  {
    unsigned char rmin,rmax;              /* Bounds on box */
    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 pmalloc1() pixpile++               /* Pixel handout function */

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

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


/****************************************************************
*
* Routine Name: lv1bgamut - library call for v1bgamut
*
* Purpose:
*    
*    Compress grey levels of an image, produce new image with map
*    
*    

* Input:
*    
*    image          pointer to xvimage structure to be processed
*    
*    nlevels        number of grey levels allowed in the output image
*    
*    fraction       allocation fraction, 0 means all levels chosen  on
*                   the  amount of area of the image that is in a par-
*                   ticular colro range, 1 means all levels chosen  to
*                   minimize  the error in the grey span. About 0.5 is
*                   good.
*    
*    

* 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
*    
*    31-Oct-91   Scott   Wilson   -   Added    missing    pointer
*    initialization  in  load_color_list1; it was fixed in vgamut
*    but not here.
*    2-Nov-91  Scott  Wilson  -  Added  output  map  sorting  ala
*    lvgamut()
*    
*    

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


/* -library_def */
int
lv1bgamut(image,nlevels,fraction)
struct xvimage *image;
int nlevels;
float fraction;
/* -library_def_end */

/* -library_code */
  {
    /* 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,"lv1bgamut: cannot allocate pixel space!\n");
        exit(0);
      }
    pixpile = pixels;

    load_color_list1(image);            /* Make color list */
    compress_colors1(nlevels,fraction); /* Squeeze the color list */
    adjust_image1(image,nlevels);       /* Make squeezed image */
    free_colors1();                     /* Give back all memory */

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

load_color_list1(image)                 /* Build the color list */
struct xvimage *image;
  {
    register struct color *pc;
    register unsigned char *p1;
    register int i,j;
    unsigned char r;
    struct color *cmalloc1();
    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,"lv1bgamut: 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);
    for (j=0; j<image->col_size; j++)
      {
        for (i=0; i<image->row_size; i++)
          {
            r = *p1++;
            pc = ch[r];
            while (pc != NULL)
              {
                if (pc->r == r) break;
                else pc = pc->next;
              }     
            if (pc == NULL)
              {
                /* Add a color with the current values */
                pc = cmalloc1();
                if (ch[r] == NULL && ct[r] == NULL) /* Empty color list */
                  {
                    ch[r] = pc;
                    ct[r] = pc;
                    pc->prev = NULL;
                    pc->next = NULL;
                  }
                else                                /* Not empty, add to head */
                  {
                    pc->prev = NULL;
                    pc->next = ch[r];
                    ch[r]->prev = pc;
                    ch[r] = pc;
                  }
                pc->r = r;
                pc->count = 1;
                pc->pixlist = pmalloc1();
                pc->pixlist->next = NULL;
                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 = pmalloc1();
                pc->pixtail = pc->pixtail->next;
                pc->pixtail->next = NULL;
                pc->pixtail->x = i;
                pc->pixtail->y = j;
              }
          }
      }

    /* 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);
  }

struct color *cmalloc1()
  {
    /* 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,"lv1bgamut: 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,"lv1bgamut: unable to allocate color block!");
            exit(1);
          }
        cbcount++;
        ccount = 0;
      }
    return(cblock[cbcount-1]+(ccount++));
  }

compress_colors1(nlevels,fraction)
int nlevels;
float fraction;
  {
    int i,count,popok;
    unsigned char r;
    struct color *p1,*p2;
    register struct box *b1,*b2;
    struct box *find_biggest_box11(),*find_biggest_box21();

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

    /* Now see if the user has requested more colors than exist in the
       image. If so, spit out a message and quit. */
    if (nlevels > count)
      {
        (void)fprintf(stderr,"lvgaumt: Found %d colors, user requested %d\n",count,nlevels);
        exit(1);
      }

    /* 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,"lv1bgamut: Not enough memory for root box!\n");
        exit(1);
      }
    boxhead = b1;
    boxtail = b1;
    b1->colors = chead;
    onegamut_set_box_bounds1(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<nlevels-1; i++)
      {
        /* Hunt down the biggest box */
        if (i < nlevels*(1.0-fraction) && popok == TRUE) 
          {
            b1 = find_biggest_box11();  /* Population */
            if (b1 == NULL)
              {
                (void)fprintf(stderr,"lv1bgamut: Largest box population was 0!\n");
                exit(1);
              }
          }
        else 
          {
retry:      b1 = find_biggest_box21();                /* 2-norm */
            if (b1 == NULL)
              {
                (void)fprintf(stderr,"lv1bgamut: 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,"lv1bgamut: 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->rmin = b1->rmin;

        /* Compute boundary for splitting the color space */
        r = b1->rmax-b1->rmin;

        /* Check to make sure that the axis being split has a legal span */
        if (popok == TRUE) /* Splitting on population */
          {
            if (r < 2)
              {
                popok = FALSE;
                free(b2);
                goto retry;
              }
          }
        else     /* Splitting on 2-norm */
          {
            if (r < 1)
              {
                fprintf(stderr,"lv1bgamut: Couldn't find a splittable color subspace!\n");
                exit(1);
              }
          }

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

        /* Modify the color bounds for the original and new boxes */
        b1->rmax = b1->rmin+r/2;
        b2->rmin = b2->rmax-r/2;

        /* 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)
          {
            if (p1->r > b1->rmax) box_move_color1(b1,b2,&p1,&p2);
            else p1 = p1->next;
          }

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

box_move_color1(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_box11()
 {
   /* 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_box21()
 {
   /* Find the box with the largest 2-norm */
   register struct box *b,*b1;
   register int maxnorm,norm,red;

   b = boxhead;
   b1 = NULL;
   maxnorm = 0;
   while (b != NULL)
     {
       red = (int)(b->rmax)-(int)(b->rmin);
       norm = red*red;
       if (norm > maxnorm)
         {
           maxnorm = norm;
           b1 = b;
         }
       b = b->next;
     }
   return(b1);
 }

onegamut_set_box_bounds1(b)
struct box *b;
  {
    register struct color *c;
    register int rmin,rmax;
    register int n;

    rmin = 255;
    rmax = 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);
        c = c->next;
        n++;
      }

    b->rmax = rmax; b->rmin = rmin;
    b->count = n;
  }

adjust_image1(image,nlevels)
struct xvimage *image;
int nlevels;
  {
    register unsigned char *d;
    register struct color *c;
    register struct pixel *p;
    register int r;
    register struct box *bp;
    register int i;

    /* Read thru the box list stepping thru its color list and placing
       the pixels in the output image */
    d = (unsigned char *)(image->imagedata);
    i = 0;
    bp = boxhead;
    while (bp != NULL)
      {
        c = bp->colors;
        while (c != NULL)
          {
            p = c->pixlist;
            while (p != NULL)
              {
                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 = 0;
        c = bp->colors;
        while (c != NULL)
          {
            r += c->count*(int)(c->r);
            i += c->count;
            c = c->next;
          }
        bp->rmin = (unsigned char)(r/i);
        bp = bp->next;
      }

    /* Build new color map */
    if (image->maps != NULL) free(image->maps);
    d = (unsigned char *)malloc((unsigned int)nlevels);
    if (d == NULL)
      {
        (void)fprintf(stderr,"lv1bgamut: Not enough memory for maps!\n");
        exit(1);
      }
    image->maps = (char *)d;
    bp = boxhead;
    while (bp != NULL)
      {
        *d = bp->rmin;
        bp = bp->next;
        d++;
      }

    image->map_storage_type = VFF_MAPTYP_1_BYTE;
    image->map_row_size = 1;
    image->map_col_size = nlevels;
    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_colors1()
  {
    /* Release all malloc()'ed items except the new map. */
    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;
  {
    /* Stolen from lvgamut() with appropriate mods SRW 2-Nov-91 */
    int i,j,k,nc,jold;
    unsigned int *r;
    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));
    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++;

    /* Find darkest color as the initial entry on the output list */
    j = 0;
    dark = r[0];
    for (i=1; i<nc; i++)
      {
        v = r[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]);
                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];

    free(used); free(trans); free(r);
  }
/* -library_code_end */
