From c01146f8ecd395bfcdeb8af3b50f8a9ab2b87488 Mon Sep 17 00:00:00 2001
From: John Tsiombikas <nuclear@member.fsf.org>
Date: Mon, 18 Dec 2023 03:45:58 +0200
Subject: [PATCH] foo

---
 Makefile               |   19 +-
 doc/vmem               |    7 +
 src/data.s             |    9 +
 src/debug.c            |   75 ++++++
 src/debug.h            |   12 +
 src/hwregs.h           |   10 +-
 src/libc/ctype.c       |   56 ++++
 src/libc/ctype.h       |   17 ++
 src/libc/inttypes.h    |   12 -
 src/libc/stdio.c       |  301 +++++++++++++++++++++
 src/libc/stdio.h       |   21 ++
 src/libc/stdlib.c      |  195 ++++++++++++++
 src/libc/stdlib.h      |   30 +++
 src/libc/string.c      |  218 ++++++++++++++++
 src/libc/string.h      |   32 +++
 src/main.c             |    7 +-
 src/vdp.S              |   21 +-
 src/vdp.h              |   12 +-
 tools/pngdump/Makefile |   10 +
 tools/pngdump/image.c  |  676 ++++++++++++++++++++++++++++++++++++++++++++++++
 tools/pngdump/image.h  |   38 +++
 tools/pngdump/main.c   |  467 +++++++++++++++++++++++++++++++++
 tools/pngdump/quant.c  |  396 ++++++++++++++++++++++++++++
 tools/pngdump/tiles.c  |   61 +++++
 tools/pngdump/tiles.h  |   14 +
 25 files changed, 2689 insertions(+), 27 deletions(-)
 create mode 100644 doc/vmem
 create mode 100644 src/data.s
 create mode 100644 src/debug.c
 create mode 100644 src/debug.h
 create mode 100644 src/libc/ctype.c
 create mode 100644 src/libc/ctype.h
 delete mode 100644 src/libc/inttypes.h
 create mode 100644 src/libc/stdio.c
 create mode 100644 src/libc/stdio.h
 create mode 100644 src/libc/stdlib.c
 create mode 100644 src/libc/stdlib.h
 create mode 100644 src/libc/string.c
 create mode 100644 src/libc/string.h
 create mode 100644 tools/pngdump/Makefile
 create mode 100644 tools/pngdump/image.c
 create mode 100644 tools/pngdump/image.h
 create mode 100644 tools/pngdump/main.c
 create mode 100644 tools/pngdump/quant.c
 create mode 100644 tools/pngdump/tiles.c
 create mode 100644 tools/pngdump/tiles.h

diff --git a/Makefile b/Makefile
index e6043d4..8f84751 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 csrc = $(wildcard src/*.c) $(wildcard src/libc/*.c)
 asrc = $(wildcard src/*.s)
 aSsrc = $(wildcard src/*.S)
-obj = $(asrc:.s=.o) $(aSsrc:.S=.o) $(csrc:.c=.o)
+obj = $(asrc:.s=-asm.o) $(aSsrc:.S=-asm.o) $(csrc:.c=.o)
 dep = $(csrc:.c=.d)
 
 z80src = $(wildcard src/z80/*.asm)
@@ -46,10 +46,17 @@ $(elf): $(obj)
 $(z80bin): $(z80obj)
 	$(Z80LD) -o $@ $(Z80LDFLAGS) $(z80obj)
 
-src/z80prog.o: src/z80prog.s $(z80bin)
+src/data.o: src/data.s data/font8x8.img
+src/z80prog-asm.o: src/z80prog.s $(z80bin)
 
 -include $(dep)
 
+%-asm.o: %.s
+	$(AS) -o $@ $(ASFLAGS) $<
+
+%-asm.o: %.S
+	$(CC) -o $@ $(ASFLAGS) -c $<
+
 %.z80: %.asm
 	$(Z80AS) -o $@ $(Z80ASFLAGS) $< >/dev/null
 
@@ -77,3 +84,11 @@ install: $(bin)
 	[ -f /media/usbmass/MEGA/MEGA.RBF ] || cp $(bin) /media/usbmass/MEGA/MEGA.BIN
 	umount /media/usbmass
 
+# ---- tools ----
+PNGDUMP = tools/pngdump/pngdump
+
+$(PNGDUMP): tools/pngdump/main.c tools/pngdump/image.c tools/pngdump/quant.c
+	$(MAKE) -C tools/pngdump
+
+%.img: %.png $(PNGDUMP)
+	$(PNGDUMP) -o $@ -oc $(@:.img=.cmap) -T 8x8 $<
diff --git a/doc/vmem b/doc/vmem
new file mode 100644
index 0000000..266a06d
--- /dev/null
+++ b/doc/vmem
@@ -0,0 +1,7 @@
+0000
+8000
+b400	font 96 glyphs * 8x8 / 2 = 3072 bytes
+c000	nametable A (64x32 * 2 = 4096)
+d000	nametable B
+e000	sprite table (?)
+ffff
diff --git a/src/data.s b/src/data.s
new file mode 100644
index 0000000..2c07f8a
--- /dev/null
+++ b/src/data.s
@@ -0,0 +1,9 @@
+	.section .rodata
+
+	.globl font8x8_data
+	.globl font8x8_data_end
+font8x8_data:
+	.incbin "data/font8x8.img"
+font8x8_data_end:
+
+| vi:ft=gas68k:
diff --git a/src/debug.c b/src/debug.c
new file mode 100644
index 0000000..d6220c0
--- /dev/null
+++ b/src/debug.c
@@ -0,0 +1,75 @@
+#include <stdio.h>
+#include <stdarg.h>
+#include <stdint.h>
+#include "debug.h"
+#include "vdp.h"
+
+#define FONT_ADDR	0xb400
+
+extern uint16_t font8x8_data[], font8x8_data_end[];
+
+static int cur_x, cur_y, left_margin;
+
+
+void dbg_init(void)
+{
+	uint16_t *src = font8x8_data;
+
+	vdp_setup_addr(VDP_VRAM, FONT_ADDR);
+	while(src < font8x8_data_end) {
+		VDP_DATA = *src++;
+	}
+}
+
+#define TILESZ	32
+
+void dbg_printchar(int x, int y, char c)
+{
+	unsigned int addr = 0xc000 + (y << 7) + (x << 1);	/* 64x32 scroll size */
+	int tile = (c - 32) + (FONT_ADDR / TILESZ);
+	vdp_setup_addr(VDP_VRAM, addr);
+	VDP_DATA = VDP_TILENAME(tile, 0, 0);
+}
+
+void dbg_printstr(int x, int y, const char *str)
+{
+	if(!*str) return;
+
+	/* put the first char to set up the address once */
+	dbg_printchar(x++, y, *str++);
+
+	while(*str && x < 40) {		/* 40 visible cells across in H40 (320) mode */
+		int tile = (*str++ - 32) + (FONT_ADDR / TILESZ);
+		VDP_DATA = VDP_TILENAME(tile, 0, 0);
+	}
+}
+
+void dbg_setcursor(int x, int y)
+{
+	cur_x = x;
+	cur_y = y;
+	left_margin = x;
+}
+
+void dbg_putchar(int c)
+{
+	switch(c) {
+	case '\n':
+		cur_x = left_margin;
+		cur_y++;
+		break;
+
+	case '\b':
+		if(cur_x > left_margin) {
+			dbg_printchar(--cur_x, cur_y, ' ');
+		}
+		break;
+
+	case '\t':
+		cur_x = (cur_x + 8) & 0xf8;
+		break;
+
+	default:
+		dbg_printchar(cur_x++, cur_y, c);
+	}
+}
diff --git a/src/debug.h b/src/debug.h
new file mode 100644
index 0000000..0bf525d
--- /dev/null
+++ b/src/debug.h
@@ -0,0 +1,12 @@
+#ifndef DEBUG_H_
+#define DEBUG_H_
+
+void dbg_init(void);
+
+void dbg_printchar(int x, int y, char c);
+void dbg_printstr(int x, int y, const char *str);
+
+void dbg_setcursor(int x, int y);
+void dbg_putchar(int c);
+
+#endif	/* DEBUG_H_ */
diff --git a/src/hwregs.h b/src/hwregs.h
index 6dd8a74..c018023 100644
--- a/src/hwregs.h
+++ b/src/hwregs.h
@@ -10,7 +10,7 @@
 #define VDP_VSRAM	0x40000010
 
 #ifndef ASM
-#include <inttypes.h>
+#include <stdint.h>
 
 #define REG16PTR(addr)	(*(volatile uint16_t*)(addr))
 #define REG32PTR(addr)	(*(volatile uint32_t*)(addr))
@@ -68,12 +68,14 @@
 #define VDP_M2_VINTR	0x20
 #define VDP_M2_DISP		0x40
 
-#define VDP_NA_ADDR(x)	(((x) >> 14) & 0x38)
-#define VDP_NW_ADDR(x)	(((x) >> 14) & 0x3e)
-#define VDP_NB_ADDR(x)	((x) >> 17)
+#define VDP_NA_ADDR(x)	(((x) >> 10) & 0x38)
+#define VDP_NW_ADDR(x)	(((x) >> 10) & 0x3e)
+#define VDP_NB_ADDR(x)	((x) >> 13)
 #define VDP_SPRTAB_ADDR(x)	((x) >> 9)
 #define VDP_HSTAB_ADDR(x)	((x) >> 10)
 
+#define VDP_ADDR_INVAL	0x10000
+
 #define VDP_BGCOL(pal, col)	(((pal) << 4) | (col))
 
 #define VDP_M3_HFULL	0
diff --git a/src/libc/ctype.c b/src/libc/ctype.c
new file mode 100644
index 0000000..f720566
--- /dev/null
+++ b/src/libc/ctype.c
@@ -0,0 +1,56 @@
+#include "ctype.h"
+
+int isalnum(int c)
+{
+	return isalpha(c) || isdigit(c);
+}
+
+int isalpha(int c)
+{
+	return isupper(c) || islower(c);
+}
+
+int isblank(int c)
+{
+	return c == ' ' || c == '\t';
+}
+
+int isdigit(int c)
+{
+	return c >= '0' && c <= '9';
+}
+
+int isupper(int c)
+{
+	return c >= 'A' && c <= 'Z';
+}
+
+int islower(int c)
+{
+	return c >= 'a' && c <= 'z';
+}
+
+int isgraph(int c)
+{
+	return c > ' ' && c <= '~';
+}
+
+int isprint(int c)
+{
+	return isgraph(c) || c == ' ';
+}
+
+int isspace(int c)
+{
+	return isblank(c) || c == '\f' || c == '\n' || c == '\r' || c == '\v';
+}
+
+int toupper(int c)
+{
+	return islower(c) ? (c + ('A' - 'a')) : c;
+}
+
+int tolower(int c)
+{
+	return isupper(c) ? (c - ('A' - 'a')) : c;
+}
diff --git a/src/libc/ctype.h b/src/libc/ctype.h
new file mode 100644
index 0000000..5b010d4
--- /dev/null
+++ b/src/libc/ctype.h
@@ -0,0 +1,17 @@
+#ifndef CTYPE_H_
+#define CTYPE_H_
+
+int isalnum(int c);
+int isalpha(int c);
+#define isascii(c)	((c) < 128)
+int isblank(int c);
+int isdigit(int c);
+int isupper(int c);
+int islower(int c);
+int isprint(int c);
+int isspace(int c);
+
+int toupper(int c);
+int tolower(int c);
+
+#endif	/* CTYPE_H_ */
diff --git a/src/libc/inttypes.h b/src/libc/inttypes.h
deleted file mode 100644
index fcbf7e1..0000000
--- a/src/libc/inttypes.h
+++ /dev/null
@@ -1,12 +0,0 @@
-#ifndef INTTYPES_H_
-#define INTTYPES_H_
-
-typedef signed char int8_t;
-typedef short int16_t;
-typedef long int32_t;
-
-typedef unsigned char uint8_t;
-typedef unsigned short uint16_t;
-typedef unsigned long uint32_t;
-
-#endif	/* INTTYPES_H_ */
diff --git a/src/libc/stdio.c b/src/libc/stdio.c
new file mode 100644
index 0000000..80da880
--- /dev/null
+++ b/src/libc/stdio.c
@@ -0,0 +1,301 @@
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include "debug.h"
+
+enum {
+	OUT_DEF,
+	OUT_BUF,
+	OUT_SCR
+};
+
+static int intern_printf(int out, char *buf, size_t sz, const char *fmt, va_list ap);
+static void bwrite(int out, char *buf, size_t buf_sz, char *str, int sz);
+
+int putchar(int c)
+{
+	dbg_putchar(c);
+	return c;
+}
+
+int puts(const char *s)
+{
+	while(*s) {
+		putchar(*s++);
+	}
+	putchar('\n');
+	return 0;
+}
+
+/* -- printf and friends -- */
+
+int printf(const char *fmt, ...)
+{
+	int res;
+	va_list ap;
+
+	va_start(ap, fmt);
+	res = intern_printf(OUT_DEF, 0, 0, fmt, ap);
+	va_end(ap);
+	return res;
+}
+
+int vprintf(const char *fmt, va_list ap)
+{
+	return intern_printf(OUT_DEF, 0, 0, fmt, ap);
+}
+
+int sprintf(char *buf, const char *fmt, ...)
+{
+	int res;
+	va_list ap;
+
+	va_start(ap, fmt);
+	res = intern_printf(OUT_BUF, buf, 0, fmt, ap);
+	va_end(ap);
+	return res;
+}
+
+int vsprintf(char *buf, const char *fmt, va_list ap)
+{
+	return intern_printf(OUT_BUF, buf, 0, fmt, ap);
+}
+
+int snprintf(char *buf, size_t sz, const char *fmt, ...)
+{
+	int res;
+	va_list ap;
+
+	va_start(ap, fmt);
+	res = intern_printf(OUT_BUF, buf, sz, fmt, ap);
+	va_end(ap);
+	return res;
+}
+
+int vsnprintf(char *buf, size_t sz, const char *fmt, va_list ap)
+{
+	return intern_printf(OUT_BUF, buf, sz, fmt, ap);
+}
+
+/* intern_printf provides all the functionality needed by all the printf
+ * variants.
+ * - buf: optional buffer onto which the formatted results are written. If null
+ *   then the output goes to the terminal through putchar calls. This is used
+ *   by the (v)sprintf variants which write to an array of char.
+ * - sz: optional maximum size of the output, 0 means unlimited. This is used
+ *   by the (v)snprintf variants to avoid buffer overflows.
+ * The rest are obvious, format string and variable argument list.
+ */
+static char *convc = "dioxXucsfeEgGpn%";
+
+#define IS_CONV(c)	strchr(convc, c)
+
+#define BUF(x)	((x) ? (x) + cnum : (x))
+#define SZ(x)	((x) ? (x) - cnum : (x))
+
+static int intern_printf(int out, char *buf, size_t sz, const char *fmt, va_list ap)
+{
+	char conv_buf[32];
+	char *str;
+	int i, slen;
+	const char *fstart = 0;
+
+	/* state */
+	int cnum = 0;
+	int base = 10;
+	int alt = 0;
+	int fwidth = 0;
+	int padc = ' ';
+	int sign = 0;
+	int left_align = 0;
+	int hex_caps = 0;
+	int unsig = 0;
+	int num, unum;
+
+	while(*fmt) {
+		if(*fmt == '%') {
+			fstart = fmt++;
+			continue;
+		}
+
+		if(fstart) {
+			if(IS_CONV(*fmt)) {
+				switch(*fmt) {
+				case 'X':
+					hex_caps = 1;
+
+				case 'x':
+				case 'p':
+					base = 16;
+
+					if(alt) {
+						bwrite(out, BUF(buf), SZ(sz), "0x", 2);
+						cnum += 2;
+					}
+
+				case 'u':
+					unsig = 1;
+
+					if(0) {
+				case 'o':
+						base = 8;
+
+						if(alt) {
+							bwrite(out, BUF(buf), SZ(sz), "0", 1);
+							cnum++;
+						}
+					}
+
+				case 'd':
+				case 'i':
+					if(unsig) {
+						unum = va_arg(ap, unsigned int);
+						utoa(unum, conv_buf, base);
+					} else {
+						num = va_arg(ap, int);
+						itoa(num, conv_buf, base);
+					}
+					if(hex_caps) {
+						for(i=0; conv_buf[i]; i++) {
+							conv_buf[i] = toupper(conv_buf[i]);
+						}
+					}
+
+					slen = strlen(conv_buf);
+
+					if(left_align) {
+						if(!unsig && sign && num >= 0) {
+							bwrite(out, BUF(buf), SZ(sz), "+", 1);
+							cnum++;
+						}
+						bwrite(out, BUF(buf), SZ(sz), conv_buf, slen);
+						cnum += slen;
+						padc = ' ';
+					}
+					for(i=slen; i<fwidth; i++) {
+						bwrite(out, BUF(buf), SZ(sz), (char*)&padc, 1);
+						cnum++;
+					}
+					if(!left_align) {
+						if(!unsig && sign && num >= 0) {
+							bwrite(out, BUF(buf), SZ(sz), "+", 1);
+							cnum++;
+						}
+						bwrite(out, BUF(buf), SZ(sz), conv_buf, slen);
+						cnum += slen;
+					}
+					break;
+
+				case 'c':
+					{
+						char c = va_arg(ap, int);
+						bwrite(out, BUF(buf), SZ(sz), &c, 1);
+						cnum++;
+					}
+					break;
+
+				case 's':
+					str = va_arg(ap, char*);
+					slen = strlen(str);
+
+					if(left_align) {
+						bwrite(out, BUF(buf), SZ(sz), str, slen);
+						cnum += slen;
+						padc = ' ';
+					}
+					for(i=slen; i<fwidth; i++) {
+						bwrite(out, BUF(buf), SZ(sz), (char*)&padc, 1);
+						cnum++;
+					}
+					if(!left_align) {
+						bwrite(out, BUF(buf), SZ(sz), str, slen);
+						cnum += slen;
+					}
+					break;
+
+				case 'n':
+					*va_arg(ap, int*) = cnum;
+					break;
+
+				default:
+					break;
+				}
+
+				/* restore default conversion state */
+				base = 10;
+				alt = 0;
+				fwidth = 0;
+				padc = ' ';
+				hex_caps = 0;
+
+				fstart = 0;
+				fmt++;
+			} else {
+				switch(*fmt) {
+				case '#':
+					alt = 1;
+					break;
+
+				case '+':
+					sign = 1;
+					break;
+
+				case '-':
+					left_align = 1;
+					break;
+
+				case 'l':
+				case 'L':
+					break;
+
+				case '0':
+					padc = '0';
+					break;
+
+				default:
+					if(isdigit(*fmt)) {
+						const char *fw = fmt;
+						while(*fmt && isdigit(*fmt)) fmt++;
+
+						fwidth = atoi(fw);
+						continue;
+					}
+				}
+				fmt++;
+			}
+		} else {
+			bwrite(out, BUF(buf), SZ(sz), (char*)fmt++, 1);
+			cnum++;
+		}
+	}
+
+	return cnum;
+}
+
+
+/* bwrite is called by intern_printf to transparently handle writing into a
+ * buffer or to the terminal
+ */
+static void bwrite(int out, char *buf, size_t buf_sz, char *str, int sz)
+{
+	int i;
+
+	if(out == OUT_BUF) {
+		if(buf_sz && buf_sz <= sz) sz = buf_sz;
+		buf[sz] = 0;
+		memcpy(buf, str, sz);
+	} else {
+		switch(out) {
+		case OUT_DEF:
+			for(i=0; i<sz; i++) {
+				putchar(*str++);
+			}
+			break;
+
+		default:
+			/* TODO: OUT_SCR */
+			break;
+		}
+	}
+}
+
diff --git a/src/libc/stdio.h b/src/libc/stdio.h
new file mode 100644
index 0000000..3b3e905
--- /dev/null
+++ b/src/libc/stdio.h
@@ -0,0 +1,21 @@
+#ifndef STDIO_H_
+#define STDIO_H_
+
+#include <stdlib.h>
+#include <stdarg.h>
+
+int putchar(int c);
+int puts(const char *s);
+
+int printf(const char *fmt, ...);
+int vprintf(const char *fmt, va_list ap);
+
+int sprintf(char *buf, const char *fmt, ...);
+int vsprintf(char *buf, const char *fmt, va_list ap);
+
+int snprintf(char *buf, size_t sz, const char *fmt, ...);
+int vsnprintf(char *buf, size_t sz, const char *fmt, va_list ap);
+
+void perror(const char *s);
+
+#endif	/* STDIO_H_ */
diff --git a/src/libc/stdlib.c b/src/libc/stdlib.c
new file mode 100644
index 0000000..a6149e9
--- /dev/null
+++ b/src/libc/stdlib.c
@@ -0,0 +1,195 @@
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <limits.h>
+#include <assert.h>
+#include <alloca.h>
+
+int atoi(const char *str)
+{
+	return strtol(str, 0, 10);
+}
+
+long atol(const char *str)
+{
+	return strtol(str, 0, 10);
+}
+
+long strtol(const char *str, char **endp, int base)
+{
+	long acc = 0;
+	int sign = 1;
+	int valid = 0;
+	const char *start = str;
+
+	while(isspace(*str)) str++;
+
+	if(base == 0) {
+		if(str[0] == '0') {
+			if(str[1] == 'x' || str[1] == 'X') {
+				base = 16;
+			} else {
+				base = 8;
+			}
+		} else {
+			base = 10;
+		}
+	}
+
+	if(*str == '+') {
+		str++;
+	} else if(*str == '-') {
+		sign = -1;
+		str++;
+	}
+
+	while(*str) {
+		long val = LONG_MAX;
+		char c = tolower(*str);
+
+		if(isdigit(c)) {
+			val = *str - '0';
+		} else if(c >= 'a' && c <= 'f') {
+			val = 10 + c - 'a';
+		} else {
+			break;
+		}
+		if(val >= base) {
+			break;
+		}
+		valid = 1;
+
+		acc = acc * base + val;
+		str++;
+	}
+
+	if(endp) {
+		*endp = (char*)(valid ? str : start);
+	}
+
+	return sign > 0 ? acc : -acc;
+}
+
+void itoa(int val, char *buf, int base)
+{
+	static char rbuf[16];
+	char *ptr = rbuf;
+	int neg = 0;
+
+	if(val < 0) {
+		neg = 1;
+		val = -val;
+	}
+
+	if(val == 0) {
+		*ptr++ = '0';
+	}
+
+	while(val) {
+		int digit = val % base;
+		*ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
+		val /= base;
+	}
+
+	if(neg) {
+		*ptr++ = '-';
+	}
+
+	ptr--;
+
+	while(ptr >= rbuf) {
+		*buf++ = *ptr--;
+	}
+	*buf = 0;
+}
+
+void utoa(unsigned int val, char *buf, int base)
+{
+	static char rbuf[16];
+	char *ptr = rbuf;
+
+	if(val == 0) {
+		*ptr++ = '0';
+	}
+
+	while(val) {
+		unsigned int digit = val % base;
+		*ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
+		val /= base;
+	}
+
+	ptr--;
+
+	while(ptr >= rbuf) {
+		*buf++ = *ptr--;
+	}
+	*buf = 0;
+}
+
+#define QSORT_THRESHOLD	4
+#define ITEM(idx)	((char*)arr + (idx) * itemsz)
+
+#define SWAP(p, q) \
+	do { \
+		int nn = itemsz; \
+		char *pp = (p); \
+		char *qq = (q); \
+		do { \
+			char tmp = *pp; \
+			*pp++ = *qq; \
+			*qq++ = tmp; \
+		} while(--nn > 0); \
+	} while(0)
+
+static void ins_sort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
+{
+	int i;
+	char *it, *a, *b;
+
+	if(count <= 1) return;
+
+	it = (char*)arr + itemsz;
+	for(i=1; i<count; i++) {
+		a = it;
+		it += itemsz;
+		while(a > (char*)arr && cmp(a, (b = a - itemsz)) < 0) {
+			SWAP(a, b);
+			a -= itemsz;
+		}
+	}
+}
+
+void qsort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
+{
+	char *ma, *mb, *mc, *left, *right;
+	size_t sepidx, nleft, nright;
+
+	if(count <= 1) return;
+
+	if(count < QSORT_THRESHOLD) {
+		ins_sort(arr, count, itemsz, cmp);
+		return;
+	}
+
+	ma = arr;
+	mb = ITEM(count / 2);
+	mc = ITEM(count - 1);
+	if(cmp(ma, mb) < 0) SWAP(ma, mb);
+	if(cmp(mc, ma) < 0) SWAP(mc, ma);
+
+	left = ma + itemsz;
+	right = mc - itemsz;
+	for(;;) {
+		while(cmp(left, ma) < 0) left += itemsz;
+		while(cmp(ma, right) < 0) right -= itemsz;
+		if(left >= right) break;
+		SWAP(left, right);
+	}
+	SWAP(ma, right);
+	sepidx = (right - (char*)arr) / itemsz;
+	nleft = sepidx;
+	nright = count - nleft - 1;
+
+	qsort(ma, nleft, itemsz, cmp);
+	qsort(right + itemsz, nright, itemsz, cmp);
+}
diff --git a/src/libc/stdlib.h b/src/libc/stdlib.h
new file mode 100644
index 0000000..961ed8e
--- /dev/null
+++ b/src/libc/stdlib.h
@@ -0,0 +1,30 @@
+#ifndef STDLIB_H_
+#define STDLIB_H_
+
+#include <stddef.h>
+
+#define RAND_MAX	2147483647
+
+#define abs(x)	__builtin_abs(x)
+
+int atoi(const char *str);
+long atol(const char *str);
+long strtol(const char *str, char **endp, int base);
+
+void itoa(int val, char *buf, int base);
+void utoa(unsigned int val, char *buf, int base);
+
+void qsort(void *arr, size_t count, size_t size, int (*cmp)(const void*, const void*));
+
+int rand(void);
+int rand_r(unsigned int *seedp);
+void srand(unsigned int seed);
+
+/* defined in malloc.c */
+/*void *malloc(size_t sz);
+void *calloc(size_t num, size_t sz);
+void *realloc(void *ptr, size_t sz);
+void free(void *ptr);
+*/
+
+#endif	/* STDLIB_H_ */
diff --git a/src/libc/string.c b/src/libc/string.c
new file mode 100644
index 0000000..81aa415
--- /dev/null
+++ b/src/libc/string.c
@@ -0,0 +1,218 @@
+#include <string.h>
+#include <ctype.h>
+#include <stdint.h>
+#include <stddef.h>
+
+void *memcpy(void *dest, const void *src, size_t n)
+{
+	size_t i;
+	char *dptr = dest;
+	const char *sptr = src;
+	for(i=0; i<n; i++) {
+		dptr[i] = sptr[i];
+	}
+
+	return dest;
+}
+
+void *memmove(void *dest, const void *src, size_t n)
+{
+	int i;
+	char *dptr;
+	const char *sptr;
+
+	if(dest <= src) {
+		/* forward copy */
+		dptr = dest;
+		sptr = src;
+		for(i=0; i<n; i++) {
+			*dptr++ = *sptr++;
+		}
+	} else {
+		/* backwards copy */
+		dptr = (char*)dest + n - 1;
+		sptr = (const char*)src + n - 1;
+		for(i=0; i<n; i++) {
+			*dptr-- = *sptr--;
+		}
+	}
+
+	return dest;
+}
+
+int memcmp(void *aptr, void *bptr, size_t n)
+{
+	int i, startoffs, diff;
+	uint32_t *a32, *b32;
+	unsigned char *a = aptr;
+	unsigned char *b = bptr;
+
+	a32 = (uint32_t*)((intptr_t)(a + 3) & 0xfffffffc);
+	b32 = (uint32_t*)((intptr_t)(b + 3) & 0xfffffffc);
+
+	/* if both are aligned the same way... */
+	if((startoffs = (unsigned char*)a32 - a) == (unsigned char*)b32 - b) {
+		/* catch-up to the 32bit alignment */
+		for(i=0; i<startoffs; i++) {
+			if((diff = *a++ - *b++) != 0 || --n <= 0) {
+				return diff;
+			}
+		}
+
+		/* compare 32bit at once */
+		while(n >= 4) {
+			if(*a32 != *b32) break;
+			a32++;
+			b32++;
+			n -= 4;
+		}
+
+		/* update byte pointers to contine with the tail */
+		a = (unsigned char*)a32;
+		b = (unsigned char*)b32;
+	}
+
+	/* we're here both for the tail-end of same-alignment buffers, or for the
+	 * whole length of mis-aligned buffers.
+	 */
+	while(n-- > 0) {
+		if((diff = *a++ - *b++) != 0) {
+			return diff;
+		}
+	}
+	return 0;
+}
+
+size_t strlen(const char *s)
+{
+	size_t len = 0;
+	while(*s++) len++;
+	return len;
+}
+
+char *strchr(const char *s, int c)
+{
+	while(*s) {
+		if(*s == c) {
+			return (char*)s;
+		}
+		s++;
+	}
+	return 0;
+}
+
+char *strrchr(const char *s, int c)
+{
+	const char *ptr = s;
+
+	/* find the end */
+	while(*ptr) ptr++;
+
+	/* go back checking for c */
+	while(--ptr >= s) {
+		if(*ptr == c) {
+			return (char*)ptr;
+		}
+	}
+	return 0;
+}
+
+char *strstr(const char *str, const char *substr)
+{
+	while(*str) {
+		const char *s1 = str;
+		const char *s2 = substr;
+
+		while(*s1 && *s1 == *s2) {
+			s1++;
+			s2++;
+		}
+		if(!*s2) {
+			return (char*)str;
+		}
+		str++;
+	}
+	return 0;
+}
+
+char *strcasestr(const char *str, const char *substr)
+{
+	while(*str) {
+		const char *s1 = str;
+		const char *s2 = substr;
+
+		while(*s1 && tolower(*s1) == tolower(*s2)) {
+			s1++;
+			s2++;
+		}
+		if(!*s2) {
+			return (char*)str;
+		}
+		str++;
+	}
+	return 0;
+}
+
+int strcmp(const char *s1, const char *s2)
+{
+	while(*s1 && *s1 == *s2) {
+		s1++;
+		s2++;
+	}
+	return *s1 - *s2;
+}
+
+int strcasecmp(const char *s1, const char *s2)
+{
+	while(*s1 && tolower(*s1) == tolower(*s2)) {
+		s1++;
+		s2++;
+	}
+	return tolower(*s1) - tolower(*s2);
+}
+
+int strncmp(const char *s1, const char *s2, int n)
+{
+	if(n <= 0) return 0;
+
+	while(n-- > 0 && *s1 && *s2 && *s1 == *s2) {
+		s1++;
+		s2++;
+	}
+
+	if(n <= 0) return 0;
+	return *s1 - *s2;
+}
+
+int strncasecmp(const char *s1, const char *s2, int n)
+{
+	if(n <= 0) return 0;
+
+	while(n-- > 0 && *s1 && *s2 && tolower(*s1) == tolower(*s2)) {
+		s1++;
+		s2++;
+	}
+
+	if(n <= 0) return 0;
+	return tolower(*s1) - tolower(*s2);
+}
+
+char *strcpy(char *dest, const char *src)
+{
+	char *dptr = dest;
+	while((*dptr++ = *src++));
+	return dest;
+}
+
+char *strcat(char *dest, const char *src)
+{
+	strcpy(dest + strlen(dest), src);
+	return dest;
+}
+
+char *strncpy(char *dest, const char *src, int n)
+{
+	char *dptr = dest;
+	while(n-- > 0 && (*dptr++ = *src++));
+	return dest;
+}
diff --git a/src/libc/string.h b/src/libc/string.h
new file mode 100644
index 0000000..7ccb18e
--- /dev/null
+++ b/src/libc/string.h
@@ -0,0 +1,32 @@
+#ifndef STRING_H_
+#define STRING_H_
+
+#include <stdlib.h>
+
+void *memset(void *s, int c, size_t n);
+
+void *memcpy(void *dest, const void *src, size_t n);
+void *memmove(void *dest, const void *src, size_t n);
+
+int memcmp(void *aptr, void *bptr, size_t n);
+
+size_t strlen(const char *s);
+
+char *strchr(const char *s, int c);
+char *strrchr(const char *s, int c);
+
+char *strstr(const char *str, const char *substr);
+char *strcasestr(const char *str, const char *substr);
+
+int strcmp(const char *s1, const char *s2);
+int strcasecmp(const char *s1, const char *s2);
+
+int strncmp(const char *s1, const char *s2, int n);
+int strncasecmp(const char *s1, const char *s2, int n);
+
+char *strcpy(char *dest, const char *src);
+char *strcat(char *dest, const char *src);
+
+char *strncpy(char *dest, const char *src, int n);
+
+#endif	/* STRING_H_ */
diff --git a/src/main.c b/src/main.c
index 9816bda..66efdda 100644
--- a/src/main.c
+++ b/src/main.c
@@ -1,12 +1,17 @@
 #include "z80.h"
 #include "vdp.h"
+#include "debug.h"
 
 int main(void)
 {
 	z80_init();
 	vdp_init();
+	dbg_init();
 
-	vdp_setcolor(0, 0, 14, 0, 0);
+	vdp_setcolor(0, 0, 2, 2, 2);
+	vdp_setcolor(0, 15, 15, 15, 15);
+
+	dbg_printstr(0, 0, "Mindlapse");
 
 	return 0;
 }
diff --git a/src/vdp.S b/src/vdp.S
index 0baa4d4..b3c6553 100644
--- a/src/vdp.S
+++ b/src/vdp.S
@@ -5,8 +5,9 @@
 
 	.globl vdp_init
 vdp_init:
+	| initialize registers
 	move.l #def_reg_tab, %a0
-	move.w #0, %d1
+	clr.w %d1
 0:	move.w %d1, %d0
 	lsl.w #8, %d0
 	or.w #0x8000, %d0
@@ -15,8 +16,19 @@ vdp_init:
 	add.w #1, %d1
 	cmp.w def_reg_tab_size, %d1
 	bne.s 0b
+
+	| clear VRAM
+	clr.l %d0
+	move.l #VDP_VRAM, %d1
+	bsr setup_addr
+	clr.w %d0
+	move.w #0xffff, %d1
+0:	move.w %d0, VDP_DATA_PORT
+	dbra.w %d1, 0b
+	
 	rts
 
+
 	| address in d0, type in d1
 setup_addr:
 	lsl.l #2, %d0
@@ -29,8 +41,9 @@ setup_addr:
 	.globl vdp_setcolor
 vdp_setcolor:
 	move.l 4(%sp), %d0	| palette number
-	lsl.l #5, %d0
+	lsl.l #4, %d0
 	add.l 8(%sp), %d0	| add index
+	lsl.l #1, %d0
 	move.l #VDP_CRAM, %d1
 	bsr setup_addr
 	move.w 22(%sp), %d0	| blue
@@ -42,12 +55,12 @@ vdp_setcolor:
 	move.w %d0, VDP_DATA_PORT
 	rts
 
-	.data
+	.section .rodata
 def_reg_tab:
 	.byte VDP_M1_INIT			| 0: mode 1
 	.byte VDP_M2_INIT + VDP_M2_DISP		| 1: mode 2
 	.byte VDP_NA_ADDR(0xc000)		| 2: scroll A nametable addr.
-	.byte 0					| 3: window nametable addr.
+	.byte VDP_NW_ADDR(VDP_ADDR_INVAL)	| 3: window nametable addr.
 	.byte VDP_NB_ADDR(0xd000)		| 4: scroll B nametable addr.
 	.byte VDP_SPRTAB_ADDR(0xe000)		| 5: sprite table addr.
 	.byte 0
diff --git a/src/vdp.h b/src/vdp.h
index 74199a1..82e6747 100644
--- a/src/vdp.h
+++ b/src/vdp.h
@@ -3,16 +3,20 @@
 
 #include "hwregs.h"
 
-#define VDP_VRAM	0x40000000
-#define VDP_CRAM	0xc0000000
-#define VDP_VSRAM	0x40000010
-
 #define vdp_setup_addr(type, addr) \
 	(VDP_CTL32 = ((type) | (((addr) & 0x3fff) << 16) | (((addr) >> 14) & 3)))
 
 #define vdp_setreg(reg, val) \
 	(VDP_CTL = 0x8000 | ((reg) << 8) | (val))
 
+#define VDP_TILE_BG			0
+#define VDP_TILE_FG			0x8000
+#define VDP_TILE_PAL(x)		((x) << 13)
+#define VDP_TILE_VFLIP		0x1000
+#define VDP_TILE_HFLIP		0x0800
+#define VDP_TILENAME(tile, pal, flags)	\
+	((tile) | VDP_TILE_PAL(pal) | (flags))
+
 void vdp_init(void);
 void vdp_setcolor(int pal, int cidx, int r, int g, int b);
 
diff --git a/tools/pngdump/Makefile b/tools/pngdump/Makefile
new file mode 100644
index 0000000..96eaa49
--- /dev/null
+++ b/tools/pngdump/Makefile
@@ -0,0 +1,10 @@
+CFLAGS = -pedantic -Wall -Wno-unused-function -g
+LDFLAGS = -lpng -lz -lm
+
+pngdump: main.o image.o quant.o tiles.o
+	$(CC) -o $@ $^ $(LDFLAGS)
+
+clean:
+	$(RM) main.o
+	$(RM) image.o
+	$(RM) pngdump
diff --git a/tools/pngdump/image.c b/tools/pngdump/image.c
new file mode 100644
index 0000000..7094888
--- /dev/null
+++ b/tools/pngdump/image.c
@@ -0,0 +1,676 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <assert.h>
+#include <png.h>
+#include "image.h"
+
+int alloc_image(struct image *img, int x, int y, int bpp)
+{
+	memset(img, 0, sizeof *img);
+	img->width = x;
+	img->height = y;
+	img->bpp = bpp;
+	img->scansz = img->pitch = x * (bpp == 15 ? 16 : bpp) / 8;
+
+	if(!(img->pixels = malloc(y * img->scansz))) {
+		fprintf(stderr, "failed to allocate %dx%d (%dbpp) pixel buffer\n", x, y, bpp);
+		return -1;
+	}
+
+	/* just a guess, assume the user will fill the details, but set up reasonable
+	 * defaults just in case...
+	 */
+	if(bpp <= 8) {
+		img->nchan = 1;
+		img->cmap_ncolors = 1 << bpp;
+	} else if(bpp <= 24) {
+		img->nchan = 3;
+	} else {
+		img->nchan = 4;
+	}
+	return 0;
+}
+
+int load_image(struct image *img, const char *fname)
+{
+	int i;
+	FILE *fp;
+	png_struct *png;
+	png_info *info;
+	int chan_bits, color_type;
+	png_uint_32 xsz, ysz;
+	png_color *palette;
+	unsigned char **scanline;
+	unsigned char *dptr;
+
+	if(!(fp = fopen(fname, "rb"))) {
+		fprintf(stderr, "failed to open: %s: %s\n", fname, strerror(errno));
+		return -1;
+	}
+
+	if(!(png = png_create_read_struct(PNG_LIBPNG_VER_STRING, 0, 0, 0))) {
+		fclose(fp);
+		return -1;
+	}
+	if(!(info = png_create_info_struct(png))) {
+		fclose(fp);
+		png_destroy_read_struct(&png, 0, 0);
+		return -1;
+	}
+	if(setjmp(png_jmpbuf(png))) {
+		fclose(fp);
+		png_destroy_read_struct(&png, &info, 0);
+		return -1;
+	}
+
+	png_init_io(png, fp);
+	png_read_png(png, info, 0, 0);
+
+	png_get_IHDR(png, info, &xsz, &ysz, &chan_bits, &color_type, 0, 0, 0);
+	img->width = xsz;
+	img->height = ysz;
+	img->nchan = png_get_channels(png, info);
+	img->bpp = img->nchan * chan_bits;
+	img->scansz = img->pitch = xsz * img->bpp / 8;
+	img->cmap_ncolors = 0;
+
+	if(color_type == PNG_COLOR_TYPE_PALETTE) {
+		png_get_PLTE(png, info, &palette, &img->cmap_ncolors);
+		memcpy(img->cmap, palette, img->cmap_ncolors * sizeof *img->cmap);
+	}
+
+	if(!(img->pixels = malloc(ysz * img->scansz))) {
+		perror("failed to allocate pixel buffer");
+		fclose(fp);
+		png_destroy_read_struct(&png, &info, 0);
+		return -1;
+	}
+	dptr = img->pixels;
+
+	scanline = (unsigned char**)png_get_rows(png, info);
+	for(i=0; i<ysz; i++) {
+		memcpy(dptr, scanline[i], img->scansz);
+		dptr += img->pitch;
+	}
+
+	fclose(fp);
+	png_destroy_read_struct(&png, &info, 0);
+	return 0;
+}
+
+int save_image(struct image *img, const char *fname)
+{
+	FILE *fp;
+	int res;
+
+	if(!(fp = fopen(fname, "wb"))) {
+		fprintf(stderr, "save_image: failed to open: %s: %s\n", fname, strerror(errno));
+		return -1;
+	}
+	res = save_image_file(img, fp);
+	fclose(fp);
+	return res;
+}
+
+int save_image_file(struct image *img, FILE *fp)
+{
+	int i, chan_bits, coltype;
+	png_struct *png;
+	png_info *info;
+	png_text txt;
+	unsigned char **scanline = 0;
+	unsigned char *pptr;
+
+	if(!(png = png_create_write_struct(PNG_LIBPNG_VER_STRING, 0, 0, 0))) {
+		fclose(fp);
+		return -1;
+	}
+	if(!(info = png_create_info_struct(png))) {
+		png_destroy_write_struct(&png, 0);
+		fclose(fp);
+		return -1;
+	}
+
+	txt.compression = PNG_TEXT_COMPRESSION_NONE;
+	txt.key = "Software";
+	txt.text = "pngdump";
+	txt.text_length = 0;
+
+	if(setjmp(png_jmpbuf(png))) {
+		png_destroy_write_struct(&png, &info);
+		free(scanline);
+		fclose(fp);
+		return -1;
+	}
+
+	switch(img->nchan) {
+	case 1:
+		if(img->cmap_ncolors > 0) {
+			coltype = PNG_COLOR_TYPE_PALETTE;
+		} else {
+			coltype = PNG_COLOR_TYPE_GRAY;
+		}
+		break;
+	case 2:
+		coltype = PNG_COLOR_TYPE_GRAY_ALPHA;
+		break;
+	case 3:
+		coltype = PNG_COLOR_TYPE_RGB;
+		break;
+	case 4:
+		coltype = PNG_COLOR_TYPE_RGB_ALPHA;
+		break;
+	}
+
+	chan_bits = img->bpp / img->nchan;
+	png_set_IHDR(png, info, img->width, img->height, chan_bits, coltype, PNG_INTERLACE_NONE,
+			PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
+	png_set_text(png, info, &txt, 1);
+
+	if(img->cmap_ncolors > 0) {
+		png_set_PLTE(png, info, (png_color*)img->cmap, img->cmap_ncolors);
+	}
+
+	if(!(scanline = malloc(img->height * sizeof *scanline))) {
+		png_destroy_write_struct(&png, &info);
+		fclose(fp);
+		return -1;
+	}
+
+	pptr = img->pixels;
+	for(i=0; i<img->height; i++) {
+		scanline[i] = pptr;
+		pptr += img->pitch;
+	}
+	png_set_rows(png, info, scanline);
+
+	png_init_io(png, fp);
+	png_write_png(png, info, 0, 0);
+	png_destroy_write_struct(&png, &info);
+	free(scanline);
+	return 0;
+}
+
+
+int cmp_image(struct image *a, struct image *b)
+{
+	int i;
+	unsigned char *aptr = a->pixels;
+	unsigned char *bptr = b->pixels;
+
+	if(a->width != b->width || a->height != b->height || a->bpp != b->bpp || a->nchan != b->nchan) {
+		return -1;
+	}
+
+	for(i=0; i<a->height; i++) {
+		if(memcmp(aptr, bptr, a->scansz) != 0) {
+			return -1;
+		}
+		aptr += a->pitch;
+		bptr += b->pitch;
+	}
+	return 0;
+}
+
+void blit(struct image *src, int sx, int sy, int w, int h, struct image *dst, int dx, int dy)
+{
+	int i;
+	unsigned char *sptr, *dptr;
+
+	assert(src->bpp == dst->bpp);
+	assert(src->nchan == dst->nchan);
+
+	if(sx < 0) { w += sx; sx = 0; }
+	if(sy < 0) { h += sy; sy = 0; }
+	if(dx < 0) { w += dx; sx -= dx; dx = 0; }
+	if(dy < 0) { h += dy; sy -= dy; dy = 0; }
+	if(sx + w >= src->width) w = src->width - sx;
+	if(sy + h >= src->height) h = src->height - sy;
+	if(dx + w >= dst->width) w = dst->width - dx;
+	if(dy + h >= dst->height) h = dst->height - dy;
+
+	if(w <= 0 || h <= 0) return;
+
+	sptr = src->pixels + sy * src->pitch + sx * src->bpp / 8;
+	dptr = dst->pixels + dy * dst->pitch + dx * dst->bpp / 8;
+
+	for(i=0; i<h; i++) {
+		memcpy(dptr, sptr, w * dst->bpp / 8);
+		dptr += dst->pitch;
+		sptr += src->pitch;
+	}
+}
+
+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:
+		pptr = img->pixels + y * img->pitch + x / 2;
+		return x & 1 ? *pptr & 0xf : *pptr >> 4;
+	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);
+	}
+
+	return 0;
+}
+
+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;
+
+	switch(img->bpp) {
+	case 4:
+		pptr = img->pixels + y * img->pitch + x / 2;
+		if(x & 1) {
+			*pptr = (*pptr & 0xf0) | pix;
+		} else {
+			*pptr = (*pptr & 0xf) | (pix << 4);
+		}
+		break;
+
+	case 8:
+		pptr = img->pixels + y * img->pitch + x;
+		*pptr = pix;
+		break;
+
+	case 15:
+	case 16:
+		pptr16 = (unsigned short*)(img->pixels + y * img->pitch + x * 2);
+		*pptr16 = pix;
+		break;
+
+	default:
+		fprintf(stderr, "put_pixel not implemented for %d bpp\n", img->bpp);
+	}
+}
+
+void overlay_key(struct image *src, unsigned int key, struct image *dst)
+{
+	int i, j;
+	unsigned int pix;
+
+	assert(src->bpp == dst->bpp);
+	assert(src->width == dst->width);
+	assert(src->height == dst->height);
+
+	for(i=0; i<dst->height; i++) {
+		for(j=0; j<dst->width; j++) {
+			pix = get_pixel(src, j, i);
+			if(pix != key) {
+				put_pixel(dst, j, i, pix);
+			}
+		}
+	}
+}
+
+#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
new file mode 100644
index 0000000..f86de94
--- /dev/null
+++ b/tools/pngdump/image.h
@@ -0,0 +1,38 @@
+#ifndef IMAGE_H_
+#define IMAGE_H_
+
+#include <stdio.h>
+
+struct cmapent {
+	unsigned char r, g, b;
+};
+
+struct image {
+	int width, height;
+	int bpp;
+	int nchan;
+	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;
+};
+
+int alloc_image(struct image *img, int x, int y, int bpp);
+int load_image(struct image *img, const char *fname);
+int save_image(struct image *img, const char *fname);
+int save_image_file(struct image *img, FILE *fp);
+
+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);
+
+int quantize_image(struct image *img, int maxcol);
+int gen_shades(struct image *img, int levels, int maxcol, int *shade_lut);
+
+#endif	/* IMAGE_H_ */
diff --git a/tools/pngdump/main.c b/tools/pngdump/main.c
new file mode 100644
index 0000000..ae06fac
--- /dev/null
+++ b/tools/pngdump/main.c
@@ -0,0 +1,467 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+#include <errno.h>
+#include <assert.h>
+#include "image.h"
+#include "tiles.h"
+
+enum {
+	MODE_PIXELS,
+	MODE_CMAP,
+	MODE_PNG,
+	MODE_INFO
+};
+
+void conv_gba_image(struct image *img);
+void dump_colormap(struct image *img, int text, FILE *fp);
+void print_usage(const char *argv0);
+
+int main(int argc, char **argv)
+{
+	int i, j, mode = 0;
+	int text = 0;
+	int renibble = 0;
+	char *outfname = 0;
+	char *slut_fname = 0, *cmap_fname = 0, *tmap_fname = 0;
+	char *infiles[256];
+	int num_infiles = 0;
+	struct image img, tmpimg;
+	FILE *out = stdout;
+	FILE *aux_out;
+	int *shade_lut = 0;
+	int *lutptr;
+	int shade_levels = 8;
+	int maxcol = 0;
+	int lvl;
+	int conv_555 = 0;
+	int gbacolors = 0;
+	int tile_width = 0, tile_height = 0;
+	int tile_dedup = 0;
+	struct tilemap tmap;
+
+	for(i=1; i<argc; i++) {
+		if(argv[i][0] == '-') {
+			if(argv[i][2] == 0) {
+				switch(argv[i][1]) {
+				case 'P':
+					mode = MODE_PNG;
+					break;
+
+				case 'p':
+					mode = MODE_PIXELS;
+					break;
+
+				case 'c':
+					mode = MODE_CMAP;
+					break;
+
+				case 'i':
+					mode = MODE_INFO;
+					break;
+
+				case 'C':
+					if(!argv[++i] || (maxcol = atoi(argv[i])) < 2 || maxcol > 256) {
+						fprintf(stderr, "-C must be followed by the number of colors to reduce down to\n");
+						return 1;
+					}
+					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':
+					text = 1;
+					break;
+
+				case 'n':
+					renibble = 1;
+					break;
+
+				case 'g':
+					gbacolors = 1;
+					break;
+
+				case 'T':
+					if(!argv[++i] || sscanf(argv[i], "%dx%d", &tile_width, &tile_height) != 2 ||
+							tile_width <= 1 || tile_height <= 1) {
+						fprintf(stderr, "-T must be followed by tile widthxheight 2x2 or higher\n");
+						return 1;
+					}
+					break;
+
+				case 'D':
+					tile_dedup = 1;
+					break;
+
+				case 'o':
+					if(!argv[++i]) {
+						fprintf(stderr, "%s must be followed by a filename\n", argv[i - 1]);
+						return 1;
+					}
+					outfname = argv[i];
+					break;
+
+				case 'h':
+					print_usage(argv[0]);
+					return 0;
+
+				default:
+					fprintf(stderr, "invalid option: %s\n", argv[i]);
+					print_usage(argv[0]);
+					return 1;
+				}
+			} else {
+				if(strcmp(argv[i], "-oc") == 0) {
+					if(!argv[++i]) {
+						fprintf(stderr, "-oc must be followed by a filename\n");
+						return 1;
+					}
+					cmap_fname = argv[i];
+
+				} else if(strcmp(argv[i], "-os") == 0) {
+					if(!argv[++i]) {
+						fprintf(stderr, "-os must be followed by a filename\n");
+						return 1;
+					}
+					slut_fname = argv[i];
+
+				} else if(strcmp(argv[i], "-om") == 0) {
+					if(!argv[++i]) {
+						fprintf(stderr, "-om must be followed by a filename\n");
+						return 1;
+					}
+					tmap_fname = argv[i];
+
+				} else if(strcmp(argv[i], "-555") == 0) {
+					conv_555 = 1;
+
+				} else {
+					fprintf(stderr, "invalid option: %s\n", argv[i]);
+					print_usage(argv[0]);
+					return 1;
+				}
+			}
+		} else {
+			infiles[num_infiles++] = argv[i];
+		}
+	}
+
+	if(!num_infiles) {
+		fprintf(stderr, "pass the filename of a PNG file\n");
+		return 1;
+	}
+	if(load_image(&img, infiles[0]) == -1) {
+		fprintf(stderr, "failed to load PNG file: %s\n", infiles[0]);
+		return 1;
+	}
+
+	if(gbacolors) {
+		conv_gba_image(&img);
+	}
+
+	for(i=1; i<num_infiles; i++) {
+		if(load_image(&tmpimg, infiles[i]) == -1) {
+			fprintf(stderr, "failed to load PNG file: %s\n", infiles[i]);
+			return 1;
+		}
+		if(tmpimg.width != img.width || tmpimg.height != img.height) {
+			fprintf(stderr, "size mismatch: first image (%s) is %dx%d, %s is %dx%d\n",
+					infiles[0], img.width, img.height, infiles[i], tmpimg.width, tmpimg.height);
+			return 1;
+		}
+		if(tmpimg.bpp != img.bpp) {
+			fprintf(stderr, "bpp mismatch: first image (%s) is %d bpp, %s is %d bpp\n",
+					infiles[0], img.bpp, infiles[i], img.bpp);
+			return 1;
+		}
+
+		overlay_key(&tmpimg, 0, &img);
+	}
+
+	/* generate shading LUT and quantize image as necessary */
+	if(slut_fname) {
+		if(img.bpp > 8) {
+			fprintf(stderr, "shading LUT generation is only supported for indexed color images\n");
+			return 1;
+		}
+		if(!(aux_out = fopen(slut_fname, "wb"))) {
+			fprintf(stderr, "failed to open shading LUT output file: %s: %s\n", slut_fname, strerror(errno));
+			return 1;
+		}
+
+		if(!maxcol) maxcol = 256;
+
+		if(!(shade_lut = malloc(maxcol * shade_levels * sizeof *shade_lut))) {
+			fprintf(stderr, "failed to allocate shading look-up table\n");
+			return 1;
+		}
+
+		gen_shades(&img, shade_levels, maxcol, shade_lut);
+
+		lutptr = shade_lut;
+		for(i=0; i<maxcol; i++) {
+			for(j=0; j<shade_levels; j++) {
+				lvl = lutptr[shade_levels - j - 1];
+				if(text) {
+					fprintf(aux_out, "%d%c", lvl, j < shade_levels - 1 ? ' ' : '\n');
+				} else {
+					fputc(lvl, aux_out);
+				}
+			}
+			lutptr += shade_levels;
+		}
+		fclose(aux_out);
+
+	} else if(maxcol) {
+		/* perform any color reductions if requested */
+		if(img.bpp <= 8 && img.cmap_ncolors <= maxcol) {
+			fprintf(stderr, "requested reduction to %d colors, but image has %d colors\n", maxcol, img.cmap_ncolors);
+			return 1;
+		}
+		quantize_image(&img, maxcol);
+	}
+
+	if(cmap_fname) {
+		if(img.bpp > 8) {
+			fprintf(stderr, "colormap output works only for indexed color images\n");
+			return 1;
+		}
+		if(!(aux_out = fopen(cmap_fname, "wb"))) {
+			fprintf(stderr, "failed to open colormap output file: %s: %s\n", cmap_fname, strerror(errno));
+			return 1;
+		}
+		dump_colormap(&img, text, aux_out);
+		fclose(aux_out);
+	}
+
+	if(img.bpp == 4 && renibble) {
+		unsigned char *ptr = img.pixels;
+		for(i=0; i<img.width * img.height; i++) {
+			unsigned char p = *ptr;
+			*ptr++ = (p << 4) | (p >> 4);
+		}
+	}
+
+	if(img.bpp == 16 && conv_555) {
+		struct image img555;
+		unsigned int rgb24[3], rgb15;
+
+		if(alloc_image(&img555, img.width, img.height, 15) == -1) {
+			fprintf(stderr, "failed to allocate temporary %dx%d image for 555 conversion\n",
+					img.width, img.height);
+			return 1;
+		}
+
+		for(i=0; i<img.height; i++) {
+			for(j=0; j<img.width; j++) {
+				get_pixel_rgb(&img, j, i, rgb24);
+				rgb15 = ((rgb24[0] >> 3) & 0x1f) | ((rgb24[1] << 2) & 0x3e0) |
+					((rgb24[2] << 7) & 0x7c00);
+				put_pixel(&img555, j, i, rgb15);
+			}
+		}
+		free(img.pixels);
+		img = img555;
+	}
+
+	if(tile_width > 0) {
+		if(img2tiles(tmap_fname ? &tmap : 0, &img, tile_width, tile_height, tile_dedup) == -1) {
+			return 1;
+		}
+
+		if(tmap_fname) {
+			dump_tilemap(&tmap, tmap_fname);
+		}
+	}
+
+	if(outfname) {
+		if(!(out = fopen(outfname, "wb"))) {
+			fprintf(stderr, "failed to open output file: %s: %s\n", outfname, strerror(errno));
+			return 1;
+		}
+	}
+
+	switch(mode) {
+	case MODE_PNG:
+		save_image_file(&img, out);
+		break;
+
+	case MODE_PIXELS:
+		fwrite(img.pixels, 1, img.scansz * img.height, out);
+		break;
+
+	case MODE_CMAP:
+		dump_colormap(&img, text, out);
+		break;
+
+	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);
+		if(img.cmap_ncolors > 0) {
+			printf("colormap entries: %d\n", img.cmap_ncolors);
+		} else {
+			printf("color channels: %d\n", img.nchan);
+		}
+		break;
+	}
+
+	fclose(out);
+	return 0;
+}
+
+#define MIN(a, b)			((a) < (b) ? (a) : (b))
+#define MIN3(a, b, c)		((a) < (b) ? MIN(a, c) : MIN(b, c))
+#define MAX(a, b)			((a) > (b) ? (a) : (b))
+#define MAX3(a, b, c)		((a) > (b) ? MAX(a, c) : MAX(b, c))
+
+void rgb_to_hsv(float *rgb, float *hsv)
+{
+	float min, max, delta;
+
+	min = MIN3(rgb[0], rgb[1], rgb[2]);
+	max = MAX3(rgb[0], rgb[1], rgb[2]);
+	delta = max - min;
+
+	if(max == 0) {
+		hsv[0] = hsv[1] = hsv[2] = 0;
+		return;
+	}
+
+	hsv[2] = max;			/* value */
+	hsv[1] = delta / max;	/* saturation */
+
+	if(delta == 0.0f) {
+		hsv[0] = 0.0f;
+	} else if(max == rgb[0]) {
+		hsv[0] = (rgb[1] - rgb[2]) / delta;
+	} else if(max == rgb[1]) {
+		hsv[0] = 2.0f + (rgb[2] - rgb[0]) / delta;
+	} else {
+		hsv[0] = 4.0f + (rgb[0] - rgb[1]) / delta;
+	}
+	/*
+	hsv[0] /= 6.0f;
+
+	if(hsv[0] < 0.0f) hsv[0] += 1.0f;
+	*/
+	hsv[0] *= 60.0f;
+	if(hsv[0] < 0) hsv[0] += 360;
+	hsv[0] /= 360.0f;
+}
+
+#define RETRGB(r, g, b) \
+	do { \
+		rgb[0] = r; \
+		rgb[1] = g; \
+		rgb[2] = b; \
+		return; \
+	} while(0)
+
+void hsv_to_rgb(float *hsv, float *rgb)
+{
+	float sec, frac, o, p, q;
+	int hidx;
+
+	if(hsv[1] == 0.0f) {
+		rgb[0] = rgb[1] = rgb[2] = hsv[2];	/* value */
+	}
+
+	sec = floor(hsv[0] * (360.0f / 60.0f));
+	frac = (hsv[0] * (360.0f / 60.0f)) - sec;
+
+	o = hsv[2] * (1.0f - hsv[1]);
+	p = hsv[2] * (1.0f - hsv[1] * frac);
+	q = hsv[2] * (1.0f - hsv[1] * (1.0f - frac));
+
+	hidx = (int)sec;
+	switch(hidx) {
+	default:
+	case 0: RETRGB(hsv[2], q, o);
+	case 1: RETRGB(p, hsv[2], o);
+	case 2: RETRGB(o, hsv[2], q);
+	case 3: RETRGB(o, p, hsv[2]);
+	case 4: RETRGB(q, o, hsv[2]);
+	case 5: RETRGB(hsv[2], o, p);
+	}
+}
+
+void gba_color(struct cmapent *color)
+{
+	float rgb[3], hsv[3];
+
+	rgb[0] = pow((float)color->r / 255.0f, 2.2);
+	rgb[1] = pow((float)color->g / 255.0f, 2.2);
+	rgb[2] = pow((float)color->b / 255.0f, 2.2);
+
+	/* saturate colors */
+	rgb_to_hsv(rgb, hsv);
+	hsv[1] *= 1.2f;
+	hsv[2] *= 2.0f;
+	if(hsv[1] > 1.0f) hsv[1] = 1.0f;
+	if(hsv[2] > 1.0f) hsv[2] = 1.0f;
+	hsv_to_rgb(hsv, rgb);
+
+	rgb[0] = pow(rgb[0], 1.0 / 2.6);
+	rgb[1] = pow(rgb[1], 1.0 / 2.6);
+	rgb[2] = pow(rgb[2], 1.0 / 2.6);
+
+	color->r = (int)(rgb[0] * 255.0f);
+	color->g = (int)(rgb[1] * 255.0f);
+	color->b = (int)(rgb[2] * 255.0f);
+}
+
+void conv_gba_image(struct image *img)
+{
+	int i;
+
+	if(img->cmap_ncolors) {
+		for(i=0; i<img->cmap_ncolors; i++) {
+			gba_color(img->cmap + i);
+		}
+	} else {
+		/* TODO */
+	}
+}
+
+void dump_colormap(struct image *img, int text, FILE *fp)
+{
+	int i;
+
+	if(text) {
+		for(i=0; i<img->cmap_ncolors; i++) {
+			fprintf(fp, "%d %d %d\n", img->cmap[i].r, img->cmap[i].g, img->cmap[i].b);
+		}
+	} else {
+		fwrite(img->cmap, sizeof img->cmap[0], 1 << img->bpp, fp);
+	}
+}
+
+void print_usage(const char *argv0)
+{
+	printf("Usage: %s [options] <input file>\n", argv0);
+	printf("Options:\n");
+	printf(" -o <output file>: specify output file (default: stdout)\n");
+	printf(" -oc <cmap file>: output colormap to separate file\n");
+	printf(" -os <lut file>: generate and output shading LUT\n");
+	printf(" -p: dump pixels (default)\n");
+	printf(" -P: output in PNG format\n");
+	printf(" -c: dump colormap (palette) entries\n");
+	printf(" -C <colors>: reduce image down to specified number of colors\n");
+	printf(" -s <shade levels>: used in conjunction with -os (default: 8)\n");
+	printf(" -i: print image information\n");
+	printf(" -t: output as text when possible\n");
+	printf(" -n: swap the order of nibbles (for 4bpp)\n");
+	printf(" -555: convert to BGR555\n");
+	printf(" -g: GBA colors (optimize colors for the GBA display)\n");
+	printf(" -T <WxH>: reorder as a series of tiles of the requested size\n");
+	printf(" -D: deduplicate tiles\n");
+	printf(" -om <tilemap file>: output tilemap recreating the image from dedup-ed tiles\n");
+	printf(" -h: print usage and exit\n");
+}
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);
+	}
+}
+
diff --git a/tools/pngdump/tiles.c b/tools/pngdump/tiles.c
new file mode 100644
index 0000000..bcf27e6
--- /dev/null
+++ b/tools/pngdump/tiles.c
@@ -0,0 +1,61 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "tiles.h"
+#include "image.h"
+
+int img2tiles(struct tilemap *tmap, struct image *img, int tw, int th, int dedup)
+{
+	int i, j, x, y, tx, ty, tileoffs, xtiles, ytiles, ntiles;
+	struct image orig;
+	unsigned int pix;
+
+	if(alloc_image(&orig, img->width, img->height, img->bpp) == -1) {
+		fprintf(stderr, "img2tiles: failed to allocate temporary image\n");
+		return -1;
+	}
+	memcpy(orig.pixels, img->pixels, img->scansz * img->height);
+
+	xtiles = (img->width + tw - 1) / tw;
+	ytiles = (img->height + th - 1) / th;
+	ntiles = xtiles * ytiles;
+
+	img->width = tw;
+	img->height = ntiles * th;
+	img->pitch = img->scansz = tw * img->bpp / 8;
+
+	if(tmap) {
+		tmap->width = xtiles;
+		tmap->height = ytiles;
+		if(!(tmap->map = malloc(ntiles * sizeof *tmap->map))) {
+			fprintf(stderr, "failed to allocate tilemap\n");
+			free(orig.pixels);
+			return -1;
+		}
+	}
+
+	tileoffs = 0;
+	y = 0;
+	for(i=0; i<ytiles; i++) {
+		x = 0;
+		for(j=0; j<xtiles; j++) {
+			for(ty=0; ty<th; ty++) {
+				for(tx=0; tx<tw; tx++) {
+					pix = get_pixel(&orig, x + tx, y + ty);
+					put_pixel(img, tx, ty + tileoffs, pix);
+				}
+			}
+			tileoffs += th;	/* destination Y offset, inc by th for every tile */
+			x += tw;
+		}
+		y += th;
+	}
+
+	free(orig.pixels);
+	return 0;
+}
+
+int dump_tilemap(struct tilemap *tmap, const char *fname)
+{
+	return -1;
+}
diff --git a/tools/pngdump/tiles.h b/tools/pngdump/tiles.h
new file mode 100644
index 0000000..5c049a8
--- /dev/null
+++ b/tools/pngdump/tiles.h
@@ -0,0 +1,14 @@
+#ifndef TILES_H_
+#define TILES_H_
+
+#include "image.h"
+
+struct tilemap {
+	int width, height;
+	int *map;
+};
+
+int img2tiles(struct tilemap *tmap, struct image *img, int tw, int th, int dedup);
+int dump_tilemap(struct tilemap *tmap, const char *fname);
+
+#endif	/* TILES_H_ */
-- 
1.7.10.4