diff options
Diffstat (limited to 'tools/gbagfx')
| -rw-r--r-- | tools/gbagfx/Makefile | 5 | ||||
| -rwxr-xr-x | tools/gbagfx/gbagfx.exe | bin | 1685933 -> 1691545 bytes | |||
| -rw-r--r-- | tools/gbagfx/huff.c | 398 | ||||
| -rw-r--r-- | tools/gbagfx/huff.h | 38 | ||||
| -rw-r--r-- | tools/gbagfx/lz.c | 4 | ||||
| -rw-r--r-- | tools/gbagfx/lz.h | 2 | ||||
| -rw-r--r-- | tools/gbagfx/main.c | 74 |
7 files changed, 515 insertions, 6 deletions
diff --git a/tools/gbagfx/Makefile b/tools/gbagfx/Makefile index 339585b..8b75d87 100644 --- a/tools/gbagfx/Makefile +++ b/tools/gbagfx/Makefile @@ -4,13 +4,16 @@ CFLAGS = -Wall -Wextra -Werror -std=c11 -O2 -DPNG_SKIP_SETJMP_CHECK LIBS = -lpng -lz -SRCS = main.c convert_png.c gfx.c jasc_pal.c lz.c rl.c util.c font.c +SRCS = main.c convert_png.c gfx.c jasc_pal.c lz.c rl.c util.c font.c huff.c .PHONY: all clean all: gbagfx @: +gbagfx-debug: $(SRCS) convert_png.h gfx.h global.h jasc_pal.h lz.h rl.h util.h font.h + $(CC) $(CFLAGS) -DDEBUG $(SRCS) -o $@ $(LDFLAGS) $(LIBS) + gbagfx: $(SRCS) convert_png.h gfx.h global.h jasc_pal.h lz.h rl.h util.h font.h $(CC) $(CFLAGS) $(SRCS) -o $@ $(LDFLAGS) $(LIBS) diff --git a/tools/gbagfx/gbagfx.exe b/tools/gbagfx/gbagfx.exe Binary files differindex a8efff4..d5def1d 100755 --- a/tools/gbagfx/gbagfx.exe +++ b/tools/gbagfx/gbagfx.exe diff --git a/tools/gbagfx/huff.c b/tools/gbagfx/huff.c new file mode 100644 index 0000000..9d807b0 --- /dev/null +++ b/tools/gbagfx/huff.c @@ -0,0 +1,398 @@ +#include <stdbool.h> +#include <string.h> +#include <assert.h> +#include <stdio.h> +#include <stdint.h> +#include "global.h" +#include "huff.h" + +static int cmp_tree(const void * a0, const void * b0) { + return ((struct HuffData *)a0)->value - ((struct HuffData *)b0)->value; +} + +typedef int (*cmpfun)(const void *, const void *); + +int msort_r(void * data, size_t count, size_t size, cmpfun cmp, void * buffer) { + /* + * Out-of-place mergesort (stable sort) + * Returns 1 on success, 0 on failure + */ + void * leftPtr; + void * rightPtr; + void * leftEnd; + void * rightEnd; + unsigned int i; + + switch (count) { + case 0: + // Should never be here + return 0; + + case 1: + // Nothing to do here + break; + + case 2: + // Swap the two entries if the right one compares higher. + if (cmp(data, data + size) > 0) { + memcpy(buffer, data, size); + memcpy(data, data + size, size); + memcpy(data + size, buffer, size); + } + break; + default: + // Merge sort out-of-place. + leftPtr = data; + leftEnd = rightPtr = data + count / 2 * size; + rightEnd = data + count * size; + + // Sort the left half + if (!msort_r(leftPtr, count / 2, size, cmp, buffer)) + return 0; + + // Sort the right half + if (!msort_r(rightPtr, count / 2 + (count & 1), size, cmp, buffer)) + return 0; + + // Merge the sorted halves out of place + i = 0; + do { + if (cmp(leftPtr, rightPtr) <= 0) { + memcpy(buffer + i * size, leftPtr, size); + leftPtr += size; + } else { + memcpy(buffer + i * size, rightPtr, size); + rightPtr += size; + } + + } while (++i < count && leftPtr < leftEnd && rightPtr < rightEnd); + + // Copy the remainder + if (i < count) { + if (leftPtr < leftEnd) { + memcpy(buffer + i * size, leftPtr, leftEnd - leftPtr); + } + else { + memcpy(buffer + i * size, rightPtr, rightEnd - rightPtr); + } + } + + // Copy the merged data back + memcpy(data, buffer, count * size); + break; + } + + return 1; +} + +int msort(void * data, size_t count, size_t size, cmpfun cmp) { + void * buffer = malloc(count * size); + if (buffer == NULL) return 0; + int result = msort_r(data, count, size, cmp, buffer); + free(buffer); + return result; +} + +static void write_tree(unsigned char * dest, HuffNode_t * tree, int nitems, struct BitEncoding * encoding) { + /* + * The example used to guide this function encodes the tree in a + * breadth-first manner. We attempt to emulate that here. + */ + + int i, j, k; + + // There are (2 * nitems - 1) nodes in the binary tree. Allocate that. + HuffNode_t * traversal = calloc(2 * nitems - 1, sizeof(HuffNode_t)); + if (traversal == NULL) + FATAL_ERROR("Fatal error while compressing Huff file.\n"); + + // The first node is the root of the tree. + traversal[0] = *tree; + i = 1; + + // Copy the tree into a breadth-first ordering using brute force. + for (int depth = 1; i < 2 * nitems - 1; depth++) { + // Consider every possible path up to the current depth. + for (j = 0; i < 2 * nitems - 1 && j < 1 << depth; j++) { + // The index of the path is used to encode the path itself. + // Start from the most significant relevant bit and work our way down. + // Keep track of the current and previous nodes. + HuffNode_t * currNode = traversal; + HuffNode_t * parent = NULL; + for (k = 0; k < depth; k++) { + if (currNode->header.isLeaf) + break; + parent = currNode; + if ((j >> (depth - k - 1)) & 1) + currNode = currNode->branch.right; + else + currNode = currNode->branch.left; + } + // Check that the length of the current path equals the current depth. + if (k == depth) { + // Make sure we can encode the current branch. + // Bail here if we cannot. + // This is only applicable for 8-bit encodings. + if (traversal + i - parent > 128) + FATAL_ERROR("Fatal error while compressing Huff file: unable to encode binary tree.\n"); + // Copy the current node, and update its parent. + traversal[i] = *currNode; + if (parent != NULL) { + if ((j & 1) == 1) + parent->branch.right = traversal + i; + else + parent->branch.left = traversal + i; + } + // Encode the path through the tree in the lookup table + if (traversal[i].header.isLeaf) { + encoding[traversal[i].leaf.key].nbits = depth; + encoding[traversal[i].leaf.key].bitstring = j; + } + i++; + } + } + } + + // Encode the size of the tree. + // This is used by the decompressor to skip the tree. + dest[4] = nitems - 1; + + // Encode each node in the tree. + for (i = 0; i < 2 * nitems - 1; i++) { + HuffNode_t * currNode = traversal + i; + if (currNode->header.isLeaf) { + dest[5 + i] = traversal[i].leaf.key; + } else { + dest[5 + i] = (((currNode->branch.right - traversal - i) / 2) - 1); + if (currNode->branch.left->header.isLeaf) + dest[5 + i] |= 0x80; + if (currNode->branch.right->header.isLeaf) + dest[5 + i] |= 0x40; + } + } + + free(traversal); +} + +static inline void write_32_le(unsigned char * dest, int * destPos, uint32_t * buff, int * buffPos) { + dest[*destPos] = *buff; + dest[*destPos + 1] = *buff >> 8; + dest[*destPos + 2] = *buff >> 16; + dest[*destPos + 3] = *buff >> 24; + *destPos += 4; + *buff = 0; + *buffPos = 0; +} + +static inline void read_32_le(unsigned char * src, int * srcPos, uint32_t * buff) { + uint32_t tmp = src[*srcPos]; + tmp |= src[*srcPos + 1] << 8; + tmp |= src[*srcPos + 2] << 16; + tmp |= src[*srcPos + 3] << 24; + *srcPos += 4; + *buff = tmp; +} + +static void write_bits(unsigned char * dest, int * destPos, struct BitEncoding * encoding, int value, uint32_t * buff, int * buffBits) { + int nbits = encoding[value].nbits; + uint32_t bitstring = encoding[value].bitstring; + + if (*buffBits + nbits >= 32) { + int diff = *buffBits + nbits - 32; + *buff <<= nbits - diff; + *buff |= bitstring >> diff; + bitstring &= ~(1 << diff); + nbits = diff; + write_32_le(dest, destPos, buff, buffBits); + } + if (nbits != 0) { + *buff <<= nbits; + *buff |= bitstring; + *buffBits += nbits; + } +} + +/* +======================================= +MAIN COMPRESSION/DECOMPRESSION ROUTINES +======================================= + */ + +unsigned char * HuffCompress(unsigned char * src, int srcSize, int * compressedSize_p, int bitDepth) { + if (srcSize <= 0) + goto fail; + + int worstCaseDestSize = 4 + (2 << bitDepth) + srcSize * 3; + + unsigned char *dest = malloc(worstCaseDestSize); + if (dest == NULL) + goto fail; + + int nitems = 1 << bitDepth; + + HuffNode_t * freqs = calloc(nitems, sizeof(HuffNode_t)); + if (freqs == NULL) + goto fail; + + struct BitEncoding * encoding = calloc(nitems, sizeof(struct BitEncoding)); + if (encoding == NULL) + goto fail; + + // Set up the frequencies table. This will inform the tree. + for (int i = 0; i < nitems; i++) { + freqs[i].header.isLeaf = 1; + freqs[i].header.value = 0; + freqs[i].leaf.key = i; + } + + // Count each nybble or byte. + for (int i = 0; i < srcSize; i++) { + if (bitDepth == 8) { + freqs[src[i]].header.value++; + } else { + freqs[src[i] >> 4].header.value++; + freqs[src[i] & 0xF].header.value++; + } + } + +#ifdef DEBUG + for (int i = 0; i < nitems; i++) { + fprintf(stderr, "%d: %d\n", i, freqs[i].header.value); + } +#endif // DEBUG + + // Sort the frequency table. + if (!msort(freqs, nitems, sizeof(HuffNode_t), cmp_tree)) + goto fail; + + // Prune zero-frequency values. + for (int i = 0; i < nitems; i++) { + if (freqs[i].header.value != 0) { + if (i > 0) { + for (int j = i; j < nitems; j++) { + freqs[j - i] = freqs[j]; + } + nitems -= i; + } + break; + } + // This should never happen: + if (i == nitems - 1) + goto fail; + } + + HuffNode_t * tree = calloc(nitems * 2 - 1, sizeof(HuffNode_t)); + if (tree == NULL) + goto fail; + + // Iteratively collapse the two least frequent nodes. + HuffNode_t * endptr = freqs + nitems - 2; + + for (int i = 0; i < nitems - 1; i++) { + HuffNode_t * left = freqs; + HuffNode_t * right = freqs + 1; + tree[i * 2] = *right; + tree[i * 2 + 1] = *left; + for (int j = 0; j < nitems - i - 2; j++) + freqs[j] = freqs[j + 2]; + endptr->header.isLeaf = 0; + endptr->header.value = tree[i * 2].header.value + tree[i * 2 + 1].header.value; + endptr->branch.left = tree + i * 2; + endptr->branch.right = tree + i * 2 + 1; + endptr--; + if (i < nitems - 2 && !msort(freqs, nitems - i - 1, sizeof(HuffNode_t), cmp_tree)) + goto fail; + } + + // Write the tree breadth-first, and create the path lookup table. + write_tree(dest, freqs, nitems, encoding); + + free(tree); + free(freqs); + + // Encode the data itself. + int destPos = 4 + nitems * 2; + uint32_t destBuf = 0; + uint32_t srcBuf = 0; + int destBitPos = 0; + + for (int srcPos = 0; srcPos < srcSize;) { + read_32_le(src, &srcPos, &srcBuf); + for (int i = 0; i < 32 / bitDepth; i++) { + write_bits(dest, &destPos, encoding, srcBuf & (0xFF >> (8 - bitDepth)), &destBuf, &destBitPos); + srcBuf >>= bitDepth; + } + } + + if (destBitPos != 0) { + write_32_le(dest, &destPos, &destBuf, &destBitPos); + } + + free(encoding); + + // Write the header. + dest[0] = bitDepth | 0x20; + dest[1] = srcSize; + dest[2] = srcSize >> 8; + dest[3] = srcSize >> 16; + *compressedSize_p = (destPos + 3) & ~3; + return dest; + +fail: + FATAL_ERROR("Fatal error while compressing Huff file.\n"); +} + +unsigned char * HuffDecompress(unsigned char * src, int srcSize, int * uncompressedSize_p) { + if (srcSize < 4) + goto fail; + + int bitDepth = *src & 15; + if (bitDepth != 4 && bitDepth != 8) + goto fail; + + int destSize = (src[3] << 16) | (src[2] << 8) | src[1]; + + unsigned char *dest = malloc(destSize); + + if (dest == NULL) + goto fail; + + int treePos = 5; + int treeSize = (src[4] + 1) * 2; + int srcPos = 4 + treeSize; + int destPos = 0; + int curValPos = 0; + uint32_t destTmp = 0; + uint32_t window; + + for (;;) + { + if (srcPos >= srcSize) + goto fail; + read_32_le(src, &srcPos, &window); + for (int i = 0; i < 32; i++) { + int curBit = (window >> 31) & 1; + unsigned char treeView = src[treePos]; + bool isLeaf = ((treeView << curBit) & 0x80) != 0; + treePos &= ~1; // align + treePos += ((treeView & 0x3F) + 1) * 2 + curBit; + if (isLeaf) { + destTmp >>= bitDepth; + destTmp |= (src[treePos] << (32 - bitDepth)); + curValPos++; + if (curValPos == 32 / bitDepth) { + write_32_le(dest, &destPos, &destTmp, &curValPos); + if (destPos == destSize) { + *uncompressedSize_p = destSize; + return dest; + } + } + treePos = 5; + } + window <<= 1; + } + } + +fail: + FATAL_ERROR("Fatal error while decompressing Huff file.\n"); +} diff --git a/tools/gbagfx/huff.h b/tools/gbagfx/huff.h new file mode 100644 index 0000000..6002fe9 --- /dev/null +++ b/tools/gbagfx/huff.h @@ -0,0 +1,38 @@ +#ifndef HUFF_H +#define HUFF_H + +union HuffNode; + +struct HuffData { + unsigned value:31; + unsigned isLeaf:1; +}; + +struct HuffLeaf { + struct HuffData header; + unsigned char key; +}; + +struct HuffBranch { + struct HuffData header; + union HuffNode * left; + union HuffNode * right; +}; + +union HuffNode { + struct HuffData header; + struct HuffLeaf leaf; + struct HuffBranch branch; +}; + +typedef union HuffNode HuffNode_t; + +struct BitEncoding { + unsigned long long nbits:6; + unsigned long long bitstring:58; +}; + +unsigned char * HuffCompress(unsigned char * buffer, int srcSize, int * compressedSize_p, int bitDepth); +unsigned char * HuffDecompress(unsigned char * buffer, int srcSize, int * uncompressedSize_p); + +#endif //HUFF_H diff --git a/tools/gbagfx/lz.c b/tools/gbagfx/lz.c index c2ba3e3..97434ce 100644 --- a/tools/gbagfx/lz.c +++ b/tools/gbagfx/lz.c @@ -69,10 +69,8 @@ fail: FATAL_ERROR("Fatal error while decompressing LZ file.\n"); } -unsigned char *LZCompress(unsigned char *src, int srcSize, int *compressedSize) +unsigned char *LZCompress(unsigned char *src, int srcSize, int *compressedSize, const int minDistance) { - const int minDistance = 2; // for compatibility with LZ77UnCompVram() - if (srcSize <= 0) goto fail; diff --git a/tools/gbagfx/lz.h b/tools/gbagfx/lz.h index 164d622..90f56b6 100644 --- a/tools/gbagfx/lz.h +++ b/tools/gbagfx/lz.h @@ -4,6 +4,6 @@ #define LZ_H unsigned char *LZDecompress(unsigned char *src, int srcSize, int *uncompressedSize); -unsigned char *LZCompress(unsigned char *src, int srcSize, int *compressedSize); +unsigned char *LZCompress(unsigned char *src, int srcSize, int *compressedSize, const int minDistance); #endif // LZ_H diff --git a/tools/gbagfx/main.c b/tools/gbagfx/main.c index 86b0afa..aa0681f 100644 --- a/tools/gbagfx/main.c +++ b/tools/gbagfx/main.c @@ -12,6 +12,7 @@ #include "lz.h" #include "rl.h" #include "font.h" +#include "huff.h" struct CommandHandler { @@ -319,6 +320,7 @@ void HandlePngToFullwidthJapaneseFontCommand(char *inputPath, char *outputPath, void HandleLZCompressCommand(char *inputPath, char *outputPath, int argc, char **argv) { int overflowSize = 0; + int minDistance = 2; // default, for compatibility with LZ77UnCompVram() for (int i = 3; i < argc; i++) { @@ -337,6 +339,19 @@ void HandleLZCompressCommand(char *inputPath, char *outputPath, int argc, char * if (overflowSize < 1) FATAL_ERROR("Overflow size must be positive.\n"); } + else if (strcmp(option, "-search") == 0) + { + if (i + 1 >= argc) + FATAL_ERROR("No size following \"-overflow\".\n"); + + i++; + + if (!ParseNumber(argv[i], NULL, 10, &minDistance)) + FATAL_ERROR("Failed to parse LZ min search distance.\n"); + + if (minDistance < 1) + FATAL_ERROR("LZ min search distance must be positive.\n"); + } else { FATAL_ERROR("Unrecognized option \"%s\".\n", option); @@ -353,7 +368,7 @@ void HandleLZCompressCommand(char *inputPath, char *outputPath, int argc, char * unsigned char *buffer = ReadWholeFileZeroPadded(inputPath, &fileSize, overflowSize); int compressedSize; - unsigned char *compressedData = LZCompress(buffer, fileSize + overflowSize, &compressedSize); + unsigned char *compressedData = LZCompress(buffer, fileSize + overflowSize, &compressedSize, minDistance); compressedData[1] = (unsigned char)fileSize; compressedData[2] = (unsigned char)(fileSize >> 8); @@ -411,6 +426,61 @@ void HandleRLDecompressCommand(char *inputPath, char *outputPath, int argc UNUSE free(uncompressedData); } +void HandleHuffCompressCommand(char *inputPath, char *outputPath, int argc, char **argv) +{ + int fileSize; + int bitDepth = 4; + + for (int i = 3; i < argc; i++) + { + char *option = argv[i]; + + if (strcmp(option, "-depth") == 0) + { + if (i + 1 >= argc) + FATAL_ERROR("No size following \"-depth\".\n"); + + i++; + + if (!ParseNumber(argv[i], NULL, 10, &bitDepth)) + FATAL_ERROR("Failed to parse bit depth.\n"); + + if (bitDepth != 4 && bitDepth != 8) + FATAL_ERROR("GBA only supports bit depth of 4 or 8.\n"); + } + else + { + FATAL_ERROR("Unrecognized option \"%s\".\n", option); + } + } + + unsigned char *buffer = ReadWholeFile(inputPath, &fileSize); + + int compressedSize; + unsigned char *compressedData = HuffCompress(buffer, fileSize, &compressedSize, bitDepth); + + free(buffer); + + WriteWholeFile(outputPath, compressedData, compressedSize); + + free(compressedData); +} + +void HandleHuffDecompressCommand(char *inputPath, char *outputPath, int argc UNUSED, char **argv UNUSED) +{ + int fileSize; + unsigned char *buffer = ReadWholeFile(inputPath, &fileSize); + + int uncompressedSize; + unsigned char *uncompressedData = HuffDecompress(buffer, fileSize, &uncompressedSize); + + free(buffer); + + WriteWholeFile(outputPath, uncompressedData, uncompressedSize); + + free(uncompressedData); +} + int main(int argc, char **argv) { if (argc < 3) @@ -433,7 +503,9 @@ int main(int argc, char **argv) { "png", "hwjpnfont", HandlePngToHalfwidthJapaneseFontCommand }, { "fwjpnfont", "png", HandleFullwidthJapaneseFontToPngCommand }, { "png", "fwjpnfont", HandlePngToFullwidthJapaneseFontCommand }, + { NULL, "huff", HandleHuffCompressCommand }, { NULL, "lz", HandleLZCompressCommand }, + { "huff", NULL, HandleHuffDecompressCommand }, { "lz", NULL, HandleLZDecompressCommand }, { NULL, "rl", HandleRLCompressCommand }, { "rl", NULL, HandleRLDecompressCommand }, |