huffman.c

// DYNAMIC HUFFMAN ENCODING
// copyright (c) 1998 by Z0MBiE/29A
// 28-12-98 15:10:33
//
// 26-11-2019 - added code to test compression ratio. 
// typically ~20% for a 1MB EXE file
// odzhan
//
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <inttypes.h>
#include <fcntl.h>

#if defined(_WIN32) || defined(_WIN64)
#define WINDOWS
#include <windows.h>
#include "mmap.h"
#if defined(_MSC_VER)
#pragma comment(lib, "advapi32.lib")
#pragma comment(lib, "user32.lib")
#endif
#else
#define LINUX
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#endif

#define COD_BITS 32

typedef struct _huffman_ctx {
    int htree_count[511];
    int htree_next [511];
    int htree_prev0[511];
    int htree_prev1[511];
    int htree_bit  [511];
    int htree_code [256];
    int htree_len  [256];
    int htree_max;
    int htree_charcount;
} huffman_ctx;

int htree_findmin(huffman_ctx *c, int n) {
    int i, v, j = v = -1;
    
    for(i=0; i<c->htree_max; i++) {
      if(c->htree_next[i]==-1)
      if((v > c->htree_count[i]) || (v == -1))
      if(i != n) {
        v = c->htree_count[i];
        j = i;
      }
    }
    return j;
}
  
void htree_build(huffman_ctx *c) {
    int a, b, i, s;
    
    for(i=0; i<511; i++) {
      c->htree_next[i]  = -1;
      c->htree_prev0[i] = -1;
      c->htree_prev1[i] = -1;
    }
    
    s = 0;
    for(i=0; i<256; i++) s += c->htree_count[i];
    c->htree_max = 256;
    
    for(;;) {
      a = htree_findmin(c, -1);
      if(a == -1) return;
      
      b = htree_findmin(c, a);
      if(b == -1) break;
      
      c->htree_next[a] = c->htree_max;
      c->htree_next[b] = c->htree_max;
      c->htree_prev0[c->htree_max] = a;
      c->htree_prev1[c->htree_max] = b;
      c->htree_bit[a] = 0;
      c->htree_bit[b] = 1;
      c->htree_count[c->htree_max] = c->htree_count[a] + c->htree_count[b];
      c->htree_max++;
      if(c->htree_max > 511) return;
    }
      
    if(s != c->htree_count[c->htree_max-1]) return;
    
    for(i=0; i<256; i++) {
      c->htree_code[i] = 0;
      c->htree_len [i] = 0;
      a = i;
      
      for(;;) {
        if(c->htree_len[i] >= COD_BITS) return;
        if(c->htree_next[a] == -1) break;
        c->htree_code[i] = (c->htree_code[i] << 1) | c->htree_bit[a];
        c->htree_len[i]++;
        a = c->htree_next[a];
      }
    }
}
  
void htree_init(huffman_ctx *c) {
    int i;
    for(i=0; i<256; i++) c->htree_count[i] = 1;
    c->htree_charcount = 0;
}
  
void htree_update(huffman_ctx *c, uint8_t x) {
    c->htree_count[x]++;
    c->htree_charcount++;
    if ((c->htree_charcount & 63) == 0) htree_build(c);
}

// read from input, compress and store in output
// return the length of compressed buffer or zero on error
uint32_t compress(void *input, uint32_t inlen, void *output) {
    uint8_t     x, *in=(uint8_t*)input, *out=(uint8_t*)output;
    uint32_t    len, code;
    huffman_ctx c;
    
    // initialize
    htree_init(&c);
    htree_build(&c);
    
    len = code = 0;
    
    // main loop
    while(inlen) {
      x = *in++;
      code |= c.htree_code[x] << len;
      len  += c.htree_len[x];
      
      if(len > COD_BITS) return 0;
      
      while(len >= 8) {
        *out++ = (code & 255);
        code >>= 8;
        len -= 8;
      }
      htree_update(&c, x);
      inlen--;
    }
    if(len != 0) *out++ = (code & 255);
    return (out - (uint8_t*)output);
}

int main(int argc, char *argv[]) {
    struct stat fs;
    int         fd;
    uint32_t    inlen, outlen, diff;
    void        *inbuf, *outbuf;
    char        *infile, *outfile;
    
    if(argc != 2) {
      printf("usage: huffman <infile>\n");
      return 0;
    }
    
    infile = argv[1];
    
    if(stat(infile, &fs) != 0) {
      printf("unable to access %s\n", infile);
      return -1;
    }
    
    // open
    fd = open(infile, O_RDONLY);
    if(fd < 0) {
      printf("unable to open %s.\n", infile);
      return -1;
    }
    
    // map input file
    inlen = fs.st_size;
    inbuf = mmap(NULL, inlen, PROT_READ, MAP_PRIVATE, fd, 0);
      
    if(inbuf != NULL) {
      // allocate buffer for output
      outbuf = malloc(inlen);
      if(outbuf != NULL) {
        outlen = compress(inbuf, inlen, outbuf);
        diff = ((float)(inlen - outlen) / (float)inlen) * 100;
        printf("size reduced by %"PRId32"%%\n", diff);
        free(outbuf);
      } else {
        printf("malloc() failed.\n", infile);
      }
      munmap(inbuf, inlen);
    } else {
      printf("mmap() failed.\n");
    }
    close(fd);
    return 0;
}