Was the design of MS-BASIC for 6502 based on MS-BASIC for 8080?

Question

Looking through the source code of the 6502 MS-BASIC, certain parts of it seem more reminiscent of how things would be done on the 8080 than on how they should be done on the 6502. Code to find a line with a specified number, for example, is relatively performance-critical, but Bill Gates' code seems less than optimal:

FNDLIN: LDWX    TXTTAB      ;LOAD [X,A] WITH [TXTTAB]
FNDLNC: LDYI    1
        STWX    LOWTR       ;STORE [X,A] INTO LOWTR
        LDADY   LOWTR       ;SEE IF LINK IS 0
        BEQ FLINRT
        INY
        INY
        LDA LINNUM+1    ;COMP HIGH ORDERS OF LINE NUMBERS.
        CMPDY   LOWTR
        BCC FLNRTS      ;NO SUCH LINE NUMBER.
        BEQ FNDLO1
        DEY
        BNE AFFRTS      ;ALWAYS BRANCH.
FNDLO1: LDA LINNUM
        DEY
        CMPDY   LOWTR       ;COMPARE LOW ORDERS.
        BCC FLNRTS      ;NO SUCH NUMBER.
        BEQ FLNRTS      ;GO TIT.
AFFRTS: DEY
        LDADY   LOWTR       ;FETCH LINK.
        TAX
        DEY
        LDADY   LOWTR
        BCS FNDLNC      ;ALWAYS BRANCHES.
FLINRT: CLC         ;C MAY BE HIGH.
FLNRTS: RTS         ;RETURN TO CALLER.

The code uses a lot of INY and DEY instructions, even though the value of Y at any given spot in the code will always be the same; using an LDY #1 rather than DEY at AFFRTS would have allowed BEQ FNDL01 / DEY / BNE AFFRTS to be replaced with BNE AFFRTS. Further, INY INY could be cheaply replaced with LDY #3 and eliminate the need for the preceding LDY #1. Further, the use of X:A to hold a temporary high/low address foregoes the possibility of using (ind,x) mode [with x set to zero] which could help eliminate some of the gymnastics with Y.

On the other hand, if the code was based on a reworking of a similar algorithm on the 8080, the use of INY/DEY could make sense since the effects would be analogous to incrementing or decrementing HL on the 8080. On the 8080, code could rather efficiently do something like:

; Using Z80 mnemonics for 8080 opcodes
loop:
    ex      de,hl
start:
    ld      e,(HL)  ; Fetch link LSB
    inc     HL
    ld      d,(HL)  ; Fetch link MSB
    inc     HL
    ld      a,c     ; Line number LSB
    sub     a,(HL)
    inc     hl
    ld      a,b     ; Line number MSB
    sbc     a,(HL)
    jc      lp

For the 6502, a more efficient approach would be to have each line preceded by a length byte, allowing something like:

start:
     lda     linNum+1
     sta     lnTemp
     ldy     #2
     ldx     #0
loop:
     lda     (ptr),y
     cmp     lnTemp   ; Carry clear if looking for < what's there
     bcs     oddBall
     lda     ptr
     adc     (ptr,x)
     sta     ptr
     bcc     loop
     inc     ptr+1
     bcs     lp       ; Carry still set from before
oddBall:
     bne     notFound
     lda     lnNum    ; Do other byte of line # if we haven't yet
     sta     lnTemp
     dey
     bne     loop     : If not equal, we need to do LSB of line #
     clc
notFound:
     rts

Only 25 cycles per line in the common case, with an extra 7-8 cycles on each page crossing (depending upon whether the lda(ind),y crossed a page). So about twice as fast as the original code. This code would rely upon the 6502's ability to directly access two addresses relative to (ind) without having to manipulate any index registers, which is something the 8080 couldn't do, but exploiting that ability could have made things much faster. Further, it benefits from the fact that adding an 8-bit value to a 16-bit pointer is much faster than loading a 16-bit value.

Does the 8080 BASIC use routines which largely mirror the logic of the 6502 versions, thus suggesting that the 6502 was strongly derived from it? Or was Bill Gates simply following the coding style of a processor other than the 6502 (perhaps an 8080, or maybe PDP-10 or something else)?

Answer 1

I've seen a number of articles, such as this one which states it was based on 8080 BASIC, and this one which states that 8080 BASIC was first ported to the 6800, which was translated to the 6502. It would make sense to take the methods used in 8080 BASIC and use them on other processors.

Answer 2

Yes, Microsoft 6502 BASIC was clearly a port of their 8080 BASIC.

Unfortunately the original 8080 source code for Microsoft BASIC isn't easily available, so we can't compare it directly to that without going to the Harvard University library to read the paper copy.

But the Microsoft source code for a later version of their 8080 BASIC, BASIC-80 5.2 (actually marked 5.11 in the source) is available online. This is copyright 1982 (from the copyright notice in INIT.MAC), but contains material obviously from the original 8080 source code, such as the following comment in BINTRP.MAC:

;--------- ---- -- ---- ----- --- ---- -----
;COPYRIGHT 1975 BY BILL GATES AND PAUL ALLEN
;--------- ---- -- ---- ----- --- ---- -----
;
;ORIGINALLY WRITTEN ON THE PDP-10 FROM
;FEBRUARY 9 TO  APRIL 9 1975

Comparing this with the 6502 source code we see substantial similarities in the overall organization of the code and almost exact correspondence of many routines within it.

START and INIT

For example, the entry point in both versions is at address 0 and contains JMP INIT; in both cases the INIT routine overwrites the target of this JMP with the address of a routine called READY that does a "warm start". After that there are a couple of words storing the addresses of routines to convert a floating point number to an integer and vice versa.

Here's the 8080 version from 1982:

        PUBLIC  START
START:
        PUBLIC  JMPINI
JMPINI: JMP     INIT                    ;INIT IS THE INTIALIZATION ROUTINE
                                        ;IT SETS UP CERTAIN
                                        ;LOCATIONS DELETES FUNCTIONS IF
                                        ;DESIRED AND
                                        ;CHANGES THIS TO JMP READY
                                        ;WARM START FOR ISIS
                                    ;OF THE ROUTINE TO CONVERT [A,B]
                                    ;TO A FLOATING POINT NUMBER IN THE FAC
    DW      FRCINT                  ;TURN FAC INTO AN INTEGER IN [H,L]
    DW      MAKINT                  ;TURN [H,L] INTO A VALUE IN THE FAC
                                    ;SET VALTYP FOR INTEGER

And the 6502 version from 1978:

START:  JMP     INIT            ;INITIALIZE - SETUP CERTAIN LOCATIONS
                                ;AND DELETE FUNCTIONS IF NOT NEEDED,
                                ;AND CHANGE THIS TO "JMP READY"
                                ;IN CASE USER RESTARTS AT LOC ZERO.
RDYJSR: JMP     INIT            ;CHANGED TO "JMP STROUT" BY "INIT"
                                ;TO HANDLE ERRORS.
ADRAYI: ADR(AYINT)              ;STORE HERE THE ADDR OF THE
                                ;ROUTINE TO TURN THE FAC INTO A 
                                ;TWO BYTE SIGNED INTEGER IN [Y,A]
ADRGAY: ADR(GIVAYF)>            ;STORE HERE THE ADDR OF THE
                                ;ROUTINE TO CONVERT [Y,A] TO A FLOATING
                                ;POINT NUMBER IN THE FAC.

STROUT

Another example is the STROUT routine, which clearly works in the same way, modulo the differences in processor architecture, and even has some comments that are nearly identical. Here's the 8080 version:

;
; PRINT THE STRING POINTED TO BY [H,L] WHICH ENDS WITH A ZERO
; IF THE STRING IS BELOW DSCTMP IT WILL BE COPIED INTO STRING SPACE
;
STROUI: INX     H                       ;POINT AT NEXT CHARACTER
STROUT: CALL    STRLIT                  ;GET A STRING LITERAL
;
; PRINT THE STRING WHOSE DESCRIPTOR IS POINTED TO BY FACLO.
;
STRPRT: CALL    FREFAC                  ;RETURN TEMP POINTER BY FACLO
        CALL    GETBCD                  ;[D]=LENGTH [B,C]=POINTER AT DATA
        INR     D                       ;INCREMENT AND DECREMENT EARLY
                                        ;TO CHECK FOR NULL STRING
STRPR2: DCR     D                       ;DECREMENT THE LENGTH
        RZ                              ;ALL DONE
        LDAX    B                       ;GET CHARACTER TO PRINT
        CALL    OUTDO
        CPI     13
        CZ      CRFIN
        INX     B                       ;POINT TO THE NEXT CHARACTER
        JMP     STRPR2                  ;AND PRINT IT...
        PAGE

And here's the 6502 version:

;
; PRINT THE STRING POINTED TO BY [Y,A] WHICH ENDS WITH A ZERO.
; IF THE STRING IS BELOW DSCTMP IT WILL BE COPIED INTO STRING SPACE.
;
STROUT: JSR     STRLIT          ;GET A STRING LITERAL.
;
; PRINT THE STRING WHOSE DESCRIPTOR IS POINTED TO BY FACMO.
;
STRPRT: JSR     FREFAC          ;RETURN TEMP POINTER.
        TAX                     ;PUT COUNT INTO COUNTER.
        LDYI    0
        INX                     ;MOVE ONE AHEAD.
STRPR2: DEX
        BEQ     PRTRTS          ;ALL DONE.
        LDADY   INDEX           ;PNTR TO ACT STRNG SET BY FREFAC.
        JSR     OUTDO
        INY
        CMPI    13
        BNE     STRPR2
        JSR     CRFIN           ;TYPE REST OF CARRIAGE RETURN.
        JMP     STRPR2          ;AND ON AND ON.

PTRGET

Even routines that are different due to feature changes are pretty clearly derived from common original source. For example, the PTRGET routine that that reads a variable name and fetches its value uses a pair of zero-page memory locations in the 6502 version to store the variable name, which is limited to two characters in that older version of BASIC. The newer 8080 code allows up to 40 characters in a variable name, but still stores the first two characters of the name in the C and B registers (memory was used in the 6502 because it has far fewer registers) and compares those first, only moving on to a further comparison with the rest of the name in a memory buffer if that fails.

And of course there's the similarity in the comments and routine name itself. The 8080 version:

; ROUTINE TO READ THE VARIABLE NAME AT THE CURRENT TEXT POSITION
; AND PUT A POINTER TO ITS VALUE IN [D,E]. [H,L] IS UPDATED
; TO POINT TO THE CHARACTER AFTER THE VARIABLE NAME.
; VALTYP IS SETUP. NOTE THAT EVALUATING SUBSCRIPTS IN
; A VARIABLE NAME CAN CAUSE RECURSIVE CALLS TO PTRGET SO AT
; THAT POINT ALL VALUES MUST BE STORED ON THE STACK.
; ON RETURN, [A] DOES NOT REFLECT THE VALUE OF THE TERMINATING CHARACTER
;
PTRGET: XRA     A                       ;MAKE [A]=0

And the 6502 version:

; ROUTINE TO READ THE VARIABLE NAME AT THE CURRENT TEXT POSITION
; AND  PUT A POINTER TO ITS VALUE IN VARPNT. [TXTPTR]
; POINTS TO THE TERMINATING CHARCTER.. NOT THAT EVALUATING SUBSCRIPTS
; IN A VARIABLE NAME CAN CAUSE RECURSIVE CALLS TO "PTRGET" SO AT
; THAT POINT ALL VALUES MUST BE STORED ON THE STACK.
;
PTRGET: LDXI    0               ;MAKE [ACCX]=0.

Comparison with Other Object Code

Though we don't have original source for an 8080 version of Microsoft BASIC from the same era as the 6502 source, we do have binaries that can be disassembled. Comparing this disassembly of Altair BASIC 3.2 we can also find substantial similarities in the code (including all the routines mentioned above), though of course there are no comments to compare.

I myself have been working on a disassembly of the 6800 BASIC that Microsoft wrote for the Altair 680B after they'd written the 8080 basic for Altair's 8800 but probably before they started the 6502 version. Both ports were done by Ric Weiland, and again the 6800 version shows the same substantial similarities in code organization and the details of how the particular routines work.

Answer 3

Bill Gates and/or Paul Allen likely did not write the 6502 version of Basic. Marc McDonald, one of the very first Microsoft employees, is reported (on the Wikipedia page for Applesoft BASIC, for instance) as having written the 6502 version of Microsoft Basic. But he would have had access to all the source code to Gates and Allen's 8080 BASIC, as well as the same DEC computer on which to run a cross-assembler.

Answer 4

The original Altair BASIC came in three versions; 4k, 8k and Extended. The numbers referred to the amount of RAM required to run it, as BASIC was loaded to RAM from paper tape. The 4k version running in 4k of RAM had a whopping 790 bytes free.

The 4k and 8k versions used a 4-byte (6-digit) floating point format. The 4k version lacked string variables and some other less important features. The 8k version added strings, some more math functions, and peek and poke. Extended added a "double precision" floating point format. I think the double was actually the 6-byte (9-digit) format found in later 6502 versions, but I'm not sure.

UPDATE: the double-precision system was a 64-bit format. The 40-bit format became the standard during the 6502 port, largely replacing both earlier formats.

I suspect, as you do, that the code was deliberately "copied" as much as possible with an eye to ease of porting rather than code size or performance. New processors were popping up continuously, and tuning for each one would not only be difficult but ultimately fruitless as some of these would be doomed to die. Like the 6800.

BTW, supercat, are you playing with the source in your own versions?