Skip to navigation

Elite on the BBC Micro and NES

Maths (Arithmetic): LL28

[BBC Micro cassette version]

Name: LL28 [Show more] Type: Subroutine Category: Maths (Arithmetic) Summary: Calculate R = 256 * A / Q Deep dive: Shift-and-subtract division
Context: See this subroutine in context in the source code Variations: See code variations for this subroutine in the different versions References: This subroutine is called as follows: * ARCTAN calls LL28 * LL145 (Part 3 of 4) calls LL28 * LL61 calls LL28 * LL9 (Part 3 of 12) calls LL28 * LL9 (Part 8 of 12) calls LL28 * DVID4 calls via LL28+4 * DVID3B2 calls via LL31

Calculate the following, where A < Q: R = 256 * A / Q This is a sister routine to LL61, which does the division when A >= Q. If A >= Q then 255 is returned and the C flag is set to indicate an overflow (the C flag is clear if the division was a success). The result is returned in one byte as the result of the division multiplied by 256, so we can return fractional results using integers. This routine uses the same shift-and-subtract algorithm that's documented in TIS2, but it leaves the fractional result in the integer range 0-255.
Returns: C flag Set if the answer is too big for one byte, clear if the division was a success
Other entry points: LL28+4 Skips the A >= Q check and always returns with C flag cleared, so this can be called if we know the division will work LL31 Skips the A >= Q check and does not set the R counter, so this can be used for jumping straight into the division loop if R is already set to 254 and we know the division will work
.LL28 CMP Q \ If A >= Q, then the answer will not fit in one byte, BCS LL2 \ so jump to LL2 to return 255 LDX #%11111110 \ Set R to have bits 1-7 set, so we can rotate through 7 STX R \ loop iterations, getting a 1 each time, and then \ getting a 0 on the 8th iteration... and we can also \ use R to catch our result bits into bit 0 each time .LL31 ASL A \ Shift A to the left BCS LL29 \ If bit 7 of A was set, then jump straight to the \ subtraction CMP Q \ If A < Q, skip the following subtraction BCC P%+4 SBC Q \ A >= Q, so set A = A - Q ROL R \ Rotate the counter in R to the left, and catch the \ result bit into bit 0 (which will be a 0 if we didn't \ do the subtraction, or 1 if we did) BCS LL31 \ If we still have set bits in R, loop back to LL31 to \ do the next iteration of 7 RTS \ R left with remainder of division .LL29 SBC Q \ A >= Q, so set A = A - Q SEC \ Set the C flag to rotate into the result in R ROL R \ Rotate the counter in R to the left, and catch the \ result bit into bit 0 (which will be a 0 if we didn't \ do the subtraction, or 1 if we did) BCS LL31 \ If we still have set bits in R, loop back to LL31 to \ do the next iteration of 7 RTS \ Return from the subroutine with R containing the \ remainder of the division .LL2 LDA #255 \ The division is very close to 1, so return the closest STA R \ possible answer to 256, i.e. R = 255 RTS \ Return from the subroutine