magazines:chacking21
######## ################## ###### ###### ##### ##### #### #### ## ##### #### #### #### #### #### ##### ##### ## ## #### ## ## ## ### ## #### ## ## ## ##### ######## ## ## ## ##### ## ## ## ## ## ##### ## ## ######## ## ## ## ### ## ## #### ## ## ##### #### #### #### #### ##### #### #### #### #### #### ###### ##### ## ###### ###### Issue #21 ################## Feb 5, 2002 ######## Special Focus on Minigames ............................................................................... "Do not meddle in the affairs of wizards, for they are subtle and quick to anger." -- Ancient Elvish saying ............................................................................... BSOUT (Why yes, I _am_ re-reading Lord Of The Rings, how did you know? Sure, the movie is pretty good, not the same as the book, but probably the best you could do, although why does every Hollywood evil creature essentially come from Night of the Living Dead? But hey, the elves actually looked like elves. Black Hawk Down is really good too, and... oh, sorry!) Hoo-ah! Welcome to another issue of C=Hacking! There's lots of nifty stuff to get to so this will be brief. First, the "Hacking Exchange" is now up at the Official Unofficial C=Hacking Homepage: http://www.ffd2.com/fridge/chacking/ It's just a simple message board, with the idea that C=Hacking types can make comments, ask questions, and otherwise talk to one another. Check it out! Second, if you have any projects you're working on... please contact me, and consider writing them up for C=Hacking! And finally, something I think you'll enjoy: http://groups.google.com/groups?hl=en&th=87c2a2ced7e32ce1&rnum=42 From: duck@clumsy.pembroke.edu (duck@clumsy.pembroke.edu) Subject: C= Hacker's Net-Mag Newsgroups: comp.sys.cbm Date: 1992-02-08 14:52:20 PST Due to the recent influx of "Tech-Know" (People who actually understand / hack te C=64 into doing stuff that was previously unknown) I am going to tentativly start a C= Hackers Net-Mag (Hacking in the 90's since of the word, not the 80's). So - please send me your netmail address if you're interested in receiving it. Or if you are interested in contatcting me concerning an article etc that you'd like to see distributed please also contact me. For the first issue I'm tentatively planning on: - Line Drawing on 8563 VDC (640 x 200 hi-res graphics) - Beginning ML column - Raster Article . . . - Craig Taylor duck@pembvax1.pembroke.edu P.S. - Not sure when the first is gonna go out but hopefully soon. From: duck@clumsy.pembroke.edu (duck@clumsy.pembroke.edu) Subject: Issue 1 - C= Hacking Available Newsgroups: comp.sys.cbm Date: 1992-02-27 17:22:44 PST Issue 1 of C= Hackers is now available via NETMAIL and is a compilation of several articles on the tehnical side of the Commodore 64 and 128. For those of you who missed the first posting, please reply via email and ask to be put on the list. The first issue had programming in ml, documented and undocumented 6502 opcodes, and a line-drawing package in machine language for the C=128 hi-res screen. Issue 2 will be coming out in a month or so. Many thanks for the bandwith. - Craig Taylor duck@pembvax1.pembroke.edu ....... .... .. . C=H 20 ::::::::::::::::::::::::::::::::::: Contents :::::::::::::::::::::::::::::::::: BSOUT o Voluminous ruminations from your unfettered editor. Jiffies o News, rumours, and stuff. Side Hacking o "Pulse Width Modulation, continued" by various. Tying up some loose ends from last issue's digi article. o "Introducing Full-Screen IFLI mode with a SuperCPU", by Todd Elliot <eyethian@msn.com> (Hey, what's with all this MSN crapola? :) Using a SuperCPU, it is possible to use the first three columns of an (I)FLI picture, and Todd shows how. Main Articles o "VIC-20 Kernel ROM Disassembly Project, part IV", by Richard Cini <rcini@msn.com> And now it's time to start on that most frightening of creations: the tape drive code! o "The Art of the Minigame" -- an article in six parts: Introduction, by the editor Part 1: Codebreaker, by David Holz <whiteflame52@yahoo.com> Part 2: TinyPlay, by S. Judd <sjudd@ffd2.com> Part 3: MagerTris, by Per Olofsson <magervalp@cling.gu.se> Part 4: Compressing Tiny Programs, by S. Judd <sjudd@ffd2.com> Part 5: TinyRinth, by Mark Seelye <mseelye@yahoo.com> Part 6: Tetrattack!, by Stephen Judd <sjudd@ffd2.com> .................................. Credits ................................... Editor, The Big Kahuna, The Car'a'carn..... Stephen L. Judd C=Hacking logo by.......................... Mark Lawrence Special thanks to the cbm-hackers for many otherwise unacknowledged contributions. Legal disclaimer: 1) If you screw it up it's your own fault! 2) If you use someone's stuff without permission you're a dork! For information on the mailing list, ftp and web sites, send some email to chacking-info@jbrain.com. ................................... Jiffies .................................. $01 Jochen Adler has made a program that reads the second side of a 1541 disk in a 1571 - without turning the disk over. It reads the blocks from end to beginning. Because of the mechanical bump however, it can only read tracks 5 to 35. If anybody wants this program please e-mail Jochen (NLQ@gmx.de) $02 Soci/Singular has been working on a commented C128 ROM listing. Check out this great effort at http://singularcrew.hu/c128rom/ $03 64net/2 has been updated: For those that do not know: 64net/2 is yet another PC-to-C64/128 User<->LPT parallel cable software. It supports d64/d71/d81/t64/lnx/dhd disk images, raw files and own Internet partition. It is possible to enter disk images like any other directory. Client programs are provided for C64 and C128. The next goal will be to patch ROM instead of loading client. A small BASIC example program is included that is able to send e-mails through 64net/2 host or any other machine if its IP is known. How many e-mail agents are there for C=? How many of them are written in plain BASIC 2.0? :) http://sourceforge.net/projects/c64net/ contains the latest version, and http://venus.wmid.amu.edu.pl/~ytm/64net2win.tar.gz contains a Windows binary. $04 CC65 is up to version 2.7.0, with many new improvements. Check it out at http://www.cc65.org/ $05 Moreover, Ullrich has set up his C64 as a web server at http://c64.cc65.org/ The web server runs on a stock 64, using a Swiftlink for communications, and uses the uIP TCP/IP stack written (with cc65) by Adam Dunkels http://dunkels.com/adam/uip Pretty cool, eh? $06 A new IDE interface has become available: Elysium is proud to announce a new software and hardware solution for your Commodore mass data storage needs. The CIA-IDE is yet another approach to connect an IDE hard drive to C64/128. It differs from previous similar projects in these areas: - it is the simpliest one (only two chips required (or just one in case of C128)) - it is free (documentation and software), - the software is available in source code form under GNU GPL, - there _exists_ a ready to use GEOS 2.0 driver. Documentation, source codes, and binaries are at: ftp://ftp.elysium.pl/groups/Elysium/Projects/ciaide/ $07 Marko Makela has developed a tape drive emulator with an RS-232 port, allowing transfers between any computer with a tape port and any computer with an RS-232 interface (e.g. a PC or Swiftlink). The hardware and software is at http://www.funet.fi/pub/cbm/crossplatform/transfer/C2N232/ $08 GoDot -- the C64 image processing program -- is now public domain. Arndt will still be working on it, but it's now available at http://members.aol.com/howtogodot/godnews.htm $09 The C64 is now listed in the Guiness Book of World Records; a scan of the page (from Robert Bernardo, posted by Frank Michlick) is at www.cupid.de/upload/famous.jpg (love that line about "16K sound"). Also, I highly recommend taking Robert's advice and checking out the infinitely cool "Logo-Matic" on the main www.cupid.de site! $0A JOS just keeps cruising along, with lots of changes. Among the biggest changes, of course, is the announcement that JOS will be merged with Clips, with the new system to be called "Wings" (with some of the letters capitalized and some not; I never remember that stuff). For the latest JOS news, check out http://www.jolz64.cjb.net/ $0B Frank Kontros has made a commented disassembly of the C64 ROM, with the BASIC ROM on the way: http://c64.uz.ua/sources/C64_Kernal_Disassembly.zip $0C And finally, Aleksi Eeben, author of two minigames, has now written a VIC-20 game: http://www.student.oulu.fi/~aeeben/download/dragonwing.zip more screenshots: http://www.student.oulu.fi/~aeeben/screen1.png - screen4.png Aleksi's homepage is at http://www.cncd.fi/aeeben Neat! ................................ Side Hacking ................................ Pulse Width Modulation, continued --------------------------------- from various The digi article in issue #20 of C=Hacking left a few loose ends, and generated some followups. First, Otto Jarvinen (sounddemon) emailed to say that the SID detection routine occasionally reported incorrect results for him, and suggested that a workaround was to do the detect several times. YMMV! Second, a day or two after issue #20 was released, Levente discovered a brilliant way to play 6-bit PWM digis on a stock machine: -- I couldn't resist, and tried something out (see attachment). It works!!! :-) In fact, when I wrote the last letter I didn't know that I found something useable, just had some ideas - I felt that I'm at the right place. When I read C=H 20 this morning and read your comment about the Test bit (from the PRG), I knew that it must work. All I had to do is then to put this idea into code. The whole idea is about starting the pulse by software, and then having the SID turn it back to 0 after a time. Is it possible? ...The keys are the Test bit (the SID wave counter can be reseted anytime), the pulse width register, the wave counter and the SIDs way of generating pulse wave. (Ie. the pulse wave is high, as long as the wave counter is less than the value in the pulse width register). Check this algorithm: - Init: volume at max, voice 1 sustain level max, start attack. Freq is selected well (=$4000), so the wave counter is incremented by 4 every processor clock cycles. Loop: - load next sample value, and put it to the pulse width low register ($d402; ensure that $d403 is 0). - Set test bit, and clear test bit (counter reset). - Increase sample pointer, some delay, then loop. The delay must be 64 clock cycles + the time while the Test bit is kept set (4 cycles if using STA $d404 : STX $d404 immediately with pre-loaded values). What will happen? The 8-bit sample value is put directly to the pulse width register (MSBs of the pulse width register are cleared!...). The wave counter is started (release test bit), and it increases 4 by every CPU cycles (= counts 256 in 64 cycles). After some time, the counter will reach the value in the pulse width register. This happens in exactly after (8-bit sample value / 4) cycles, because of the above. In this cycle (or the next?...) the SID turns its pulse output to 0. Voilá! One must just make sure that the loop length in cycles matches the above conditions, and then it runs like hell... Since it does exactly the same on the SID as the other (bit-banging) way, it just does it with some hardware help, there's also no problem with the 4khz maximum barrier (since the oscillator is reset every loop). With little enhancement, it's possible to write an about 7.5 bits player for a stock C64 by this method. This is what you find in the attachment... The idea is using all the 3 channels simultaneously. A slightly increased sample value is written to the three pulse width registers, so the oscillators will finish the duty cycle one processor cycle later, when there's a carry between bits(0,1) to the MSBs. The replay freq is the CPU clk / 68 (~15khz). 64 cycles (variable duty cycle) + 4 cycles (constant duty cycle because of the reset time - no problems with that, it doesn't change (just gives a small constant DC...)). By similar methods, it should be possible to write a sample player with higher PWM freq (with less resolution of course, but eliminating this still audible whistling). (I tried using the filter to reduce it, but it sounded so bad that I left it out. It clicked like hell. The FETs got saturated.) [Richard Atkinson suggested turning down the sustain volumes to avoid this] See the attachment, and the binary. I think the sample sounds pretty good :-). (The cut is from 'Greece 2000' by Three drives on a vinyl). (Another idea that popped up in my mind: since the TED sound generator can also be reset, I could probably translate this idea to the Plus/4 :-O ). Best regards, Levente -- The binary is available at http://www.ffd2.com/fridge/chacking/ towards the bottom of the page. Third, I received a very interesting email from an Apple-II guy, which I'd like to pass on: -- Hi! I found your page as I was searching for something else 6502-related, and was very interested. Although I have always been aware of the C64, I have never really been a user--I have used Apple II's since 1980. I was particularly interested in the article on playing "digis" on the C64. I became interested in playing digitized sounds on the Apple II in 1993, after hearing a 3-bit, 11.025 KHz PWM player. At 3 bits, you can imagine how noisy speech samples were, but the overall effect for a 1 MHz machine with a 1-bit speaker "toggle" was amazing. It made me wonder how far this PWM technique could be pushed on a stock, 1 MHz Apple II (not the somewhat faster, 65816-based IIgs). The short answer is, much farther than I expected! Robin and Stephen accurately describe the theoretical PWM limit as 6 bit samples at about 16 KHz for a stock 1 MHz machine, but, as they point out, that is not practically realizable for a number of reasons, unless the play loop is completely unrolled! Furthermore, in the Apple II world, sampled sounds have acquired a few standardized sampling rates--mostly as a result of Mac influence, which was in turn influenced by CD's. The most common rate in the Apple II world is 11.025 KHz, or one-fourth of the audio CD sampling rate. This is commonly considered to be "AM radio quality", with a Nyquist bandwidth of about 5.5 KHz and a practical bandwidth of 4+ KHz, given practical anti-aliasing filters (at the sampling end, not the playback end). A frequency of 11.025 KHz is, though high, still painfully audible to people whose ears are not zonked--a piercing "squeal" running through every sound. So even though it is possible to write a practical 6-bit 11.025 KHz PWM player (usually called a SoftDAC in the Apple II world), the resulting listening experience is disappointing. So I went to work on a way to do 2x oversampling, and built a 5-bit 22.050 KHz PWM player. It was sad to lose a bit, but the absence of any audible "carrier" more than compensated for it! If you have access to an 8-bit Apple II (preferably with lower case, like a //e), and also preferably with a way of attaching an external speaker or headphones in place of the miserable 2.75" internal speaker, then you can easily give it a try and judge for yourself. I'm pretty proud of the novel design of the code, which I would characterize as "vectored" unrolled loops, one for every two pulse duty cycles, which I wrote a BASIC program to write for me--much less painful for counting cycles! The package is available on the web at: http://members.aol.com/MJMahon/index.html and is called <A HREF="http://members.aol.com/MJMahon/sound22.shk">Sound Editor v2.2</A>, since I had to "dress up" the player into something fun to play with. ;-) An earlier version of Sound Editor was published on SoftDisk in 1994, IIRC, but this one is a little more evolved. It also introduced 2:1 ADPCM compression of 8-bit sampled sounds, to save disk space. It is a lossy compression, but not very noticeably. The editor package also includes those routines, in 6502 assembly code. All of this should be trivially adaptable to the stock, 1 MHz C64, with very good results. By using the filters, you could probably filter out the 11.025 KHz carrier and return to 6-bit accuracy! I should note that in the Apple world, sampled sounds are usually represented as "excess-128" codes, which means that the sign bit is inverted. This actually simplifies things, since the sample value is within a few shifts of being the pulse width in cycles. Let me know what you think! -michael -- (Always great to hear from Atari and Apple ][ folks!) And finally, I have a little mathematical analysis of PWM and how it compares to a "straight" digi. Basically, I found some of the PWM explanations a little unconvincing in issue #20 (even though I wrote them!). For example, the idea of "average voltage" seems a little funny, since every two samples has an "average voltage", as does every four, etc. but that set of average voltages would give a different sounding signal than the original (or more dramatically, there is an average voltage over a full second of digi playback, but that's not what you hear!). So I wanted to know how a PWM signal _really_ compares to a straight digi playback. Another issue is changing the amplitude of a PWM digi, i.e. using two pulse waveforms, with one 1/16 the value of the other, to get higher resolution. If you recall the discussion of digis, the resolution of a PWM digi depends on the number of pulse widths available, not the amplitude. Adding two PWM waveforms together does not change the number of pulse widths available, so I wanted to figure out what changing the amplitude _really_ does to a PWM digi, and if it can really be exploited. And finally, I wanted to know about the carrier wave (that is so piercing at lower playback frequencies) -- and once again, how it compares with a standard digi (which, after all, is stair-stepping the voltages at the playback rate). Since the rest of this article is some Fourier analysis that 99% of people will have zero interest in, I'll put the conclusions here. The first is: PWM digis and standard digis are essentially identical except at higher frequencies (except for a phase shift, which doesn't make any difference to your ear). The second is: changing the amplitude of a PWM changes the resolution. More specifically, the amplitude of the pulse multiplies the digi sample value. If two pulses can be synced close enough, it should indeed be possible to use two pulses to get a higher resolution. Moreover, by modulating the amplitude of a single PWM digi, using the $d418 volume register -- that is, using PWM _and_ $d418 -- it should be possible to get a higher dynamic range, something that should be a little more achievable using SID (but maybe not that useful, so I didn't try it out). And finally, a standard digi has zero amplitude at the carrier frequency. In other words, after a lot of effort I was able to demonstrate what everyone already knows. The analysis doesn't change anything from the previous articles (except possibly the idea for changing the PWM amplitude to get more dynamic range). And now, some Fourier analysis. A standard digi just sets the voltage to the sample value s_j, for a length of time dt (dt = 1/sample rate). The Fourier transform of a single sample s_j (occuring at time t_j) is s_j [e^(-iw dt) - 1] * [e^(-iw t_j) / -iw] where w = angular frequency. Since the above is a little hard to read, I'll say it in words. The first term is the sample value s_j, which scales amplitudes at all frequencies. The second term is due to the finite length of the pulse (evaluating the Fourier integral at the boundaries), and basically changes the phase of the transform. The third term is like sin(w)/w -- a sinusoid with decreasing amplitude as frequency increases. So: the transform goes like sin(w)/w times the sample value, with some phase effects thrown in (we'll get back to these in a moment). A PWM digi sets the duty cycle of a pulse to the sample value s_j, giving a Fourier transform of [e^(-iw s_j dt) - 1] * [e^(-iw t_j) / -iw] Compare this with the earlier expression, and you'll see that the sample value s_j has moved up in to the exponent of the "phase term" but that they're otherwise the same. The first thing to do is to show that both expressions, PWM and standard, reduce to the same thing -- that is, that a PWM and a standard digi sound the same! The expressions both decrease as 1/frequency, due to the sin(w)/w term. This means that at large frequencies the values become negligible. (How large? For example, if the sample frequency is just 1KHz, then sin(w)/w is .001 times smaller near w=1KHz (i.e. the sample frequency, which is twice the Nyquist limit) than it is near w=0). So now consider the phase terms for small w. The Taylor expansion for e^x is 1 + x + x^2/2 + ... We can therefore expand the "phase terms" as regular: e^(-iw dt) - 1 = (1 - iw*dt + w^2 dt^2/2 + ...) - 1 = -iw*dt + O(w^2 dt^2) pwm: e^(-iw s_j dt) - 1 = -iw*s_j*dt + O(w^2 dt^2) where O(w^2 dt^2) is considered very small since w and dt are both small. Substituting the above into the original expressions gives s_j*iw*dt [e^(-iw t_j) / iw] in both cases. That is, we have shown that for "small" frequencies -- more specifically, for frequencies where (w^2*dt^2) is much smaller than (w*dt), which is where w*dt<1, which is frequencies less than the sample frequency, which is all frequencies of interest! -- PWM and standard digis are the same. The explanation lies in the phase terms. Those "phase terms" [e^(iw dt) - 1] (regular) and [e^(iw s_j dt) - 1] (PWM) do more than just change the phase. When they multiply the sin(w)/w signal, they take the sin(w)/w signal, change the phase, and then subtract the sin(w)/w signal again. It's this difference of signals that makes things work out at the frequencies we care about. PWM and standard digis are _not_ the same, but the main differences are at higher frequencies, where the amplitudes are in general much smaller. But... but... what about the PWM carrier frequency? If we take a constant digi, say with sample values = 1/2, the standard digi gives a constant voltage, whereas a PWM digi gives a square wave at the sample frequency. The answer comes from the "phase terms" above. The sample frequency is w = 2*pi/dt. Substituting this into the phase terms gives [e^(i*2*pi) - 1] (regular) and [e^(i s_j 2*pi) - 1] (PWM) The regular expression is exactly zero -- there is _nothing_ at the sample frequency of a regular digi. But that's not the case for the PWM term, because of the s_j up in the exponent. PWM digis have a _finite_ amplitude at the carrier frequency. Note that because of the sin(w)/w term it gets smaller as the sample frequency increases -- but it isn't zero. Finally, the phase term expansions give some insight into what happens when both the pulse width _and_ height are varied. If the pulse width is s_j, and the height is set to h_j, then the Fourier transform becomes h_j*s_j *iw*dt [e^(-iw t_j) / iw] That is, the amplitude multiples the width. For the case of adding two PWM waves together, then, the amplitude really does effectively scale the sample value, and it should be possible to add one PWM value at 1/16 the amplitude of another to get an effective 8-bit value. What about _varying_ the amplitude of a single PWM sequence? For a 6-bit PWM digi, say, the sample values s_j can go from 0 to 63. If this is then multiplied by h_j=2 say, then the values become 0 2 4 ... 126 -- a 7-bit number where the lowest bit is always 0. What use is that? Well, we still have the h_j=1 values of 0..63, which do include the lowest bit. So we can effectively change the dynamic range from 0..63 to 0..126 using just two amplitude values. As a practical matter, then, it might be possible to use all 15 $d018 values available to get a big dynamic range, and hence a better sounding digi, using fewer CPU cycles. Well, ok, we're only _sort of_ changing the dynamic range, so I pretty much doubt the usefulness of it. But maybe someone out there would like to give it a shot. All right, let's hope this closes the book on pulse width modulation for digi playback! ....... .... .. . C=H 20 .............................................................................. Introducing Full-Screen FLI mode for the SuperCPU Copyright (C) 2002 By Todd S. Elliott The 'FLI Bug', where the first three columns of a FLI screen are essentially unusable, can be squashed with the help of a SuperCPU. I won't go into great detail on IFLI, as it has been well-documented elsewhere, but I'll begin with a short summary to get us all up to speed. I refer you to Albert 'Pasi' Ojala's excellent coverage of the FLI mode in C=Hacking #4. Pasi also proofread this article. A Three-Minute Summary of the FLI mode The VIC-II chip asserts a badline when it needs to access the databus and fetch character data or videomatrix data. It was discovered that the VIC-II chip can be manipulated by its vertical scroll register at $d011 (SCROLY) to induce a badline at any given rasterline. By having a badline at every visible rasterline, the program can manipulate $d018 (VMCSB) to point at the right videomatrix to achieve the maximum flexibility of colors given to a multi-color screen. Unfortunately, when a program forces a badline via SCROLY, the BA (Bus Available) line in the computer goes high, and for three cycles the 6510/8510 processor has to finish its write operations or halt its read operations before the BA line is released to the VIC-II chip. The maximum number of successive write operations is three, hence the 3-cycle delay. It is in those three cycles that the VIC-II does not fetch video matrix data to fill in the first three columns and causes the 'FLI Bug'. I wish to stress that in those first three cycles, when the BA line is high, the 6510/8510 processor is still active and can complete write operations. It isn't fully shut down. After the badline retrigger at STA SCROLY, the code following it is fetched on the databus and is ready to be executed by the 6510/8510 processor. When BA is high, the VIC-II will reference the value on the databus as videomatrix data and display it in the first three columns of the screen. The actual instructions that follow the STA SCROLY in the FLI loop constitutes the video matrix data for the first three columns of the screen. Enter the SuperCPU! Normally, a VIC-II chip access is only possible every 4 cycles. The SuperCPU can access the VIC-II chip in 1 cycle (1MHz) intervals, making cycle to cycle changes possible within the VIC-II chip. More importantly, the SuperCPU tristates the 6510/8510 processor inside the host Commodore computer (which is a fancy way of saying that you can disconnect the processor from the system without physically removing it). When a forced badline retrigger occurs with a STA SCROLY in a FLI loop under the SuperCPU, the BA signal inside the host Commodore computer goes high. But, the SuperCPU runs asynchronously and really doesn't have to pay attention to the host Commodore as it runs code after the STA SCROLY. In fact, the SuperCPU will execute code even if the VIC-II badline is in full swing inside the host Commodore computer. I knew that the instruction opcodes left on the databus after the STA SCROLY made up the video matrix data for the VIC-II chip for those first three columns of the screen. But I wondered how this was possible in a SuperCPU configuration because there would be no instruction opcodes left hanging on the databus inside the host Commodore computer. After some discussions with Per Olofsson ("MagerValp"), he suggested that writes/reads to the i/o area will force a value to be put on the databus. This is where the magic begins, when the FLI loop forces the SuperCPU to write to the i/o area of the host Commodore after the forced badline retrigger at STA SCROLY. The SuperCPU will note that the BA signal is still high, so it can still access the databus and stash values there via DMA. This BA high signal will last for 3 cycles, enough for the SuperCPU to stash three values onto the databus. The 6510/8510 is still tristated by the SuperCPU, and there's nothing on the databus after the forced badline retrigger at STA SCROLY. Normally, the 6510/8510 CPU shares the databus with the VIC-II for each machine cycle. With the 6510/8510 CPU out of the equation, the SuperCPU can stash a value onto this shared bus on the CPU half of this machine cycle and the VIC-II chip will see it in its other half of the machine cycle. However, the databus is only eight bits wide. The VIC-II chip fetches video matrix data and color ram data 12 bits at a time. The SuperCPU can force values onto the databus during the first three cycles after the forced badline retrigger, but on each cycle the last four bits belonging to Color RAM would not be fed to the VIC-II chip. Only pixel values of %10 and %01 can be individually selected in multicolor FLI mode, while %11 pixel values cannot be individually set for those first three columns of the screen. The high resolution FLI mode does not suffer from this problem because it does not use color RAM for color attribute information. Full-Screen FLI in practice Let's get down to the nitty gritty. The Write I/O Approach requires three 200-byte tables, corresponding to each column. Each value on those tables correspond to each visible rasterline. For example, the first byte of each table corresponds to rasterline 50, the second byte of each table corresponds to rasterline 51, etc. The first table contains values needed for the first column of the screen, the second table contains values needed for the second column of the screen, and the third table values for the third column. In the FLI display loop prior to the STA SCROLY command, the current rasterline is used as an index to all three tables. The values are then fetched from the tables and inserted into the code that follows the STA SCROLY command using self-modifying code techniques. When the STA SCROLY happens, the code that immediately follows it starts writing the values onto the databus, all three in a row to complete the first three columns of the screen. There is a disadvantage with this approach. It requires that three 200-byte tables be specially constructed and stored somewhere in memory that is not mirrored by the SuperCPU. A routine would have to read in a FLI graphics file, extract information from the first three columns and store it into their respective 200-byte tables. Pasi Ojala came up with a graph depicting the SuperCPU interacting with the VIC-II in action, showing what happens after the forced DMA retrigger at STA SCROLY. The 'LDA #$xx' would have been modified earlier in the FLI routine (before the STA SCROLY) using self-modifying code. Here is the relevant source code which takes up 4 machine cycles inside the host Commodore computer. sta scroly : abcd, d = write Y to SCROLY on 1MHz bus CPU half - Mach. Cycle #1 lda #$00 : ef sta $d022 : ghij, j = write 1 to $D022 on 1MHz bus CPU half - Mach. Cycle #2 lda #$00 : kl sta $d022 : mnop, p = write 2 to $D022 on 1MHz bus CPU half - Mach. Cycle #3 lda #$00 : qr sta $d022 : stuv, v = write 3 to $D022 on 1MHz bus CPU half - Mach. Cycle #4 There are the two shared halves consisting of a machine cycle inside the host Commodore bus, and by stashing values onto the databus, this value is carried over to the VIC-II half and is read as videomatrix data during the first three columns of the FLI screen. ________ = VIC-II half of the 1MHz cycle . = SCPU synchronizes to 1MHz bus Each char position is equivalent to a 1 (20MHz) cycle. Mach. Cycle #1 Mach. Cycle #2 Mach. Cycle #3 Mach. Cycle #4 +-------------------+-------------------+-------------------+------------------- __________YYYYYYYYYY___DMA____1111111111___col0___2222222222___col1___3333333333___col2___ 1MHz abc.......ddddddddddefghi.....jjjjjjjjjjklmno.....ppppppppppqrstu.....vvvvvvvvvv SCPU Values on the databus which is carried over onto the VIC-II half of the databus: DMA: DMA condition detected by VIC-II col0: colors for column 0 read, gets the value 1 put into the bus by SCPU col1: colors for column 1 read, gets the value 2 put into the bus by SCPU col2: colors for column 2 read, gets the value 3 put into the bus by SCPU An alternative approach bites the dust The SuperCPU can also fetch values onto the databus by reading from the I/O region. If a coder were so inclined to use a 'Read I/O Approach', where is a program going to find 600 free bytes in the i/o region at $d000-$dfff? The idea is to force the SuperCPU to do a read on the databus via DMA and this can't be done with mirrored locations similar to the ones used in those VIC optimization modes. When a SuperCPU reads a value from mirrored memory, it does so from its local RAM and not the RAM that is inside the host Commodore computer. However, if the SuperCPU reads from the I/O block at $d000-$dfff, it will read a value from inside the host Commodore computer using DMA. Unfortunately, this approach did not work when the BA line went high inside the host Commodore computer and is unworkable for a full-screen FLI mode. The SuperCPU stops for reads if BA is high, just like its 1MHz 6510/8510 counterpart. Other Considerations. There were some interesting observations while debugging the full-screen FLI routines. The full-screen FLI routines were originally inspired by Robin Harbron's IRQ-based IFLI routines. Because they are driven by an IRQ, the CPU is still available for normal computational tasks. When all three videomatrix values are written to after the STA SCROLY in the line-interruptible FLI routine, the IRQ must then exit quickly with the restoration of the registers. It's a good idea to avoid writing to any mirrored location or read/write to any I/O region ($D000-$DFFF), since the SuperCPU will have to wait for VIC to finish with the data bus. Using a raster IRQ will naturally lead to trouble, since cycle-exact timing is needed, so a CIA timer is used. The timer may be set to synchronize a PAL or NTSC machine. Then in the FLI routine the timer can be checked and indexed into a table of preset timing values so that the forced badline retrigger at STA SCROLY will always happen at the right time on the screen, no matter what the SuperCPU is doing when the VIC-II interrupted it with an raster IRQ. Thanks goes to Ninja/The-Dreams (aka Wolfram Sang) for tips on how to create a stable line-interruptible FLI routine using timers. Source code Without further ado, here is the source code. This source code was used in the Santa Claus FLI Demo for Wheels OS. This code will run in either Commodore 64 or 128 computers and in either PAL or NTSC systems. It did take a lot of tweaking at Points #1, #2, #3, #4, & #5 as I tried to perfect the routines as closely as possible. The full source code for the Santa Claus FLI demo can be supplied via email upon request. It is in Concept+ (geoProgrammer) format. ; Wedges the full-screen FLI interrupt handler in Wheels systems. ; Thanks goes to Robin Harbron for the idea of a line-interruptible FLI routine. InstallFLI: ; Installs the FLI routine jsr ClearMouseMode ; Turn off the mouse. sei lda CPU_DATA ; Save 6510/8510 Location #$01. sta r6510 lda screenMode ; Check computer. bne 2$ ; Take branch in 128 mode. lda #IO_IN .byte $2c 2$: lda #%00110111 ; for 128 mode only sta CPU_DATA lda vmcsb ; Save original video bank info for Wheels. sta oVMBmp lda scroly ; save screen Y axis sta yaxis MoveW $fffe, oldVector ; Saves the old Wheels IRQ vector. lda #<fli ; Sets up fli raster. sta $fffe ; At the IRQ interrupt vector. lda #>fli sta $ffff ; Point #1 lda #$31 ; Trigger the IRQ request sta raster ; At rasterline 49. lda scroly and #$7f ; Clear bit 7 of raster register. sta scroly lda #1 sta vicirq ; Ack raster ints. cli rts RemoveFLI: ; Removes the FLI routine sei MoveW oldVector, $fffe ; Restores the old Wheels IRQ vector. lda #$fb ; Trigger the IRQ request sta raster ; At rasterline 251. lda yaxis ; restore screen Y axis and #$7f ; Clear bit 7 of raster register. sta scroly lda #1 sta vicirq ; Ack raster ints. lda oVMBmp ; Restore original video bank info for Wheels. sta vmcsb lda r6510 sta CPU_DATA ; Restores 6510 Port #$01 cli jmp StartMouseMode ; Start the mouse on. fli: ; The actual FLI interrupt routine lies here. pha .byte $da ;phx .byte $5a ;phy php ; Save processor flags. ; Point #2 ldx #$03 ; #$0f for PAL SuperCPU systems. 3$ dex bpl 3$ lda raster tax ldy colOneClrs,x ; Get colors for the first three columns. sty mark4+1 ldy colTwoClrs,x sty mark5+1 ldy colThreeClrs,x sty mark6+1 ; ldy backgndTable,x ; Get background color for scanline. ; stx $d021 inx ; Point #3 cpx #$f9 ; Have we reached scanline 249? bne 1$ ; Point #1 ldx #$31 ; Restart the IRQ at rasterline 49. 1$: stx raster ; By this time, the raster interrupt register is ; incremented by one, and will re-trigger the ; same fli routine. ; This way, it is fully line-interruptible ; and frees up SuperCPU time. ldy #$01 sty vicirq ; Ack raster ints. and #$07 ; Mask out lower three bits. tax ldy tabd018,x ; Use preset values for vmcsb. lda d011tab,x ; Use preset values for scroly. sty vmcsb ; Select video matrix. sta scroly ; Forces the badline. mark4: lda #$00 ; Stores a video matrix value onto the first column. sta $d022 mark5: lda #$00 ; Stores a video matrix value onto the second column. sta $d022 mark6: lda #$00 ; Stores a video matrix value onto the third column. sta $d022 plp ; Restore processor flags. .byte $7a ;ply .byte $fa ;plx pla ; Do NOT use any memory accesses to the host rti ; Commodore databus in this part because it will ; be blocked by the VIC-II badline. ; Point #4 tabd018: ; Preset video matrix values. .byte $78,$08,$18,$28,$38,$48,$58,$68; NTSC systems ;.byte $08,$18,$28,$38,$48,$58,$68,$78 - PAL systems d011tab: ; Preset VIC DMA retrigger values. .byte $38,$39,$3a,$3b,$3c,$3d,$3e,$3f ChkAbortKey: ; Checks the RUN/STOP keypress. LoadB $dc00, #$7f ; check for the STOP key 3$: asl $dc01 ; Check for the RUN/STOP keypress. ; This also synchronizes the line-interruptible FLI routine. bcs 3$ ; Branch if it isn't pressed. rts prep3Cols: ; Prepares the first three columns of the FLI screen ; Ideally, a FLI file would be loaded in and this ; routine would then be called to set up the three ; 200-byte tables corresponding to each column, ; covering the first three columns of the screen. lda #$40 sta mark1+2 ; Prepare the marks. sta mark2+2 sta mark3+2 ldy #$00 sty mark1+1 iny sty mark2+1 iny sty mark3+1 php sei lda screenMode beq 1$ ; take branch in 64 mode. lda $ff00 pha ; save 128 configuration. lda #%01111110 ; select RAM at $4000 sta $ff00 1$: ldy #$00 ldx #$07 ; Use self-modifying code to create three ; Point #5 mark1: lda $4000 ; 200-byte tables for each column of the sta colOneClrs+49,y ; FLI screen and each value is indexed by mark2: lda $4001 ; the scanline in the FLI routine. sta colTwoClrs+49,y mark3: lda $4002 sta colThreeClrs+49,y ; use +48 for the column offset in PAL clc ; systems. lda mark1+2 adc #$04 sta mark1+2 sta mark2+2 sta mark3+2 iny dex bpl mark1 sec lda mark1+2 sbc #$20 sta mark1+2 clc lda mark1+1 adc #$28 sta mark1+1 tax inx stx mark2+1 inx stx mark3+1 lda mark1+2 adc #$00 sta mark1+2 sta mark2+2 sta mark3+2 cpy #200 bne mark1-2 lda screenMode beq 2$ ; take branch in 64 mode. pla sta $ff00 ; restore 128 configuration. 2$: plp rts .ramsect $1000 ; All column colors are referenced by scanline. colOneClrs: ; Column one colors of the FLI screen. .block 256 colTwoClrs: ; Column two colors of the FLI screen. .block 256 colThreeClrs: ; Column three colors of the FLI screen. .block 256 Hopefully the full-screen FLI possibilities that the SuperCPU can now unlock will bring forth cool software for our SuperCPU's and tons of 'eye candy'. Enjoy. ....... .... .. . C=H 20 :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Main Articles :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: VIC KERNAL Disassembly Project - Part V Richard Cini February, 2002 Introduction ============ In Part 4 of this series, we discovered that of the 39 ROM routines available to be called by user code, 26 of them related to device I/O. The path to using a device from machine code was to first "open" it. So, we looked at the routines required to open and begin using a logical device. When we concluded the discussion on the OPEN command, we left out seven routines dealing with the tape device. This is some of the most complex code I've ever seen. Unlike the IEEE serial peripherals, the tape deck is a "dumb" device, meaning that the VIC Kernal has to do the work of moving the data to/from the tape. With the serial peripherals, the Kernal just sends a character to the device that then acts on it independently of the VIC. After opening the device, there are nine non-tape routines to deal with getting data into and out of the VIC, including talking and untalking, listening and unlistening, moving the characters in and out, and some secondary address stuff. In this installment, we'll conclude our discussion of the OPEN procedure by looking at the tape routines that are called from OPEN. Later articles will discuss the actual movement of bits to and from the cassette and the remaining IEEE serial routines, as well as the loading and saving of files. Tape Routines ============= In the last installment, we examined the beginnings of opening a device for use by a program. The reader will find that the routines are convoluted and hard to follow, with jumps and branches into apparently unrelated subroutines. Overall it appears to be ugly but highly functional code. Here's a "calling tree" outline to the routines called by OPEN: IOPEN---- |-FIND (analyzed in Part IV of this series) |-SENDSA (ultimately handles IEEE serial stuff) |-SEROPN (handles RS232 stuff) | |(all tape-related from here down) |-GETBFA (get address of tape buffer) |-PLAYMS (prompt user to press PLAY on tape deck) | |-TPSTAT (tape key status) | |-TPSTOP (check for STOP keyboard key during tape ops) | |-SRCHMS (print "Searching" or "Searching for..." messages) |-LOSCPH (locate a tape header with filename matching one in | OPEN) |-LOCTPH (locate first/next header; no filename specified) | |-SETBST (sets tape buffer start/end pointers) | |-PLAYMS (see above) | |-TPCODE (main tape code-moves bits in and out on IRQ) | |-SBIDLE (serial buss idle check) | |-STOIRQ1 (put key tape vectors into table) | |-NCHAR (sets bit counter for char input operations) | |-TPSTOP (see above) | |-IUDTIM (update jiffy clock; previous installment) | |-RECDMS (prompt user to press PLAY & RECORD on tape deck) |-WRTPHD (write a tape header to tape) | |-SETSBT (see above) | |-TPWRIT1 (precedes TPCODE by 12 bytes) When dealing with the tape, it helps to understand that Commodore built the tape protocol with an eye towards readability under adverse conditions, including tape quality and motor speed. This made Commodore tapes probably one of the most reliable data systems when compared to TI, Apple, and Tandy, among others. Data headers and data blocks are repeated on the tape and a comparison is made between the two reads to ensure integrity. Additionally, the recording method is self-clocking so the effects of varying tape speed are minimized. One of the first routines used in opening the tape device is determining the address of the tape buffer and making sure that it's in the $02xx page (or higher) of the system RAM. A test at IOPEN_S5 bails out with an "illegal device" error if the tape buffer isn't just so. F84D ;============================================================= F84D ; GETBFA - Get start of tape buffer F84D ; Returns buffer address in .X (LSB) and .Y (MSB) F84D ; F84D GETBFA F84D A6 B2 LDX TAPE1 F84F A4 B3 LDY TAPE1+1 F851 C0 02 CPY #$02 ;is buffer at $02xx? F853 60 RTS PLAYMS is called by IOPEN at IOPEN_S6. A test there determines if we're trying to read/load or write/save from/to a tape. Read mode results in the "Press Play..." message, the "Searching for..." message and two routines that search for the appropriate tape header. F894 ;=============================================================== F894 ; PLAYMS - Wait for tape key on read F894 ; F894 PLAYMS F894 20 AB F8 JSR TPSTAT ;get tape key status F897 F0 1C BEQ TPSTEX ;$F8B5 pressed? yes, exit. F899 F899 A0 1B LDY #KIM_PLAY ;offset for "Press Play..." message F89B PLAYMS1 F89B 20 E6 F1 JSR MSG ;print it F89E WTPLAY F89E 20 4B F9 JSR TPSTOP ; check for STOP key F8A1 20 AB F8 JSR TPSTAT ;get key status F8A4 D0 F8 BNE WTPLAY ;$F89E wait for PLAY switch F8A6 A0 6A LDY #KIM_OK ;offset for "OK" message F8A8 4C E6 F1 JMP MSG ;print it and return to caller This simple routine prints the "Searching for..." message only if in direct mode, and if appropriate, the filename that is being searched for. If no filename is present, the message is changed to "Searching..." (without the "for") before it's output to the screen. F647 ;============================================================== F647 ; SRCHMS - Print "Searching for [filename]" F647 ; F647 SRCHMS F647 A5 9D LDA CMDMOD ;direct mode? F649 10 1E BPL SRCHEX ;$F669 no (programmed mode), exit F64B F64B A0 0C LDY #KIM_SRCH ;"Searching" message F64D 20 E6 F1 JSR MSG ;output message F650 A5 B7 LDA FNMLEN ;get filename length F652 F0 15 BEQ SRCHEX ;$F669 no filename, skip "for" F654 A0 17 LDY #$17 ;point to "FOR" in "Searching For" F656 20 E6 F1 JSR MSG ;print it F659 ; F659 ; FLNMMS - Print filename F659 ; F659 FLNMMS F659 A4 B7 LDY FNMLEN ;get filename length F65B F0 0C BEQ SRCHEX ;$F669 no filename, exit F65D A0 00 LDY #$00 F65F FLNMLP ; loop to print filename F65F B1 BB LDA (FNPTR),Y ;get character F661 20 D2 FF JSR CHROUT ; and print it F664 C8 INY F665 C4 B7 CPY FNMLEN F667 D0 F6 BNE FLNMLP ;$F65F loop F669 SRCHEX F669 60 RTS ;exit If the user is attempting to open a tape file with a specific filename, the IOPEN code makes a call to LOCSPH in IOPEN_S6 to find the file header associated with the filename. If the specific header is not found, the routine emits the "File not Found" error message. LOCSPH is a loop wrapper around the LOCTPH routine that searches for the "next" file header regardless of name. The secondary address parameter of the OPEN command defines whether the action is to (0) read a tape file and relocate it in memory, (1) read a tape file without relocation (a machine program), or (2) write a tape file and put both EOF an EOT markers after it. Once a header is found, the filename from the header is compared to the filename in the OPEN command to see if there's a match. F867 ;============================================================ F867 ; LOCSPH- Find specific tape header F867 ; F867 LOCSPH F867 20 AF F7 JSR LOCTPH ;search for next header F86A B0 1D BCS LCSPEXC+1 ;$F889 returned EOT? Go to ready F86C A0 05 LDY #$05 ;filename offset in header F86E 84 9F STY TPTR2 ;save offset F870 A0 00 LDY #$00 ;loop counter F872 84 9E STY TPTR1 ;save it F874 LCSPHLP F874 C4 B7 CPY FNMLEN ;compare filename length F876 F0 10 BEQ LCSPEXC ;$F888 counter 0, exit F878 F878 B1 BB LDA (FNPTR),Y ;get filename letter F87A A4 9F LDY TPTR2 ; offset to name in header F87C D1 B2 CMP (TAPE1),Y ;compare to tape header F87E D0 E7 BNE LOCSPH ;f867 different, get next header F880 E6 9E INC TPTR1 ;increment counters F882 E6 9F INC TPTR2 F884 A4 9E LDY TPTR1 F886 D0 EC BNE LCSPHLP ;$F874 compare next character F888 LCSPEXC F888 18 CLC ; exit success F889 60 RTS Tape searches are performed linearly, so the LOCTPH routine is used to search for the next file header on the tape starting from the current tape position. This routine is also called by LOAD through IOPEN if no filename is provided as a parameter to the LOAD (or OPEN) call. Additionally, it's called in a loop by the LOCSPH routine when searching for a specific file. LOCTPH reads a tape block to the tape buffer using TPREAD and examines a few important fields in the file header. The fields examined indicate the file type and the filename. If the file header indicates that the file is anything other than a program file or a data file, the routine looks for another file header until it reaches the end of the tape. If BASIC is in "direct mode", LOCTPH prints the "Found" message in addition to the filename. F7AF ;============================================================ F7AF ; LOCTPH - Read any tape header F7AF ; Header type: 1=BASIC program, 2=data block, 3=machine program, F7AF ; 4=data header, 5=end-of-tape marker F7AF ; F7AF LOCTPH F7AF A5 93 LDA IOFLG2 F7B1 48 PHA ;save load/verify flag F7B2 20 C0 F8 JSR TPREAD ;read tape block to buffer F7B5 68 PLA F7B6 85 93 STA IOFLG2 ;restore flag F7B8 B0 2C BCS LOCTPEX ;F7E6 error, end search F7BA A0 00 LDY #$00 ;index reg F7BC B1 B2 LDA (TAPE1),Y ;get header type F7BE C9 05 CMP #$05 ;EOT? F7C0 F0 24 BEQ LOCTPEX ;$F7E6 yes, exit F7C2 C9 01 CMP #$01 ;BASIC program? F7C4 F0 08 BEQ LOCTP1 ;$F7CE yes, branch F7C6 C9 03 CMP #$03 ;ML program? F7C8 F0 04 BEQ LOCTP1 ;$F7CE yes, branch F7CA C9 04 CMP #$04 ;data header? F7CC D0 E1 BNE LOCTPH ;must be data block-skip it F7CE LOCTP1 ;program or data header comes here F7CE AA TAX F7CF 24 9D BIT CMDMOD ;direct mode? F7D1 10 11 BPL LOCTPEX-2 ;$F7E4 no, continue F7D3 A0 63 LDY #KIM_FOUN ;setup for "Found" msg F7D5 20 E6 F1 JSR MSG ;print it F7D8 A0 05 LDY #$05 ;offset to file name F7DA LOCLOOP ; loop to print filename F7DA B1 B2 LDA (TAPE1),Y ;print loop F7DC 20 D2 FF JSR CHROUT F7DF C8 INY F7E0 C0 15 CPY #$15 ;21 characters max F7E2 D0 F6 BNE LOCLOOP ;$F7DA loop F7E4 18 CLC F7E5 88 DEY F7E6 LOCTPEX F7E6 60 RTS The TPREAD routine is responsible for the setup required to read or verify a block from the tape. It prompts the user to press the PLAY button on the tape deck, disables system interrupts and sets some important parameters before execution falls through to the code responsible for starting the tape IRQ routines. In many Commodore machines, tape operations are performed under the operation of a routine installed as a temporary IRQ handler -- sort of a cheap multitasking so that the system doesn't appear to be hung while tape operations are occurring. Execution ultimately comes to code at $F8EF (TPCODE) which is responsible for installing and starting the tape IRQ routine. All of this and we haven't yet reached the bits on the tape :-) F8C0 ;========================================================== F8C0 ; TPREAD - Read tape block F8C0 ; F8C0 TPREAD F8C0 A9 00 LDA #$00 F8C2 85 90 STA CSTAT ;clear status variable... F8C4 85 93 STA IOFLG2 ;and read/verif flag F8C6 TPREAD1 F8C6 20 54 F8 JSR SETBST ;set tape buffer pointers F8C9 ; F8C9 ; load program F8C9 ; F8C9 TPREAD2 F8C9 20 94 F8 JSR PLAYMS ;wait for Play key F8CC B0 1F BCS TPCODE-2 ;$F8ED (in TPWRIT1) F8CE F8CE 78 SEI ;disable interrupts F8CF A9 00 LDA #$00 ;clear work memory for IRQ routines F8D1 85 AA STA RIDATA F8D3 85 B4 STA BITTS F8D5 85 B0 STA TPCON1 F8D7 85 9E STA TPTR1 F8D9 85 9F STA TPTR2 F8DB 85 9C STA BYTINF F8DD A9 82 LDA #$82 ;Timer H constant F8DF A2 0E LDX #$0E ;number for IRQ vector F8E1 D0 11 BNE TPCODE1 ;$F8F4 (TPCODE1 in TPWRIT below) ; falls through to TPWRIT below) SRCHMS also calls this small routine to determine if a key is pressed on the tape deck. TPSTAT looks at PA6 on VIA1 to determine the key state and sets up the Z flag for a compare to be performed in SRCHMS. F8AB ;============================================================ F8AB ; TPSTAT - Check tape key status F8AB ; F8AB TPSTAT F8AB A9 40 LDA #%01000000 ;$40 F8AD 2C 1F 91 BIT D1ORAH ;switch sense F8B0 D0 03 BNE TPSTEX ;$F8B5 not pressed, exit F8B2 2C 1F 91 BIT D1ORAH ;button pressed. Setup for another F8B5 ;compare later. Z=1 if pressed F8B5 TPSTEX F8B5 18 CLC F8B6 60 RTS ;return clear One of the tests performed in IOPEN (also at IOPEN_S6) is to determine if the tape operation is a read or a write. If we're in the write mode, the code jumps to IOPEN2. At IOPEN2, the Kernal prompts for the user to press play and record on the tape deck and then writes a file header by calling WRTPHD with a control ID of $04 (a data header). Then, IOPEN writes a control byte ID of $02 (block is a data block) to the tape buffer and returns. RECDMS is called by IOPEN to determine if a key is pressed on the tape deck and if not, sets the message flag to the "Press Play & Record" message and prints the message by calling into the PLAYMS routine. PLAYMS prints the message and then checks for the key press. F8B7 ;=========================================================== F8B7 ; RECDMS - Wait for tape key on write F8B7 ; F8B7 RECDMS F8B7 20 AB F8 JSR TPSTAT ;get button status F8BA F0 F9 BEQ TPSTEX ;$F8B5 pressed? Yes, continue F8BC A0 2E LDY #KIM_RECP ;no, remind to "Press Play & Record" F8BE D0 DB BNE PLAYMS1 ;exit through $F89B IOPEN calls WRTPHD at IOPEN2 with $04 as the control byte (following block is a data header) to be written into the header. WRTPHD then writes some critical information into zero-page locations in advance of filling the tape buffer with the same information. At the end of the routine, the data is written to the tape in WRTPH1. F7E7 ;========================================================== F7E7 ; WRTPHD - Write tape header F7E7 ; On entry, .A is the header type: 2=data blk; 4=data hdr F7E7 ; F7E7 WRTPHD F7E7 85 9E STA TPTR1 ;save header type F7E9 20 4D F8 JSR GETBFA ;get tape buffer address F7EC 90 5E BCC WRTPEX ;$F84C exit if not right F7EE A5 C2 LDA STAL+1 ; save some program info F7F0 48 PHA ;save...start H F7F1 A5 C1 LDA STAL F7F3 48 PHA ;...start L F7F4 A5 AF LDA EAL+1 F7F6 48 PHA ;...end H F7F7 A5 AE LDA EAL F7F9 48 PHA ;...end L F7FA A0 BF LDY #$BF ;buffer length-1 (191) F7FC A9 20 LDA #$20 ; {space} F7FE WRTPLP1 ; write program data to tape buffer F7FE 91 B2 STA (TAPE1),Y ;clear buffer F800 88 DEY F801 D0 FB BNE WRTPLP1 ;$F7FE F803 A5 9E LDA TPTR1 ;get header type F805 91 B2 STA (TAPE1),Y ;write it F807 C8 INY F808 A5 C1 LDA STAL ;get start L F80A 91 B2 STA (TAPE1),Y ;write it F80C C8 INY F80D A5 C2 LDA STAL+1 ;get start H F80F 91 B2 STA (TAPE1),Y ;write it F811 C8 INY F812 A5 AE LDA EAL ;get end L F814 91 B2 STA (TAPE1),Y ;write it F816 C8 INY F817 A5 AF LDA EAL+1 ;get end H F819 91 B2 STA (TAPE1),Y ;write it F81B C8 INY F81C 84 9F STY TPTR2 ;save buffer offset F81E A0 00 LDY #$00 ;filename loop counter F820 84 9E STY TPTR1 ;save loop counter F822 WRTPLP2 ; write filename to buffer F822 A4 9E LDY TPTR1 ;get loop counter F824 C4 B7 CPY FNMLEN ;compare filename length F826 F0 0C BEQ WRTPH1 ;$F834 done F828 B1 BB LDA (FNPTR),Y ;get filename char F82A A4 9F LDY TPTR2 ;get tape buffer pointer F82C 91 B2 STA (TAPE1),Y ;write char to buffer F82E E6 9E INC TPTR1 ;increment loop counters F830 E6 9F INC TPTR2 F832 D0 EE BNE WRTPLP2 ;$F822 loop F834 WRTPH1 ; flush buffer to tape F834 20 54 F8 JSR SETBST ;set start and end address pointers F837 A9 69 LDA #$69 ;checksum block ID F839 85 AB STA RIPRTY ;save parity character F83B 20 EA F8 JSR TPWRIT1 ;$F8EA write block F83E A8 TAY ;restore start and end addresses F83F 68 PLA F840 85 AE STA EAL F842 68 PLA F843 85 AF STA EAL+1 F845 68 PLA F846 85 C1 STA STAL F848 68 PLA F849 85 C2 STA STAL+1 F84B 98 TYA F84C F84C WRTPEX F84C 60 RTS ;exit SETBST is a helper routine called by LOCTPH and WRTPHD to setup the tape buffer before a tape operation takes place. It sets the starting address of the buffer to the first address of the assigned buffer range and sets the end of the buffer to start + 192 bytes. F854 ;========================================================== F854 ; SETBST - Set buffer start/end pointers F854 ; F854 SETBST F854 20 4D F8 JSR GETBFA ;get buffer address F857 8A TXA F858 85 C1 STA STAL ;start=start of buffer F85A 18 CLC F85B 69 C0 ADC #$C0 ;end=start+192 F85D 85 AE STA EAL F85F 98 TYA F860 85 C2 STA STAL+1 F862 69 00 ADC #$00 F864 85 AF STA EAL+1 F866 60 RTS TPWRIT performs the nuts and bolts of moving cassette data in and out of the VIC. The VIC moves tape data by using a series of interrupt routines that are swapped into the IRQ vector as needed. The benefit here is that the tape IRQ code is then executed 60 times per second, along with normal processing, until the operation is complete, resulting in a cheap form of multitasking. TPWRIT performs some setup chores before changing the IRQ vector, including clearing interrupts, ensuring that the IEEE serial bus is idle, saving the old vector, assigning the new vector and setting-up the variables used by the tape IRQ routine to actually move bits. Finally, interrupts are enabled at $F92E which starts the whole process. When the tape IRQ routine is finished it restores the IRQ vector to the standard $EABF which is detected by TPWRIT at TPCDLP2 (an I/O loop). When completed, TPWRIT exits through the TPSTOP routine. This loop also updates the jiffy clock. F8E3 ;========================================================== F8E3 ; TPWRIT - Initiate tape write F8E3 ; F8E3 TPWRIT F8E3 20 54 F8 JSR SETBST ;get buffer pointers F8E6 A9 14 LDA #$14 ;checksum F8E8 85 AB STA RIPRTY ;save it F8EA ; F8EA ; write buffer to tape F8EA ; F8EA TPWRIT1 F8EA 20 B7 F8 JSR RECDMS ;wait for Record+Play keys F8ED B0 68 BCS TPSTPX1 ;$F957 exit F8EF ; F8EF ; TPCODE - Common tape code F8EF ; F8EF TPCODE F8EF 78 SEI ;disable interrupts F8F0 A9 A0 LDA #%10100000 ;$A0 Timer H constant F8F2 A2 08 LDX #%00001000 ;$08 offset for tape IRQ vector F8F4 TPCODE1 F8F4 A0 7F LDY #%01111111 ;$7F disable interrupts F8F6 8C 2E 91 STY D2IER ;save to interrupt enable reg F8F9 8D 2E 91 STA D2IER ; on VIAs F8FC 20 60 F1 JSR SBIDLE ;wait for timeout F8FF AD 14 03 LDA IRQVP ;save current IRQ Vector F902 8D 9F 02 STA TAPIRQ F905 AD 15 03 LDA IRQVP+1 F908 8D A0 02 STA TAPIRQ+1 F90B 20 FB FC JSR STOIRQ1 ;$FCFB .X=8 set tape IRQ vectors F90E A9 02 LDA #$02 ;read # of blocks F910 85 BE STA FSBLK F912 20 DB FB JSR NCHAR ;set bit counter for serial shifts F915 AD 1C 91 LDA D1PCR F918 29 FD AND #%11111101 ;$FD CA2 manual low F91A 09 0C ORA #%00001100 ;$0C force bits 2,3 high F91C 8D 1C 91 STA D1PCR ;switch on tape drive F91F 85 C0 STA CAS1 ;flag as on F921 A2 FF LDX #$FF ;delay loop for high (outer) F923 A0 FF LDY #$FF ;inner loop F925 TPCDLP1 F925 88 DEY F926 D0 FD BNE TPCDLP1 ;$F925 F928 CA DEX F929 D0 F8 BNE TPCDLP1-2 ;$F923 outside loop F92B 8D 29 91 STA D2TM2H F92E 58 CLI ;allow tape interrupts F92F ; F92F ; wait for I/O-end F92F ; F92F TPCDLP2 F92F AD A0 02 LDA TAPIRQ+1 ;check IRQ direction F932 CD 15 03 CMP IRQVP+1 ;standard vector? F935 18 CLC F936 F0 1F BEQ TPSTPX1 ;$F957 yes, ready F938 20 4B F9 JSR TPSTOP ;no, check STOP key F93B AD 2D 91 LDA D2IFR ;timer 1 IF clear? F93E 29 40 AND #%01000000 ;$40 F940 F0 ED BEQ TPCDLP2 ;$F92F continue F942 AD 14 91 LDA D1TM1L ; get timer 1 loword F945 20 34 F7 JSR IUDTIM ;update RTC F948 4C 2F F9 JMP TPCDLP2 ;$F92F loop TPSTOP is another helper routine. It scans for the keyboard STOP key, and if detected, restores the standard IRQ vector and returns to the caller's caller (the caller to TPWRIT). F94B ;=========================================================== F94B ; TPSTOP - Check for tape stop F94B ; F94B TPSTOP F94B 20 E1 FF JSR STOP ;scan STOP key F94E 18 CLC F94F D0 0B BNE TPSTPX ;$F95C not pressed, return F951 20 CF FC JSR RESIRQ ;pressed, turn drive off and restore IRQ F954 38 SEC ;set error flag F955 68 PLA ;pop return address F956 68 PLA F957 TPSTPX1 F957 A9 00 LDA #$00 ;flag normal IRQ vector F959 8D A0 02 STA TAPIRQ+1 F95C TPSTPX F95C 60 RTS ; return to caller's caller The SBIDLE routine is used in TPWRIT to detect if the RS-232 serial bus is active and if so, will wait until it's idle before returning to continue the tape code. F160 ;=========================================================== F160 ; SBIDLE - Set timer for serial bus timeout F160 ; F160 SBIDLE F160 48 PHA ;save .A F161 AD 1E 91 LDA D1IER ;get IER F164 F0 0C BEQ SBIDLEX ;$F172 no interrupts pending, exit F166 SBIDLLP F166 AD 1E 91 LDA D1IER ;get IER F169 29 60 AND #%01100000 ;$60 T1 & T2 F16B D0 F9 BNE SBIDLLP ;$F166 F16D F16D A9 10 LDA #%00010000 ;$10 kill CB1 RS232 F16F 8D 1E 91 STA D1IER F172 SBIDLEX F172 68 PLA F173 60 RTS RATS3 is at the tail end of the RAMTAS routine - the subroutine that precedes the tape vectors. FCF6 ;=========================================================== FCF6 ; STOIRQ - Set IRQ vector FCF6 ; usually called with .x=$08 or $0e. $08 points to the first FCF6 ; entry in TAPVEC while $0e points to the last entry FCF6 STOIRQ FCF6 20 CF FC JSR RESIRQ ;restore std IRQs FCF9 F0 97 BEQ TPEOI ;$FC92 FCFB STOIRQ1 FCFB BD E9 FD LDA RATS3,X ;$FDE9,X set vectors from table FCFE 8D 14 03 STA IRQVP FD01 BD EA FD LDA RATS3+1,X ;$FDEA,X FD04 8D 15 03 STA IRQVP+1 FD07 60 RTS These are the actual routines responsible for writing bits to the tape. Various calling routines place these vectors into the IRQ vector that then gets executed 60 times per second. In order, these routines are for writing a leader block to the tape, the routine to write data to the tape, the standard IRQ vector, and the routine to read bits from the tape. FDF1 ;=========================================================== FDF1 ; TAPEVC - Tape IRQ vectors FDF1 ; FDF1 TAPEVC FDF1 ; .dw $FCA8, $FC0B, $EABF, $F98E FDF1 A8FC0BFCBFEA .dw WRLDR2, TWRD7, IRQVEC, RDTPBT FDF7 8EF9 The NCHAR routine resets the internal bit counters to their initial state before a calling routine begins to shift the bits over a serial or tape channel. It sets the bit length to 8 and resets intermediate variables to 0. FBDB ;=========================================================== FBDB ; NCHAR - Set bit counter for new character (serial output) FBDB ; FBDB NCHAR FBDB A9 08 LDA #$08 FBDD 85 A3 STA SBITCF FBDF A9 00 LDA #$00 FBE1 85 A4 STA CYCLE FBE3 85 A8 STA BITCI FBE5 85 9B STA TPRTY FBE7 85 A9 STA RINONE FBE9 60 RTS That's all of the room we have for this part of the series. All of this code and we still haven't moved the bits off the tape. So, next time we'll look at the actual routines responsible for moving bits on and off of the tape and we'll begin to look at the IEEE serial routines. ....... .... .. . C=H 20 :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: ----------------------- The Art Of The Minigame ----------------------- Introduction ------------ In summer 2001, an 8-bit minigame contest was held. Voter turnout may have been low, but author turnout was high, with a total of thirty entries for the C64, Spectrum, Amstrad, and Atari 8-bit. The entries and the results are available at http://demo.raww.net/minigame/, and what follows are a series of articles by several minigame authors. The articles are for enjoyment, to stimulate thought, and, hopefully, to motivate people for next year's contest. (Everyone had a great time, btw.) Minigames -- writing tiny programs in general -- present a set of very unique challenges. Whereas many of us are used to optimizing programs for cycle-efficiency, optimizing programs for byte-efficiency turns out to be very different -- challenging, at times aggrivating, but very rewarding. I think you will find the challenges and solutions ahead to be very interesting. The game authors were pioneers, exploring pretty new territory, and I salute all that entered the contest (especially for making such a nice C64 showing). A special mention should be made of MagerValp ("Skinny Puppy" in Swedish, in case you've been wondering), who motivated a number of lazy people (e.g. myself) to get involved with the contest. Before diving in to the articles ahead, which contain lots of tricks to save memory, I thought it might get us in the mood to go over some general ideas and concerns for saving bytes on a C64. It should be obvious that some balance has to be found between cycle- efficiency and memory-efficiency. Routines should be reasonably fast in most cases, but the major portion of that balance is -- has to be -- memory efficiency. Obviously, everything that can be put into zero page should be put there, since zero page instructions are two bytes instead of three. Equally obvious is that every list-type fetch should use the .X register, since there is no zero-page lda xx,y instruction. Moreover, memory is initialized to various values when the computer is reset. Many zero-page locations have specific values -- by careful code design, these can be taken advantage of to avoid any initialization code. For example, many times the code needs a zero-page pointer with the low byte zero (i.e. sta (point),y). If that variable is chosen as a location which is already zero, the code doesn't have to waste four bytes on lda #00 sta point. One-time counters can also be used in this way. Finally, certain locations can be manipulated to have certain values; for example, the Tetrattack load address forces the end address+1 to be $10f0, because $10 and $f0 are the z-coordinates of two object vertices. There is also a fairly substantial kernal to take advantage of -- routines to clear the screen, perform memory manipulations, and so on. Knowing what is available, and what the routines do, is handy. Self-modifying code comes in handy when large portions of code can be used for similar things with just a few changes. For example, the line routine in Tetrattack uses a single routine for lines in both the x- and y-directions, by just interchanging a few INX/INY instructions. And finally, there are things which Mark Seelye terms "injections", which seems like a good term to me. The idea is to reuse known register values whenever possible. That is, instead of having LDA #00 STA zp in a subroutine, you might put an "STX zp" in an earlier subroutine, where you know the value of .X is zero. In other words, the instruction to clear the zp location is "injected" into a different subroutine to save a couple of bytes. Every program below uses this trick in one form or another. You'll see lots of neat tricks in the articles ahead, but the basic design framework is: put stuff in zero-page, take advantage of default zero-page values, take advantage of the kernal, always know the register values, and reuse as much code as possible. With that, let's check out the programs. ....... .... .. . C=H 20 =====================================Part 1=================================== Postmortem: Codebreaker by White Flame (aka David Holz) http://white-flame.com The most difficult part of making an entry for this compo was deciding what game to do that could fit in 512 bytes. The ubiquitous snake clones and scroll/dodge games abound; finding something different is truly a challenge. I wanted to do a Mastermind game a looong time ago, with a full-on "We're getting attacked, solve to code to save the world!" type of setting with lots of animation, but usually found myself in application and library/utility programming instead. But luckily this idea popped back into my head as something different that would fit in the 2-page limit. The concept is pretty simple (as most 512-byte games are). There's a 4-color secret key, you get 10 guesses at it. Two numbers reflect the score for the current guess: a black number shows how many slots have the right color, and a white number shows how many correct colors are in the guess, but in the wrong slot. Experienced players should be able to deduce the correct answer in 4-6 guesses. Random number generation There are 3 obvious ways to get random numbers easily in the 64: SID oscillator with noise waveform, BASIC prng, or the raster counter. I decided to go for the raster solution. Obviously, you need to wait a certain amount of time between reads of the raster location, or they'd be the same or linear. To fix this, every time I wanted a random number, I'd read the raster and call a loop that many times. When it was done, $d012 should have a "random enough" number in its lower 3 bits (to get a color from 0 to 5). randomDelay: ldx $d012 randomLoop: jsr delay dex bne randomLoop; delay: dey bne delay rts Code space saving What's interesting is that it actually took less bytes of code and data to have custom draw loops for the 3 textual messages than setting a pointer and calling a drawText function. ldy #22 titleloop: lda titletext,y sta screenLoc-48,y dey bpl titleloop: These functions assume that you're not running on an ancient kernal, so color memory is initialized to the cursor color (white). I also had all variables (except the secret key) use screen memory, color memory, or register .Y instead of manipulating off-screen variables and then updating the screen to match: - For entering a guess, color memory is INC'd and DEC'd, with .Y holding the current offset from the fixed screen location. JSR $e8ea is used to scroll the screen, and everything is drawn to screen line 23. - To find out if you've already made 10 guesses, a memory location near the top of the screen was polled to see if it was still a space. As guesses are made, the screen was scrolled, and if the title line ever scrolled into that memory location, it's game over. - The current guess score '0 0' is drawn to the screen first, then those screen values are INC'd or DEC'd as matches are found. - Winning constitutes checking to see if the screen has a '4' in the black score location. Score calculation This was a bit of a pain. At first I trying to calculate the white score by the scoring rules (every matching color that was in the wrong slot), INCing the white score on every hit, then looping for exact matches, INCing the black score on every hit. This code ended up being way too big, so I got the idea to simplify the white loop: INC the white score on every color match, whether in the right spot or not, then on every black match, DEC the white score and INC the black score. This gave the same result, but with much simpler code. Conclusion All in all, it was an interesting challenge for me, and had I not gotten stuck in Phoenix for an extra week, I'd have finished my 2k entry. The code is pretty straightforward, and at 415 bytes total, I'm quite happy to claim having the smallest entry, even if I didn't win (why Pacman didn't beat out a low-res scroll/dodge/single-shot game is a mystery to me). Being a hobbyist C64 programmer, and my career history being more on the research end of things, having a deadline is a nice change in terms of getting a project completed. :) Publisher: Gasman/Raww Arse Number of full-time developers: 1 programmer Number of contractors: 0 Estimated budget: 0 USD (0 EUR) Development time: About 5 hours Release date: August 22, 2001 Platforms: Commodore 64 and compatibles Development hardware: pee sea (1.4GHz T-bird, 512MB RAM, 100GB HD, Win98SE) 3rd party tools: xa, Vice, Notepad In-house tools: none Project size: 290 lines of 6502 assembly code, containing 1 line of tokenized BASIC --- cb.asm --- .word $0801 ;Starting address for loader * = $0801 .word nextLine ;Line link .word $0 ;Line number .byte 158 ;SYS .byte 50,48,54,54 ;"2066" .byte 0 nextLine .byte 0,0 ;end of basic screenGameOver = $0400+(4*40)+16 screenLoc = $0400+(23*40)+16 colorLoc = $d800+(23*40)+16 screen = $fd color = $fb peg = 81 cursor = 87 crsr_up = 145 crsr_down = 17 crsr_left = 157 crsr_right = 29 WaitStart: jsr $ffe4 beq WaitStart Start: ;Change to white lda #$05 jsr $ffd2 ;Clear screen lda #147 jsr $ffd2 ;Set bg colors lda #$00 sta $d020 sta colorLoc sta colorLoc+1 sta colorLoc+2 sta colorLoc+3 sta $ff ;for cursor lda #11 ;dark gray sta $d021 ;Init zp pointers lda #<screenLoc sta screen sta color lda #>screenLoc sta screen+1 lda #>colorLoc sta color+1 ;Draw text ldy #22 titleloop: lda titletext,y sta screenLoc-48,y dey bpl titleloop: ;Randomize values iny newGuess sty $02 guessAgain jsr randomDelay lda $d012 and #$07 cmp #$06 bpl guessAgain ldy $02 checkLoop: ;See if the color's already in the key dey bmi goodGuess cmp secret,y beq guessAgain bne checkLoop goodGuess: ;Save the color and put a peg on the screen to show progress ldy $02 sta secret,y lda #peg sta (screen),y iny cpy #$04 bne newGuess Game_Loop: ;Get cursor pos ldy $ff ;Draw cursor lda #cursor sta (screen),y Key_Loop: ;Wait for key getin: jsr $ffe4 beq getin ldy $ff ;If up, bump color up cmp #crsr_up bne notUp lda (color),y and #$07 adc #$00 ;carry is always set after the cmp cmp #$06 bne colorNotHigh lda #$00 colorNotHigh: sta (color),y notUp: ;If down, bump color down cmp #crsr_down bne notDown lda (color),y and #$07 bne colorNotLow lda #$06 colorNotLow: sbc #$01 ;carry is always set after the cmp sta (color),y notDown: ;If left, cmp #crsr_left bne notLeft ; Erase cursor lda #peg sta (screen),y ; Bump cursor left dey bpl cursorOKLeft ldy #$03 cursorOKLeft: ; Draw cursor lda #cursor sta (screen),y notLeft: ;If right, cmp #crsr_right bne notRight ; Erase cursor lda #peg sta (screen),y iny cpy #$04 bne cursorOKRight ldy #$00 cursorOKRight: lda #cursor sta (screen),y notRight: ;Store cursor pos sty $ff ;If not enter, goto Key_Loop cmp #13 bne Key_Loop ;------------------------ ;Erase cursor lda #peg sta (screen),y ;Check score ;Draw "0 0" lda #'0 sta screenLoc+5 sta screenLoc+7 lda #0 ;black sta colorLoc+5 ;Calculate white score (any matches between the guess & key) ldy #3 yLoop: ldx #3 xLoop: lda (color),y and #$07 cmp secret,x bne noWhiteMatch inc screenLoc+7 noWhiteMatch dex bpl xLoop dey bpl yLoop ;Calculate black score (exact matches between the guess & key) ldy #3 blackLoop: lda (color),y and #$07 cmp secret,y bne noBlackMatch inc screenLoc+5 dec screenLoc+7 noBlackMatch: dey bpl blackLoop ;Check win (black score = "4") lda #'4 cmp screenLoc+5 beq Win ;Check for Game Over (screen's getting full) lda screenGameOver cmp #32 bne Game_Over ;Scroll screen up 2 rows jsr $e8ea jsr $e8ea ;Copy last hand ldy #3 copyLoop: lda colorLoc-80,y sta (color),y lda #peg sta (screen),y dey bpl copyLoop: jmp Game_Loop Game_Over: jsr $e8ea ldy #8 ;Show "YOU SUCK!" loseloop: lda losetext,y sta (screen),y dey bpl loseloop: jsr $e8ea ldy #3 ;Reveal the secret key losecopy: lda secret,y sta (color),y lda #peg sta (screen),y dey bpl losecopy jmp WaitStart Win: jsr $e8ea ldy #15 ;Show Zero Wing reference winloop: lda wintext,y sta screenLoc-4,y dey bpl winloop rts randomDelay: ldx $d012 ;Loop n times, n = current raster location randomLoop: jsr delay dex bne randomLoop; delay: dey bne delay rts wintext .byte 1,32,23,9,14,14,5,18,32,9,19,32,25,15,21,33 losetext .byte 25,15,21,32,19,21,3,11,33 titletext .byte 58,58,58,32,3,54,52,32,3,15,4,5,2,18,5,1,11,5,18,32,58,58,58 secret = * --- end cb.asm --- ....... .... .. . C=H 20 =====================================Part 2=================================== Tinyplay by SLJ -------- Like many people, I was a serious Ultima guy growing up. Not only did I love the games (and still do), but I absolutely loved the music (and still do). In fact, I think the music from III and IV is some of the finest, most musical composing ever done on the C64, and the best example of how appropriate, atmospheric music can add volumes (so to speak) to a game. It also turns out that I had been thinking about some new ideas for a new music system for a while. So when Robin said he was writing an Ultima-like game -- well! I'm certainly no Kenneth W. Arnold, but a set of tiny tunes sure sounded like a neat and fun thing to do, especially in the Ultima style! Robin removed a lot of neat features and text to add in the music, so I feel pretty honored to have been included. The player and tunes were written on pretty short notice; I think we started a week or so before the deadline. Moreover, I had to go out of town the weekend of the deadline, getting back that Sunday, where many of the optimizations took place in frantic coding sessions! So it shouldn't be surprising that the code is not as optimal as it could be -- if you get around to looking at the source code, you'll see an awful lot of weird, duplicate, and otherwise embarrasing lines of code which anyone with a clear head would never have used. But as is, the player and three tunes take up some 428 bytes (I think), which isn't too bad. (Later on I'll describe a music compression routine which would have worked great, but that I didn't have time to implement.) Broadly speaking, the player is a note-duration based player, using two sawtooth voices for that Ultima sound (originally, before reality kicked in, the thinking was to put some sound fx in the third voice). It uses a single play routine, using the .X register to tell which voice to play, and can play multiple tunes. The original version has several effects included like major and minor arpeggios, but memory constraints forced these to be taken out (along with the original tune, alas, alas). The full source code for the player is at the end of this article, and can be divided into four primary parts: a one-time init routine, a routine to select a tune, a routine to play notes, and the music data. But perhaps the best way to understand the player is to begin by looking at how the data for a tune is stored. Tune encoding ------------- Here is the third, "castle" tune, in its entirety: * Tune 3: Castle t2v1 dfb 97 ;gate dfb 24+$80-1 dfb 70,96,72 dfb 6+$80-1 dfb 96,96,70,72 dfb 12+$80-1 dfb 74,74,96,75 dfb 24+$80-1 dfb 77,75,74,96,72 dfb 6+$80-1 dfb 96,96,70,72 dfb 24+$80-1 dfb 70,96,96,96 dfb 00 t2v2 dfb 97 dfb 24+$80-1 dfb 34,41,46,41 dfb 34,41,46,41 dfb 58,62,53,57 dfb 58,53,46,96 dfb 0 end The first chunk of data (t2v1) is the voice 1 data, and the second chunk the voice 2 data (t2v2). There are 12 notes in an octave, and eight octaves total, for 96 possible notes. In the player, data bytes 0-95 represent these notes -- the player just uses the data as an index into a frequency table. This leaves bytes 96 and above free for other uses; also, since the lower note values are rarely used, values like 0, 1, etc. are also free in principle. Byte values >= 128 are used to specify the note duration. When the player encounters these byte values it simply strips the high bit and stores the result. When a new note is read in, this stored duration is placed into a counter which is decremented on each player call. In the castle tune above, the duration for voice 2 is only set once, at the very beginning -- every note has the same duration. In the voice 1 data it is set several times, to change the duration when appropriate. For some reason the code decrements the duration counter until it becomes negative, instead of decrementing it until it becomes zero. I'm sure it was because of something relevant in an earlier version of the player, I just totally don't remember what. But that is why the durations above are encoded as 24+$80-1 -- the -1 is to make it go negative, instead of to zero. Looks weird. Byte values >95 and <128 are available for 'special' features. The player supports one "effect": the gate toggle. The player can either leave the gate bit on all the time or can turn it off right as a note is about to finish (say, when the duration counter decrements down to 2). A byte value of 97 turns the gate toggle on -- in the castle tune above it is the first byte of data. In other tunes, a value of 100 is used to turn off gate toggling. (Historically speaking, values 98 and 99 were used for major and minor arpeggios, and 100 was for no fx at all.) The byte value 96 is used as a "rest" (or hold) -- the player resets the duration counter but does not reset the gate bit or the note value. When there is no gate toggling this provides a way of holding a note for longer than the basic duration. When there is gate toggling, it starts the release cycle, and lets notes fade away. In the castle tune above, the first two notes in voice 1 are "70 96" -- a note, then a rest, during which the note fades away. Finally, the value 0 is used to indicate the end of data. While 0 is technically a note it never gets used as such. When the player hits a zero it simply resets the data pointer. So with all that in mind, let's take a look at the player. The Player ---------- Before playing a tune, a one-time routine is called which sets up the frequency tables; when the player reads a new note, it looks up the SID frequency settings in this table, along the lines of: ldy note,x lda freqlo,y sta $d400 lda freqhi,y sta $d401 Frequencies in different octaves are related by powers of 2. When you go up an octave, the frequency doubles -- for example, the frequency of C-5 is twice the frequency of C-4. The routine starts with a table of twelve frequency values for the highest octaves, and copies those values into the end of the frequency table (e.g. freqlo+95, freqlo+94, ..., freqlo+84). After copying, it divides each value by 2 and repeats the process -- now the frequencies correspond to the next lower octave -- and this is done until the frequency table is full. Piece of cake. Once the frequency table is set up, the main play routine is called with the tune number in .A. If the tune number is different than the current tune, the player simply resets the music data pointers and note durations, and falls through to the main player routine. And the main player routine simply decrements the duration, and when it becomes negative reads in the next data. Because the process -- decrement duration, read next data, store frequencies in SID -- is the same for each voice, a single routine is used for both voices one and two, using .X as the voice index. That is, instead of dec duration the code can use dec duration,x and instead of sta $d400 the code can use something like ldy SidOffset,x sta $d400,x where .X is 0 or 1. And that's about all there is to it -- the code is pretty straightforward. Compressing Music ----------------- Most music has the property that it doesn't jump around all over the place, but rather notes progress in relatively small intervals (seconds, thirds, fifths, etc.). For example, a major chord (as used in a typical arpeggio) is note note+4 note+7 note So the idea is to use a differential scheme, encoding the note _intervals_ instead of the note _values_. That is, the above could instead be encoded as x 4 3 -7 where each value is added to the current note value. Thus, if intervals are restricted to -8..7 then only four bits are required, cutting the data size in half. Well, not quite of course, because an escape code is needed to specify notes outside of the -8..7 range, not to mention durations and fx settings. Luckily, not all interval values are used, so these can be used for escape codes; code 96 -- the rest or "hold" note -- can also use an otherwise unused value. So the decompression code looks something like read next four bits if escape code then read next byte otherwise add to current note value Pretty simple, and leads to quite substantial savings. Ah, but for a little more time... Another possibility arises if not all note values are used. I set up the frequency tables to contain all 12 notes in eight octaves. If not all twelve notes are actually used -- if none of the tunes contain a D# or whatever -- then a few bytes can be shaved off of the frequency table. But this means a lot of renumbering and such... it all depends on just how much you want those extra bytes! And that's about all there is to it. Source code ----------- * * Tiny music player, for the * minigame contest. * * slj 9/23/01 * sjudd@ffd2.com * ; org $2800-491 org $2800-425 ARPDEL = 2 SR = $c9 GATEDEL = 2 curtune = $fe curdur = $fc tunepos = $b0 ;position in note sequence seqpos = $b2 ;position in seq list dur = $b4 ;2 bytes each notefx = $b6 curnote = $b8 newnote = $ba arpdur = $bc arpoff = $bd noteptr = $fa temp = $fa freqtab = $c000 * * Code begins here * start *------------------------------- do 0 jmp InitFreq jmp Play jmp Reset fin *------------------------------- * * InitFreq -- set up note table * InitFreq ldy #192 :l2 ldx #24 :loop lda freq-1,x sta freqtab-1,y dex dey lda freq-1,x sta freqtab-1,y lsr freq,x ror freq-1,x dey beq :xit dex bne :loop beq :l2 :xit rts * * Play routine * tune in .A * Reset ; Force a tune reset sec ror curtune ; ldx #255 ; stx curtune Play ldx #1 cmp curtune beq PlayTune sta curtune ldy #00 sty tunepos ; sty tunepos+1 sty dur sty dur+1 lda #15 sta $d418 lda #SR sta $d406 sta $d406+7 * * Main routine * * voice in .X (0, 1) * SetTune ldy curtune txa beq :v1 :v2 lda v2tunepos,y bne :sta :v1 lda v1tunepos,y :sta sta tunepos,x PlayTune Get lda #00 sta newnote,x dec dur,x bpl DoFx :next ldy tunepos,x inc tunepos,x lda tunes,y beq SetTune bpl :c1 and #$7f ;$80+dur sta curdur,x bne :next :c1 cmp #96 bcc :setfreq beq :hold sta notefx,x bne :next :note ;sta curnote,x ; sta newnote,x ; jsr setfreq :SetFreq asl tay lda Freqtab,y pha lda Freqtab+1,y ldy SidOffset,x sta $d401,y pla sta $d400,y :gate lda #$21 ldy SidOffset,x sta $d404,y :hold lda curdur,x sta dur,x DoFx ldy notefx,x cpy #97 bne AllDone ldy dur,x cpy #GATEDEL bcs :c1 lda #$20 ldy SidOffset,x sta $d404,y :c1 AllDone dex bpl PlayTune RTS rts * * Frequencies * freq da 34334 da 36377 da 38539 da 40831 da 43258 da 45831 da 48557 da 51444 da 54502 da 57743 da 61177 da 64815 ;arptab dfb 0,4,7 * * Tune positions (offset into sequence * list) * v1tunepos dfb t0v1-tunes dfb t1v1-tunes dfb t2v1-tunes v2tunepos dfb t0v2-tunes dfb t1v2-tunes dfb t2v2-tunes tunes ; dfb 00 ;dummy byte * * Sid offset table * SidOffset dfb 00 dfb 07 t0v1 dfb 97 dfb 10+$80-1 ;dur=10 dfb 42,47,51 dfb 42,47,51 dfb 42,47,47,47 dfb 51,51,51 dfb 54,52,51 dfb 52,51,49 dfb 51,51,51 dfb 49,49,49 dfb 51,49,47 dfb 49,47,46 dfb 44,44,44 dfb 46,46,46 dfb 47,51,47 dfb 46,42,46 dfb 47,96,96 dfb 96,96 dfb 00 t0v2 ;v2 dfb 97 dfb 10+$80-1 dfb 35,35,96 dfb 35,35,96 dfb 35,35,96 dfb 35,39,96 dfb 39,42,96 dfb 42,30,96 dfb 30,35,96 dfb 35,34,96 dfb 34,32,96 dfb 32,32,96 dfb 32,32,96 dfb 32,34,96 dfb 34,35,96 dfb 35,30,96 dfb 35,35,96 dfb 35,35,96 dfb 00 * Tune 2: Combat t1v1 dfb 100 ;No gate dfb 11+$80-1 ;dur=11 dfb 51,54,58,59,96 dfb 58,57,54,51,54,58,63,96 dfb 62,61,60,59,56,53 dfb 58,54,51,56,53 dfb 46,50,53,56 dfb 59,58,57,54 dfb 0 t1v2 ;v2 dfb 100 dfb 11+$80-1 dfb 15,27,15,39 dfb 15,27,15,39 dfb 15,27,15,39 dfb 15,27,15,39 dfb 47,44,41,51,46,42,47,44 dfb 22,34 dfb 22,34 dfb 22,34 dfb 22,34 dfb 0 * Tune 3: Castle t2v1 dfb 97 ;gate dfb 24+$80-1 dfb 70,96,72 dfb 6+$80-1 dfb 96,96,70,72 dfb 12+$80-1 dfb 74,74,96,75 dfb 24+$80-1 dfb 77,75,74,96,72 dfb 6+$80-1 dfb 96,96,70,72 dfb 24+$80-1 dfb 70,96,96,96 dfb 00 t2v2 dfb 97 dfb 24+$80-1 dfb 34,41,46,41 dfb 34,41,46,41 dfb 58,62,53,57 dfb 58,53,46,96 dfb 0 end ....... .... .. . C=H 20 =====================================Part 3=================================== MagerTris -- by Per Olofsson <magervalp@cling.gu.se> Way back in 1990 or thereabouts I wrote a Tetris clone in basic on the Amiga. When the compo was announced I scratched my head for a bit and figured that I should have a good chance of fitting Tetris in 512 bytes. If I couldn't I would at least have a good engine for the 2K compo. The Game This puzzle game was invented in the 80s by the Russian programmer Alexey Pazhitnov. The game has a vertical field where one of seven puzzle pieces appears at the top and falls towards the bottom. The player can rotate the piece 90 degrees or move it left or right. When it reaches the bottom the game field is checked for filled lines that are removed. The player is awarded points for removing lines (with a bonus for clearing more than one in one go) and the game is over when the screen fills up so that new pieces can't enter the game field. Drawing the Screen The screen is filled with inverted space and the game pieces and the border is drawn into the color ram. There aren't any real tricks used here, the only one is that the color of the border is a side effect of the last character printed, ascii 13 (light green). Random Numbers We need a decent source of random numbers to generate a random Tetris piece. The SID chip's noise waveform is probably the best one available on the C64, and fortunately the code to access it is really short. To initialize I used: initrnd subroutine lda #$81 ; enable noise sta $d412 ; voice 3 control register sta $d40f ; $81xx as the frequency and to get an 8-bit random number all you have to do is lda $d41b. The Tetris Pieces Tetris has 7 puzzle pieces that you have to store in a table. As every piece consists of four boxes we need a total of 7*4 = 28 entries. The smallest tetris table is probably the one where each piece is represented by 8 bits, like this: 0010 0000 0011 0110 0100 0010 0110 0111 1111 0110 0011 0111 1110 0110 The table is very compact, a mere 7 bytes, but then you need code to rotate every piece and accessing the table is somewhat clunky on the 6502. I've seen an x86 version that did this though, with a total size of less then 256 bytes. However, on the 6502 I needed four bytes for each piece for the code to be reasonably compact and I also kept all the rotated pieces in the table, for a total of 112 bytes. Fortunately, as every piece has a center box we only need to store 3 which trims the table to 84 bytes. But what do we actually store? As the screen is painted to color ram I used a pointer to the current position. In the table I simply stored the offset in color ram from the center box. With indirect indexed addressing the routine is nice and short. Failure The rest of the program is fairly straight forward. User input is just a cmp loop, there are dec zp timers for most events, and a raster wait to time everything. This is also where I failed to fit everything inside the 512 byte limit, as everything put together took about 600 bytes, even after some serious optimizations. There are two very similar routines: the one that draws a piece on the screen and the one that checks for collisions. Both iterate through the four boxes in a piece, but because of the way I used some zeropage pointers I couldn't merge the two routines into one without rewriting most of the code. Success As rewriting everything meant too much work, I just decided to go for plan B: write a 2K entry. With a 600 byte engine there was plenty of space to add features, and at around 700 bytes or so compressíon starts to make sense -- pucrunch breaks even around there somewhere, and the final binary is actually 6500 bytes uncompressed. I could easily fit a title screen complete with custom graphics, a nice tile set for the tetris pieces, and even a hiscore list that saves to disk. The only trick I used here was that the custom character set was EOR:d with the ROM font, and as most characters are the same or very similar it compresses much better that way. And that's the story of the 2K MagerTris. ....... .... .. . C=H 20 =====================================Part 4=================================== Tuff -- Compressing tiny programs -----------------------------------> Stephen L. Judd <sjudd@ffd2.com> Most compression schemes address the problem of taking a large program or data file and compressing it down. But have you given much thought to the problem of trying to compress a _small_ program, even a 512-byte program? I spent some time trying to come up with a compression scheme for tiny programs -- saving even 2 or 3 bytes in tetrattack would have been helpful. The effort was basically a failure, as the best I thought I could do was to break even (on paper, for tetrattack). I never actually implemented the code either -- just worked it out on paper. It is fairly interesting though, and maybe these preliminary efforts will give other people ideas (especially for compressing 2k programs). And after writing this article, I now think it might have really worked, and saved a handful of bytes -- maybe next year? Tiny Compression Basics ----------------------- If you remember your C=Hacking #16, there are two basic approaches to compression: taking a fixed-length input while giving a variable-length output, or taking a variable-length input and producing a fixed-length output. An example of the latter is LZ compression -- looking for repeated strings of length 2, 3, etc. and replacing those with a single byte (or two bytes, or whatever). An example of the former is a Huffman tree, which replaces each byte with a string of bits, using fewer bits for the most common bytes. To decompress the compressed data, of course, a decompression routine is needed. For tiny compression, this routine obviously needs to be as tiny as possible. Most C64 decompression programs copy themselves somewhere before decompressing the data stream to wherever it is supposed to go. Obviously, if we put a few restrictions on the data to be decompressed the decompression routine can be made smaller, and more specific to the task. Finally, it is worth mentioning that a tiny program in general does not use all possible byte values. Now, first consider Huffman encoding. In a typical Huffman decoding scheme, the decoder reads a bit at a time, traversing the Huffman tree with each bit, until a byte is hit. This implies a fairly complicated decoder, and worse the tree must be stored. Finally, the tree can be fairly large, if the number of possible symbols is large. So Huffman doesn't seem like a good approach. So, consider LZ-style encoding: replacing n-byte sequences with a shorter code. In LZ, the n-byte code is replaced with a reference to the previously decompressed bytes -- a code which says how far back to go, and how many bytes to copy. What a drag -- an escape code, the distance backwards, and the number of bytes to copy. For a byte-aligned decompressor, this implies at least two bytes (since the decompression routine must be small, a byte- aligned decompressor is of greater interest). So far so bad. But, since a tiny program doesn't use all possible byte values, perhaps a simple substitution method is possible -- that is, replacing various 2-, 3-, 4- etc. byte sequences with one of those bytes. Alas, the numbers don't work out very well: in the above scheme, let's say an n-byte sequence appears m times, for a total of n*m bytes. We replace each of those sequences with a single byte, giving a savings of n*m - m bytes. But we also need to store the original sequence in a table somewhere, plus the byte corresponding to that sequence. This means another n+1 bytes, so the total savings is n*m - (m+n+1) So, for example, if we have a 2-byte sequence repeated 3 times, the savings is 2*3 - (2+3+1) = 0 bytes! The issue is that replacing a 2-byte sequence with a 1-byte sequence saves one byte, and this must happen at least three times to overcome the three bytes of table storage. With 4 repetitions, one byte is saved. And so on. The net result is that you have to have a _lot_ of sequences repeated a lot of times to get any savings, and somehow this savings needs to be greater than the decompression code. Note that, in general, if there are only a few sequences to replace then some custom code can be shorter, but as the number of sequences increases then generic code, with sequences stored in tables, quickly becomes shorter. The final dagger in the heart of these schemes is the program itself. I wrote a simple program to find all the repeated strings in tetrattack. There were numerous 2-byte sequences, but rarely repeated more than three times. There were a few 3-byte sequences, and even one 4-byte sequence. But overall, there just aren't enough sequences, especially long sequences, to make any sequence-shortening scheme worthwhile. There are, however, lots of repeated bytes. For example, there are an awful lot of STA instructions and zp variables, and usually a lot of zeros. This suggests taking another look at a Huffman-style scheme to replace those bytes with a smaller number of bits. One major problem identified earlier is storing the Huffman tree -- it's just too big. So, the first thing to consider is to just compress the most common bytes -- maybe the top five or eight bytes or whatever -- to make the tree smaller. But that still leaves a substantial decompression code to traverse the tree, and a tree with several empty nodes in it. Once again, if there are only a few nodes then custom code might be shorter, but beyond a few nodes it's more practical to store the tree and have some generic traversal code. But consider the following alternative to a Huffman tree: what if we had a tree which looked like 0/\1 / \ lit 0/\1 / \ b1 0/\1 / \ b2 ... where "lit" is a literal byte and b1, b2, etc. are encoded bytes. This would encode the most common byte with two bits (10), the next-most common byte with three bits (110), and so on, and encode literal bytes with nine bits (0byte). To see if this is a viable scheme, check out the numbers. Let's say that we encoded just the top three most common bytes in a program; in an early version of tetratack those bytes were 00 $2F occurances 03 $1A occurances (ZP variable) 8D $18 occurances (STA opcode) In a real implementation, I'd choose zp variables to be common opcodes like $8D, which would double the number of occurances of that byte, but let's just consider the above numbers in a 512-byte program. Those top three bytes total $5A bytes, almost 1/8 of the total bytes (the top seven bytes take a little less than 1/3 of the total, by contrast). The number of bits required is 9*($200-$5A) + 2*$2F + 3*$1A + 4*$18 = $FE2 bits = $1FD bytes. so, a whopping 3 byte savings -- just enough to store the three "tree" values. For the top seven bytes, a similar calculation suggests $01D8 bytes of compressed data, again for code not optimized for compression. For a more optimized code, with zp variables the same as common opcodes and such, the total bytes could conceivably be on the order of $1C0 bytes -- maybe 64 bytes of savings (but again, I never actually tried coding a more optimized version so I don't know for sure). Of course, we haven't talked about decompression yet. One important feature of this tree is that the "treeness" of it is unimportant -- it's really just a substitution code. Remember that the data is encoded as 0+8 bits literal byte 10 byte 1 110 byte 2 1110 byte 3 and so on. A decompression algorithm simply reads bits until a 0 is found, and then looks up the relevant value in a table. The exception is if the first bit read is 0, in which case the code needs to read the next eight bits and output the byte. There is no tree traversal, in the sense of looking up nodes and moving left/right, to speak of. Reading bits is trickier than reading bytes. After every eight bits read some sort of memory pointer has to be incremented to the next eight bits. Moreover, when reading codes like 110 or 1110 the number of 1's read has to be counted too, to be used as an index into the lookup table. And if there's a literal byte then the next eight bits need to be read, regardless of their value. When reading the bitstream, after every eight bits the pointer into that bitstream must be incremented. To count eight "global" bits at a time, I use a zp variable "count" and just rotate a bit through the different bit positions. Every time it turns zero, the data stream pointer is incremented. The advantage of this method is that it frees up a register (and winds up saving a byte overall). To count the number of "local" bits read, I use the .Y register. Initially it is set to zero, and increments as 1s are read. For a literal byte, I set .Y to -8, and put a little check in the bit reader for negative .Y; that way, it simply increments to .Y=0. When bit=0 is finally found, the code simply does an lda data,y to get the coded data. Since .Y counts the number of bits read, .Y will be at least 1 for any coded data, but .Y=0 for a literal byte as described above. Therefore, for a literal byte, the code can simply rotate bits into the location "data", and use the same lda data,y instruction to fetch the literal byte. With all that in mind, here's the code I finally came up with (on paper!): Tuff+1 [data lookup table] Source [compressed data bitstream] :lit ldy #-8 :getbit lsr count ;Increment pointer every eight bits bne :skip ror count inx bne :skip inc :src+2 :skip :src asl Source,x ;Get next bit bcs :next tya ;.y=0 means first bit is 0 beq :lit ;so read next 8 bits bpl :found ;If .y<0 then literal :next rol Tuff ;Save bit iny bne :getbit ;until .y=0 :found lda Tuff,y ;Fetch code/literal byte ldy #00 sta (zp),y ;Output data inc zp bne :getbit inc zp+1 bpl :getbit [Uncompressed code -- (zp) points here!] for a total of 45 bytes, plus 7 bytes for the "Tuff" byte table -- total of 52 bytes, compared with a possible 64 byte savings (maybe I should have tried to implement this after all!). Hopefully someone can improve on this further. (And "Tuff", btw, is a contraction of "TinyHuff"). Now, there may be a few raised eyebrows here which I hope I'll lower. This code makes several assumptions. It can either be entered in at ":src", or at ":getbit" depending on the value of "count", the global bit counter. I assume count is already initialized (e.g. default kernal/restart value), either to 1 (in which case :getbit is the entry point) or $80, in which case :src is the entry point, with the "Source" stream modified accordingly in each case. I further assume that .axy have their default values of 0 when the routine is called from BASIC. I also assume "zp" is initialized to the correct value already. One easy way to do this is to use $ae/$af, the end load address+1, but other options are certainly available. Finally, you may have noticed that the thing just keeps outputting data until zp=$8000 -- correct. Unless you really really care about garbage in memory above the program, there's no reason to waste bytes on an "end of data" check. Another variant --------------- I spent a little time looking at a variant of this scheme: using a fixed length bit sequence, for example, assigning four bits to each substitution byte, i.e. 0+ literal byte 1000 byte 1 1001 byte 2 1010 byte 3 ... 1111 byte 8 The numbers work out pretty well, compression-wise, but at the time I felt the decompression code was more complicated and that it wouldn't break even. Looking at it now, though, I'm starting to think otherwise -- that loading three bits at a time isn't any more complicated that fetching eight bits so code can be reused, and there isn't any issue about checking for a 1 bit, so the decompression code ought to be even simpler. So this may actually be the better scheme. Sigh... I don't know about you, but every time I revisit a problem I wind up feeling much stupider. Final thoughts -------------- So, that's it: assign shorter bit codes to the most common bytes, and use a highly optimized decompression routine. This method is very specialized, obviously, but might, just might, make it possible to save a few bytes on a tiny program that has been optimized for compression -- using zp locations the same value as common opcodes, reusing vars as often as possible, and so forth. The reason this works is that, in general, repeated long strings in a small program just don't happen, whereas repeated bytes are common and make up a substantial fraction of the total. Pelle (magervalp@cling.gu.se) has suggested the possibility using the first eight bytes of the compressed program for the 'Tuffman' table -- to structure the code to make these common bytes, and thereby save eight bytes by not having to store the 'tree'. Might save a few more bytes with some programs. Finally, while writing this article, I started to wonder about byte sequences with "holes", for example, <byte skip byte skip> for things like STA zp1 STA zp2. I wonder if there's some way of taking advantage of these repeated "mask" patterns. But I leave that thought for another person, for another day. ....... .... .. . C=H 20 =====================================Part 5=================================== Tinyrinth by Mark Seelye (aka Burning Horizon) mseelye@yahoo.com http://www,burninghorizon.com Introduction When the mini-game competition was first announced I was originally not interested because of time considerations -- I spend most of my time at work, or watching the kids. But once I saw that nearly everyone on EFNet #c-64 was doing one, I thought it would be fun if I could just keep it simple. I had no idea what game to do. I had a few other ideas but I settled on a maze game because I thought it'd be an interesting challenge doing a maze algorithm and have game code in under 512 bytes. As it turned out, I ended up getting the code down to like 475 bytes, but the version I turned in was 509 bytes. (I ended up shaving an additional 34 bytes just before the due date.) The other reason for the maze game is I have this weird thing I do where in each language I know I code this little maze generation algorithm that I made a long time ago. I had used the algorithm in ASP, VB, C, and a few others but for some reason I had never done it in 6502! Imagine that! It was going to be a bit of a challenge because I had never done it in so few instructions, and never in ASM. It would have to lose some weight and fluff - but I knew I could do it. So obviously there are MANY better ways to generate a maze, but in light of trying to make it small this routine ended up being such a strange mutation of my idea that I'm surprised it worked at all. Setup Before I do anything I must setup some things. This is also used when a player dies OR enters a new level. The only difference between a reset of the game and moving to the next level is the ldx #$00: sta $53. The $53 is also used to set the color of the maze so it rotates from a level one of white, to a level 16 of BLACK (which is evil because then you can't see the maze except for the small hint of the corners on a turn.) ; Initialization setup = * gameover = * ;Setup game variables ldx #$00 stx $53 ; Start at level 1 (to be inc'd) init = * ;Setup level inc $53 ; next level ldx $53 stx $54 ;Counter for drawing Keys (next level) stx $0286 ;Character Color to use on clear (e544) ;Set Render Cursor Start Pos / Player Color lda #$05 sta EBCM1 ;Set ebcm color PLAYER to GREEN ($d022) sta $45 ; Cursor/Player Position X (0-39) sta $46 ; Cursor/Player Position Y (0-24) ;Clear Screen jsr $E544 ;clear screen set to char color ($0286) lda #$5b sta $d011 ;turn on EBCM lda #$18 sta $d018 ;Activate Cset As you can see that I mention extended color background mode, I'll talk about that later. You also might notice I use a character set, but that I will talk about a little later as well, first I want to jump right into the maze generation. Maze Algorithm The easiest way to describe how the algorithm works is to compare it to a worm. The worm eats through an area until it gets blocked by one of its former meals. While eating the worm is counting how many meals he has, once he gets to a certain number he knows he can eat no more. With that said, I'm sure you're completely confused and probably think (know?) I'm crazy. So now for the technical explanation. Starting with a 2-dimensional grid of some size, initialized with 0's, set a start point for the formation of the maze within the grid somewhere. After that has been taken care of the rest follows simple logic: Have we reached every part of the grid? if so: done; if not: Can we grow the maze into an adjacent area from the current position? if so: Grow in one of those directions at random, count it, continue; if not: Find a place in the maze that can grow, continue I had to change the order of the logic around to get it to better fit into a smaller number of bytes. So I moved the "find a place to grow from" routine, and the "Have we reached every part of the grid" check after the check if we can grow in any direction from the current position. To check in all directions from the current position I used a subroutine. The subroutine has 5 entry points which translate to: cangrow up/right/down/ left, and the 5th entry point is actually the first entry point - it checks to see what is in .a and checks the direction that value represents. To check the direction I use a kernal routine to set some zp so I can easily check the value on the screen to the left, right, below, or above the current position. This is also where the boundaries are set: 40 columns wide and 25 characters high. popgridloop = * ldy $45 ;xpos ldx $46 ;ypos cangrowxy = * ;Can grow in any direction? jsr cgup ;check up beq _cgxy ;if 0 then we can grow inx ;offset up check jsr cgright ;check right beq _cgxy ;if 0 then we can grow dey ;offset right check jsr cgdown ;check down beq _cgxy ;if 0 then we can grow dex ;offset down check jsr cgleft ;check left _cgxy beq growloop ;if 0 then we can grow ....The subroutine!... There is a weird "injection" in the bottom of this routine to save a couple bytes.. it is explained in the comments to the code. ;Check if a cell can grow a direction ;1-up 2-right 3-down 4-left ; (y xpos, x ypos, a=dir) x/y switched for indirect lda($xx),y below ; return: a == 0 : true (can move) ; a <> 0 : false (cannot move) cangrow = * cmp #$01 beq cgup cmp #$02 beq cgright cmp #$03 beq cgdown ;cmp #$04 ;beq cgleft *** not needed falling through cgleft = * dey ;set xpos - 1 cpy #$ff ;check xpos beq cgno bne cgloadcell cgright = * iny ;set xpos + 1 cpy #$28 ;check xpos (<40) beq cgno bne cgloadcell cgup = * dex ;set ypos - 1 cpx #$ff ;check xpos beq cgno bne cgloadcell cgdown = * inx ;set ypos + 1 cpx #$19 ;check ypos (<25) beq cgno ;*** fallthrough, bne cgloadcell not needed cgloadcell = * lda #$1f loadcell = * ;x = ypos, y = xpos, a = and value sta $50 jsr $e9f0 ; * sets $d1 $d2 lda ($d1),y ;load byte (x pos in y reg!) cgno = * and $50 ;#$1f = use only low 5 bits! ;rts see below! ; This is mixed with the rts because the first byte would ; be wasted growfrom = * rts .byte 1 ; this is part growfrom part growto 48 is used for both ; again first byte would be wasted so we overlap with the previous growinto = * .byte 2, 4, 8, 1, 2 ;explanation of above ; 0 1 2 4 8 ; 0 4 8 1 2 ;rts 1 2 4 8 ; 4 8 1 2 *From Mapping: ;59888 $E9F0 ;Set Pointer to Screen Address of Start of Line ;This subroutine puts the address of the first byte of the ;screen line designated by the .X register into locations ;209-210 ($D1-$D2). Well, if the code at "cangrowxy" discovers that it cannot grow in any direction from the current position, it has to find a place to grow from. To do this it falls into the "findgrow" routine; the findgrow routine is interesting because it is a "stateful" routine, meaning that upon reentry it resumes what it was doing before. The reason for this is I didn't want it restarting at the top of the maze each time it entered this find routine - I wanted it to continue to search from where it left off. This routine works by "walking" the current x and y positions through the grid. To walk it through it keeps track of where it left off and it just keeps setting the x and y pointers to the next place and "returns" to the start of the generation portion of the code. The other advantage to doing it this way is I can reset this routine to place a "key" at a dead end in the maze. This reset is done elsewhere in the maze by setting a zp value to 0. When the reset is done the findgrow routine runs a small piece of code to reset itself, but before it does this it places a key if it has not exceeded the max number of keys. Here is the find grow routine, each line of code is documented to hint at what it is doing: ; *** fall into findgrow findgrow = * lda $4b ; Check byte 0 != resume findgrow bne _fgresume sta $49 ;Reset Findgrow Xpos sta $4a ;Reset Findgrow Ypos inc $4b ;Set findgrow flag to resume (<>0) ;Place keys in corners (injected here for ease of placement, d1/d2 is ;pointed at a dead end) iny ; offset left check beq _fgresume ;Do not try when column is 0, it freaks out lda $54 beq _fgresume ;if 0 then keys are done dec $54 ;dec # of keys left to place inc $51 ;actual num keys left lda ($d1),y ;load byte ora #$c0 ;EBCM value for key! sta ($d1),y ;store new value ;(end of injection) _fgresume = * _fgx ldx $4a ;Findgrow ypos _fgy ldy $49 ;Findgrow xpos inc $49 ;Next xpos (next round) cpy #$28 ; < 40 beq _fgcr ; next line if >= 40 jsr cgloadcell ; load cell byte beq _fgy ; if 0 then get next xpos/byte sty $45 ;Set Current xpos stx $46 ;Set Current ypos jmp cangrowxy ;Check if this can grow _fgcr lda #$00 ;Reset Findgrow xpos sta $49 ; 0->xpos inc $4a ;Next Findgrow ypos lda $4a cmp #$19 ;check ypos (<25) bne _fgx ;If we're at x40y25 we are ready to play! beq gameinit ;Start game logic That code also checks to see if we have completed generating the maze, at which point it enters the game logic. But before we jump into that I have to explain what happens when the "cangrowxy" routine discovers that it CAN GROW, instead of falling into the "findgrow" routine. In the "cangrowxy" routine described a bit above there was the final line of: _cgxy beq growloop ;if 0 then we can grow This "growloop" routine is the place where the actual "growing" or "eating" occurs. This routine works by choosing a direction at random, and attempting to grow in that direction. It reuses the same "cgup" etc. routines that the "cangrowxy" uses because although we know we can grow in a direction, we don't know which direction. In a larger version of this algorithm I usually link all of this stuff together, but this is how it worked out in tinyrinth. growloop = * randdir = * ;jsr getrand; not a func, not reused yet getrand = * lda #$80 sta $028a ; Key Repeat; (injected here for #$80) just using #$80 for ;smaller code sta $d412 ;sta $d404 d412 is V3, d404 is V1!! sta $d40f ;set v3 random # gen bits lda $d41b ; read random number from V3 and #$03 ; Force Random number to 0-3 clc adc #$01 ; Add 1 to get 1-4 sta $4c ; store rand direction ldy $45 ; Current Xpos ldx $46 ; Current Ypos jsr cangrow ; Check if we can grow in that direction bne randdir ; if <> 0 then Try again sta $4b ; reset findgrow flag (injected here for .a==0) grow = * ldx $4c ;Get saved rand direction lda growinto,x ; 1-4 (4, 8, 1, 2) Get bit set for new cell sta ($d1),y ; write new location lda growfrom,x ; 1-4 (1, 2, 4, 8) Get bit to set for old sta $4d ; Save growfrom bit ldy $45 ; Reload Current xpos ldx $46 ; Reload Current ypos jsr cgloadcell ; Load base cell again ora $4d ; Combine with growfrom bit sta ($d1),y ;Modify old cell to connect to new loc ;Change current position lda $4c ; Get saved rand direction jsr cangrow ; Get new x y again - (this will only perform next x/y ;adj, returns <>0) sty $45 ; xpos set to new location stx $46 ; ypos jmp popgridloop ; Return to populate grid loop As you can see above I use the random number generator from V3 to get the random direction. A HUGE bonus here is I can use the value returned to directly call that main entry point in "cangrow" so it will figure out which direction to check by itself. If the direction it checks is bad it just loops and tries again. In a larger version of the program I'd make this much more efficient, but efficiency costs bytes. Many coders would be afraid of using a loop like this but since I pre-checked that I can grow before entering this loop, unless my random number generator never returns that direction, I should be fine! Once we have a good direction I use the already set $d1 zp to read and update the screen data. Nice bonus of using the routine that sets it! The code that updates the data must update the cell you are growing to, but ALSO it must update the cell you are growing from, which is why I have to reload the original data up there. When it is finished doing the growing it moves the x/y positions ($45, $46) to the place it grew to; and resumes the maze generation from there. As I said before, the findgrow routine will jump into the game logic once it knows it is finished, but before we talk about that I should describe another problem that I needed to solve. In a 2 dimensional maze there are 16 possible pieces that can be formed. Starting with completely closed ending with completely open. I represent these pieces with numbers 0-15; each bit represents a side of a cell that is open/closed. So when I finish with the maze generation I have a grid of numbers 0-15. (Actually 1-14; in this game I never end up with 0's or 15's as all pieces are used.) In Tinyrinth the "grid" I used was the screen memory (40x25), so I ended up with a screen full of characters A-N. Navigating a maze of characters A-N would be rather difficult so I had to decide whether to use the built in character set and transform what was on the screen or somehow use a character set. Well, another hitch was I wanted this to be a game and losing the simplicity of 0-15 for detecting which way a player could move would be bad - so I opted for a character set of 16 characters. Hmmm 8 bytes per character time 16 characters.. 128 bytes! Yikes! Character Set Generation So I was going to need a 128 byte character set, but I didn't want to have to lose 128 bytes. So what did I do? I coded about 70 bytes of code to generate the character set. This too pained me because I was sure I could make it smaller somehow, but once I got it working and a decent percentage smaller than the size of what it produced I stopped worrying about it. Here is how it works: we know we want to represent the 16 pieces with 0-15 so the bits must give some hint to the shape of the piece. What I did was create a loop to check the current counter value and either set or skip the top, sides, bottom of the piece. Here is how it works, I have commented each line of code to describe what it is doing. ; Generate Cset! lda #$20 ; write hi sta $48 ; use zp lda #$00 ; write lo ;Initialize Screen, variables (injected here to save bytes - using ;lda #$00) sta $51 ; Clear actual num keys placed counter (see findgrow) sta $d020 sta EBCM0; Set BG Color ($d021) ;(end of injection) tax ; counter = 0 _again sta $47 ; use zp ldy #$00 ; index txa ; counter to a and #$01 ; check for top beq _ytop ; yes top eor #%01111111 ; 00000001 -> 011111110 -> 10000001 _ytop eor #%11111111 ; 00000000 -> 111111111 _6sides sta ($47),y ; store top/sides to cset iny ; next mem location txa ; counter to a and #$02 ; check for right eor #%00000010 ; flip lsr ; 00000010 -> 00000001 || 0->0 sta $49 ; store for right side txa ; counter to a and #$08 ; check for left side bne _noleft ; no left eor #%10001000 ; 00000000 -> 10001000 -> 10000000 _noleft eor #%00001000 ; 00001000 -> 00000000 ora $49 ; merge with right cpy #$07 ; 7->15->23->... bne _6sides ; total of 6 side pieces txa ; counter to a and #$04 ; check for bottom beq _ybot ; no bottom eor #%01111010 ; 00000100 -> 01111110 -> 10000001 _ybot eor #%11111111 ; 00000000 -> 11111111 sta ($47),y ; store bottom to cset inx ; next counter clc ; clear carry lda $47 ; inc zp adc #$08 ; by 8 bne _again ; do it again inc $48 ldy $48 cpy #$28 ;repeat through cset 2000-2800 bne _again sty EBCM2 ;Set Death color ($d023) (using result of cset gen for ;color value!) I still think I could have made that smaller; either way though it was fun making a little routine to generate the cest. With that all said, we now know how the maze is generated. But now I needed a way to play it, as suggesting players use dry erase markers on their screens was not a great idea. Game Loop Ok, once "findgrow" reaches the end of its maximum size it branches to "gameinit". Game init sets up some quick things and gets going on the game play. The game loop loops until the player either gets all the keys or dies. When the player gets all the keys the level number ($53) is increased which is used to increase the maximum number of keys and the color of the maze! Here is the game loop, I have commented much of the code and separated it into sections: *** Flashes the keys, sets speed of "minitaur" based on the level ; Game Initialization and Game Loop gameinit = * gameloop=* inc EBCM3 ; Flash Keys ($d024) inc $58 ; Increase Speed counter #1 (0-255) bne moveplayer ; Skip move inc $57 ; Increase Speed counter #2 ($57|#$f0 - 255) bne moveplayer ; Skip Move ;set death speed lda $53 ;Use level for Speed value cmp #%11111000 ;If more than this use default speed bmi _dsp lda #%11111000 ;Default speed _dsp ora #%11110000 ;Set high nibble so counter counts up to 255 sta $57 ; Set Speed counter #2 *** Moves the minitaur to the next position if it is time. (Checks for player *** hits) ;move death movedeath = * ldy $55 ;Baddy Xpos ldx $56 ;Baddy Ypos jsr cgloadcell ; load the cell/point the zps (ANDs by #$1f) sta ($d1),y ;store cleared value _newy iny ;increase xpos cpy #$28 ;less than 40? bmi _go ;don't reset ldx $46 ;ypos of player stx $56 ;ypos of death ldy #$00 ;clear xpos counter _go sty $55 ;Set baddy xpos lda #$ff ;Get all bits! (see loadcell) jsr loadcell ;load the cell/point the zps sta $59 ;Save cell value (withh all possible bits) and #%11000000 ;and by EBCM bits cmp #%11000000 ;Check for KEY - (so it can skip over) beq _newy ;Jump ahead 1 more to skip key position cmp #%01000000 ;Check for player hit bne _nodie ;Player is not dead jmp gameover ;Game Over! _nodie lda $59 ;Reload stored value ora #$80 ;EBCM for Death sta ($d1),y ;store value ; *** fall through to Move Player *** Checks the keyboard for input, moves player if possible ;Move Player moveplayer=* _ffe4 jsr $ffe4 ;Get keypress beq gameloop ;no key - goto gameloop and #%00000011 ;.a == 0-7 at this point tax lda keytodir,x ;Loads from keytodir ;Move entity in game ; .a=direction 1-up 2-right 3-down 4-left glmove tax stx $4e ; store direction lda growinto,x ; get check bit sta $4f ; store check bit ldy $45 ; current xpos ldx $46 ; current ypos jsr cgloadcell ; load the cell (and with #$1f) sta ($d1),y ; store the data (clear the EBCM) lda #$00 ; Bottom "fall out" fix sta $50 ; clear and of cangrow Bottom "fall out" fix lda $4e ; load direction jsr cangrow ; call cangrow to move xpos/ypos and $4f ; check bit bne glmyes ; if we have a bit then we can move! ldy $45 ; reload xpos - do not move ldx $46 ; reload ypos - do not move glmyes lda #$ff ; bits to obtain from loadcell jsr loadcell ; load the cell/point the zps pha ; temp store value for later checks and #$1f ; clear other EBCM bits ora #$40 ; EBCM ORA Player/Baddy sta ($d1),y ; store new data sty $45 ; store xpos of new position stx $46 ; store ypos of new position *** Checks for key hits, minitaur hits, Check for end-level: (jumps to next level if it is the end of the level, loops to the beginning of the game loop if not.) ;Hit checks pla ; load previous value and #$c0 ; check for hits "11xxxxxx" cmp #$c0 ; check for key hit bne _back ;_notkey ; to next check dec $51 ; dec number of keys left in level bne _back ; if 0 then we should go to the next level jmp init ; gen maze again ;_notkey cmp #$80 ; check for death hit! ; bne _back ; jmp gameover ; game over _back jmp gameloop ;more checks here? keytodir=* .byte 2,1,4,3 To make this all work, I reused the "cangrow" routine again! Because basically it is the exact same logic. One thing that I found unfortunate is I never coded a way for the minitaurs to have any intelligence, there was an attempt that worked - but it was FAR too many bytes (over by like 20-30). So I just axed it. I also at one time made the movement routines all one subroutine that took parameters that would move any "entity". This also took too many bytes to be useful for this version of the game. Perhaps some day I'll write a kick butt 1k or 2k version with all those features coded in. Various Space Saving Techniques Used If you look throughout the code, you'll notice I comment a lot on "injections". These are little bits of code that are conveniently put in places to take advantage of the state of a register, or a memory location. Here is an example: in the "getrand" routine I injected a line to set the key repeat, using the value that I wanted to also put into $d412 for the random number generation. lda #$80 sta $028a; Ket Repeat; (injected here for #$80) just using #$80 for smaller code sta $d412 ;sta $d404 d412 is V3, d404 is V1!! Another example, here I mixed some static data together to save some bytes and just labeled it so some would be reused. To save additional bytes I also positioned the label in front of the "rts". (This was because the code accessing the data never used an index of 0.) This is mixed with the rts because the first byte would be wasted growfrom = * rts .byte 1 ; this is part growfrom part growto 48 is used for both ; again first byte would be wasted so we over lap with the previous growinto = * .byte 2, 4, 8, 1, 2 ;explanation of above ; 0 1 2 4 8 ; 0 4 8 1 2 ;rts 1 2 4 8 ; 4 8 1 2 I also reused the "cangrow" routine as much as possible, and on top of that I made it more usable by making multiple entry points so it could be used in different way. Finally the best thing I did was use kernal routines, like $E544 to clear the screen to the set char color at $0286. This allowed me to change the color of the maze each level just by changing the value at $0286. I also used $e9f0, Mapping the c64 says, "Set Pointer to Screen Address of Start of Line. This subroutine puts the address of the first byte of the screen line designated by the .X register into locations 209-210 ($D1-$D2)." This was handy because I could use this to read from and write to the screen. Extended Color Background Mode I could not use sprites. This made me sad, but there was just no room for it. So I just decided to allow the cset to repeat itself through the whole cset area ($2000-$2800) and use ECBM! This allowed me to just set a bit and make a maze piece a different color, what more when I read this value I could easily tell what the piece represented! That made collision detection very easy, and also allowed me to have cool flashing keys. Conclusion I had a LOT of fun coding this and look forward to another competition. I was surprised and amazed by the entries! This even inspired me to make a better version of Tinyrinth, of which I have not completed. I did add to it, I made a version in which the minitaurs move through the maze. I made another version that would also increase the number of minitaurs in the maze. I made yet another version that would change the size of the maze, and thought about changing the shape too. All of these ideas were easy to implement once I had the base game working. Oh by the way, I know how to spell Minotaur, the Minitaur thing is just a bad joke. :) Final Code Stats Total source compiled: 445 lines in 1 file(s) Symbol table: 29 global and 1 local constants, 0 global variables, 2 global and 15 local labels, 0 source labels. Data size: 10 bytes Code size: 475 bytes in 231 instructions Memory block affected: $1000 - $11E4 (total size: 485 bytes) Source Note: This source is not the source I released for the event. It is a bit smaller, I cannot locate my original source for some reason. Also, some of it may differ a tiny bit from the code documented above. I had written the article using the wrong copy of the source, I have attempted to go back and update it though. (Note to self: keep better records!) :) Another note: This source compiles with c64asm by Balint Toth. :) -- tinyrinth.asm -- ; Tinyrinth ; entry for a 512b game contest ; Burning Horizon/FTA ; Mark Seelye ; mseelye@yahoo.com ; =================================================================== * = $1000 ;name loc desc color ecbm bits EBCM0 = $d021 ; untouched black $00 00 EBCM1 = $d022 ; cursor red $40 01 EBCM2 = $d023 ; touched green $80 10 EBCM3 = $d024 ; keys yellow $c0 11 ;ZPs used: (Consolidation Possible if needed) ;43/44 - Not Used ;45/46 - Current X/Y Position, Maze Generation & Game ;47/48 - CSet Location, CSet Generation ;49 - Temp Storage, CSet Generation ;49/4a - Xpos/Ypos Findgrow, Maze Generation ;4b - Flag, Findgrow, Maze Generation ;4c - Temp Storage, randdir, Maze Generation ;4d - Temp Storage, grow, Maze Generation ;4e/4f - Temp Storage, glmove, Game ;50 - Temp Storage, loadcell, Maze Generation & Game ;51 - NumKeys Left in level (affected by: destroyed & found keys) ;52 - not used ;53 - Current Level ;54 - # of Keys to try and place, gameinit, Game ;55/56 - X/Y Pos of Death ;57/58 - speed counter for death ;Collect all keys ; gen crummb path for visited areas? ; once all keys collected next maze is gen'd ; Initialization setup = * gameover = * ;Setup game variables ldx #$00 stx $53 ; Start at level 1 (to be inc'd) init = * ;Setup level inc $53 ; next level ldx $53 stx $54 ;Counter for drawing Keys (next level) stx $0286 ;Character Color to use on clear (e544) ;Set Render Cursor Start Pos / Player Color lda #$05 sta EBCM1 ;Set ebcm color PLAYER to GREEN ($d022) sta $45 ; Cursor/Player Position X (0-39) sta $46 ; Cursor/Player Position Y (0-24) ;Clear Screen jsr $E544 ;clear screen set to char color ($0286) lda #$5b sta $d011 ;turn on EBCM lda #$18 sta $d018 ;Activate Cset ; Generate Cset! lda #$20 ; write hi sta $48 ; use zp lda #$00 ; write lo ;Initialize Screen, variables (injected here to save bytes - using lda #$00) sta $51 ; Clear actual num keys placed counter (see findgrow) sta $d020 sta EBCM0; Set BG Color ($d021) ;(end of injection) tax ; counter = 0 _again sta $47 ; use zp ldy #$00 ; index txa ; counter to a and #$01 ; check for top beq _ytop ; yes top eor #%01111111 ; 00000001 -> 011111110 -> 10000001 _ytop eor #%11111111 ; 00000000 -> 111111111 _6sides sta ($47),y ; store top/sides to cset iny ; next mem location txa ; counter to a and #$02 ; check for right eor #%00000010 ; flip lsr ; 00000010 -> 00000001 || 0->0 sta $49 ; store for right side txa ; counter to a and #$08 ; check for left side bne _noleft ; no left eor #%10001000 ; 00000000 -> 10001000 -> 10000000 _noleft eor #%00001000 ; 00001000 -> 00000000 ora $49 ; merge with right cpy #$07 ; 7->15->23->... bne _6sides ; total of 6 side pieces txa ; counter to a and #$04 ; check for bottom beq _ybot ; no bottom eor #%01111010 ; 00000100 -> 01111110 -> 10000001 _ybot eor #%11111111 ; 00000000 -> 11111111 sta ($47),y ; store bottom to cset inx ; next counter clc ; clear carry lda $47 ; inc zp adc #$08 ; by 8 bne _again ; do it again inc $48 ldy $48 cpy #$28 ;repeat through cset 2000-2800 bne _again sty EBCM2 ;Set Death color ($d023) (using result of cset gen for color value!) popgridloop = * ;can grow from current? ldy $45 ;xpos ldx $46 ;ypos ;Can grow in any direction? cangrowxy = * jsr cgup ;check up beq _cgxy ;if 0 then we can grow inx ;offset up check jsr cgright ;check right beq _cgxy ;if 0 then we can grow dey ;offset right check jsr cgdown ;check down beq _cgxy ;if 0 then we can grow dex ;offset down check jsr cgleft ;check left _cgxy beq growloop ;if 0 then we can grow ; *** fall into findgrow findgrow = * lda $4b ; Check byte 0 != resume findgrow bne _fgresume sta $49 ;Reset Findgrow Xpos sta $4a ;Reset Findgrow Ypos inc $4b ;Set findgrow flag to resume (<>0) ;Place keys in corners (injected here for ease of placement, d1/d2 is pointed at a dead end) iny ; offset left check beq _fgresume ;Do not try when column is 0, it freaks out lda $54 beq _fgresume ;if 0 then keys are done dec $54 ;dec # of keys left to place inc $51 ;actual num keys left lda ($d1),y ;load byte ora #$c0 ;EBCM value for key! sta ($d1),y ;store new value ;(end of injection) _fgresume = * _fgx ldx $4a ;Findgrow ypos _fgy ldy $49 ;Findgrow xpos inc $49 ;Next xpos (next round) cpy #$28 ; < 40 beq _fgcr ; next line if >= 40 jsr cgloadcell ; load cell byte beq _fgy ; if 0 then get next xpos/byte sty $45 ;Set Current xpos stx $46 ;Set Current ypos jmp cangrowxy ;Check if this can grow _fgcr lda #$00 ;Reset Findgrow xpos sta $49 ; 0->xpos inc $4a ;Next Findgrow ypos lda $4a cmp #$19 ;check ypos (<25) bne _fgx ;If we're at x40y25 we are ready to play! beq gameinit ;Start game logic growloop = * randdir = * ;jsr getrand; not a func, not reused yet getrand = * lda #$80 sta $028a; Ket Repeat; (injected here for #$80) just using #$80 for smaller code sta $d412 ;sta $d404 d412 is V3, d404 is V1!! sta $d40f ;set v3 random # gen bits lda $d41b ; read random number from V3 and #$03 ; Force Random number to 0-3 clc adc #$01 ; Add 1 to get 1-4 sta $4c ; store rand direction ldy $45 ; Current Xpos ldx $46 ; Current Ypos jsr cangrow ; Check if we can grow in that direction bne randdir ; if <> 0 then Try again sta $4b ; reset findgrow flag (injected here for .a==0) grow = * ldx $4c ;Get saved rand direction lda growinto,x ; 1-4 (4, 8, 1, 2) Get bit set for new cell sta ($d1),y ; write new location lda growfrom,x ; 1-4 (1, 2, 4, 8) Get bit to set for old sta $4d ; Save growfrom bit ldy $45 ; Reload Current xpos ldx $46 ; Reload Current ypos jsr cgloadcell ; Load base cell again ora $4d ; Combine with growfrom bit sta ($d1),y ;Modify old cell to connect to new loc ;Change current position lda $4c ; Get saved rand direction jsr cangrow ; Get new x y again - (this will only perform next x/y adj, returns <>0) sty $45 ; xpos set to new location stx $46 ; ypos jmp popgridloop ; Return to populate grid loop ; Game Initialization and Game Loop gameinit = * gameloop=* inc EBCM3 ; Flash Keys ($d024) inc $58 ; Increase Speed counter #1 (0-255) bne moveplayer ; Skip move inc $57 ; Increase Speed counter #2 ($57|#$f0 - 255) bne moveplayer ; Skip Move ;set death speed lda $53 ;Use level for Speed value cmp #%11111000 ;If more than this use default speed bmi _dsp lda #%11111000 ;Default speed _dsp ora #%11110000 ;Set high nibble so counter counts up to 255 sta $57 ; Set Speed counter #2 ;move death movedeath = * ldy $55 ;Baddy Xpos ldx $56 ;Baddy Ypos jsr cgloadcell ; load the cell/point the zps (ANDs by #$1f) sta ($d1),y ;store cleared value _newy iny ;increase xpos cpy #$28 ;less than 40? bmi _go ;don't reset ldx $46 ;ypos of player stx $56 ;ypos of death ldy #$00 ;clear xpos counter _go sty $55 ;Set baddy xpos lda #$ff ;Get all bits! (see loadcell) jsr loadcell ;load the cell/point the zps sta $59 ;Save cell value (withh all possible bits) and #%11000000 ;and by EBCM bits cmp #%11000000 ;Check for KEY - (so it can skip over) beq _newy ;Jump ahead 1 more to skip key position cmp #%01000000 ;Check for player hit bne _nodie ;Player is not dead jmp gameover ;Game Over! _nodie lda $59 ;Reload stored value ora #$80 ;EBCM for Death sta ($d1),y ;store value ; *** fall through to Move Player ;Move Player moveplayer=* _ffe4 jsr $ffe4 ;Get keypress beq gameloop ;no key - goto gameloop and #%00000011 ;.a == 0-7 at this point tax lda keytodir,x ;Loads from keytodir ;Move entity in game ; .a=direction 1-up 2-right 3-down 4-left glmove tax stx $4e ; store direction lda growinto,x ; get check bit sta $4f ; store check bit ldy $45 ; current xpos ldx $46 ; current ypos jsr cgloadcell ; load the cell (and with #$1f) sta ($d1),y ; store the data (clear the EBCM) lda #$00 ; Bottom "fall out" fix sta $50 ; clear and of cangrow Bottom "fall out" fix lda $4e ; load direction jsr cangrow ; call cangrow to move xpos/ypos and $4f ; check bit bne glmyes ; if we have a bit then we can move! ldy $45 ; reload xpos - do not move ldx $46 ; reload ypos - do not move glmyes lda #$ff ; bits to obtain from loadcell jsr loadcell ; load the cell/point the zps pha ; temp store value for later checks and #$1f ; clear other EBCM bits ora #$40 ; EBCM ORA Player/Baddy sta ($d1),y ; store new data sty $45 ; store xpos of new position stx $46 ; store ypos of new position ;Hit checks pla ; load previous value and #$c0 ; check for hits "11xxxxxx" cmp #$c0 ; check for key hit bne _back ;_notkey ; to next check dec $51 ; dec number of keys left in level bne _back ; if 0 then we should go to the next level jmp init ; gen maze again ;_notkey cmp #$80 ; check for death hit! ; bne _back ; jmp gameover ; game over _back jmp gameloop ;more checks here? keytodir=* .byte 2,1,4,3 ;Check if a cell can grow a direction ;1-up 2-right 3-down 4-left ; (y xpos, x ypos, a=dir) x/y switched for indirect lda($xx),y below ; return: a == 0 : true (can move) ; a <> 0 : false (can not move) cangrow = * cmp #$01 beq cgup cmp #$02 beq cgright cmp #$03 beq cgdown ;cmp #$04 ;beq cgleft *** not needed falling through cgleft = * dey ;set xpos - 1 cpy #$ff ;check xpos beq cgno bne cgloadcell cgright = * iny ;set xpos + 1 cpy #$28 ;check xpos (<40) beq cgno bne cgloadcell cgup = * dex ;set ypos - 1 cpx #$ff ;check xpos beq cgno bne cgloadcell cgdown = * inx ;set ypos + 1 cpx #$19 ;check ypos (<25) beq cgno ;*** fallthrough, bne cgloadcell not needed cgloadcell = * lda #$1f loadcell = * ;x = ypos, y = xpos, a = and value sta $50 jsr $e9f0 ; sets $d1 $d2 ;59888 $E9F0 ;Set Pointer to Screen Address of Start of Line ;This subroutine puts the address of the first byte of the screen line ;designated by the .X register into locations 209-210 ($D1-$D2). lda ($d1),y ;load byte (x pos in y reg!) cgno = * and $50 ;#$1f = use only low 5 bits! ;rts see below! ; This is mixed with the rts because the first byte would ; be wasted growfrom = * rts .byte 1 ; this is part growfrom part growto 48 is used for both ; again first byte would be wasted so we over lap with the previous growinto = * .byte 2, 4, 8, 1, 2 ;explanation of above ; 0 1 2 4 8 ; 0 4 8 1 2 ;rts 1 2 4 8 ; 4 8 1 2 ;Notes ; 1 ;8 2 ; 4 ; ; ;*** * * *** * * ;*0* *1* *2 *3 @ A B C ;*** *** *** *** ; ;*** * * *** * * ;*4* *5* *6 *7 D E F G ;* * * * * * * * ; ;*** * * *** * * ; 8* 9* a b H I J K ;*** *** *** *** ; ;*** * * *** * * ; c* d* e f L M N O ;* * * * * * * * -- end: tinyrinth.asm -- ....... .... .. . C=H 20 =====================================Part 6=================================== Tetrattack! by Stephen L. Judd <sjudd@ffd2.com> Introduction ------------ The main point of Tetrattack!, of course, was to try and write a 3D engine in 512 bytes. I had a few other routine ideas but couldn't think of anything remotely fun to do with them, but I finally thought of a neat 3D game idea and decided to go for it. Alas, as code kept getting bigger that idea had to be discarded, and the eventual result was tetrattack, the simplest/smallest 3D game that wasn't (totally) stupid. But it is a 3D engine in 512 bytes! At first blush a 512-byte 3D engine might seem ridiculous but think about it: a basic 3d program doesn't need to store any graphics definitions or things like that -- it draws its own as it goes. In fact, all that is needed is a line routine, a rotation/projection routine, and some routines to keep track of angles and positions and such. What could possibly be hard about that, right? Well, it seemed reasonable at the time, anyways. At exactly 512 bytes, the code really had to sweat out the bytes, and every single byte saved was important; meanwhile, the routines still had to be reasonably fast. So this article will discuss the line routine, the rotation/projection routine, and the object and game manipulation routines, and the various optimizations used. I must say that writing this program really was fun; I'm sure that everyone else had the same problems I had, trying to shift from a "cycle-optimization" mindset to a "byte-optimization" mindset. Finding those extra few bytes here and there was a mighty challenge, sometimes taking hours or even days just to save one or two bytes. That part was frustrating, of course, as is the fact that the 'game' aspect of the program is thoroughly lame. But it was a neat challenge, and there was never an issue of adding too many features to the program and never finishing it! Quick Summary ------------- A full-on 3D program uses matrix multiplications to compute rotations, but 3D calculations get a whole lot easier in a Battlezone or driving-type situation, when you only turn left or right. There are no longer rotation matrices to keep track of -- just a single angle. This means that rotations are done with a simple INC/DEC, and there are no matrix multiplies to deal with. Rotations are done with some simple table lookups. The line drawing routine is pretty standard. Self-modifying code is used to manipulate a single routine to draw different lines, by swapping INX/INY instructions (which turns out to be less efficient, memory-wise -- sigh, oh well). Lines are plotted to a double-buffered 128x128 charmap, and once again setting up the screen took extra bytes. The "game code" is the simplest possible -- tetrahedrons are moved by just incrementing their z-coordinate, and rotated by incrementing their angle. Their locations are determined by whatever zero page is initialized to -- the program never sets explicit locations. Instead, I just chose a portion of zero page that had a reasonable range of default values (default zero-page values are used extensively in the code) In addition to default zero-page values the code uses several kernal routines (including a few unusual ones, for example the shift-C= routine for swapping charset buffers), self-modifying code, lots of zero-page instructions, and a whole bunch of tightly optimized code. The code was written over a few weeks -- a good week of planning and writing out possible routines, and a good week or two of coding. A couple of times I froze the program (using AR) and the freeze almost always happened in the same place: the buffer clearing routines. So the rotation and line drawing routines turned out to be fast enough, even with all the byte savings. The code was developed using the Sirius assembler on a 128D+SCPU -- and btw, the Jammon debugging mode has turned out to be awfully cool, with being able to visually single-step through code while simultaneously viewing memory and registers. Action Replay was downright clunky afterwards (but could freeze!). Yep, just a plug, with a bit of amazement that it actually all worked. I also tested it with VICE, to make sure it worked OK. VICE initializes zero page to different values than my 128, unfortunately, so some tweaking had to be done. And that's about it. Now on to more detail. ---------- Setting up ---------- The setup routines initialize VIC, initialize tables used by the line and rotation routines, and set up the screen. I note that when I started planning this program I computed the sizes of line and rotation routines without considering the code needed to set up tables and such for those routines. Oops! The default initial values for .X, .Y, and .A are 0 after a SYS, so the code made a little use of this. Line routine setup ------------------ The line routine uses tables to look up pixel addresses and bit locations for each x,y coordinate (the line routine stores the x and y coordinates directly in the .X and .Y registers, so looking up pixel addresses amounts to LDA Bitp,X kinds of instructions). The "bitmap" is a 128x128 charmap, so the calculations are pretty easy. The bit patterns which correspond to different x-coordinates (10000000 01000000 etc.) are computed using cmp #$80 rol to cyclically rotate a single bit. Rotation routine setup ---------------------- Another little piece of code is piggybacked into this loop, which extends a sine table from 0..pi. In this program, "angles" can go from 0..63, corresponding to 0..2*pi; the most memory-efficient way to store the sine table is to store the values for 0..pi/2, and then extend the table to pi/2..pi. That is, angle=16 (angles go from 0..63, remember) corresponds to pi/2, so the job of extending the table amounts to copying table values 15..0 to values 17..32 (value 16 is not copied because it is pi/2 -- the values are 'mirrored' through pi/2. To put it another way: where would it be copied to?). This amounts to starting one index register at 15 and decrementing it, while starting the other register at 17 and incrementing: ldy #15 ldx #17 lda table,y sta table,x inx dey The problem here is piggybacking into a loop where .Y is initialized to ldy #$7F instead of ldy #15. The solution is to initialize .X carefully [ldy #$7f] ldx #$90 and use the following: lda sin0,y sta sin0+17,x inx [dey] The idea is that when .Y=15, .X will equal 0 and start incrementing. This copies a lot of junk into the table that is never used but doesn't overwrite the existing 0..16 table values, and saves several bytes. The rotation tables are tables of r*sin(theta), one table for every allowed value of theta=0..64 and r=-128..127. The idea is that every 256-byte page contains r*sin(theta) for one value of theta, so that a table lookup amounts to lda theta ora #>high byte of sin tables sta zp+1 ldy r lda (zp),y The table values are computed using a standard shift-and-add multiply routine, with a little extra code to handle negative values of r. What about negative values of sin(theta), though? Recall that theta=0..63 corresponds to 0..2*pi, but the init code only extends the sine table from 0..pi (i.e. theta=0..32). The table values for pi..2*pi are computed simply by taking the negative of the values for 0..pi: sta (p4000),y eor #$ff clc adc #1 STA (p6000),y (The clc adc #1 code was painful, byte-wise, but necessary). The pointers p4000 and p6000 are initialized to $4000 and $6000 by default -- or at least are supposed to be. Unfortunately, VICE and my 128D had different ideas about this, so a little extra code was necessary to initialize them. A big reason for putting a table at $6000 is that it ends at $8000, to provide an easy exit condition for the loop: inc p6000+1 bpl :mult8 ;to $8000 Screen setup ------------ A couple of things need to be done here: clear the screen, set the color RAM to the background color, and put a 16x16 block of characters in the middle of the screen (and do so in as few bytes as possible!). Clearing the screen is a piece of cake: sta $d021 sta $0286 ;clear color jsr $e544 ;clr scr The $0286 STA is to clear the color RAM to black, and work with different kernals. (With both color RAM and background the same, pixels won't appear where they aren't wanted). Storing a block of chars isn't quite so straightforward; rather, the straightforward methods use up a fair number of bytes, especially since both screen and color RAM have to be set up. Here's the method I finally came up with: :l2a jsr $e8ea ;scroll up ;.A = ($AC) ;.X=00 clc ;necessary? :l2 ;set one line sta $0720+12,x inc $db20+12,x inx adc #16 bcc :l2 ; adc #$00 inc $ac cmp #15 bne :l2a Kernal routine $e8ea is the routine to scroll the entire screen up one line, and disassembly shows that when it exits .A is equal to the contents of $AC and .X is 0. So the routine stores one line of chars to the middle of the screen, increments the corresponding color RAM (to white), and moves the screen up (chars and color RAM). By incrementing $AC before moving the screen up ($AC starts at zero normally), .A is re-initialized to its previous value+1, so this prints the next line of chars to the screen (that is, the previous line of chars + 1). By doing this 16 times a 16x16 block of chars is produced, with color RAM set to white inside the block, and set to black everywhere else. And that brings us to the main program loop. --------- Main Loop --------- The main loop is pretty straightforward: clear buffer, get input, update positions and angles, render the buffer, and swap buffers. The only thing special in this process is swapping buffers via the kernal routine at $eb59 -- this is the routine that is called when C= and shift are held down. There is also a lame dot that pulses to the screen when you hold the fire button down (how cool some laser lines would have been). Alas... But that's pretty much it. So now let's talk a little about some of the optimizations that can be made for a 3D program, followed by a discussion of the line routine and the rotation routine. -------- 3D Stuff -------- For detailed information on how to "do" 3D worlds I suggest reading issue #16 of C=Hacking, but the basics of rendering a 3D world are: 1) figuring out where an object is, relative to you, 2) if the object is visible, computing what it looks like from your perspective, and 3) rendering the object. To define and operate on an "object", we need to know the vertices of the object, and how to connect them together with lines, i.e. to draw the edges. The simplest object of all is a tetrahedron -- four points, and every point is connected to every other point. This turns out to be pretty important, as a lot of memory is saved by using only tetrahedrons. To see why, first consider what the code to draw edges from a list of vertices must look like: rotate points ldx #number_of_edges :loop stx temp ldy edge_vertex1,x ;index into some list of vertices lda edge_vertex2,x tax jsr drawline ldx temp dex bpl :loop Now consider a cube; in my original code idea, I was going to use cubes and tetrahedrons (pyramids). A cube has eight vertices and 12 edges. Each vertex has an x, y, and z coordinate, and from the code above each edge needs two bytes, one for each vertex of the edge. 48 bytes, just to store a cube -- almost 1/10 of the entire 512-byte code! (Using code to generate the vertices is possible, but still takes a fair number of bytes.) Compare this to the humble tetrahedron, which only requires twelve bytes: three for each vertex. What about the edges? Remember that every point is connected to every other point in a tetrahedron. This means that we do not have to store the edge connections, but can compute them manually, and draw the whole thing using the following code: [count = 3] ; Plot :ploop ldy count :l2 ldx count dey tya pha jsr DrawLine pla tay bne :l2 dec count bne :ploop This code simply draws lines between all vertices: 3-2, 3-1, 3-0, and so on. It uses pretty much the same number of bytes as the earlier code, but doesn't require any storage of the edge connections (12 bytes to store the connections). Next consider the vertices of a tetrahedron. It turns out that by carefully selecting the vertices, default zero-page values can be used, something that isn't possible with e.g. a cube. Consider the following tetrahedron vertices: Px = 0, -4, 16, -4 Py = 16, 0, 8, 0 Pz = 0, 16, 0, -16 (just the vertices of a more or less regular tetrahedron which I drew on a piece of paper). The trick is to arrange these coordinates in the right way. Location $ae/$af is used by the load routine (among others) to store to memory while loading; at the end of a load, this location contains the end address+1. And, it is surrounded by zeros: >C:00ab 00 00 00 00 00 00 00 3c 03 00 00 00 00 00 00 00 .......<........ which means that by engineering the end address right we can store two coordinates here. In this case, I chose the end address+1 to be $10f0, which stores $f0 and $10 in $ae/$af -- -16 and 16, two of the Pz values, the other two being zero. This was my original plan anyways, until I re-discovered that the screen setup routine altered the value of $ac (the kernal routine to move the screen up exits with .A=$ac, so incrementing it re-initializes .A in every loop iteration.) On the other hand, it increments it 16 times, so that after the load and the init the zp values are >C:00ab 00 10 00 f0 10 .. The values 00 10 00 f0 are exactly the Pz values above: 0, 16, 0, -16. Careful study of default zero-page values then shows >C:0040 00 00 08 00 00 00 00 24 00 00 00 00 00 00 00 00 .......$........ This is pretty much Py, except for the first value -- so all the code has to do is store a 16 at location $40, and it turns out the screen init loop ends with .X=$10. So, one STX does the job, saving yet more bytes. Moreover, by locating the vertices in zero page, zero-page instructions can be used to access the point lists, saving even more bytes. Now, the above are the vertices, but what about the _centers_, i.e. the object locations? Once again, to save space I just used some default zero-page values, with the x-coordinates at $14 and the z-coordinates at $7d. The reason these were chosen is pretty straightforwards. Since objects just move 'downstream' with increasing z-coordinate, the z-coords should be somewhat spread out; the values at $7d are: >C:007d 3a b0 0a c9 20 f0 ef 38 e9 30 38 e9 d0 60 80 4f which are somewhat spread-out. The x-coords, on the other hand, need to be clustered around 0. The camera (you) is located at x=0, and if objects have a large value for the center x-coordinate they are way off to the side (you've probably noticed a few objects like this). Location $14 has some zeros and some nonzero numbers that are near zero, i.e. that cluster around zero: >C:0014 00 00 19 16 00 0a 76 a3 00 00 00 00 00 00 76 a3 Not great values, but good enough -- beggars can't be choosers. Of course, poking different values into locations 20 and above will put the tetrahedrons in different places. ----------------------- Rotation and Projection ----------------------- Rotations are done very simply, using tables. As outlined earlier, there is a complete set of tables of r*sin(theta). At first blush, the 'natural' way of setting up these tables would be to have a table of 1*sin(theta) in one page, a table of 2*sin(theta) in the next page, and so on, maybe fitting a table of cos(theta) in the same page. The location of r*cos(theta) would then be given by page = offset+256*r (e.g. $40+r for tables starting at $4000) value = page+theta It makes a lot more sense, though, to instead let _theta_ be the page index, and let each page contain r*sin(theta) for different values of _r_; the lookup is then page = offset+256*theta (e.g. $5300 for theta=$13) value = page+r For one thing, the pointer setup is very easy -- there's only one value of theta to set up, instead of different values of r (for different x,y coordinates). For another, the entire range r=-128..127 can be used, which means the same tables can be used to rotate object _centers_ in addition to object _vertices_. (If you recall programs like lib3d, the object centers are 16-bit signed values and have their own rotation routine, whereas the object vertices are limited to -96..95 and have a separate, optimized rotation routine; in this case, both the vertices and centers are eight-bit signed numbers.) This all means that rotations (e.g. y*cos(theta) - x*sin(theta)) amount to LDY Py,X LDA (cos),Y LDY Px,X SEC SBC (sin),Y to rotate a point. Now, the usual 3D world calculations look like: rotate object centers rotate vertices, add to rotated center, and project Consider rotating the z-coordinate; the code will look like LDA (cos),Y LDY Px,X SEC SBC (sin),Y CLC RotM1 ADC CZ that is: rotate vertex (z*cos(theta) - x*sin(theta)) and add to center (ADC CZ). Here's the great part: if we instead want to rotate the _center_ of the object, we want to _store_ the rotated point in CZ; the code would look like LDA (cos),Y LDY Px,X SEC SBC (sin),Y STA CZ This is exactly the same code as above, except the ADC is changed to a STA. Therefore only one routine is needed, using self-modifying code to decide whether to STA the center coordinate or ADC it. In the code, the appropriate instruction is passed into the routine in the .Y register. There's one other thing to be mentioned about the rotation routine. The rotation tables are of r*sin(theta), and r*cos(theta) is of course done by adding pi/2 to the theta-coordinate (theta+16 in the program). There are two ways to do this -- add 16 to the theta coordinate and correct any overflow (AND #63, for example), or extend the tables by an extra pi/2. Byte-wise, the first method is the best, but check this out: instead of adding pi/2, we can also subtract 3*pi/2. The setup code then becomes: RotProj AND #$3F ORA #>SINTAB STA sin+1 SBC #$2F ;-3*pi/4 ; ADC #$10 ; AND #$3F ORA #>SINTAB STA cos+1 The trick works here because of the ORA #>SINTAB, which is $4000 -- this allows negative angles to work, by borrowing higher bits. Consider: .A ORA #>SINTAB SBC #$2F ORA #>SINTAB -- ------------ -------- ------------ $12 $52 - sin tab at $5200 $22 $62 - cos tab at $6200 $22 $62 - sin tab at $6200 $32 $72 - cos tab at $7200 $32 $72 - sin tab at $7200 $42 $42 - cos tab at $4200 (C is clear in the SBC above). By using an SBC, angles automatically wrap around from $8000 to $4000. This saves two bytes over the ADC #$10 AND #$3F method (commented out above). Every byte counts!!! Projections ----------- The easiest way to do projections, once again, is via tables of f(x,z)=x/z, much like the tables of f(r,theta) = r*sin(theta). Alas, the setup code to generate these tables took up too much space, so the projects are computed 'manually', using a shift-and-add division routine. Now, it turns out that the routine really computes 64*x/z -- the 64 is the magnification factor. The nice thing about a shift-and-add routine is that multiplying by 64 is possible just by changing the number of shifts. So the routine adds an extra 6 shifts into the division loop -- a little inefficient cycle-wise, but pretty thrifty byte-wise. ------------- Drawing lines ------------- Obviously, to render an object we need a line drawing routine. The line routine in the program is pretty standard, and described in several earlier issues of C=Hacking, so I won't go into too much detail. Most of the paragraphs below are just random tidbits, so feel free to skip any (there won't be a test). The simplest and most efficient routines draw to a charmap -- you can read about this in detail in C=Hacking #8 and beyond -- since the .Y register maps directly to the y-coordinate, and the column-offsets are easy to compute. The biggest charmap available is 128x128, so that's what I used. Overall, the line routine is pretty small, while being reasonably fast. The plot routine is 'dumb', and recalculated for every pixel, but the recalculation itself is fairly efficient, with a few table lookups. It draws into a 128x128 buffer and can handle off-screen coordinates, and the buffer can be anywhere (that it, it supports a double-buffer display). So, I think it turned out OK, all things considered. With that background, here's the main line drawing loop: plot pha tya bmi calcline lda bitphi,x ora base sta point+1 lda bitplo,x sta point lda bitp,x beq calcline ora (point),y sta (point),y calcline pla mod2 sbc #dx bcs mod5 mod3 adc #dy mod4 inx mod5 iny dec temp bne plot The basic line routine iteration goes like plot x,y y=y+1 a = a - dx if a<0 then a=a+dy, x=x+1 for slope>1. The code for slope<1 is exactly the same, except for swapping x and y, and dx and dy. Therefore, I just used one routine and self-modifying code to set INX and INY etc. in the right places (mod2, mod3, mod4, and mod5 above). In retrospect this was not smart, and I think it would have saved 5 or 6 bytes to use two routines, and jsr to the plot routine -- the routines to set up the self-modifying lines take more space than the basic iteration. The x and y coordinates are stored directly in the .x and .y registers. This makes the plotting really easy and relatively fast, and works well with the 128x128 charmap. Off-screen points are a must, so the allowed coordinates are -64..192, giving 64 pixels to either side of the 128x128 visible area. Checking for these is easy, since the high bit will be set for coords <0 and >127. These are checked in the plot routine. The y-coordinate is checked directly, using tya; the x-coordinate is checked for range by use of the bitp table -- this table contains the bit pattern for the x-coordinate (%1000000 %01000000 etc.), and all of the values for x>127 are set to zero. Once again, in retrospect it would have been more memory-efficient to do this with txa (two more bytes), but darn it all, SOMETHING has to be at least a little bit cycle efficient here! Old habits die hard! The line routine always draws from left to right, which means the initialization routine calculates dx = x2-x1, and if dx<0 then it swaps the two endpoints. This creates a problem when coordinates are -64..192 though; after subtracting x2 and x1 do you check the negative bit, or the carry bit? Cases like x1=-1, x2=1 should work, so the carry bit is useless; on the other hand, long lines, say x1=1, x2=130, should also work, so the high bit is also useless. The solution I used was to offset coordinates by +64 (and once again, in retrospect...). The point coordinates are stored in two lists, one of x-coords and one of y-coords. This means that the endpoints are simply indexes into those point lists, i.e.: xlist contains list of x-coords; ylist list of y-coords xlist,x and ylist,x contain left endpoint xlist,y and ylist,y contain right endpoint That simplified a lot of things -- the lists can be in zero-page, swapping coordinates is very simple, and so on. The routine is double-buffered -- flickery single-buffers are just too painful. Since $2000 and $2800 are the locations of the two charset buffers, the current buffer is stored in zero-page variable $ce ("base" in the plot code above), which starts out initialized to #$20 (location $81 would also work) -- one more variable to not initialize. So, in summary: a pretty standard line routine, with a few memory optimizations thrown in. ------- Wrap-up ------- Well, that's about it. As you can see, the code really runs on the edge -- zero-page has to be initialized correctly, little bits and pieces are missing from certain routines, things have to line up just right... but it works! There are undoubtably other places where bytes can be saved, of course, but I think it does a pretty good job of shaving bytes overall. See you at next year's contest! * * tetrattack! * * Mini-3D rendering package * * - Motion in the x-z plane => rotations about one axis only * - Plots to charmap * * SLJ 9/01 * ; org $1000 org $0ef0 NUMOBJS = 9 temp = $02 dx = $03 dy = $04 point = $05 AUX = $03 ACC = $04 CX = $07 CZ = $08 rottemp = $09 ;0 initially zpoint = $0a ;low byte already set to zero zpoint2 = $0c count = $0e angle = $0f cenx = $14 Py = $40 XCoord = $50 YCoord = $60 theta = $70 cenz = $7d ; $ac taken by screen setup routine ; final value = $10 Pz = $ab base = $ce ;$20 initially ;alternate: ($81) p4000 = $8f ;$4000 initially p6000 = $89 ;$60xx initially p8000 = $9c ;$8000 tagged = $e0 sin = $f7 ;0 low byte cos = $f9 curobj = $ff bitp = $1c00 bitplo = $1d00 bitphi = $1e00 bitphi2 = $1f00 SINTAB = $4000 PROJTAB = $8000 DEY = $88 INY = $c8 INX = $e8 ADC = $65 STA = $85 start sta $8f ;set up p4000 * * Set up VIC * sta $d021 sta $0286 ;clear color jsr $e544 ;clr scr lda #$18 sta $d018 * * Line drawing tables * ldx #$90 ldy #$7f lda #$01 :l1 sta bitp,y cmp #$80 rol pha tya lsr lsr lsr lsr sta bitphi,y lda #00 sta bitp+128,y ;0 = dont draw ror sta bitplo,y * * Extend sin table to 0..31 * lda sin0,y sta sin0+17,x ;sta sin0+32,x inx pla dey bpl :l1 ;.y=$ff ;.x=$10 * * Set up sin tables * InitRot iny sty p6000 ;rats :( ; ldy #00 ;rats :( ; ; sty temp ;:l3 ldx rottemp ; lda sin0,x ; sta aux ;sin(theta) ; ;:l4 ; ; clc ; jsr MULT8 ;.Y * AUX ; ; AUX*.Y -> ACC,.A (low,hi) 16-bit result ; AUX, .Y unaffected ; .Y can be negative ; :Mult8 sty temp ;dumb multiply ; sty acc ; lda #00 ; tay ;:mloop clc ; adc sin0-$10,x ; bcc :skip ; iny ;:skip dec acc ; bne :mloop ; tya sty acc lda #00 ldy #9 clc :mloop ror ror acc bcc :mul2 ; clc ;dec sin0 table by 1 instead adc sin0-$10,x :mul2 dey bne :mloop ldy temp bpl :pos sec sbc sin0-$10,x :pos sta (p4000),y eor #$ff clc adc #1 STA (p6000),y iny bne :mult8 inx inc p4000+1 inc p6000+1 bpl :mult8 ;to $8000 ;.x=$20 ;.y=0 * * Set up Screen * ; lda #00 ;bah! ; tya :l2a ; pha jsr $e8ea ;scroll up ; pla ;.A = ($AC) ;.X=00 clc ;necessary? :l2 ;set one line sta $0720+12,x inc $db20+12,x inx adc #16 bcc :l2 ; adc #$00 inc $ac cmp #15 bne :l2a :done ;.X=$10 stx $40 ;rats :( ;init Py * * Main program loop: * - get input * - update positions/angles * - render * - swap buffers * MainLoop ; Clear buffer and swap lda base eor #$08 sta base sta zpoint+1 ldy #00 tya ldx #8 :l0 sta (zpoint),y iny bne :l0 inc zpoint+1 dex bne :l0 ; Get Input ; .X=0 lda $dc00 lsr lsr lsr bcs :c1 inc theta :c1 lsr bcs :c2 dec theta :c2 and #$01 sta tagged eor #$01 ora $23c0+6 sta $23c0+6 ;shot fired ; lda $cb ; and #3 ; beq :skip ; lsr ; bcc :inc ; dec theta ; lsr ; bcc :skip ; jsr Forwards ;:inc inc theta ;:skip ObjLoop ; Compute relative center inx stx curobj dec cenz,x ;Update pos lda cenx,x ; sec ; sbc cenx sta Px+4 lda cenz,x ; sbc cenz sta Pz+4 ; Rotate Rot lda theta,x adc theta sta angle lda theta ldx #4 ldy #STA jsr RotProj lda cz sbc #14 ; bmi :skip cmp #125 bcs NoDraw cmp cx bmi NoDraw adc cx bmi NoDraw ; If in view, rotate project & plot dex stx count :loop lda angle ldy #ADC jsr RotProj sta YCoord,X dex bpl :loop ; Plot :ploop ldy count :l2 ldx count dey tya pha jsr DrawLine pla tay bne :l2 dec count bne :ploop ;.y=0 NoDraw ldx curobj ; Update lda tagged,x beq :zip lda cx ora tagged sta tagged,x dfb $2c :zip inc theta,x cpx #NUMOBJS bcc ObjLoop jsr $eb59 ;Swap buffer ;.Y=1 .A=$7F jmp MainLoop * * Line routine * - Draws from L to R * - Forces dx>0 (x1 < x2) * - Numbers are +128 offset, to allow * - DX and DY to be 0..255 for long lines * - Uses same core routine for stepinx * and stepiny by changing variables * * On input: * .X = index into point list, point 1 * .Y = index of point 2 * Pswap sty temp txa tay ldx temp DrawLine lda xcoord,y sec sbc xcoord,x bcc Pswap ;x2 >= x1 sta dx lda ycoord,y sbc ycoord,x ;dy = y2-y1 bcs :posy ldy #DEY eor #$ff adc #1 dfb $2c :posy ldy #INY sta dy cmp dx lda #INX ; bcs stepiny bcs :noswap tya ldy #INX :noswap sty mod5 sta mod4 stepinx ; sta mod5 ; sty mod4 ;INY/DEY lda dy ldy dx bcc mod stepiny ; sta mod4 ; sty mod5 ;iny/dey lda dx ldy dy mod ; sty mod1+1 sty temp sty mod3+1 sta mod2+1 Draw lda ycoord,x sec sbc #64 tay lda xcoord,x sec sbc #64 tax ;mod1 lda #dy lda temp beq done ;no steps! ; sta temp lsr plot pha tya bmi calcline lda bitphi,x ora base sta point+1 lda bitplo,x sta point lda bitp,x beq calcline ora (point),y sta (point),y calcline pla mod2 sbc #dx bcs mod5 mod3 adc #dy mod4 inx mod5 iny dec temp bne plot done rts * * Rotate and project point * * On entry: * .X = index into point list * .A = rotation angle * .Y = ADC/STA for points/centers * CX,CZ = location of object * * On exit: * Points stored in xcoord,x ycoord,x * RotProj AND #$3F ORA #>SINTAB STA sin+1 SBC #$2F ;-3*pi/4 ; ADC #$10 ; AND #$3F ORA #>SINTAB STA cos+1 STY RotM1 STY RotM2 RotProj2 LDY Pz,X LDA (sin),Y PHA LDA (cos),Y LDY Px,X SEC SBC (sin),Y CLC RotM1 ADC CZ STA aux ; LDY Px,X ; LDA (cos),Y ; LDY Pz,X ; CLC ; ADC (sin),Y PLA CLC ADC (cos),Y CLC RotM2 ADC CX JSR Div8 STA XCoord,X LDA Py,X ; JSR Div8 ; STA YCoord,X ; RTS * * Signed division routine * * 64*.A/AUX -> .A * Only valid for .Y/AUX < 1 * .A pos or neg, AUX > 0 * AUX, .X unaffected * DIV8 ; STY ACC ; tya php bpl :pos ;.A just loaded eor #$ff :pos sta acc LDA #0 LDY #14 :DLOOP ASL ACC ROL CMP AUX BCC :DIV2 SBC AUX INC ACC :DIV2 DEY BNE :DLOOP ;RTS lda acc plp bpl :pos2 eor #$ff :pos2 eor #$80 ;+128 offset rts * * Point list * Last point is for relative cx,cz * ;Pz dfb 0,16,0,-16,0 ;Py dfb 16,0,8,0 Px dfb 0,-4,16,-4 ;note: px+4 intrudes on table below * * 128*sin(t), t=0..15 * * Table must be at end of code! * ;sin0 dfb 0,13,25,37,49,60,71,81 ; dfb 91,99,106,113 ; dfb 118,122,126,127,128 ;sin0 dfb 0,25,50,74,98,120,142,162 ; dfb 180,197,212,225,236,244,250,254,255 sin0 dfb 0,24,49,73,97,119,141,161 dfb 179,196,211,224,235,243,249,253,255 end ....... .... .. . - fin -
magazines/chacking21.txt · Last modified: 2015-04-17 04:34 by 127.0.0.1