home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / LZSSU102.ZIP / LZSSUNIT.PAS < prev    next >
Pascal/Delphi Source File  |  1994-11-29  |  38KB  |  1,146 lines
  1. Unit LZSSUnit;
  2. {
  3.    LZSSUNIT - Compress and uncompress unit using LZ77 algorithm for
  4.    Borland (Turbo) Pascal version 7.0.
  5.  
  6.    Assembler Programmer: Andy Tam, Pascal Conversion: Douglas Webb,
  7.    Unit Conversion and Dynamic Memory Allocation: Andrew Eigus.
  8.  
  9.    Public Domain version 1.02, last changed on 30.11.94.
  10.    Target platforms: DOS, DPMI, Windows.
  11.  
  12.    Written by Andrew Eigus (aka: Mr. Byte) of:
  13.    Fidonet: 2:5100/33,
  14.    Internet: aeigus@fgate.castle.riga.lv, aeigus@kristin.cclu.lv.
  15. }
  16.  
  17. interface
  18.  
  19. {#Z+}
  20. { This unit is ready for use with Dj. Murdoch's ScanHelp utility which
  21.   will make a Borland .TPH file for it. }
  22. {#Z-}
  23.  
  24. const
  25.   LZRWBufSize     = 8192; { Read buffer size }
  26.  
  27. {#Z+}
  28.   N           = 4096;  { Bigger N -> Better compression on big files only. }
  29.   F           = 18;
  30.   Threshold   = 2;
  31.   Nul         = N * 2;
  32.   InBufPtr    : word = LZRWBufSize;
  33.   InBufSize   : word = LZRWBufSize;
  34.   OutBufPtr   : word = 0;
  35. {#Z-}
  36.  
  37. type
  38. {#X TWriteProc}{#X LZSquash}{#X LZUnsquash}
  39.  
  40.   TReadProc = function(var ReadBuf; var NumRead : word) : word;
  41.   { This is declaration for custom read function. It should read
  42.     #LZRWBufSize# bytes from ReadBuf. The return value is ignored. }
  43.  
  44. {#X TReadProc}{#X LZSquash}{#X LZUnsquash}
  45.   TWriteProc = function(var WriteBuf; Count : word; var NumWritten : word) : word;
  46.   { This is declaration for custom write function. It should write
  47.     Count bytes into WriteBuf and return number of actual bytes written
  48.     into NumWritten variable. The return value is ignored. }
  49.  
  50. {#Z+}
  51.   PLZRWBuffer = ^TLZRWBuffer;
  52.   TLZRWBuffer = array[0..LZRWBufSize - 1] of Byte; { file buffers }
  53.  
  54.   PLZTextBuf = ^TLZTextBuf;
  55.   TLZTextBuf = array[0..N + F - 2] of Byte;
  56.  
  57.   PLeftMomTree = ^TLeftMomTree;
  58.   TLeftMomTree = array[0..N] of Word;
  59.   PRightTree = ^TRightTree;
  60.   TRightTree = array[0..N + 256] of Word;
  61.  
  62. const
  63.   LZSSMemRequired = SizeOf(TLZRWBuffer) * 2 +
  64.     SizeOf(TLZTextBuf) + SizeOf(TLeftMomTree) * 2 + SizeOf(TRightTree);
  65. {#Z-}
  66.  
  67. function LZInit : boolean;
  68. { This function should be called before any other compression routines
  69.   from this unit - it allocates memory and initializes all internal
  70.   variables required by compression procedures. If allocation fails,
  71.   LZInit returns False, this means that there isn't enough memory for
  72.   compression or decompression process. It returns True if initialization
  73.   was successful. }
  74. {#X LZDone}{#X LZSquash}{#X LZUnsquash}
  75.  
  76. procedure LZSquash(ReadProc : TReadProc; WriteProc : TWriteProc);
  77. { This procedure is used for compression. ReadProc specifies custom
  78.   read function that reads data, and WriteProc specifies custom write
  79.   function that writes compressed data. }
  80. {#X LZUnsquash}{#X LZInit}{#X LZDone}
  81.  
  82. procedure LZUnSquash(ReadProc : TReadProc; WriteProc : TWriteProc);
  83. { This procedure is used for decompression. ReadProc specifies custom
  84.   read function that reads compressed data, and WriteProc specifies
  85.   custom write function that writes decompressed data. }
  86. {#X LZSquash}{#X LZInit}{#X LZDone}
  87.  
  88. procedure LZDone;
  89. { This procedure should be called after you finished compression or
  90.   decompression. It deallocates (frees) all memory allocated by LZInit.
  91.   Note: You should always call LZDone after you finished using compression
  92.   routines from this unit. }
  93. {#X LZInit}{#X LZSquash}{#X LZUnsquash}
  94.  
  95. implementation
  96.  
  97. var
  98.   Height, MatchPos, MatchLen, LastLen : word;
  99.   TextBufP : PLZTextBuf;
  100.   LeftP, MomP : PLeftMomTree;
  101.   RightP : PRightTree;
  102.   CodeBuf : array[0..16] of Byte;
  103.   LZReadProc : TReadProc;
  104.   LZWriteProc : TWriteProc;
  105.   InBufP, OutBufP : PLZRWBuffer;
  106.   Bytes : word;
  107.   Initialized : boolean;
  108.  
  109. Function LZSS_Read : word;    { Returns # of bytes read }
  110. Begin
  111.   LZReadProc(InBufP^, Bytes);
  112.   LZSS_Read := Bytes;
  113. End; { LZSS_Read }
  114.  
  115. Function LZSS_Write : word;  { Returns # of bytes written }
  116. Begin
  117.   LZWriteProc(OutBufP^, OutBufPtr, Bytes);
  118.   LZSS_Write := Bytes
  119. End; { LZSS_Write }
  120.  
  121. Procedure Getc; assembler;
  122. Asm
  123. {
  124.   getc : return a character from the buffer
  125.           RETURN : AL = input char
  126.                    Carry set when EOF
  127. }
  128.               push    bx
  129.               mov     bx, inBufPtr
  130.               cmp     bx, inBufSize
  131.               jb      @getc1
  132.               push    cx
  133.               push    dx
  134.               push    di
  135.               push    si
  136.               call    LZSS_Read
  137.               pop     si
  138.               pop     di
  139.               pop     dx
  140.               pop     cx
  141.               mov     inBufSize, ax
  142.               or      ax, ax
  143.               jz      @getc2               { ; EOF }
  144.               xor     bx, bx
  145.   @getc1:
  146.               PUSH    DI
  147.               LES     DI,[InBufP]
  148.               MOV     AL,BYTE PTR [ES:DI+BX]
  149.               POP     DI
  150.               inc     bx
  151.               mov     inBufPtr, bx
  152.               pop     bx
  153.               clc                         { ; clear the carry flag }
  154.               jmp     @end
  155.   @getc2:     pop     bx
  156.               stc                         { ; set carry to indicate EOF }
  157.   @end:
  158. End; { Getc }
  159.  
  160. Procedure Putc; assembler;
  161. {
  162.   putc : put a character into the output buffer
  163.              Entry : AL = output char
  164. }
  165. Asm
  166.               push    bx
  167.               mov     bx, outBufPtr
  168.               PUSH    DI
  169.               LES     DI,[OutBufP]
  170.               MOV     BYTE PTR [ES:DI+BX],AL
  171.               POP     DI
  172.               inc     bx
  173.               cmp     bx, LZRWBufSize
  174.               jb      @putc1
  175.               mov     OutBufPtr,LZRWBufSize   { Just so the flush will work. }
  176.               push    cx
  177.               push    dx
  178.               push    di
  179.               push    si
  180.               call    LZSS_Write
  181.               pop     si
  182.               pop     di
  183.               pop     dx
  184.               pop     cx
  185.               xor     bx, bx
  186.   @putc1:     mov     outBufPtr, bx
  187.               pop     bx
  188. End; { Putc }
  189.  
  190. Procedure InitTree; assembler;
  191. {
  192.   initTree : initialize all binary search trees.  There are 256 BST's, one
  193.              for all strings started with a particular character.  The
  194.              parent is tree K is the node N + K + 1 and it has only a
  195.              right child
  196. }
  197. Asm
  198.       cld
  199.       push    ds
  200.       pop     es
  201.       LES     DI,[RightP]
  202. {      mov     di,offset right}
  203.       add     di, (N + 1) * 2
  204.       mov     cx, 256
  205.       mov     ax, NUL
  206.       rep     stosw
  207.       LES     DI,[MomP]
  208. {      mov     di, offset mom}
  209.       mov     cx, N
  210.       rep     stosw
  211. End; { InitTree }
  212.  
  213. Procedure Splay; assembler;
  214. {
  215.   splay : use splay tree operations to move the node to the 'top' of
  216.            tree.  Note that it will not actual become the root of the tree
  217.            because the root of each tree is a special node.  Instead, it
  218.            will become the right child of this special node.
  219.  
  220.              ENTRY : di = the node to be rotated
  221. }
  222. Asm
  223.   @Splay1:
  224.               PUSH    BX
  225.               LES     BX,[MomP]
  226.               MOV     SI,[ES:BX+DI]
  227.               POP     BX
  228. {              mov     si, [Offset Mom + di]}
  229.               cmp     si, NUL           { ; exit if its parent is a special node }
  230.               ja      @Splay4
  231.               PUSH    DI
  232.               LES     DI,[MomP]
  233.               ADD     DI,SI
  234.               MOV     BX,[ES:DI]
  235. {              mov     bx, [Offset Mom + si]}
  236.               POP     DI
  237.               cmp     bx, NUL           { ; check if its grandparent is special }
  238.               jbe     @Splay5           { ; if not then skip }
  239.               PUSH    BX
  240.               LES     BX,[LeftP]
  241.               CMP     DI,[ES:BX+SI]
  242.               POP     BX
  243. {              cmp     di, [Offset Left + si]} { ; is the current node is a left child ? }
  244.               jne     @Splay2
  245.               PUSH    BX
  246.               LES     BX,[RightP]
  247.               MOV     DX,[ES:BX+DI]
  248. {              mov     dx, [Offset Right + di]}    { ; perform a left zig operation }
  249.               LES     BX,[LeftP]
  250.               MOV     [ES:BX+SI],DX
  251. {              mov     [Offset Left + si], dx}
  252.               LES     BX,[RightP]
  253.               MOV     [ES:BX+DI],SI
  254.               POP     BX
  255. {              mov     [Offset Right + di], si}
  256.               jmp     @Splay3
  257.   @Splay2:
  258.               PUSH    BX
  259.               LES     BX,[LeftP]
  260.               MOV     DX,[ES:BX+DI]
  261. {              mov     dx, [Offset Left + di]}     { ; perform a right zig }
  262.               LES     BX,[RightP]
  263.               MOV     [ES:BX+SI],DX
  264. {              mov     [Offset Right + si], dx}
  265.               LES     BX,[LeftP]
  266.               MOV     [ES:BX+DI],SI
  267.               POP     BX
  268. {              mov     [Offset Left + di], si}
  269.   @Splay3:
  270.               PUSH    SI
  271.               LES     SI,[RightP]
  272.               MOV     [ES:SI+BX],DI
  273.               POP     SI
  274. {              mov     [Offset Right + bx], di}
  275.               xchg    bx, dx
  276.               PUSH    AX
  277.               MOV     AX,BX
  278.               LES     BX,[MomP]
  279.               ADD     BX,AX
  280.               MOV     [ES:BX],SI
  281.               LES     BX,[MomP]
  282.               MOV     [ES:BX+SI],DI
  283.               LES     BX,[MomP]
  284.               MOV     [ES:BX+DI],DX
  285.               MOV     BX,AX
  286.               POP     AX
  287. {              mov     [Offset Mom + bx], si
  288.               mov     [Offset Mom + si], di
  289.               mov     [Offset Mom + di], dx}
  290.   @Splay4:    jmp     @end
  291.   @Splay5:
  292.               PUSH    DI
  293.               LES     DI,[MomP]
  294.               MOV     CX,[ES:DI+BX]
  295.               POP     DI
  296. {              mov     cx, [Offset Mom + bx]}
  297.               PUSH    BX
  298.               LES     BX,[LeftP]
  299.               CMP     DI,[ES:BX+SI]
  300.               POP     BX
  301. {              cmp     di, [Offset Left + si]}
  302.               jne     @Splay7
  303.               PUSH    DI
  304.               LES     DI,[LeftP]
  305.               CMP     SI,[ES:DI+BX]
  306.               POP     DI
  307. {              cmp     si, [Offset Left + bx]}
  308.               jne     @Splay6
  309.               PUSH    AX
  310.               MOV     AX,DI
  311.               LES     DI,[RightP]
  312.               ADD     DI,SI
  313.               MOV     DX,[ES:DI]
  314. {              mov     dx, [Offset Right + si]   } { ; perform a left zig-zig operation }
  315.               LES     DI,[LeftP]
  316.               MOV     [ES:DI+BX],DX
  317. {              mov     [Offset Left + bx], dx}
  318.               xchg    bx, dx
  319.               LES     DI,[MomP]
  320.               MOV     [ES:DI+BX],DX
  321. {              mov     [Offset Mom + bx], dx}
  322.               LES     DI,[RightP]
  323.               ADD     DI,AX
  324.               MOV     BX,[ES:DI]
  325. {              mov     bx, [Offset Right + di]}
  326.               LES     DI,[LeftP]
  327.               ADD     DI,SI
  328.               MOV     [ES:DI],BX
  329.               LES     DI,[MomP]
  330.               MOV     [ES:DI+BX],SI
  331. {              mov     [Offset Left +si], bx
  332.               mov     [Offset Mom + bx], si}
  333.               mov     bx, dx
  334.               LES     DI,[RightP]
  335.               ADD     DI,SI
  336.               MOV     [ES:DI],BX
  337.               LES     DI,[RightP]
  338.               ADD     DI,AX
  339.               MOV     [ES:DI],SI
  340. {              mov     [Offset Right + si], bx
  341.               mov     [Offset Right + di], si}
  342.               LES     DI,[MomP]
  343.               MOV     [ES:DI+BX],SI
  344.               LES     DI,[MomP]
  345.               ADD     DI,SI
  346.               STOSW
  347.               MOV     DI,AX
  348.               POP     AX
  349. {              mov     [Offset Mom + bx], si
  350.               mov     [Offset Mom + si], di}
  351.               jmp     @Splay9
  352.   @Splay6:
  353.               PUSH    AX
  354.               MOV     AX,SI
  355.               LES     SI,[LeftP]
  356.               ADD     SI,DI
  357.               MOV     DX,[ES:SI]
  358. {              mov     dx, [Offset Left + di]}     { ; perform a left zig-zag operation }
  359.               LES     SI,[RightP]
  360.               MOV     [ES:SI+BX],DX
  361. {              mov     [Offset Right + bx], dx}
  362.               xchg    bx, dx
  363.               LES     SI,[MomP]
  364.               MOV     [ES:SI+BX],DX
  365. {              mov     [Offset Mom + bx], dx}
  366.               LES     SI,[RightP]
  367.               ADD     SI,DI
  368.               MOV     BX,[ES:SI]
  369. {              mov     bx, [Offset Right + di]}
  370.               LES     SI,[LeftP]
  371.               ADD     SI,AX
  372.               MOV     [ES:SI],BX
  373. {              mov     [Offset Left + si], bx}
  374.               LES     SI,[MomP]
  375.               MOV     [ES:SI+BX],AX
  376. {              mov     [Offset Mom + bx], si}
  377.               mov     bx, dx
  378.               LES     SI,[LeftP]
  379.               ADD     SI,DI
  380.               MOV     [ES:SI],BX
  381. {              mov     [Offset Left + di], bx}
  382.               LES     SI,[RightP]
  383.               ADD     SI,DI
  384.               MOV     [ES:SI],AX
  385. {              mov     [Offset Right + di], si}
  386.               LES     SI,[MomP]
  387.               ADD     SI,AX
  388.               MOV     [ES:SI],DI
  389. {              mov     [Offset Mom + si], di}
  390.               LES     SI,[MomP]
  391.               MOV     [ES:SI+BX],DI
  392.               MOV     SI,AX
  393.               POP     AX
  394. {              mov     [Offset Mom + bx], di}
  395.               jmp     @Splay9
  396.   @Splay7:
  397.               PUSH    DI
  398.               LES     DI,[RightP]
  399.               CMP     SI,[ES:DI+BX]
  400.               POP     DI
  401. {              cmp     si, [Offset Right + bx]}
  402.               jne     @Splay8
  403.               PUSH    AX
  404.               MOV     AX,SI
  405.               LES     SI,[LeftP]
  406.               ADD     SI,AX
  407.               MOV     DX,[ES:SI]
  408. {              mov     dx, [Offset Left + si]}     { ; perform a right zig-zig }
  409.               LES     SI,[RightP]
  410.               MOV     [ES:SI+BX],DX
  411. {              mov     [Offset Right + bx], dx}
  412.               xchg    bx, dx
  413.               LES     SI,[MomP]
  414.               MOV     [ES:SI+BX],DX
  415. {              mov     [Offset Mom + bx], dx}
  416.               LES     SI,[LeftP]
  417.               ADD     SI,DI
  418.               MOV     BX,[ES:SI]
  419. {              mov     bx, [Offset Left + di]}
  420.               LES     SI,[RightP]
  421.               ADD     SI,AX
  422.               MOV     [ES:SI],BX
  423. {              mov     [Offset Right + si], bx}
  424.               LES     SI,[MomP]
  425.               MOV     [ES:SI+BX],AX
  426. {              mov     [Offset Mom + bx], si}
  427.               mov     bx, dx
  428.               LES     SI,[LeftP]
  429.               ADD     SI,AX
  430.               MOV     [ES:SI],BX
  431. {              mov     [Offset Left + si], bx}
  432.               LES     SI,[LeftP]
  433.               ADD     SI,DI
  434.               MOV     [ES:SI],AX
  435. {              mov     [Offset Left + di], si}
  436.               LES     SI,[MomP]
  437.               MOV     [ES:SI+BX],AX
  438. {              mov     [Offset Mom + bx], si}
  439.               LES     SI,[MomP]
  440.               ADD     SI,AX
  441.               MOV     [ES:SI],DI
  442. {              mov     [Offset Mom + si], di}
  443.               MOV     SI,AX
  444.               POP     AX
  445.               jmp     @Splay9
  446.   @Splay8:
  447.               PUSH    AX
  448.               MOV     AX,SI
  449.               LES     SI,[RightP]
  450.               ADD     SI,DI
  451.               MOV     DX,[ES:SI]
  452. {              mov     dx, [Offset Right + di]}    { ; perform a right zig-zag }
  453.               LES     SI,[LeftP]
  454.               MOV     [ES:SI+BX],DX
  455. {              mov     [Offset Left + bx], dx}
  456.               xchg    bx, dx
  457.               LES     SI,[MomP]
  458.               MOV     [ES:SI+BX],DX
  459. {              mov     [Offset Mom + bx], dx}
  460.               LES     SI,[LeftP]
  461.               ADD     SI,DI
  462.               MOV     BX,[ES:SI]
  463. {              mov     bx, [Offset Left + di]}
  464.               LES     SI,[RightP]
  465.               ADD     SI,AX
  466.               MOV     [ES:SI],BX
  467. {              mov     [Offset Right + si], bx}
  468.               LES     SI,[MomP]
  469.               MOV     [ES:SI+BX],AX
  470. {              mov     [Offset Mom + bx], si}
  471.               mov     bx, dx
  472.               LES     SI,[RightP]
  473.               ADD     SI,DI
  474.               MOV     [ES:SI],BX
  475. {              mov     [Offset Right + di], bx}
  476.               LES     SI,[LeftP]
  477.               ADD     SI,DI
  478.               MOV     [ES:SI],AX
  479. {              mov     [Offset Left + di], si}
  480.               LES     SI,[MomP]
  481.               ADD     SI,AX
  482.               MOV     [ES:SI],DI
  483.               LES     SI,[MomP]
  484.               MOV     [ES:SI+BX],DI
  485. {              mov     [Offset Mom + si], di
  486.               mov     [Offset Mom + bx], di}
  487.               MOV     SI,AX
  488.               POP     AX
  489.   @Splay9:    mov     si, cx
  490.               cmp     si, NUL
  491.               ja      @Splay10
  492.               PUSH    DI
  493.               LES     DI,[LeftP]
  494.               ADD     DI,SI
  495.               CMP     BX,[ES:DI]
  496.               POP     DI
  497. {              cmp     bx, [Offset Left + si]}
  498.               jne     @Splay10
  499.               PUSH    BX
  500.               LES     BX,[LeftP]
  501.               MOV     [ES:BX+SI],DI
  502.               POP     BX
  503. {              mov     [Offset Left + si], di}
  504.               jmp     @Splay11
  505.   @Splay10:
  506.               PUSH    BX
  507.               LES     BX,[RightP]
  508.               MOV     [ES:BX+SI],DI
  509.               POP     BX
  510. {              mov     [Offset Right + si], di}
  511.   @Splay11:
  512.               PUSH    BX
  513.               LES     BX,[MomP]
  514.               MOV     [ES:BX+DI],SI
  515.               POP     BX
  516. {              mov     [Offset Mom + di], si}
  517.               jmp     @Splay1
  518.   @end:
  519. End; { SPlay }
  520.  
  521. Procedure InsertNode; assembler;
  522. {
  523.   insertNode : insert the new node to the corresponding tree.  Note that the
  524.                position of a string in the buffer also served as the node
  525.                number.
  526.              ENTRY : di = position in the buffer
  527. }
  528. Asm
  529.               push    si
  530.               push    dx
  531.               push    cx
  532.               push    bx
  533.               mov     dx, 1
  534.               xor     ax, ax
  535.               mov     matchLen, ax
  536.               mov     height, ax
  537.               LES     SI,[TextBufP]
  538.               ADD     SI,DI
  539.               MOV     AL,BYTE PTR [ES:SI]
  540. {             mov     al, byte ptr [Offset TextBuf + di]}
  541.               shl     di, 1
  542.               add     ax, N + 1
  543.               shl     ax, 1
  544.               mov     si, ax
  545.               mov     ax, NUL
  546.               PUSH    BX
  547.               LES     BX,[RightP]
  548.               MOV     WORD PTR [ES:BX+DI],AX
  549. {              mov     word ptr [Offset Right + di], ax}
  550.               LES     BX,[LeftP]
  551.               MOV     WORD PTR [ES:BX+DI],AX
  552.               POP     BX
  553. {              mov     word ptr [Offset Left + di], ax}
  554.   @Ins1:inc     height
  555.               cmp     dx, 0
  556.               jl      @Ins3
  557.               PUSH    DI
  558.               LES     DI,[RightP]
  559.               ADD     DI,SI
  560.               MOV     AX,WORD PTR [ES:DI]
  561.               POP     DI
  562. {              mov     ax, word ptr [Offset Right + si]}
  563.               cmp     ax, NUL
  564.               je      @Ins2
  565.               mov     si, ax
  566.               jmp     @Ins5
  567.   @Ins2:
  568.               PUSH    BX
  569.               LES     BX,[RightP]
  570.               MOV     WORD PTR [ES:BX+SI],DI
  571. {              mov     word ptr [Offset Right + si], di}
  572.               LES     BX,[MomP]
  573.               MOV     WORD PTR [ES:BX+DI],SI
  574.               POP     BX
  575. {              mov     word ptr [Offset Mom + di], si}
  576.               jmp     @Ins11
  577.   @Ins3:
  578.               PUSH    BX
  579.               LES     BX,[LeftP]
  580.               ADD     BX,SI
  581.               MOV     AX,WORD PTR [ES:BX]
  582.               POP     BX
  583. {              mov     ax, word ptr [Offset Left + si]}
  584.               cmp     ax, NUL
  585.               je      @Ins4
  586.               mov     si, ax
  587.               jmp     @Ins5
  588.   @Ins4:
  589.               PUSH    BX
  590.               LES     BX,[LeftP]
  591.               ADD     BX,SI
  592.               MOV     WORD PTR [ES:BX],DI
  593. {              mov     word ptr [Offset Left + si], di}
  594.               LES     BX,[MomP]
  595.               ADD     BX,DI
  596.               MOV     WORD PTR [ES:BX],SI
  597.               POP     BX
  598. {              mov     word ptr [Offset Mom + di], si}
  599.               jmp     @Ins11
  600.   @Ins5:      mov     bx, 1
  601.               shr     si, 1
  602.               shr     di, 1
  603.               xor     ch, ch
  604.               xor     dh, dh
  605.   @Ins6:
  606.               PUSH    SI
  607.               LES     SI,[TextBufP]
  608.               ADD     SI,DI
  609.               MOV     DL,BYTE PTR [ES:SI+BX]
  610.               POP     SI
  611.               PUSH    DI
  612.               LES     DI,[TextBufP]
  613.               ADD     DI,SI
  614.               MOV     CL,BYTE PTR [ES:DI+BX]
  615.               POP     DI
  616. {              mov     dl, byte ptr [Offset Textbuf + di + bx]
  617.               mov     cl, byte ptr [Offset TextBuf + si + bx]}
  618.               sub     dx, cx
  619.               jnz     @Ins7
  620.               inc     bx
  621.               cmp     bx, F
  622.               jb      @Ins6
  623.   @Ins7:      shl     si, 1
  624.               shl     di, 1
  625.               cmp     bx, matchLen
  626.               jbe     @Ins1
  627.               mov     ax, si
  628.               shr     ax, 1
  629.               mov     matchPos, ax
  630.               mov     matchLen, bx
  631.               cmp     bx, F
  632.               jb      @Ins1
  633.   @Ins8:
  634.               PUSH    CX
  635.               LES     BX,[MomP]
  636.               MOV     AX,WORD PTR [ES:BX+SI]
  637. {              mov     ax, word ptr [Offset Mom + si]}
  638.               LES     BX,[MomP]
  639.               MOV     WORD PTR [ES:BX+DI],AX
  640. {              mov     word ptr [Offset Mom + di], ax}
  641.               LES     BX,[LeftP]
  642.               MOV     CX,WORD PTR [ES:BX+SI]
  643. {              mov     bx, word ptr [Offset Left + si]}
  644.               LES     BX,[LeftP]
  645.               MOV     WORD PTR [ES:BX+DI],CX
  646. {              mov     word ptr [Offset Left + di], bx}
  647.               LES     BX,[MomP]
  648.               ADD     BX,CX
  649.               MOV     WORD PTR [ES:BX],DI
  650. {              mov     word ptr [Offset Mom + bx], di}
  651.               LES     BX,[RightP]
  652.               MOV     CX,WORD PTR [ES:BX+SI]
  653. {              mov     bx, word ptr [Offset Right + si]}
  654.               LES     BX,[RightP]
  655.               MOV     WORD PTR [ES:BX+DI],CX
  656. {              mov     word ptr [Offset Right + di], bx}
  657.               LES     BX,[MomP]
  658.               ADD     BX,CX
  659.               MOV     WORD PTR [ES:BX],DI
  660. {              mov     word ptr [Offset Mom + bx], di}
  661.               LES     BX,[MomP]
  662.               MOV     CX,WORD PTR [ES:BX+SI]
  663. {              mov     bx, word ptr [Offset Mom + si]}
  664.               MOV     BX,CX
  665.               POP     CX
  666.               PUSH    DI
  667.               LES     DI,[RightP]
  668.               CMP     SI,WORD PTR [ES:DI+BX]
  669.               POP     DI
  670. {              cmp     si, word ptr [Offset Right + bx]}
  671.               jne     @Ins9
  672.               PUSH    SI
  673.               LES     SI,[RightP]
  674.               MOV     WORD PTR [ES:SI+BX],DI
  675.               POP     SI
  676. {              mov     word ptr [Offset Right + bx], di}
  677.               jmp     @Ins10
  678.   @Ins9:
  679.               PUSH    SI
  680.               LES     SI,[LeftP]
  681.               MOV     WORD PTR [ES:SI+BX],DI
  682.               POP     SI
  683. {              mov     word ptr [Offset Left + bx], di}
  684.   @Ins10:
  685.               PUSH    DI
  686.               LES     DI,[MomP]
  687.               ADD     DI,SI
  688.               MOV     WORD PTR [ES:DI],NUL
  689.               POP     DI
  690. {              mov     word ptr [Offset Mom + si], NUL}
  691.   @Ins11:     cmp     height, 30
  692.               jb      @Ins12
  693.               call    Splay
  694.   @Ins12:     pop     bx
  695.               pop     cx
  696.               pop     dx
  697.               pop     si
  698.               shr     di, 1
  699. End; { InsertNode }
  700.  
  701.  
  702. Procedure DeleteNode; assembler;
  703. {
  704.    deleteNode : delete the node from the tree
  705.  
  706.             ENTRY : SI = position in the buffer
  707. }
  708. Asm
  709.               push    di
  710.               push    bx
  711.               shl     si, 1
  712.               PUSH    DI
  713.               LES     DI,[MomP]
  714.               ADD     DI,SI
  715.               CMP     WORD PTR [ES:DI],NUL
  716.               POP     DI
  717. {              cmp     word ptr [Offset Mom + si], NUL}   { ; if it has no parent then exit }
  718.               je      @del7
  719.               PUSH    DI
  720.               LES     DI,[RightP]
  721.               ADD     DI,SI
  722.               CMP     WORD PTR [ES:DI],NUL
  723.               POP     DI
  724. {              cmp     word ptr [Offset Right + si], NUL} { ; does it have right child ? }
  725.               je      @del8
  726.               PUSH    BX
  727.               LES     BX,[LeftP]
  728.               MOV     DI,WORD PTR [ES:BX+SI]
  729.               POP     BX
  730. {              mov     di, word ptr [Offset Left + si] }  { ; does it have left child ? }
  731.               cmp     di, NUL
  732.               je      @del9
  733.               PUSH    SI
  734.               LES     SI,[RightP]
  735.               ADD     SI,DI
  736.               MOV     AX,WORD PTR [ES:SI]
  737.               POP     SI
  738. {              mov     ax, word ptr [Offset Right + di]}  { ; does it have right grandchild ? }
  739.               cmp     ax, NUL
  740.               je      @del2                             { ; if no then skip }
  741.   @del1:      mov     di, ax                            { ; find the rightmost node in }
  742.               PUSH    SI
  743.               LES     SI,[RightP]
  744.               ADD     SI,DI
  745.               MOV     AX,WORD PTR [ES:SI]
  746.               POP     SI
  747. {              mov     ax, word ptr [Offset Right + di] } { ;   the right subtree }
  748.               cmp     ax, NUL
  749.               jne     @del1
  750.               PUSH    CX
  751.               MOV     CX,SI
  752.               LES     SI,[MomP]
  753.               ADD     SI,DI
  754.               MOV     BX,WORD PTR [ES:SI]
  755. {              mov     bx, word ptr [Offset Mom + di] }   { ; move this node as the root of }
  756.               LES     SI,[LeftP]
  757.               ADD     SI,DI
  758.               MOV     AX,WORD PTR [ES:SI]
  759. {              mov     ax, word ptr [Offset Left + di]}   { ;   the subtree }
  760.               LES     SI,[RightP]
  761.               MOV     WORD PTR [ES:SI+BX],AX
  762. {              mov     word ptr [Offset Right + bx], ax}
  763.               xchg    ax, bx
  764.               LES     SI,[MomP]
  765.               MOV     WORD PTR [ES:SI+BX],AX
  766. {              mov     word ptr [Offset Mom + bx], ax}
  767.               LES     SI,[LeftP]
  768.               ADD     SI,CX
  769.               MOV     BX,WORD PTR [ES:SI]
  770. {              mov     bx, word ptr [Offset Left + si]}
  771.               LES     SI,[LeftP]
  772.               ADD     SI,DI
  773.               MOV     WORD PTR [ES:SI],BX
  774. {              mov     word ptr [Offset Left + di], bx}
  775.               LES     SI,[MomP]
  776.               MOV     WORD PTR [ES:SI+BX],DI
  777. {              mov     word ptr [Offset Mom + bx], di}
  778.               MOV     SI,CX
  779.               POP     CX
  780.   @del2:
  781.               PUSH    CX
  782.               MOV     CX,SI
  783.               LES     SI,[RightP]
  784.               ADD     SI,CX
  785.               MOV     BX,WORD PTR [ES:SI]
  786. {              mov     bx, word ptr [Offset Right + si]}
  787.               LES     SI,[RightP]
  788.               ADD     SI,DI
  789.               MOV     WORD PTR [ES:SI],BX
  790. {              mov     word ptr [Offset Right + di], bx}
  791.               LES     SI,[MomP]
  792.               MOV     WORD PTR [ES:SI+BX],DI
  793.               MOV     SI,CX
  794.               POP     CX
  795. {              mov     word ptr [Offset Mom + bx], di}
  796.   @del3:
  797.               PUSH    CX
  798.               MOV     CX,DI
  799.               LES     DI,[MomP]
  800.               ADD     DI,SI
  801.               MOV     BX,WORD PTR [ES:DI]
  802. {              mov     bx, word ptr [Offset Mom + si]}
  803.               LES     DI,[MomP]
  804.               ADD     DI,CX
  805.               MOV     WORD PTR [ES:DI],BX
  806. {              mov     word ptr [Offset Mom + di], bx}
  807.               MOV     DI,CX
  808.               POP     CX
  809.               PUSH    DI
  810.               LES     DI,[RightP]
  811.               CMP     SI,WORD PTR [ES:DI+BX]
  812.               POP     DI
  813. {              cmp     si, word ptr [Offset Right + bx]}
  814.               jne     @del4
  815.               PUSH    SI
  816.               LES     SI,[RightP]
  817.               MOV     WORD PTR [ES:SI+BX],DI
  818.               POP     SI
  819. {              mov     word ptr [Offset Right + bx], di}
  820.               jmp     @del5
  821.   @del4:
  822.               PUSH    SI
  823.               LES     SI,[LeftP]
  824.               MOV     WORD PTR [ES:SI+BX],DI
  825.               POP     SI
  826. {              mov     word ptr [Offset Left + bx], di}
  827.   @del5:
  828.               PUSH    DI
  829.               LES     DI,[MomP]
  830.               ADD     DI,SI
  831.               MOV     WORD PTR [ES:DI],NUL
  832.               POP     DI
  833. {              mov     word ptr [Offset Mom + si], NUL}
  834.   @del7:      pop     bx
  835.               pop     di
  836.               shr     si, 1
  837.               jmp     @end;
  838.   @del8:
  839.               PUSH    BX
  840.               LES     BX,[LeftP]
  841.               MOV     DI,WORD PTR [ES:BX+SI]
  842.               POP     BX
  843. {              mov     di, word ptr [Offset Left + si]}
  844.               jmp     @del3
  845.   @del9:
  846.               PUSH    BX
  847.               LES     BX,[RightP]
  848.               MOV     DI,WORD PTR [ES:BX+SI]
  849.               POP     BX
  850. {              mov     di, word ptr [Offset Right + si]}
  851.               jmp     @del3
  852.   @end:
  853. End; { DeleteNode }
  854.  
  855.  
  856. Procedure Encode; assembler;
  857. Asm
  858.               call    initTree
  859.               xor     bx, bx
  860.               mov     [Offset CodeBuf + bx], bl
  861.               mov     dx, 1
  862.               mov     ch, dl
  863.               xor     si, si
  864.               mov     di, N - F
  865.   @Encode2:   call    getc
  866.               jc      @Encode3
  867.               PUSH    SI
  868.               LES     SI,[TextBufP]
  869.               ADD     SI,DI
  870.               MOV     BYTE PTR [ES:SI+BX],AL
  871.               POP     SI
  872. {              mov     byte ptr [Offset TextBuf +di + bx], al}
  873.               inc     bx
  874.               cmp     bx, F
  875.               jb      @Encode2
  876.   @Encode3:   or      bx, bx
  877.               jne     @Encode4
  878.               jmp     @Encode19
  879.   @Encode4:   mov     cl, bl
  880.               mov     bx, 1
  881.               push    di
  882.               sub     di, 1
  883.   @Encode5:   call    InsertNode
  884.               inc     bx
  885.               dec     di
  886.               cmp     bx, F
  887.               jbe     @Encode5
  888.               pop     di
  889.               call    InsertNode
  890.   @Encode6:   mov     ax, matchLen
  891.               cmp     al, cl
  892.               jbe     @Encode7
  893.               mov     al, cl
  894.               mov     matchLen, ax
  895.   @Encode7:   cmp     al, THRESHOLD
  896.               ja      @Encode8
  897.               mov     matchLen, 1
  898.               or      byte ptr codeBuf, ch
  899.               mov     bx, dx
  900.               PUSH    SI
  901.               LES     SI,[TextBufP]
  902.               ADD     SI,DI
  903.               MOV     AL,BYTE PTR [ES:SI]
  904.               POP     SI
  905. {              mov     al, byte ptr [Offset TextBuf + di]}
  906.               mov     byte ptr [Offset CodeBuf + bx], al
  907.               inc     dx
  908.               jmp     @Encode9
  909.   @Encode8:   mov     bx, dx
  910.               mov     al, byte ptr matchPos
  911.               mov     byte ptr [Offset Codebuf + bx], al
  912.               inc     bx
  913.               mov     al, byte ptr (matchPos + 1)
  914.               push    cx
  915.               mov     cl, 4
  916.               shl     al, cl
  917.               pop     cx
  918.               mov     ah, byte ptr matchLen
  919.               sub     ah, THRESHOLD + 1
  920.               add     al, ah
  921.               mov     byte ptr [Offset Codebuf + bx], al
  922.               inc     bx
  923.               mov     dx, bx
  924.   @Encode9:   shl     ch, 1
  925.               jnz     @Encode11
  926.               xor     bx, bx
  927.   @Encode10:  mov     al, byte ptr [Offset CodeBuf + bx]
  928.               call    putc
  929.               inc     bx
  930.               cmp     bx, dx
  931.               jb      @Encode10
  932.               mov     dx, 1
  933.               mov     ch, dl
  934.               mov     byte ptr codeBuf, dh
  935.   @Encode11:  mov     bx, matchLen
  936.               mov     lastLen, bx
  937.               xor     bx, bx
  938.   @Encode12:  call    getc
  939. {              jc      @Encode14}
  940.               jc      @Encode15
  941.               push    ax
  942.               call    deleteNode
  943.               pop     ax
  944.               PUSH    DI
  945.               LES     DI,[TextBufP]
  946.               ADD     DI,SI
  947.               stosb
  948.               POP     DI
  949. {              mov     byte ptr [Offset TextBuf + si], al}
  950.               cmp     si, F - 1
  951.               jae     @Encode13
  952.               PUSH    DI
  953.               LES     DI,[TextBufP]
  954.               ADD     DI,SI
  955.               MOV     BYTE PTR [ES:DI+N],AL
  956.               POP     DI
  957. {              mov     byte ptr [Offset TextBuf + si + N], al}
  958.   @Encode13:  inc     si
  959.               and     si, N - 1
  960.               inc     di
  961.               and     di, N - 1
  962.               call    insertNode
  963.               inc     bx
  964.               cmp     bx, lastLen
  965.               jb      @Encode12
  966. (*  @Encode14:  sub     printCount, bx
  967.               jnc     @Encode15
  968.               mov     ax, printPeriod
  969.               mov     printCount, ax
  970.               push    dx                 { Print out a period as a sign. }
  971.               mov     dl, DBLARROW
  972.               mov     ah, 2
  973.               int     21h
  974.               pop     dx *)
  975.   @Encode15:  cmp     bx, lastLen
  976.               jae     @Encode16
  977.               inc     bx
  978.               call    deleteNode
  979.               inc     si
  980.               and     si, N - 1
  981.               inc     di
  982.               and     di, N - 1
  983.               dec     cl
  984.               jz      @Encode15
  985.               call    insertNode
  986.               jmp     @Encode15
  987.   @Encode16:  cmp     cl, 0
  988.               jbe     @Encode17
  989.               jmp     @Encode6
  990.   @Encode17:  cmp     dx, 1
  991.               jb      @Encode19
  992.               xor     bx, bx
  993.   @Encode18:  mov     al, byte ptr [Offset Codebuf + bx]
  994.               call    putc
  995.               inc     bx
  996.               cmp     bx, dx
  997.               jb      @Encode18
  998.   @Encode19:
  999. End; { Encode }
  1000.  
  1001. Procedure Decode; assembler;
  1002. Asm
  1003.               xor     dx, dx
  1004.               mov     di, N - F
  1005.   @Decode2:   shr     dx, 1
  1006.               or      dh, dh
  1007.               jnz     @Decode3
  1008.               call    getc
  1009.               jc      @Decode9
  1010.               mov     dh, 0ffh
  1011.               mov     dl, al
  1012.   @Decode3:   test    dx, 1
  1013.               jz      @Decode4
  1014.               call    getc
  1015.               jc      @Decode9
  1016.               PUSH    SI
  1017.               LES     SI,[TextBufP]
  1018.               ADD     SI,DI
  1019.               MOV     BYTE PTR [ES:SI],AL
  1020.               POP     SI
  1021. {              mov     byte ptr [Offset TextBuf + di], al}
  1022.               inc     di
  1023.               and     di, N - 1
  1024.               call    putc
  1025.               jmp     @Decode2
  1026.   @Decode4:   call    getc
  1027.               jc      @Decode9
  1028.               mov     ch, al
  1029.               call    getc
  1030.               jc      @Decode9
  1031.               mov     bh, al
  1032.               mov     cl, 4
  1033.               shr     bh, cl
  1034.               mov     bl, ch
  1035.               mov     cl, al
  1036.               and     cl, 0fh
  1037.               add     cl, THRESHOLD
  1038.               inc     cl
  1039.   @Decode5:   and     bx, N - 1
  1040.               PUSH    SI
  1041.               LES     SI,[TextBufP]
  1042.               MOV     AL,BYTE PTR [ES:SI+BX]
  1043.               ADD     SI,DI
  1044.               MOV     BYTE PTR [ES:SI],AL
  1045.               POP     SI
  1046. {              mov     al, byte ptr [Offset TextBuf + bx]
  1047.               mov     byte ptr [Offset TextBuf + di], al}
  1048.               inc     di
  1049.               and     di, N - 1
  1050.               call    putc
  1051.               inc     bx
  1052.               dec     cl
  1053.               jnz     @Decode5
  1054.               jmp     @Decode2
  1055.   @Decode9:
  1056. End; { Decode }
  1057.  
  1058. Function LZInit : boolean;
  1059. Begin
  1060.   if Initialized then Exit;
  1061.   LZInit := False;
  1062.   New(InBufP);
  1063.   New(OutBufP);
  1064.   New(TextBufP);
  1065.   New(LeftP);
  1066.   New(MomP);
  1067.   New(RightP);
  1068.   Initialized := (InBufP <> nil) and (OutBufP <> nil) and
  1069.     (TextBufP <> nil) and (LeftP <> nil) and (MomP <> nil) and (RightP <> nil);
  1070.   if Initialized then LZInit := True else
  1071.   begin
  1072.     Initialized := True;
  1073.     LZDone
  1074.   end
  1075. End; { LZInit }
  1076.  
  1077. Procedure LZDone;
  1078. Begin
  1079.   if Initialized then
  1080.   begin
  1081.     Dispose(InBufP);
  1082.     Dispose(OutBufP);
  1083.     Dispose(RightP);
  1084.     Dispose(MomP);
  1085.     Dispose(LeftP);
  1086.     Dispose(TextBufP);
  1087.     Initialized := False
  1088.   end
  1089. End; { LZDone }
  1090.  
  1091. Procedure LZSquash;
  1092. Begin
  1093.   if Initialized then
  1094.   begin
  1095.     InBufPtr := LZRWBufSize;
  1096.     InBufSize := LZRWBufSize;
  1097.     OutBufPtr := 0;
  1098.     Height := 0;
  1099.     MatchPos := 0;
  1100.     MatchLen := 0;
  1101.     LastLen := 0;
  1102.  
  1103.     FillChar(TextBufP^, SizeOf(TLZTextBuf), 0);
  1104.     FillChar(LeftP^, SizeOf(TLeftMomTree), 0);
  1105.     FillChar(MomP^, SizeOf(TLeftMomTree), 0);
  1106.     FillChar(RightP^, SizeOf(TRightTree), 0);
  1107.     FillChar(CodeBuf, SizeOf(CodeBuf), 0);
  1108.  
  1109.     LZReadProc := ReadProc;
  1110.     LZWriteProc := WriteProc;
  1111.  
  1112.     Encode;
  1113.     LZSS_Write
  1114.   end
  1115. End; { LZSquash }
  1116.  
  1117. Procedure LZUnSquash;
  1118. Begin
  1119.   if Initialized then
  1120.   begin
  1121.     InBufPtr := LZRWBufSize;
  1122.     InBufSize := LZRWBufSize;
  1123.     OutBufPtr := 0;
  1124.     FillChar(TextBufP^, SizeOf(TLZTextBuf), 0);
  1125.  
  1126.     LZReadProc := ReadProc;
  1127.     LZWriteProc := WriteProc;
  1128.  
  1129.     Decode;
  1130.     LZSS_Write
  1131.   end
  1132. End; { LZUnSquash }
  1133.  
  1134. {$IFDEF Windows}
  1135. Function HeapFunc(Size : word) : integer; far; assembler;
  1136. Asm
  1137.   MOV AX,1
  1138. End; { HeapFunc }
  1139. {$ENDIF}
  1140.  
  1141. Begin
  1142. {$IFDEF Windows}
  1143.   HeapError := @HeapFunc;
  1144. {$ENDIF}
  1145.   Initialized := False
  1146. End. { LZSSUNIT }