From: John Tsiombikas <nuclear@member.fsf.org>
Date: Tue, 11 May 2021 01:49:01 +0000 (+0300)
Subject: pngdump: image quantization, first attempt at shademap generation
X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=gbajam21;a=commitdiff_plain;h=95693de3106b0304fe8e5c705c37e633f91a4ad5

pngdump: image quantization, first attempt at shademap generation
---

diff --git a/tools/pngdump/Makefile b/tools/pngdump/Makefile
index fcd3f4b..f6cbd9d 100644
--- a/tools/pngdump/Makefile
+++ b/tools/pngdump/Makefile
@@ -1,6 +1,7 @@
+CFLAGS = -pedantic -Wall -g
 LDFLAGS = -lpng -lz
 
-pngdump: main.o image.o
+pngdump: main.o image.o quant.o
 	$(CC) -o $@ $^ $(LDFLAGS)
 
 clean:
diff --git a/tools/pngdump/image.c b/tools/pngdump/image.c
index f276e63..5602354 100644
--- a/tools/pngdump/image.c
+++ b/tools/pngdump/image.c
@@ -127,7 +127,7 @@ int save_image(struct image *img, const char *fname)
 
 	txt.compression = PNG_TEXT_COMPRESSION_NONE;
 	txt.key = "Software";
-	txt.text = "img2tiles";
+	txt.text = "pngdump";
 	txt.text_length = 0;
 
 	if(setjmp(png_jmpbuf(png))) {
@@ -236,10 +236,12 @@ void blit(struct image *src, int sx, int sy, int w, int h, struct image *dst, in
 	}
 }
 
-static unsigned int get_pixel(struct image *img, int x, int y)
+unsigned int get_pixel(struct image *img, int x, int y)
 {
+	unsigned int r, g, b;
 	unsigned char *pptr;
 	unsigned short *pptr16;
+	unsigned int *pptr32;
 
 	switch(img->bpp) {
 	case 4:
@@ -248,9 +250,20 @@ static unsigned int get_pixel(struct image *img, int x, int y)
 	case 8:
 		pptr = img->pixels + y * img->pitch + x;
 		return *pptr;
+	case 15:
 	case 16:
 		pptr16 = (unsigned short*)(img->pixels + y * img->pitch + x * 2);
 		return *pptr16;
+	case 24:
+		pptr = img->pixels + y * img->pitch + x * 3;
+		r = pptr[0];
+		g = pptr[1];
+		b = pptr[2];
+		return r | (g << 8) | (b << 16);
+	case 32:
+		pptr32 = (unsigned int*)(img->pixels + y * img->pitch + x * 4);
+		return *pptr32;
+
 	default:
 		fprintf(stderr, "get_pixel not implemented for %d bpp\n", img->bpp);
 	}
@@ -258,7 +271,47 @@ static unsigned int get_pixel(struct image *img, int x, int y)
 	return 0;
 }
 
-static void put_pixel(struct image *img, int x, int y, unsigned int pix)
+unsigned int get_pixel_rgb(struct image *img, int x, int y, unsigned int *rgb)
+{
+	unsigned int pix = get_pixel(img, x, y);
+
+	switch(img->bpp) {
+	case 15:
+		rgb[0] = (pix & 0x7c00) >> 7;
+		rgb[1] = (pix & 0x03e0) >> 2;
+		rgb[2] = (pix & 0x001f) << 3;
+		rgb[0] |= ((rgb[0] & 8) >> 1) | ((rgb[0] & 8) >> 2) | ((rgb[0] & 8) >> 3);
+		rgb[1] |= ((rgb[1] & 8) >> 1) | ((rgb[1] & 8) >> 2) | ((rgb[1] & 8) >> 3);
+		rgb[2] |= ((rgb[2] & 8) >> 1) | ((rgb[2] & 8) >> 2) | ((rgb[2] & 8) >> 3);
+		break;
+
+	case 16:
+		rgb[0] = (pix & 0xf800) >> 8;
+		rgb[1] = (pix & 0x07e0) >> 3;
+		rgb[2] = (pix & 0x001f) << 3;
+		rgb[0] |= ((rgb[0] & 8) >> 1) | ((rgb[0] & 8) >> 2) | ((rgb[0] & 8) >> 3);
+		rgb[1] |= ((rgb[1] & 4) >> 1) | ((rgb[1] & 4) >> 2);
+		rgb[2] |= ((rgb[2] & 8) >> 1) | ((rgb[2] & 8) >> 2) | ((rgb[2] & 8) >> 3);
+		break;
+
+	case 24:
+	case 32:
+		rgb[0] = pix & 0xff;
+		rgb[1] = (pix >> 8) & 0xff;
+		rgb[2] = (pix >> 16) & 0xff;
+		break;
+
+	default:
+		assert(pix >= 0 && pix < img->cmap_ncolors);
+		rgb[0] = img->cmap[pix].r;
+		rgb[1] = img->cmap[pix].g;
+		rgb[2] = img->cmap[pix].b;
+	}
+
+	return pix;
+}
+
+void put_pixel(struct image *img, int x, int y, unsigned int pix)
 {
 	unsigned char *pptr;
 	unsigned short *pptr16;
@@ -291,16 +344,12 @@ static void put_pixel(struct image *img, int x, int y, unsigned int pix)
 void overlay_key(struct image *src, unsigned int key, struct image *dst)
 {
 	int i, j;
-	unsigned char *sptr, *dptr;
 	unsigned int pix;
 
 	assert(src->bpp == dst->bpp);
 	assert(src->width == dst->width);
 	assert(src->height == dst->height);
 
-	sptr = src->pixels;
-	dptr = dst->pixels;
-
 	for(i=0; i<dst->height; i++) {
 		for(j=0; j<dst->width; j++) {
 			pix = get_pixel(src, j, i);
@@ -310,3 +359,310 @@ void overlay_key(struct image *src, unsigned int key, struct image *dst)
 		}
 	}
 }
+
+#if 0
+/* ---- color quantization ---- */
+struct octnode;
+
+struct octree {
+	struct octnode *root;
+	struct octnode *levn[8];
+	int ncol, maxcol;
+};
+
+struct octnode {
+	struct octree *tree;
+	int r, g, b, nref;
+	int palidx;
+	int nsub;
+	struct octnode *sub[8];
+	struct octnode *next;
+};
+
+static void add_color(struct octree *ot, int r, int g, int b);
+static void reduce_colors(struct octree *ot);
+static int assign_colors(struct octnode *on, int next, struct cmapent *cmap);
+static int lookup_color(struct octree *ot, int r, int g, int b);
+static struct octnode *new_node(struct octree *ot, int lvl);
+static void del_node(struct octnode *on, int lvl);
+static void print_tree(struct octnode *n, int lvl);
+static int count_leaves(struct octnode *n);
+
+void quantize_image(struct image *img, int maxcol)
+{
+	int i, j, cidx;
+	unsigned int rgb[3];
+	struct octree ot = {0};
+	struct image newimg = *img;
+
+	if(img->bpp > 8) {
+		newimg.bpp = 8;
+		newimg.nchan = 1;
+		newimg.scansz = newimg.width;
+		newimg.pitch = 8 * img->pitch / img->bpp;
+	}
+
+	ot.root = new_node(&ot, 0);
+	ot.maxcol = maxcol;
+
+	for(i=0; i<img->height; i++) {
+		for(j=0; j<img->width; j++) {
+			get_pixel_rgb(img, j, i, rgb);
+			add_color(&ot, rgb[0], rgb[1], rgb[2]);
+
+			while(count_leaves(ot.root) > ot.maxcol) {
+			//while(ot.ncol > ot.maxcol) {
+				reduce_colors(&ot);
+			}
+		}
+	}
+
+	/* use created octree to generate the palette */
+	newimg.cmap_ncolors = assign_colors(ot.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(&ot, rgb[0], rgb[1], rgb[2]);
+			assert(cidx >= 0 && cidx < maxcol);
+			put_pixel(&newimg, j, i, cidx);
+		}
+	}
+
+	*img = newimg;
+}
+
+static int subidx(int bit, int r, int g, int b)
+{
+	assert(bit >= 0 && bit < 8);
+	bit = 7 - bit;
+	return ((r >> bit) & 1) | ((g >> (bit - 1)) & 2) | ((b >> (bit - 2)) & 4);
+}
+
+static int tree_height(struct octnode *on)
+{
+	int i, subh, max = 0;
+
+	if(!on) return 0;
+
+	for(i=0; i<8; i++) {
+		subh = tree_height(on->sub[i]);
+		if(subh > max) max = subh;
+	}
+	return max + 1;
+}
+
+static void add_color(struct octree *ot, int r, int g, int b)
+{
+	int i, idx;
+	struct octnode *on;
+
+	on = ot->root;
+	for(i=0; i<8; i++) {
+		idx = subidx(i, r, g, b);
+
+		if(!on->sub[idx]) {
+			on->sub[idx] = new_node(ot, i + 1);
+			if(i == 7) {
+				/* this only adds a color if the parent node was previously not
+				 * a leaf. Otherwise the new one just takes the parent's place
+				 */
+				ot->ncol++;
+			}
+			on->nsub++;
+		}
+
+		on->r += r;
+		on->g += g;
+		on->b += b;
+		on->nref++;
+
+		on = on->sub[idx];
+	}
+
+	on->r += r;
+	on->g += g;
+	on->b += b;
+	on->nref++;
+}
+
+static int count_nodes(struct octnode *n)
+{
+	int count = 0;
+	while(n) {
+		count++;
+		n = n->next;
+	}
+	return count;
+}
+
+static int count_leaves(struct octnode *n)
+{
+	int i, cnt;
+
+	if(!n) return 0;
+	if(n->nsub <= 0) return 1;
+
+	cnt = 0;
+	for(i=0; i<8; i++) {
+		cnt += count_leaves(n->sub[i]);
+	}
+	return cnt;
+}
+
+static void reduce_colors(struct octree *ot)
+{
+	int i, lvl, best_nref;
+	struct octnode *n, *best;
+
+	lvl = 8;
+	while(--lvl >= 0) {
+		best_nref = INT_MAX;
+		best = 0;
+		n = ot->levn[lvl];
+
+		while(n) {
+			if(n->nref < best_nref && n->nsub) {
+				best = n;
+				best_nref = n->nref;
+			}
+			n = n->next;
+		}
+
+		if(best) {
+			for(i=0; i<8; i++) {
+				if(best->sub[i]) {
+					del_node(best->sub[i], lvl + 1);
+					best->sub[i] = 0;
+				}
+			}
+			if(best->nsub) {
+				/* this wasn't previously a leaf, but now it is */
+				ot->ncol++;
+				best->nsub = 0;
+			}
+			break;
+		}
+	}
+}
+
+static int assign_colors(struct octnode *on, int next, struct cmapent *cmap)
+{
+	int i;
+
+	if(!on) return next;
+
+	if(on->nsub <= 0) {
+		assert(next < on->tree->maxcol);
+		cmap[next].r = on->r / on->nref;
+		cmap[next].g = on->g / on->nref;
+		cmap[next].b = on->b / on->nref;
+		on->palidx = next++;
+	}
+
+	for(i=0; i<8; i++) {
+		next = assign_colors(on->sub[i], next, cmap);
+	}
+	return next;
+}
+
+static int lookup_color(struct octree *ot, int r, int g, int b)
+{
+	int i, idx;
+	struct octnode *on = ot->root;
+
+	for(i=0; i<8; i++) {
+		idx = subidx(i, r, g, b);
+		if(!on->sub[idx]) break;
+		on = on->sub[idx];
+	}
+
+	return on->palidx;
+}
+
+static int have_node(struct octnode *list, struct octnode *n)
+{
+	while(list) {
+		if(list == n) return 1;
+		list = list->next;
+	}
+	return 0;
+}
+
+static struct octnode *new_node(struct octree *ot, int lvl)
+{
+	struct octnode *on;
+
+	if(!(on = calloc(1, sizeof *on))) {
+		perror("failed to allocate octree node");
+		abort();
+	}
+
+	on->tree = ot;
+	on->palidx = -1;
+
+	if(lvl < 8) {
+		if(have_node(ot->levn[lvl], on)) {
+			fprintf(stderr, "double-insertion!\n");
+			abort();
+		}
+		on->next = ot->levn[lvl];
+		ot->levn[lvl] = on;
+	}
+	return on;
+}
+
+static void del_node(struct octnode *on, int lvl)
+{
+	int i;
+	struct octree *ot;
+	struct octnode dummy, *prev;
+
+	if(!on) return;
+	ot = on->tree;
+
+	if(!on->nsub) {
+		ot->ncol--;	/* removing a leaf removes a color */
+	}
+
+	for(i=0; i<8; i++) {
+		del_node(on->sub[i], lvl + 1);
+	}
+
+	if(lvl < 8) {
+		dummy.next = ot->levn[lvl];
+		prev = &dummy;
+
+		while(prev->next) {
+			if(prev->next == on) {
+				prev->next = on->next;
+				break;
+			}
+			prev = prev->next;
+		}
+		ot->levn[lvl] = dummy.next;
+	}
+
+	free(on);
+}
+
+static void print_tree(struct octnode *n, int lvl)
+{
+	int i;
+
+	if(!n) return;
+
+	for(i=0; i<lvl; i++) {
+		fputs("|  ", stdout);
+	}
+
+	printf("+-%p: <%d %d %d> #%d", (void*)n, n->r, n->g, n->b, n->nref);
+	if(n->palidx >= 0) printf(" [%d]\n", n->palidx);
+	putchar('\n');
+
+	for(i=0; i<8; i++) {
+		print_tree(n->sub[i], lvl + 1);
+	}
+}
+#endif
diff --git a/tools/pngdump/image.h b/tools/pngdump/image.h
index 7a42fba..d5aaccf 100644
--- a/tools/pngdump/image.h
+++ b/tools/pngdump/image.h
@@ -9,7 +9,8 @@ struct image {
 	int width, height;
 	int bpp;
 	int nchan;
-	int scansz, pitch;
+	int scansz;	/* scanline size in bytes */
+	int pitch;	/* bytes from one scanline to the next */
 	int cmap_ncolors;
 	struct cmapent cmap[256];
 	unsigned char *pixels;
@@ -24,4 +25,12 @@ int cmp_image(struct image *a, struct image *b);
 void blit(struct image *src, int sx, int sy, int w, int h, struct image *dst, int dx, int dy);
 void overlay_key(struct image *src, unsigned int key, struct image *dst);
 
+unsigned int get_pixel(struct image *img, int x, int y);
+unsigned int get_pixel_rgb(struct image *img, int x, int y, unsigned int *rgb);
+void put_pixel(struct image *img, int x, int y, unsigned int pix);
+
+void quantize_image(struct image *img, int maxcol);
+int gen_shade_lut(struct image *img, int levels, int maxcol, struct cmapent *shade_cmap,
+		int *shade_lut);
+
 #endif	/* IMAGE_H_ */
diff --git a/tools/pngdump/main.c b/tools/pngdump/main.c
index d7aba3e..9f281cc 100644
--- a/tools/pngdump/main.c
+++ b/tools/pngdump/main.c
@@ -5,6 +5,14 @@
 #include <assert.h>
 #include "image.h"
 
+enum {
+	MODE_PIXELS,
+	MODE_CMAP,
+	MODE_INFO,
+	MODE_SHADE_CMAP,
+	MODE_SHADE_LUT
+};
+
 void print_usage(const char *argv0);
 
 int main(int argc, char **argv)
@@ -17,21 +25,39 @@ int main(int argc, char **argv)
 	int num_infiles = 0;
 	struct image img, tmpimg;
 	FILE *out = stdout;
+	struct cmapent shade_cmap[256] = {0};
+	int *shade_lut = 0;
+	int shade_levels = 8;
 
 	for(i=1; i<argc; i++) {
 		if(argv[i][0] == '-') {
 			if(argv[i][2] == 0) {
 				switch(argv[i][1]) {
 				case 'p':
-					mode = 0;
+					mode = MODE_PIXELS;
 					break;
 
 				case 'c':
-					mode = 1;
+					mode = MODE_CMAP;
 					break;
 
 				case 'i':
-					mode = 2;
+					mode = MODE_INFO;
+					break;
+
+				case 'C':
+					mode = MODE_SHADE_CMAP;
+					break;
+
+				case 'S':
+					mode = MODE_SHADE_LUT;
+					break;
+
+				case 's':
+					if(!argv[++i] || (shade_levels = atoi(argv[i])) == 0) {
+						fprintf(stderr, "-s must be followed by the number of shade levels\n");
+						return 1;
+					}
 					break;
 
 				case 't':
@@ -113,11 +139,11 @@ int main(int argc, char **argv)
 	}
 
 	switch(mode) {
-	case 0:
+	case MODE_PIXELS:
 		fwrite(img.pixels, 1, img.scansz * img.height, out);
 		break;
 
-	case 1:
+	case MODE_CMAP:
 		if(text) {
 			for(i=0; i<img.cmap_ncolors; i++) {
 				printf("%d %d %d\n", img.cmap[i].r, img.cmap[i].g, img.cmap[i].b);
@@ -128,7 +154,7 @@ int main(int argc, char **argv)
 		}
 		break;
 
-	case 2:
+	case MODE_INFO:
 		printf("size: %dx%d\n", img.width, img.height);
 		printf("bit depth: %d\n", img.bpp);
 		printf("scanline size: %d bytes\n", img.scansz);
@@ -138,6 +164,28 @@ int main(int argc, char **argv)
 			printf("color channels: %d\n", img.nchan);
 		}
 		break;
+
+	case MODE_SHADE_LUT:
+		if(!(shade_lut = malloc(256 * shade_levels * sizeof *shade_lut))) {
+			fprintf(stderr, "failed to allocate shading look-up table\n");
+			return 1;
+		}
+	case MODE_SHADE_CMAP:
+		if(!img.cmap_ncolors) {
+			fprintf(stderr, "can't generate shade levels for non-indexed images\n");
+			return 1;
+		}
+		if(gen_shade_lut(&img, shade_levels, 256, shade_cmap, shade_lut) == -1) {
+			return 1;
+		}
+		if(mode == MODE_SHADE_CMAP) {
+			fwrite(shade_cmap, sizeof shade_cmap, 1, out);
+		} else {
+			for(i=0; i<img.cmap_ncolors * shade_levels; i++) {
+				fputc(shade_lut[i], out);
+			}
+		}
+		break;
 	}
 
 	fclose(out);
@@ -151,6 +199,9 @@ void print_usage(const char *argv0)
 	printf(" -o <output file>: specify output file (default: stdout)\n");
 	printf(" -p: dump pixels (default)\n");
 	printf(" -c: dump colormap (palette) entries\n");
+	printf(" -C: generate shading colormap\n");
+	printf(" -S: generate shading LUT\n");
+	printf(" -s <shade levels>: used in conjunction with -C or -S (default: 8)\n");
 	printf(" -i: print image information\n");
 	printf(" -t: dump as text\n");
 	printf(" -n: swap the order of nibbles (for 4bpp)\n");