/*

Ein Beispiel einer Lauflaengenkodierung von Texten.

Siehe auch:
http://www.ogobin.org/home/algorithms/huffman.php

Die folgende Schleife kann benutzt werden, um eine
Text-Datei direkt nach *fin einzulesen und nach
*fout zu schreiben:

  #define BUFFERSIZE     8*256
  char buf[BUFFERSIZE];
  FILE *fout, *fin;

  [...]

  while(!feof(fin))  {
    n = fread(&buf, 1, BUFFERSIZE, fin);
    p = txtZip(buf, n);
    fwrite(p, 1, strlen(p), fout);
  }

  Von Oliver Gobin <og@ogobin.org> schnell
  in die Tasten gehackt.

*/

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

char *txtZip(char *p, int len) {
  char *s;
  int i = 0; // i Zaehler fuer den ersten String
  int k = 0; // k Zaehler fuer den ersten String
             // k ist somit die neue Laenge des
             // Strings. Um (k - len) wurde der
             // String komprimiert
  int a = 0; // Zaehler fuer gleiche Zeichen
  s = (char *) malloc(len);
  for(i = 0; i < len; i++) {
    // Wenn zwei benachbarte Zeichen gleich sind,
    // erhoehe a
    if(p[i] == p[i+1])
      a++;
    else {
      // keine Komprimierung moeglich daher
      // setze das Zeichen in den neuen String
      // und erhoehe seinen Zaehler um eins
      if(a == 0) {
      	s[k] = p[i];
        k += 1;
      }
      else {
        // Komprimierung moeglich:
        // Kodierung: Marker: '2', Anzahl: 'a', Zeichen: 'p[i]'
        // nur 8bit, daher umplappen nach 255...
        do {
          if(a >= 255) {
            s[k] = 2;
            s[k+1] = 255;
          }
          // zwei Ausnahmen:
          else if(a == 1) {
            s[k] = p[i];
            s[k+1] = p[i];
            k += 2;
            break;
          }
          else if(a == 2) {
            s[k] = p[i];
            s[k+1] = p[i];
          }
          else {
            s[k] = 2;
            s[k+1] = a+1;
          }
      	  s[k+2]=p[i];
          k += 3;
          a -= 255;
        }
        while(a >= 0);
      }
      a=0;
    }
  }
  s[k] = '\0';
  return s;
}

char *txtdeZip(char *s, int len) {
  char *p;
  int i = 0, a = 0, k = 0, newlen = 0;
  // berechne die Laenge des dekomprimierten Strings:
  for(i = 0; i < len; i++) {
    if(s[i] == 2)
      newlen += s[i+1];
    else
      newlen += 1;
  }

  p = (char *) malloc(newlen);

  for(i = 0; i < len; i++) {
    if(s[i] == 2) {
      for(a = 0; a < s[i+1]; a++) {
        p[k] = s[i+2];
        k++;
      }
      i += 2;
    }
    else {
      p[k] = s[i];
      k++;
    }
  }
  p[k] = '\0';
  return p;
}

int main(void) {
  char *p = "ssssssssssssdddddddd jajaja Hallo Welt....";
  char *s;
  int i;
  FILE *fout;

  s = txtZip(p, strlen(p));

  // File-Output:
  if((fout = fopen("c:\\out.file", "wb")) == NULL) {
    printf("Could not open out.file for writing");
    getch();
    return(1);
  }
  fprintf (fout, "%s", s);
  fclose(fout);

  // Bildschirm-Output:
  printf("%d bytes gespart!\nKomprimierter String im Hex-Code:\n", (strlen(p) - strlen(s)));
  for(i = 0; i < strlen(s); i++)
    printf("%X ", s[i]);

  // Dekomprimierung:
  p = txtdeZip(s, strlen(s));
  printf("\n\nDekodierte Eingabe:\n%s", p);

  return(0);
}