Doing it in less than Bill Gates. Loading Microsoft 4K BASIC on ALTAIR 8800 with Papertape

Two years ago, I demonstrated the loading of Micro-Soft's first software product on their first platform.  If you didn't already know, it was BASIC for the ALTAIR 8800 computer.  The story is well known in the vintage computer community.  It was a real success for Bill Gates and Paul Allen and they are nothing less than artists!

In preparation for the demonstration at World of Commodore 2014, I found there were multiple bootstrap programs.  It depended on hardware.  The manual has two, a 21 byte and a 20 byte version.  Over the course of a month, I studied the boot strap and tape in detail and found it really just loads another bootstrap program with better capabilities.  It may seem that 20 bytes is not a lot, but there should be a warning in the manual "fingers will get sore after repeated use of the small switches on the ALTAIR".  Further, each byte in turn lead to a greater probability of making an error.

The show went well, my friend Jeff Brown made a great video of the event "A re-tracing of how Paul Allen loaded BASIC on the MITS Altair 8800 from paper tape".  I really must thank him for the idea of loading 4K BASIC!  He saw my ALTAIR on a visit where we repaired his PET 2001 and suggested it.  After he released his youtube video, I stumbled upon another video called "Bill Gates talks about Microsoft and the Altair 8800".  At 3:26 into the video, Bill talks about the bootstrap loader and says Paul wrote the first loader in 46 bytes and he (Bill) later wrote it in 17 bytes.  I thought to myself, yes, 17 bytes is better than 20 bytes... especially if you are repeatedly demonstrating it.  I played with the idea of figuring out those 17 bytes then set out to make it as small as possible.  Well, that's when I got it down to just 14 bytes and now down further (with some encouragement) to 12 bytes!

Last summer, I acquired a Teletype ASR33 in working condition and decided it was time return to World of Commodore 2016 with a smaller bootstrap loader.  I narrowed what the bootstrap loader needs to work.
It needs to:

• initialize a memory pointer
• read a byte coming from the papertape
• load it to memory
• change the memory address
• loop back and repeat
• break out of this loop to execute the code

Well, Bill's code was pretty good and hard to beat, it used a stack to leverage smaller (shorter) instructions to reduce the byte count.  But I found 2 things that would save some steps (bytes).  The first was the way to break out of the loop, why not have the code written to decrement the memory pointer and let the code overwrite the bootstrap to break out.  The second save would be in how to determine if a byte was ready to read from the papertape.  Bill's bootstrap has to check for a status flag from the UART to indicate a new byte was shifted into the UART.  Well, if a new byte was NOT shifted into the UART, then the UART receive register would have the same byte that was previously there.  The trick is then simply to compare to the last byte saved to memory, and if it changed, then it would be understood that it's a new byte that is to be written.  The writes will then happen for all bytes that are different from the previous, so this now requires some extra "special coding" on the papertape.  Rule #1, no sequential bytes can be the same value.  Rule #2, we will not be guaranteed an absolute location in memory.  Of course, this means that the bootstrap loader cannot directly load 4K BASIC, but following in Bill's example, why not have the bootstrap load another bootstrap???  And since Bill's 20 byte bootstrap to load the 174 byte loader works, we can just load a program that will load that program.  **News Flash**, comments below suggested I re-evaluate some earlier work and now it's possible to do it in just 12 bytes!!! Without further adieu, here's the 12 bytes.

Octal
041     LXI   H,              ;Initialize Memory pointer to 0x01DB
333     IN 1                    ;Read UART data register (skip the status register)
001
276     CMP M              ;Compare with data stored at memory pointer
312     JZ 0001              ;Loop back if data is the same as stored
001
000
053     DCX H                ;When it's a different byte, decrement the memory pointer
167     MOV M,A          ;and save in memory
303     JMP 0001           ;Loop back for the next byte.
001
000

Now, you may notice, there's no way to break out of this loop, it will keep writing to memory until it overwrites itself... well that's great news!!!  The bytes targeted to overwrite the jump will be 01 or 00.  So, when the program finally gets overwritten the final jump will become JMP 0101 *OR* NOP
A long section of 00/01 is punched on the tape and these result in instructions that have no impact on program flow.  Next there are some instructions that align the PC in an unambiguous way and finally a section of code that simply stores Bill's original bootstrap to 0000, waits for the "AE" leader as required, then branches to 0000 to continue with the original bootstrap.

Since the nuked jump can be to 0101, the program to load the program must be after that point, which is fine because the memory pointer starts as 01DB, which happen to be the instructions to input port 1.

Also, the boot strap program could be shorten even further, but only with a significant hardware modification to wait for bytes in hardware.  The Tarbell 1101 Disk controller uses such a technique, hats off to Don Tarbell for a clever design!

That pretty much wraps up loading 4K basic with 5 bytes less than Bill.  It should be noted... at 110 baud, the extra papertape takes more time than it would take to switch in the extra bytes.  From start to finish, it takes about 9 minutes to load doing it Bill's way, and 10 minutes doing it my way.  But my way takes only 1 minute at the switches, while Bill's way takes 2 minutes.

Sincerely,
Josh Bensadon

A friend sent me this picture... why does Bill look so concerned?

My friend Walter (right) and me at WoC 2016.  ALTAIR and Teletype ASR33 in background.

My friend Jeff Brown (left) and me at WoC 2014.

Do two 8 bit machines stack up to a 16 bit machine?

-----------------------------------------------------------------------------------------------
The program to load the program on the papertape is....

Code to insert the original boot loader to 0000:  
56 BYTES. (38h) Plus 3 (since JUMP 0203)
Puts lowest starting address at 023B.

DB 01    IN 01
FE AE    CPI AE
C2 0201    JNZ 0102  LOOP BACK AND WAIT UNTIL TAPE LEADER
31 1400    LXI SP,0014
21 0300    LXI H,0003
E5    PUSH H
21 C0E9    LXI H,
E5    PUSH H
21 2D77    LXI H,
E5    PUSH H
21 BDC8    LXI H,
E5    PUSH H
21 DB01    LXI H,
E5    PUSH H
21 0FD8    LXI H,
E5    PUSH H
21 DB00    LXI H,
E5    PUSH H
21 1200    LXI H,
E5    PUSH H
21 0F31    LXI H,
E5    PUSH H
11 21AE    LXI D,  (Can't use H, 21 21 code repeats)
D5    PUSH D
        (Can't JP 0000, 00 code repeats)
21 0100    LXI H,0001
2B    DCX H
E9    PCHL    Jump to 0000


*** I punched a new tape for the 12 byte system and have tested it, works perfectly!  I must thank kgsws for encouraging me to go back to my notes and code it with one more trick.  The trick of reusing data bytes as instruction bytes ***