From 93446262d26f467e1f33972383c4996b4586c7de Mon Sep 17 00:00:00 2001
From: John Tsiombikas <nuclear@member.fsf.org>
Date: Fri, 14 May 2021 21:02:05 +0300
Subject: [PATCH] forgot to add quant.c in pngdump

---
 tools/pngdump/quant.c |  396 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 396 insertions(+)
 create mode 100644 tools/pngdump/quant.c

diff --git a/tools/pngdump/quant.c b/tools/pngdump/quant.c
new file mode 100644
index 0000000..4dc2fee
--- /dev/null
+++ b/tools/pngdump/quant.c
@@ -0,0 +1,396 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+#include <errno.h>
+#include <assert.h>
+#include "image.h"
+
+#define NUM_LEVELS	8
+
+struct octnode;
+
+struct octree {
+	struct octnode *root;
+	struct octnode *redlist[NUM_LEVELS];
+	int redlev;
+	int nleaves, maxcol;
+};
+
+struct octnode {
+	int lvl;
+	struct octree *tree;
+	int r, g, b, nref;
+	int palidx;
+	int nsub, leaf;
+	struct octnode *sub[8];
+	struct octnode *next;
+};
+
+
+static void init_octree(struct octree *tree, int maxcol);
+static void destroy_octree(struct octree *tree);
+
+static struct octnode *alloc_node(struct octree *tree, int lvl);
+static void free_node(struct octnode *n);
+static void free_tree(struct octnode *n);
+
+static void add_color(struct octree *tree, int r, int g, int b, int nref);
+static void reduce_colors(struct octree *tree);
+static int assign_colors(struct octnode *n, int next, struct cmapent *cmap);
+static int lookup_color(struct octree *tree, int r, int g, int b);
+static int subidx(int bit, int r, int g, int b);
+static void print_tree(struct octnode *n, int lvl);
+
+int quantize_image(struct image *img, int maxcol)
+{
+	int i, j, cidx;
+	unsigned int rgb[3];
+	struct octree tree;
+	struct image newimg = *img;
+
+	if(maxcol < 2 || maxcol > 256) {
+		return -1;
+	}
+
+	if(img->bpp > 8) {
+		newimg.bpp = maxcol > 16 ? 8 : 4;
+		newimg.nchan = 1;
+		newimg.scansz = newimg.width * newimg.bpp / 8;
+		newimg.pitch = newimg.scansz;
+	}
+
+	init_octree(&tree, maxcol);
+
+	for(i=0; i<img->height; i++) {
+		for(j=0; j<img->width; j++) {
+			get_pixel_rgb(img, j, i, rgb);
+			add_color(&tree, rgb[0], rgb[1], rgb[2], 1);
+
+			while(tree.nleaves > maxcol) {
+				reduce_colors(&tree);
+			}
+		}
+	}
+
+	/* use created octree to generate the palette */
+	newimg.cmap_ncolors = assign_colors(tree.root, 0, newimg.cmap);
+
+	/* replace image pixels */
+	for(i=0; i<img->height; i++) {
+		for(j=0; j<img->width; j++) {
+			get_pixel_rgb(img, j, i, rgb);
+			cidx = lookup_color(&tree, rgb[0], rgb[1], rgb[2]);
+			assert(cidx >= 0 && cidx < maxcol);
+			put_pixel(&newimg, j, i, cidx);
+		}
+	}
+
+	*img = newimg;
+
+	destroy_octree(&tree);
+	return 0;
+}
+
+int gen_shades(struct image *img, int levels, int maxcol, int *shade_lut)
+{
+	int i, j, cidx, r, g, b;
+	unsigned int color[3];
+	struct octree tree;
+	struct image newimg = *img;
+
+	if(maxcol < 2 || maxcol > 256) {
+		return -1;
+	}
+
+	init_octree(&tree, maxcol);
+
+	for(i=0; i<img->cmap_ncolors; i++) {
+		add_color(&tree, img->cmap[i].r, img->cmap[i].g, img->cmap[i].b, 1024);
+	}
+
+	for(i=0; i<img->cmap_ncolors; i++) {
+		for(j=0; j<levels - 1; j++) {
+			r = img->cmap[i].r * j / (levels - 1);
+			g = img->cmap[i].g * j / (levels - 1);
+			b = img->cmap[i].b * j / (levels - 1);
+			add_color(&tree, r, g, b, 1);
+
+			while(tree.nleaves > maxcol) {
+				reduce_colors(&tree);
+			}
+		}
+	}
+
+	newimg.cmap_ncolors = assign_colors(tree.root, 0, newimg.cmap);
+
+	/* replace image pixels */
+	for(i=0; i<img->height; i++) {
+		for(j=0; j<img->width; j++) {
+			get_pixel_rgb(img, j, i, color);
+			cidx = lookup_color(&tree, color[0], color[1], color[2]);
+			put_pixel(&newimg, j, i, cidx);
+		}
+	}
+
+	/* populate shade_lut based on the new palette, can't generate levels only
+	 * for the original colors, because the palette entries will have changed
+	 * and moved around.
+	 */
+	for(i=0; i<newimg.cmap_ncolors; i++) {
+		for(j=0; j<levels; j++) {
+			r = newimg.cmap[i].r * j / (levels - 1);
+			g = newimg.cmap[i].g * j / (levels - 1);
+			b = newimg.cmap[i].b * j / (levels - 1);
+			*shade_lut++ = lookup_color(&tree, r, g, b);
+		}
+	}
+	for(i=0; i<(maxcol - newimg.cmap_ncolors) * levels; i++) {
+		*shade_lut++ = maxcol - 1;
+	}
+
+	*img = newimg;
+
+	destroy_octree(&tree);
+	return 0;
+}
+
+static void init_octree(struct octree *tree, int maxcol)
+{
+	memset(tree, 0, sizeof *tree);
+
+	tree->redlev = NUM_LEVELS - 1;
+	tree->maxcol = maxcol;
+
+	tree->root = alloc_node(tree, 0);
+}
+
+static void destroy_octree(struct octree *tree)
+{
+	free_tree(tree->root);
+}
+
+static struct octnode *alloc_node(struct octree *tree, int lvl)
+{
+	struct octnode *n;
+
+	if(!(n = calloc(1, sizeof *n))) {
+		perror("failed to allocate octree node");
+		abort();
+	}
+
+	n->lvl = lvl;
+	n->tree = tree;
+	n->palidx = -1;
+
+	if(lvl < tree->redlev) {
+		n->next = tree->redlist[lvl];
+		tree->redlist[lvl] = n;
+	} else {
+		n->leaf = 1;
+		tree->nleaves++;
+	}
+	return n;
+}
+
+static void free_node(struct octnode *n)
+{
+	struct octnode *prev, dummy;
+
+	dummy.next = n->tree->redlist[n->lvl];
+	prev = &dummy;
+	while(prev->next) {
+		if(prev->next == n) {
+			prev->next = n->next;
+			break;
+		}
+		prev = prev->next;
+	}
+	n->tree->redlist[n->lvl] = dummy.next;
+
+	if(n->leaf) {
+		n->tree->nleaves--;
+		assert(n->tree->nleaves >= 0);
+	}
+	free(n);
+}
+
+static void free_tree(struct octnode *n)
+{
+	int i;
+
+	if(!n) return;
+
+	for(i=0; i<8; i++) {
+		free_tree(n->sub[i]);
+	}
+	free_node(n);
+}
+
+static void add_color(struct octree *tree, int r, int g, int b, int nref)
+{
+	int i, idx, rr, gg, bb;
+	struct octnode *n;
+
+	rr = r * nref;
+	gg = g * nref;
+	bb = b * nref;
+
+	n = tree->root;
+	n->r += rr;
+	n->g += gg;
+	n->b += bb;
+	n->nref += nref;
+
+	for(i=0; i<NUM_LEVELS; i++) {
+		if(n->leaf) break;
+
+		idx = subidx(i, r, g, b);
+
+		if(!n->sub[idx]) {
+			n->sub[idx] = alloc_node(tree, i + 1);
+		}
+		n->nsub++;
+		n = n->sub[idx];
+
+		n->r += rr;
+		n->g += gg;
+		n->b += bb;
+		n->nref += nref;
+	}
+}
+
+static struct octnode *get_reducible(struct octree *tree)
+{
+	int best_nref;
+	struct octnode dummy, *n, *prev, *best_prev, *best = 0;
+
+	while(tree->redlev >= 0) {
+		best_nref = INT_MAX;
+		best = 0;
+		dummy.next = tree->redlist[tree->redlev];
+		prev = &dummy;
+		while(prev->next) {
+			n = prev->next;
+			if(n->nref < best_nref) {
+				best = n;
+				best_nref = n->nref;
+				best_prev = prev;
+			}
+			prev = prev->next;
+		}
+		if(best) {
+			best_prev->next = best->next;
+			tree->redlist[tree->redlev] = dummy.next;
+			break;
+		}
+		tree->redlev--;
+	}
+
+	return best;
+}
+
+static void reduce_colors(struct octree *tree)
+{
+	int i;
+	struct octnode *n;
+
+	if(!(n = get_reducible(tree))) {
+		fprintf(stderr, "warning: no reducible nodes!\n");
+		return;
+	}
+	for(i=0; i<8; i++) {
+		if(n->sub[i]) {
+			free_node(n->sub[i]);
+			n->sub[i] = 0;
+		}
+	}
+	n->leaf = 1;
+	tree->nleaves++;
+}
+
+static int assign_colors(struct octnode *n, int next, struct cmapent *cmap)
+{
+	int i;
+
+	if(!n) return next;
+
+	if(n->leaf) {
+		assert(next < n->tree->maxcol);
+		assert(n->nref);
+		cmap[next].r = n->r / n->nref;
+		cmap[next].g = n->g / n->nref;
+		cmap[next].b = n->b / n->nref;
+		n->palidx = next;
+		return next + 1;
+	}
+
+	for(i=0; i<8; i++) {
+		next = assign_colors(n->sub[i], next, cmap);
+	}
+	return next;
+}
+
+static int lookup_color(struct octree *tree, int r, int g, int b)
+{
+	int i, j, idx;
+	struct octnode *n;
+
+	n = tree->root;
+	for(i=0; i<NUM_LEVELS; i++) {
+		if(n->leaf) {
+			assert(n->palidx >= 0);
+			return n->palidx;
+		}
+
+		idx = subidx(i, r, g, b);
+		for(j=0; j<8; j++) {
+			if(n->sub[idx]) break;
+			idx = (idx + 1) & 7;
+		}
+
+		assert(n->sub[idx]);
+		n = n->sub[idx];
+	}
+
+	fprintf(stderr, "lookup_color(%d, %d, %d) failed!\n", r, g, b);
+	abort();
+	return -1;
+}
+
+static int subidx(int bit, int r, int g, int b)
+{
+	assert(bit >= 0 && bit < NUM_LEVELS);
+	bit = NUM_LEVELS - 1 - bit;
+	return ((r >> bit) & 1) | ((g >> (bit - 1)) & 2) | ((b >> (bit - 2)) & 4);
+}
+
+static void print_tree(struct octnode *n, int lvl)
+{
+	int i;
+	char ptrbuf[32], *p;
+
+	if(!n) return;
+
+	for(i=0; i<lvl; i++) {
+		fputs("|  ", stdout);
+	}
+
+	sprintf(ptrbuf, "%p", (void*)n);
+	p = ptrbuf + strlen(ptrbuf) - 4;
+
+	if(n->nref) {
+		printf("+-(%d) %s: <%d %d %d> #%d", n->lvl, p, n->r / n->nref, n->g / n->nref,
+				n->b / n->nref, n->nref);
+	} else {
+		printf("+-(%d) %s: <- - -> #0", n->lvl, p);
+	}
+	if(n->palidx >= 0) printf(" [%d]", n->palidx);
+	if(n->leaf) printf(" LEAF");
+	putchar('\n');
+
+	for(i=0; i<8; i++) {
+		print_tree(n->sub[i], lvl + 1);
+	}
+}
+
-- 
1.7.10.4