######## ################## ###### ###### ##### ##### #### #### ## ##### #### #### #### #### #### ##### ##### ## ## #### ## ## ## ### ## #### ## ## ## ##### ######## ## ## ## ##### ## ## ## ## ## ##### ## ## ######## ## ## ## ### ## ## #### ## ## ##### #### #### #### #### ##### #### #### #### #### #### ###### ##### ## ###### ###### Issue #18 ################## July 3, 1999 ######## ............................................................................... Time flies like the wind; fruit flies like a banana. "Yet if the only form of tradition, of handing down, consisted in following the ways of the immediate generation before us in a blind or timid adherence to its successes, 'tradition' should be positively discouraged. We have seen many such simple currents lost in the sand; and novelty is better than repetition. [Tradition] cannot be inherited, and if you want it you must obtain it by great labor." T. S. Eliot, "Tradition and the Individual Talent" ............................................................................... BSOUT Tradition. C=Hacking is a magazine of considerable tradition, a tradition that is not merely imitating the successes of previous generations. C=Hacking has a tradition of true excellence, and once again, great people have contributed their time and talents towards the 64 community, and another fine issue of C=Hacking. And once again, innovative ideas have grown and borne delectable fruits for those seated at the C=Hacking table. And once again, in keeping with one of C=Hacking's most hallowed traditions, the issue is really, really late. A new job, a new move, a new house, a new puppy -- what can I say? This real world stuff takes some getting used to, and so this issue is even later than usual. On the plus side, I think you'll find it worth the wait (at least, I hope so!). A lot has happened in the C= world since the last issue of C=Hacking. At the personal level, all my moves and uphevals have led to a few changes. Now that I'm fabulously wealthy (compared to my old graduate student salary, I am fabulously wealthy), I splurged on a custom domain name. The Fridge is now located at http://www.ffd2.com, and thus the Official Unofficial C=Hacking Homepage is now located at http://www.ffd2.com/fridge/chacking/ And in the "well, it's news to me" department: - SuperCPU acitivty seems to be picking up steam, at long last. The giga.or.at scpu mail list recently revived itself, and several new projects and web pages have appeared. Moreover, 65816 assemblers have finally started to appear. El Cheapo Assembler (CheapAss), for SuperCPU-equipped 64s, is available in the Fridge. A new cross-assembler, ACME, is being worked on. And a *third* project, Virtualass816, is said to be underway. In addition to the assemblers, there is an 816 backend to LCC, some new operating system projects (e.g. JOS), rumors of games, game fixes (including a Flight Simulator patch by Maurice Randall), and more. http://come.to/supercpu is a good place to learn more about new SCPU developments. - There will be an English version of GO64! magazine, starting with the August issue, available by subscription. For more information, visit http://www.go64.c64.org - The annual Chicago Expo will take place in -- amazingly enough -- Chicago, on September 25. Last year was a hoot and hopefully our group will be there again this year. For more details, http://members.aol.com/~rgharris/swrap.html will surely contain info as the date draws near. - Justin Beck, a dj at station KDVS, in Davis, CA, runs a SID radio show every tuesday night at 8PM Pacific time. You can tune in at 90.3 in the Davis/Sacramento area, or the webcast at http://www.kdvs.org. For more information, write jrbeck@ucdavis.edu; actually, write him anyways, to tell him how cool the show is! - CBM FIDO echos are available at several places on the web these days -- http://cereal.mv.com is a pretty popular source. - Craig Bruce has been placing old issues of the Transactor online at http://www.pobox.com/~csbruce/commodore/transactor/ Well worth a visit. - Another unzip program has appeared, by Pasi Ojala. Visit his homepage http://www.cs.tut.fi/~albert/ for more details. - Richard Atkinson has drawn up schematics of the Commodore Sound Expander, a Yamaha-chip-based cartridge. For more info, email Richard! (And maybe look in a future issue of C=Hacking??? :) This weekend, here in the states, we are celebrating our independence (I think the Canadians tried to invade us once, or something...). I can't help but reflect that the Commodore 8-bits also represent a kind of independence. As the above (and the below) amply demonstrates, that independent spirit is alive and thriving, a fact that is not only remarkable, but even perhaps worth celebrating. Enjoy the issue! -S ....... .... .. . C=H 18 ::::::::::::::::::::::::::::::::::: Contents :::::::::::::::::::::::::::::::::: BSOUT o Voluminous ruminations from your unfettered editor. Jiffies o Maybe next time! The C=Hallenge o Yet again, no C=Hallenge, sigh... Side Hacking o Data Structures 101: Linked Lists DS101 is a new article series. The idea is to review different data structures, with examples of their use in 64 programming. This installment covers linked lists, and how to use them to make a zippy insertion sort with almost zero overhead. o Counting Sort, by Pasi Ojala And, since we're on the subject of sorting algorithms, Pasi wrote up the counting sort. What's a counting sort? Well, read the article! Main Articles o "VIC-20 Kernel ROM Disassembly Project", by Richard Cini This installment covers interrupts -- IRQ and NMI sources, the kernal handler code. o "A Diehard Programmer's Introduction to GEOS, and geoWrite Disassembly Notes", by Todd S. Elliott As part of his effort to learn about GEOS programming, Todd disassembled geoWrite 128, and patched it to be more accepting of new devices and such. This article summarizes that adventure -- the results and the lessons learned. o Masters Class: "NTSC/PAL fixing: FLI", by Russell Reed , Robin Harbron , and S. Judd. This time around the subject is FLI and IFLI graphics, and a tutorial on fixing them. Several pictures are provided for the reader to fix, in the included .zip file. o "Obj3d: The 3D object library", by S. Judd Obj3d is a set of routines for creating, manipulating, and displaying 3D worlds on the 64. It consists of routines to add and remove objects, move and rotate objects, render the display, and so on, and hence vastly simplifies the creation of 3D programs. This article actually consists of three articles. The first article describes the library, and walks through a simple example program. The second article is the "programmer's guide", containing memory maps and a list of all the routines. The third article discusses "stroids", a more advanced example program in which a space ship can fly around a randomly drifting asteroid field, to demonstrate that sophisticated programs can be written with only a few hundred lines of code. The program is purposely left incomplete -- it's up to you to finish it up! We had hoped to include a "3D Object Editor", written by Mark Seelye, but it wasn't quite done yet -- next issue! Source code and binaries are included at the end of the issue. .................................. Credits ................................... Editor, The Big Kahuna, The Car'a'carn..... Stephen L. Judd C=Hacking logo by.......................... Mark Lawrence For information on the mailing list, ftp and web sites, send some email to chacking-info@jbrain.com. 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 serious dork! About the authors: Todd Elliot is 30 years old, working as a Community Client Advisor for the Center On Deafness - Inland Empire, working with deaf people in the local communities. He got his first 64 in December 1983, using it for games, BBS activities, and dabbling in programming. Nowadays Todd focuses on ML programming, and his latest project is an AVI movie player for the SuperCPU. Todd is a huge fan of sports and the Miami Dolphins in particular, and enjoys writing articles and watching movies. At the 1998 Chicago Expo Todd enjoyed meeting all those people who were previously a name and an email address; according to Todd, "The Chicago Expo truly embodies what is going on with today's CBM community." Richard Cini is a 31 year old vice president of Congress Financial Corporation, and first became involved with Commodore 8-bits in 1981, when his parents bought him a VIC-20 as a birthday present. Mostly he used it for general BASIC programming, with some ML later on, for projects such as controlling the lawn sprinkler system, and for a text-to-speech synthesyzer. All his CBM stuff is packed up right now, along with his other "classic" computers, including a PDP11/34 and a KIM-1. In addition to collecting old computers Richard enjoys gardening, golf, and recently has gotten interested in robotics. As to the C= community, he feels that it is unique in being fiercely loyal without being evangelical, unlike some other communities, while being extremely creative in making the best use out of the 64. Pasi 'Albert' Ojala is a 29 year old software engineer, currently working at a VLSI design company on a RISC DSP core C compiler. Around 1984 a friend introduced him to the VIC-20, and a couple of years later he bought a 64+1541 to replace a broken Spectrum48K. He began writing his own BBS, using ML routines for speed, and later wrote a series of demos under the Pu-239 label. In addition to pucrunch and his many C=Hacking articles, Pasi's most recent project is an "unzip" program for the 64. Pasi is also a huge Babylon-5 fan, and has a B5 quote page at http://www.cs.tut.fi/~albert/Quotes/B5-quotes.html Robin Harbron is a 26 year old internet tech support at a local independent phone company. He first got involved with C= 8-bits in 1980, playing with school PETs, and in 1983 his parents convinced him to spend the extra money on a C64 instead of getting a VIC-20. Like most of us he played a lot of games, typed in games out of magazines, and tried to write his own games. Now he writes demos, dabbles with Internet stuff, writes C= magazine articles, and, yes, plays games. He is currently working on a few demos and a few games, as well as the "in-progress-but-sometimes-stalled-for-a-real-long-time- until-inspiration-hits-again Internet stuff". He is also working on raising a family, and enjoys music (particularly playing bass and guitar), church, ice hockey and cricket, and classic video games. .................................. Jiffies ................................... Blah. ............................... The C=Hallenge ............................... Bleah. ................................ Side Hacking ................................ Data Structures 101 -- Linked lists and a nifty sorting algorithm ------------------- by S. Judd and Pasi Ojala -- Every computer science major has taken a class in data structures. The 64 programming world, however, is full of non-CS majors. Data structures are such useful tools for programmers to have in their toolbox that I thought it would be a worthwhile thing to have various people periodically review different types of data structures, and common algorithms which make use of them, and their relevance to an 8-bit CBM. What is a data structure? Perhaps a reasonable definition is that it is an abstract method of storing and retrieving data. These abstractions may then be implemented on the computer, to solve different types of problems. Whereas no single data structure is ideal for all problems, often a given problem has a data structure ideally suited for it. The "optimal" data structure for a given problem depends heavily upon what kind of data is stored, and how it is stored, retrieved, or otherwise manipulated. (On a more humorous note, /dev/null is ideal for storing information provided you don't need to retrieve it, ever -- this probably doesn't count as a data structure, though). A simple example of a data structure is an array: abstractly, it stores and retrieves data by means of an index value, e.g. A$(I). On the computer it might be implemented in many different ways, depending on the type of data stored (integers, strings, floating point, custom records, etc.), the dimension of the array, the computer hardware, and even whether the index is e.g. an integer or a string. So it is worthwhile to distinguish the abstract concept of an "array" from its actual implementation. Another type of useful data structure is a linked list. Imagine attaching a pointer to some chunk of data (usually called a "node"). This pointer can then point, or link, to another chunk of data -- the next node in the list. This can be schematically illustrated as: +---+ +---+ +---+ +---+ +---+ | 3 |---->| 1 |---->| 4 |---->| 5 |---->| 9 |----> ... +---+ +---+ +---+ +---+ +---+ Here each node contains some data (a number) and a pointer to the next node. Starting from the first node -- called the "head" of the list -- a program can reach every other node by following the pointers. This is the basic idea of a linked list. Linked lists are used all over the place in the 64. BASIC programs are a type of linked list. Each line of a basic program is stored as a line link, then a line number and the data. The link points to the next line in the program. Having links speeds up BASIC programs (imagine finding and counting the ends of each line for every GOTO or GOSUB), and links are useful because each program line can be of different size (imagine storing a program in something like an array). The end of the list is specified with a line link of 00. A better example is the DOS. Every 256-byte sector on a disk drive starts with a 2-byte track and sector pointer, pointing to the next sector in the chain, and contains 254 bytes of data. This is exactly a linked list. The directory tells where the first sector of a program is -- the head of the list -- and the program is loaded by simply traversing the list -- following each link and reading the data. The end of the list is specified by using a special link value (track = $FF). The reason it is "better" is that whereas a BASIC program is stored sequentially in memory, a program stored on disk might be strewn all over the place. This is an important feature of linked lists: they can join together data that is spread all over memory. If you think about it for a moment, you'll quickly realize that elements may be added into (or removed from) the middle of a list simply by changing a pointer: +---+ +---+ +---+ +---+ +---+ | 3 |---->| 1 |---->| 4 |-+ +->| 5 |---->| 9 |----> ... +---+ +---+ +---+ | | +---+ +---+ | | | +---+ | +->| 1 |-+ +---+ (Well, okay, two pointers :). Inserting sectors into the middle of a program isn't exactly very useful for disk storage, but there are plenty of applications where it is extremely useful; one such application, discussed below, is sorting data. Both BASIC and the disk drive are examples of a forward- or singly- linked list. But imagine attaching a second pointer to each disk sector, pointing to the _previous_ track and sector: +---+ +---+ +---+ +---+ +---+ | |---->| |---->| |---->| |---->| |----> ... | | | | | | | | | | | |<----| |<----| |<----| |<----| |<---- ... +---+ +---+ +---+ +---+ +---+ This would be a "doubly-linked list". The downside would be a loss of two bytes per sector; the upside would be that if your directory track were destroyed, you could recover all programs on a disk -- in a singly-linked list like C= DOS, you have to know where the start of the list, i.e. the first track and sector, is. Moreover, with a doubly-linked list you can _delete_ a node without even knowing where the node is in the list; with a singly-linked list, you have to search through the list to find the pointer to the node. Of course, you could add even more pointers to a list, which is done for certain types of trees, for example. (Trees will perhaps be covered some other time). A fast sorting algorithm ------------------------ Let's say you had a list of numbers that you wanted to sort from largest to smallest. For example, the obj3d library, discussed later in this issue, needs to depth-sort objects, so that far-away objects don't overlap nearby objects when drawn on the screen. This amounts to sorting a list of 16-bit numbers. These numbers are stored in a simple list -- not a linked list, but an array, like: lobytes lo0 lo1 lo2 ... hibytes hi0 hi1 hi2 A typical sorting algorithm would have to spend a lot of time swapping numbers, moving stuff around, etc. Even with 16-bits this is a fair amount of overhead, and with even larger numbers it gets very time- consuming. But, as mentioned earlier, a linked list is tailor-made for rearranging data. That is, if we start with a list of sorted numbers, then inserting a new number into the list amounts to finding the right spot in the list, +---+ +---+ +---+ | 1 |---->| 2 |---->| 5 |--- +---+ +---+ +---+ changing the first part of the list to point to the new number, +---+ +---+ +---+ | 1 |---->| 2 |---->| 5 |-+ +---+ +---+ +---+ | | | +---+ +->| 6 |--- +---+ and having that new number point to the rest of the list. +---+ +---+ +---+ +---+ +---+ | 1 |---->| 2 |---->| 5 |-+ +->| 8 |---->| 9 |----> ... +---+ +---+ +---+ | | +---+ +---+ | | | +---+ | +->| 6 |-+ +---+ So sorting a list of numbers amounts to inserting these numbers into the right spot in the list, one at a time. Amazingly enough, this type of sort is called an "insertion sort". Your first thought might be "doesn't that mean a whole lot of overhead in copying data and changing pointers?!" It might, if we were lame PC programmers; but, of course, we are 64 coders, which means we are handsome, witty, superior, humble -- and most of all, sneaky. All we _really_ need is a) an index into the list of numbers b) a pointer to the next number The trick is simply to combine the two, by storing the linked list just like the list of numbers, as a sequential array of *8-bit* links: list link0 link1 link2 ... Now each link not only points to the next list element -- it exactly points to the next number as well. For example, let's say that the earlier list of numbers was 23,16,513 lobyte 23 01 16 hibyte 00 02 00 Sorting from largest to smallest should give 1-0-2 -- that is, element 1 is the largest, followed by element 0, followed by element 2. So the linked list could have the form head = 1 list 2 0 $80 To see how this works, start with the head of the list, which points to list element 1. LDX head To get the next element in the list is easy: LDA list,X Now .X is the current element, and .A is a link to the next element. To traverse the entire list, then we simply need to TAX and loop: LDX head :loop LDA list,X TAX BPL :loop This will traverse the list, until the $80 is reached. The thing to realize is that .X is *also* a list into the list of numbers, so for example you could print out the numbers, in order, with some code like LDX head :loop LDA lobyte,X LDY hibyte,X JSR PrintAY LDA list,X TAX BPL :loop Now all we have to do is construct the list! get next coordinate traverse linked list compare to coordinates in linked list, to find correct spot split linked list in half make bottom half of list point to the new element make the new element point to the rest of the list So far it is just your basic insertion-sort; if you are familiar with AmigaOS, it is similar to Enqueue(), which inserts nodes by priority. The beauty here is that the index registers make all this really, really easy; here's the sort code from obj3d, to sort positive numbers, stored in CZ and HCZ = lo and hi bytes, from largest to smallest. It starts at the head of the list (at list+$80), traverses the list to find the right spot, and inserts the "node": :loop [copy number to be inserted to TEMP, TEMP+1 for a little speed] LDY #$80 ;Head of list :l1 LDA VISOBJS,Y ;Linked list of objects BMI :link STY TEMPY TAY ;Next object LDA CZ,Y ;If farther, then CMP TEMP ;move down list LDA HCZ,Y SBC TEMP+1 BCS :l1 ;Nearest objects last in list TYA LDY TEMPY ;Insert into list :link STA VISOBJS,X ;X -> rest of list TXA STA VISOBJS,Y ;beginning of list -> X DEX BPL :loop :rts RTS Here, VISOBJS is the linked list of sorted coordinates. Personally, I think that's awfully nifty -- an insertion sort with almost zero overhead. In summary, a linked list is simply an abstract method of storing and retrieving data. For certain kinds of problems it is extremely useful, even optimal, and for certain problems it can be implemented in a very efficient and convenient way. And as pointed out in the beginning of this article, that is the essence of a data structure. I suppose that about wraps things up. So, who wants to volunteer the next data structures article? :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Counting sort ------------- by Pasi Ojala Because we got ourselves tangled up with sorting algorithms, we may as well take a look into another one called counting sort. The idea is to sort a list of symbols according not to the symbols themselves, but rather according to a "key" associated with the symbols. This will become clear shortly. This sorting algorithm can be used with integer-valued data when the range of sorting key values (the values by which the order is decided) is small enough. The foundation for counting sort is to make one pass through the data and determine the sorted order of the data, then make another pass and perform the actual shuffling of data. Now, what kind of a data structure is used for counting sort? Surprise, we only need a counter for every possible sorting key. This is why a limited range of values is required or the memory consumption would simply be too large. And we need an array of input data and an array for the sorted output data, as the sorting can't be performed in place. An example sorts the following data, which in fact represents a Huffman tree. The sorting keys are the code lengths, and the associated data is the corresponding symbol. The sorting of symbols is required in some of the Huffman tree creation routines. key: 4 3 1 5 3 6 3 6 sym: A B C D E F G H The sorting keys can have value from 1 to 6, so we need 6 counters. Their initial values are set to zero: for(i=1;i<7;i++) count[i-1] = 0; count: 0 0 0 0 0 0 Then we perform the counting stage by going through the data and incrementing the counter corresponding to the sorting key value. In the end the counters contain the number of each code length found in the data. for(i=0;i<#ofvalues;i++) { count[sort_key[i]-1] = count[sort_key[i]-1] + 1; } count: 1 0 3 1 1 2 Then cumulative counts are calculated for this array. for(i=1;i<6;i++) { count[i+1] = count[i+1] + count[i]; } count: 1 1 4 5 6 8 If you take a close look into the meaning of the values now in the count array, you might notice that the last count value gives us from which element downward to stick the data with sorting key 6, the previous one where to stuff data with key 5 and so on. So, next we simply copy each element in the data into its final place in the output array using the cumulative counts calculated previously. Note that in C the indexing starts from 0, but in the table from 1 for the reader's convenience. for(i=#ofvalues-1;i>=0;i--) { count[key[i]-1] = count[key[i]-1] - 1; outputkey[count[key[i]-1]] = key[i]; outputsym[count[key[i]-1]] = sym[i]; } 1 2 3 4 5 6 1 2 3 4 5 6 7 8 --------------------------------- 6 1 1 4 5 6 8 x x x x x x x 6 H 7 X X X X X x X H 3 1 1 4 5 6 7 x x x 3 x x x 6 G 3 X X X G X x X H 6 1 1 3 5 6 7 x x x 3 x x 6 6 F 6 X X X G X x F H 3 1 1 3 5 6 6 x x 3 3 x x 6 6 E 2 X X E G X x F H 5 1 1 2 5 6 6 x x 3 3 x 5 6 6 D 5 X X E G X D F H 1 1 1 2 5 6 6 1 x 3 3 x 5 6 6 C 0 C X E G X D F H 3 0 1 2 5 6 6 1 3 3 3 x 5 6 6 B 1 C B E G X D F H 4 0 1 1 5 6 6 1 3 3 3 4 5 6 6 A 4 C B E G A D F H So, after the loop we have sorted the symbols according to the code lengths. We haven't talked about the O() notation, but the counting sort is an O(n) process. Counting sort only needs three fixed-sized loops, thus if the amount of data increases linearly, the sorting time also increases linearly. With insertion sort the sorting time increases geometrically because searching for the right spot to add a node takes longer and longer when the number of already sorted nodes increases. One extra bonus for counting sort is that it preserves the so-called inside order. The order of elements with identical keys is preserved in the end result. This is very important in many algorithms, like the Huffman tree creation GZip uses (and which gunzip.c64 used before the algorithm was changed to not require sorting). On the minus side is the necessity of the output buffer. Other sorting algorithms can sort the data in-place, although that also means that the data must be copied a lot of times. The preservation of inside-order also allows the sorting of data by multiple keys: first sort by secondary keys, then by primary keys. After this the data is sorted by the primary keys and all elements having identical keys are sorted by the secondary keys. And that's it! ....... .... .. . C=H #18 :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Main Articles ------------- VIC KERNAL Disassembly Project - Part II Richard Cini May 21, 1999 Introduction ============ Last issue, we began by exam