Elk: Assembly equivalent of simple BBC Basic

[MrGpG]

Hi all

In my attempt to bring some semblance of symbolic programming back into my teaching, I am using my Elks with KS2 and KS3. We have been programming using For / Next loops -- for example:

Code: Select all

   10 FOR x = 1 TO 100
   20   sum = sum + x
   30 NEXT
   40 PRINT sum

Now, I happened to mention "Assembly" and that this would compute quicker than in Basic. So "that kid" asked me to write the above in assembly -- clearly I can't as I never went there as a kid and stuck to Basic.

I can just about fathom the For/Next loop -- but the rest is alluding my 49yo brain.

Any pointers (or code) for the above in Elk Assembly?

Supplementary: Other than memory addresses (and hardware differences) is Elk Assembly the same as BBC / Master Assembly? They are all 6502 underneath...

Cheers
Glen

[Rich Talbot-Watkins]

That's an interesting little problem.

The first thing I would do, in BBC BASIC, is perhaps generalise it so that you can sum numbers up to 'n', like this:

Code: Select all

   10 PRINT FNsum(100)
   20 END
   30 :
   40 DEF FNsum(max%)
   50 sum%=0
   60 FOR x%=1 TO max%
   70    sum%=sum%+x%
   80 NEXT
   90 =sum%

Now a naive way to write that in 6502 assembly might be as follows (untested):

Code: Select all

   10 DIM code% 255
   20 result=&70
   30 max=&72
   40 FOR pass%=0 TO 2 STEP 2
   50 P%=code%
   60 [OPT pass%
   70 LDA #0:STA result:STA result+1
   80 LDX #0
   90 .loop
  100 INX
  110 TXA
  120 CLC
  130 ADC result:STA result
  140 LDA #0:ADC result+1:STA result+1
  150 CPX max
  160 BNE loop
  170 RTS
  180 ]
  190 NEXT
  200 :
  210 PRINT FNsum(100)
  220 END
  230 :
  240 DEF FNsum(max%)
  250 ?max=max%
  260 CALL code%
  270 =?result+256*result?1

But then the final step I'd probably take is the same one that modern compilers take, which is to notice that the whole thing is just an arithmetic sequence, and thus you can calculate the result without a loop at all!

Code: Select all

   10 PRINT FNsum(100)
   20 END
   30 :
   40 DEF FNsum(max%)
   50 =max%*(max%+1) DIV 2

[BigEd]

Crossed in the post but it took a little effort, so here's my take.

Yes, the assembly language in BBC Basic is the same from Beeb to Elk to Master.

If you were only looping up to 22, or less, then it would be easier, because there's only one byte needed for the sum.

Here's a trivial program to get started with.

And here's an attempt at the problem, using only single-byte values.

Here's my effort as text (supply your own line numbers):

Code: Select all

DIM var 4
DIM code 200
FOR i = 0 TO 3 STEP 3
P%=code
[
   LDA #0
   STA var   ; we'll accumulate into var
   LDX #1    ; X can be our index
   .again
   TXA       ; using A for arithmetic
   CLC
   ADC var   ; add to our running total
   STA var   ; and store back
   INX
   CPX #20+1 ; check our loop index
   BNE again
   RTS       ; we're done
]
NEXT
CALL code
PRINT ?var

[BigEd]

And here's one which should work for slightly larger numbers - it uses a one byte index and accumulates into a two byte result. Also fixes a bug or two in the earlier effort.

See also this manual (for example) and perhaps this tutorial.

The 6502 deals with 8 bit values almost exclusively, so you have to do more work to deal with 32 bit values. In assembly, you'd usually choose the smallest type you can to minimise the work.

[MrGpG]

The first thing I would do, in BBC BASIC, is perhaps generalise it so that you can sum numbers up to 'n', like this:

That's the way the lesson goes (eventually) - after a couple of session we talk about functions / procedures.

Now a naive way to write that in 6502 assembly might be as follows (untested):

Code: Select all

   10 DIM code% 255
   20 result=&70
   30 max=&72
   40 FOR pass%=0 TO 2 STEP 2
   50 P%=code%
   60 [OPT pass%
   70 LDA #0:STA result:STA result+1
   80 LDX #0
   90 .loop
  100 INX
  110 TXA
  120 CLC
  130 ADC result:STA result
  140 LDA #0:ADC result+1:STA result+1
  150 CPX max
  160 BNE loop
  170 RTS
  180 ]
  190 NEXT
  200 :
  210 PRINT FNsum(100)
  220 END
  230 :
  240 DEF FNsum(max%)
  250 ?max=max%
  260 CALL code%
  270 =?result+256*result?1

Will have a fiddle and see how I get on.

But then the final step I'd probably take is the same one that modern compilers take, which is to notice that the whole thing is just an arithmetic sequence, and thus you can calculate the result without a loop at all!

This is the final lesson - generalising via algebra -- but I was not aware that was potentially part of a compilation process.

Thanks for the pointers.
Glen

[MrGpG]

And here's one which should work for slightly larger numbers - it uses a one byte index and accumulates into a two byte result. Also fixes a bug or two in the earlier effort.

See also this manual (for example) and perhaps this tutorial.

The 6502 deals with 8 bit values almost exclusively, so you have to do more work to deal with 32 bit values. In assembly, you'd usually choose the smallest type you can to minimise the work.

Fantastic -- great pointers.

Most appreciated.

Now, to settle down for a couple of evenings of 6502 speak!

[RobC]

But then the final step I'd probably take is the same one that modern compilers take, which is to notice that the whole thing is just an arithmetic sequence, and thus you can calculate the result without a loop at all!

Code: Select all

   10 PRINT FNsum(100)
   20 END
   30 :
   40 DEF FNsum(max%)
   50 =max%*(max%+1) DIV 2

Indeed - as Gauss famously noticed aged 7 when given the same sum to solve!

[BigEd]

And there's von Neumann, who did the opposite...

(I'm not a teacher, but it feels to me that the point of this exercise is not to compute the answer, but to show your working: we need to learn assembly, which means labels, branches, storage, arithmetic, and so on.)

There are a few ways in which my submission misses a few tricks which are usually brought into play: most notably, that it's more natural to count down to zero than to count up to a target. But a more or less direct translation which is then improved might be good teaching. And if extending to the more Basic-like case of everything being 32 bits, an opportunity to have a couple of subroutines to handle the arithmetic.

[alex_farlie]

But then the final step I'd probably take is the same one that modern compilers take, which is to notice that the whole thing is just an arithmetic sequence, and thus you can calculate the result without a loop at all!

Code: Select all

   10 PRINT FNsum(100)
   20 END
   30 :
   40 DEF FNsum(max%)
   50 =max%*(max%+1) DIV 2

Indeed - as Gauss famously noticed aged 7 when given the same sum to solve!

or in a different language:

SUM [ DUP 1 + * 2 DIV ]

100 SUM .

I think, Or have I got the wrong syntax for defining and IO?

[nismo]

(I'm not a teacher, but it feels to me that the point of this exercise is not to compute the answer, but to show your working: we need to learn assembly, which means labels, branches, storage, arithmetic, and so on.)

Very true. I'm not a teacher either, but I do sometimes set interview questions. I always try and look for thought process rather than giving candidates an opportunity to be able to just churn out an answer by rote.

That's an interesting little problem.

It was indeed a very interesting problem! Haven't had to think in 6502 for a while so I decided to challenge myself to a little optimisation. Anyone else who's game please jump in and comment!

With that, I open myself to possibly severe criticism ( ) and present a full 32-bit version. Here's my thinking:

• Bounding the code's execution. Assumes the loop control variable X is a 32-bit unsigned integer and computes a 32-bit unsigned result. Returns an error if the result requires more than 32-bits.
• Error checking. I am fastidious about error checking and robust code. Often, though, thorough error checking can lead to good optimisation opportunities. In this case, the optimisation is knowing that anything more than 17 bits for the loop control variable X (in fact, X <= 92,681, or &16A09) will overflow a 32-bit result. This allows the manipulation of X in the main loop to be reduced to a 24-bit wide operation. Thus, any non-zero value for bits 31-17 of X is automatically failed as an overflow.
• Registerising bottom 16 bits of the loop control variable X. This was a fairly easy decision. Reduces two zero-page LDAs in the main loop to two immediate-mode register-to-register transfers, saving two clocks per iteration. As X is always having one subtracted from it (rather than any other number), decrement/comparison of X/Y registers to 255 is faster than using SBC via the accumulator even with the benefit of being able to test the carry flag on the result.
• Loop control variable X is counted down, not up. This removes, per iteration, a 24-bit comparison to X's upper bound. However, I don't compare X to zero to exit the loop; I exit on -1.
  Traversing the loop one more time only to add zero to the result may seem illogical. However, in addition to subtracting one from X which requires comparisons to 255 across 24-bits, an additional comparison of the X/Y registers to zero would yield at minimum an extra compare-zero/branch-test every iteration on at least the X register (total: 4 clocks). It is more performant in the general case to use the existing comparisons to 255 required during subtraction and exit at -1.
  The result of sacrificing a loop's worth of clocks adding zero to the final result (I make it 34 51 clocks...) saves potentially at least up to 370,724 clocks when X is a maximum (4 clocks/iteration x 92,681). On paper, the exit-at-minus-one implementation looks slower than an exit-at-zero implementation for X <= 12. For all other X it's faster, and at maximum X the speed-up might be visibly noticeable.

I think this is a fairly quick implementation. Possibly a bit cheeky in places... Thoughts?

Here's the code (tested over at https://bbcmic.ro/, but not tested on a real Electron).

Code: Select all

DIM srce 4, dest 4
DIM code 255
FOR I% = 0 TO 2 STEP 2
P%=code
[OPT I%
    LDA srce+3      \ no point checking anything above &1FFFF
    BNE overflow
    LDA srce+2
    AND #&FE
    BNE overflow
    STA dest        \ dest = 0
    STA dest+1
    STA dest+2
    STA dest+3
    LDX srce        \ YX = (srce AND &FFFF)
    LDY srce+1
.addition
    CLC             \ dest = dest + srce
    TXA
    ADC dest
    STA dest
    TYA
    ADC dest+1
    STA dest+1
    LDA srce+2
    ADC dest+2
    STA dest+2
    BCC loop
    INC dest+3      \ only 1 ever gets added to dest+4. sets Z on overflow.
    BEQ overflow
.loop
    DEX             \ srce = srce - 1
    CPX #255
    BNE addition
    DEY
    CPY #255
    BNE addition
    DEC srce+2      \ due to error checks on entry, srce+2 bit 7 is guaranteed
    BPL addition    \ to start off cleared. "N" flag signifies wrap to 255.
    RTS
.overflow
    BRK
    EQUB 10
    EQUS "Overflow"
    BRK
]
NEXT

INPUT "Upper bound", !srce
CALL code
PRINT "Result: &";FN_Hex(dest?3);FN_Hex(dest?2);FN_Hex(dest?1);FN_Hex(?dest)
END

DEF FN_Hex(value%)
IF value% > 255 THEN ="??"
=MID$("0123456789ABCDEF",(value%DIV16)+1,1) + MID$("0123456789ABCDEF",(value%MOD16)+1,1)

[BigEd]

Nice! You can do this instead:

Code: Select all

PRINT "Result: ";!dest;" (or in hex: ";~!dest;")"

A couple of ideas came up in the ABUG dev night when we talked about this situation - teaching the rudiments and advantages of assembly language.
- print a string such as "Hello" to illustrate ASCII and OS calls, and possibly straight line versus looping
- write the simplest possible pre-snake game to show interactivity and performance. (Use INKEY or OSBYTE&81 to check for 'D', increment an X and use VDU 31 to move the text cursor and print a character at a particular position.)

[nismo]

Nice! You can do this instead:

Code: Select all

PRINT "Result: ";!dest;" (or in hex: ";~!dest;")"

I knew there was something better on the BASIC side I could have done You know, my BASIC is so rusty that the Hex output function alone took about three times longer to write than the assembly routine itself!

Edit: the tilde trick strips leading zeroes, though. So I get a point there, right?

[BigEd]

Yes, showing leading zeros takes more effort. I think some STR$ and RIGHT$ can do it:

Code: Select all

PRINT RIGHT$("0000000"+STR$~(A),8)

[nismo]

Yes, showing leading zeros takes more effort. I think some STR$ and RIGHT$ can do it:

Code: Select all

PRINT RIGHT$("0000000"+STR$~(A),8)

Hmmm... My BASIC truly is rusty

[nismo]

A couple of ideas came up in the ABUG dev night when we talked about this situation - teaching the rudiments and advantages of assembly language.
- print a string such as "Hello" to illustrate ASCII and OS calls, and possibly straight line versus looping
- write the simplest possible pre-snake game to show interactivity and performance. (Use INKEY or OSBYTE&81 to check for 'D', increment an X and use VDU 31 to move the text cursor and print a character at a particular position.)

I think those kinds of concepts are a great place to start. Being assembly language, I think that the one area that tends to get skipped a lot is the importance of the flags register and how manipulating it properly can really make programs faster and smaller; two of the reasons why you would want to use assembly language over, say, BASIC in the first place.

[BigEd]

Another thing which could be illustrated is that putting lots of comments in your Basic will slow it down, whereas lots of comments in assembly code make no difference at all...

[nismo]

Another thing which could be illustrated is that putting lots of comments in your Basic will slow it down, whereas lots of comments in assembly code make no difference at all...

Ahh.. you've touched a point very close to my heart here. With C I'm always trying to extol the virtues of commenting ones intentions in the code rather than relying on the reader to understand supposedly "self-explanatory" code.

I learned my commenting style from the Acorn Electron User Guide and it comments virtually every single line. I've "optimised" my commenting style a little since then but I've always encouraged full commenting of C code as the same principle applies; what's compiled out doesn't affect performance so what's the point in being brief when it only makes it difficult for the next person...

[nismo]

But then the final step I'd probably take is the same one that modern compilers take, which is to notice that the whole thing is just an arithmetic sequence, and thus you can calculate the result without a loop at all!

Code: Select all

   10 PRINT FNsum(100)
   20 END
   30 :
   40 DEF FNsum(max%)
   50 =max%*(max%+1) DIV 2

You tempted me again! Feeling newly invigourated from my last escapade, I couldn't let this one off so lightly The result is further down.

In 6502 assembler, the crux lies in being able to multiply without a MUL-style instruction. It's done by right-shifting and adding based on fixed-width addition. For those not sure how this works, there is an excellent tutorial about it on page 221-225 of the Electron User Guide which is where I learned how to do it. The principle is that to multiply an N-bit number by an M-bit number you need (N + M) bits of space and either N iterations or M iterations, whichever way you want to do the multiplication.

This implementation has a fatter loop than the last implementation (maximum 74 clocks as opposed to 51 for the looped version). However, it always runs a constant 24 iterations which yields a bounded loop time of just 1776 clocks for 0 <~ X <= 92,681. The last implementation was around 4.7m clocks worst running time which was visible when you run it (51 x 92,681 clocks; over 2 seconds!). This new version is constant time and is instantaneous in comparison.

This new implementation is optimised for size. There is one place I could have unrolled it further for speed. However, doing so resulted in branch ranges being exceeded which meant a little more twiddling was required. I leave that as an "exercise for the reader"

Here's the code (again, tested at https://bbcmic.ro/ but not on a real Electron).

Code: Select all

DIM srce 5, dest 6
DIM code 255
FOR I% = 0 TO 2 STEP 2
P%=code
[OPT I%
    LDA srce+3      \ no point computing anything above &1FFFF.
    BNE overflow
    LDA srce+2
    AND #&FE
    BNE overflow
    STA dest+3      \ to multiply two 24 bit numbers we'll need 48 bits of
    STA dest+4      \ space. the result will be the bottom 32 of those 48 bits.
    STA dest+5      \ initialise upper 24 of those 48 bits to zero.
    LDA #24         \ use 24-bit counter at srce+4 to perform multiplication.
    STA srce+4      \ objective is to calculate !srce * (!srce + 1).
    CLC             \ set up YX = !srce AND &FFFF (bottom 16 bits of the 
    LDX srce        \ "multiplicator") and !dest = !srce + 1 ("multiplicand").
    TXA
    ADC #1
    STA dest
    LDY srce+1
    TYA
    ADC #0
    STA dest+1
    LDA srce+2      \ bits 23-16 of multiplicator not registerised.
    ADC #0
    STA dest+2
.multiply
    CLC             \ clear carry in preparation for next round of addition.
    LDA dest        \ test bottom bit of multiplicand. this tells us whether we
    AND #1          \ need to add the multiplicator (YX) to top bits of result.
    BEQ rotate      \ no addition of multiplicator required? skip to rotate.
    TXA             \ add multiplicator (YX) to top 24 bits of the result.
    ADC dest+3
    STA dest+3
    TYA
    ADC dest+4
    STA dest+4
    LDA srce+2      \ bits 23-16 of multiplicator not registerised. note that
    ADC dest+5      \ if we overflow (C=1) at this stage then it will ripple
    STA dest+5      \ into the result on the rotate so no need to raise errors.
.rotate
    ROR dest+5      \ advance multiplication. this implicitly rotates the
    ROR dest+4      \ multiplicand, setting us up for the next bottom bit test.
    ROR dest+3      \ previous error checks clamped (!srce + 1) to 18 bits, so
    ROR dest+2      \ bit 23 of mulitplicand (carry result on 24th rotate) will
    ROR dest+1      \ always be zero; no explicit CLC needed for 25th rotate.
    ROR dest
    DEC srce+4      \ one more bit of the multiplicand analysed. after 24
    BEQ rotate      \ iterations, the result is a factor of two too big. run a
    BPL multiply    \ 25th iteration with just the rotate (DIV 2) to finalise.
    LDA dest+4
    ORA dest+5      \ if all is good, we should have only 32 bits of result.
    BNE overflow
    RTS
.overflow
    BRK
    EQUB 20
    EQUS "Too big"
    BRK
]
NEXT

INPUT "Upper bound", !srce
CALL code
PRINT "Result: ";!dest;" (or in hex: &";RIGHT$("0000000"+STR$~!dest,8);")"

Edited: code indentation plus a few extra comments.

[Kecske Bak]

A couple of ideas came up in the ABUG dev night when we talked about this situation

I was trying to find this on the ABUG dev night to throw into the conversation, but couldn't find it at the time. I think this page is a very nice way to teach 6502.

https://skilldrick.github.io/easy6502/

[1024MAK]

Another thing which could be illustrated is that putting lots of comments in your Basic will slow it down, whereas lots of comments in assembly code make no difference at all...

Comments don’t slow down all BASIC versions the same amount. It depends on how the interpreter deals with line length and how it finds the start of the next line. And how a REM is treated.

And of course comments made in a compiled BASIC have no effect on execution time.

Mark

[BigEd]

Oh yes indeed - I might have a slightly biased opinion as I helped out a bit with it.

[ChrisB]

Interesting discussion. Something I've been using is the functionality of the CALL keyword. Rather than poke values into memory and then read them out again you can include them in the call statement and have the assembler modify BASIC's variables directly. So modifying Rich's code from above (with no error checking etc.) and a couple of convoluted examples.

Code: Select all

   10 DIM code% 255
   20 DIM sum%(9,1)
   30 result=&70
   40 max=&72
   50 FOR pass%=0 TO 2 STEP 2
   60 P%=code%
   70 [OPT pass%
   80 LDA &601:STA max
   90 LDA &602:STA max+1
  100 LDA &604:STA result
  110 LDA &605:STA result+1
  120 LDY #0
  130 LDA #0:STA (result),Y
  140 INY:STA (result),Y
  150 DEY:LDA (max),Y:TAX
  160 .loop
  170 TXA
  180 CLC
  190 ADC (result),Y:STA (result),Y
  200 INY:LDA #0
  210 ADC (result),Y:STA (result),Y
  220 DEY
  230 DEX
  240 BNE loop
  250 RTS
  260 ]
  270 NEXT
  280 :
  290 PRINT FNsum(100)
  300 REM It even works with arrays
  310 FOR X%=0 TO 9
  320 sum%(X%,0)=(X%+1)*10
  330 CALL code%,sum%(X%,0),sum%(X%,1)
  340 PRINT sum%(X%,0),sum%(X%,1)
  350 NEXT
  360 END
  370 :
  380DEFFNsum(max%)
  390 LOCAL result%
  400 CALL code%,max%,result%
  410 =result%

[BigEd]

BTW, I highly recommend the 'remastered' series of PDFs of the various user guides: see here.

Also there's a very nice diagram and table of the 6502 programmer's model by Bob Sander-Cederlof here.

CALL is very powerful, but note also that USR will initialise A, X and Y from A%, X% and Y%, and return them back (with the processor status) in the 4 byte integer return value.

[MrGpG]

Hi all

Really appreciate all the food for thought and sample code.

Lots to get my teeth into.

Glen