summaryrefslogtreecommitdiff
path: root/tools/gbagfx/huff.c
diff options
context:
space:
mode:
Diffstat (limited to 'tools/gbagfx/huff.c')
-rw-r--r--tools/gbagfx/huff.c398
1 files changed, 398 insertions, 0 deletions
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");
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-05 19:12:56 +0000