Compression Using the Splay-tree technique

Compress and decompress files using the "splay tree" technique. Based on the article by Douglas W. Jones, Application of Splay Trees to Data Compression in Communications of the ACM, August 1988.

Usage:
SPLAYIT (no filenames or parameters)
SPLAYIT simply compresses a predefined file to a predefined file and then uncompresses back to another predefined file. You can change the filenames in the code or add a command-line parser.

**Caution**
This routine has NO error checking. It is given to show how to program a splay tree compression routine. You can simple add error checking by testing each file read buffer and file write buffer routines as well as the open and close file routines.


SPLAY.ASM Copyright 1984-2015
by Forever Young Software
Benjamin David Lunt
Version 1.02
09 Dec 1998
Assembled with: NBASM

Comment |=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  Compress and decompress files using the "splay tree" technique.
  Based on the article by Douglas W. Jones, "Application of Splay Trees to
  Data Compression" in Communications of the ACM, August 1988.

  Usage:
    SPLAYIT     (no filenames or parameters)

  SPLAYIT simply compresses a predefined file to a predefined file and then
  uncompresses back to another predefined file.  You can change the filenames
  in the code or add a command-line parser.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=|

.model tiny
.186
.code
           org  100h

           mov  dx,offset CompStr       ; ** compress file
           mov  ah,09
           int  21h
           mov  dx,offset InName
           call OpenSFile
           mov  dx,offset OutName
           call OpenTFile
           call InitSplay
           call CompFile
           mov  bx,Handle1
           call CloseFile
           mov  bx,Handle2
           call CloseFile               ; ** done compress file


           mov  dx,offset ExpndStr      ; ** expand file
           mov  ah,09
           int  21h
           mov  dx,offset OutName
           call OpenSFile
           mov  dx,offset OrgName
           call OpenTFile
           call InitSplay
           call ExpndFile
           mov  bx,Handle1
           call CloseFile
           mov  bx,Handle2
           call CloseFile               ; ** done expand file

           mov  ax,4C00h
           int  21h

InitSplay  proc near

           ; nbasm does not support the local directive (yet)
           ;local I:word,K:word,J:byte

           jmp  short ISkipLocal
I          dw 00h
J          dw 00h
K          dw 00h
ISkipLocal:

           mov  cx,512
           xor  ax,ax
           mov  di,offset Up
           stosb
           inc  ax
UpLoop:    push ax
           dec  ax
           shr  ax,1
           stosb
           pop  ax
           inc  ax
           loop UpLoop

           mov  cx,256
           xor  ax,ax
           mov  si,offset Left
           mov  di,offset Right
LRLoop:    push ax
           inc  ax
           shl  ax,1
           stosw
           dec  ax
           mov  [si],ax
           inc  si
           inc  si
           pop  ax
           inc  ax
           loop LRLoop
           ret
InitSplay  endp

OpenSFile  proc near
           mov  ax,3D00h                ; open RO file
           int  21h                     ;
           mov  Handle1,ax
           ret
OpenSFile  endp

OpenTFile  proc near
           mov  ah,5Bh                  ; create new file
           xor  ch,ch                   ; normal file
           mov  cl,00100000b            ;
           int  21h                     ;
           mov  Handle2,ax
           ret
OpenTFile  endp

CloseFile  proc near
           mov  ah,3Eh                  ; Close File
           int  21h                     ;
           ret
CloseFile  endp

SPlay      proc near uses ax bx         ; uses passed ax
           
           ; nbasm does not support the local directive (yet)
           ;local A:word,B:word,C:byte,D:byte

           jmp  short SSkipLocal
A          dw 00h
B          dw 00h
C          dw 00h
D          dw 00h
SSkipLocal:

           add  ax,256                  ; A = Plain + 256;
           mov  A,ax                    ;
                                        ;
SLoop:     mov  bx,offset Up            ; C = Up[A]
           add  bx,ax                   ;
           mov  al,[bx]                 ;
           mov  C,al                    ;

           or   al,al                   ; if C <> Root then begin
           jnz  NotSElse
           jmp  SElse                   ;
NotSElse:  mov  bx,offset Up            ; D = Up[C]
           xor  ah,ah                   ;
           add  bx,ax                   ;
           mov  al,[bx]                 ;
           mov  D,al                    ;

           mov  bx,offset Left          ; B = Left[D]
           xor  ah,ah                   ;
           shl  ax,1                    ; double for word
           add  bx,ax                   ;
           mov  ax,[bx]                 ;
           mov  B,ax                    ;

           mov  al,C                    ; if C = B then begin
           xor  ah,ah                   ;
           cmp  ax,B                    ;
           jne  short NotCBE            ;
           mov  bx,offset Right         ; B = Right[D]
           mov  al,D                    ;
           xor  ah,ah                   ;
           shl  ax,1                    ; double for word
           add  bx,ax                   ;
           mov  ax,[bx]                 ;
           mov  B,ax                    ;
           mov  ax,A                    ; Right[D] = A
           mov  [bx],ax                 ;
           jmp  short NextIf            ;
NotCBE:    mov  al,D                    ; Left[D] = A
           xor  ah,ah                   ;
           shl  ax,1                    ; double for word
           mov  bx,offset Left          ;
           add  bx,ax                   ;
           mov  ax,A                    ;
           mov  [bx],ax                 ;
NextIf:    mov  al,C                    ; if A = Left[C] then
           xor  ah,ah                   ;
           shl  ax,1                    ; double for word
           mov  bx,offset Left          ;
           add  bx,ax                   ;
           mov  ax,[bx]                 ;
           cmp  ax,A                    ;
           jne  short RCEB              ;
           mov  ax,B                    ; Left[C] = B
           mov  [bx],ax                 ;
           jmp  short DoUps             ;
RCEB:      mov  al,C                    ; Right[C] = B
           xor  ah,ah                   ;
           shl  ax,1                    ; double for word
           mov  bx,offset Right         ;
           add  bx,ax                   ;
           mov  ax,B                    ;
           mov  [bx],ax                 ;
DoUps:     mov  ax,A                    ; Up[A] = D
           mov  bx,offset UP            ;
           add  bx,ax                   ;
           mov  al,D                    ;
           mov  [bx],al                 ;
           mov  ax,B                    ; Up[B] = C
           mov  bx,offset UP            ;
           add  bx,ax                   ;
           mov  al,C                    ;
           mov  [bx],al                 ;
           mov  al,D                    ; A = D
SElse:     xor  ah,ah                   ; A = C
           mov  A,ax                    ;
           or   ax,ax                   ; until A = Root   (see next comment)
           jz   short SPlayRet
           jmp  SLoop                   ;     (A=ax)(faster to test ax then A)
SPlayRet:  ret
SPlay      endp

FOBuffer   proc near uses ax bx cx dx

           cmp  word OutSize,00h        ; if OutSize > 0 then begin
           je   short DFO               ;
           mov  ah,40h                  ; write to file
           mov  bx,Handle2
           mov  cx,OutSize
           mov  dx,offset BufferOut
           int  21h
           mov  word OutSize,00h
DFO:       ret
FOBuffer   endp

WriteByte  proc near uses ax bx

           cmp  word OutSize,16384           ; if OutSize = 16384 then
           jb   short NoFLO
           call FOBuffer                ; FlushOutBuffer
NoFLO:     mov  bx,offset BufferOut     ; OutBuffer[OutSize] = OutByte
           add  bx,OutSize              ;
           mov  al,OutByte              ;
           mov  [bx],al                 ;
           inc  word OutSize            ; inc OutSize
           ret
WriteByte  endp

Compress   proc near uses cx si di      ; uses passed ax
           
           ; nbasm does not support the local directive (yet)
           ;local PSDAX:word,A1:word,U:byte

           jmp  short CSkipLocal
PSDAX      dw 00h
A1         dw 00h
U          dw 00h
CSkipLocal:

           mov  PSDAX,ax                ; A1 = Plain + 256
           add  ax,256                  ;
           mov  A1,ax                   ;

           push ax                      ; save A1
           mov  di,offset Stck          ; our stack
           mov  al,0FFh                 ; bottom of stack flag
           stosb                        ;
           pop  ax                      ; restore A1
                                        ; repeat
RCLoop:    mov  bx,offset Up            ; U = Up[A1]
           add  bx,ax                   ;
           mov  al,[bx]                 ;
           mov  U,al                    ;

           mov  bx,offset Right         ; Stack[Sp] = (Right[U] = A1)
           xor  ah,ah                   ;
           shl  ax,1                    ; double for word
           add  bx,ax                   ;
           mov  ax,[bx]                 ;
           cmp  ax,A1                   ;
           jne  short NotTrue           ;
           mov  al,01h                  ; TRUE
           jmp  short IsTrue            ;
NotTrue:   xor  al,al                   ; FALSE
IsTrue:    stosb                        ; save on stack
           mov  al,U                    ; A1 = U
           xor  ah,ah                   ;
           mov  A1,ax                   ;
           or   ax,ax                   ; until A1 = Root
           jnz  short RCLoop            ;

UnStack:   dec  di                      ; if Stack[Sp] then
           mov  al,[di]                 ;
           cmp  al,0FFh
           je   short DoneStck
           cmp  al,01h                  ; TRUE
           jne  short NotOrIt           ;
           mov  bl,OutByte              ;
           or   bl,OrIt                 ;
           mov  OutByte,bl              ;
NotOrIt:   cmp  byte OrIt,10000000b
           jne  short NotPos7
           call WriteByte               ;
           mov  byte OutByte,00h        ;
NotPos7:   rol  byte OrIt,1
           jmp  short UnStack           ; go to the next one
DoneStck:  mov  ax,PSDAX
           call SPlay                   ; Splay(Plain)
           ret
Compress   endp

CompFile   proc near
           mov  byte OrIt,00000001b
DoIt:      mov  ah,3Fh                  ; BlockRead.....
           mov  cx,16384                ;
           mov  bx,Handle1              ;
           mov  dx,offset BufferIn      ;
           int  21h                     ;
           or   ax,ax                   ; if none read finish up
           jz   short NoMore            ;
           push ax                      ;
           mov  cx,ax                   ; Index = 1 to InSize
           mov  si,offset BufferIn      ;
DoFor:     lodsb                        ;
           xor  ah,ah                   ;
           call Compress                ; Compress(InBuffer[index])
           loop DoFor                   ;
           pop  ax                      ;
           cmp  ax,16384                ; until InSize < 16384
           je   short DoIt              ;

NoMore:    mov  ax,256                  ; Compress(EofChar)
           call Compress                ;
           cmp  byte OrIt,00000001b          ; if BitPos <> 0 then
           je   short FlushIt
           call WriteByte
FlushIt:   call FOBuffer
           ret
CompFile   endp


;; **  now begins the expansion part  ** ;;
GetByte    proc near uses bx cx dx

           inc  word Index
           mov  ax,Index
           cmp  ax,InSize
           jb   short GetIt
           mov  ah,3Fh                  ; BlockRead.....
           mov  cx,16384                ;
           mov  bx,Handle1              ;
           mov  dx,offset BufferIn      ;
           int  21h                     ;
           mov  InSize,ax
           mov  word Index,00h
GetIt:     mov  bx,offset BufferIn
           add  bx,Index
           mov  al,[bx]
           ret
GetByte    endp

Expand     proc near uses bx 

           xor  dx,dx                   ; A = Root;
ExLoop:    cmp  byte OrIt,10000000b
           jne  short ENot07
           call GetByte                 ; returns in al
           mov  InByte,al
ENot07:    rol  byte OrIt,1
           mov  al,InByte
           and  al,OrIt
           or   al,al
           jnz  short NBitEZ
           mov  bx,offset Left          ; A = left[A]
           jmp  short DoUntA
NBitEZ:    mov  bx,offset Right         ; A = right[A]
DoUntA:    mov  ax,dx
           shl  ax,1
           add  bx,ax
           mov  ax,[bx]
           mov  dx,ax                   ; A
           cmp  ax,255                  ; until A > PredMax
           jbe  short ExLoop

           sub  ax,256
           call Splay
ReadErr:   ret
Expand     endp

ExpndFile  proc near uses ax bx cx dx

           mov  byte OrIt,10000000b
EoCLoop:   call Expand                  ; returns in ax
           cmp  ax,256
           je   short XEndIt
           mov  OutByte,al
           call WriteByte
           jmp  short EoCLoop
XEndIt:    call FOBuffer
           ret
ExpndFile  endp

Handle1    dw  00h        ; handle for source file
Handle2    dw  00h        ; handle for target file
OutByte    db  00h        ; the byte to write
InByte     db  00h        ; the byte read
OrIt       db  00h        ; AND var
InSize     dw  00h        ; len of data in source buffer (amount read in)
Index      dw  00h        ; location to put next byte in buffer
OutSize    dw  00h        ; len of data in target buffer (amount to write)
InName     db  'name.org',0   ; *** filename to use here (source)(orig. file)
OutName    db  'name.spl',0   ; ***  and here  (compressed file)(splayed)
OrgName    db  'name.uns',0   ; ***  and here  (uncompressed file)(unsplayed)
CompStr    db  13,10,'Compressing...$'
ExpndStr   db  13,10,'Expanding...$'

Stck       dup 256,?
Left       dup 512,?
Right      dup 512,?
Up         dup 514,?  ; (2 extra for safety)
BufferIn   dup 16384,?
BufferOut  dup 16390,?
.end