[Back to DATATYPE SWAG index] [Back to Main SWAG index] [Original]

    Unit LZSSUnit;
    {
       LZSSUNIT - Compress and uncompress unit using LZ77 algorithm for
       Borland (Turbo) Pascal version 7.0.

       Assembler Programmer: Andy Tam, Pascal Conversion: Douglas Webb,
       Unit Conversion and Dynamic Memory Allocation: Andrew Eigus.

       Public Domain version 1.02, last changed on 30.11.94.
       Target platforms: DOS, DPMI, Windows.

       Written by Andrew Eigus (aka: Mr. Byte) of:
       Fidonet: 2:5100/33,
       Internet: aeigus@fgate.castle.riga.lv, aeigus@kristin.cclu.lv.
    }

    interface

    {#Z+}
    { This unit is ready for use with Dj. Murdoch's ScanHelp utility which
      will make a Borland .TPH file for it. }
    {#Z-}

    const
      LZRWBufSize     = 8192; { Read buffer size }

    {#Z+}
      N           = 4096;  { Bigger N -> Better compression on big files only. }
      F           = 18;
      Threshold   = 2;
      Nul         = N * 2;
      InBufPtr    : word = LZRWBufSize;
      InBufSize   : word = LZRWBufSize;
      OutBufPtr   : word = 0;
    {#Z-}

    type
    {#X TWriteProc}{#X LZSquash}{#X LZUnsquash}

      TReadProc = function(var ReadBuf; var NumRead : word) : word;
      { This is declaration for custom read function. It should read
        #LZRWBufSize# bytes from ReadBuf. The return value is ignored. }

    {#X TReadProc}{#X LZSquash}{#X LZUnsquash}
      TWriteProc = function(var WriteBuf; Count : word; var NumWritten : word) :
    word;  { This is declaration for custom write function. It should write
        Count bytes into WriteBuf and return number of actual bytes written
        into NumWritten variable. The return value is ignored. }

    {#Z+}
      PLZRWBuffer = ^TLZRWBuffer;
      TLZRWBuffer = array[0..LZRWBufSize - 1] of Byte; { file buffers }

      PLZTextBuf = ^TLZTextBuf;
      TLZTextBuf = array[0..N + F - 2] of Byte;

      PLeftMomTree = ^TLeftMomTree;
      TLeftMomTree = array[0..N] of Word;
      PRightTree = ^TRightTree;
      TRightTree = array[0..N + 256] of Word;

    const
      LZSSMemRequired = SizeOf(TLZRWBuffer) * 2 +
        SizeOf(TLZTextBuf) + SizeOf(TLeftMomTree) * 2 + SizeOf(TRightTree);
    {#Z-}

    function LZInit : boolean;
    { This function should be called before any other compression routines
      from this unit - it allocates memory and initializes all internal
      variables required by compression procedures. If allocation fails,
      LZInit returns False, this means that there isn't enough memory for
      compression or decompression process. It returns True if initialization
      was successful. }
    {#X LZDone}{#X LZSquash}{#X LZUnsquash}

    procedure LZSquash(ReadProc : TReadProc; WriteProc : TWriteProc);
    { This procedure is used for compression. ReadProc specifies custom
      read function that reads data, and WriteProc specifies custom write
      function that writes compressed data. }
    {#X LZUnsquash}{#X LZInit}{#X LZDone}

    procedure LZUnSquash(ReadProc : TReadProc; WriteProc : TWriteProc);
    { This procedure is used for decompression. ReadProc specifies custom
      read function that reads compressed data, and WriteProc specifies
      custom write function that writes decompressed data. }
    {#X LZSquash}{#X LZInit}{#X LZDone}

    procedure LZDone;
    { This procedure should be called after you finished compression or
      decompression. It deallocates (frees) all memory allocated by LZInit.
      Note: You should always call LZDone after you finished using compression
      routines from this unit. }
    {#X LZInit}{#X LZSquash}{#X LZUnsquash}

    implementation

    var
      Height, MatchPos, MatchLen, LastLen : word;
      TextBufP : PLZTextBuf;
      LeftP, MomP : PLeftMomTree;
      RightP : PRightTree;
      CodeBuf : array[0..16] of Byte;
      LZReadProc : TReadProc;
      LZWriteProc : TWriteProc;
      InBufP, OutBufP : PLZRWBuffer;
      Bytes : word;
      Initialized : boolean;

    Function LZSS_Read : word;    { Returns # of bytes read }
    Begin
      LZReadProc(InBufP^, Bytes);
      LZSS_Read := Bytes;
    End; { LZSS_Read }

    Function LZSS_Write : word;  { Returns # of bytes written }
    Begin
      LZWriteProc(OutBufP^, OutBufPtr, Bytes);
      LZSS_Write := Bytes
    End; { LZSS_Write }

    Procedure Getc; assembler;
    Asm
    {
      getc : return a character from the buffer
              RETURN : AL = input char
                       Carry set when EOF
    }
                  push    bx
                  mov     bx, inBufPtr
                  cmp     bx, inBufSize
                  jb      @getc1
                  push    cx
                  push    dx
                  push    di
                  push    si
                  call    LZSS_Read
                  pop     si
                  pop     di
                  pop     dx
                  pop     cx
                  mov     inBufSize, ax
                  or      ax, ax
                  jz      @getc2               { ; EOF }
                  xor     bx, bx
      @getc1:
                  PUSH    DI
                  LES     DI,[InBufP]
                  MOV     AL,BYTE PTR [ES:DI+BX]
                  POP     DI
                  inc     bx
                  mov     inBufPtr, bx
                  pop     bx
                  clc                         { ; clear the carry flag }
                  jmp     @end
      @getc2:     pop     bx
                  stc                         { ; set carry to indicate EOF }
      @end:
    End; { Getc }

    Procedure Putc; assembler;
    {
      putc : put a character into the output buffer
                 Entry : AL = output char
    }
    Asm
                  push    bx
                  mov     bx, outBufPtr
                  PUSH    DI
                  LES     DI,[OutBufP]
                  MOV     BYTE PTR [ES:DI+BX],AL
                  POP     DI
                  inc     bx
                  cmp     bx, LZRWBufSize
                  jb      @putc1
                  mov     OutBufPtr,LZRWBufSize   { Just so the flush will work. }
                  push    cx
                  push    dx
                  push    di
                  push    si
                  call    LZSS_Write
                  pop     si
                  pop     di
                  pop     dx
                  pop     cx
                  xor     bx, bx
      @putc1:     mov     outBufPtr, bx
                  pop     bx
    End; { Putc }

    Procedure InitTree; assembler;
    {
      initTree : initialize all binary search trees.  There are 256 BST's, one
                 for all strings started with a particular character.  The
                 parent is tree K is the node N + K + 1 and it has only a
                 right child
    }
    Asm
          cld
          push    ds
          pop     es
          LES     DI,[RightP]
    {      mov     di,offset right}
          add     di, (N + 1) * 2
          mov     cx, 256
          mov     ax, NUL
          rep     stosw
          LES     DI,[MomP]
    {      mov     di, offset mom}
          mov     cx, N
          rep     stosw
    End; { InitTree }

    Procedure Splay; assembler;
    {
      splay : use splay tree operations to move the node to the 'top' of
               tree.  Note that it will not actual become the root of the tree
               because the root of each tree is a special node.  Instead, it
               will become the right child of this special node.

                 ENTRY : di = the node to be rotated
    }
    Asm
      @Splay1:
                  PUSH    BX
                  LES     BX,[MomP]
                  MOV     SI,[ES:BX+DI]
                  POP     BX
    {              mov     si, [Offset Mom + di]}
                  cmp     si, NUL           { ; exit if its parent is a special
    node }              ja      @Splay4
                  PUSH    DI
                  LES     DI,[MomP]
                  ADD     DI,SI
                  MOV     BX,[ES:DI]
    {              mov     bx, [Offset Mom + si]}
                  POP     DI
                  cmp     bx, NUL           { ; check if its grandparent is special
    }              jbe     @Splay5           { ; if not then skip }
                  PUSH    BX
                  LES     BX,[LeftP]
                  CMP     DI,[ES:BX+SI]
                  POP     BX
    {              cmp     di, [Offset Left + si]} { ; is the current node is a
    left child ? }              jne     @Splay2
                  PUSH    BX
                  LES     BX,[RightP]
                  MOV     DX,[ES:BX+DI]
    {              mov     dx, [Offset Right + di]}    { ; perform a left zig
    operation }              LES     BX,[LeftP]
                  MOV     [ES:BX+SI],DX
    {              mov     [Offset Left + si], dx}
                  LES     BX,[RightP]
                  MOV     [ES:BX+DI],SI
                  POP     BX
    {              mov     [Offset Right + di], si}
                  jmp     @Splay3
      @Splay2:
                  PUSH    BX
                  LES     BX,[LeftP]
                  MOV     DX,[ES:BX+DI]
    {              mov     dx, [Offset Left + di]}     { ; perform a right zig }
                  LES     BX,[RightP]
                  MOV     [ES:BX+SI],DX
    {              mov     [Offset Right + si], dx}
                  LES     BX,[LeftP]
                  MOV     [ES:BX+DI],SI
                  POP     BX
    {              mov     [Offset Left + di], si}
      @Splay3:
                  PUSH    SI
                  LES     SI,[RightP]
                  MOV     [ES:SI+BX],DI
                  POP     SI
    {              mov     [Offset Right + bx], di}
                  xchg    bx, dx
                  PUSH    AX
                  MOV     AX,BX
                  LES     BX,[MomP]
                  ADD     BX,AX
                  MOV     [ES:BX],SI
                  LES     BX,[MomP]
                  MOV     [ES:BX+SI],DI
                  LES     BX,[MomP]
                  MOV     [ES:BX+DI],DX
                  MOV     BX,AX
                  POP     AX
    {              mov     [Offset Mom + bx], si
                  mov     [Offset Mom + si], di
                  mov     [Offset Mom + di], dx}
      @Splay4:    jmp     @end
      @Splay5:
                  PUSH    DI
                  LES     DI,[MomP]
                  MOV     CX,[ES:DI+BX]
                  POP     DI
    {              mov     cx, [Offset Mom + bx]}
                  PUSH    BX
                  LES     BX,[LeftP]
                  CMP     DI,[ES:BX+SI]
                  POP     BX
    {              cmp     di, [Offset Left + si]}
                  jne     @Splay7
                  PUSH    DI
                  LES     DI,[LeftP]
                  CMP     SI,[ES:DI+BX]
                  POP     DI
    {              cmp     si, [Offset Left + bx]}
                  jne     @Splay6
                  PUSH    AX
                  MOV     AX,DI
                  LES     DI,[RightP]
                  ADD     DI,SI
                  MOV     DX,[ES:DI]
    {              mov     dx, [Offset Right + si]   } { ; perform a left zig-zig
    operation }              LES     DI,[LeftP]
                  MOV     [ES:DI+BX],DX
    {              mov     [Offset Left + bx], dx}
                  xchg    bx, dx
                  LES     DI,[MomP]
                  MOV     [ES:DI+BX],DX
    {              mov     [Offset Mom + bx], dx}
                  LES     DI,[RightP]
                  ADD     DI,AX
                  MOV     BX,[ES:DI]
    {              mov     bx, [Offset Right + di]}
                  LES     DI,[LeftP]
                  ADD     DI,SI
                  MOV     [ES:DI],BX
                  LES     DI,[MomP]
                  MOV     [ES:DI+BX],SI
    {              mov     [Offset Left +si], bx
                  mov     [Offset Mom + bx], si}
                  mov     bx, dx
                  LES     DI,[RightP]
                  ADD     DI,SI
                  MOV     [ES:DI],BX
                  LES     DI,[RightP]
                  ADD     DI,AX
                  MOV     [ES:DI],SI
    {              mov     [Offset Right + si], bx
                  mov     [Offset Right + di], si}
                  LES     DI,[MomP]
                  MOV     [ES:DI+BX],SI
                  LES     DI,[MomP]
                  ADD     DI,SI
                  STOSW
                  MOV     DI,AX
                  POP     AX
    {              mov     [Offset Mom + bx], si
                  mov     [Offset Mom + si], di}
                  jmp     @Splay9
      @Splay6:
                  PUSH    AX
                  MOV     AX,SI
                  LES     SI,[LeftP]
                  ADD     SI,DI
                  MOV     DX,[ES:SI]
    {              mov     dx, [Offset Left + di]}     { ; perform a left zig-zag
    operation }              LES     SI,[RightP]
                  MOV     [ES:SI+BX],DX
    {              mov     [Offset Right + bx], dx}
                  xchg    bx, dx
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],DX
    {              mov     [Offset Mom + bx], dx}
                  LES     SI,[RightP]
                  ADD     SI,DI
                  MOV     BX,[ES:SI]
    {              mov     bx, [Offset Right + di]}
                  LES     SI,[LeftP]
                  ADD     SI,AX
                  MOV     [ES:SI],BX
    {              mov     [Offset Left + si], bx}
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],AX
    {              mov     [Offset Mom + bx], si}
                  mov     bx, dx
                  LES     SI,[LeftP]
                  ADD     SI,DI
                  MOV     [ES:SI],BX
    {              mov     [Offset Left + di], bx}
                  LES     SI,[RightP]
                  ADD     SI,DI
                  MOV     [ES:SI],AX
    {              mov     [Offset Right + di], si}
                  LES     SI,[MomP]
                  ADD     SI,AX
                  MOV     [ES:SI],DI
    {              mov     [Offset Mom + si], di}
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],DI
                  MOV     SI,AX
                  POP     AX
    {              mov     [Offset Mom + bx], di}
                  jmp     @Splay9
      @Splay7:
                  PUSH    DI
                  LES     DI,[RightP]
                  CMP     SI,[ES:DI+BX]
                  POP     DI
    {              cmp     si, [Offset Right + bx]}
                  jne     @Splay8
                  PUSH    AX
                  MOV     AX,SI
                  LES     SI,[LeftP]
                  ADD     SI,AX
                  MOV     DX,[ES:SI]
    {              mov     dx, [Offset Left + si]}     { ; perform a right zig-zig
    }              LES     SI,[RightP]
                  MOV     [ES:SI+BX],DX
    {              mov     [Offset Right + bx], dx}
                  xchg    bx, dx
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],DX
    {              mov     [Offset Mom + bx], dx}
                  LES     SI,[LeftP]
                  ADD     SI,DI
                  MOV     BX,[ES:SI]
    {              mov     bx, [Offset Left + di]}
                  LES     SI,[RightP]
                  ADD     SI,AX
                  MOV     [ES:SI],BX
    {              mov     [Offset Right + si], bx}
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],AX
    {              mov     [Offset Mom + bx], si}
                  mov     bx, dx
                  LES     SI,[LeftP]
                  ADD     SI,AX
                  MOV     [ES:SI],BX
    {              mov     [Offset Left + si], bx}
                  LES     SI,[LeftP]
                  ADD     SI,DI
                  MOV     [ES:SI],AX
    {              mov     [Offset Left + di], si}
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],AX
    {              mov     [Offset Mom + bx], si}
                  LES     SI,[MomP]
                  ADD     SI,AX
                  MOV     [ES:SI],DI
    {              mov     [Offset Mom + si], di}
                  MOV     SI,AX
                  POP     AX
                  jmp     @Splay9
      @Splay8:
                  PUSH    AX
                  MOV     AX,SI
                  LES     SI,[RightP]
                  ADD     SI,DI
                  MOV     DX,[ES:SI]
    {              mov     dx, [Offset Right + di]}    { ; perform a right zig-zag
    }              LES     SI,[LeftP]
                  MOV     [ES:SI+BX],DX
    {              mov     [Offset Left + bx], dx}
                  xchg    bx, dx
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],DX
    {              mov     [Offset Mom + bx], dx}
                  LES     SI,[LeftP]
                  ADD     SI,DI
                  MOV     BX,[ES:SI]
    {              mov     bx, [Offset Left + di]}
                  LES     SI,[RightP]
                  ADD     SI,AX
                  MOV     [ES:SI],BX
    {              mov     [Offset Right + si], bx}
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],AX
    {              mov     [Offset Mom + bx], si}
                  mov     bx, dx
                  LES     SI,[RightP]
                  ADD     SI,DI
                  MOV     [ES:SI],BX
    {              mov     [Offset Right + di], bx}
                  LES     SI,[LeftP]
                  ADD     SI,DI
                  MOV     [ES:SI],AX
    {              mov     [Offset Left + di], si}
                  LES     SI,[MomP]
                  ADD     SI,AX
                  MOV     [ES:SI],DI
                  LES     SI,[MomP]
                  MOV     [ES:SI+BX],DI
    {              mov     [Offset Mom + si], di
                  mov     [Offset Mom + bx], di}
                  MOV     SI,AX
                  POP     AX
      @Splay9:    mov     si, cx
                  cmp     si, NUL
                  ja      @Splay10
                  PUSH    DI
                  LES     DI,[LeftP]
                  ADD     DI,SI
                  CMP     BX,[ES:DI]
                  POP     DI
    {              cmp     bx, [Offset Left + si]}
                  jne     @Splay10
                  PUSH    BX
                  LES     BX,[LeftP]
                  MOV     [ES:BX+SI],DI
                  POP     BX
    {              mov     [Offset Left + si], di}
                  jmp     @Splay11
      @Splay10:
                  PUSH    BX
                  LES     BX,[RightP]
                  MOV     [ES:BX+SI],DI
                  POP     BX
    {              mov     [Offset Right + si], di}
      @Splay11:
                  PUSH    BX
                  LES     BX,[MomP]
                  MOV     [ES:BX+DI],SI
                  POP     BX
    {              mov     [Offset Mom + di], si}
                  jmp     @Splay1
      @end:
    End; { SPlay }

    Procedure InsertNode; assembler;
    {
      insertNode : insert the new node to the corresponding tree.  Note that the
                   position of a string in the buffer also served as the node
                   number.
                 ENTRY : di = position in the buffer
    }
    Asm
                  push    si
                  push    dx
                  push    cx
                  push    bx
                  mov     dx, 1
                  xor     ax, ax
                  mov     matchLen, ax
                  mov     height, ax
                  LES     SI,[TextBufP]
                  ADD     SI,DI
                  MOV     AL,BYTE PTR [ES:SI]
    {             mov     al, byte ptr [Offset TextBuf + di]}
                  shl     di, 1
                  add     ax, N + 1
                  shl     ax, 1
                  mov     si, ax
                  mov     ax, NUL
                  PUSH    BX
                  LES     BX,[RightP]
                  MOV     WORD PTR [ES:BX+DI],AX
    {              mov     word ptr [Offset Right + di], ax}
                  LES     BX,[LeftP]
                  MOV     WORD PTR [ES:BX+DI],AX
                  POP     BX
    {              mov     word ptr [Offset Left + di], ax}
      @Ins1:inc     height
                  cmp     dx, 0
                  jl      @Ins3
                  PUSH    DI
                  LES     DI,[RightP]
                  ADD     DI,SI
                  MOV     AX,WORD PTR [ES:DI]
                  POP     DI
    {              mov     ax, word ptr [Offset Right + si]}
                  cmp     ax, NUL
                  je      @Ins2
                  mov     si, ax
                  jmp     @Ins5
      @Ins2:
                  PUSH    BX
                  LES     BX,[RightP]
                  MOV     WORD PTR [ES:BX+SI],DI
    {              mov     word ptr [Offset Right + si], di}
                  LES     BX,[MomP]
                  MOV     WORD PTR [ES:BX+DI],SI
                  POP     BX
    {              mov     word ptr [Offset Mom + di], si}
                  jmp     @Ins11
      @Ins3:
                  PUSH    BX
                  LES     BX,[LeftP]
                  ADD     BX,SI
                  MOV     AX,WORD PTR [ES:BX]
                  POP     BX
    {              mov     ax, word ptr [Offset Left + si]}
                  cmp     ax, NUL
                  je      @Ins4
                  mov     si, ax
                  jmp     @Ins5
      @Ins4:
                  PUSH    BX
                  LES     BX,[LeftP]
                  ADD     BX,SI
                  MOV     WORD PTR [ES:BX],DI
    {              mov     word ptr [Offset Left + si], di}
                  LES     BX,[MomP]
                  ADD     BX,DI
                  MOV     WORD PTR [ES:BX],SI
                  POP     BX
    {              mov     word ptr [Offset Mom + di], si}
                  jmp     @Ins11
      @Ins5:      mov     bx, 1
                  shr     si, 1
                  shr     di, 1
                  xor     ch, ch
                  xor     dh, dh
      @Ins6:
                  PUSH    SI
                  LES     SI,[TextBufP]
                  ADD     SI,DI
                  MOV     DL,BYTE PTR [ES:SI+BX]
                  POP     SI
                  PUSH    DI
                  LES     DI,[TextBufP]
                  ADD     DI,SI
                  MOV     CL,BYTE PTR [ES:DI+BX]
                  POP     DI
    {              mov     dl, byte ptr [Offset Textbuf + di + bx]
                  mov     cl, byte ptr [Offset TextBuf + si + bx]}
                  sub     dx, cx
                  jnz     @Ins7
                  inc     bx
                  cmp     bx, F
                  jb      @Ins6
      @Ins7:      shl     si, 1
                  shl     di, 1
                  cmp     bx, matchLen
                  jbe     @Ins1
                  mov     ax, si
                  shr     ax, 1
                  mov     matchPos, ax
                  mov     matchLen, bx
                  cmp     bx, F
                  jb      @Ins1
      @Ins8:
                  PUSH    CX
                  LES     BX,[MomP]
                  MOV     AX,WORD PTR [ES:BX+SI]
    {              mov     ax, word ptr [Offset Mom + si]}
                  LES     BX,[MomP]
                  MOV     WORD PTR [ES:BX+DI],AX
    {              mov     word ptr [Offset Mom + di], ax}
                  LES     BX,[LeftP]
                  MOV     CX,WORD PTR [ES:BX+SI]
    {              mov     bx, word ptr [Offset Left + si]}
                  LES     BX,[LeftP]
                  MOV     WORD PTR [ES:BX+DI],CX
    {              mov     word ptr [Offset Left + di], bx}
                  LES     BX,[MomP]
                  ADD     BX,CX
                  MOV     WORD PTR [ES:BX],DI
    {              mov     word ptr [Offset Mom + bx], di}
                  LES     BX,[RightP]
                  MOV     CX,WORD PTR [ES:BX+SI]
    {              mov     bx, word ptr [Offset Right + si]}
                  LES     BX,[RightP]
                  MOV     WORD PTR [ES:BX+DI],CX
    {              mov     word ptr [Offset Right + di], bx}
                  LES     BX,[MomP]
                  ADD     BX,CX
                  MOV     WORD PTR [ES:BX],DI
    {              mov     word ptr [Offset Mom + bx], di}
                  LES     BX,[MomP]
                  MOV     CX,WORD PTR [ES:BX+SI]
    {              mov     bx, word ptr [Offset Mom + si]}
                  MOV     BX,CX
                  POP     CX
                  PUSH    DI
                  LES     DI,[RightP]
                  CMP     SI,WORD PTR [ES:DI+BX]
                  POP     DI
    {              cmp     si, word ptr [Offset Right + bx]}
                  jne     @Ins9
                  PUSH    SI
                  LES     SI,[RightP]
                  MOV     WORD PTR [ES:SI+BX],DI
                  POP     SI
    {              mov     word ptr [Offset Right + bx], di}
                  jmp     @Ins10
      @Ins9:
                  PUSH    SI
                  LES     SI,[LeftP]
                  MOV     WORD PTR [ES:SI+BX],DI
                  POP     SI
    {              mov     word ptr [Offset Left + bx], di}
      @Ins10:
                  PUSH    DI
                  LES     DI,[MomP]
                  ADD     DI,SI
                  MOV     WORD PTR [ES:DI],NUL
                  POP     DI
    {              mov     word ptr [Offset Mom + si], NUL}
      @Ins11:     cmp     height, 30
                  jb      @Ins12
                  call    Splay
      @Ins12:     pop     bx
                  pop     cx
                  pop     dx
                  pop     si
                  shr     di, 1
    End; { InsertNode }

    Procedure DeleteNode; assembler;
    {
       deleteNode : delete the node from the tree

                ENTRY : SI = position in the buffer
    }
    Asm
                  push    di
                  push    bx
                  shl     si, 1
                  PUSH    DI
                  LES     DI,[MomP]
                  ADD     DI,SI
                  CMP     WORD PTR [ES:DI],NUL
                  POP     DI
    {              cmp     word ptr [Offset Mom + si], NUL}   { ; if it has no
    parent then exit }              je      @del7
                  PUSH    DI
                  LES     DI,[RightP]
                  ADD     DI,SI
                  CMP     WORD PTR [ES:DI],NUL
                  POP     DI
    {              cmp     word ptr [Offset Right + si], NUL} { ; does it have
    right child ? }              je      @del8
                  PUSH    BX
                  LES     BX,[LeftP]
                  MOV     DI,WORD PTR [ES:BX+SI]
                  POP     BX
    {              mov     di, word ptr [Offset Left + si] }  { ; does it have left
    child ? }              cmp     di, NUL
                  je      @del9
                  PUSH    SI
                  LES     SI,[RightP]
                  ADD     SI,DI
                  MOV     AX,WORD PTR [ES:SI]
                  POP     SI
    {              mov     ax, word ptr [Offset Right + di]}  { ; does it have
    right grandchild ? }              cmp     ax, NUL
                  je      @del2                             { ; if no then skip }
      @del1:      mov     di, ax                            { ; find the rightmost
    node in }              PUSH    SI
                  LES     SI,[RightP]
                  ADD     SI,DI
                  MOV     AX,WORD PTR [ES:SI]
                  POP     SI
    {              mov     ax, word ptr [Offset Right + di] } { ;   the right
    subtree }              cmp     ax, NUL
                  jne     @del1
                  PUSH    CX
                  MOV     CX,SI
                  LES     SI,[MomP]
                  ADD     SI,DI
                  MOV     BX,WORD PTR [ES:SI]
    {              mov     bx, word ptr [Offset Mom + di] }   { ; move this node as
    the root of }              LES     SI,[LeftP]
                  ADD     SI,DI
                  MOV     AX,WORD PTR [ES:SI]
    {              mov     ax, word ptr [Offset Left + di]}   { ;   the subtree }
                  LES     SI,[RightP]
                  MOV     WORD PTR [ES:SI+BX],AX
    {              mov     word ptr [Offset Right + bx], ax}
                  xchg    ax, bx
                  LES     SI,[MomP]
                  MOV     WORD PTR [ES:SI+BX],AX
    {              mov     word ptr [Offset Mom + bx], ax}
                  LES     SI,[LeftP]
                  ADD     SI,CX
                  MOV     BX,WORD PTR [ES:SI]
    {              mov     bx, word ptr [Offset Left + si]}
                  LES     SI,[LeftP]
                  ADD     SI,DI
                  MOV     WORD PTR [ES:SI],BX
    {              mov     word ptr [Offset Left + di], bx}
                  LES     SI,[MomP]
                  MOV     WORD PTR [ES:SI+BX],DI
    {              mov     word ptr [Offset Mom + bx], di}
                  MOV     SI,CX
                  POP     CX
      @del2:
                  PUSH    CX
                  MOV     CX,SI
                  LES     SI,[RightP]
                  ADD     SI,CX
                  MOV     BX,WORD PTR [ES:SI]
    {              mov     bx, word ptr [Offset Right + si]}
                  LES     SI,[RightP]
                  ADD     SI,DI
                  MOV     WORD PTR [ES:SI],BX
    {              mov     word ptr [Offset Right + di], bx}
                  LES     SI,[MomP]
                  MOV     WORD PTR [ES:SI+BX],DI
                  MOV     SI,CX
                  POP     CX
    {              mov     word ptr [Offset Mom + bx], di}
      @del3:
                  PUSH    CX
                  MOV     CX,DI
                  LES     DI,[MomP]
                  ADD     DI,SI
                  MOV     BX,WORD PTR [ES:DI]
    {              mov     bx, word ptr [Offset Mom + si]}
                  LES     DI,[MomP]
                  ADD     DI,CX
                  MOV     WORD PTR [ES:DI],BX
    {              mov     word ptr [Offset Mom + di], bx}
                  MOV     DI,CX
                  POP     CX
                  PUSH    DI
                  LES     DI,[RightP]
                  CMP     SI,WORD PTR [ES:DI+BX]
                  POP     DI
    {              cmp     si, word ptr [Offset Right + bx]}
                  jne     @del4
                  PUSH    SI
                  LES     SI,[RightP]
                  MOV     WORD PTR [ES:SI+BX],DI
                  POP     SI
    {              mov     word ptr [Offset Right + bx], di}
                  jmp     @del5
      @del4:
                  PUSH    SI
                  LES     SI,[LeftP]
                  MOV     WORD PTR [ES:SI+BX],DI
                  POP     SI
    {              mov     word ptr [Offset Left + bx], di}
      @del5:
                  PUSH    DI
                  LES     DI,[MomP]
                  ADD     DI,SI
                  MOV     WORD PTR [ES:DI],NUL
                  POP     DI
    {              mov     word ptr [Offset Mom + si], NUL}
      @del7:      pop     bx
                  pop     di
                  shr     si, 1
                  jmp     @end;
      @del8:
                  PUSH    BX
                  LES     BX,[LeftP]
                  MOV     DI,WORD PTR [ES:BX+SI]
                  POP     BX
    {              mov     di, word ptr [Offset Left + si]}
                  jmp     @del3
      @del9:
                  PUSH    BX
                  LES     BX,[RightP]
                  MOV     DI,WORD PTR [ES:BX+SI]
                  POP     BX
    {              mov     di, word ptr [Offset Right + si]}
                  jmp     @del3
      @end:
    End; { DeleteNode }

    Procedure Encode; assembler;
    Asm
                  call    initTree
                  xor     bx, bx
                  mov     [Offset CodeBuf + bx], bl
                  mov     dx, 1
                  mov     ch, dl
                  xor     si, si
                  mov     di, N - F
      @Encode2:   call    getc
                  jc      @Encode3
                  PUSH    SI
                  LES     SI,[TextBufP]
                  ADD     SI,DI
                  MOV     BYTE PTR [ES:SI+BX],AL
                  POP     SI
    {              mov     byte ptr [Offset TextBuf +di + bx], al}
                  inc     bx
                  cmp     bx, F
                  jb      @Encode2
      @Encode3:   or      bx, bx
                  jne     @Encode4
                  jmp     @Encode19
      @Encode4:   mov     cl, bl
                  mov     bx, 1
                  push    di
                  sub     di, 1
      @Encode5:   call    InsertNode
                  inc     bx
                  dec     di
                  cmp     bx, F
                  jbe     @Encode5
                  pop     di
                  call    InsertNode
      @Encode6:   mov     ax, matchLen
                  cmp     al, cl
                  jbe     @Encode7
                  mov     al, cl
                  mov     matchLen, ax
      @Encode7:   cmp     al, THRESHOLD
                  ja      @Encode8
                  mov     matchLen, 1
                  or      byte ptr codeBuf, ch
                  mov     bx, dx
                  PUSH    SI
                  LES     SI,[TextBufP]
                  ADD     SI,DI
                  MOV     AL,BYTE PTR [ES:SI]
                  POP     SI
    {              mov     al, byte ptr [Offset TextBuf + di]}
                  mov     byte ptr [Offset CodeBuf + bx], al
                  inc     dx
                  jmp     @Encode9
      @Encode8:   mov     bx, dx
                  mov     al, byte ptr matchPos
                  mov     byte ptr [Offset Codebuf + bx], al
                  inc     bx
                  mov     al, byte ptr (matchPos + 1)
                  push    cx
                  mov     cl, 4
                  shl     al, cl
                  pop     cx
                  mov     ah, byte ptr matchLen
                  sub     ah, THRESHOLD + 1
                  add     al, ah
                  mov     byte ptr [Offset Codebuf + bx], al
                  inc     bx
                  mov     dx, bx
      @Encode9:   shl     ch, 1
                  jnz     @Encode11
                  xor     bx, bx
      @Encode10:  mov     al, byte ptr [Offset CodeBuf + bx]
                  call    putc
                  inc     bx
                  cmp     bx, dx
                  jb      @Encode10
                  mov     dx, 1
                  mov     ch, dl
                  mov     byte ptr codeBuf, dh
      @Encode11:  mov     bx, matchLen
                  mov     lastLen, bx
                  xor     bx, bx
      @Encode12:  call    getc
    {              jc      @Encode14}
                  jc      @Encode15
                  push    ax
                  call    deleteNode
                  pop     ax
                  PUSH    DI
                  LES     DI,[TextBufP]
                  ADD     DI,SI
                  stosb
                  POP     DI
    {              mov     byte ptr [Offset TextBuf + si], al}
                  cmp     si, F - 1
                  jae     @Encode13
                  PUSH    DI
                  LES     DI,[TextBufP]
                  ADD     DI,SI
                  MOV     BYTE PTR [ES:DI+N],AL
                  POP     DI
    {              mov     byte ptr [Offset TextBuf + si + N], al}
      @Encode13:  inc     si
                  and     si, N - 1
                  inc     di
                  and     di, N - 1
                  call    insertNode
                  inc     bx
                  cmp     bx, lastLen
                  jb      @Encode12
    (*  @Encode14:  sub     printCount, bx
                  jnc     @Encode15
                  mov     ax, printPeriod
                  mov     printCount, ax
                  push    dx                 { Print out a period as a sign. }
                  mov     dl, DBLARROW
                  mov     ah, 2
                  int     21h
                  pop     dx *)
      @Encode15:  cmp     bx, lastLen
                  jae     @Encode16
                  inc     bx
                  call    deleteNode
                  inc     si
                  and     si, N - 1
                  inc     di
                  and     di, N - 1
                  dec     cl
                  jz      @Encode15
                  call    insertNode
                  jmp     @Encode15
      @Encode16:  cmp     cl, 0
                  jbe     @Encode17
                  jmp     @Encode6
      @Encode17:  cmp     dx, 1
                  jb      @Encode19
                  xor     bx, bx
      @Encode18:  mov     al, byte ptr [Offset Codebuf + bx]
                  call    putc
                  inc     bx
                  cmp     bx, dx
                  jb      @Encode18
      @Encode19:
    End; { Encode }

    Procedure Decode; assembler;
    Asm
                  xor     dx, dx
                  mov     di, N - F
      @Decode2:   shr     dx, 1
                  or      dh, dh
                  jnz     @Decode3
                  call    getc
                  jc      @Decode9
                  mov     dh, 0ffh
                  mov     dl, al
      @Decode3:   test    dx, 1
                  jz      @Decode4
                  call    getc
                  jc      @Decode9
                  PUSH    SI
                  LES     SI,[TextBufP]
                  ADD     SI,DI
                  MOV     BYTE PTR [ES:SI],AL
                  POP     SI
    {              mov     byte ptr [Offset TextBuf + di], al}
                  inc     di
                  and     di, N - 1
                  call    putc
                  jmp     @Decode2
      @Decode4:   call    getc
                  jc      @Decode9
                  mov     ch, al
                  call    getc
                  jc      @Decode9
                  mov     bh, al
                  mov     cl, 4
                  shr     bh, cl
                  mov     bl, ch
                  mov     cl, al
                  and     cl, 0fh
                  add     cl, THRESHOLD
                  inc     cl
      @Decode5:   and     bx, N - 1
                  PUSH    SI
                  LES     SI,[TextBufP]
                  MOV     AL,BYTE PTR [ES:SI+BX]
                  ADD     SI,DI
                  MOV     BYTE PTR [ES:SI],AL
                  POP     SI
    {              mov     al, byte ptr [Offset TextBuf + bx]
                  mov     byte ptr [Offset TextBuf + di], al}
                  inc     di
                  and     di, N - 1
                  call    putc
                  inc     bx
                  dec     cl
                  jnz     @Decode5
                  jmp     @Decode2
      @Decode9:
    End; { Decode }

    Function LZInit : boolean;
    Begin
      if Initialized then Exit;
      LZInit := False;
      New(InBufP);
      New(OutBufP);
      New(TextBufP);
      New(LeftP);
      New(MomP);
      New(RightP);
      Initialized := (InBufP <> nil) and (OutBufP <> nil) and
        (TextBufP <> nil) and (LeftP <> nil) and (MomP <> nil) and (RightP <> nil);
      if Initialized then LZInit := True else
      begin
        Initialized := True;
        LZDone
      end
    End; { LZInit }

    Procedure LZDone;
    Begin
      if Initialized then
      begin
        Dispose(InBufP);
        Dispose(OutBufP);
        Dispose(RightP);
        Dispose(MomP);
        Dispose(LeftP);
        Dispose(TextBufP);
        Initialized := False
      end
    End; { LZDone }

    Procedure LZSquash;
    Begin
      if Initialized then
      begin
        InBufPtr := LZRWBufSize;
        InBufSize := LZRWBufSize;
        OutBufPtr := 0;
        Height := 0;
        MatchPos := 0;
        MatchLen := 0;
        LastLen := 0;

        FillChar(TextBufP^, SizeOf(TLZTextBuf), 0);
        FillChar(LeftP^, SizeOf(TLeftMomTree), 0);
        FillChar(MomP^, SizeOf(TLeftMomTree), 0);
        FillChar(RightP^, SizeOf(TRightTree), 0);
        FillChar(CodeBuf, SizeOf(CodeBuf), 0);

        LZReadProc := ReadProc;
        LZWriteProc := WriteProc;

        Encode;
        LZSS_Write
      end
    End; { LZSquash }

    Procedure LZUnSquash;
    Begin
      if Initialized then
      begin
        InBufPtr := LZRWBufSize;
        InBufSize := LZRWBufSize;
        OutBufPtr := 0;
        FillChar(TextBufP^, SizeOf(TLZTextBuf), 0);

        LZReadProc := ReadProc;
        LZWriteProc := WriteProc;

        Decode;
        LZSS_Write
      end
    End; { LZUnSquash }

    {$IFDEF Windows}
    Function HeapFunc(Size : word) : integer; far; assembler;
    Asm
      MOV AX,1
    End; { HeapFunc }
    {$ENDIF}

    Begin
    {$IFDEF Windows}
      HeapError := @HeapFunc;
    {$ENDIF}
      Initialized := False
    End. { LZSSUNIT }

    Program LZSSDemo;
    { Copyright (c) 1994 by Andrew Eigus   Fidonet: 2:5100/33 }
    { Demonstrates the use of LZSSUnit (LZSSUNIT.PAS), Public Domain }

    uses LZSSUnit;

    var InFile, OutFile : file;

    Function ToUpper(S : string) : string; assembler;
    Asm
      PUSH DS
      CLD
      LDS SI,S
      LES DI,@Result
      LODSB
      STOSB
      XOR AH,AH
      XCHG AX,CX
      JCXZ @@3
    @@1:
      LODSB
      CMP AL,'a'
      JB  @@2
      CMP AL,'z'
      JA  @@2
      SUB AL,20h
    @@2:
      STOSB
      LOOP @@1
    @@3:
      POP DS
    End; { ToUpper }

    Function ReadProc(var ReadBuf; var NumRead : word) : word; far;
    Begin
      BlockRead(InFile, ReadBuf, LZRWBufSize, NumRead);
      Write(#13, FilePos(InFile), ' -> ')
    End; { ReadProc }

    Function WriteProc(var WriteBuf; Count : word; var NumWritten : word) : word;
    far;Begin
      BlockWrite(OutFile, WriteBuf, Count, NumWritten);
      Write(FilePos(OutFile), #13)
    End; { WriteProc }

    Begin
      if ParamCount < 2 then
      begin
        WriteLn('Usage: LZSSDEMO <inputfile> <outputfile> [unsquash]');
        Halt(1)
      end;
      if not LZInit then
      begin
        WriteLn('Not enough memory');
        Halt(8)
      end;
      Assign(InFile, ParamStr(1));
      Reset(InFile, 1);
      if IOResult = 0 then
      begin
        Assign(OutFile, ParamStr(2));
        Rewrite(OutFile, 1);
        if IOResult = 0 then
        begin
          if ToUpper(ParamStr(3)) =  'UNSQUASH' then
            LZUnSquash(ReadProc, WriteProc)
          else
            LZSquash(ReadProc, WriteProc);
          Close(OutFile)
        end else WriteLn('Cannot create output file');
        Close(InFile)
      end else WriteLn('Cannot open input file');
      LZDone;
      WriteLn
    End.

    {
    So boys and girls...

    Here is just a ritual doc file, couz i hate to write READMEs! ;)
    Okay, LZSSUNIT.PAS is my source unit for Borland (Turbo) Pascal for
    implementation of LZSS (LZ77) compression algorithm in your programs.
    It is designed to work with all three DOS, DPMI and Windows platforms
    of Borland Pascal 7.0. Extremely clear example to show the use of this
    unit and very easy implementation.

    One note: I figured out that it compresses and decompresses files faster
    and better! than the similar Microsoft COMPRESS/EXPAND utilities used by slow
    Microsoft Setup program. Microsoft COMPRESS uses the same algo, however.

    The source code provided is all Public Domain and thus no charge is
    required for the author. Use at your own risk and modify as you wish.
    I have am also not against of putting it in the new SWAG, eh Gayle?

    Thanks send to:

    Mr. Byte of TR/-\NC3T3CHN0PH0BiA
    SysOp of AndRew's BBS  * +371-2-559777
    Fidonet: 2:5100/33
    Internet: aeigus@fgate.castle.riga.lv, aeigus@kristin.cclu.lv

    If you still love the source so much, you are still welcome to send
    some "support" fee to:

    Andrew Eigus
    Heinrichstr. 76
    CH-8005 Zurich
    }

[Back to DATATYPE SWAG index] [Back to Main SWAG index] [Original]