KITTY Compression Algorithm

kitty.c

//
// 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;
}

Great work! What license is this released under?

It was on the encode forum about tiny compression algorithms. Public Domain I'd say. No license published by the original author. There are probably better algorithms TBH.

Thanks for the response! It seems to do quite alright for such a small algorithm, but you're right, there probably are better ones.