just one more geek in a sea of austin techies

March 11, 2012

Me, an Apple III and programming the 6502 #CodeGeek

Way, way back -- back when I was a grade school kid with plenty of free time, my father brought home an Apple III computer.  Although I'd previously tinkered with a loaned Sinclair ZX80, the Apple was the first computer that was ours (er, mine!)  My father's company had moved to using Apple III and Lisa systems and, always the forward-thinker, he was determined to have the same capabilities at home.  Though unintended, that decision determined my own life's direction...

The Apple III (yes, there was a "III")
The Apple III was the first "modern" PC targeted for business.  "First for business" because its May, 1980, release predated the IBM PC 5150 by more than a year and "modern" due to the fact that the OS was not stored in firmware but was disk-based.  The Apple III featured the "Sophisticated Operating System" a.k.a. "SOS" -- a very unfortunate name as the Apple III initially suffered from a number of design flaws.  One flaw translated to an exceedingly high failure rate of it's built-in floppy disk drive which, incidentally, was the drive you were required to load the OS from (ouch!).  Improvements were made with a relaunched Apple III and an eventual Apple III+.  Still, while Apple moved upwards of 6 million Apple II-series systems, only around 125,000 Apple III-series were ever sold.

Design issues and poor sales aside, our family's Apple III worked perfectly for many years -- more than enough time to set me on the software development path.  In the 4th grade I began teaching myself Apple Business Basic because games cost too much so I decided to make my own.  Before long I discovered the Apple II+ emulator which greatly widened my options and access to relevant programming information. Monthly issues of SoftTalk magazine delivered techie info I would not have otherwise discovered as programming books were too pricey for my $5 weekly allowance.  Occasionally I'd manage to get my hands on a coveted Beagle Bros poster and gleam bits of peek and poke goodness from memory maps and sample code.  Before long I'd forgotten all about making games -- I found that I was happy making anything.

Assembly language and the 6502
By 7th grade I had moved up to assembler programming for my system's emulated 6502 (see a sweet 6502 JavaScript-based emulator here).  Apple Basic was too slow or too limited for many of the features I wanted to implement.  It made no sense to purchase and learn another language when I had free, direct access to the assembler.  Thankfully there was no one around to tell me that a 7th-grader had no real business mucking about with assembly language.

The following year I met a kid newly moved to town and in need of friends.  He was a fellow band geek and followed the same class schedule I did.  It didn't take me long to spot the circuit diagrams he often carried around -- I struck up a conversation.  He was a Commodore kid but we still managed to find common ground and eventually collaborate on code.  I had written a modest graphic editing suite for Apple II systems.  My editor's forte was the manipulation of images such as tweaking colors, moving/copying selections around the screen and the "Holy Grail" of Apple II graphics: typing text directly onto the graphics page.  I'd spent the better part of a year developing the various aspects of the suite.  My new friend ported much of the functionality to the Vic20 in under a month (*grrrr*).  Armed with both Apple and Commodore versions of the same software, we set our minds to the task of importing/exporting our images between our disparate systems.  

Creating a Graphic File Standard
The issue of sharing images between systems was that the Apple II had a very odd way of mapping graphic data.  In short, contiguous bytes in memory did not fully correlate to contiguous pixels on the screen.  By contrast, Commodore systems were very programmer-friendly in terms of graphics (and sound).  Still, there were no real agnostic, open-source image file standards at the time.  My 8th grade friend and I had to come up with our own standard.

The first attempt was simple:  get the graphic data from the Apple and put it into visually-contiguous byte order for the Commodore.  The Apple had a lower resolution so we elected to give Apple images a black border on the Commodore and to clip Commodore images on the Apple.  This approach worked *but* the amount of data was very large. I had no modem for my Apple and the Apple and Commodore disk formats were not compatible.  Instead of electronic transfer, I printed the data via our Epson JX-80 dot matrix printer (and Grappler adapter) and my friend typed it all in.  The proof-of-concept worked but we obviously needed a more efficient system.

Before worrying over the programming involved with modem-based communication, I concentrated on being more efficient with my data.  I eventually had two big realizations:
  1. Compression:  In many cases side-by-side bytes were copies of each other.  That is, given that a byte represents a single pixel of a single color, there is an excellent chance that the next byte will represent a pixel of the same color.  Instead of recording graphic data byte-by-byte, it is much more efficient to record the color value of the byte along with the number of times the byte should be repeated.

    My 8th grade mind had just invented Run-Length Encoding (RLE).  Brilliant!  Except that RLE is the most simple form of compression and had been used in countless ways long before I ever pondered the mysteries of efficient data storage.  Still the approach did much to reduce the size of our data sets though I never actually managed to talk my friend into typing in another complete data set, compressed or no.  Thereafter he opted to validate only the first 20% of data and call it a success.

    We went a step beyond byte-level compression and graduated to bit-level compression which opened up pattern-matching to the most granular level possible.  The switch to bit-level RLE resulted in even better compression.

    This was great but I still had one more notable realization before the end of my 8th grade year...
  2. Understanding Nature:  When examining images and looking for visual clues on how to better compress data I had a graphic-pattern epiphany:  bits of objects tend to repeat more often in a vertical direction than in a horizontal direction.  I had been compiling my RLE data using "runs" of bytes moving from left-to-right since this horizontal movement matched the order of bytes in memory.  However, if I wanted my "runs" to be as long (efficient) as possible, I needed to order the bytes vertically instead of horizontally.

    Reviewing the following example photos it's easy to see that pixels/colors tend to repeat a bit more often from top-to-bottom than from left-to-right:

    Purple coneflower   Seed Collecting
    North Shore    Jack ladder carry red pine logs to the head saw - Bailey Lumber Co
    dune    Specticle Reef Lighthouse Straits of Mackinac

    Changing the direction of my encoding meant major changes to my RLE compilation code.  No longer was I tackling bits spanning contiguous bytes (left-to-right).  My existing assembler routine would be of little use.  As a quick proof-of-concept, I turned back to Apple Basic and utilized an XOR function with collision detection to determine how a specific pixel was set. This method was slow but it was simple and it worked.  Thanks to the XOR operation you would also see a visual indicator of the progress of the scan.  The proof-of-concept confirmed that RLE compression for graphic images was generally better top-to-bottom than left-to-right.  Writing an assembler version of my top-to-bottom scan would take care of the speed issue.   Also, since I would then have both horizontal and vertical scanners, I could scan both ways, pick the more efficient result and simply add a meta-data header value to the result set defining the direction of RLE encoding.  Better and better!
Except... that's where the story ends.  8th grade gave way to high school.  Suddenly I had many new, exciting things to get involved with, a new level of freedom and a mother who was worried sick that her son would develop no social skills spending countless hours in front of a computer.  She was right.  At the time I was so deeply focused on programming that I thought of little else.  My eventual ability to occasionally attract girls would have been seriously jeopardized if I'd been allowed continue as I had through my junior high years.

I do wonder, though, what might have become of our graphic suite project if 8th grade could have somehow lasted one more year.  And -- packed away but not forgotten -- I still have that big, beautiful beige box responsible for launching my tech career and guiding me to my adopted home of Austin, Texas.

No comments:

Post a Comment