とりあえず圧縮部分まで書いてみた。

Programming C 圧縮

変換辞書と、データ部分は別ファイルに。

% gcc press.c
% ./a.out bar
% ls -l bar*
-rw-r--r--    1 sun31048 J03A           24 Nov 16 19:09 bar
-rw-r--r--    1 sun31048 J03A           10 Nov 16 19:10 bar.code
-rw-r--r--    1 sun31048 J03A            4 Nov 16 19:10 bar.data
% cat bar
aaaaaaaabbbbbbbbaaaaaaaa% cat bar.code
61 1
62 0
% hexdump -b bar.data
0000000 377 000 377 000
0000004
% echo -n a >> bar
% ./a.out bar
% ls -l bar*
-rw-r--r--    1 sun31048 J03A           25 Nov 16 19:27 bar
-rw-r--r--    1 sun31048 J03A           10 Nov 16 19:27 bar.code
-rw-r--r--    1 sun31048 J03A            5 Nov 16 19:27 bar.data
% hexdump -b bar.data
0000000 377 000 377 001 001
% ./a.out press.c
% ls -l press.c*
-rw-r--r--    1 sun31048 J03A         3868 Nov 16 19:29 press.c
-rw-r--r--    1 sun31048 J03A          853 Nov 16 19:33 press.c.code
-rw-r--r--    1 sun31048 J03A         2432 Nov 16 19:33 press.c.data

うん、なんだか圧縮できてるっぽいかな？ .dataの最後の1バイトだけはフッタみたいなもの。最後から数えて2バイト目のデータは下位何ビットが有効データか、ということを記録している。barがちゃんと圧縮できてるのはわかるけど、press.cがちゃんと圧縮できてるかは、そのデータを伸張して元データを得られるかやってみないとわからんな。
まだ伸張部分書いてないけど。
つーか変換表（.code)の形式をもうちょい考えれば小さくなるな。とりあえず伸張部分書いてからにするけど。
以下プログラムソース。

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

#define HCODEMAX 256

typedef struct{
  unsigned char c;
  int count;
} item;
struct node{
  item data;
  struct node *lbranch, *rbranch;
};

struct node** isort(struct node *table[], int length){
  int i, j;
  struct node *tmp;
  for(i=1;i<length;++i){
    for(j=i;j>0 && table[j-1]->data.count>table[j]->data.count;--j){
      tmp = table[j-1];
      table[j-1] = table[j];
      table[j] = tmp;
    }
  }
  return table;
}
struct node* mknode(item data, struct node *lbranch, struct node *rbranch){
  struct node *n;
  n = (struct node *)malloc(sizeof(struct node));
  n->data = data;
  n->lbranch = lbranch;
  n->rbranch = rbranch;
  return n;
}
struct node* mktree(struct node *table[], int length){
  struct node *top_node;
  item tmp;

  if(length == 1) return table[0];
  
  tmp.count = table[0]->data.count + table[1]->data.count;
  
  table[1] = mknode(tmp, table[0], table[1]);
  
  isort(&table[1], length-1);
  top_node = mktree(&table[1], length-1);

  return top_node;
}
int print_htable(FILE *fh, char *htable[256]){
  int i;

  for(i=0;i<256;++i)
    if(htable[i] != NULL) fprintf(fh, "%02x %s\n", i, htable[i]);

  return 1;
}
int mkhtable(char *htable[256], struct node *top_node, char *precode){
  char lcode[HCODEMAX], rcode[HCODEMAX];
  strcpy(lcode, precode);
  strcpy(rcode, precode);

  if(top_node->lbranch != NULL)
    mkhtable(htable, top_node->lbranch, strcat(lcode, "0"));
  if(top_node->rbranch != NULL)
    mkhtable(htable, top_node->rbranch, strcat(rcode, "1"));
  if(top_node->lbranch == NULL && top_node->rbranch == NULL){
    htable[top_node->data.c] = (char *)malloc(sizeof(char)*HCODEMAX);
    strcpy(htable[top_node->data.c], precode);
  }

  return 1;
}
unsigned int hcode2uint(char *hcode){
  unsigned int u, i;
  u = 0;
  while(*hcode != '\0'){
    u = (u << 1) + *hcode - '0';
    ++hcode;
  }
  return u;
}
int putc_archive(int c, char *htable[256], FILE *arch){
  static int length = 0;
  static unsigned int archdata = 0;
  unsigned char unit;
  if(c != EOF){
    archdata = (archdata << strlen(htable[c])) + hcode2uint(htable[c]);
    length += strlen(htable[c]);
    while(length >= 8){
      length -= 8;
      unit = archdata >> length;
      fputc(unit, arch);
      archdata = archdata ^ (unit << length);
    }
  } else {
    if(length != 0){
      fputc(archdata, arch);
    }
    fputc(length, arch);
  }
  return 1;
}
int write_archive(FILE *arch, FILE *plain, char *htable[256]){
  int c;
  while((c = fgetc(plain)) != EOF) putc_archive(c, htable, arch);
  putc_archive(EOF, htable, arch);
  return 1;
}
int compress(char *plainname){
  char archname[256], codename[256];
  int c, i, j, length;
  FILE *plain, *arch, *code;
  struct node *table[256], *top_node;
  item tmpitem;
  char *htable[256];

  length = 256;
  strcpy(archname, plainname);
  strcat(archname, ".data");
  strcpy(codename, plainname);
  strcat(codename, ".code");

  if((plain = fopen(plainname, "r")) == NULL){
    perror("cannot open plain");
    return -1;
  }
  if((arch = fopen(archname, "w")) == NULL){
    perror("cannot open arch");
    return -1;
  }
  if((code = fopen(codename, "w")) == NULL){
    perror("cannot open tree");
    return -1;
  }

  for(i=0;i<length;++i){
    tmpitem.count = 0;
    tmpitem.c = i;
    table[i] = mknode(tmpitem, NULL, NULL);
  }
  while((i=fgetc(plain)) != EOF) ++table[i]->data.count;

  isort(table, length);
  for(i=0;table[i]->data.count == 0;++i);
  top_node = mktree(&table[i], length-i);

  for(i=0;i<256;++i) htable[i] = NULL;
  mkhtable(htable, top_node, "");
  print_htable(code, htable);

  fseek(plain, 0, SEEK_SET);

  write_archive(arch, plain, htable);

  fclose(plain);
  fclose(code);
  fclose(arch);
  return 1;
}
int main(int argc, char *argv[]){
  if(argc>1)
    if(!compress(argv[argc-1]))
      puts("cannot compress");
  return 0;
}

例外処理っていうのかな？ そういうのを全然していないような気がする。
プログラミングってやつは、自由度が高くて困ってしまいますね。僕を走らせたいのならレールを敷いてください。なっちゃおうぜ、社会の歯車に。

test