Modulus arithmetic on the 6502

Question

I have a very simple problem with is turning out to be surprisingly complex to solve.

I wish to add two bytes using modulus arithmetic, where the modulus is known at compile time. e.g. given modulus 5, 3+3 = 1. The specific number I have currently for the modulus is 201, but that might change in the future.

On fast computers, this is just (x+y) % modulus. Except, this requires extending the intermediate values to words, to avoid overflow, and then doing a division, which I'd very much like to avoid (this is going to be happening rather a lot). The other option is to try and redefine my problem so that modulus is a power of two, and then just masking the result... but I can't do that in this case.

Are there any cunning tricks for doing this on the 6502 which someone can suggest?

Answer 1

Here's a shorter solution than wizzwizz4's:

  SEC
  LDA x
  SBC modulus
  ADC y
  BCS end
  ADC modulus
end:

The idea is to bias the inputs so that the addition overflows just when the modulus needs to be subtracted.

This requires x < modulus. If y < modulus then the result will be less than modulus, otherwise it may be any value like y. The carry will always be set at the end which may be useful.

Answer 2

The easiest solution is to assume they're both below modulus already, then do if (result >= modulus) result -= modulus; – same as the method in the question, but with faster subtraction (or addition) instead of division.

Since 210 is between 128 and 256, this is even easier. I don't know 6502, so here's some fake C:

const mod = 210;

char sum_mod(char a, char b) {
            a = a + b;
            if (!CARRY) goto later;
            a -= mod;
            if (!CARRY) goto again;
    later:  COMPARE(a, mod);
            if (!(a > mod)) goto after;
    again:  a -= mod;
    after:  return a;
}

For modulus less than 128, you'd need to compare and subtract successively smaller (mod << n), after the overflow check. The overflow check should use the largest (mod << n) (i.e., the largest less than 256; including as the again target), because the important part is just to get it back under the overflow threshold so normal mathematics works again.

Explanation

Theoretical a + b might be:

• >= 0 and < mod: both of the conditional jumps encountered will be followed, and a + b will be returned.
• > mod but < 256: the carry flag is not set, so the later jump will be followed, but neither the again nor after jump will; this means that a + b - mod will be returned.
• > 255 and < 2 * mod: the carry flag is set, so the later jump won't be followed, and then the after jump will; this means that a + b - mod will be returned.
• >= 2 * mod and < mod + 256: no jump will be followed, so a + b - 2 * mod will be returned.
• > mod + 255 and < 511: again will be followed, so a + b - 2 * mod will be returned.

Thanks to Raffzahn for pointing out the need for the again jump. (And sorry for the useless label names.)

Answer 3

If one needs to compute the mod-201 sum of many values, a useful technique is e.g.

    ; Compute the mod-M sum of N values, for N up to 129.
    ; Easily adaptable for 256 values, or for other numbers of values.
    ldy #N-1
    lda #256-M
    clc
loop:
    adc values,y
    bcc noWrap
wrapped:
    sbc #M      ; Note that carry is set here
    bcs wrapped ; Could be omitted if original values are all less than M
noWrap:
    dey
    bpl loop
    adc #M ; Note carry is clear here

While performing the computation, there's no need for code to care about the modulus except when a carry occurs. At the end of the loop, the value in the accumulator will be equal to the correct residue plus (256-M), so adding M will negate the -M term.

Answer 4

Given the assumption that 0 < A < modulus and 0 < B < modulus, than the following routine for 6502 (following the suggested algorithm of wizzwizz4) does the job:

MODULUS=201
varA=$FC
varB=$FD

;add two numbers A and B given in memory address
;numbers A and B must be < MODULUS
;returns with the value (A+B) mod MODULUS in Accu

        clc
        lda varA
        adc varB
        ;we only need this if the added numbers could overflow
        .if MODULUS>=128
        bcc no_overflow
        sbc #MODULUS
        rts
        .endif
no_overflow:
        cmp #MODULUS
        bcc exit
        sbc #MODULUS ;carry is 1 because of past two lines
exit:
        rts

I tested several combinations of modulus, A and B with a BASIC program

10 FORM=5TO255STEP37
20 POKE49160,M:POKE49163,M:POKE49167,M
30 FORA=1TOM-1STEP1+INT(M/37)
40 FORB=4TOM-1STEP1+INT(M/26)
50 POKE252,A:POKE253,B:SYS49152
60 C=PEEK(780)
70 D=A+B:IFD>=MTHEND=D-M
80 IFC<>DTHEN PRINTM;A,B,C,D:END
90 NEXTB,A,M

finding it working in all tested cases.

Shortened version hinted by David:

MODULUS=201
varA=$FC
varB=$FD

;add two numbers A and B given in memory address
;numbers A and B must be < MODULUS
;returns with the value (A+B) mod MODULUS in Accu
        clc
        lda varA
        adc varB
        ;we only need this if the added numbers could overflow
        .if MODULUS>=128
        bcs overflow
        .endif
        cmp #MODULUS
        bcc exit
overflow:
        sbc #MODULUS ;carry is already set
exit:
        rts

Automatic testing program for second version:

10 FORM=5TO255STEP37
20 POKE49160,M:POKE49164,M
30 FORA=1TOM-1STEP1+INT(M/37)
40 FORB=4TOM-1STEP1+INT(M/26)
50 POKE252,A:POKE253,B:SYS49152
60 C=PEEK(780)
70 D=A+B:IFD>=MTHEND=D-M
80 IFC<>DTHEN PRINTM;A,B,C,D:END
90 NEXTB,A,M

Some example testcases for manual testing:

A=0, B=0 -> (A+B)%201=0
A=1, B=1 -> (A+B)%201=2
A=100, B=100 -> (A+B)%201=200
A=101, B=100 -> (A+B)%201=0
A=200, B=0 -> (A+B)%201=200
A=200, B=1 -> (A+B)%201=0
A=200, B=200 -> (A+B)%201=199