home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / enterprs / c128 / text / hacking6.arc / LZW.TXT < prev    next >
Text File  |  1993-09-16  |  23KB  |  766 lines
  1. =============================================================================
  2. LZW Compression
  3. by Bill Lucier (Blucier@ersys.edmonton.ab.ca, b.lucier1 on Genie)
  4.  
  5. LZW is perhaps the most widely used form of data compression today. It
  6. is simple to implement and achieves very decent compression at a fairly
  7. quick pace. LZW is used in PKZIP (shrink),PKARC (crunch), gifs,V.42bis
  8. and unix's compress. This article will attempt to explain how the
  9. compression works with a short example and 6502 source code in Buddy
  10. format.
  11.  
  12. Originally named lz78, it was invented by Jacob Ziv and Abraham Lempel
  13. in 1978 , it was later modified by Terry Welch to its present format.
  14. The patent for the LZW compression method is presently held by Unisys.
  15.  
  16. LZW compresses data by taking phrases and compressing them into codes.
  17. The size of the codes could vary from 9 bits to 16 bits. Although for
  18. this implementation we will be using only 12 bits. As byte are read in
  19. from a file they are added to a dictionary. For a 12-bit implementation
  20. a dictionary will be 4k (2^12=4096) . Each entry in the dictionary
  21. requires five bytes, which will be built in the form of a tree. It is
  22. not a binary tree because each node may have more than two offsprings.
  23. In fact, because our dictionary can hold up to 4096 different codes it
  24. is possible to have one node with 3800 children nodes, although this is
  25. not likely to happen. The five bytes that make up our tree will be:
  26.  
  27. The parent code: Each node has one and only one parent node. When the parent
  28.                  code is less then 255 it is the end of a phrase. The codes
  29.                  0-255 do not actually exist in the tree. The following
  30.                  values do not appear either as they have special meaning:
  31.  
  32.                  256 : End of Stream-This marks the end of one compressed file
  33.                  257 : This tells the decompressor to increase the number
  34.                        of bits its reading by one.
  35.                  258 : Wipe out dictionary
  36.                  
  37. The code value : This is the code that will be sent to the compressor. 
  38. The character  : The value contained at this node. It have a value of 0-255.
  39.  
  40. Initially we send out codes that are 9 bits long, this will cover the values
  41. 0-511. Once we have reached 511, we will need to increase the number of
  42. bits to write by 1. This will give room for code numbers 512-1023, or
  43. (2^10)-1. At this point we must ensure that the decompressor knows how
  44. bits to read in at once so a code number 257 is sent to indicate that
  45. the number of bits to be read is to be bumped up by one. The size of the
  46. dictionary is finite so at some point we do have to be concerned with
  47. what we will do when it does fill up. We could stop compiling new
  48. phrases and just compress with the ones that are already in the
  49. dictionary. This is not a very good choice, files tend to change
  50. frequently (eg. program files as they change from code to data) so
  51. sticking with the same dictionary will actually increase the size of the
  52. file or at best, give poor compression. Another choice is to wipe the
  53. dictionary out and start building new codes and phrases, or wipe out
  54. some of the dictionary leaving behind only the newer codes and phrases.
  55. For the sake of simplicity this program will just wipe out the
  56. dictionary when it becomes full.
  57.  
  58. To illustrate how LZW works a small phrase will be compressed : heher.
  59. To start the first two characters would be read in. The H would be
  60. treated as the parent code and E becomes the character code. By means of
  61. a hashing routine (the hashing routine will be explained more fully in
  62. the source code) the location where HE should be is located. Since we
  63. have just begun there will be nothing there,so the phrase will be added
  64. to the dictionary. The codes 0-258 are already taken so we start using
  65. 259 as our first code. The binary tree would look something like this:
  66.             
  67.           node # 72 - H
  68.                  |
  69.      node #3200 259 - E
  70.  
  71.  The node # for E is an arbitrary one. The compressor may not choose
  72. that location, 3200 is used strictly for demonstration purposes. So at
  73. node #3200 the values would be:
  74.  
  75. Parent code - 72
  76. code value  - 259
  77. character   - E
  78.  
  79. The node #72 is not actually used. As soon as a value less than 255 is
  80. found it is assumed to be the actual value. We can't compress this yet
  81. so the value 72 is sent to the output file(remember that it is sent in 9
  82. bits). The E then becomes the parent code and a new character code ( H )
  83. is read in. After again searching the dictionary the phrase EH is not
  84. found. It is added to the dictionary as code number 260. Then we send
  85. the E to the disk and H becomes the new parent code and the next E
  86. becomes the new character code. After searching the dictionary we find
  87. that we can compress HE into the code 259,we want to compress as much as
  88. possible into one code so we make 259 the parent code. There may be a
  89. longer string then HE that can be compressed. The R is read in as the
  90. new character code. The dictionary is searched for the a 259 followed a
  91. R, since it is not found it is added to the dictioary and it looks like
  92. this:
  93.  
  94.            node #72 - H             node #69 - E
  95.                  |                        | 
  96.     node #3200  259 - E    node #1600    260 - H
  97.                  |
  98.     node #1262  261 - R
  99.  
  100. Then the value 259 is sent to the output file (to represent the HE) and
  101. since that is the EOF the R is sent as well,as well as a 256 to indicate
  102. the EOF has been reached.
  103.  
  104. Decompression is extremely simple. As long as the decompressor maintains
  105. the dictionary as the compressor did, there will be no problems,except
  106. for one problem that can be handled as an exceptional case. All of the
  107. little details of increasing the number of bits to read, and when to
  108. flush the dictionary are taken care of by the compressor. So if the
  109. dictionary was increased to 8k, the compressor would have to be set up
  110. to handle a larger dictionary, but the decompressor only does as the
  111. compressed file tells it to and will work with any size dictionary. The
  112. only problem would be that a larger dictionary will creep into the ram
  113. under the rom or possibly even use all available memory, but assuming
  114. that the ram is available the decompressor will not change. The
  115. decompressor would start out reading 9 bits at a time, and starts it
  116. free code at 259 as the compressor did. To use the above input from the
  117. compressor as an example, the output was:
  118.  
  119. 72  - For the First H
  120. 69  - For the First E
  121. 259 - For the Compressed HE
  122. 82  - For the R
  123. 256 - Eof indicator
  124.  
  125.  To begin decompressing, two values are needed. The H and E are read in,
  126. (note they will both be 9 bits long). As they are both below 256 they
  127. are at the end of the string and are sent straight to the output file.
  128. The first free code is 259 so that is the value assigned to the phrase
  129. HE. Note when decompressing there is no need for the hashing routine,
  130. the codes are the absolute locations in the dictionary (i.e. If the
  131. dictionary was considered to be an array then the entry number 259 would
  132. be dictionary[259]), because of this, the code value is no longer
  133. needed. So the decompressor would have an entry that looks like this:
  134.  
  135. Node # 259
  136. Parent Code - H
  137. Character   - E
  138.  
  139. The decompressor will read in the next value (259). Because the node
  140. number is at the end of the compressed string we will have to take the
  141. code value and place it on a stack, and take them off in a
  142. Last-in,First-out (LIFO) fashion. That is to say that the first
  143. character to go on the stack (in this case the E) will be the last to
  144. come off. The size of the stack is dependent on the size of the
  145. dictionary, so for this implementation we need a stack that is 4k long.
  146. After all the characters from the string have been placed on the stack
  147. they are taken off and sent to the outputfile.
  148.  
  149.   There is one small error that is possible with LZW because of the way
  150. the compressor defines strings. Consider the compression dictionary that
  151. has the following in it:
  152.  
  153.      node #   Code         Parent  character 
  154.               Value         code 
  155.      ------   ------        ------  ---------
  156.         65      65           n/a       A 
  157.        723     259            65       C
  158.       1262     260           259       U
  159.       2104     261           260       T
  160.       2506     262           261       E
  161.  
  162. Now if the compressor was to try to compress the string ACUTEACUTEA The
  163. compressor will find a match for the first five characters 'ACUTE' and
  164. will send a 262 to the output file. Then it will add the following entry
  165. to the dictionary:
  166.  
  167.       3099     263           262       A
  168.  
  169. Now it will try to compress the remaining characters, and it finds that
  170. it can compress the entire string with the code 263, but notice that the
  171. middle A, the one that was just added onto the end of the string 'ACUTE'
  172. was never sent to the output file. The decompressor will not have the
  173. code 263 defined in it's dictionary. The last code it will have defined
  174. will be 262. This problem is easily remedied though, when the
  175. decompressor does not have a code defined, it takes the first letter
  176. from the last phrase defined and tacks it onto the end of the last
  177. phrase. IE It takes the first letter (the A) from the phrase and adds it
  178. on to the end as code #263.
  179.  
  180. This particular implementation is fairly slow because it reads a byte
  181. and then writes one, it could be made much faster with some buffering.
  182. It is also limited to compressing and decompressing one file at a time
  183. and has no error checking capabilities. It is meant strictly to teach
  184. LZW compression, not provide a full fledged compressor.
  185.  
  186. And now for the code:
  187.   
  188. SYS 4000      ; sys 999 on a 64
  189. .DVO 9        ; or whatever drive used for output
  190. .ORG 2500
  191. .OBJ "LZW.ML"
  192.  
  193. TABLESIZE =5021     
  194.  
  195. ; THE TABLESIZE IS ACTUALLY 5021, ABOUT 20% LARGER THEN 4K. THIS GIVES
  196. ; THE HASHING ROUTINE SOME ROOM TO MOVE. IF THE TABLE WAS EXACTLY 4K
  197. ; THERE WOULD BE FREQUENT COLLISIONS WHERE DIFFERENT COMBINATIONS OF
  198. ; CHARACTERS WOULD HAVE THE SAME HASH ADDRESS. INCREASING THE TABLE SIZE
  199. ; REDUCES THE NUMBER OF COLLISIONS.
  200.  
  201. EOS =256          ; eos = End of stream This marks the end of file
  202.  
  203. FIRSTCODE =259
  204. MAXCODE =4096
  205.  
  206. BUMPCODE =257     ; Whenever a 257 is encountered by the decompressor it
  207.                   ; increases the number of bits it reads by 1
  208.  
  209. FLUSHCODE =258   
  210.  
  211. TABLEBASE =14336  ; The location that the dictionary is located at
  212.  
  213. DECODESTACK =9300 ; The location of the 4k LIFO stack
  214.  
  215. ; ORG = DECOMPRESS FILE
  216. ; ORG + 3 = COMPRESS FILE
  217.  
  218. JMP EXPANDFILE
  219.  
  220. ;********************************
  221. ; COMPRESSFILE
  222. ;********************************
  223.  
  224. COMPRESSFILE JSR INITDIC ; EMPTY THE DICTIONARY
  225. LDA #128
  226. STA BITMASK
  227. LDA #0
  228. STA RACK
  229. JSR GETCHAR      ; GET A CHAR FROM THE INPUT FILE
  230. STA STRINGCODE   ; INITIALIZE THE STRINGCODE (PARENT CODE)
  231. LDA #0
  232. STA STRINGCODE+1
  233. NEXTCHAR JSR GETCHAR
  234.          STA CHARACTER
  235.          JSR FINDNODE    ; FINDNODE CALCULATES THE HASHED LOCATION OF
  236.          LDA ($FE),Y     ; THE STRINGCODE AND CHARACTER  IN THE DICT.
  237.          INY             ; AND SETS $FE/$FF POINTING TO IT. IF THE ENTRY
  238.          AND ($FE),Y     ; HAS TWO 255 IN IT THEN IT IS EMPTY AND SHOULD
  239.          CMP #255        ; BE ADDED TO THE DICTIONARY.
  240.          BEQ ADDTODICT
  241.              LDA ($FE),Y     ; IT HAS A DEFINED PHRASE. STORE THE CODE VALUE IN
  242.              STA STRINGCODE+1; THE PARENT CODE
  243.              DEY
  244.              LDA ($FE),Y
  245.              STA STRINGCODE
  246.          JMP EOF
  247.          ADDTODICT LDY #0
  248.          - LDA NEXTCODE,Y
  249.            STA ($FE),Y
  250.            INY
  251.            CPY #5
  252.          BNE -
  253.          INC NEXTCODE             ; INCREASE THE NEXTCODE
  254.          BNE +
  255.              INC NEXTCODE+1
  256.          + JSR OUTPUT
  257.          LDA NEXTCODE+1          ; CHECK IF NEXTCODE=4096 IF SO THEN FLUSH THE
  258.          CMP #>MAXCODE           ; DICTIONARY AND START ANEW
  259.          BNE CHECKBUMP
  260.          LDA NEXTCODE
  261.          CMP #<MAXCODE
  262.          BNE CHECKBUMP
  263.          LDA #<FLUSHCODE        ; SEND THE FLUSH CODE TO THE COMPRESSED FILE SO
  264.          STA STRINGCODE         ; THE DECOMPRESSOR WILL KNOW TO FLUSH THE
  265.          LDA #>FLUSHCODE        ; DICTIONARY
  266.          STA STRINGCODE+1
  267.          JSR OUTPUT
  268.          JSR INITDIC
  269.          JMP CHECKEOF
  270.          CHECKBUMP LDA NEXTBUMP+1
  271.          CMP NEXTCODE+1         ; CHECKBUMP CHECK TO SEE IF THE NEXTCODE HAS
  272.          BNE CHECKEOF        ; REACHED THE MAXIMUM VALUE FOR THE CURRENT
  273.          LDA NEXTBUMP                    ; NUMBER OF BITS BEING OUTPUT.
  274.          CMP NEXTCODE        ; FOR     X  BITS     NEXTCODE HAS Y PHRASES
  275.          BNE CHECKEOF        ;        --------     -----------------------
  276.          LDA #>BUMPCODE      ;           9                 511
  277.          STA STRINGCODE+1    ;          10                1023
  278.          LDA #<BUMPCODE      ;          11                2047
  279.          STA STRINGCODE      ;          12                4095
  280.          JSR OUTPUT
  281.          INC CURRENTBITS
  282.          ASL NEXTBUMP
  283.          ROL NEXTBUMP+1
  284.          CHECKEOF LDA #0
  285.          STA STRINGCODE+1
  286.          LDA CHARACTER
  287.          STA STRINGCODE
  288.          EOF LDA 144
  289.          BNE DONE
  290. JMP NEXTCHAR
  291. DONE JSR OUTPUT
  292. LDA #>EOS               ; SEND A 256 TO INDICATE EOF
  293. STA STRINGCODE+1
  294. LDA #<EOS
  295. STA STRINGCODE
  296. JSR OUTPUT
  297. LDA BITMASK
  298. BEQ +
  299.     JSR $FFCC
  300.     LDX #3
  301.     JSR $FFC9
  302.     LDA RACK              ; SEND WHAT BITS WEREN'T SEND WHEN OUTPUT
  303.     JSR $FFD2
  304. + JSR $FFCC
  305. LDA #3
  306. JSR $FFC3
  307. LDA #2
  308. JMP $FFC3
  309.  
  310. ;**********************************
  311. ; INITDIC
  312. ; INITIALIZES THE DICTIONARY, SETS
  313. ; THE NUMBER OF BITS TO 9
  314. ;**********************************
  315.  
  316. INITDIC LDA #9
  317. STA CURRENTBITS
  318. LDA #>FIRSTCODE
  319. STA NEXTCODE+1
  320. LDA #<FIRSTCODE
  321. STA NEXTCODE
  322. LDA #>512
  323. STA NEXTBUMP+1
  324. LDA #<512
  325. STA NEXTBUMP
  326. LDA #<TABLEBASE
  327. STA $FE
  328. LDA #>TABLEBASE
  329. STA $FF
  330. LDA #<TABLESIZE
  331. STA $FC
  332. LDA #>TABLESIZE
  333. STA $FD
  334. - LDY #0
  335.   LDA #255      ; ALL THE CODE VALUES ARE INIT TO 255+256*255
  336.   STA ($FE),Y   ; OR -1 IN TWO COMPLEMENT
  337.   INY
  338.   STA ($FE),Y
  339.   CLC
  340.   LDA #5        ; EACH ENTRY IN THE TABLE TAKES 5 BYTES
  341.   ADC $FE
  342.   STA $FE
  343.   BCC +
  344.       INC $FF
  345.   + LDA $FC
  346.   BNE +
  347.       DEC $FD
  348.   + DEC $FC
  349.   LDA $FD
  350.   ORA $FC
  351. BNE -
  352. RTS
  353.  
  354. ;************************************
  355. ; GETCHAR
  356. ;************************************
  357.  
  358. GETCHAR JSR $FFCC
  359. LDX #2
  360. JSR $FFC6
  361. JMP $FFCF
  362.  
  363. ;************************************
  364. ; OUTPUT
  365. ;************************************
  366.  
  367. OUTPUT LDA #0      ; THE NUMBER OF BITS OUTPUT CAN BE OF A VARIABLE
  368. STA MASK+1         ; LENGTH,SO THE BITS ARE ACCUMULATED TO A BYTE IS
  369. LDA #1             ; FULL AND THEN IT IS SENT TO THE OUTPUT FILE
  370. LDX CURRENTBITS
  371. DEX
  372. - ASL
  373.   ROL MASK+1
  374.   DEX
  375. BNE -
  376. STA MASK
  377. MASKDONE LDA MASK
  378. ORA MASK+1
  379. BNE +
  380.     RTS
  381. + LDA MASK
  382. AND STRINGCODE
  383. STA 3
  384. LDA MASK+1
  385. AND STRINGCODE+1
  386. ORA 3
  387. BEQ NOBITON
  388.     LDA RACK
  389.     ORA BITMASK
  390.     STA RACK
  391. NOBITON LSR BITMASK
  392. LDA BITMASK
  393. BNE +
  394.     JSR $FFCC
  395.     LDX #3
  396.     JSR $FFC9
  397.     LDA RACK
  398.     JSR $FFD2
  399.     LDA #0
  400.     STA RACK
  401.     LDA #128
  402.     STA BITMASK
  403. + LSR MASK+1
  404. ROR MASK
  405. JMP MASKDONE
  406.  
  407. ;******************************
  408. ; FINDNODE
  409. ; THIS SEARCHES THE DICTIONARY TILL IT FINDS A PARENT NODE THAT MATCHES
  410. ; THE STRINGCODE AND A CHILD NODE THAT MATCHES THE CHARACTER OR A EMPTY
  411. ; NODE.
  412. ;*******************************
  413.  
  414. ; THE HASHING FUNCTION - THE HASHING FUNCTION IS NEEDED BECAUSE
  415. ; THERE ARE 4096 X 4096 (16 MILLION) DIFFERENT COMBINATIONS OF
  416. ; CHARACTER AND STRINGCODE. BY MULTIPLYING THE CHARACTER AND STRINGCODE
  417. ; IN A FORMULA WE CAN DEVELOP OF METHOD OF FINDING THEM IN THE
  418. ; DICTIONARY. IF THE STRINGCODE AND CHARACTER IN THE DICTIONARY
  419. ; DON'T MATCH THE ONES WE ARE LOOKING FOR WE CALCULATE AN OFFSET
  420. ; AND SEARCH THE DICTIONARY FOR THE RIGHT MATCH OR A EMPTY
  421. ; SPACE IS FOUND. IF AN EMPTY SPACE IS FOUND THEN THAT CHARACTER AND
  422. ; STRINGCODE COMBINATION IS NOT IN THE DICTIONARY
  423.  
  424. FINDNODE LDA #0
  425. STA INDEX+1
  426. LDA CHARACTER     ; HERE THE HASHING FUNCTION IS APPLIED TO THE
  427. ASL               ; CHARACTER AND THE STRING CODE. FOR THOSE WHO
  428. ROL INDEX+1       ; CARE THE HASHING FORMULA IS:
  429. EOR STRINGCODE    ; (CHARACTER << 1) ^ STRINGCODE
  430. STA INDEX         ; FIND NODE WILL LOOP TILL IT FINDS A NODE
  431. LDA INDEX+1       ; THAT HAS A EMPTY NODE OR MATCHES THE CURRENT
  432. EOR STRINGCODE+1  ; PARENT CODE AND CHARACTER
  433. STA INDEX+1
  434. ORA INDEX 
  435. BNE +
  436.     LDX #1
  437.     STX OFFSET
  438.     DEX
  439.     STX OFFSET+1
  440.     JMP FOREVELOOP
  441. + SEC
  442. LDA #<TABLESIZE
  443. SBC INDEX
  444. STA OFFSET
  445. LDA #>TABLESIZE
  446. SBC INDEX+1
  447. STA OFFSET+1
  448.  
  449. FOREVELOOP JSR CALCULATE     
  450.            LDY #0
  451.            LDA ($FE),Y
  452.            INY
  453.            AND ($FE),Y
  454.            CMP #255
  455.            BNE +
  456.                LDY #0
  457.                RTS
  458.            + INY
  459.            - LDA ($FE),Y
  460.              CMP STRINGCODE-2,Y
  461.              BNE +
  462.              INY
  463.              CPY #5
  464.              BNE -
  465.           LDY #0
  466.           RTS
  467.           + SEC
  468.           LDA INDEX
  469.           SBC OFFSET
  470.           STA INDEX
  471.           LDA INDEX+1
  472.           SBC OFFSET+1
  473.           STA INDEX+1
  474.           AND #128
  475.           BEQ FOREVELOOP
  476.           CLC
  477.           LDA #<TABLESIZE
  478.           ADC INDEX
  479.           STA INDEX
  480.           LDA #>TABLESIZE
  481.           ADC INDEX+1
  482.           STA INDEX+1
  483. JMP FOREVELOOP
  484.  
  485. ;***************************
  486. ; CALCULATE
  487. ; TAKES THE VALUE IN INDEX AND CALCULATES ITS LOCATION IN THE DICTIONARY
  488. ;****************************
  489.  
  490. CALCULATE LDA INDEX
  491. STA $FE
  492. LDA INDEX+1
  493. STA $FF
  494. ASL $FE
  495. ROL $FF
  496. ASL $FE
  497. ROL $FF
  498. CLC
  499. LDA INDEX
  500. ADC $FE
  501. STA $FE
  502. LDA INDEX+1
  503. ADC $FF
  504. STA $FF
  505. CLC
  506. LDA #<TABLEBASE
  507. ADC $FE
  508. STA $FE
  509. LDA #>TABLEBASE
  510. ADC $FF
  511. STA $FF
  512. LDY #0
  513. RTS
  514.  
  515. ;******************************
  516. ; DECODESTRING
  517. ;******************************
  518.  
  519. DECODESTRING TYA   ; DECODESTRING PUTS THE STRING ON THE STACK
  520. STA COUNT          ; IN A LIFO FASHION.
  521. LDX #>DECODESTACK
  522. CLC
  523. ADC #<DECODESTACK
  524. STA $FC
  525. STX $FD
  526. LDA #0
  527. STA COUNT+1
  528. - LDA INDEX+1
  529.   BEQ +
  530.   JSR CALCULATE
  531.   LDY #4
  532.   LDA ($FE),Y
  533.   LDY #0
  534.   STA ($FC),Y
  535.   LDY #2
  536.   LDA ($FE),Y
  537.   STA INDEX
  538.   INY
  539.   LDA ($FE),Y
  540.   STA INDEX+1
  541.   JSR INFC
  542. JMP -
  543. + LDY #0
  544. LDA INDEX
  545. STA ($FC),Y
  546. INC COUNT
  547. BNE +
  548.     INC COUNT+1
  549. + RTS
  550.  
  551. ;******************************
  552. ; INPUT
  553. ;******************************
  554.  
  555. INPUT LDA #0  ; THE INPUT ROUTINES IS USED BY THE DECOMPRESSOR
  556. STA MASK+1    ; TO READ IN THE VARIABLE LENGTH CODES
  557. STA RETURN
  558. STA RETURN+1
  559. LDA #1
  560. LDX CURRENTBITS
  561. DEX
  562. - ASL
  563.   ROL MASK+1
  564.   DEX
  565. BNE -
  566. STA MASK
  567. - LDA MASK
  568.   ORA MASK+1
  569.   BEQ INPUTDONE
  570.   LDA BITMASK
  571.   BPL +
  572.       JSR GETCHAR
  573.       STA RACK
  574.   + LDA RACK
  575.   AND BITMASK
  576.   BEQ +
  577.       LDA MASK
  578.       ORA RETURN
  579.       STA RETURN
  580.       LDA MASK+1
  581.       ORA RETURN+1
  582.       STA RETURN+1
  583.   + LSR MASK+1
  584.   ROR MASK
  585.   LSR BITMASK
  586.   LDA BITMASK
  587.   BNE +
  588.       LDA #128
  589.       STA BITMASK
  590. + JMP -
  591. INPUTDONE RTS
  592.  
  593. ;*******************************
  594. ; EXPANDFILE
  595. ; WHERE THE DECOMPRESSION IS DONE
  596. ;*******************************
  597.  
  598. EXPANDFILE LDA #0
  599. STA RACK
  600. LDA #128
  601. STA BITMASK
  602. START JSR INITDIC
  603. JSR INPUT
  604. LDA RETURN+1
  605. STA OLDCODE+1       ; Save the first character in OLDCODE
  606. LDA RETURN
  607. STA CHARACTER
  608. STA OLDCODE
  609. CMP #<EOS
  610. BNE +
  611.     LDA RETURN+1    ; If return = EOS (256) then all done 
  612.     CMP #>EOS
  613.     BNE +
  614.     JMP CLOSE
  615. + JSR $FFCC
  616. LDX #3
  617. JSR $FFC9
  618. LDA OLDCODE         ; Send oldcode to the output file
  619. JSR $FFD2
  620. NEXT JSR INPUT
  621.      LDA RETURN
  622.      STA NEWCODE
  623.      LDA RETURN+1
  624.      STA NEWCODE+1
  625.      CMP #1         ; All of the special codes Flushcode,BumpCode & EOS
  626.      BNE ++         ; Have 1 for a MSB.
  627.          LDA NEWCODE
  628.          CMP #<BUMPCODE
  629.          BNE +
  630.              INC CURRENTBITS
  631.              JMP NEXT
  632.          + CMP #<FLUSHCODE
  633.          BEQ START
  634.          CMP #<EOS
  635.          BNE +
  636.          JMP CLOSE
  637.      + SEC          ; Here we compare the newcode just read in to the
  638.      LDA NEWCODE    ; next code. If newcode is greater than it is a 
  639.      SBC NEXTCODE   ; ACUTEACUTEA situation and must be handle differently.
  640.      STA 3
  641.      LDA NEWCODE+1 
  642.      SBC NEXTCODE+1
  643.      ORA 3
  644.      BCC +
  645.          LDA CHARACTER
  646.          STA DECODESTACK
  647.          LDA OLDCODE
  648.          STA INDEX
  649.          LDA OLDCODE+1
  650.          STA INDEX+1
  651.          LDY #1
  652.          BNE ++
  653.      + LDA NEWCODE  ; Point index to newcode spot in the dictionary   
  654.      STA INDEX      ; So DECODESTRING has a place to start
  655.      LDA NEWCODE+1
  656.      STA INDEX+1
  657.      LDY #0
  658.      + JSR DECODESTRING
  659.      LDY #0
  660.      LDA ($FC),Y
  661.      STA CHARACTER
  662.      INC $FC
  663.      BNE +
  664.          INC $FD
  665.      + JSR $FFCC
  666.      LDX #3
  667.      JSR $FFC9
  668.      L1 LDA COUNT+1  ; Count contains the number of characters on the stack
  669.         ORA COUNT
  670.         BEQ +       
  671.         JSR DECFC
  672.         LDY #0
  673.         LDA ($FC),Y
  674.         JSR $FFD2
  675.      JMP L1
  676.      + LDA NEXTCODE  ; Calculate the spot in the dictionary for the string
  677.      STA INDEX       ; that was just entered.
  678.      LDA NEXTCODE+1
  679.      STA INDEX+1
  680.      JSR CALCULATE
  681.      LDY #2          ; The last character read in is tacked onto the end
  682.      LDA OLDCODE     ; of the string that was just taken off the stack
  683.      STA ($FE),Y     ; The nextcode is then incremented to prepare for the 
  684.      INY             ; next entry.
  685.      LDA OLDCODE+1
  686.      STA ($FE),Y
  687.      INY
  688.      LDA CHARACTER
  689.      STA ($FE),Y
  690.      INC NEXTCODE
  691.      BNE +
  692.          INC NEXTCODE+1
  693.      + LDA NEWCODE
  694.      STA OLDCODE
  695.      LDA NEWCODE+1
  696.      STA OLDCODE+1
  697. JMP NEXT
  698. CLOSE JSR $FFCC
  699. LDA #2
  700. JSR $FFC3
  701. LDA #3
  702. JMP $FFC3
  703.  
  704. DECFC LDA $FC
  705. BNE +
  706.     DEC $FD
  707. + DEC $FC
  708. LDA COUNT
  709. BNE +
  710.     DEC COUNT+1
  711. + DEC COUNT
  712. RTS
  713. INFC INC $FC
  714. BNE +
  715.     INC $FD
  716. + INC COUNT
  717. BNE +
  718.     INC COUNT+1
  719. + RTS
  720.  
  721. NEXTCODE .WOR 0
  722. STRINGCODE .WOR 0
  723. CHARACTER .BYT 0
  724. NEXTBUMP .WOR 0
  725. CURRENTBITS .BYT 0
  726. RACK .BYT 0
  727. BITMASK .BYT 0
  728. MASK .WOR 0
  729. INDEX .WOR 0
  730. OFFSET .WOR 0
  731. RETURN .WOR 0
  732. COUNT .WOR 0
  733. NEWCODE .WOR 0
  734. OLDCODE .WOR 0
  735. TEST .BYT 0
  736.  
  737. TO DRIVE THE ML I WROTE THIS SMALL BASIC PROGRAM. NOTE THAT CHANNEL TWO IS
  738. ALWAYS THE INPUT AND CHANNEL THREE IS ALWAYS THE OUTPUT. EX AND CO MAY BE
  739. CHANGED TO SUIT WHATEVER LOCATIONS THE PROGRAM IS REASSEMBLED AT.
  740.  
  741. 1 IFA=.THENA=1:LOAD"LZW.ML",PEEK(186),1
  742. 10 EX=2500:CO=2503
  743. 15 PRINT"[E]XPAND OR [C]OMPRESS?"
  744. 20 GETA$:IFA$<>"C"ANDA$<>"E"THEN20
  745. 30 INPUT"NAME OF INPUT FILE";FI$:IFLEN(FI$)=.THEN30
  746. 40 INPUT"NAME OF OUTPUT FILE";FO$:IFLEN(FO$)=.THEN40
  747. 50 OPEN2,9,2,FI$+",P,R":OPEN3,9,3,FO$+",P,W"
  748. 60 IFA$="E"THENSYSEX
  749. 70 IFA$="C"THENSYSCO
  750. 80 END
  751.  
  752. For those interested in learning more about data
  753. compression/decompression I recommend the book 'The Data Compression
  754. Book' written by Mark Nelson. I learned a great deal from reading this
  755. book. It explains all of the major data compression methods. (huffman
  756. coding, dictionary type compression such as LZW, arithmatic coding,
  757. speech compression and lossy graphics compression)
  758.  
  759. Questions or comments are welcome, they may be directed to me at :
  760.  
  761. Internet   : Blucier@ersys.edmonton.ab.ca
  762. Genie      : b.lucier1
  763.  
  764. ===============================================================================
  765.  
  766.