Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
KITTY Compression Algorithm
//
// KITTY compression algorithm, by snowcat
// converted to C, by odzhan
// 2019-12-07
//
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#define KITTY_COMPRESS 1
#define KITTY_DECOMPRESS 0
FILE *in, *out;
typedef struct _kitty_ctx_t {
uint32_t x, x1, x2, mode;
uint8_t m[256];
uint16_t t[256];
} kitty_ctx;
uint32_t update(kitty_ctx *c, uint32_t cxt, uint32_t y) {
uint32_t tx = c->t[cxt];
uint32_t xmid = c->x1 + (c->x2 - c->x1 >> 12) * (tx >> 4);
if(c->mode == KITTY_DECOMPRESS) y = c->x <= xmid;
y ? (c->x2 = xmid) : (c->x1 = xmid + 1);
c->t[cxt] += ( (((y << 16) - tx) & 0xFFFFFFFF) * 15) >> 9; // update cxt
while((c->x1 ^ c->x2) <= 0x00ffffff) { // pass equal leading bytes of range
if(c->mode == KITTY_DECOMPRESS) {
c->x = (c->x << 8) + (getc(in) & 255); // decompress
} else {
putc(c->x2 >> 24, out); // compress
}
c->x1 <<= 8;
c->x2 =(c->x2 << 8) + 255;
}
return y;
}
void literal(kitty_ctx *c, uint32_t code) {
uint32_t bit, x = 1;
do {
bit = (code & 0x80) == 0;
update(c, x, bit); // compress
x += x + bit;
code <<= 1;
} while(x <= 0xFF);
}
// initialize kitty context
void kitty_init(kitty_ctx *c, int mode) {
int i;
c->mode = mode;
c->x = 0;
c->x1 = 0;
c->x2 = -1;
for(i=0; i<256; i++) {
c->t[i] = 1 << 15;
c->m[i] = i;
}
}
void kitty_compress(const void *inbuf, uint32_t inlen, void *outbuf) {
kitty_ctx ctx;
uint32_t i, c, c1 = 0;
kitty_init(&ctx, KITTY_COMPRESS);
while ((c = getc(in)) != EOF) {
if(ctx.m[c1] == c) {
update(&ctx, 0, 0); // match
} else {
ctx.m[c1] = c; // update array m
update(&ctx, 0, 1); // literal
literal(&ctx, c); // code a literal
}
c1 = c;
}
update(&ctx, 0, 1);
literal(&ctx, ctx.m[c1]);
for(i=0; i<4; ++i) {
putc(ctx.x2 >> 24, out); // flush
ctx.x2 <<= 8;
}
}
void kitty_decompress(const void *inbuf, uint32_t inlen, void *outbuf) {
kitty_ctx ctx;
uint32_t x, i, c1 = 0;
kitty_init(&ctx, KITTY_DECOMPRESS);
for(i=0; i<4; i++) {
ctx.x = (ctx.x << 8) + (getc(in) & 255);
}
while (1) {
if(update(&ctx, 0, 0) == 0) {
c1 = ctx.m[c1];
} else {
x = 1;
do {
x += x + (update(&ctx, x, 0) == 0);
} while(x <= 0xFF);
if((x &= 0xFF) == ctx.m[c1]) break;
ctx.m[c1] = x;
c1 = x;
}
putc(c1, out);
}
}
// User interface. Args are input and output file.
int main(int argc, char **argv) {
// Check arguments
if ((argc!=4)||((argv[1][0]!='c')&&(argv[1][0]!='d'))) {
printf("Usage: kitty c/d input output\n");
return 0;
}
in = fopen(argv[2], "rb");
if (!in) {perror(argv[2]); return 1;}
out = fopen(argv[3], "wb");
if (!out) {perror(argv[3]); return 1;}
if (argv[1][0]=='c') {
printf("Compressing %s to %s ...\n", argv[2], argv[3]);
kitty_compress(0, 0, 0); // Compress
} else {
printf("Decompressing %s from %s ...\n", argv[3], argv[2]);
kitty_decompress(0, 0, 0); // Decompress
}
fclose(in);
fclose(out);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.