Merge branch 'master' into tools-makefile-integration

6 files changed, 444 insertions, 3 deletions

diff --git a/tools/Makefile b/tools/Makefile
index 66e9be8a5..752658b06 100644
--- a/tools/Makefile
+++ b/tools/Makefile
@@ -1,13 +1,16 @@
 .PHONY: all clean
 
+CFLAGS := -std=c99
+
 tools := \
 	lzcomp \
 	png_dimensions \
 	scan_includes \
 	palette \
 	pokemon_animation \
-	pokemon_animation_graphics
-
+	pokemon_animation_graphics \
+	gfx \
+	md5
 all: $(tools)
 	@:
 
@@ -15,4 +18,4 @@ clean:
 	rm -f $(tools)
 
 %: %.c
-	$(CC) -o $@ $<
+	$(CC) $(CFLAGS) -o $@ $<
diff --git a/tools/common.h b/tools/common.h
new file mode 100644
index 000000000..bc877ccb9
--- /dev/null
+++ b/tools/common.h
@@ -0,0 +1,37 @@
+#ifndef GUARD_COMMON_H
+#define GUARD_COMMON_H
+
+int __getopt_long_i__;
+#define getopt_long(c, v, s, l) getopt_long(c, v, s, l, &__getopt_long_i__)
+
+FILE *fopen_verbose(char *filename, char *mode) {
+	FILE *f = fopen(filename, mode);
+	if (!f) {
+		fprintf(stderr, "Could not open file: \"%s\"\n", filename);
+	}
+	return f;
+}
+
+uint8_t *read_u8(char *filename, int *size) {
+	FILE *f = fopen_verbose(filename, "rb");
+	if (!f) {
+		exit(1);
+	}
+	fseek(f, 0, SEEK_END);
+	*size = ftell(f);
+	rewind(f);
+	uint8_t *data = malloc(*size);
+	fread(data, 1, *size, f);
+	fclose(f);
+	return data;
+}
+
+void write_u8(char *filename, uint8_t *data, int size) {
+	FILE *f = fopen_verbose(filename, "wb");
+	if (f) {
+		fwrite(data, 1, size, f);
+		fclose(f);
+	}
+}
+
+#endif // GUARD_COMMON_H
diff --git a/tools/gfx.c b/tools/gfx.c
new file mode 100644
index 000000000..207dcb6c2
--- /dev/null
+++ b/tools/gfx.c
@@ -0,0 +1,271 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <getopt.h>
+#include <string.h>
+#include <stdint.h>
+
+#include "common.h"
+
+static void usage(void) {
+	fprintf(stderr, "Usage: gfx [--trim-whitespace] [--remove-whitespace] [--interleave] [--remove-duplicates [--keep-whitespace]] [--remove-xflip] [--remove-yflip] [-w width] [-d depth] [-h] [-o outfile] infile\n");
+}
+
+static void error(char *message) {
+	fputs(message, stderr);
+	fputs("\n", stderr);
+}
+
+struct Options {
+	int trim_whitespace;
+	int remove_whitespace;
+	int help;
+	char *outfile;
+	int depth;
+	int interleave;
+	int width;
+	int remove_duplicates;
+	int keep_whitespace;
+	int remove_xflip;
+	int remove_yflip;
+};
+
+struct Options Options = {
+	.depth = 2,
+};
+
+void get_args(int argc, char *argv[]) {
+	struct option long_options[] = {
+		{"remove-whitespace", no_argument, &Options.remove_whitespace, 1},
+		{"trim-whitespace", no_argument, &Options.trim_whitespace, 1},
+		{"interleave", no_argument, &Options.interleave, 1},
+		{"remove-duplicates", no_argument, &Options.remove_duplicates, 1},
+		{"keep-whitespace", no_argument, &Options.keep_whitespace, 1},
+		{"remove-xflip", no_argument, &Options.remove_xflip, 1},
+		{"remove-yflip", no_argument, &Options.remove_yflip, 1},
+		{"width", required_argument, 0, 'w'},
+		{"depth", required_argument, 0, 'd'},
+		{"help", no_argument, 0, 'h'},
+		{0}
+	};
+	for (int opt = 0; opt != -1;) {
+		switch (opt = getopt_long(argc, argv, "ho:d:", long_options)) {
+		case 'h':
+			Options.help = true;
+			break;
+		case 'o':
+			Options.outfile = optarg;
+			break;
+		case 'd':
+			Options.depth = strtoul(optarg, NULL, 0);
+			break;
+		case 'w':
+			Options.width = strtoul(optarg, NULL, 0);
+			break;
+		case 0:
+		case -1:
+			break;
+		default:
+			usage();
+			exit(1);
+			break;
+		}
+	}
+}
+
+struct Graphic {
+	int size;
+	uint8_t *data;
+};
+
+bool is_whitespace(uint8_t *tile, int tile_size) {
+	uint8_t WHITESPACE = 0;
+	for (int i = 0; i < tile_size; i++) {
+		if (tile[i] != WHITESPACE) {
+			return false;
+		}
+	}
+	return true;
+}
+
+void trim_whitespace(struct Graphic *graphic) {
+	int tile_size = Options.depth * 8;
+	for (int i = graphic->size - tile_size; i > 0; i -= tile_size) {
+		if (is_whitespace(&graphic->data[i], tile_size)) {
+			graphic->size = i;
+		} else {
+			break;
+		}
+	}
+}
+
+void remove_whitespace(struct Graphic *graphic) {
+	int tile_size = Options.depth * 8;
+	if (Options.interleave) tile_size *= 2;
+	int i = 0;
+	for (int j = 0; i < graphic->size && j < graphic->size; i += tile_size, j += tile_size) {
+		while (is_whitespace(&graphic->data[j], tile_size)) {
+			j += tile_size;
+		}
+		if (j >= graphic->size) {
+			break;
+		}
+		if (j > i) {
+			memcpy(&graphic->data[i], &graphic->data[j], tile_size);
+		}
+	}
+	graphic->size = i;
+}
+
+bool tile_exists(uint8_t *tile, uint8_t *tiles, int tile_size, int num_tiles) {
+	for (int i = 0; i < num_tiles; i++) {
+		bool match = true;
+		for (int j = 0; j < tile_size; j++) {
+			if (tile[j] != tiles[i * tile_size + j]) {
+				match = false;
+			}
+		}
+		if (match) {
+			return true;
+		}
+	}
+	return false;
+}
+
+void remove_duplicates(struct Graphic *graphic) {
+	int tile_size = Options.depth * 8;
+	if (Options.interleave) tile_size *= 2;
+	int num_tiles = 0;
+	for (int i = 0, j = 0; i < graphic->size && j < graphic->size; i += tile_size, j += tile_size) {
+		while (tile_exists(&graphic->data[j], graphic->data, tile_size, num_tiles)) {
+			if (Options.keep_whitespace && is_whitespace(&graphic->data[j], tile_size)) {
+				break;
+			}
+			j += tile_size;
+		}
+		if (j >= graphic->size) {
+			break;
+		}
+		if (j > i) {
+			memcpy(&graphic->data[i], &graphic->data[j], tile_size);
+		}
+		num_tiles++;
+	}
+	graphic->size = num_tiles * tile_size;
+}
+
+bool flip_exists(uint8_t *tile, uint8_t *tiles, int tile_size, int num_tiles, bool xflip, bool yflip) {
+	uint8_t *flip = calloc(tile_size, 1);
+	int half_size = tile_size / 2;
+	for (int i = 0; i < tile_size; i++) {
+		int byte = i;
+		if (yflip) {
+			byte = tile_size - 1 - (i ^ 1);
+			if (Options.interleave && i < half_size) {
+				byte = half_size - 1 - (i ^ 1);
+			}
+		}
+		if (xflip) {
+			for (int bit = 0; bit < 8; bit++) {
+				flip[byte] |= ((tile[i] >> bit) & 1) << (7 - bit);
+			}
+		} else {
+			flip[byte] = tile[i];
+		}
+	}
+	if (tile_exists(flip, tiles, tile_size, num_tiles)) {
+		return true;
+	}
+	return false;
+}
+
+void remove_flip(struct Graphic *graphic, bool xflip, bool yflip) {
+	int tile_size = Options.depth * 8;
+	if (Options.interleave) tile_size *= 2;
+	int num_tiles = 0;
+	for (int i = 0, j = 0; i < graphic->size && j < graphic->size; i += tile_size, j += tile_size) {
+		while (flip_exists(&graphic->data[j], graphic->data, tile_size, num_tiles, xflip, yflip)) {
+			if (Options.keep_whitespace && is_whitespace(&graphic->data[j], tile_size)) {
+				break;
+			}
+			j += tile_size;
+		}
+		if (j >= graphic->size) {
+			break;
+		}
+		if (j > i) {
+			memcpy(&graphic->data[i], &graphic->data[j], tile_size);
+		}
+		num_tiles++;
+	}
+	graphic->size = num_tiles * tile_size;
+}
+
+void interleave(struct Graphic *graphic, int width) {
+	int tile_size = Options.depth * 8;
+	int width_tiles = width / 8;
+	int num_tiles = graphic->size / tile_size;
+	uint8_t *interleaved = malloc(graphic->size);
+	for (int i = 0; i < num_tiles; i++) {
+		int tile = i * 2;
+		int row = i / width_tiles;
+		tile -= width_tiles * row;
+		if (row % 2) {
+			tile -= width_tiles;
+			tile += 1;
+		}
+		memcpy(&interleaved[tile * tile_size], &graphic->data[i * tile_size], tile_size);
+	}
+	graphic->size = num_tiles * tile_size;
+	memcpy(graphic->data, interleaved, graphic->size);
+	free(interleaved);
+}
+
+
+int main(int argc, char *argv[]) {
+	get_args(argc, argv);
+	argc -= optind;
+	argv += optind;
+	if (Options.help) {
+		usage();
+		return 0;
+	}
+	if (argc < 1) {
+		usage();
+		exit(1);
+	}
+	char *infile = argv[0];
+	struct Graphic graphic;
+	graphic.data = read_u8(infile, &graphic.size);
+	if (Options.trim_whitespace) {
+		trim_whitespace(&graphic);
+	}
+	if (Options.interleave) {
+		if (!Options.width) {
+			error("interleave: must set --width to a nonzero value");
+			usage();
+			exit(1);
+		}
+		interleave(&graphic, Options.width);
+	}
+	if (Options.remove_duplicates) {
+		remove_duplicates(&graphic);
+	}
+	if (Options.remove_xflip) {
+		remove_flip(&graphic, true, false);
+	}
+	if (Options.remove_yflip) {
+		remove_flip(&graphic, false, true);
+	}
+	if (Options.remove_xflip && Options.remove_yflip) {
+		remove_flip(&graphic, true, true);
+	}
+	if (Options.remove_whitespace) {
+		remove_whitespace(&graphic);
+	}
+	if (Options.outfile) {
+		write_u8(Options.outfile, graphic.data, graphic.size);
+	}
+	free(graphic.data);
+	return 0;
+}
diff --git a/tools/md5.c b/tools/md5.c
new file mode 100644
index 000000000..e043e8537
--- /dev/null
+++ b/tools/md5.c
@@ -0,0 +1,128 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+
+#include "common.h"
+
+static const int s[64] = {
+	7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,
+	5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,
+	4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,
+	6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,
+};
+
+static const uint32_t K[64] = {
+	0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
+	0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
+	0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
+	0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
+	0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
+	0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
+	0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
+	0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
+	0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
+	0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
+	0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
+	0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
+	0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
+	0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
+	0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
+	0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391,
+};
+
+#define rotate_left_32(value, by) \
+	((((value) << (by)) & 0xffffffff) | ((value) >> 32 - (by)))
+
+void md5_wikipedia(uint8_t *data, int length, uint8_t *result) {
+
+	uint8_t *message = calloc(length + 64, sizeof(uint8_t));
+	memcpy(message, data, length);
+
+	long orig_bitlength = length * 8;
+
+	message[length++] |= 1 << 7;
+
+	while (length % 64 != (64 - 8)) {
+		length++;
+	}
+	for (int i = 0; i < 8; i++) {
+		message[length++] = (orig_bitlength >> (i * 8)) & 0xff;
+	}
+
+	int a0 = 0x67452301;
+	int b0 = 0xefcdab89;
+	int c0 = 0x98badcfe;
+	int d0 = 0x10325476;
+
+	for (int start = 0; start < length; start += 64) {
+		uint32_t M[16];
+		for (int j = 0; j < 16; j++) {
+			uint8_t *word = &message[start + j * 4];
+			M[j] = *word++;
+			M[j] |= *word++ << 8;
+			M[j] |= *word++ << 16;
+			M[j] |= *word++ << 24;
+		}
+
+		int A = a0;
+		int B = b0;
+		int C = c0;
+		int D = d0;
+		for (int i = 0; i < 64; i++) {
+			int F, g;
+			switch (i / 16) {
+			case 0:
+				F = (B & C) | (~B & D);
+				g = i;
+				break;
+			case 1:
+				F = (D & B) | (~D & C);
+				g = (5 * i + 1) % 16;
+				break;
+			case 2:
+				F = B ^ C ^ D;
+				g = (3 * i + 5) % 16;
+				break;
+			case 3:
+				F = C ^ (B | ~D);
+				g = (7 * i) % 16;
+				break;
+			}
+			int e = D;
+			D = C;
+			C = B;
+			B = B + rotate_left_32(A + F + K[i] + M[g], s[i]);
+			A = e;
+		}
+		a0 += A;
+		b0 += B;
+		c0 += C;
+		d0 += D;
+	}
+
+	int values[] = {a0, b0, c0, d0};
+	for (int i = 0; i < 16; i++) {
+		int value = values[i >> 2];
+		int shift = (i % 4) * 8;
+		result[i] = (value >> shift) & 0xff;
+	}
+
+	free(message);
+}
+
+int main(int argc, char *argv[]) {
+	if (argc < 2) {
+		exit(1);
+	}
+	char *infile = argv[1];
+	int size;
+	uint8_t *data = read_u8(infile, &size);
+
+	uint8_t result[16];
+	md5_wikipedia(data, size, result);
+	for (int i = 0; i < 16; i++) {
+		printf("%02x", result[i]);
+	}
+	printf("\n");
+}
diff --git a/tools/palette.c b/tools/palette.c
index c1beb40e4..39837a096 100644
--- a/tools/palette.c
+++ b/tools/palette.c
@@ -3,6 +3,7 @@
 #include <stdint.h>
 #include <stdlib.h>
 #include <stdbool.h>
+#include <getopt.h>
 
 void usage(void) {
 	printf("Usage: palette palfile\n");
diff --git a/tools/pokemon_animation.c b/tools/pokemon_animation.c
index 835160c24..0728788ec 100644
--- a/tools/pokemon_animation.c
+++ b/tools/pokemon_animation.c
@@ -4,6 +4,7 @@
 #include <string.h>
 #include <stdint.h>
 #include <stdbool.h>
+#include <getopt.h>
 
 struct Frame {
 	uint8_t* data;