8bitfiles.net/archives

home *** CD-ROM | disk | FTP | other *** search

/ 8bitfiles.net/archives / archives.tar / archives / genie-commodore-file-library / Information / HACKING6E.SFX / hacking6e

Wrap

Text File | 1993-09-17 | 19.0 KB | 699 lines

There is one small error that is possible with LZW because of the way the compressor defines strings. Consider the compression dictionary that has the following in it: node # Code Parent character Value code ------ ------ ------ --------- 65 65 n/a A 723 259 65 C 1262 260 259 U 2104 261 260 T 2506 262 261 E Now if the compressor was to try to compress the string ACUTEACUTEA The compressor will find a match for the first five characters 'ACUTE' and will send a 262 to the output file. Then it will add the following entry to the dictionary: 3099 263 262 A Now it will try to compress the remaining characters, and it finds that it can compress the entire string with the code 263, but notice that the middle A, the one that was just added onto the end of the string 'ACUTE' was never sent to the output file. The decompressor will not have the code 263 defined in it's dictionary. The last code it will have defined will be 262. This problem is easily remedied though, when the decompressor does not have a code defined, it takes the first letter from the last phrase defined and tacks it onto the end of the last phrase. IE It takes the first letter (the A) from the phrase and adds it on to the end as code #263. This particular implementation is fairly slow because it reads a byte and then writes one, it could be made much faster with some buffering. It is also limited to compressing and decompressing one file at a time and has no error checking capabilities. It is meant strictly to teach LZW compression, not provide a full fledged compressor. And now for the code: SYS 4000 ; sys 999 on a 64 .DVO 9 ; or whatever drive used for output .ORG 2500 .OBJ "LZW.ML" TABLESIZE =5021 ; THE TABLESIZE IS ACTUALLY 5021, ABOUT 20% LARGER THEN 4K. THIS GIVES ; THE HASHING ROUTINE SOME ROOM TO MOVE. IF THE TABLE WAS EXACTLY 4K ; THERE WOULD BE FREQUENT COLLISIONS WHERE DIFFERENT COMBINATIONS OF ; CHARACTERS WOULD HAVE THE SAME HASH ADDRESS. INCREASING THE TABLE SIZE ; REDUCES THE NUMBER OF COLLISIONS. EOS =256 ; eos = End of stream This marks the end of file FIRSTCODE =259 MAXCODE =4096 BUMPCODE =257 ; Whenever a 257 is encountered by the decompressor it ; increases the number of bits it reads by 1 FLUSHCODE =258 TABLEBASE =14336 ; The location that the dictionary is located at DECODESTACK =9300 ; The location of the 4k LIFO stack ; ORG = DECOMPRESS FILE ; ORG + 3 = COMPRESS FILE JMP EXPANDFILE ;******************************** ; COMPRESSFILE ;******************************** COMPRESSFILE JSR INITDIC ; EMPTY THE DICTIONARY LDA #128 STA BITMASK LDA #0 STA RACK JSR GETCHAR ; GET A CHAR FROM THE INPUT FILE STA STRINGCODE ; INITIALIZE THE STRINGCODE (PARENT CODE) LDA #0 STA STRINGCODE+1 NEXTCHAR JSR GETCHAR STA CHARACTER JSR FINDNODE ; FINDNODE CALCULATES THE HASHED LOCATION OF LDA ($FE),Y ; THE STRINGCODE AND CHARACTER IN THE DICT. INY ; AND SETS $FE/$FF POINTING TO IT. IF THE ENTRY AND ($FE),Y ; HAS TWO 255 IN IT THEN IT IS EMPTY AND SHOULD CMP #255 ; BE ADDED TO THE DICTIONARY. BEQ ADDTODICT LDA ($FE),Y ; IT HAS A DEFINED PHRASE. STORE THE CODE VALUE IN STA STRINGCODE+1; THE PARENT CODE DEY LDA ($FE),Y STA STRINGCODE JMP EOF ADDTODICT LDY #0 - LDA NEXTCODE,Y STA ($FE),Y INY CPY #5 BNE - INC NEXTCODE ; INCREASE THE NEXTCODE BNE + INC NEXTCODE+1 + JSR OUTPUT LDA NEXTCODE+1 ; CHECK IF NEXTCODE=4096 IF SO THEN FLUSH THE CMP #>MAXCODE ; DICTIONARY AND START ANEW BNE CHECKBUMP LDA NEXTCODE CMP #<MAXCODE BNE CHECKBUMP LDA #<FLUSHCODE ; SEND THE FLUSH CODE TO THE COMPRESSED FILE SO STA STRINGCODE ; THE DECOMPRESSOR WILL KNOW TO FLUSH THE LDA #>FLUSHCODE ; DICTIONARY STA STRINGCODE+1 JSR OUTPUT JSR INITDIC JMP CHECKEOF CHECKBUMP LDA NEXTBUMP+1 CMP NEXTCODE+1 ; CHECKBUMP CHECK TO SEE IF THE NEXTCODE HAS BNE CHECKEOF ; REACHED THE MAXIMUM VALUE FOR THE CURRENT LDA NEXTBUMP ; NUMBER OF BITS BEING OUTPUT. CMP NEXTCODE ; FOR X BITS NEXTCODE HAS Y PHRASES BNE CHECKEOF ; -------- ----------------------- LDA #>BUMPCODE ; 9 511 STA STRINGCODE+1 ; 10 1023 LDA #<BUMPCODE ; 11 2047 STA STRINGCODE ; 12 4095 JSR OUTPUT INC CURRENTBITS ASL NEXTBUMP ROL NEXTBUMP+1 CHECKEOF LDA #0 STA STRINGCODE+1 LDA CHARACTER STA STRINGCODE EOF LDA 144 BNE DONE JMP NEXTCHAR DONE JSR OUTPUT LDA #>EOS ; SEND A 256 TO INDICATE EOF STA STRINGCODE+1 LDA #<EOS STA STRINGCODE JSR OUTPUT LDA BITMASK BEQ + JSR $FFCC LDX #3 JSR $FFC9 LDA RACK ; SEND WHAT BITS WEREN'T SEND WHEN OUTPUT JSR $FFD2 + JSR $FFCC LDA #3 JSR $FFC3 LDA #2 JMP $FFC3 ;********************************** ; INITDIC ; INITIALIZES THE DICTIONARY, SETS ; THE NUMBER OF BITS TO 9 ;********************************** INITDIC LDA #9 STA CURRENTBITS LDA #>FIRSTCODE STA NEXTCODE+1 LDA #<FIRSTCODE STA NEXTCODE LDA #>512 STA NEXTBUMP+1 LDA #<512 STA NEXTBUMP LDA #<TABLEBASE STA $FE LDA #>TABLEBASE STA $FF LDA #<TABLESIZE STA $FC LDA #>TABLESIZE STA $FD - LDY #0 LDA #255 ; ALL THE CODE VALUES ARE INIT TO 255+256*255 STA ($FE),Y ; OR -1 IN TWO COMPLEMENT INY STA ($FE),Y CLC LDA #5 ; EACH ENTRY IN THE TABLE TAKES 5 BYTES ADC $FE STA $FE BCC + INC $FF + LDA $FC BNE + DEC $FD + DEC $FC LDA $FD ORA $FC BNE - RTS ;************************************ ; GETCHAR ;************************************ GETCHAR JSR $FFCC LDX #2 JSR $FFC6 JMP $FFCF ;************************************ ; OUTPUT ;************************************ OUTPUT LDA #0 ; THE NUMBER OF BITS OUTPUT CAN BE OF A VARIABLE STA MASK+1 ; LENGTH,SO THE BITS ARE ACCUMULATED TO A BYTE IS LDA #1 ; FULL AND THEN IT IS SENT TO THE OUTPUT FILE LDX CURRENTBITS DEX - ASL ROL MASK+1 DEX BNE - STA MASK MASKDONE LDA MASK ORA MASK+1 BNE + RTS + LDA MASK AND STRINGCODE STA 3 LDA MASK+1 AND STRINGCODE+1 ORA 3 BEQ NOBITON LDA RACK ORA BITMASK STA RACK NOBITON LSR BITMASK LDA BITMASK BNE + JSR $FFCC LDX #3 JSR $FFC9 LDA RACK JSR $FFD2 LDA #0 STA RACK LDA #128 STA BITMASK + LSR MASK+1 ROR MASK JMP MASKDONE ;****************************** ; FINDNODE ; THIS SEARCHES THE DICTIONARY TILL IT FINDS A PARENT NODE THAT MATCHES ; THE STRINGCODE AND A CHILD NODE THAT MATCHES THE CHARACTER OR A EMPTY ; NODE. ;******************************* ; THE HASHING FUNCTION - THE HASHING FUNCTION IS NEEDED BECAUSE ; THERE ARE 4096 X 4096 (16 MILLION) DIFFERENT COMBINATIONS OF ; CHARACTER AND STRINGCODE. BY MULTIPLYING THE CHARACTER AND STRINGCODE ; IN A FORMULA WE CAN DEVELOP OF METHOD OF FINDING THEM IN THE ; DICTIONARY. IF THE STRINGCODE AND CHARACTER IN THE DICTIONARY ; DON'T MATCH THE ONES WE ARE LOOKING FOR WE CALCULATE AN OFFSET ; AND SEARCH THE DICTIONARY FOR THE RIGHT MATCH OR A EMPTY ; SPACE IS FOUND. IF AN EMPTY SPACE IS FOUND THEN THAT CHARACTER AND ; STRINGCODE COMBINATION IS NOT IN THE DICTIONARY FINDNODE LDA #0 STA INDEX+1 LDA CHARACTER ; HERE THE HASHING FUNCTION IS APPLIED TO THE ASL ; CHARACTER AND THE STRING CODE. FOR THOSE WHO ROL INDEX+1 ; CARE THE HASHING FORMULA IS: EOR STRINGCODE ; (CHARACTER << 1) ^ STRINGCODE STA INDEX ; FIND NODE WILL LOOP TILL IT FINDS A NODE LDA INDEX+1 ; THAT HAS A EMPTY NODE OR MATCHES THE CURRENT EOR STRINGCODE+1 ; PARENT CODE AND CHARACTER STA INDEX+1 ORA INDEX BNE + LDX #1 STX OFFSET DEX STX OFFSET+1 JMP FOREVELOOP + SEC LDA #<TABLESIZE SBC INDEX STA OFFSET LDA #>TABLESIZE SBC INDEX+1 STA OFFSET+1 FOREVELOOP JSR CALCULATE LDY #0 LDA ($FE),Y INY AND ($FE),Y CMP #255 BNE + LDY #0 RTS + INY - LDA ($FE),Y CMP STRINGCODE-2,Y BNE + INY CPY #5 BNE - LDY #0 RTS + SEC LDA INDEX SBC OFFSET STA INDEX LDA INDEX+1 SBC OFFSET+1 STA INDEX+1 AND #128 BEQ FOREVELOOP CLC LDA #<TABLESIZE ADC INDEX STA INDEX LDA #>TABLESIZE ADC INDEX+1 STA INDEX+1 JMP FOREVELOOP ;*************************** ; CALCULATE ; TAKES THE VALUE IN INDEX AND CALCULATES ITS LOCATION IN THE DICTIONARY ;**************************** CALCULATE LDA INDEX STA $FE LDA INDEX+1 STA $FF ASL $FE ROL $FF ASL $FE ROL $FF CLC LDA INDEX ADC $FE STA $FE LDA INDEX+1 ADC $FF STA $FF CLC LDA #<TABLEBASE ADC $FE STA $FE LDA #>TABLEBASE ADC $FF STA $FF LDY #0 RTS ;****************************** ; DECODESTRING ;****************************** DECODESTRING TYA ; DECODESTRING PUTS THE STRING ON THE STACK STA COUNT ; IN A LIFO FASHION. LDX #>DECODESTACK CLC ADC #<DECODESTACK STA $FC STX $FD LDA #0 STA COUNT+1 - LDA INDEX+1 BEQ + JSR CALCULATE LDY #4 LDA ($FE),Y LDY #0 STA ($FC),Y LDY #2 LDA ($FE),Y STA INDEX INY LDA ($FE),Y STA INDEX+1 JSR INFC JMP - + LDY #0 LDA INDEX STA ($FC),Y INC COUNT BNE + INC COUNT+1 + RTS ;****************************** ; INPUT ;****************************** INPUT LDA #0 ; THE INPUT ROUTINES IS USED BY THE DECOMPRESSOR STA MASK+1 ; TO READ IN THE VARIABLE LENGTH CODES STA RETURN STA RETURN+1 LDA #1 LDX CURRENTBITS DEX - ASL ROL MASK+1 DEX BNE - STA MASK - LDA MASK ORA MASK+1 BEQ INPUTDONE LDA BITMASK BPL + JSR GETCHAR STA RACK + LDA RACK AND BITMASK BEQ + LDA MASK ORA RETURN STA RETURN LDA MASK+1 ORA RETURN+1 STA RETURN+1 + LSR MASK+1 ROR MASK LSR BITMASK LDA BITMASK BNE + LDA #128 STA BITMASK + JMP - INPUTDONE RTS ;******************************* ; EXPANDFILE ; WHERE THE DECOMPRESSION IS DONE ;******************************* EXPANDFILE LDA #0 STA RACK LDA #128 STA BITMASK START JSR INITDIC JSR INPUT LDA RETURN+1 STA OLDCODE+1 ; Save the first character in OLDCODE LDA RETURN STA CHARACTER STA OLDCODE CMP #<EOS BNE + LDA RETURN+1 ; If return = EOS (256) then all done CMP #>EOS BNE + JMP CLOSE + JSR $FFCC LDX #3 JSR $FFC9 LDA OLDCODE ; Send oldcode to the output file JSR $FFD2 NEXT JSR INPUT LDA RETURN STA NEWCODE LDA RETURN+1 STA NEWCODE+1 CMP #1 ; All of the special codes Flushcode,BumpCode & EOS BNE ++ ; Have 1 for a MSB. LDA NEWCODE CMP #<BUMPCODE BNE + INC CURRENTBITS JMP NEXT + CMP #<FLUSHCODE BEQ START CMP #<EOS BNE + JMP CLOSE + SEC ; Here we compare the newcode just read in to the LDA NEWCODE ; next code. If newcode is greater than it is a SBC NEXTCODE ; ACUTEACUTEA situation and must be handle differently. STA 3 LDA NEWCODE+1 SBC NEXTCODE+1 ORA 3 BCC + LDA CHARACTER STA DECODESTACK LDA OLDCODE STA INDEX LDA OLDCODE+1 STA INDEX+1 LDY #1 BNE ++ + LDA NEWCODE ; Point index to newcode spot in the dictionary STA INDEX ; So DECODESTRING has a place to start LDA NEWCODE+1 STA INDEX+1 LDY #0 + JSR DECODESTRING LDY #0 LDA ($FC),Y STA CHARACTER INC $FC BNE + INC $FD + JSR $FFCC LDX #3 JSR $FFC9 L1 LDA COUNT+1 ; Count contains the number of characters on the stack ORA COUNT BEQ + JSR DECFC LDY #0 LDA ($FC),Y JSR $FFD2 JMP L1 + LDA NEXTCODE ; Calculate the spot in the dictionary for the string STA INDEX ; that was just entered. LDA NEXTCODE+1 STA INDEX+1 JSR CALCULATE LDY #2 ; The last character read in is tacked onto the end LDA OLDCODE ; of the string that was just taken off the stack STA ($FE),Y ; The nextcode is then incremented to prepare for the INY ; next entry. LDA OLDCODE+1 STA ($FE),Y INY LDA CHARACTER STA ($FE),Y INC NEXTCODE BNE + INC NEXTCODE+1 + LDA NEWCODE STA OLDCODE LDA NEWCODE+1 STA OLDCODE+1 JMP NEXT CLOSE JSR $FFCC LDA #2 JSR $FFC3 LDA #3 JMP $FFC3 DECFC LDA $FC BNE + DEC $FD + DEC $FC LDA COUNT BNE + DEC COUNT+1 + DEC COUNT RTS INFC INC $FC BNE + INC $FD + INC COUNT BNE + INC COUNT+1 + RTS NEXTCODE .WOR 0 STRINGCODE .WOR 0 CHARACTER .BYT 0 NEXTBUMP .WOR 0 CURRENTBITS .BYT 0 RACK .BYT 0 BITMASK .BYT 0 MASK .WOR 0 INDEX .WOR 0 OFFSET .WOR 0 RETURN .WOR 0 COUNT .WOR 0 NEWCODE .WOR 0 OLDCODE .WOR 0 TEST .BYT 0 TO DRIVE THE ML I WROTE THIS SMALL BASIC PROGRAM. NOTE THAT CHANNEL TWO IS ALWAYS THE INPUT AND CHANNEL THREE IS ALWAYS THE OUTPUT. EX AND CO MAY BE CHANGED TO SUIT WHATEVER LOCATIONS THE PROGRAM IS REASSEMBLED AT. 1 IFA=.THENA=1:LOAD"LZW.ML",PEEK(186),1 10 EX=2500:CO=2503 15 PRINT"[E]XPAND OR [C]OMPRESS?" 20 GETA$:IFA$<>"C"ANDA$<>"E"THEN20 30 INPUT"NAME OF INPUT FILE";FI$:IFLEN(FI$)=.THEN30 40 INPUT"NAME OF OUTPUT FILE";FO$:IFLEN(FO$)=.THEN40 50 OPEN2,9,2,FI$+",P,R":OPEN3,9,3,FO$+",P,W" 60 IFA$="E"THENSYSEX 70 IFA$="C"THENSYSCO 80 END For those interested in learning more about data compression/decompression I recommend the book 'The Data Compression Book' written by Mark Nelson. I learned a great deal from reading this book. It explains all of the major data compression methods. (huffman coding, dictionary type compression such as LZW, arithmatic coding, speech compression and lossy graphics compression) Questions or comments are welcome, they may be directed to me at : Internet : Blucier@ersys.edmonton.ab.ca Genie : b.lucier1 ------------------------------------------------------------------------------ begin 644 lzw.ml MQ`E,N`P@GPJI@(WT#:D`C?,-(.L*C>T-J0"-[@T@ZPJ-[PT@6`NQ_L@Q_LG_ M\`ZQ_HWN#8BQ_HWM#4QH"J``N>L-D?[(P`70]N[K#=`#[NP-(/8*K>P-R1#0 M&JWK#<D`T!.I`HWM#:D!C>X-(/8*()\*3%T*K?$-S>P-T!ZM\`W-ZPW0%JD! MC>X-J0&-[0T@]@KN\@T.\`TN\0VI`(WN#:WO#8WM#:60T`-,WPD@]@JI`8WN M#:D`C>T-(/8*K?0-\`X@S/^B`R#)_ZWS#2#2_R#,_ZD#(,/_J0),P_^I"8WR M#:D!C>P-J0.-ZPVI`HWQ#:D`C?`-J0"%_JDXA?^IG87\J1.%_:``J?^1_LB1 M_ABI!67^A?Z0`N;_I?S0`L;]QORE_07\T-Y@(,S_H@(@QO],S_^I`(WV#:D! MKO(-R@HN]@W*T/F-]0VM]0T-]@W0`6"M]0TM[0V%`ZWV#2WN#04#\`FM\PT- M]`V-\PU.]`VM]`W0&"#,_Z(#(,G_K?,-(-+_J0"-\PVI@(WT#4[V#6[U#4P+ M"ZD`C?@-K>\-"B[X#4WM#8WW#:WX#4WN#8WX#=`1K?<-T`RB`8[Y#<J.^@U, MEPLXJ9WM]PV-^0VI$^WX#8WZ#2#C"Z``L?[(,?[)_]`#H`!@R+'^V>L-T`C( MP`70]*``8#BM]PWM^0V-]PVM^`WM^@V-^`TI@/`1&*F=;?<-C?<-J1-M^`V- M^`U,EPNM]PV%_JWX#87_!OXF_P;^)O\8K?<-9?Z%_JWX#67_A?\8J0!E_H7^ MJ3AE_X7_H`!@F(W]#:(D&&E4A?R&_:D`C?X-K?@-\!X@XPN@!+'^H`"1_*`" ML?Z-]PW(L?Z-^`T@W`U,)@R@`*WW#9'\[OT-T`/N_@U@J0"-]@V-^PV-_`VI M`:[R#<H*+O8-RM#YC?4-K?4-#?8-\#NM]`T0!B#K"HWS#:WS#2WT#?`2K?4- M#?L-C?L-K?8-#?P-C?P-3O8-;O4-3O0-K?0-T`6I@(WT#4QT#&"I`(WS#:F` MC?0-()\*(%D,K?P-C0(.K?L-C>\-C0$.R0#0"JW\#<D!T`-,NPT@S/^B`R#) M_ZT!#B#2_R!9#*W[#8W_#:W\#8T`#LD!T!BM_PW)`=`&[O(-3/,,R0+PJ\D` MT`-,NPTXK?\-[>L-A0.M``[M[`T%`Y`6K>\-C50DK0$.C?<-K0(.C?@-H`'0 M#JW_#8WW#:T`#HWX#:``(!0,H`"Q_(WO#>;\T`+F_2#,_Z(#(,G_K?X-#?T- M\`T@R`V@`+'\(-+_3&T-K>L-C?<-K>P-C?@-(.,+H`*M`0Z1_LBM`@Z1_LBM M[PV1_N[K#=`#[NP-K?\-C0$.K0`.C0(.3/,,(,S_J0(@P_^I`TS#_Z7\T`+& M_<;\K?T-T`/._@W._0U@YOS0`N;][OT-T`/N_@U@```````````````````` *```````````````` ` end crc32 for lzw.ml = 2460116527 begin 644 lzw.bas M`0@<"`$`BT&R+J=!LC$ZDR),6E<N34PB+#DL,0`P"`H`15BR,C4P,#I#3[(R M-3`S`%`(#P"9(I,219)84$%.1"!/4B`20Y)/35!215-3/R(`;`@4`*%!)#J+ M022SL2)#(J]!)+.Q(D4BIS(P`)<('@"%(DY!344@3T8@24Y0550@1DE,12([ M1DDD.HO#*$9))"FR+J<S,`##""@`A2).04U%($]&($]55%!55"!&24Q%(CM& M3R0ZB\,H1D\D*;(NIS0P`.L(,@"?,BPY+#(L1DDDJB(L4RQ2(CJ?,RPY+#,L M1D\DJB(L4"Q7(@#["#P`BT$DLB)%(J>>15@`"PE&`(M!)+(B0R*GGD-/```` ` end crc32 for lzw.bas = 100674089 =============================================================================== THREE-KEY ROLLOVER for the C-128 and C-64. by Craig Bruce <csbruce@neumann.uwaterloo.ca> 1. INTRODUCTION This article examines a three-key rollover mechanism for the keyboards of the C-128 and C-64 and presents Kernal-wedge implementations for both machines. Webster's doesn't seem to know, so I'll tell you that this means that the machine will act sensibly if you are holding down one key and then press another without releasing the first (or even press a third key while holding down two others). This is useful to fast touch typers. In fact, fast typing without rollover can be quite annoying; you get a lot of missing letters. Another annoying property of the kernel keyscanning is joystick interference. If you move the joystick plugged into port #1, you will notice that some junk keystrokes result. The keyscanners here eliminate this problem by simply checking if the joystick is pressed and ignoring the keyboard if it is. The reason that a 3-key rollover is implemented instead of the more general N-key rollover is that scanning the keyboard becomes more and more unreliable as more keys are held down. Key "shaddows" begin to appear to make it look like you are holding down a certain key when you really are not. So, by limiting the number of keys scanned to 3, some of this can be avoided. You will get strange results if you hold down more than three keys at a time, and even sometimes when holding down 3 or less. The "shift" keys (Shift, Commodore, Control, Alternate, and CapsLock) don't count in the 3 keys of rollover, but they do make the keyboard harder to read correctly. Fortunately, three keys will allow you to type words like "AND" and "THE" without releasing any keys. 2. USER GUIDE Using these utilities is really easy - you just type away like normal. To install the C-128 version, enter: BOOT "KEYSCAN128"