1 REM Ins{nd av Kristoffer Eriksson <5357> 1987-11-14 03.09.15 (DUMP) HFM.INF +-------------------------------------------------------------+ ! HFM.BAC Ver 1.00 - Huffmann-komprimering av filer. ! ! F|r ABC800-serien. ! ! Av Kristoffer Eriksson <5357>, November 1987. ! ! F}r kopieras fritt, dock endast f|r icke-kommersiellt bruk. ! +-------------------------------------------------------------+ 1. Nyttan av HFM. 2. Hur HFM startas och k|rs. 2.1 Parametrar p} kommandoraden. 2.2 Interaktiv k|rning. 2.3 Frekvenstabell 3. M|jliga filer. 4. Effektivitet. 5. Teknisk beskrivning. Filformat. 1. Nyttan av HFM. ------------------ HFM.BAC {r ett program som krymper filer. Det l{ser av en angiven fils inneh}ll, konstruerar en s} effektiv kodning av filens tecken som m|jligt med Huffmann-teknik, och |vers{tter sen filens inneh}ll till denna kod, s} man f}r en ny fil med samma inneh}ll men som tar mindre utrymme att lagra p} disketten, eller tar kortare tid att |verf|ra per modem. F|r att kunna anv{nda den komprimerade filen, m}ste den dekomprimeras, dvs |vers{ttas tillbaks till vanliga tecken, eller vad filen nu inneh|ll fr}n b|rjan, igen. I komprimerat tillst}nd {r filen oanv{ndbar, enda nyttan med att ha den komprimerad {r just att den d} tar mindre plats n{r den inte beh|vs. Dekomprimeringen {r ocks} en uppgift f|r programmet HFM. F|r att konstruera Huffmann-kodningen av en fil, m}ste HFM g} igenom filen och r{kna hur ofta olika tecken anv{nds. De oftast anv{nda tecknen f}r korta koder, medan de ovanligaste tecknen f}r l}nga koder. Normalt har annars alla tecken lika l}nga koder, n{mligen en byte = }tta bits, vilket inte {r s} effektivt, {ven om det {r praktiskt n{r man arbetar med filen. HFM kan f}s att skriva ut resultatet av sin frekvensr{kning, utan att n|dv{ndigtvis komprimera filen samtidigt. HFM {r skriven helt i assembler, som kompilerats till en form som kan startas p} samma s{tt som vanliga Basic-program. Det finns en f|reg}ngare till HFM, skriven i Basic, som heter HUFFMANN.BAS. HFM och HUFFMANN f|rst}r varandras komprimerade filer. HFM {r mycket snabbare {n HUFFMANN, men g|r i |vrigt precis samma saker. Alla slags filer kan komprimeras av HFM, b}de text- och bin{r-filer. 2. Hur HFM startas och k|rs. ----------------------------- Det finns tv} s{tt att k|ra HFM. 1) Man anger allt HFM beh|ver veta direkt p} samma rad som man startar HFM med, typ "RUN HFM,K FOO" som f}r HFM att komprimera filen FOO 2) Man bara startar HFM med "RUN HFM" och besvarar de fr}gor programmet d} st{ller. Det g}r {ven bra att starta HFM via CHAIN i st{llet f|r RUN. N{r HFM v{l arbetar kan det avbrytas med CTRL-C. CTRL-C kontrolleras under frekvensr{kningsfasen, kodningsfasen och avkodningsfasen. 2.1 Parametrar p} kommandoraden. --------------------------------- Anger man alla indata direkt p} kommandoraden, s} {r det f|ljande syntax som g{ller: RUN HFM,Optioner Infil ( = Utfil) ... (; N{staprogram) Det som {r skrivet inom parentes beh|ver inte n|dv{ndigtvis anges. Den enklast formen {r allts} bara: RUN HFM,Optioner Infil "Optioner" best}r av en eller tv} bokst{ver som anger exakt vad HFM ska g|ra med den eller de filer som anges p} resten av raden. De optioner som finns {r: K = Komprimera fil D = Dekomprimera fil F = Visa frekvenstabell f|r alla teckenkoder i fil Optionen F kan anv{ndas samtidigt med K, om man vill b}de komprimera en fil och se frekvenstabellen. Det {r till}tet att skriva ett bindestreck f|re optionerna, om man skulle tycka det ser snyggt ut. Det f}r inte f|rekomma blanktecken mellan K och F om de anv{nds tillsammans. "Infil" {r namnet p} den fil som ska behandlas p} det s{tt optionerna anger. Mer {n en infil kan anges. Alla infiler genomg}r samma behandling individuellt i tur och ordning, s}vida inget fel uppst}r. Vid komprimering skapar HFM en ny fil med det komprimerade inneh}llet fr}n infilen. Den nya filen f}r samma namn som infilen, utom extensionen som blir ".HFM". Om infilen heter FOO.BAR s} blir utfilen FOO.HFM. Infilen tas INTE bort automatiskt efter komprimeringen. Vill man inte ha den kvar f}r man ta bort den manuellt med Basic-kommandot KILL eller UNSAVE. Vid dekomprimering skapar HFM ocks} en ny fil, den h{r g}ngen med det dekomprimerade inneh}llet fr}n infilen, som f|rst}s m}ste inneh}lla resultatet av en tidigare komprimering. Om den angivna filen inte {r komprimerad, eller {r komprimerad med n}gon senare sl{kting till HFM, avbryts behandlingen med ett meddelande om detta. Den nya filen kommer att ha identiskt inneh}ll med den ursprungliga filen som en g}ng komprimerades (f|rutsatt att allting fungerar f|rst}s). Den nya filens namn kommer ocks} att vara detsamma som den ursprungliga filens. Om extensionen p} infilen {r HFM, vilket den borde vara efter att ha komprimerats av HFM, beh|ver den inte anges. FOO.HFM kan allts} anges som bara FOO. Om n}got annat namn {n det normala |nskas p} den fil som skapas av HFM, kan detta ocks} anges p} kommandoraden. Skriv ett likhetstecken (=) efter infi- lens namn, och sen det |nskade namnet p} utfilen. Det m}ste vara blanktec- ken mellan filnamnen och likhetstecknet. Anges enhet p} infilen men inte p} utfilen, placeras utfilen p} samma enhet som infilen. Anges ingen extension p} utfilen vid komprimering, blir den automatiskt ".HFM". Alla filnamn }tskiljs av blanktecken eller kommatecken. Det {r till}tet att s{tta citationstecken (") eller apostrofer (') runt enskilda filnamn. Om det redan finns en fil med samma namn som utfilen, kommer HFM att fr}ga om denna f}r skrivas |ver. Svarar man nej, avbryts hela behandlingen. Till sist g}r det att ange namnet p} n}got program som ska startas efter att HFM slutf|rt sin uppgift. Det anges efter semikolon (;) sist p} raden. Programmet startas om HFM inte stoppas p} grund av n}got fel under k|rningen. Det finns {ven m|jlighet att med programmet ST[LLPAR, permanent st{lla in en fil som HFM kommer att starta efter k|rning. 2.2 Interaktiv k|rning. ------------------------ Vill man l}ta programmet fr}ga sig fram, {r det bara att starta det med kommandot RUN HFM HFM b|rjar d} med att fr}ga vad som ska g|ras, komprimering, dekomprimering eller frekvensr{kning. Den fr}gan kan besvaras med K, D, F, eller KF, p} samma s{tt som optionerna som beskrevs ovan. Sedan fr}gar HFM vilken fil som ska behandlas, och behandlingen s{tter ig}ng. Det g}r att ange flera infiler och utfilernas namn p} samma s{tt som p} kommandoraden, som beskrevs i stycke 2.1. [ven vid interaktiv k|rning g}r det att p} kommandoraden ange ett program som ska startas efter att HFM avslutats: RUN HFM,;N{staprogram f|rutom att det lika g{rna kan anges sist p} fr}gan om infil. 2.3 Frekvenstabell ------------------- Optionen F f}r HFM att presentera en frekvenstabell p} sk{rmen. Tabellen visar f|r varje teckenkod hur m}nga g}nger den f|rekommer i filen. Koder som inte f|rekommer alls visas inte. Optionen kan kombineras med komprimering om s} |nskas. Frekvensr{kningen {r en biprodukt av komprimeringen. Tabellen visas endast p} sk{rmen. Den kan i denna version inte styras om till n}gon fil. Om n}gon utfil anges (och det inte g{ller komprimering), struntar HFM i den. Tabellen visas en rad i taget, s} mycket som f}r plats med aktuell radl{ngd. N{r utskriften n}tt till underkanten av sk{rmen m}ste raderna stegas fram med valfri tangent. 3. M|jliga filer. ------------------ I princip HFM behandla filer fr}n vilken k{lla som helst. HFM kommer inte att protestera om det instrueras att komprimera en fil fr}n CON:, NUL:, V24: eller liknande. Men de flesta av dessa skulle st{lla till problem. NUL: g}r bra, men ger f|rst}s en tom fil vid dekomprimering. CON: och V24: har inget s{tt att tala om f|r HFM n{r ska anses vara slut. Dessutom l{ser HFM 253 tecken i taget, vilket g|r att det inte ens med CTRL-C kan stoppas annat {n vid vart 253:e tecken. Till detta kommer att HFM vid komprimering m}ste l{sa filen tv} g}nger, en g}ng f|r frekvensr{kningen och en g}ng f|r kodningen, vilket inte fungerar n}got vidare p} filen som inte kan backas. Detta skulle kunna l|sas i senare versioner av HFM. Dekomprimering till CON:, V24: eller PR: kan verka anv{ndbart, men om det g{ller en textfil, f}r man t{nka p} att filen har komprimerats s} som den ursprungligen s}g ut p} skiv-mediet, inklusive styrtecken f|r sektorbyte och utan LF (radframmatningstecken) mellan raderna, vilket f}r utskriften att bli ganska oanv{ndbar. Detta skulle ocks} kunna l|sas i senare versioner av HFM. Meddelanden fr}n HFM p} sk{rmen skrivs via filnummer 0, inte via system- anropet CONWRITE som annars {r vanligt i maskinkodsprogram. Detta b|r g|ra att HFM fungerar i remote-k|rning och liknande. 4. Effektivitet. ----------------- Hur mycket en fil minskar i storlek av komprimeringen beror p} hur m}nga olika tecken som anv{nds i filen, och deras relativa frekvenser. En fil som inneh}ller alla 256 koder en byte kan }stadkomma, och allihop lika vanligt f|rekommande, kommer inte att krympa ett enda dugg, utan i st{llet bli lite st|rra pga den extra information om kodningen som m}ste l{ggas till. En fil som anv{nder 128 av de 256 koderna, dvs h{lften av alla m|jliga, men alla koder lika vanligt f|rekommande, kommer att krympas till 7 bits per tecken i st{llet f|r de 8 som finns i originalet. Det kr{vs ju bara 7 bits f|r att f} 128 olika m|jliga koder. Detta ger en minskning med en }ttondel av filens l{ngd (en }ttondel av varje byte f|rsvinner). P} samma s{tt minskar antalet bits per tecken ju f{rre tecken som anv{nds. I extremfallet d{r filen bara inneh}ller en enda sorts tecken, beh|vs noll bits per tecken f|r att koda dessa. Eftersom det bara finns ett tecken att v{lja p}, beh|vs ingen information f|rutom detta faktum, f|r att koda alla exemplar i filen av detta tecken. OBS: Detta {r ett fall programmet HUFFMANN inte klarar av, utan bara HFM. En fil d{r olika tecken f|rekommer olika ofta, vilket torde vara normalfallet, kommer att f} olika l}nga koder f|r de olika tecknen. De tecken som f|rekommer oftast f}r korta koder, eftersom det l|nar sig b{st. Ovanliga tecken f}r i geng{ld l}nga koder. N{r det g{ller textfiler, s} anv{nder dessa bara ca 100 av 256 m|jliga tecken. Det betyder att {ven ett program med fast kodtabell kan komprimera bort ungef{r en sj{ttedel (1/(1-log(100)/log(256))) av den ursprungliga storleken fr}n en s}dan fil, vilket {r en minskning med 17%. HFM ger ofta en minskning n}gonstanns mellan 20 och 35 procent p} textfiler. Eftersom bin{rfiler anv{nder fler av de m|jliga tecknen, har HFM s{mre effekt p} dem {n p} textfiler. Observera att p} diskett m{ts filernas l{ngd i hela sektorer, s} om en fil minskar med bara n{stan en sektor, har man i praktiken inte tj{nat n}got alls. 5. Teknisk beskrivning. ------------------------ Programmet kr{ver n{stan 4200 bytes f|r programkoden och 5700 bytes f|r ett datastruktur som beskriver Huffmann-koden f|r den fil som behandlas. Den komprimerade filen, den s.k. Huffmann-filen, best}r av ett huvud med lite data om filen, ett kodningstr{d som beskriver den kod som anv{nts f|r just denna fil, och sist den komprimerade originalfilen. Huvudet ser ut som f|ljer: Pos L{ngd Inneh}ll --- ------ -------- 0 2 Talet 9967 som identifierar detta som en {kta komprimerad fil. 2 1 Talet 1 som talar om att filen {r kodad med just Huffmannkod. 3 1 Talet 1 vilket {r versionen av filformatet. 4 1 Talet 8 vilket {r antalet bits i de tokens som koden utg}tt ifr}n. Det {r nu helt enkelt vanliga bytes. 5 3 Originalfilens storlek i bytes. Minst signifikant byte i talet f|rst. 8 4 Reservutrymme. Inneh}ller noll. 12 1 L{ngd p} filens namn. 13 - Filens namn, med angiven l{ngd. Efter huvudet kommer kodningstr{det. Med hj{lp av kodningstr{det kan resten av filen avkodas. Tr{det best}r av noder: inre noder och {ndnoder (vanligen kallade l|v). Varje inre nod har tv} dotternoder. Vid avkodning b|rjar man vid tr{dets rot, och l{ser en bitt fr}n den kodade filen. [r bitten en nolla g}r man vidare till v{nster dotternod, och {r det en etta g}r man till h|ger dotternod. Visar det sig att den nya noden {r en {ndnod, s} finns d{r angivet vilket token den representerar i originalfilen. Detta token skrivs ut p} utfilen och man b|rjar om vid tr{dets rot f|r att avkoda n{sta token. Var det d{remot inte en {ndnod, forts{tter man med n{sta bitt. Tr{det sj{lvt {r kodat efter en vandring genom det fr}n roten, via v{nster dotternod, till n{sta h|gra nod osv. F|r varje nod som inte {r en {ndnod st}r det en noll-bitt i tr{dets kodade form. N{r man kommer till en {ndnod st}r det en ett-bitt, f|ljd av {ndnodens token med det antal bits som anges i filens huvud, i denna version av HFM alltid }tta. Sedan b|rjar det hela om med f|reg}ende nods h|gra dotternod, och osv tills man {r tillbaks vid roten. Endast vandring mot {ndnoderna {r representerad i kodningen, vandring tillbaks mot roten {r implicit. Efter kodningstr{det f|ljer direkt det kodade inneh}llet fr}n original- filen, som kan avkodas enligt ovan. \verg}ngen fr}n tr{det till inneh}llet kan ske mitt inne i en byte. K{llkoden finns delvis i filen HFM.ASM. D{r finns ocks} h{nvisningar till |vriga k{llkodsfiler, och en hel del id`er till f|rb{ttringar av programmet. /Kristoffer Eriksson, ABC-klubben <5357>