16

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, then on how they should be done on the 6502. Code to find a line with a specified number, for example, is a 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)?

  • 4
    They certainly made their 6502 assembly syntax as close to 8080 syntax (or at least their own 8080 syntax) as they could. Hard to say how much the 6502 source copies from the 8080 source without having them side by side to compare though. It doesn't look machine translated though. – Ross Ridge Oct 28 '17 at 18:37
  • 1
    @RossRidge: It certainly wasn't machine translated. On the other hand, someone who is familiar with the 8080 machine code [I don't think the source exists] might be able to say whether the structure bears any similarity to the 6502 version. If I were designing a BASIC interpreter from scratch for the 6502, I'd prefix lines with the length, and might store the characters of each line--as well as the characters of strings--in reverse order. Adding two to the address of a line (to skip over the line number) before executing would then allow code to notice the end of a line via "dey / bne". – supercat Oct 28 '17 at 18:43
  • 1
    The source code for the original 8080 version exists, but not online, you need to go a Harvard library to read it: theregister.co.uk/2001/05/13/raiders_of_the_lost_altair You can find the annotated disassembly the article refers to pretty easily on the web. – Ross Ridge Oct 28 '17 at 19:12
  • 1
    @RossRidge: Interesting article. After reading it, I looked for and found the aforementioned disassembly. The "find program line" function for the 6502 does somewhat resemble how the code could have been written on the 8080, but not how it actually was written. The code reads the next-line link (two bytes) for purposes of checking against zero, without saving it anywhere, then decrements HL back to where it was so it can call a function to push (HL) and (HL+1) while incrementing HL twice. Maybe that saved a byte or two of code, but in exchange for a huge speed penalty. – supercat Oct 28 '17 at 20:45
  • 2
    @RossRidge: I wonder if Gates and Allen suffered from "If all you have is a hammer, everything looks like a nail" syndrome. Memory-copy loops are very important to a program's performance, but the loops within the interpreter could easily have been made twice as fast for a few bytes. Instead of calling CMPDEHL within the loop, compute bc=65536-#bytes, and then do ldax d/stax h/inx d/inx h/inc c/jnz lp/inc b/jnz lp. Sure RST vectors are cute, but they're not exactly speedy. – supercat Oct 28 '17 at 20:57
12

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.

  • 1
    Now I'm curious to see the 6800 code, but a google search isn't showing anything. I recall thinking that the Altair 680 seemed sluggish running BASIC even when using a 110-baud teletype. I wonder if the routines to move memory up and down make horrid speed/space trade-offs like on the 8080 version. – supercat Oct 28 '17 at 21:12
5

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.

1

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 6-byte floating point format. The 4k version lacked strings 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 9-byte format found in later 6502 versions, but I'm not sure.

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.

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

  • I'm not actively working on any BASIC interpreters, though I've toyed with some conceptual designs. The garbage-collector design leaves perhaps the most room for improvement. If strings were preceded by length (or any other byte which is guaranteed non-zero) and took up a minimum of three bytes, then on each GC pass where one had N bytes of contiguous storage available, one could relocate into that region all strings that were within an N-byte region elsewhere and observe the address of the string (if any) which crosses out of it. In most usage cases, the amount... – supercat May 18 '18 at 18:49
  • ...of free storage would grow significantly after each GC pass, making the process closer to O(NlgN) than O(N*N). A key point, though, would be that as the GC relocated each string it would be replaced with a relocation marker containing a zero byte and the new address. If the first byte of each string is the length, and zero-byte strings are represented as null pointers, this works out nicely. If strings aren't prefixed, however, this works out less well. – supercat May 18 '18 at 18:50
  • Do you know how the Altair 6800 BASIC did its memory-copy loops? The 6800 isn't amenable to doing anything very fast; I'd guess a self-modifying loop: lda extended / sta 0,x / inx / inc lsb_of_extended / inc b / bne loop" would be best, but wouldn't be at all surprised if the BASIC does something like ldx src / lda 0,x / inx / stx src / ldx dest / sta 0,x / inx / stx dest`. I really don't see any good way to do things without using self-modifying code or trashing SP. – supercat May 18 '18 at 20:43
  • @supercat - I have never seen the original 6800 source, only the 6502 port. Your musings on strings are VERY interesting to me. I am not an assembly programmer, but I have collected ideas wide and far that seem to present the possibility of major performance improvements to the 6502 code. I'm adding yours! – Maury Markowitz May 29 '18 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.