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