home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / amiga / convrtrs / hamsharp.lzh / HamSharp3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-08-04  |  5.7 KB  |  228 lines
  1. /*
  2. ** Part 3
  3. */
  4.  
  5. #include <stdio.h>
  6.  
  7. struct rgb {int r, g, b;};
  8.  
  9. extern int pals, colors;
  10. extern long colorerr [256];
  11. extern struct rgb cmap [256], palette [32];
  12.  
  13. struct adjcell {
  14.    unsigned char color;
  15.    int dist;
  16. };
  17.  
  18. /* Select and set palette */
  19. setpalette ()
  20. {
  21.    char *calloc ();
  22.    struct adjcell **adj;
  23.    static marked [256];
  24.    int color, color2, r, g, b, len, dup, unmarked, marks;
  25.    int mindist, mincolor, distance, colperpal, i, pal, radius;
  26.    struct adjcell *p;
  27.    struct rgb *rgbp;
  28.  
  29.    /* Clear marked array */
  30.    for (color = 0; color < colors; color++)
  31.       marked [color] = 0;
  32.    marks = 0;
  33.  
  34.    /* Always assign background */
  35.    palette [0] = cmap [0];
  36.    pals = 1;
  37.    if (!marked [0]) {
  38.       marked [0] = -1;
  39.       marks++;
  40.    }
  41.    printf ("Colours after removing background colour = %d\n", colors-marks);
  42.  
  43.    /* Mark off colors that are never used */
  44.    calcremap ();
  45.    scanpic ();
  46.    for (color = 0; color < colors; color++)
  47.       if ((colorerr [color] == 0L) && !marked [color]) {
  48.          marked [color] = -1;
  49.          marks++;
  50.       }
  51.    printf ("Colours after removing no-error  colours = %d\n", colors-marks);
  52.  
  53.    /* Mark off duplicates */
  54.    for (color = 0; color < colors; color++)
  55.       if (!marked [color]) {
  56.          r = cmap [color].r;
  57.          g = cmap [color].g;
  58.          b = cmap [color].b;
  59.          for (color2 = color+1; color2 < colors; color2++)
  60.             if (!marked [color2]) {
  61.                rgbp = &cmap [color2];
  62.                if ((r == rgbp->r) && (g == rgbp->g) && (b == rgbp->b)) {
  63.                   marked [color2] = -1;
  64.                   marks++;
  65.                }
  66.             }
  67.       }
  68.    printf ("Colours after removing duplicate colours = %d\n", colors-marks);
  69.  
  70.    pals = 16;
  71.    unmarked = colors - marks;
  72.    colperpal = unmarked / (pals - 1);
  73.    if (colperpal == 0)
  74.       colperpal = 1;
  75.    printf ("Colours per palette colour = %d\n", colperpal);
  76.  
  77.    /* Select and set palette based on sorted lists */
  78.    /* Create sorted-by-distance list of colors for each colors */
  79.    /* Leave out marked colors */
  80.    printf ("Sorting colour\n");
  81.    adj = (struct adjcell **) calloc (colors, sizeof (struct adjcell *));
  82.    if (adj == NULL)
  83.       fatalerr ("Out of memory");
  84.    for (color = 0; color < colors; color ++) {
  85.       if (marked [color])
  86.          adj [color] = NULL;
  87.       else {
  88.          adj [color] = (struct adjcell *)
  89.                        calloc (unmarked, sizeof (struct adjcell));
  90.          if (adj [color] == NULL)
  91.             fatalerr ("Out of memory");
  92.          len = 0;
  93.          r = cmap [color].r;
  94.          g = cmap [color].g;
  95.          b = cmap [color].b;
  96.          for (color2 = 0; color2 < colors; color2 ++)
  97.             if (!marked [color2])
  98.                insertheap (
  99.                   color2,
  100.                   rgberr (
  101.                      r, g, b,
  102.                      cmap [color2].r,
  103.                      cmap [color2].g,
  104.                      cmap [color2].b),
  105.                   &len,
  106.                   adj [color]);
  107.          heapsort (len, adj [color]);
  108.       }
  109.       printf ("%d\n\x1BM", color);
  110.    }
  111.    printf ("   ");                     /* Erase sorting count */
  112.    printf ("\x1B[1F\x1B[40K\n\x1BM");  /* Erase sorting message */
  113.  
  114.    /* Select and set palette based on sorted lists */
  115.    for (pal = 1; pal < pals; pal ++) {
  116.       radius = 0;
  117.       mincolor = 0;
  118.       mindist = 32000;
  119.       if (marks >= colors)
  120.          goto noassign;
  121.       /* Pick the best color to assign to the palette */
  122.       for (color = 1; color < colors; color ++)
  123.          if (!marked [color]) {
  124.             distance = 0;
  125.             p = adj [color];
  126.             for (i = 0; i < colperpal; i ++) {
  127.                while (marked [p->color])
  128.                   p ++;
  129.                distance += p->dist;
  130.                p ++;
  131.             }
  132.             if (distance < mindist) {
  133.                mindist = distance;
  134.                mincolor = color;
  135.             }
  136.          }
  137.       /* Mark off mincolor and the colors around it */
  138.       p = adj [mincolor];
  139.       radius = 0;
  140.       for (i = 0; i < colperpal; i++) {
  141.          while (marked [p->color])
  142.             p ++;
  143.          marked [p->color] = -1;
  144.          marks++;
  145.          if (p->dist > radius)
  146.             radius = p->dist;
  147.          p ++;
  148.       }
  149.       noassign:
  150.       palette [pal] = cmap [mincolor];
  151.       printf ("Palette %3d = colour %3d, radius = %3d\n\x1BM",
  152.                pal, mincolor, radius);
  153.    }
  154.  
  155.    /* Free up some memory */
  156.    for (color = 0; color < colors; color++)
  157.       if (adj [color] != NULL)
  158.          free (adj [color]);
  159.    free (adj);
  160.  
  161.    printf ("\x1B[4F");   /* Move to first line of stats */
  162.    printf ("\x1B[J");    /* Erase to end of display */
  163. }
  164.  
  165. /* Insert a value into a heap */
  166. insertheap (color, dist, len, adjline)
  167. int *len;
  168. struct adjcell *adjline;
  169. {
  170.    struct adjcell *heap = adjline - 1;
  171.    struct adjcell *p, *q, temp;
  172.    int i;
  173.  
  174.    i = ++(*len);
  175.    heap [i].color = color;
  176.    heap [i].dist = dist;
  177.    while ((i > 1) && ((p=heap+i)->dist > (q=heap+(i>>1))->dist)) {
  178.       temp = *p;
  179.       *p = *q;
  180.       *q = temp;
  181.       i >>= 1;
  182.    }
  183. }
  184.  
  185. /* Rearrange heap into sorted list */
  186. heapsort (last, adjline)
  187. struct adjcell *adjline;
  188. {
  189.    struct adjcell *h = adjline - 1;
  190.    struct adjcell *q, temp;
  191.    int n = last;
  192.    int i;
  193.  
  194.    for (i = n; i >= 2; i--) {
  195.       q = h + last;
  196.       temp = *adjline;
  197.       *adjline = *q;
  198.       *q = temp;
  199.       last --;
  200.       pushdown (last, h, 1);
  201.    }
  202. }
  203.  
  204. /* Part of heapsort */
  205. pushdown (last, h, start)
  206. struct adjcell *h;
  207. {
  208.    struct adjcell *p, *q, temp;
  209.    int i = start;
  210.    int j = i;
  211.    int last2 = last >> 1;
  212.  
  213.    while ((i <= last2) && (i == j)) {
  214.       j = i << 1;
  215.       if (j < last) {
  216.          if (h [j].dist < h [j + 1].dist)
  217.             j++;
  218.       }
  219.       if ((p=h+i)->dist < (q=h+j)->dist) {
  220.          temp = *p;
  221.          *p = *q;
  222.          *q = temp;
  223.          i = j;
  224.       }
  225.    }
  226. }
  227.  
  228.