# HG changeset patch
# User Matti Hamalainen <ccr@tnsp.org>
# Date 1352254140 -7200
# Node ID b768bfb0b36410e6dbcf5a82caff9eba513878d0
# Parent  7c7a575902367d7366c518522ed9ccfa4765704f
Improve color remapping, add option for removing unused colors from the final output palette.

diff -r 7c7a57590236 -r b768bfb0b364 gfxconv.c
--- a/gfxconv.c	Wed Nov 07 03:03:01 2012 +0200
+++ b/gfxconv.c	Wed Nov 07 04:09:00 2012 +0200
@@ -118,7 +118,8 @@
 int     optInSkip = 0;
 BOOL    optInMulticolor = FALSE,
         optSequential = FALSE,
-        optRemapColors = FALSE;
+        optRemapColors = FALSE,
+        optRemapRemove = FALSE;
 int     optNRemapTable = 0;
 DMMapValue optRemapTable[DM_MAX_COLORS];
 int     optColors[C64_MAX_COLORS];
@@ -152,6 +153,7 @@
     { 13, 'B', "bplanes",      "Bits per pixel OR # of bitplanes (certain output formats)", OPT_ARGREQ },
     { 14, 'I', "interleave",   "Interleave scanlines (default: output whole planes)", OPT_NONE },
     { 16, 'R', "remap",        "Remap output image colors (-R <(#RRGGBB|index):index>[,<..>] | -R @map.txt)", OPT_ARGREQ },
+    { 18, 'r', "remap-remove", "Remove unused colors from remapped palette (requires -R)\n", OPT_NONE },
 };
 
 static const int optListN = sizeof(optList) / sizeof(optList[0]);
@@ -580,6 +582,10 @@
             optRemapColors = TRUE;
             break;
 
+        case 18:
+            optRemapRemove = TRUE;
+            break;
+
         default:
             dmError("Unknown option '%s'.\n", currArg);
             return FALSE;
@@ -745,27 +751,43 @@
 {
     dmMsg(1, "Remapping %d output image colors.\n", optNRemapTable);
     DMColor *npal = dmCalloc(image->ncolors, sizeof(DMColor));
-    int *dpal = dmMalloc(image->ncolors * sizeof(int));
-    BOOL *spal = dmCalloc(image->ncolors, sizeof(BOOL));
-    int index, xc, yc, nncolors = image->ncolors;
+    int  *mapping = dmMalloc(image->ncolors * sizeof(int));
+    BOOL *mapped  = dmMalloc(image->ncolors * sizeof(BOOL));
+    BOOL *used    = dmMalloc(image->ncolors * sizeof(BOOL));
+    int n, index, xc, yc, ncolors = image->ncolors;
 
-    if (npal == NULL || spal == NULL || dpal == NULL)
+    if (npal == NULL || mapping == NULL || mapped == NULL || used == NULL)
     {
-        dmError("Could not allocate memory for remapped palette.\n");
+        dmError("Could not allocate memory for reused palette.\n");
         return DMERR_MALLOC;
     }
 
     for (index = 0; index < image->ncolors; index++)
-        dpal[index] = -1;
+    {
+        mapping[index] = -1;
+        used[index] = mapped[index] = FALSE;
+    }
 
-    // Find and mark mapped colors    
+    // Find used colors
+    dmMsg(2, "Scanning image for used colors...\n");
+    for (yc = 0; yc < image->height; yc++)
+    {
+        Uint8 *dp = image->data + image->pitch * yc;
+        for (xc = 0; xc < image->width; xc++)
+        {
+            Uint8 col = dp[xc];
+            if (col < image->ncolors)
+                used[col] = TRUE;
+        }
+    }
+
+    // Match and mark mapped colors
     for (index = 0; index < optNRemapTable; index++)
     {
         DMMapValue *map = &optRemapTable[index];
         if (map->triplet)
         {
             BOOL found = FALSE;
-            int n;
             for (n = 0; n < image->ncolors; n++)
             {
                 if (dmCompareColor(&(image->pal[n]), &(map->color), map->alpha))
@@ -775,10 +797,12 @@
                         n,
                         map->to);
                     
-                    dpal[map->to] = n;
-                    spal[n] = TRUE;
-                    found = TRUE;
-//                    break;
+                    if (used[n])
+                    {
+                        mapping[n] = map->to;
+                        mapped[map->to] = TRUE;
+                        found = TRUE;
+                    }
                 }
             }
             
@@ -791,57 +815,75 @@
         }
         else
         {
-            dmMsg(3, "Map index: %d -> %d\n",
-                map->from, map->to);
-            
-            dpal[map->to] = map->from;
-            spal[map->from] = TRUE;
+            if (used[map->from])
+            {
+                dmMsg(3, "Map index: %d -> %d\n",
+                    map->from, map->to);
+
+                mapping[map->from] = map->to;
+                mapped[map->to] = TRUE;
+            }
         }
     }
     
     // Fill in the rest
-    dmMsg(3, "Placing non-mapped palette entries.\n");
-    for (index = 0; index < image->ncolors; index++)
+    if (optRemapRemove)
     {
-        if (dpal[index] < 0)
+        dmMsg(2, "Removing unused colors.\n");
+        for (index = 0; index < image->ncolors; index++)
+        if (mapping[index] < 0 && used[index])
         {
-            int src;
-            for (src = 0; src < image->ncolors; src++)
+            for (n = 0; n < image->ncolors; n++)
+            if (!mapped[n])
             {
-                if (!spal[src])
-                {
-                    dpal[index] = src;
-                    spal[src] = TRUE;
-                    break;
-                }
+                mapping[index] = n;
+                mapped[n] = TRUE;
+                break;
+            }
+        }
+    }
+    else
+    {
+        for (index = 0; index < image->ncolors; index++)
+        if (mapping[index] < 0)
+        {
+            for (n = 0; n < image->ncolors; n++)
+            if (!mapped[n])
+            {
+                mapping[index] = n;
+                mapped[n] = TRUE;
+                break;
             }
         }
     }
     
-    // Copy palette entries
-    dmMsg(3, "Creating new palette.\n");
+    // Calculate final number of palette colors
+    ncolors = 0;
     for (index = 0; index < image->ncolors; index++)
     {
-        if (dpal[index] >= 0 && dpal[index] < image->ncolors)
+        if (mapping[index] > ncolors)
+            ncolors = mapping[index] + 1;
+    }
+    
+    // Copy palette entries
+    for (index = 0; index < ncolors; index++)
+    {
+        if (mapping[index] >= 0)
         {
-            memcpy(&npal[index], &(image->pal[dpal[index]]), sizeof(DMColor));
-            nncolors = index;
+            memcpy(&npal[index], &(image->pal[mapping[index]]), sizeof(DMColor));
         }
     }
-    
 
     // Remap image
-    dmMsg(1, "Remapping image ...\n");
+    dmMsg(1, "Remapping image to %d colors...\n", ncolors);
     for (yc = 0; yc < image->height; yc++)
     {
         Uint8 *dp = image->data + image->pitch * yc;
         for (xc = 0; xc < image->width; xc++)
         {
             Uint8 col = dp[xc];
-            if (col < image->ncolors && dpal[col] >= 0 && dpal[col] < image->ncolors)
-            {
-                dp[xc] = dpal[col];
-            }
+            if (col < image->ncolors && mapping[col] >= 0 && mapping[col] < image->ncolors)
+                dp[xc] = mapping[col];
             else
                 dp[xc] = 0;
         }
@@ -850,9 +892,11 @@
     // Set new palette, free memory
     dmFree(image->pal);
     image->pal = npal;
-    image->ncolors = nncolors;
-    dmFree(spal);
-    dmFree(dpal);
+    image->ncolors = ncolors;
+
+    dmFree(mapping);
+    dmFree(mapped);
+    dmFree(used);
     return DMERR_OK;
 }