pt_huffman

#include <stdio.h>

#define NCHARS 128
#define EOT 4

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
  FILE* fptr;
  int currentBit;
  unsigned char currentByte;
} BitStream;

void openWrite(BitStream* bs, char* filename) {
  bs->fptr = fopen(filename, "w");
  bs->currentBit = 0;
  bs->currentByte = 0;
}

void openRead(BitStream* bs, char* filename) {
  bs->fptr = fopen(filename, "r");
  bs->currentBit = 0;
  bs->currentByte = 0;
}

void closeWrite(BitStream bs) {
  bs.currentByte << 8 - bs.currentBit;
  fputc(bs.currentByte, bs.fptr);
  fclose(bs.fptr);
}

void closeRead(BitStream bs) { fclose(bs.fptr); }

int readBit(BitStream* bs) {
  if (bs->currentBit == 0) {
    bs->currentByte = fgetc(bs->fptr);
  }
  int result = bs->currentByte & (1 << (7 - bs->currentBit));
  bs->currentBit = (bs->currentBit + 1) % 8;
  return result;
}

void writeBit(BitStream* bs, int b) {
  if (b) {
    bs->currentByte = bs->currentByte | (1 << (7 - bs->currentBit));
  }
  bs->currentBit = (bs->currentBit + 1) % 8;
  if (bs->currentBit == 0) {
    fputc(bs->currentByte, bs->fptr);
    bs->currentByte = 0;
  }
}

typedef struct node {
  int f;
  char c;
  struct node* links;
  struct node* rechts;
} Node;

Node* create(int f, char c) {
  Node* node = (Node* )malloc(sizeof(Node));
  node->f = f;
  node->c = c;
  node->links = NULL;
  node->rechts = NULL;
}

Node* destroy(Node* node) {
  if (node != NULL) {
    destroy(node->links);
    destroy(node->rechts);
    free(node);
  }
  return NULL;
}

void printBoom(Node* t, int level) {
  if (t == NULL) {
    return;
  }
  printBoom(t->rechts, level + 1);
  for (int i = 0; i < 4 * level; ++i) {
    printf(" ");
  }
  printf("->");
  printf("%c %-3d\n", t->c, t->f);
  printBoom(t->links, level + 1);
}

Node* voegSamen(Node* x, Node* y) {
  assert(x != NULL);
  assert(y != NULL);
  assert(x->f <= y->f);
  Node* result = create(x->f + y->f, '\0');
  result->links = x;
  result->rechts = y;
}

void merge(Node* a[], int n1, int n2, Node* b[]) {
  for (int i = 0; i < n2; ++i) {
    b[i] = a[i];
  }
  int j = 0;
  int k = n1;
  for (int i = 0; i < n2; ++i) {
    if (j < n1 && (k == n2 || b[j]->f <= b[k]->f)) {
      a[i] = b[j];
      ++j;
    } else {
      a[i] = b[k];
      ++k;
    }
  }
}

void mergeSort(Node* a[], int n, Node* b[]) {
  if (n <= 1) {
    return;
  }
  int mid = n / 2;
  mergeSort(&a[0], mid, b);
  mergeSort(&a[mid], n - mid, b);
  merge(a, mid, n, b);
}

Node* hoffmanBoom(char a[], int f[], int n) {
  Node* nodes[NCHARS];
  for (int i = 0; i < n; ++i) {
    nodes[i] = create(f[i], a[i]);
  }

  Node* tmp[NCHARS];
  mergeSort(nodes, n, tmp);

  for (int i = 1; i < n; ++i) {
    nodes[i] = voegSamen(nodes[i - 1], nodes[i]);
    for (int j = i + 1; j < n; ++j) {
      if (nodes[j - 1]->f > nodes[j]->f) {
        Node* tmp = nodes[j];
        nodes[j] = nodes[j - 1];
        nodes[j - 1] = tmp;
      } else {
        break;
      }
    }
  }

  return nodes[n - 1];
}

int vind(char c, Node* boom, char* code) {
  if (boom == NULL) {
    return 0;
  }
  if (boom->c == c) {
    return 1;
  }
  int n = strlen(code);
  code[n + 1] = '\0';
  code[n] = '1';
  if (vind(c, boom->links, code)) {
    return 1;
  }
  code[n] = '0';
  if (vind(c, boom->rechts, code)) {
    return 1;
  }
  code[n] = '\0';
  return 0;
}

int codeer(char* infile, Node* boom, char* outfile) {
  FILE* fptr = fopen(infile, "r");
  BitStream bs;
  openWrite(&bs, outfile);
  char code[NCHARS] = "";

  char c = EOF;
  while (c != EOT) {
    c = fgetc(fptr);
    if (c == EOF) {
      c = EOT;
    }
    code[0] = '\0';
    vind(c, boom, code);
    for (int i = 0; i < strlen(code); ++i) {
      writeBit(&bs, code[i] == '1');
    }
  }
  fclose(fptr);
  closeWrite(bs);
}

int decodeer(char* infile, Node* root, char* outfile) {
  FILE* fptr = fopen(outfile, "w");
  BitStream bs;
  openRead(&bs, infile);

  Node* current = root;
  while (current->c != EOT) {
    current = root;
    while (current->c == '\0') {
      if (readBit(&bs)) {
        current = current->links;
      } else {
        current = current->rechts;
      }
    }
    fprintf(fptr, "%c", current->c);
  }

  fclose(fptr);
  closeRead(bs);
}

void bewaarFrequenties(char* filename, char* a, int* f, int n) {
  FILE* fptr = fopen(filename, "w");
  for (int i = 0; i < n; ++i) {
    fprintf(fptr, "%c %d\n", a[i], f[i]);
  }
  fclose(fptr);
}

void berekenFrequenties(char* filename, char* a, int* f, int* n) {
  int charToFreq[NCHARS];
  for (int c = 0; c < NCHARS; ++c) {
    charToFreq[c] = 0;
  }

  charToFreq[EOT] = 1; // last character

  FILE* fptr = fopen(filename, "r");
  while (1) {
    char c = fgetc(fptr);
    if (c == EOF) {
      break;
    }
    ++charToFreq[c];
  }
  fclose(fptr);
  assert(charToFreq[EOT] == 1);

  int k = 0;
  for (int c = 0; c < NCHARS; ++c) {
    if (charToFreq[c] > 0) {
      a[k] = c;
      f[k] = charToFreq[c];
      ++k;
    }
  }
  *n = k;
}

void leesFrequenties(char* filename, char* a, int* f, int* n) {
  FILE* fptr = fopen(filename, "r");
  int k = 0;
  while (1) {
    char c = fgetc(fptr);
    if (c == EOF) {
      break;
    }
    fgetc(fptr); // spatie
    fscanf(fptr, "%d", &f[k]);
    a[k] = c;
    ++k;
    fgetc(fptr); // newline
  }
  fclose(fptr);
  *n = k;
}

int main(int argc, char* argv[]) {
  if (argc != 5) {
    fprintf(stderr, "Verkeerde argumenten: ./a.out [codeer/decodeer] "
                    "inputbestand frequentiebestand outputbestand\n");
    return 1;
  }

  int doeCodeer = strcmp(argv[1], "decodeer");
  char* input = argv[2];
  char* frequentie = argv[3];
  char* output = argv[4];

  char a[NCHARS];
  int f[NCHARS];
  int n = 0;

  Node* root = NULL;

  if (doeCodeer) {
    printf("coderen...\n");

    berekenFrequenties(input, a, f, &n);
    root = hoffmanBoom(a, f, n);
    printBoom(root, 0);
    bewaarFrequenties(frequentie, a, f, n);

    codeer(input, root, output);
  } else {
    printf("decoderen...\n");

    leesFrequenties(frequentie, a, f, &n);
    root = hoffmanBoom(a, f, n);
    printBoom(root, 0);
    decodeer(input, root, output);
  }

  root = destroy(root);

  return 0;
}