111 lines
2.9 KiB
C
111 lines
2.9 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <limits.h>
|
|
|
|
#define GLYPHS_IN_LOOKUP 4
|
|
#define GLYPH_SIZE (CHAR_BIT)
|
|
|
|
unsigned char* encode(const unsigned char* data, const size_t len, size_t* out_len)
|
|
{
|
|
// This can be further optimized for size, I was just lazy
|
|
unsigned char* rle = calloc(len + 1, sizeof(unsigned char));
|
|
|
|
if (len == 0) {
|
|
*out_len = 0;
|
|
return rle;
|
|
}
|
|
|
|
*out_len = 1;
|
|
unsigned char bit = 0;
|
|
for (size_t i = 0; i < len; ++i) {
|
|
unsigned char val = data[i >> 3] & ((unsigned char) (1 << (7 - i & 7)));
|
|
// A bit flip has occurred in the stream
|
|
if (!val ^ !bit) {
|
|
bit = !bit;
|
|
(*out_len)++;
|
|
}
|
|
|
|
(*(rle + *out_len - 1))++;
|
|
}
|
|
|
|
return rle;
|
|
}
|
|
|
|
struct lookup_val {
|
|
unsigned char position : 5;
|
|
unsigned char offset : 3;
|
|
};
|
|
|
|
// Just assume lookup is the correct length
|
|
void fill_lookup(struct lookup_val* lookup, const unsigned char* rle, const size_t rle_len) {
|
|
size_t current = 0;
|
|
size_t rest = GLYPH_SIZE;
|
|
for (size_t i = 0; i < rle_len; ++i) {
|
|
while (rest >= GLYPH_SIZE) {
|
|
rest -= GLYPH_SIZE;
|
|
lookup[current].position = i;
|
|
lookup[current].offset = rest;
|
|
current++;
|
|
}
|
|
|
|
rest += rle[i];
|
|
}
|
|
}
|
|
|
|
void lookup_glyph(const unsigned char* rle,
|
|
const struct lookup_val* lookup,
|
|
const char glyph,
|
|
unsigned char* glyph_data_out,
|
|
const size_t glyph_data_len) {
|
|
const unsigned char* rle_current = &rle[lookup[glyph].position];
|
|
unsigned char current = *rle_current - lookup[glyph].offset;
|
|
unsigned char bit = 0;
|
|
for (size_t i = 0; i < glyph_data_len; ++i) {
|
|
if (!current) {
|
|
rle_current++;
|
|
current = *rle_current;
|
|
bit = !bit;
|
|
}
|
|
|
|
glyph_data_out[i >> 3] |= bit << (unsigned char) (7 - i & 7);
|
|
|
|
current--;
|
|
}
|
|
}
|
|
|
|
int main()
|
|
{
|
|
// The encoding can be done externally, just like building the lookup table
|
|
unsigned char data[] = { 0b01000101, 0b1110001, 0b00010010, 0b000100010 };
|
|
size_t rle_len;
|
|
unsigned char* rle = encode(data, sizeof(data) * CHAR_BIT, &rle_len);
|
|
|
|
printf("RLE-encoded data: \n");
|
|
for (int i = 0; i < rle_len; ++i)
|
|
printf("%dx%s, ", rle[i], i % 2 ? "1" : "0");
|
|
|
|
printf("\n\n");
|
|
|
|
// Index into the lookup table is the ASCII char value we want, here for simplicity only 4 chars
|
|
struct lookup_val lookup[GLYPHS_IN_LOOKUP];
|
|
fill_lookup(lookup, rle, rle_len);
|
|
|
|
printf("Lookup table: \n");
|
|
for (int i = 0; i < GLYPHS_IN_LOOKUP; ++i)
|
|
printf("%d, %d \n", lookup[i].position, lookup[i].offset);
|
|
|
|
putchar('\n');
|
|
|
|
unsigned char glyph;
|
|
lookup_glyph(rle, lookup, 2, &glyph, GLYPH_SIZE);
|
|
|
|
printf("Lookup result: ");
|
|
|
|
for (unsigned char i = GLYPH_SIZE; i > 0; --i) {
|
|
bool val = glyph & (1 << (i - 1));
|
|
putchar('1' * val + '0' * !val);
|
|
}
|
|
|
|
putchar('\n');
|
|
}
|