6502 Challenge #1

[Crispy]

For the first in what will hopefully be a series of challenges, I've chosen a favorite topic of mine. As we all know, the 6502 lacks multiply and divide instructions, so we are required to roll our own when we need to perform these operations. I've seen a few threads here about dividing by specific values, but I don't recall seeing a discussion on a general purpose divide routine. So, for this week's challenge that is exactly what we are going to do.

 

Challenge

Write a routine that will perform a divide operation given a dividend and divisor, and then return the quotient along with the remainder.

Requirements

The routine is to perform an integer division, and then return the quotient and remainder. There are no requirements for error checking; you may assume that the routine will always be called with valid parameters. Please post your solution as a spoiler.

Input

A = the divisor, where 255 >= divisor >= 1.

X = the dividend, where 255 >= dividend >= 0.

Return

A = the quotient

X = the remainder

[Crispy]

And since I've already worked out a solution, I'll go ahead and post it.

 

 

            org  $80

divisor     ds.w 1
dividend    ds.b 1
quotient    ds.b 1

div         ldy  #$00
            sty  quotient
            lsr
            sta  divisor+1
            sty  divisor
            ror  divisor
            stx  dividend
            ldx  #$08

.1          cpy  divisor+1
            bcc  .2
            lda  dividend
            sbc  divisor
            bcc  .2
            sta  dividend

.2          rol  quotient
            lsr  divisor+1
            ror  divisor
            dex
            bne  .1

            lda  quotient
            ldx  dividend
            rts

 

[Omegamatrix]

I've seen many solutions to this before, having interest in division routines myself. The one solution Crispy posted is similar to the ones I saw. The one I'm posting is untested, but I think it works. It gets the job done albeit a little slow.

 

;A = the divisor, where 255 >= divisor >= 1.
;X = the dividend, where 255 >= dividend >= 0.

    sta    temp
    txa
    ldx    #-1
    sec
.loopDivide:
    inx
    sbc   temp
    bcs   .loopDivide
    
    adc   temp
    sta   temp
    txa
    ldx   temp
    
;A = the quotient
;X = the remainder


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; and by changing the conditions of the test...
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;X = the divisor, where 255 >= divisor >= 1.
;A = the dividend, where 255 >= dividend >= 0.

    stx    temp
    ldx    #-1
    sec
.loopDivide:
    inx
    sbc   temp
    bcs   .loopDivide
    
    adc   temp
    
;X = the quotient
;A = the remainder

 

 

[Mr SQL]

Fun challenge Crispy!

 

Let's see, you used c last time, so how about 5 characters of BASIC?

 

e=5/2

 

 

[Sheddy]

5 characters? Qoutient and remainder not in A and X ?

[Mr SQL]

5 characters? Qoutient and remainder not in A and X ?

 

No problem, BBC BASIC style inline Assembly is supported:

 

e=5/2:" ldx b: lda e"

 

But BASIC addresses variables like registers so I think that construct would be pretty unlikely.

 

I had actually used the 5 character version in a 10 line BASIC game GATES I wrote for a programming contest earlier this year.

 

Here's another interesting challenge for programmers to try in any language:

 

What is the least amount of characters needed to toggle one of the variable in your gameloop between 0 and 1?

 

 

5

 

[Osgeld]

 

No problem, BBC BASIC style inline Assembly is supported:

 

e=5/2:" ldx b: lda e"

 

But BASIC addresses variables like registers so I think that construct would be pretty unlikely.

 

I had actually used the 5 character version in a 10 line BASIC game GATES I wrote for a programming contest earlier this year.

 

Here's another interesting challenge for programmers to try in any language:

 

What is the least amount of characters needed to toggle one of the variable in your gameloop between 0 and 1?

 

 

5

 

 

x = !x

[Mr SQL]

 

x = !x

 

Very cool, you solved it in 4!

I was using x=1-x

[Osgeld]

 

Very cool, you solved it in 4!

I was using x=1-x

 

well to be fair ! is ! used in all languages, like in apple basic you have to use x = not x which is obviously more than 5

[ZackAttack]

This was a really cool challenge.

 

I think my solution is doing something similar to what Crispy's solution does. It uses one less byte of ZP ram and only the A and X registers. I didn't test it to verify that it actually works and I have no idea if it's faster with regards to worst case and average.

Rather than subtracting A from X in a loop it calculates multiples by doubling A until it exceeds 8 bits. Then each multiple is compared to see if it "fits" into X and if so we reduce X by that multiple and add the corresponding power of 2 to the quotient. when we run out of multiples whatever is left of X is now the remainder.

IsZero:
  tax
  lda #0
  rts

IsOne:
  ldx #0
  lda #1
  rts

DivideAbyX: ; SubRoutine which divides X/A and returns A remainder X
  stx dividend
  cmp dividend
  beq IsOne
  bcs IsZero

  ldx #1
  stx pow2

FindBiggestMultiple:
  asl pow2
  rol A
  bcc FindBiggestMultiple

  lsr pow2 ;this works because A is at least 2 or the quotient would be 0 or 1 and this path is skipped
  ror A
  sta multiple

DivideLoop:
  lda dividend
  cmp multiple
  bcc SkipMultiple ; if dividend >= multiple add pow2 to quotient and subtract multiple
    sbc multiple
    sta dividend
    txa
    clc
    adc pow2
    tax
SkipMultiple:
  lsr multiple
  lsr pow2
  bne DivideLoop

  txa
  ldx dividend
  rts

 

 

[explorer]

The solution at 6502.org wiki is... witty.

 

 

 

http://6502org.wikidot.com/software-math-intdiv

 

 

Edited July 27, 2018 by explorer

[MLdB]

In the great tradition of posts by me: off the top of my head and completely untested But I am too curious about the other solutions to spend more time on mine.

 

This is certainly not the fastest method for every division, but I wanted something that was better at solving the worst cases (255/1 for example).

 

 

    ; To speed up worst cases like 255/1, let's find the biggest multiple of the divider that fits in 8 bits,
    ; doubling it every step until the most significant bit flows into the carry.
    
    ; I assume divisor is never 0. It's a trivial check, but the assignment states that the divisor >= 1
    LDA divisor
    
    ; I use X to keep track of how many times I left-shift the divisor.
    LDX #0
    
    ; Let's reuse those two cycles to initialize our solution
    STX quotient
    
Precalc:
    ASL
    INX
    BCC Precalc

    ; We have shifted the divisor once too many and it has overflown into the carry. I undo this by a single
    ; rotate right after which the multiplied divisor is written back to ram.
    ROR
    STA divisor
    
    ; Let's see if the biggest multiple of the divisor we found can be subtracted from the dividend (CMP divisor).
    ; If it can, the carry will be set (BCC, dividend >= divisor), the subtract will be executed (SBC divisor)
    ; (how convenient that the carry is already set!). These steps are skipped if dividend < (multiple of) divisor.
    LDA dividend
Subtract:
    CMP divisor
    BCC SkipSub
    SBC divisor

SkipSub:
    ; Let's update our solution (quotient) by rolling in the carry flag, which is 1 only if the current multiple
    ; of the divisor was subtracted from the remainder of the dividend.
    ROL quotient

    ; The ROL is guaranteed to have cleared the carry so we can easily divide the divisor by two for the next
    ; round by a rotate right.
    ROR divisor

    ; By taking the same number of steps as during the precalc phase, we end up with all the bits of the quotient
    ; in the right place.
    DEX
    BNE Subtract
    
    ; We now have our quotient in ram and our remainder in the accumulator, but the assignment states that the
    ; former should go in the accumulator and the latter in X
    TAX
    LDA quotient

Edited July 31, 2018 by MLdB

[+Gemintronic]

Next level maneuver: port SWEET 16 and write a routine for that

http://www.6502.org/source/interpreters/sweet16.htm

[MLdB]

I've been updating my solution over the past days, shaving off a couple of cycles every edit. I will test my solution to see if it works as it should and post some cycle counts to compare it to the other solutions.

 

(These are cycle counts, obviously, not answers  )

0/1   = 243
 
128/8   = 161
128/128 =  49
 
255/2   = 229
255/4   = 199
255/8   = 169
255/16  = 139
255/32  = 109
255/64  =  79
255/128 =  49
 
255/1   = 259
255/3   = 223
255/7   = 191
255/15  = 163
255/31  = 133
255/63  = 105
255/127 =  77
255/255 =  49

Edit: I wanted to test the other solutions as well, but could not get them to execute properly (yet) on the emulator I used. I noticed however that Zack's solution probably has a small error in it:

 

 

 

FindBiggestMultiple:

asl pow2
rol A
bcc FindBiggestMultiple

 

; The right shift (LSR pow2) will clear the carry, so the most significant bit of A (divisor) is not rolled back in on the next instruction (ROR A)
lsr pow2
ror A
sta multiple

 

 

Edited July 31, 2018 by MLdB

[ZackAttack]

Edit: I wanted to test the other solutions as well, but could not get them to execute properly (yet) on the emulator I used. I noticed however that Zack's solution probably has a small error in it:

Yeah, I'm not very happy with how badly I implemented my algorithm. I thought the algorithm itself was pretty neat, but after seeing how much better the 6502 wiki solution is I didn't bother trying to fix mine up. Though, fully understanding and commenting that solution might be its own challenge

 

What emulator where you using to test with? I was thinking that we should build a 2600 program to serve as a test harness for future challenges. I.E. for this challenge it could use the RIOT timer to track how long it takes a provided algorithm to perform all 65k possible divisions and then display a total in hex once it's done.

[MLdB]

Essentially it's doing a long division, shifting the most significant bits of the dividend through the carry into the accumulator until the latter is bigger than the divisor. The way 'we' do long divisions is the same: looking at the most significant digits of the dividend and dividing those by the divisor (binary systems have the advantage that the quotient of each step is always 1 or 0 (each digit of the solution) instead of 0-9 as in our decimal system, so there's no division involved only a single subtract)

 

After subtracting the divisor from the accumulator the carry is 1, but if the subtract was skipped, the carry is 0. The carry is then rolled into the solution, which may even be the same variable that is used for the dividend, shifting the dividend out and the solution in.

 

This is exactly what you do with long divisions: adding digits to the end of the solution, shifting the other digits into their eventual correct place (eg thousands, hundreds, tens, ones)

Edited July 31, 2018 by MLdB

[MLdB]

Though, fully understanding and commenting that solution might be its own challenge

 

 

 

   ; What the routine below does is analogue to how most of us
   ; have learned to do a long division, there's some irony in
   ; the fact that Zack's and my 6502 solutions work in the 
   ; opposite way from what we would normally do when dividing
   ; with pen and paper.

   ; The accumulator is cleared and will be used to hold an
   ; upper (leftmost) portion of the dividend which is shifted
   ; in bit by bit from the left of the dividend (the higher
   ; valued bits) through the carry into the lower end of the
   ; accumulator.
   LDA #0

   ; We need to repeat this 8 times so we have shifted all bits
   ; of the dividend through the carry into the accumulator.
   LDX #8

   ; This is the initial shift. TQ holds the dividend AND the
   ; quotient: as the dividend is shifted out on the left, the
   ; solution is shifted IN from the right bit by bit. More on
   ; that later. This means the routine uses only the two bytes
   ; of ram already in use to hold the dividend and divisor.
   ASL TQ

   ; Bit 7 of the dividend is now in the carry. By rolling it
   ; will be fed into bit 0 of the accumulator. Let's say the
   ; dividend > 127, then bit 7 was a 1 and the accumulator is
   ; at this moment %00000001.
L1 ROL

   ; Now we compare the accumulator to the divisor. If the carry
   ; is set by the CMP, the accumulator >= divisor and the divisor
   ; is subtracted. This, in effect, subtracts the highest possible
   ; multiple of the divisor without first precalculating it like our
   ; solutions.
   CMP B
   BCC L2
   SBC B

   ; Here we do two things: 1. rol a bit of the solution into TQ and
   ; 2. rol the next bit of the dividend into the carry from which
   ; it will be rolled into the accumulator once we branch back to L1
   ;
   ; The carry is 0 if the divisor was NOT subtracted from the 
   ; Accumulator at this iteration and 1 if it was. The bit of the
   ; first iteration for example corresponds to a 128-fold subtraction
   ; of the divisor. It enters the quotient (TQ) from the right, but
   ; will eventually be pushed up to it's correct position at bit 7
   ; by the next 7 iterations.
L2 ROL TQ
   DEX
   BNE L1

   ; Example: %11010000 / %11

   ; On the first iteration, the accumulator is %1, which is less
   ; than the divisor (%11). The carry is cleared, the subtract
   ; skipped and the clear carry (0) is rolled into the solution
   ; at label L2. TQ now being %01000000.
   ; (TQ is split between the dividend and quotient, right now
   ; it is: (remaining bits of dividend)(0)(upper bits of quotient)
   ; -> (010000)(0)(0). We got the 0 separating the dividend from
   ; the partial quotient from the "ASL TQ" step.

   ; On the second iteration, the accumulator is %11, which is
   ; equal to the divisor. The subtract is carried out and a 1 is
   ; rolled into TQ: %10000001 (or: (10000)(0)(01) )

   ; The third iteration pushes a zero in the accumulator which is
   ; also 0 after the subtract. TQ is now %00000010

   ; The fourth iteration: Acc = %00000001 -> no subtract
   ; TQ = %00000100 (or: (000)(0)(0100) )

   ; The fifth: Acc = %00000010 -> no subtract, TQ = %00001000

   ; The sixth: Acc = %00000100, subtract %11 leaves Acc = %00000001
   ; A 1 is rolled into TQ: %00010001 (or: (0)(0)(010001) )
   
   ; The seventh: Acc = %00000010 -> no subtract, TQ = %00100010
   ; (or: (0)(0100010) )
   
   ; The eighth: Acc = %00000100, subtract %11 leaves Acc = %00000001
   ; and TQ gets another 1: %01000101 (the separating 0 is shifted off,
   ; only the quotient remains with all the bits in their final place.)

   ; This is the final iteration. We solved 208/3 (= %11010000/%11)
   ; The accumulator holds the remainder (1) and the TQ variable the
   ; quotient (69 = %01000101)
 

 

 

Edited July 31, 2018 by MLdB