| /************************************************
* LZH Version 1.0 vom 22.08.91 * * Autor: Joerg Gurowski * * Alle Rechte beim * * DMV-Verlag Red.CPC International * * Komprimierprogramm nach dem * * Huffman-Coding-Verfahren * ************************************************/ #include iolib.h #include args.h #define EOF -1 #define MAXL 1040 #define MAXTBL 2304 int help,*blow,*bhigh,*anz,trpos,*fpi,*fpo,cbit, *stat1,*stat2,contr; char *bits,byte,iname[16],oname[16]; main() é char i[2]; /*Uebergabe der Argumente*/ setargs(); if(getarg(1,i,2)==EOF) noarg(); if(getarg(2,iname,16)==EOF) noarg(); if(getarg(3,oname,16)==EOF) noarg(); /*Auswahl der Programme*/ if(upper(i[0])=='C') cod(); else if(upper(i[0])=='D') decod(); elseé print("Falsche option angegeben!"); noarg(); è è /*Textausgabe*/ print(text) char *text; é int i; char c; i=0; while((c=text[i++])!=0) putchar(c); putchar('çn'); è /*Ausgabe des Fehlertextes fuer fehlende Argumente*/ noarg() é print("Komprimieren : lzh c Quelle Ziel"); print("Dekomprimieren: lzh d Quelle Ziel"); exit(0); è noidat() é print("Quelldatei nicht vorhanden!"); exit(0); è /*Statistische Ermittlung der Haeufigkeit eines Zeichens und Anlegen einer Tabelle nach der Haeufigkeit des Auftretens*/ stat() é int b,c,cc,ind,max; char h; /*Speicher fuer zwei Felder resevieren*/ stat1=alloc(512); stat2=alloc(512); c=0; /*Setzen aller Werte der Felder auf Null*/ while(c!=256) stat1[c++]=stat2[c]=0; /*Ermittlung der Haeufigkeit eines Zeichens*/ while((b=getb(fpi))!=EOF) stat1[b]++; /*Anlegen einer Charactertabelle nach der Haeufigkeit eines Zeichens*/ c=cc=0; while(c!=256)é max=stat1[cc]; ind=0; while(++cc!=256) if(max<stat1[cc])é max=stat1[cc]; ind=cc; è; stat2[c++]=ind; stat1[ind]=cc=0; è c=0; /*Erstellung der Kodiertabelle*/ while(c!=256)é /*Ausgabe der Charactertabelle in die Datei*/ putb(stat2[c],fpo); ind=stat2[c]; stat1[ind]=c++; è /*Freigabe des nicht mehr benoetigten Speichers*/ free(stat2); è /*Entkomprimierroutine*/ decod() é int b; char h; /*Oeffnen der Dateien*/ if((fpi=fopen(iname,"r"))==0) noidat(); fpo=fopen(oname,"w"); print("Anlegen des Huffman-Trees"); mktree(); print("Dekodieren"); /*Decodieren mittels Huffman-Tree*/ trpos=cbit=contr=0; while(1==1)é /*Wenn Bitzaehler(cbit)=0 naechstes Byte hohlen */ if(cbit==0)é if((h=b=getb(fpi))==EOF) break; /*Nach hohlen von 1kB "." ausgeben*/ if(contr++ ==1024)é putchar('.'); contr=0; è è /* if(b==EOF) break;*/ /*Wenn Zeichen gefunden - Ausgabe in die Datei*/ if(decsearch(&h)==1)é byte=bhigh[trpos]; putb(byte,fpo); trpos=0; è è fclose(fpi); fclose(fpo); è /*Komprimierroutine*/ cod() é int b,c; /*Oeffnen der Dateien*/ if((fpi=fopen(iname,"r"))==0) noidat(); fpo=fopen(oname,"w"); print("Statistik"); stat(); /*Ruecksetzen der Eingabedatei*/ fclose(fpi); fpi=fopen(iname,"r"); print("Anlegen der Kodier-Tabelle"); /*Anlegen der Tabelle mit den Bitmustern*/ mktable(); print("Komprimieren"); /*Komprimieren*/ cbit=contr=0; while((b=getb(fpi))!=EOF)é /*Dem Zeichen entsprechendes Byte aus der Kodiertabelle hohlen*/ c=stat1[b]; /*Dem Zeichen entsprechendes Bitmuster suchen und in Datei schreiben*/ codsearch(c); è fclose(fpi); fclose(fpo); è /*Suchen des Bitmusters fuer jedes Zeichen und dieses in ein Byte schieben, wenn dieses vollstaendig ist, Ausgabe in eine Datei*/ codsearch(b) int b; é int c,max; char buff[9]; /*Arbeitspuffer*/ max=anz[b]; mbits(&bits[b*9],buff); c=0; /*Zaehlung der Bits fuer die Bitkombination eines Zeichens*/ while(c++ !=max)é shftb(buff,&byte); /*Wenn ein Byte vollstaendig ist - Ausgabe in die Datei*/ if(cbit++ ==7)é /*Ausgabe eines Punktes fuer jeweils 1kB*/ if(contr++ ==1024)é putchar('.'); contr=0; è putb(byte,fpo); cbit=0; è è è /*Durchsuchen des Huffmantrees*/ decsearch(byte) char *byte; é while(cbit++!=8)é/*Zaehler fuer 8Bit = 1Byte*/ if(shr(byte)==1) trpos=bhigh[trpos]; else trpos=blow[trpos]; if(blow[trpos]==0) é return 1; /*Zeichen gefunden*/ è è cbit=0; return 0;/*Zeichen nicht gefunden*/ è /*Erstellung des Huffman-Trees zur Dekomprimierung*/ mktree() é int p,c,b; char *tabl; blow=alloc(MAXL);/*Feld fuer 0-Richtung*/ bhigh=alloc(MAXL);/*Feld fuer 1-Richtung*/ tabl=alloc(256);/*Feld fuer Charactertabelle*/ c=0; /*Einlesen der Charactertabelle*/ while(c!=256) tabl[c++]=getb(fpi); c=p=b=0; /*Erstellung der Wurzel*/ while(c!=14)é blow[p]=++c; bhigh[p++]=++c; è /*Erstellung des Baumes*/ while(b!=256)é blow[p]=0; /*Zuweisung der Werte fuer die Blaetter*/ bhigh[p++]=tabl[b++]; blow[p]=++c; bhigh[p++]=++c; è è /*Erstellung der Tabelle zur Zuweisung der Bitfolgen*/ mktable() é int c,o[4],x,xanz,ind; char buff[9]; bits=alloc(MAXTBL+1);/*Feld fuer Bitfolgen*/ anz=alloc(512);/*Feld fuer Bitbreiten*/ c=0; while(c!=MAXTBL+1)/* Loeschen*/ bits[c++]=0; /*Anfangswerte der Tabelle, jede Bitfolge hat eine Laenge von 9 Byte*/ bits[0]=0; bits[9]=2; bits[18]=4; bits[27]=6; anz[0]=anz[1]=anz[2]=anz[3]=3; c=4; x=0; xanz=4; /*Anfangswerte fuer den Feldindex*/ o[0]=0; o[1]=9; o[2]=18; o[3]=27; while(c!=256)é ind=c*9; /*9 Byte Bitfolge*/ /*Kopie der vorhergehenden Bitfolge an die neue Position*/ mbits(&bits[o[x]],&bits[ind]); /*Erstellung der Bitlaenge*/ anz[c++]=xanz; /*Index merken*/ o[x++]=ind; if(x==4)é /* 4 Bitfolgen mit gleicher Laenge */ x=0; xanz++; è /*Erstellun der neuen Bitfolge*/ bits[ind]=bits[ind]+1;/*letztes Bit setzen*/ shft(&bits[ind]);/*Linksverschiebung 1Bit*/ è x=0; /*Bitmuster wenden, d.h. Byte 1 wird zu Byte 8*/ while(x!=256)é ind=9*x; mbits(&bits[ind],buff); c=0; while(c!=9)é bits[ind+c]=buff[8-c++]; è c=0; /*Vornullen bis auf die zum Bitmuster gehoerigen entfernen*/ xanz=72-anz[x++]; while(c++ !=xanz) shftl(&bits[ind]); è è /*Kopie eines Bitfeldes(=9 Byte) von s nach d*/ mbits(s,d) char *s,*d; é int c; c=0; while(c!=9) d[c]=s[c++]; è /*Assemblerroutinen*/ #asm ;Linksverschiebung des Bytes auf der Adresse adr ;um ein Bit - return 1 wenn das aus dem Byte ;geschobene Bit gleich eins ist ;shr(adr) ;char *adr; QSHR: OR A ;CY=0 SLA (HL) JR C,MSHR LD HL,0 ;return 0 RET MSHR: LD HL,1 ;return 1 RET ;9 Byte werden um ein Bit verschoben, ;beginnend auf adr1, ueberlaufende Bits werden ;in das naechste Byte geschoben, das am Ende ;ueberlaufende Bit wird nach adr2 geschoben ;shftb(adr1,adr2) ;char *adr1,adr2 qshftb: ;Uebergabe der Argumente POP BC POP DE POP HL PUSH HL PUSH DE PUSH BC LD BC,8 ADD HL,BC LD B,9 OR A PUSH AF LSHFTB: POP AF RL (HL) PUSH AF DEC HL DJNZ LSHFTB POP AF LD A,(DE) RLA LD (DE),A RET ;9 Byte werden um je 1 Bit verschoben, begonnen ;wird mit 9.Byte, ansonsten wie unten ;shftl(adr) ;char *adr qshftl: POP BC POP HL PUSH HL PUSH BC LD BC,8 ADD HL,BC LD B,9 OR A PUSH AF LSHFTL: POP AF RL (HL) PUSH AF DEC HL DJNZ LSHFTL POP AF RET ;shft(adr) ;char *adr; qshft: ;Uebergabe der Argumente POP BC POP HL PUSH HL PUSH BC ;9 Byte muessen um je 1 Bit verschoben werden, ; ein uebergelaufenes Bit wird in das naechste ; Byte geschoben, begonnen wird mit dem 1.Byte LD B,9 OR A PUSH AF LSHFT: POP AF RL (HL) ;CY-Flag retten PUSH AF INC HL DJNZ LSHFT POP AF RET #endasm |