Tuesday, July 30, 2013

RC 2013 SC Wrap-Up

Once again, a Retrochallenge event draws to a close.  As usual, I have greatly enjoyed participating in this event.  Setting some deadlines is a good way to motivate progress on a project, even silly ones involving retro computers.  Plus, it is always great to have the recognition and the feeling of accomplishment that comes from having the audience that comes with participation in a great event!

Recap

My project for this month was to adapt the Dunfield Micro-C compiler for building code to run on the CoCo.  Initially I just wanted to make it relatively simple to use the tool for building simple CoCo programs.  After some initial victories, I went further by supporting a variety of ways for loading and starting such programs.  I also now support several options for passing data between C programs and the built-in Color BASIC on the CoCo.  To prove the point, I implemented a couple of non-trivial CoCo programs in C -- an animated clock display and a solver for Sudoku puzzles.  Although I have more in mind to do on this project, I am extremely happy with the results as they stand right now!

Benefit

The CoCo community has a bit of a schism between users of OS-9 (or its descendant Nitros-9) and those that mostly stick to the Disk Extended Color BASIC (DECB) environment.  For sure, most CoCoNuts have a foot in each camp.  Yet, most prefer one or the other.  Each option has its own merits, but those that prefer the DECB environment usually cite both simplicity and the direct control of the CoCo's hardware as important strengths.

Both camps have both BASIC (including BASIC09) programmers and assembly language programmers.  The OS-9ers have also enjoyed a C compiler for decades, but the DECB-based C compilers are mostly the stuff of barely remembered advertisements in The Rainbow.  Now, the DECB crowd has at least the beginnings of another option!

Onward

I have really enjoyed using C to program for the DECB environment.  So, I am planning to continue this project in the hopes of enabling more CoCoNuts to have the same opportunity.

As I have pursued this project, I have generated a list of more TODO items than I have had a chance to pursue.  These include a few more startup options, code libraries, hardware drivers, and the like.  I expect to hit many of these over the next few weeks or months.  If nothing else, then I should have something together by next year's CoCoFEST!

Normally I would like to have more code to release at this point.  Unfortunately, I haven't had a chance to pull a release package together.  Since this project depends on the Dunfield compiler distribution, I want to make sure that I can release something as clean as possible to make the distinction clear between my code and the Micro-C package.  Also, I want to put together at least some minimal documentation on how to put everything together in order to start building CoCo programs!

So, for now you will have to make do with the bits and pieces that I have released along the way.  I hope that whets your appetite for more.  If you want to collaborate on advancing this project, then feel free to contact me and let me know so.  And, in any case, be sure to stay tuned... :-)

Sunday, July 28, 2013

Sudoku Solver

My Micro-C for CoCo project is showing some real strength!  Yesterday, in just a couple of hours I was able to crank-out a non-trivial C program to solve a popular style of number puzzle.  That was a lot of fun!  Moreover, it was simpler than trying to implement the same thing in pure assembly language and the resulting program ran a lot faster than it would run if it were written in Color BASIC.

Sudoku

In the past decade or so, Sudoku puzzles have become as commonplace as the venerable crossword puzzle.  The use of numbers seems to have a special appeal for some folks, and it has been quite common for people to implement solvers for these puzzles as a programming exercise.  Quite a lot of discussion is available over various algorithms for solving such puzzles, and implementations of these algorithms are quite numerous.

A friend of mine had such a project a while back.  When he learned of my current project, he jokingly suggested that I should try to compile his solver for the CoCo.  I think that his project implemented some clever algorithm or another -- I never saw his code, so I don't know if it would be out of the question for the CoCo or not.  But, I did find a brute force algorithm that seemed simple enough to implement.

Recursion

If one makes the distinction between computer scientists and computer engineers, one often finds that the scientists love recursion while the engineers are more skeptical.  To be sure, recursive algorithms often lead to elegant programs that are powerful, expressive, and succinct.  On the other hand, language implementations often impose practical costs on function call stacks that can grow very deep with recursion.  The engineers...ahem...are correct, of course!

Recursive algorithms are only safe when there is a finite and tolerable limit to the recursion.  In the case of Sudoku, there are only 81 positions on the game board to evaluate.  My implementation uses a recursive, brute force algorithm, and it runs without issue in the 8K of RAM that I'm currently allocating for the code and the stack.  It will probably run in half of that or even less, but I haven't tested to find out.

Load 'Em Up

A puzzle solver isn't of much use if it always solves the same puzzle.  On the other hand, writing a puzzle editor doesn't sound like much fun for the amount of effort involved.  What to do?  If only the CoCo came with some sort of built-in editing facility that could help with such tedious tasks...hmmm...

Rather than delving into the minutiae of building a Sudoku editor in C, I decided to let BASIC do the work for me.  I wrote a short BASIC program that first reserves space for the C program and loads that there.  The BASIC code then READs the Sudoku game setup from the included DATA statements and pokes that into memory where the C program can find it.  The puzzle can be changed by simply editing the DATA statements to reflect the new puzzle.  It would be hard to make things any easier, and IMHO it isn't worthwhile to do so.


Burlington Mini Maker Faire

Where I live, we have a little "maker club" called the Alamance Makers Guild.  Last year we held a mini Maker Faire at the local mall, and we will do so again this year on August 17, 2013.  At last year's event, Fahrfall made a good showing and at least some people seemed to enjoy seeing that and my video player for the CoCo3.  I think the Sudoku solver will make its public debut there this year, and I am planning to make a little contest out of it.  I'm thinking that I will challenge humans to see if they can solve a Sudoku puzzle before the CoCo can do it.  I might even make them edit the BASIC program with the Sudoku data themselves before they run it!  Well, it sounds like fun to me...

This seems like a high note on which to end this summer's Retrochallenge event.  I probably won't be doing much more technically on this project before the end of that event.  I do, however, plan to be back with a more reflective post as a wrap-up.  Until then, please do stay tuned...

Friday, July 26, 2013

Marking Time

It is time once again for another exciting update on my Micro-C for CoCo project.  It has been a busy week for me here in North Cackalacky!  Unfortunately for me, it has mostly been a "work" kind of busy...  Nevertheless, I have been able to make a little progress on my project.

Pak It In

Like many machines of it's era (e.g. the Atari 2600), the CoCo had the option of using software distributed on ROM cartridges.  The clever marketing folks at Tandy marketed this as "Program Pak" software...  In any case, there are advantages to this software format.  So, it might be nice to distribute compiled C programs the same way.

Relocating the compiled code to the ROM cartridge address space is the obvious first step.  An added twist is the question of where to put the variables.  Obviously, storing "variables" in ROM is of limited value.  Luckily, the Dunfield library already provides for allocating variables in a different address range from where the code resides.  Yet another variation of the startup code allows for selecting this configuration.


Many programs require the use of interrupts for proper operation.  But, handling interrupts requires machine-specific accommodations that aren't part of the standard C language.  Many compilers provide mechanisms for implementing interrupt handlers in C, and Micro-C is no exception.  Unfortunately, the default mechanism provided with the Micro-C package generates code to hook the 6809's interrupt vectors in a ROM image.  That is fine for use in an embedded system, but it won't work with the CoCo.

The CoCo ROMs redirect the interrupt vectors through a secondary set of vectors in RAM.  Using the stock Micro-C interrupt implementation as a guide for interfacing with the compiled code, I implemented a CoCo-compatible version.  My implementation uses a macro to output some inline assembly code in order to establish some code labels and to provide a 'trampoline' function.  The trampoline function calls the C interrupt handler and then uses an RTI instruction to resume normal operation of the CPU.  I also added some macros to make it easier to point the secondary interrupt vectors at the appropriate handlers in the C code.

Time Flies

One of the few timing sources on the CoCo is the ~60 Hz Vertical Sync (a.k.a. "Vsync") interrupt.  With the code described above I was able to build a simple clock program that keeps time by counting Vsync interrupts.  I also used an inline assembly macro to provide access to the SYNC instruction.  This allowed me to properly time a colorful border animation for the clock -- the border is timed to complete a loop in approximately 1 second.  Just for fun, I compiled the clock to run in the emulator as a ROM image.  Since I didn't bother to burn a physical ROM, I also re-compiled the clock as a BIN file to load through the cassette interface on a real CoCo.


If you experiment with running my clock demo, you will find that the CoCo isn't really a very good time keeper.  Keeping time by dead reckoning with an almost-but-not-quite 60 Hz timing source doesn't compete with the accuracy of a Swiss watch!  I toyed with a few drift compensation strategies, but so far all I've done is prove that programming the CoCo in C is every bit as much fun as it is to program one in BASIC or assembly... :-)

Anyway, I guess that is enough for now.  Only a few more days remain for the Summer 2013 Retrochallenge event.  I hope to make the most of them, but I suspect that in any case I will be working on this project well past the end of the competition.  Either way, I hope you will stay tuned!

Sunday, July 21, 2013

BASIC Instinct

As I was working on implementing a CoCo API comparable to what Color BASIC provides, I had a couple of realizations.  The first was that while such an API might be superficially familiar to some CoCo programmers, it wouldn't necessarily be a good API for anyone to use.  The other was that an API implementation wasn't actually as interesting as some other aspects of the project!

So for now, I'll leave the remainder of the API library work undone.  I may return to expanding the library later, but for now I want to hit a few more objectives.  In this episode, we will look at interfacing C programs to Color BASIC...

CLEAR Some Space

Once again we come to the problem of where to put a program in the CoCo's memory space.  This is similar to what we faced before, except that now we have to share the available memory with a BASIC program at the same time.  What needs to happen is for BASIC to give us some space to live and for it then to leave us alone.

Color BASIC is ready for us.  The CLEAR command allows us to influence how BASIC allocates memory, including the ability to set a limit on the highest address BASIC will use for its programs.  This allows a BASIC program to make room for us before loading and executing our program.

Corresponding to that, I created options in the startup code to allow the C programmer to specify what CLEAR value is being used.  This causes the C program to be compiled to run in the proper space and to allocate memory appropriately.  More importantly, it provides us an open field in which to run without worrying that we might trample on something important to our BASIC program.


CoCo programs that don't interact with BASIC don't have any way to accept anything like a 'command-line argument', so there has been no need to worry about that until now.  BASIC doesn't offer C programs a command-line either, but there are ways to pass information to our C program if we so desire.  In fact, perusal of the Color BASIC documentation reveals that there are a variety of options for passing information both into and out of C programs.

Lacking a single path to follow, I implemented a variety of options in the startup code.  These correspond to the documented options for Color BASIC to pass information to a 6809 machine language program, and they require certain variations to the 'main' declaration in the C program.  Some of those options require data structures that are foreign to anything resembling standard C, so I also knocked together a header file to describe the various data structures involved.  I posted that header file and some sample prefix files that set options for the startup code, if anyone is interested.


The Color BASIC documentation had another interesting point -- the stack provided by Color BASIC is only good for about 30 bytes of usage.  It wouldn't take many levels of function calls with arguments pushed onto the stack to burn-up that little amount of space!  Not only that, but the Micro-C library's implementation of malloc presumes that the stack is at a higher address than the heap.  The memory provided by the CLEAR command is at a higher address than the Color BASIC stack, so malloc won't work with it.

The answer is simple enough -- allocate a new stack at the top of RAM.  Of course, in order to return to the calling BASIC program the Color BASIC stack pointer has to be saved at program entry and restored at program exit.  A few more simple modifications to the library startup code accomplished this task without incident.

So, now we can produce CoCo programs written in C that either stand alone or which can fully cooperate with programs written in BASIC.  Things are coming together nicely!  There is only a little more than a week left in the Summer 2013 Retrochallenge event.  Do you want to see what comes next?  Then I guess you'll have to stay tuned!

Monday, July 15, 2013

Know Your Compiler

We've reached the half-way point for the 2013 Summer Retrochallenge event!  I would, of course, like to be further along with my Micro-C/6809 support package for the CoCo.  But, overall, I think the project is making good progress.  Over the weekend I posted about my success at getting some initial routines implemented, and I was able to show a simple low-res graphics program running.  In the process, I have learned a bit more about how that compiler works and how best to make use of it.

Cast Away

When I was implementing a routine to compute the address for a byte of graphics data, I discovered an anomaly.  I initially tried to use an expression that added a computed value to a constant offset, but found that the resulting value was incorrect.  Surprisingly, separating the addition of the computed value into a different line from the initial assignment of the offset value resulted in a correct result.  Reviewing the generated code showed that the non-working case was adding a 16-bit constant to an 8-bit register -- oops!

Compilers often have quirks, and "small" compilers often have some weird ones.  I suspected that I might have been hitting one of those, so I reviewed the docs that came with Micro-C.  The docs revealed that due to performance considerations (i.e. a preference for 8-bit operations), untyped constants used in an expression with 8-bit types are treated as 8-bit values.  I can't help but think that this sort of situation begs for throwing a warning at compile time, but alas it did not.  Anyway, adding an explicit typecast to a 16-bit type prompted the compiler into generating working code.

Optimism

As I was rooting around in the code generated by the compiler, I noted some oddities.  The code was doing some weird things, like a register store to memory followed immediately by a load from that same memory location to the exact same register.  This sub-optimal behavior reminded me that I was not telling the compiler to run the optimizer.  So, I added the "-o" option to the invocation of cc09 and observed many improvements to the generated code.

When running the test code built without optimization, I observed that the program didn't run significantly faster than the BASIC program upon which it was based.  I originally surmised that the slow speed was the result of including a keyboard scan inside the "blinking" loop.  However, the optimized code was easily observed to run much faster than the non-optimized code!  Maybe compiled languages really are faster... ;-)

Handiwork

The expression in question included a combination of multiplication and division by powers of two, which I recognized could be implemented with logical operations like masking and shifting.  I observed that even with optimization enabled, the generated code was still using multiply and divide operations to compute that expression.  A more modern compiler might be expected to recognize this situation and to use the logical operations instead, but the "peephole" optimizer included with Micro-C doesn't make the connection.

In order to squeeze out a little more performance, I re-implemented the expression using logical operations in the C code itself.  This generated the code as expected, and a modest performance gain was observed with the test program.  Sometimes you just have to take matters into your own hands!

I'll make a study of the generated code available for those interested in such things.  Next time I'll probably move onto implementing some solutions for better integration with BASIC...or maybe I'll do something else...  Anyway, I guess you'll have to stay tuned to find out!

Saturday, July 13, 2013

Set, Reset, Point

Another week passes with limited progress on my Retrochallenge project.  My day job has been keeping me busy lately.  So, I've been working for the weekend! :-)

BASIC Functionality

I wasn't sure where to start on designing an API for the CoCo.  So for now, I've decided to punt by simply mimicking the commands provided by the CoCo's built-in BASIC programming environment.  I won't attempt to transform C into BASIC with implementations of MID$ and the like.  But, I will try to implement some of the machine-specific commands for graphics, sound, and the like.

With that said, I have begun by implementing the simplest suite of graphics commands.  On the CoCo, this is provided by the set, reset, and point operations for turning pixels on and off and querying a pixel's status on the "semi-graphics" (i.e. VDG mode SG4) screen.  Since that mode allows for mixed text and graphics, I also included routines for clearing the screen and for positioning the text cursor.

Parsing Anomaly?

A funny thing happened on the way to the forum...  While implementing the code to calculate the addresses used in the graphics routines, I discovered that the calculation was producing incorrect results.  To debug that situation, I deconstructed a complex statement into multiple simpler statements.  To my surprise, the calculation then produced the correct results!

I still don't see what difference exists between those implementations that could explain why one performs correctly and the other does not.  Sometimes compilers (particularly "small" ones) have some idiosyncrasies, and the Dunfield compiler is no exception.  I'll have to dig back through the documentation to see if I am hitting one of those cases.  On the other hand, I may simply have done something wrong.  I would welcome anyone who is interested to look at the code in _getpos and to let me know if they see the difference.


Slow Ride

The program running in the video is a C implementation of a program from page 128 of Getting Started with Extended Color BASIC.  As I commented in the video, the C program doesn't seem to run any faster than the original BASIC program.  The difference is that the C program checks for keyboard input after each "blink", while the BASIC program just loops with a GOTO and has to be stopped by pressing BREAK.  If you remove the keyboard check in the C program, the blink is more like a fast flicker.

I would guess that the same keyboard scan routine is called in either case, with that fact hidden in the case of the BASIC program.  The keyboard scan in the ROM does a lot of work, and that work takes time.  Hopefully the speed penalty demonstrated with the C program calling the ROM routine illustrates that simply coding a program in a compiled language is insufficient to guarantee improved performance.

I had a lot of fun working on this today.  Hopefully I can get some chores done and find more time to work on this tomorrow!  If you want to see what comes of that, then I guess you'll have to stay tuned...

Sunday, July 7, 2013

Small Steps

Well, I'm still trudging along on retargeting Micro-C for the CoCo.  As with any project, the fundamentals must come first!

The docs from the Micro-C package covered how to run the tools, what they do, etc.  The key to targeting a specific system is to port the included library, lib09, to the target system.  This is described in the readme.txt file under the lib09 directory.

Location, Location, Location

First and foremost, the decision must be made as to where the code will live in the CoCo's memory.  This location might be anywhere, but realistically it needs to be somewhere in RAM.   Ideally the code will also be located somewhere that won't interfere with Color BASIC, or at least somewhere that allows Color BASIC to load our programs.

There are a number of considerations that might influence this choice.  These include how one intends to load programs, what limits one might impose on the size of programs, what level of cooperation one might want to have between C and BASIC programs, etc.  For now, I'm going to shoot for loading under Disk Extended Color BASIC (i.e. DECB) and I'm not going to worry about cooperation between C and BASIC at runtime.  Being familiar with how DECB uses memory on the CoCo, I have chosen to load C programs at address $0E00 and to set the initial stack pointer to $8000 at program entry.  At program exit, the CPU reset vector at [$FFFE] will be executed.

Console I/O

The lib09 file called serio.asm implements the basic operations for reading and writing text, one character at a time.  The default implementation targets a 6551 ACIA, commonly used for RS-232 implementations on 6809-based machines of a certain era.  In fact, that would work great if we only wanted to use the Tandy Deluxe RS-232 Pak.  But, I think it would be better to write to the video screen and to read from the keyboard... :-)

Fortunately, Microsoft included ROM routines in Color BASIC for just this purpose.  The CHROUT routine handles screen output, including basic scrolling.  The POLCAT routine handles scanning the keyboard.  I implemented routines in serio.asm that used CHROUT and POLCAT in place of the example 6551-based routines.

File Format

The S-record file output by the Micro-C tools isn't directly usable by the CoCo.  The hex values need to be translated to the equivalent binary values, and both header and footer data need to be added to tell DECB where to load the program and how to execute it.  A little cleverness with ORG, FCB, and FDB statements in the lib09 prefix and suffix files tricks the Micro-C tools into generating the header and footer data required by DECB.  Translating the file into binary requires another utility.

Older versions of the Dunfield tools included a utility called hexfmt that could translate between S-record files and pure binary files (among other things).  I can't seem to find this file for download on the Dunfield site right now, but I might be overlooking it.  (It seems to be included in the Z80 cross assembler package here.)  On Linux the objcopy utility can also do such conversions.


Achievement Unlocked

With the fundamentals covered, I am now free to move onto library enhancements, better cooperation with Color BASIC, etc.  I also plan to go into a bit more detail on the wonders of MON09.  Of course, to see that you will have to stay tuned... :-)