1 REM Ins{nd av Kristoffer Eriksson <5357>    1987-12-11 19.56.03 (KERMIT)
; Fil: HFMTREE.ASM till HFM.ASM
; Av: Kristoffer Eriksson, "SKE" <5357>, 1987.
;
;-Ver--/-Datum----/-Sign-/-Kommentar----------------------------------
;      / 87-07-16 / SKE  / HFMTREE
; 1.00 / 87-11-13 / SKE  / Klart.
;
; Inre rutiner i HFM.ASM. Tr{dbyggnad, filkodning, frekvensr{kning.

Iocm.Rdc:   =  5                      ; "GET"
Iocm.Wrc:   =  6                      ; "PUT"
Err.NoExist:=  21
Err.EOFr:   =  38
Err.EOFa:   =  34
Lu.Pos:     =  +6
Lu.Line:    =  +7
Lu.Wid:     =  +8
Y.Int:      =  +35                    ; CTRL-C-flagga.
Int.Ctrc:   =  0

TopMem:     DEFW   0                  ; H|gsta lediga adress i RAM - 1.
TopMem2:    DEFW   0                  ; TopMem - marginal, temp anv{ndning.
PoolP:      DEFW   0                  ; B|rjan av pool-listan.
FreeP:      DEFW   0                  ; B|rjan av ledig-listan.
TreeP:      DEFW   0                  ; Kodtr{dets rot.
Token#:     DEFW   0                  ; Antal m|jliga olika tokens.

Node.Freq:  =  0   ; Antal exemplar av detta token i filen. Tre bytes.
Node.Left:  =  3   ; V{nster tr{dl{nk.
Node.Right: =  5   ; H|ger tr{dl{nk.
Node.Paren: =  7   ; L{nk tillbaks till f|r{ldranoden.
Node.Pool:  =  9   ; L{nk till n{sta nod {nnu ej inl{nkad i tr{det.
NodeSize:   =  11  ; OBS: TokenNode m}ste justeras n{r nodstorleken {ndras.

TokenBuf:   DEFS   253                ; Buffert f|r en sektor.


            EXTERN Freq.Byte, DispFreq, Cmprs.Byte, DeCom.Byte, RemoveUnused
            EXTERN ZeroTriB, ConstructTree, PutTree, PutHead, GetTree, GetHead
            EXTERN InitNodes, Node.Freq, BDoIO

; (Anledningen till att Node.Freq exporteras, {r att den p} en plats i den h{r
; filen adderas till Nodes, som kommer fr}n en annan fil, och kan inte hela
; uttrycket ber{knas h{r, f|rs|ker den ber{kna hela uttrycket senare. AZZAM
; 3.4 kan inte ber{kna en bit h{r och en bit d{r. Det hade jag aldrig t{nkt
; p}.)


;*  Frekvensr{kning f|r token = bin{r byte fr}n fil IX.
;*  In: IX = LU-block f|r infil.
;*  Ut: Vid fel: Carry, A = Felkod fr}n GIO, eller 0 vid CTRL-C-stopp.

Freq.Byte:  LD     BC,256             ; 256 tokens = bin{ra bytes.
            CALL   InitNodes
FB.Loop:    BIT    Int.Ctrc,(IY+Y.Int)
            JR NZ  RetAvbryt
            LD     HL,TokenBuf
            LD     BC,253
            LD     A,Iocm.Rdc
            CALL   GIO
            JR C   Freq.Err
            LD     HL,TokenBuf
            LD     B,253
FB.LoopByte:PUSH   BC
            LD     C,(HL)             ; BC <- Aktuellt tecken.
            LD     B,0
            INC    HL
            PUSH   HL
            CALL   IncFreq
            POP    HL
            POP    BC
            DJNZ   FB.LoopByte
            JR     FB.Loop

RetAvbryt:  XOR    A                  ; CTRL-C-stopp returneras som fel 0.
            SCF
            RET

Freq.Err:   CP     Err.EOFr           ; Felkod 38 och 34 markerar filslut,
            RET Z                     ;  och det {r helt ok. 34 f}r man fr}n
            CP     Err.EOFa           ;  NUL:, |vriga 38.
            RET Z
            SCF                       ; \vriga fel {r verkligen fel.
            RET

IncFreq:    LD     HL,BinFileSize     ; R{kna upp antal tokens i filen.
            CALL   IncTriB
            CALL   TokenNode          ; HL <- Nod f|r token BC.
            ; Forts{tt in i IncTriB   ; R{kna upp frekvensen f|r token BC.

IncTriB:    INC    (HL)               ; \ka trebytes-tal vi HL. S{tt Z-flaggan
            RET NZ                    ; enligt resultatet.
            INC    HL                 ; Minnessiffra (INC (HL) ger ej carry).
            INC    (HL)
            RET NZ
            INC    HL
            INC    (HL)
            RET

ZeroTriB:   XOR    A                  ; Nollst{ll trebytes-tal vid HL.
            LD     (HL),A
            INC    HL
            LD     (HL),A
            INC    HL
            LD     (HL),A
            RET

NegTriB:    LD     B,3                ; Negera trebytes-tal vid HL.
NT.Loop:    LD     A,(HL)             ; N <- 0 - N = (NOT N) + 1.
            CPL    A
            LD     (HL),A
            INC    HL
            DJNZ   NT.Loop
            DEC    HL
            DEC    HL
            DEC    HL
            JR     IncTriB

TestTriB:   LD     A,(HL)             ; Kolla om trebytes-tal {r noll.
            AND    A
            RET NZ
            INC    HL
            LD     A,(HL)
            AND    A
            RET NZ
            INC    HL
            LD     A,(HL)
            AND    A
            RET


; Skriv ut frekvenstabellen till sk{rmen. Anv{nder alternativregister och IX.

DispFreq:   LD     BC,(Token#)
            LD     HL,Nodes+Node.Freq
            LD     IX,(ConsLu)
DF.Loop:    PUSH   BC
            PUSH   HL
            CALL   TestTriB
            JR Z   DF.Next            ; Skriv inte ut noder med frekvens 0.
            PUSH   BC
            LD     A,(IX+Lu.Wid)
            SUB    (IX+Lu.Pos)
            CP     16                 ; Radbyte om n{sta utskrift (16 tkn) inte
            CALL C ConsCR             ; rymms p} raden (t ex vid 40tkns-rader).
            LD     A,(IX+Lu.Line)
            CP     23
            JR C   DF.x1
            LD     A,(IX+Lu.Pos)
            AND    A
            JR NZ  DF.x1
            LD     HL,DigBuf
            LD     BC,1               ; Paus i b|rjan av varje rad, fr.o.m.
            CALL   ConsGet            ; rad 23.
DF.x1:      POP    BC
            LD     HL,(Token#)
            XOR    A                  ; Nolla carry, och undertryck nollor.
            SBC    HL,BC              ; HL <- Token-nummer.
            EX     DE,HL
            LD     C,A                ; CDE <- HL.
            EXX
            LD     HL,DigBuf
            LD     BC,5 << 8 + 10     ; F{ltvidd 5 tkn, Bas 10.
            CALL   TriRegAsc
            LD     (HL),":"           ; HL = N{sta lediga tkn.
            INC    HL
            LD     (HL)," "
            INC    HL
            LD     (HL),0
            LD     HL,DigBuf
            CALL   ConsWriteS
            POP    DE
            PUSH   DE
            LD     HL,DigBuf
            LD     BC,8 << 8 + 10     ; F{ltvidd 8 tkn, Bas 10.
            XOR    A                  ; Undertryck nollor.
            CALL   TriBAsc
            LD     HL,DigBuf
            LD     BC,9
            CALL   ConsWrite          ; "00000000,"
DF.Next:    POP    HL
            LD     BC,NodeSize
            ADD    HL,BC
            POP    BC
            DEC    BC
            LD     A,C
            OR     B
            JR NZ  DF.Loop
            JP     ConsCR             ; Avsluta med radbyte.

DigBuf:     DEFS   8,"0"
            DEFM   ","


;*  L{sning och skrivning av bytes f|r BitIn och BitOut, kombinerat med
;*  uppr{kning av CmpFileSize.

BDoIO:      PUSH   HL
            LD     HL,CmpFileSize
            CALL   IncTriB
            POP    HL
            JP     GIO


;*  Koda infilen enligt kodningstr{det, och skriv ut till utfilen, f|r Token =
;*  bin{r byte. Vid retur signalerar sann carry fel fr}n GIO med felkod i A,
;*  eller om A=0 stopp pga CTRL-C. IX kan anv{ndas f|r att avg|ra i vilken fil
;*  felet intr{ffade.

Cmprs.Byte: BIT    Int.Ctrc,(IY+Y.Int)
            JP NZ  RetAvbryt
            LD     HL,TokenBuf
            LD     BC,253
            LD     IX,LU.In           ; Infil.
            LD     A,Iocm.Rdc
            CALL   GIO
            JP C   Freq.Err
            LD     HL,TokenBuf
            LD     B,253
            LD     IX,LU.Ut           ; Utfil.
CB.LoopByte:PUSH   BC
            LD     C,(HL)             ; BC <- Aktuellt tecken.
            LD     B,0
            INC    HL
            PUSH   HL
            CALL   Cmprs.Token
            POP    HL
            POP    BC
            RET C
            DJNZ   CB.LoopByte
            JR     Cmprs.Byte

; Koda token BC och skriv till utfilen IX.
; Alla register anv{nds IX p}verkas. Vid retur signalerar sann carry fel
; fr}n GIO med felkod i A.

Cmprs.Token:CALL   TokenNode          ; HL <- Node f|r Token BC.
            LD     BC,Node.Paren
CM.Loop1:   PUSH   HL                 ; Stacka nodadresser p} v{gen fr}n
            ADD    HL,BC              ; l|vet till rot-noden.
            LD     A,(HL)
            INC    HL
            LD     H,(HL)
            LD     L,A                ; Fler f|r{ldranoder?
            OR     H
            JR NZ  CM.Loop1
            POP    HL                 ; HL <- Rot-nod.
CM.Loop2:   LD     BC,Node.Left       ; Nysta upp stackade noder fr}n rot-nod
            ADD    HL,BC              ; till l|v, och skriv ut en bittkodning
            LD     A,(HL)             ; f|r v{gen, som utg|r de s|kta koden.
            INC    HL
            OR     (HL)
            RET Z                 ; Avbryt om l|v (inga undernoder), ej carry.
            POP    DE                 ; Undernod.
            LD     A,D                ; Kolla om det var v{nster nod, skriv
            CP     (HL)               ; i s} fall en 0-bitt, annars en 1-bitt.
            JR NZ  CM.One
            DEC    HL
            LD     A,E
            SUB    (HL)               ; SUB s} att A blir noll om lika.
            JR Z   CM.Put
CM.One:     LD     A,255
CM.Put:     CALL   BitOut
            JR C   CM.Err
            EX     DE,HL              ; HL <- Undernod.
            JR     CM.Loop2

CM.End:     AND    A                  ; Ingen carry, inget fel.
            RET

CM.Err:     EX     AF,AF'
            EX     DE,HL
CM.Loop3:   LD     BC,Node.Left       ; Fel fr}n GIO. Forts{tt uppnystningen
            ADD    HL,BC              ; f|r att t|mma stacken, men skriv inget.
            LD     A,(HL)
            INC    HL
            OR     (HL)
            JR Z   CM.ErrEnd          ; Forts{tt tills l|v.
            POP    HL
            JR     CM.Loop3
CM.ErrEnd:  EX     AF,AF'             ; Ta fram felkod och carry igen.
            RET

;*  Avkoda infilen enligt kodningstr{det, och skriv ut till utfilen, f|r
;*  Token = bin{r byte. Vid retur signalerar sann carry fel fr}n GIO med
;*  felkod i A, eller stopp pga CTRL-C om A=0. IX kan anv{ndas f|r att avg|ra
;*  i vilken fil felet intr{ffade.

DeCom.Byte: LD     HL,BinFileSize     ; Det {r s} kr}ngligt att r{kna ned Tri-
            CALL   NegTriB            ; bytes, s} vi negerar och r{knar upp i
            RET Z                     ; st{llet. Ev uppt{cker vi nu att l{ng-
DB.LoopBuf: BIT    Int.Ctrc,(IY+Y.Int); den {r noll, d} {r det klart direkt.
            JP NZ  RetAvbryt
            LD     DE,TokenBuf
            LD     B,253
            LD     IX,LU.In           ; Infil.
DB.LoopByte:PUSH   BC
            PUSH   DE
            CALL   DeCom.Token
            POP    DE
            POP    BC
            RET    C                  ; Avbryt vid fel.
            LD     A,L
            LD     (DE),A             ; Lagra aktuellt tecken.
            INC    DE
            LD     HL,BinFileSize
            CALL   IncTriB
            JR Z   DB.End
            DJNZ   DB.LoopByte
            LD     HL,TokenBuf
            LD     BC,253
            LD     IX,LU.Ut           ; Utfil.
            LD     A,Iocm.Wrc
            CALL   GIO
            RET C
            JR     DB.LoopBuf

DB.End:     LD     A,254
            SUB    B                  ; Ber{kna antal bytes i sista bufferten.
            LD     C,A
            LD     B,0
            LD     HL,TokenBuf
            LD     IX,LU.Ut           ; Utfil.
            LD     A,Iocm.Wrc
            JP     GIO                ; Avslutande utskrift av sista bufferten.


; Avkoda token fr}n infilen IX och returnera i HL.
; Alla register utom IX p}verkas. Vid retur signalerar sann carry fel
; fr}n GIO med felkod i A.

DeCom.Token:LD     HL,(TreeP)         ; B|rja vid tr{dets rot.
DT.Loop:    LD     BC,Node.Left+1
            ADD    HL,BC
            LD     A,(HL)
            AND    A
            JR Z   DT.End             ; Noden har inga barn, allts} {ndnod.
            CALL   BitIn
            RET C
            JR Z   DT.x
            LD     BC,Node.Right-Node.Left
            ADD    HL,BC
DT.x:       LD     A,(HL)             ; HL <- H|ger eller v{nster nod.
            DEC    HL                 ; (HL pekar p} h|ga byten i nodpekaren.)
            LD     L,(HL)
            LD     H,A
            JR     DT.Loop

DT.End:     LD     DE,Nodes           ; (Carry {r redan noll)
            SBC    HL,DE              ; F} fram offset inom nod-tabellen.
            LD     BC,NodeSize
            CALL   IDivZ              ; Dividera med nodstorleken, f|r att
            RET                       ; f} fram nodnumret, som ska returneras.

;*  R{kna ut adressen till noden f|r token BC och returnera i HL.
;*  OBS: Multiplikationen med nodstorleken {r h}rdkodad av effektivitetssk{l!!
;*  F|r{ndrar HL och DE.

TokenNode:  LD     L,C                ; BC = Token.
            LD     H,B
            ADD    HL,HL              ; HL <- Token * 2.
            LD     E,L                ; DE <- HL.
            LD     D,H
            ADD    HL,HL
            ADD    HL,HL              ; HL <- Token * 8.
            ADD    HL,DE              ; HL <- Token * 10.
            ADD    HL,BC              ; HL <- Token * 11 = Token * TokenSize
            LD     DE,Nodes
            ADD    HL,DE              ; HL <- Adress till nod f|r Token.
            RET

;*  Rensa bort oanv{nda token-noder ur poolen.
;*  Borttagna noder g}r f|rlorade f|r alltid. Inga in- och ut-register.

RemoveUnused:LD    DE,PoolP-Node.Pool ; DE pekar p} f|reg}ende nod.
            LD     HL,(PoolP)         ; HL pekar p} n{sta nod.
RU.Loop:    LD     A,H
            OR     L
            RET Z                     ; Slut p} noder - klart.
            PUSH   HL
            PUSH   HL
            POP    IX                 ; IX pekar p} aktuell nod.
            LD     C,(IX+Node.Pool)   ; Avl{s n{sta nod redan nu, eftersom
            LD     B,(IX+Node.Pool+1) ;   den nollst{lls vid ev url{nkning.
            LD     A,(IX+Node.Freq)
            OR     (IX+Node.Freq+1)
            OR     (IX+Node.Freq+2)
            JR NZ  RU.Next
            LD     HL,Node.Pool       ; Nodens frekvens noll, s} ta bort den.
            ADD    HL,DE              ; HL <- F|reg}ende pool-l{nk.
            CALL   UnlinkNode
            POP    HL                 ; G|r inte den nu borttagna noden till
            PUSH   DE                 ; f|reg}ende nod, utan byt.
RU.Next:    POP    DE                 ; Nuvarande nod blir f|reg}ende nod.
            LD     L,C                ; HL <- N{sta nod.
            LD     H,B
            JR     RU.Loop

;*  Leta upp den nod i poolen som har l{gst frekvens, l{nka ur den ur listan,
;*  och returnera dess adress i HL. [r listan tom returneras 0. Finns flera
;*  noder med l{gst frekvens returneras den sista, s} det blir lite "rotation"
;*  p} noderna. Nya noder kommer ju in i b|rjan av listan.
;*  F|r{ndrar HL, DE, BC, A (men inte IX).
;*
;*  Registeranv{ndning internt:
;*  IX = Aktuell nod,
;*  HL = N{sta nod (tillf{lligtvis),
;*  DE = F|reg}ende nod,
;*  BC = Noden f|re den med hittills l{gsta frekvens.

RemoveSmallest:
            LD     HL,(PoolP)
            LD     A,L
            OR     H
            RET Z                     ; Listan {r tom - avbryt (HL {r 0).
            PUSH   IX
            PUSH   HL          ;--,
            PUSH   HL          ;-,!
            POP    IX          ;-'!     Aktuell nod <- F|rsta noden.
            LD     BC,PoolP-Node.Pool ; Noden f|re l{gsta <- Pool-pekaren.
            JR     RS.Lower2          ; B|rja med att anta att f|rsta noden
                                      ; {r den med l{gst frekvens.
RS.Loop:    LD     A,L
            OR     H
            JR Z   RS.End             ; Slut p} noder - avbryt s|kningen.
            PUSH   HL          ;--,
            PUSH   HL          ;-,!
            POP    IX          ;-'!     IX <- Aktuell nod.
            LD     HL,LowestFreq+2    ; J{mf|r nodens frekvens med den hit-
            LD     A,(HL)             ; tills l{gsta. B|rja med den mest
            CP     (IX+Node.Freq+2)   ; signifikanta byten (tredje). [r nodens
            JR C   RS.Next            ; st|rre, s} ta n{sta nod. [r den lika,
            JR NZ  RS.Lower           ; s} kolla n{sta byte. [r den mindre,
            DEC    HL                 ; s} g|r den h{r till hittills l{gsta.
            LD     A,(HL)
            CP     (IX+Node.Freq+1)
            JR C   RS.Next
            JR NZ  RS.Lower
            DEC    HL
            LD     A,(HL)
            CP     (IX+Node.Freq)     ; B}de mindre eller lika godk{nns, f|r
            JR C   RS.Next            ; att hitta den sista om flera {r minst.
RS.Lower:   LD     C,E                ; Spara f|reg}ende nod.
            LD     B,D
RS.Lower2:  LD     HL,LowestFreq
            LD     A,(IX+Node.Freq)   ; Spara den nya l{gsta frekvensen.
            LD     (HL),A
            INC    HL
            LD     A,(IX+Node.Freq+1)
            LD     (HL),A
            INC    HL
            LD     A,(IX+Node.Freq+2)
            LD     (HL),A      ;  !
RS.Next:    POP    DE          ;--'   ; Nuvarande nod blir f|reg}ende nod.
            LD     L,(IX+Node.Pool)   ; HL <- N{sta nod.
            LD     H,(IX+Node.Pool+1)
            JR     RS.Loop

RS.End:     LD     HL,Node.Pool
            ADD    HL,BC              ; HL <- Pool-l{nken till den l{gsta.
            LD     E,(HL)             ; DE <- L{gsta noden.
            INC    HL
            LD     D,(HL)
            DEC    HL                 ; Backa tillbaks HL.
            PUSH   DE
            PUSH   DE
            POP    IX
            CALL   UnlinkNode         ; L{nka ur l{gsta noden.
            POP    HL                 ; Svaret i HL, den l{gsta noden.
            POP    IX                 ; ]terst{ll IX.
            RET

LowestFreq: DEFS   3,255

;*  Ta bort en nod ur fri-listan och returnera den i IX.

NN.Err:     LD     HL,TNodFel
            JP     FelSlut

NewNode:    LD     HL,(FreeP)
            LD     A,L
            OR     H
            JR Z   NN.Err             ; Noderna ska r{cka om programmet
            PUSH   HL                 ; fungerar som det ska.
            POP    IX
            LD     HL,Freep
            ; Forts{tt in i UnlinkNode

;*  L{nka ur nod fr}n pool-listan, och nollst{ll dess pool-l{nk.
;*  In: IX = Nod att l{nka ur,
;*      HL = Adress till pool-l{nken i noden f|re den som ska l{nkas ur.
;*  F|r{ndrar HL, BC och A.

UnlinkNode: LD     A,(IX+Node.Pool)   ; L{nka f|rbi aktuell nod genom att
            LD     (HL),A             ; l}ta f|reg}ende nods pool-l{nk peka
            INC    HL                 ; p} den nod som aktell nod nu pekar p}.
            LD     A,(IX+Node.Pool+1)
            LD     (HL),A
            XOR    A
            LD     (IX+Node.Pool),A   ; Nollst{ll aktuell nods pool-l{nk.
            LD     (IX+Node.Pool+1),A
            RET

;*  HL.Node.Paren <- IX. Inga register {ndras.

SetParen:   PUSH   HL
            EX     (SP),IX
            POP    HL
            LD     (IX+Node.Paren),L
            LD     (IX+Node.Paren+1),H
            PUSH   HL
            EX     (SP),IX
            POP    HL
            RET

;*  Konstruera kod-tr{det av noderna i poolen. Inga in- och ut-register.
;*  HL, DE, BC, IX och A f|r{ndras.

ConstructTree:
            LD     HL,(PoolP)
            LD     A,L
            OR     H
            JR NZ  CT.Loop
            LD     (TreeP),HL         ; Tomt tr{d, nollst{ll pekare. (HL {r 0)
            RET

CT.Loop:    CALL   NewNode            ; IX <- Ny nod.
            CALL   RemoveSmallest     ; HL <- Minsta nod.
            LD     (IX+Node.Left),L
            LD     (IX+Node.Left+1),H
            PUSH   HL
            CALL   RemoveSmallest     ;HL <- En liten nod till (om det finns).
            POP    DE
            LD     A,L
            OR     H
            JR Z   CT.End1
            LD     (IX+Node.Right),L
            LD     (IX+Node.Right+1),H
            CALL   SetParen
            EX     DE,HL
            CALL   SetParen
            LD     A,(DE)             ; Addera ihop de funna nodernas
            ADD    (HL)               ; frekvenser, och placera summan i
            LD     (IX+Node.Freq),A   ; den nya noden.
            INC    DE                 ; H{r utnyttjas p} (DE) och (HL) det
            INC    HL                 ; faktum att Node.Freq = 0.
            LD     A,(DE)
            ADC    (HL)
            LD     (IX+Node.Freq+1),A
            INC    DE
            INC    HL
            LD     A,(DE)
            ADC    (HL)
            LD     (IX+Node.Freq+2),A
            LD     HL,(PoolP)         ; Finns n}gra noder kvar?
            LD     A,L
            OR     H
            JR Z   CT.End
            LD     (IX+Node.Pool),L   ; Placera den nya noden i poolen.
            LD     (IX+Node.Pool+1),H
            LD     (PoolP),IX
            JR     CT.Loop

CT.End:     LD     (TreeP),IX         ; Sista inre noden blir tr{dets rot.
            RET

CT.End1:    LD     (TreeP),DE         ; Finns bara en nod. Den f}r bli rot.
            RET                       ; (Gl|m den p}b|rjade nya noden.)

;*  Skriv ut en kodad form av kodningstr{det till filen IX. Vid retur markerar
;*  sann carry fel fr}n GIO med felkod i A. BitOut m}ste vara initierad.
;*
;*  [r tr{det tomt, skrivs inget alls ut, allts} ska man inte f|rs|ka l{sa in
;*  tr{det igen om fill{ngden {r noll, vilket ska vara den enda orsaken till
;*  ett tomt kodtr{d.
;*  Tr{det kodas med en bitt per nod, plus tokennumret f|r l|vnoderna. Noll
;*  markerar en inre nod, och ett markerar l|v.
;*  Rutinen {r rekursiv (svansrekursiv rent av).

PutTree:    LD     DE,(TreeP)
            LD     A,E
            OR     D
            RET Z
PutTreeRec: EX     DE,HL              ; HL <- Aktuell nod.
            LD     BC,Node.Left
            ADD    HL,BC
            LD     E,(HL)
            INC    HL
            LD     D,(HL)
            LD     A,E                ; Har noden inga barn, {r den en ytter-
            OR     D                  ; nod och markerar ett visst token.
            JR Z   PT.Leaf            ; (Noder har aldrig bara ett barn.)
            XOR    A
            CALL   BitOut
            RET C
            PUSH   HL
            CALL   PutTreeRec         ; V{nster tr{d.
            POP    HL
            RET C
            INC    HL
            LD     E,(HL)             ; Node.Right.
            INC    HL
            LD     D,(HL)
            JP     PutTreeRec         ; H|ger tr{d. (Svansrekursion)

PT.Leaf:    LD     A,255
            CALL   BitOut
            RET C
            LD     DE,Nodes           ; (Carry {r redan noll)
            SBC    HL,DE              ; F} fram offset inom nod-tabellen.
            LD     BC,NodeSize
            CALL   IDivZ              ; Dividera med nodstorleken, f|r att
            LD     B,8                ; f} token-numret.
PT.Loop:    XOR    A                  ; Skifta ut bittarna till utfilen. H{r
            RL     L                  ; har bara programmerats f|r token=byte,
            SBC    A                  ; det {r d{rf|r B laddas f|r 8 bittar.
            PUSH   BC
            CALL   BitOut
            POP    BC
            RET C
            DJNZ   PT.Loop
            RET

;*  L{s in kodningstr{det fr}n filen IX. Ev felkod i A med carry.
;*  Ge (del)tr{dets rot i DE. Node.Paren initieras inte, eftersom den
;*  bara beh|vs n{r tr{det anv{nds f|r kodning, inte avkodning.

GetTree:    LD     HL,BinFileSize     ; [r filstorleken 0, s} {r tr{det tomt
            CALL   TestTriB           ;  och ska inte l{sas in. Det finns
            RET Z                     ;  uttrycklig kodning f|r tomt tr{d.
            CALL   GetTreeRec
            LD     (TreeP),DE
            RET

GetTreeRec: CALL   BitIn
            RET C
            JR NZ  GT.Leaf            ; Etta markerar l|v - {ndpunkt i tr{det.
            PUSH   IX
            CALL   NewNode
            EX     (SP),IX
            POP    HL
            LD     BC,Node.Left
            ADD    HL,BC
            PUSH   HL
            CALL   GetTreeRec         ; V{nster deltr{d.
            POP    HL
            RET C
            LD     (HL),E
            INC    HL
            LD     (HL),D
            INC    HL
            PUSH   HL
            CALL   GetTreeRec         ; H|ger deltr{d.
            POP    HL
            RET C
            LD     (HL),E
            INC    HL
            LD     (HL),D
            LD     BC,Node.Right+1
            SBC    HL,BC              ; Backa till b|rjan av nod. (Ingen carry)
            EX     DE,HL
            RET                       ; (Ingen carry)

GT.Leaf:    LD     B,8
GT.Loop:    PUSH   BC                 ; Skifta in bittarna som anger vilket l|v
            CALL   BitIn              ; detta {r fr}n infilen. H{r har bara
            POP    BC                 ; programmerats f|r token=byte, det {r
            RET C                     ; d{rf|r B laddas f|r 8 bittar.
            RRCA
            RL     L
            DJNZ   GT.Loop
            LD     C,L
            LD     B,0
            CALL   TokenNode          ; Nodadress f|r Token BC -> HL.
            EX     DE,HL
            AND    A                  ; Inget fel - ingen carry.
            RET

;*  Skriv ut filhuvud p} komprimerad fil IX. Filnamn enligt FNamA.In och
;* FNamL.In. Filstorlek enligt BinFileSize.

PutHead:    LD     HL,(FNamA.In)      ; Se till att eventuellt enhetsnamn
            LD     BC,(FNamL.In)      ; i b|rjan av filnamnet utel{mnas.
            LD     A,":"
            CPIR
            JR Z   PH.x
            LD     HL,(FNamA.In)
            LD     BC,(FNamL.In)
PH.x:       PUSH   HL
            PUSH   BC
            LD     A,C
            LD     (HH.Nlen),A        ; Placera namnets l{ngd i huvudet.
            LD     HL,(BinFileSize)   ; Placera filens l{ngd i huvudet.
            LD     (HH.Flen),HL
            LD     A,(BinFileSize+2)
            LD     (HH.Flen+2),A
            LD     A,HH.Len
            ADD    C
            LD     (CmpFileSize),A    ; Initiera komprimerad fill{ngd till
            LD     HL,0               ; huvudets storlek.
            LD     (CmpFileSize+1),HL
            LD     HL,HfmHead         ; Skriv huvudet.
            LD     BC,HH.Len
            LD     A,Iocm.Wrc
            CALL   GIO
            POP    BC
            POP    HL
            RET C
            LD     A,Iocm.Wrc
            JP     GIO                ; Skriv filnamnet (slutet av huvudet).

HfmHead:    DEFW   9967               ; Magiskt nummer.
            DEFB   1, 1, 1, 8         ; Huffmann, Version, Tokenset, -size.
HH.Flen:    DEFB   0, 0, 0            ; Fill{ngd.
            DEFS   4, 0               ; Reserv.
HH.Nlen:    DEFB   0                  ; L{ngd av filnamn.
HH.Len:     =      * - HfmHead

;*  L{s in filhuvudet fr}n komprimerad fil IX, och intiera r{tt antal
;*  tr{dnoder, filstorlekar och filnamn. Filnamn initieras bara om (FNamA.Ut)
;*  {r noll. OBS att filnamnet skrivs |ver n{sta g}ng bufferten anv{nds.
;*  Fel markeras med carry. Fel fr}n GIO ger felkod i A. Fel p} huvudet ger
;*  A=0 och HL pekande p} en feltext.

GetHead:    LD     HL,TokenBuf
            LD     BC,HH.Len
            LD     A,Iocm.Rdc
            CALL   GIO                ; L{s in huvudet.
            RET C
            LD     HL,TokenBuf
            LD     DE,HfmHead
            LD     A,(DE)
            CP     (HL)
            JR NZ  GH.EjHfm
            INC    HL
            INC    DE
            LD     A,(DE)
            CP     (HL)
            JR NZ  GH.EjHfm
            LD     B,4
GH.Loop:    INC    HL
            INC    DE
            LD     A,(DE)
            CP     (HL)
            JR NZ  GH.VerFel
            DJNZ   GH.Loop
            INC    HL
            INC    DE
            PUSH   HL
            LD     BC,256             ; 256 tokens = bin{ra bytes, det enda
            CALL   InitNodes          ; nuvarande version klarar av.
            POP    HL
            LD     DE,BinFileSize     ; Kopiera den opackade filens l{ngd.
            LD     BC,3
            LDIR
            INC    HL                 ; Reservutrymmet i huvudet.
            INC    HL
            INC    HL
            INC    HL
            LD     C,(HL)
            LD     B,0
            INC    HL
            LD     A,(FNamA.Ut+1)
            AND    A                  ; S{tt ej filnamnspekare om den (eller
            JR NZ  GH.x               ; dess h|ga byte) ej {r 0.
            LD     (FNamL.Ut),BC      ; Filnamnets l{ngd.
            LD     (FNamA.Ut),HL      ; Filnamnet.
GH.x:       LD     A,HH.Len
            ADD    C
            LD     (CmpFileSize),A    ; Initiera komprimerad fill{ngd till
            LD     E,B                ; huvudets storlek.
            LD     D,B
            LD     (CmpFileSize+1),DE
            LD     A,Iocm.Rdc
            JP     GIO                ; Avsluta med att l{sa in filnamnet.

GH.EjHfm:   LD     HL,TEjHfm
            JR     GH.Fel
GH.VerFel:  LD     HL,TVerFel
GH.Fel:     XOR    A
            SCF
            RET

;*  Nollst{ll de blivande tr{dnoderna.
;*  In: BC = Antal {ndnoder (l|v) i tr{det = Antal olika tokens. BC>0.
;*  F|rst|r HL, BC, DE, A.
;*
;*  Tv} upps{ttningar noder l{ggs upp, dels BC {ndnoder, och dels lika m}nga
;*  lediga noder som ska anv{ndas till att binda ihop {ndnoderna i en riktigt
;*  tr{dstruktur. B}da upps{ttningarna l{nkas ihop till en lista med
;*  pool-l{nkarna, och lagras i PoolP och FreeP.
;*  Sparar ocks} antalet tokens (BC) i Token#.

InitNodes:  PUSH   IX
            PUSH   BC
            LD     HL,(TopMem)
            LD     BC,NodeSize
            AND    A
            SBC    HL,BC
            LD     (TopMem2),HL       ; Maxadress med marginal f|r en nod.
            POP    BC
            LD     HL,Nodes
            LD     (PoolP),HL         ; Pool-listans startpunkt.
            LD     (Token#),BC        ; Lagra antal tokens.
            DEC    BC                 ; R{kna inte med sista noden.
            PUSH   BC
            CALL   InitList           ; [ndnoder.
            POP    BC
            LD     (FreeP),HL
            CALL   InitList           ; Lediga noder till tr{dets inre.
            POP    IX
            RET

; Nollst{ll och l{nka ihop en lista p} BC+1 noder. HL = Utrymme f|r listan.

InitList:   PUSH   BC
            PUSH   HL
            CALL   ZeroNode
            POP    IX
            LD     (IX+Node.Pool),L   ; L{nka till n{sta nod.
            LD     (IX+Node.Pool+1),H
            POP    BC
            DEC    BC
            LD     A,C
            OR     B
            JR NZ  InitList
            CALL   ZeroNode
            RET

ZeroNode:   LD     BC,(TopMem2)
            PUSH   HL
            AND    A
            SBC    HL,BC
            LD     HL,TMemFel
            JP NC  FelSlut
            POP    HL
            LD     (HL),0             ; Nollst{ll nod HL.
            LD     E,L
            LD     D,H
            INC    DE
            LD     BC,NodeSize
            LDIR
            RET

TNodFel:    DEFM   "Internt fel: Slut p} noder."
            DEFB   13,10,0
TMemFel:    DEFM   "F|r lite minne f|r kodtr{det."
            DEFB   13,10,0
TEjHfm:     DEFM   "Detta {r inte n}gon huffmann-fil."
            DEFB   13,10,0
TVerFel:    DEFM   "Filen {r komprimerad p} ett s{tt denna programversion"
            DEFM   " inte klarar av."
            DEFB   13,10,0
