rleflate.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/param.h>

// huffman tree encoding is suboptimal rn, will improve later...
static const uint8_t RLEFLATE_MAGIC[] = "\xed\xe3\t\x90$I\x92$I\xcc\xff\xff\xff\xff\xff\xff\xff\xff"
"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
"\xff\xff\xff\xff?3333\xe1\x0e\x00\x0e``\xa0\xaa*\"\xc2\xdc]U\x04\x00\x80";
static const size_t RLEFLATE_MAGIC_LEN = sizeof(RLEFLATE_MAGIC) - 1;

static const uint8_t RLEFLATE_EOF = 0x77;
static const uint8_t RLEFLATE_REPEAT_PREFIX = 0xf7;
static const uint8_t RLEFLATE_REPEAT_A[] = {-1, 0x57, 0x37, 0x47, 0x67, 0x23, 0x33, 0x2b, 0x3b, 0x11, 0x51, 0x19, 0x59, 0x15, 0x55, 0x1d, 0x5d, 0x0a, 0x2a, 0x4a, 0x6a, 0x0e, 0x2e, 0x4e, 0x6e};
static const uint8_t RLEFLATE_REPEAT_B[] = {0x0b, 0x2b, 0x4b, 0x6b, 0x0f, 0x2f, 0x4f, 0x6f, 0x04, 0x14, 0x24, 0x34, 0x44, 0x54, 0x64, 0x74, 0x06, 0x16, 0x26, 0x36, 0x46, 0x56, 0x66, 0x76, 0x05, 0x15, 0x25, 0x35, 0x45, 0x55, 0x65, 0x75};
static const uint8_t RLEFLATE_REPEAT_C[] = {0x04, 0x14, 0x24, 0x34, 0x44, 0x54, 0x64, 0x74};

#if 1
static void write_uint32(uint8_t *buf, uint32_t in)
{
	uint32_t swp = in; // swap bit order in each nibble
	swp = ((swp >> 2) & 0b00110011001100110011001100110011) | ((swp << 2) & 0b11001100110011001100110011001100);
	swp = ((swp >> 1) & 0b01010101010101010101010101010101) | ((swp << 1) & 0b10101010101010101010101010101010);

	// swap nibbles and shift right by 8
	uint32_t swp2 = ((swp >> 12) & 0b000011110000000000001111) | ((swp >> 4) & 0b111100000000000011110000);

	// note: current swp shift values assume little-endian
	buf[0] = 0x0f | (swp & 0xf0);
	buf[1] = 0xf0 | (swp & 0x0f);
	buf[2] = swp2;
	buf[3] = 0x0f | ((swp >> 16) & 0xf0);
	buf[4] = 0xf0 | ((swp >> 16) & 0x0f);
	buf[5] = swp2 >> 16;
}
# else
static void write_uint32(uint8_t *buf, uint32_t in)
{
	uint64_t swp = in; // swap bit order in each byte
	swp = ((swp >> 4) & 0b00001111000011110000111100001111) | ((swp << 4) & 0b11110000111100001111000011110000);
	swp = ((swp >> 2) & 0b00110011001100110011001100110011) | ((swp << 2) & 0b11001100110011001100110011001100);
	swp = ((swp >> 1) & 0b01010101010101010101010101010101) | ((swp << 1) & 0b10101010101010101010101010101010);

	uint64_t word = 0x00f00f00f00f |
		((swp & 0xff) << 4) |
		((swp & 0xff00) << 8) |
		((swp & 0xff0000) << 12) |
		((swp & 0xff000000) << 16);
	
	*((uint64_t*)buf) = word;
}
#endif

static void write_uint16(uint8_t *buf, uint16_t in)
{
	uint16_t swp = in; // swap bit order in each nibble
	swp = ((swp >> 2) & 0b0011001100110011) | ((swp << 2) & 0b1100110011001100);
	swp = ((swp >> 1) & 0b0101010101010101) | ((swp << 1) & 0b1010101010101010);

	// note: current swp shift values assume little-endian
	buf[0] = 0x0f | (swp & 0xf0);
	buf[1] = 0xf0 | (swp & 0x0f);
	buf[2] = ((swp >> 12) & 0x0f) | ((swp >> 4) & 0xf0);
}

static void write_uint8_final(uint8_t *buf, uint8_t in)
{
	uint8_t swp = in; // swap bit order in each nibble
	swp = ((swp >> 2) & 0b00110011) | ((swp << 2) & 0b11001100);
	swp = ((swp >> 1) & 0b01010101) | ((swp << 1) & 0b10101010);

	// note: current swp shift values assume little-endian
	buf[0] = 0x0f | (swp & 0xf0);
	buf[1] = 0x70 | (swp & 0x0f);
	buf[2] = 0x07;
}

static size_t rledeflate(uint8_t *out, uint8_t *in, size_t inlen)
{
	size_t outi = 0;
	size_t ini = 0;
	memcpy(out, RLEFLATE_MAGIC, RLEFLATE_MAGIC_LEN);
	outi += RLEFLATE_MAGIC_LEN;
	while (ini + 3 < inlen) {
		size_t runlen = 0;
		uint32_t *words = (uint32_t*)&in[ini];
		size_t limit = MIN(64, (inlen - ini) / 4); // TODO: verify no off-by-one
		if (ini >= 4) {
			while ((words[-1] == words[runlen]) && runlen < limit) {
				runlen++;
			}
		}
		if ((runlen == 0) || 0) {
			write_uint32(&out[outi], words[0]);
			ini += 4;
			outi += 6;
		} else {
			if (runlen < sizeof(RLEFLATE_REPEAT_A)) {
				out[outi++] = RLEFLATE_REPEAT_A[runlen];
			} else if (runlen < sizeof(RLEFLATE_REPEAT_A) + sizeof(RLEFLATE_REPEAT_B)) {
				out[outi++] = RLEFLATE_REPEAT_PREFIX;
				out[outi++] = RLEFLATE_REPEAT_B[runlen - sizeof(RLEFLATE_REPEAT_A)];
			} else {
				out[outi++] = RLEFLATE_REPEAT_C[runlen - sizeof(RLEFLATE_REPEAT_A) - sizeof(RLEFLATE_REPEAT_B)];
			}
			ini += 4 * runlen;
		}
	}
	size_t remainder = inlen - ini;
	if (remainder >= 2) {
		write_uint16(&out[outi], *((uint16_t*)&in[ini]));
		remainder -= 2;
		ini += 2;
		outi += 3;
	}
	if (remainder == 1) {
		write_uint8_final(&out[outi], in[ini]);
		outi += 3;
	} else {
		out[outi++] = RLEFLATE_EOF;
	}
	return outi;
}

#if 0
static size_t rleinflate(uint8_t *out, uint8_t *in, size_t inlen)
{
	size_t outi = 0;
	size_t ini = 0;
	while (ini < inlen) {
		uint64_t word = *((uint64_t*)&in[ini]);
		uint64_t masked = word & 0x00f00f00f00f;
		if (masked == 0x00f00f00f00f) {
			// TODO
		}
	}
	return outi;
}
#endif

int main(int argc, char *argv[])
{
	if (argc != 3) {
		printf("USAGE: %s input.bin output.bin\n", argv[0]);
		return -1;
	}

	FILE *infile = fopen(argv[1], "rb");
	if (infile == NULL) {
		perror("fopen");
		return -1;
	}

	fseek(infile, 0, SEEK_END);
	size_t inlen = ftell(infile);
	rewind(infile);

	uint8_t *inbuf = malloc(inlen);
	if (inbuf == NULL) {
		perror("malloc");
		return -1;
	}

	if (fread(inbuf, 1, inlen, infile) != inlen) {
		fprintf(stderr, "rleflate: failed to read whole input file\n");
		return -1;
	}

	fclose(infile);

	size_t worst_case_outlen = RLEFLATE_MAGIC_LEN + inlen * 1.5 + 3;
	uint8_t *outbuf = malloc(worst_case_outlen);
	if (outbuf == NULL) {
		perror("malloc");
		return -1;
	}

	struct timespec tstart={0,0}, tend={0,0};
	clock_gettime(CLOCK_MONOTONIC, &tstart);

	size_t compressed_len = rledeflate(outbuf, inbuf, inlen);

	clock_gettime(CLOCK_MONOTONIC, &tend);
	double duration = ((double)tend.tv_sec + 1.0e-9*tend.tv_nsec) - ((double)tstart.tv_sec + 1.0e-9*tstart.tv_nsec);


	FILE *outfile = fopen(argv[2], "wb");
	if (outfile == NULL) {
		perror("fopen");
		return -1;
	}

	if (fwrite(outbuf, 1, compressed_len, outfile) != compressed_len) {
		fprintf(stderr, "rleflate: failed to write whole output file\n");
		return -1;
	}

	fclose(outfile);

	fprintf(stderr, "rleflate: Success!\n");
	fprintf(stderr, "ratio: %lf (%lub in, %lub out)\n", (double)compressed_len/inlen, inlen, compressed_len);
	fprintf(stderr, "time: %lfs\n", duration);
	double mbytesperse = (double)inlen / duration / 0x100000p0;
	fprintf(stderr, "speed: %uMB/s\n", (unsigned int)mbytesperse);
}