8bitfiles.net/archives

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

/ 8bitfiles.net/archives / archives.tar / archives / genie-commodore-file-library / Information / HACKING6D.SFX / hacking6d

Wrap

Text File | 1993-09-17 | 34.8 KB | 705 lines

Operational diagram of STA $DDFD,X: # data address R/W description --- ---- ------- --- --------------------------------- 1 9D PCR R fetch opcode 2 FD PCR+1 R fetch address low 3 DC PCR+2 R fetch address high, add X to address low 4 xx $DD0D R read from address, fix high byte of address 5 ac $DE0D W write to right address With branch instructions: ; acknowledge interrupts to CIA 2 LDA #$00 ; clear N flag JMP $DD0A DD0A BPL $DC9D ; branch DC9D BRK ; return You need the following preparations to initialize the CIA registers: LDA #$91 ; argument of BPL STA $DD0B LDA #$10 ; BPL STA $DD0A STA $DD08 ; load the ToD values from the latches LDA $DD0B ; jam the ToD display LDA #$7F STA $DC0D ; assure that $DC0D is $00 Operational diagram of BPL $DC9D: # data address R/W description --- ---- ------- --- --------------------------------- 1 10 $DD0A R fetch opcode 2 91 $DD0B R fetch argument 3 xx $DD0C R fetch opcode, add argument to PCL 4 yy $DD9D R fetch opcode, fix PCH ( 5 00 $DC9D R fetch opcode ) ; acknowledge interrupts to CIA 1 LDA #$00 ; clear N flag JMP $DCFA DCFA BPL $DD0D DD0D BRK ; Again you need to set the ToD registers of CIA 1 and the ; Interrupt Control Register of CIA 2 first. Operational diagram of BPL $DD0D: # data address R/W description --- ---- ------- --- --------------------------------- 1 10 $DCFA R fetch opcode 2 11 $DCFB R fetch argument 3 xx $DCFC R fetch opcode, add argument to PCL 4 yy $DC0D R fetch opcode, fix PCH ( 5 00 $DD0D R fetch opcode ) ; acknowledge interrupts to CIA 2 automagically ; preparations LDA #$7F STA $DD0D ; disable CIA 2's all interrupt sources LDA $DD0E AND #$BE ; ensure that $DD0C remains constant STA $DD0E ; and stop the timer LDA #$FD STA $DD0C ; parameter of BPL LDA #$10 STA $DD0B ; BPL LDA #$40 STA $DD0A ; RTI/parameter of LSR LDA #$46 STA $DD09 ; LSR STA $DD08 ; load the ToD values from the latches LDA $DD0B ; jam the ToD display LDA #$09 STA $0318 LDA #$DD STA $0319 ; change NMI vector to $DD09 LDA #$FF ; Try changing this instruction's operand STA $DD05 ; (see comment below). LDA #$FF STA $DD04 ; set interrupt frequency to 1/65536 cycles LDA $DD0E AND #$80 ORA #$11 LDX #$81 STX $DD0D ; enable timer interrupt STA $DD0E ; start timer LDA #$00 ; To see that the interrupts really occur, STA $D011 ; use something like this and see how LOOP DEC $D020 ; changing the byte loaded to $DD05 from BNE LOOP ; #$FF to #$0F changes the image. When an NMI occurs, the processor jumps to Kernal code, which jumps to ($0318), which points to the following routine: DD09 LSR $40 ; clear N flag BPL $DD0A ; Note: $DD0A contains RTI. Operational diagram of BPL $DD0A: # data address R/W description --- ---- ------- --- --------------------------------- 1 10 $DD0B R fetch opcode 2 11 $DD0C R fetch argument 3 xx $DD0D R fetch opcode, add argument to PCL 4 40 $DD0A R fetch opcode, (fix PCH) With RTI: ; the fastest possible interrupt handler in the 6500 family ; preparations SEI LDA $01 ; disable ROM and enable I/O AND #$FD ORA #$05 STA $01 LDA #$7F STA $DD0D ; disable CIA 2's all interrupt sources LDA $DD0E AND #$BE ; ensure that $DD0C remains constant STA $DD0E ; and stop the timer LDA #$40 STA $DD0C ; store RTI to $DD0C LDA #$0C STA $FFFA LDA #$DD STA $FFFB ; change NMI vector to $DD0C LDA #$FF ; Try changing this instruction's operand STA $DD05 ; (see comment below). LDA #$FF STA $DD04 ; set interrupt frequency to 1/65536 cycles LDA $DD0E AND #$80 ORA #$11 LDX #$81 STX $DD0D ; enable timer interrupt STA $DD0E ; start timer LDA #$00 ; To see that the interrupts really occur, STA $D011 ; use something like this and see how LOOP DEC $D020 ; changing the byte loaded to $DD05 from BNE LOOP ; #$FF to #$0F changes the image. When an NMI occurs, the processor jumps to Kernal code, which jumps to ($0318), which points to the following routine: DD0C RTI How on earth can this clear the interrupts? Remember, the processor always fetches two successive bytes for each instruction. A little more practical version of this is redirecting the NMI (or IRQ) to your own routine, whose last instruction is JMP $DD0C or JMP $DC0C. If you want to confuse more, change the 0 in the address to a hexadecimal digit different from the one you used when writing the RTI. Or you can combine the latter two methods: DD09 LSR $xx ; xx is any appropriate BCD value 00-59. BPL $DCFC DCFC RTI This example acknowledges interrupts to both CIAs. If you want to confuse the examiners of your code, you can use any of these techniques. Although these examples use no undefined opcodes, they do not run correctly on CMOS processors. However, the RTI example should run on 65C02 and 65C816, and the latter branch instruction example might work as well. The RMW instruction method has been used in some demos, others were developed by Marko M"akel"a. His favourite is the automagical RTI method, although it does not have any practical applications, except for some time dependent data decryption routines for very complicated copy protections. MAKING USE OF THE I/O REGISTERS If you are making a resident program and want to make as invisible to the system as possible, probably the best method is keeping most of your code under the I/O area (in the RAM at $D000-$DFFF). You need only a short routine in the normally visible RAM that pushes the current value of the processor's I/O register $01 on stack, switches I/O and ROMs out and jumps to this area. Returning from the $D000-$DFFF area is easy even without any routine in the normally visible RAM area. Just write a RTS to an I/O register and return through it. But what if your program needs to use I/O? And how can you write the RTS to an I/O register while the I/O area is switched off? You need a swap area for your program in normally visible memory. The first thing your routine at $D000-$DFFF does is copying the I/O routines (or the whole program) to normally visible memory, swapping the bytes. For instance, if your I/O routines are initially at $D200-$D3FF, exchange the bytes at $D200-$D3FF with the contents of $C000-$C1FF. Now you can call the I/O routines from your routine at $D000-$DFFF, and the I/O routines can switch the I/O area temporarily on to access the I/O circuitry. And right before exiting your program at $D000-$DFFF swaps the old contents of that I/O routine area in, e.g. exchanges the memory areas $D200-$D3FF and $C000-$C1FF again. What I/O registers can you use for the RTS? There are two alternatives: 8-bit VIC sprite registers or CIA serial port register. The CIA register is usually better, as changing the VIC registers might change the screen layout. However, also the SP register has some drawbacks: If the machine's CNT1 and CNT2 lines are connected to a frequency source, you must stop either CIA's Timer A to use the SP register method. Normally the 1st CIA's Timer A is the main hardware interrupt source. And if you use the Kernal's RS232, you cannot stop the 2nd CIA's Timer A either. Also, if you don't want to lose any CIA interrupts, remember that the RTS at SP register causes also the Interrupt Control Register to be read. Also keep in mind that the user could press RESTORE while the Kernal ROM and I/O areas are disabled. You could write your own NMI handler (using the NMI vector at $FFFA), but a fast loader that uses very tight timing would still stop working if the user pressed RESTORE in wrong time. So, to make a robust program, you have to disable NMI interrupts. But how is this possible? They are Non-Maskable after all. The NMI interrupt is edge-sensitive, the processor jumps to NMI handler only when the -NMI line drops from +5V to ground. Just cause a NMI with CIA2's timer, but don't read the Interrupt Control register. If you need to read $DD0D in your program, you must add a NMI handler just in case the user presses RESTORE. And don't forget to raise the -NMI line upon exiting the program. This can be done automatically by the latter two of the three following examples. ; Returning via VIC sprite 7 X coordinate register Initialization: ; This is executed when I/O is switched on LDA #$60 STA $D015 ; Write RTS to VIC register $15. Exiting: ; NOTE: This procedure must start at VIC register ; $12. You have multiple alternatives, as the VIC ; appears in memory at $D000+$40*n, where $0<=n<=$F. PLA ; Pull the saved 6510 I/O register state from stack STA $01 ; Restore original memory bank configuration ; Now the processor fetches the RTS command from the ; VIC register $15. ; Returning via CIA 2's SP register (assuming that CNT2 is stable) Initialization: ; This is executed when I/O is switched on LDA $DD0E ; CIA 2's Control Register A AND #$BF ; Set Serial Port to input STA $DD0E ; (make the SP register to act as a memory place) LDA #$60 STA $DD0C ; Write RTS to CIA 2 register $C. Exiting: ; NOTE: This procedure must start at CIA 2 register ; $9. As the CIA 2 appears in memory at $DD00+$10*n, ; where 0<=n<=$F, you have sixteen alternatives. PLA STA $01 ; Restore original memory bank configuration ; Now the processor fetches the RTS command from ; the CIA 2 register $C. ; Returning via CIA 2's SP register, stopping the Timer A ; and forcing SP2 and CNT2 to output Initialization: ; This is executed when I/O is switched on LDA $DD0E ; CIA 2's Control Register A AND #$FE ; Stop Timer A ORA #$40 ; Set Serial Port to output STA $DD0E ; (make the SP register to act as a memory place) LDA #$60 STA $DD0C ; Write RTS to CIA register $C. Exiting: ; NOTE: This procedure must start at CIA 2 register ; $9. As the CIA 2 appears in memory at $DD00+$10*n, ; where, 0<=n<=$F, you have sixteen alternatives. PLA STA $01 ; Restore original memory bank configuration ; Now the processor fetches the RTS command from ; the CIA 2 register $C. For instance, if you want to make a highly compatible fast loader, make the ILOAD vector ($0330) point to the beginning of the stack area. Remember that the BASIC interpreter uses the first bytes of stack while converting numbers to text. A good address is $0120. Robust programs practically never use so much stack that it could corrupt this routine. Usually only crunched programs (demos and alike) use all stack in the decompression phase. They also make use of the $D000-$DFFF area. This stack routine will jump to your routine at $D000-$DFFF, as described above. For performance's sake, copy the whole byte transfer loop to the swap area, e.g. $C000-$C1FF, and call that subroutine after doing the preliminary work. But what about files that load over $C000-$C1FF? Wouldn't that destroy the transfer loop and jam the machine? Not necessarily. If you copy those bytes to your swap area at $D000-$DFFF, they will be loaded properly, as your program restores the original $C000-$C1FF area. If you want to make your program user-friendly, put a vector initialization routine to the stack area as well, so that the user can restore the fast loader by issuing a SYS command, rather than loading it each time he has pressed STOP & RESTORE or RESET. NOTES See MCS 6500 Microcomputer Family Programming Manual for more information. There is also a table showing functional description and timing for complete 6510 instruction set on C=Hacking magazine issue 1/92 (available via FTP at ccosun.caltech.edu:/pub/rknop/hacking.mag/ and nic.funet.fi:/pub/cbm/c=hacking/). References: C64 Memory Maps C64 Programmer's Reference Guide pp. 262-267 6510 Block Diagram C64 Programmer's Reference Guide p. 404 Instruction Set C64 Programmer's Reference Guide pp. 416-417 C=Hacking Volume 1, issue #1, 1/92 C=Lehti magazine 4/87 ============================================================================= A Heavy-Duty Power Supply for the C-64 by John C. Andrews (no email address) As a Commodore User for the last 4 plus years, I am aware of the many articles and letters in the press that have bemoaned the burn-out problem of the C-64 power supply. When our Club BBS added a one meg drive and stayed on around the clock, the need for heavy-duty power supply became very apparent.... Three power supplies went in 3 successive days! Part of the problem was my ignoring the seasons. You see during the winter I had set the power supply between the window and the screen, Yes, outside! With the advent of Spring... well, you get the picture. The turn-around time forgetting a new commerical supply was not in the best interest of the BBS and its members. Therefore, taking power supply inhand, I proceeded to cut one open on my shop bandsaw. I do not suggest that you do this. The parts are FIRMLY and COMPLETELY encased in a hard plastic potting compound. The purpose of this is not to make the item difficult to repair, but to make the entire unit conductive to the heat generated inside. I doubt the wisedom of potting the fuse as well. However, CBM was probably thinking of the number of little fingers that could fit into an accessable fuse holder. if you want the punch line it is: the final circuit board and its componets are about the size of a box of matches. This includes the built-in metal heat sink. From these minscule innards I traced out the circuit and increased the size of ALL components. The handiest source of electronic parts is, of course, Radio Shack. All but one part can be purchased there. 212-1013 Capacitor, 35V, 4700 mF 212-1022 Capacitor, 35V, 10 uF 273-1515 Transformer, 2 Amp, 9-0-9 VAC 276-1184 Rectifier 270- 742 Fuse Block 270-1275 Fuses Note that there are only five parts. The rest are fuses, fuse blocks, heat sinks, wire and misc. hardware. Note also that I have not listed any plugs and cords. This because you can clip the cords off of both sides of your defunct power supply. This will save you the hassle of wriing the DIN power plug correctly: DIN PIN OUT COLOR pin 6 9VAC black pin 7 9VAC black pin 5 +5 Volts blue pin 1,2,3 shield, gnd orange The part that you can NOT get at Radio Shack is the power regulator. This part will have to be scrounged up from some local, big electronics supply house: SK 9067 5 volt voltage regulator, 3+ amps. (I prefer the 5 amp.) Radio Shack does carry regulators, but their capacity is no larger than that with which you started. The Heat sinks, (yes, more than one!) are the key to the success of this project. The ones I used came from my Model Railroading days. Sorry to say, I did just ahve them 'lying about'. The heat sinks that I priced at the local electronics supply were more costly than the other parts. The worst case situation is that you may need to drill out a couple pieces of aluminum sheet. Try for 12 x 12, and bend them into square bottomed U-shapes to save room. heat sinks should not touch, or be electronically grounded to each other. You can also mount them on stand-offs from your chassis for total air circulation. The Radio Shack transformer is rated at only 2 amps. If you can not find one with a higher rating elsewhere, it is possible to hook two in parallel to get a 4 ampere output. This si tricky, as it can be done either right or wrong! Here is how to do it the right way: Tape off one yellow secondary lead on each transformer. With tape mark the four remaining secondary leads and letter them A and B on one transformer, C and D onthe other. Hook up the black primary leads to a plug to your 120 wall outlet: |------------- Note: *'s - indicate connections | 3 || +'s - indicate skip overs | 3 || (Transformer) | 3 || | 3 || | ---------- | | +--\ /-------------------*---+--------- --|120|/ | 3 || --|Vlt| ____ | 3 || -|Plg|------------|FUSE|-------* 3 || +--/ ---- | 3 || (Transformer) |--------- This would now be a good time to install a fuse in your 120 VAC line. Now before plugging this into the wall, tie two of the scondary leads (one from EACH transformer) together. Something like this: A--Xfmr--B+C--Xfmr--D Plug in your 120V side. Now using a VOM meter, measure the voltage between A and D. If the meter reads 18 volts, then: 1. unplug from the 120. 2. tie A and C together. tie B and D together. 3. your 2 transformers will now give you 9 volts at 4 amps. If the meter reads 0 volts, then: 1. unplug from the 120. 2. tie A and D together. Tie B and C together. 3. your 2 transformers will now give you 9 volts at 4 amps. Below is the file corresponding to the full schematic of the power supply. [Ed's note: in GeoPaint format, converted, then uuencoded]. As you can see in the picture, I used only one transformer. Because it got hot, I epoxied a small heat sink to it. While this solved the heat problem, it did not increase the capacity of the total power supply. Note that I used fuses on all lines. ----------------------------------------------------------------------------- begin 700 schematic. M@PD,<V-H96UA=&ECH*"@H*"@H`D&`0=8!P8-,Q(`4%)'(&9O<FUA='1E9"!' M14]3(&9I;&4@5C$N,``CF````"```.``0X(``$5P<V]N($U8+3@P`*"@H*`` MUH>-UH?(F!AE`H4"D`+F`V"@H*"@H*"@H`@%`0A6!`<,`"````"""@A30TA% M34%424.@H*"@H*"@````````````$P!"3$%35$52)U,@0T].5D525$52(%8R M+C4$6`<X"````@RP#0T].5D525*"@H*"@H*"@H"P2``99`Q$&`10````` M```````````````````````````````````````#%;_____```.@``6?__F5 M55F:JJF555F:JJF555F:JJF555F:JJF?__F@``7```/___\```````-__[:` M`/Y__[R#!P$``/__``!086EN="!);6%G92!6,2XQ```````````````````` M````````````9V5O4&%I;G0@("`@5C(N,``````@*$')!M`"J1*-(D"I`(TG M0"#]/Y`%J0"-)T`@#!\@2$&I`(VL7ZD`A1&I!X40J3^%%ZGQA1:I7X4-J:R% M#*!`J0X@3S&B_Z4"R0+P)LG_T`8@-$&X4*G)!M`-H$.I)B!/,2"APKA0F*VL M7_`&(+T\(($\8%!A:0#_"@#_`3P!>`)+`EL"/P&R`38!B@%Z`38!C@(G`/\` M_P#_`/\`_P#_`/\`_P#_`/\`_P#_`/\`_P#_`/\`_P#_`/\`_P#_`/\`_P#_ M`/\`_P#_`/\`_P#_`/\````````````````````````````````````````` M```````````````````````````````````````````````````````````` M```````````````````````````````````````````````````````````` M`````````````````````````````````````````````````````````/\` M_P#_`/\`_P#_`/\`E0`"/R!%````````_P"%``,0_Q!$````````_P"&``+X M"/\`_P"B`/^_H;\``"`@,!@,_PP810``````_P``"!`0,&#@_\#`0P`````` M_P``A1`#\!`0H`"("/\`_P#*``(@/X8``>#_`+```3"'(*@``F`PAA"8`(@0 MH`"("/\`_P"B`/^_H;\`(*@`B!"8`(00!!\0$!!$`````/\```"$"`3X"`@( M_P#_`,(``O__A@`"X."&((L`#0$!`0($@("`#A$0$!.%``-98D.%``.,4MZ% M``/@D)"0``$'0P````````#_AP`!@,\`B""H_P#.``H#1$0HA0`##03$A0`# M@("9AP`!!*``B""H`(@0H`"("/\`_P#_`.,`'2D1$1$0````).0$),0```"E MI*2DF`````2HJ%!0HP"&(`)@8*(``1^$``P!$!#_````/-,``/B$``&`F`"( M"/\`_P"B`/^_H;\``+```3"'(*@``F`PAA"8`(@0H`"("/\`_P"B`/^_H;\` M(*@`B!"8`(00!!\0$!!$`````/\```"$"`3X"`@(_P#_`,(``O__A@`"X."& M((L`#0$!`0($@("`#A$0$!.%``-98D.%``.,4MZ%``/@D)"0``$'0P`````` M``#_AP`!@,\`B""HS@`""`B&``(*BH8``@D!O@`"#PA#````````_P"&``R` M8``/##`P#`PP`/^%``,\`/^%``/``/^%``$$1`#_`````````P#_`84`"L#_ M@,#@8"`@`/^'``'PAA"0``(&"(8`A!`,$A(2$V`0```\!(3.A``$<8J*BH0` M#,`@("<````X*"!P((<(`0^'``&`_P#_`,<``S\@((8``N`<B``1!`4%`@(" M``"34E(B(B(``)N$20E(``"8)#P@))BR`(@(D0`Q`0$```$!`&"%A65EA85E M,`P,,#`,##`B(CPB(B(\`$!,4DY24DX`!&25AH:59```@(0``8"A`(@@A0`+ M`0(*!!`0.$2"`0"`A@`"@$"0`(@0`H2$A@`"BG&&``(JRH8`#*"@`0$#`P4% M,,```(0%"&`8!`3R"@D1_P#_`)H`_[^AOP`````````````````````````` M```````````````````````````````````````````````````````````` M```````````````````````````````````````````````````````````` M```````````````````````````````````````````````````````````` M``````````````````````````````````"<``(!`T(```````#__P(``(0@ M!N#@("`#`88`"/^`0"`0"`0$2O\``````````?B8`!<!`0```0$`986%966% MA64P#`\P,`P,,$8``/\```````,``/Z%`H@``3^'`!3X"P0"`0```(#G@(`! M@D0X(+]`@$(``````/\``(0``A#_AA!#`/\````````8!?P$`@(!`0"-B8G9 M<7$`P.$A(2(2#`08_P#_`*T``@$#0@```````/__"P```"`@(.#@("`@B``$ M`@$!`8@`'("`@$```'E$1'A$1```@("8I9VE```(",DJ#`S)`#<!`0```0$` M986%966%A64P#`PP,`P,,`!$"D0H*1$1$0`-!,0DY`0D`("`F:6DI*0````$ M!*BH4)```0-#`````````/^'``'PAQ"8`(@0CP`!#(<``0B(``(X#X8(`F"` M_P#_`*``_[^AOP`````````````````````````````````````````````` M```````````````````````````````````````````````````````````` M```````````````````````````````````````````````````````````` M`````````````````````````````````````````````````````+``B""0 M`(5`%7]`0$1X````_P``I9P```#_```JR4(```#_``````<```#_```'A`0; M_`0$_P`],3TQ,`#_`+.VL['G`/\`O#`\L#P`A8`#_X"`0@``````_P``-0`! M`0``_P``986%8&"````P#`PP/P```!````#_````Q````/\```"8````_P`` M`%````#_AP`$X"`@(*@`B!"8`(00!!\0$!"$`!3_`````@$!`/\``0$("`B( MCX@("(0`!/\```"$"`3X"`@(_P#_`,(``O__A@`"X."&((L`#0$!`0($@("` M#A$0$!.%``-98D.%``.,4MZ%``/@D)"0``$'0P````````H`_X<``8#/`(@@ MJ`"($)@`B!"(``L"#```GJ&AH0@("(D`!&"PD("("/\`_P"B`/^_H;\```$, MAP`!"(@``C@/A@@"8(#_`/\`H`#_OZ&_```````````````````````````` M```````````````````````````````````````````````````````````` M```````````````````````````````````````````````````````````` M```````````````````````````````````````````````````````````` M````````````L`"(((4`)@$"'`0($"!`_P``$1$.``#_``!"0D$``/\``!!2 MC```_P``D)"04```_P``````#0``_P``("`P&`S_#!A%``````#_```($!`P M8.#_P,!#``````#_``"%$`/P$!"(``2AH:&>A``)`2(B(AP```#`A(`#```` MB`C_`/\`R@`"(#^&``'@_P"P``,P(`"%(*@``F`PAA"8`(@0H`"("/\`_P"B M`/^_H;\`_P`!`0@("(B/B`@(A``$_P```(0(!/@("`C_`/\`P@`"__^&``+@ MX(8@BP`-`0$!`@2`@(`.$1`0$X4``UEB0X4``XQ2WH4``^"0D)#_`.D`B""H M`(@0F``*B!"@`(@(_P#_`/\`_P"$`(@@J`"($)@`B!"@`(@(_P#_`*(`_[^A MOP``#0``_P``("`P&`S_#!A%``````#_```($!`P8.#_P,!#``````#_``"% M$`/P$!"(``2AH:&>A``)`2(B(AP```#`A(`#````B`C_`/\`R@`"(#^&``'@ M_P"P``,P(`"%(*@``F`PAA"8`(@0H`"("/\`_P"B`/^_H;\`_P`!`0@("(B/ MB`@(A``$_P```(0(!/@("`C_`/\`P@`"__^&``+@X(8@BP`-`0$!`@2`@(`. M$1`0$X4``UEB0X4``XQ2WH4``^"0D)#_`.D`B""H`(@0F`"($*``B`C_`/\` M_P#S``$#AP(8_P``>V-[8V'_``!G;&9CSO\``'A@>&!XB("8`(@0B`"(`1G_ M```],3TQ,/\``+.VL['G_P``O#`\L#S`AT")``,?$!"$$Q@(_P``VQO;&P#_ M```[8S,;`/P$!,0$Q`3_`/\`D@#_OZ&_`(8``>#_`+```S`@`(4@J``"8#"& M$)@`B!"@`(@(_P#_`*(`_[^AOP#_``$!"`@(B(^("`B$``3_````A`@$^`@( M"/\`_P#"``+__X8``N#@AB"+``T!`0$"!("`@`X1$!`3A0`#66)#A0`#C%+> MA0`#X)"0D/\`V0`#`@(#0@``````"@``_X40`P``_X4``X"`@)T`B!"(``,! M`0%"`````````/^%"`,``/^%``-`0,"-``03$!`?A``$#@``_X0$!',``/^$ M``3$!`3\_P#_`/\`]P"($*@`B!"8`(@(H`"(!/\`_P"B`/^_H;\`!,0$Q`3_ M`/\`D@#_OZ&_`(8``>#_`+```S`@`(4@J``"8#"&$)@`B!"@`(@(_P#_`*(` M_[^AOP#_``$!"`@(B(^("`B$``3_````A`@$^`@("/\`_P#"``+__X8``N#@ MAB"+``T!`0$"!("`@`X1$!`3A0`#66)#A0`#C%+>A0`#X)"0D/\`Z0"($*@` MB!"8`(@(H`"(!/\`_P#_`/\`A`"($*@`B!"8`(@(H`"(!/\`_P"B`/^_H;\` M_X4``T!`P(T`!!,0$!^$``0.``#_A`0$<P``_X0`!,0$!/S_`/\`_P#W`(@0 MJ`"($)@`B`B@`(@$_P#_`*(`_[^AOP`$Q`3$!/\`_P"2`/^_H;\`A@`!X/\` ML``#,"``A2"H``)@,(80F`"($*``B`C_`/\`H@#_OZ&_`/\``0$("`B(CX@( M"(0`!/\```"$"`3X"`@(_P#_`,(``O__A@`"X."&((L`#0$!`0($@("`#A$0 M$!.%``-98D.%``.,4MZ%``/@D)"0_P#I`(@0J`"($)@`B`B@``J(!/\`_P#_ M`/@``P,$!(4``X%!0(00!``1$:*%``,.$9"4``0'"`@(A``,`H*!@1`0$``B M(D5%A``$'"(@((<`"P,````?$!`>P0@(B0`-<HN#@IH````N*2BHJ(4`$X"` M@`````$!!P$!`!\0$![!`1'_`/\`H@#_OZ&_`/\`L``#,"``A2"H``)@,(80 MF`"($*``B`C_`/\`H@#_OZ&_`/\``0$("`B(CX@("(0`!/\```"$"`3X"`@( M_P#_`,(``O__A@`"X."&((L`#0$!`0($@("`#A$0$!.%``-98D.%``.,4MZ% M``/@D)"0_P#9``P$`P```P```$#`0("$``VBI$=$1````)!0T%%.DP`*!P`! M!@````^!@(4`$1!(CXB(`````Z"@HIP```#@A@`C`P(!$0X```#$(```("!` M````BHIR````0<)H:2X```#!(("%``+P((0`#`<$!`0.````B$!;2H0`!`$! M@4&$``3P``#@_P#_`/\`XP`3!P0$!`<$!`2(0%M*B@H*"@``@81!"4!@@`#@ M$!`0X)``"P@("`\("`@`@+>4A!0#````A8`:`"`@0$"`@(```@(#`@("```M M)<4%!04``,"%(!X``$!`0$%"2P@0($"```'D!`A`X!`0$.````<$!`2$``2* >"@H*A``$0$`*04"$``00$!#@_P#_`)8`_[^AOP`* ` end ============================================================================= LZW Compression by Bill Lucier (Blucier@ersys.edmonton.ab.ca, b.lucier1 on Genie) LZW is perhaps the most widely used form of data compression today. It is simple to implement and achieves very decent compression at a fairly quick pace. LZW is used in PKZIP (shrink),PKARC (crunch), gifs,V.42bis and unix's compress. This article will attempt to explain how the compression works with a short example and 6502 source code in Buddy format. Originally named lz78, it was invented by Jacob Ziv and Abraham Lempel in 1978 , it was later modified by Terry Welch to its present format. The patent for the LZW compression method is presently held by Unisys. LZW compresses data by taking phrases and compressing them into codes. The size of the codes could vary from 9 bits to 16 bits. Although for this implementation we will be using only 12 bits. As byte are read in from a file they are added to a dictionary. For a 12-bit implementation a dictionary will be 4k (2^12=4096) . Each entry in the dictionary requires five bytes, which will be built in the form of a tree. It is not a binary tree because each node may have more than two offsprings. In fact, because our dictionary can hold up to 4096 different codes it is possible to have one node with 3800 children nodes, although this is not likely to happen. The five bytes that make up our tree will be: The parent code: Each node has one and only one parent node. When the parent code is less then 255 it is the end of a phrase. The codes 0-255 do not actually exist in the tree. The following values do not appear either as they have special meaning: 256 : End of Stream-This marks the end of one compressed file 257 : This tells the decompressor to increase the number of bits its reading by one. 258 : Wipe out dictionary The code value : This is the code that will be sent to the compressor. The character : The value contained at this node. It have a value of 0-255. Initially we send out codes that are 9 bits long, this will cover the values 0-511. Once we have reached 511, we will need to increase the number of bits to write by 1. This will give room for code numbers 512-1023, or (2^10)-1. At this point we must ensure that the decompressor knows how bits to read in at once so a code number 257 is sent to indicate that the number of bits to be read is to be bumped up by one. The size of the dictionary is finite so at some point we do have to be concerned with what we will do when it does fill up. We could stop compiling new phrases and just compress with the ones that are already in the dictionary. This is not a very good choice, files tend to change frequently (eg. program files as they change from code to data) so sticking with the same dictionary will actually increase the size of the file or at best, give poor compression. Another choice is to wipe the dictionary out and start building new codes and phrases, or wipe out some of the dictionary leaving behind only the newer codes and phrases. For the sake of simplicity this program will just wipe out the dictionary when it becomes full. To illustrate how LZW works a small phrase will be compressed : heher. To start the first two characters would be read in. The H would be treated as the parent code and E becomes the character code. By means of a hashing routine (the hashing routine will be explained more fully in the source code) the location where HE should be is located. Since we have just begun there will be nothing there,so the phrase will be added to the dictionary. The codes 0-258 are already taken so we start using 259 as our first code. The binary tree would look something like this: node # 72 - H | node #3200 259 - E The node # for E is an arbitrary one. The compressor may not choose that location, 3200 is used strictly for demonstration purposes. So at node #3200 the values would be: Parent code - 72 code value - 259 character - E The node #72 is not actually used. As soon as a value less than 255 is found it is assumed to be the actual value. We can't compress this yet so the value 72 is sent to the output file(remember that it is sent in 9 bits). The E then becomes the parent code and a new character code ( H ) is read in. After again searching the dictionary the phrase EH is not found. It is added to the dictionary as code number 260. Then we send the E to the disk and H becomes the new parent code and the next E becomes the new character code. After searching the dictionary we find that we can compress HE into the code 259,we want to compress as much as possible into one code so we make 259 the parent code. There may be a longer string then HE that can be compressed. The R is read in as the new character code. The dictionary is searched for the a 259 followed a R, since it is not found it is added to the dictioary and it looks like this: node #72 - H node #69 - E | | node #3200 259 - E node #1600 260 - H | node #1262 261 - R Then the value 259 is sent to the output file (to represent the HE) and since that is the EOF the R is sent as well,as well as a 256 to indicate the EOF has been reached. Decompression is extremely simple. As long as the decompressor maintains the dictionary as the compressor did, there will be no problems,except for one problem that can be handled as an exceptional case. All of the little details of increasing the number of bits to read, and when to flush the dictionary are taken care of by the compressor. So if the dictionary was increased to 8k, the compressor would have to be set up to handle a larger dictionary, but the decompressor only does as the compressed file tells it to and will work with any size dictionary. The only problem would be that a larger dictionary will creep into the ram under the rom or possibly even use all available memory, but assuming that the ram is available the decompressor will not change. The decompressor would start out reading 9 bits at a time, and starts it free code at 259 as the compressor did. To use the above input from the compressor as an example, the output was: 72 - For the First H 69 - For the First E 259 - For the Compressed HE 82 - For the R 256 - Eof indicator To begin decompressing, two values are needed. The H and E are read in, (note they will both be 9 bits long). As they are both below 256 they are at the end of the string and are sent straight to the output file. The first free code is 259 so that is the value assigned to the phrase HE. Note when decompressing there is no need for the hashing routine, the codes are the absolute locations in the dictionary (i.e. If the dictionary was considered to be an array then the entry number 259 would be dictionary[259]), because of this, the code value is no longer needed. So the decompressor would have an entry that looks like this: Node # 259 Parent Code - H Character - E The decompressor will read in the next value (259). Because the node number is at the end of the compressed string we will have to take the code value and place it on a stack, and take them off in a Last-in,First-out (LIFO) fashion. That is to say that the first character to go on the stack (in this case the E) will be the last to come off. The size of the stack is dependent on the size of the dictionary, so for this implementation we need a stack that is 4k long. After all the characters from the string have been placed on the stack they are taken off and sent to the outputfile.