Skip to content

Instantly share code, notes, and snippets.

@odzhan
Created December 7, 2019 09:09
Show Gist options
  • Save odzhan/6d8e10f81fd6e451ae0edc1a81ef8304 to your computer and use it in GitHub Desktop.
Save odzhan/6d8e10f81fd6e451ae0edc1a81ef8304 to your computer and use it in GitHub Desktop.
Jacky Qwerty/29A Compression Algorithm
//
// Jacky Qwerty/29A compression algorithm, by Matt Mahoney
// modified by odzhan
// 2019-12-07
//
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
FILE *in, *out;
void jqwerty_compress(const void *inbuf, uint32_t inlen, void *outbuf) {
int flags=1; // 8 packed bits: 1 = mispredicted byte. bit 8 = sentinel
int cxt=0; // 2 byte context
int n=0; // number of pending literals to write
int c; // last byte
int i;
unsigned char buf[8]={0}; // pending literals to write
unsigned char model[1<<16]={0}; // order 2 prediction of next byte
while(1) {
c = getc(in);
if(c != EOF) {
flags += flags;
if(c != model[cxt]) {
++flags;
buf[n++] = model[cxt] = c;
}
cxt=((cxt << 8) | c) & 0xffff;
} else {
while (flags < 256) {
flags += flags + 1; // pad
}
}
if(flags >= 256) {
putc(flags & 255, out);
for(i=0; i<n; ++i) {
putc(buf[i], out);
}
flags = 1;
n = 0;
}
if (c == EOF) break;
}
}
void jqwerty_decompress(const void *inbuf, uint32_t inlen, void *outbuf) {
int flags=1; // 8 packed bits: 1 = mispredicted byte. bit 8 = sentinel
int cxt=0; // 2 byte context
int c; // last byte
int i;
unsigned char model[1<<16]={0}; // order 2 prediction of next byte
while((flags = getc(in)) != EOF) {
for(i=7; i>=0; --i) {
if ((flags>>i)&1) {
c = getc(in);
if(c == EOF) break;
else putc(model[cxt] = c, out);
} else putc(c = model[cxt], out);
cxt=(cxt << 8 | c) & 0xffff;
}
}
}
// 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: jqwerty 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]);
jqwerty_compress(0, 0, 0); // Compress
} else {
printf("Decompressing %s from %s ...\n", argv[3], argv[2]);
jqwerty_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