Index color if possible in pngo

2 files changed, 40 insertions, 3 deletions

diff --git a/bin/README b/bin/README
index 94429275..32f9862d 100644
--- a/bin/README
+++ b/bin/README
@@ -82,6 +82,7 @@ PNG optimizer. Does not support interlaced PNGs.
  - Discards ancillary chunks
  - Discards unnecessary alpha channel
  - Converts unnecessary truecolor to grayscale
+ - Indexes color if possible
  - Applies a simple filter type heuristic
  - Applies zlib's best compression
 
diff --git a/bin/pngo.c b/bin/pngo.c
index bf592ad1..37fd6af7 100644
--- a/bin/pngo.c
+++ b/bin/pngo.c
@@ -197,9 +197,7 @@ static void writeHeader(void) {
 
 static struct {
     uint32_t len;
-    struct PACKED {
-        uint8_t r, g, b;
-    } entries[256];
+    uint8_t entries[256][3];
 } palette;
 
 static void readPalette(void) {
@@ -473,6 +471,43 @@ static void discardColor(void) {
     header.color &= ~TRUECOLOR;
 }
 
+static void indexColor(void) {
+    if (header.color != TRUECOLOR || header.depth != 8) return;
+    for (uint32_t y = 0; y < header.height; ++y) {
+        for (uint32_t x = 0; x < header.width; ++x) {
+            uint32_t i;
+            for (i = 0; i < palette.len; ++i) {
+                if (0 == memcmp(palette.entries[i], &lines[y].data[x * 3], 3)) {
+                    break;
+                }
+            }
+            if (i < palette.len) continue;
+            if (palette.len == 256) return;
+            memcpy(palette.entries[i], &lines[y].data[x * 3], 3);
+            palette.len++;
+        }
+    }
+
+    uint8_t *ptr = data;
+    for (uint32_t y = 0; y < header.height; ++y) {
+        uint8_t *type = ptr++;
+        uint8_t *data = ptr;
+        *type = *lines[y].type;
+        for (uint32_t x = 0; x < header.width; ++x) {
+            uint32_t i;
+            for (i = 0; i < palette.len; ++i) {
+                if (0 == memcmp(palette.entries[i], &lines[y].data[x * 3], 3)) {
+                    break;
+                }
+            }
+            *ptr++ = i;
+        }
+        lines[y].type = type;
+        lines[y].data = data;
+    }
+    header.color = INDEXED;
+}
+
 static void optimize(const char *inPath, const char *outPath) {
     if (inPath) {
         path = inPath;
@@ -501,6 +536,7 @@ static void optimize(const char *inPath, const char *outPath) {
     reconData();
     discardAlpha();
     discardColor();
+    indexColor();
     filterData();
     free(lines);