Version analysis of LOIN (Part 5 of 7) / LOINQ (Part 5 of 7)

This code appears in the following versions (click to see it in the source code):

Cassette, Disc (flight), Disc (docked), 6502 Second Processor, Master and Electron

Code variations between these versions are shown below.

Code variation 1 of 9A variation in the comments only

Tap on a block to expand it, and tap it again to revert.

Cassette, Flight, Docked, 6502SP, Electron
Master
       Name: LOIN (Part 5 of 7)
       Name: LOINQ (Part 5 of 7)

       Type: Subroutine
   Category: Drawing lines
    Summary: Draw a line: Line has a steep gradient, step up along y-axis
  Deep dive: Elite's line-drawing algorithm


 This routine draws a line from (X1, Y1) to (X2, Y2). It has multiple stages.
 If we get here, then:

   * |delta_y| >= |delta_x|

   * The line is closer to being vertical than horizontal

   * We are going to step up along the y-axis

   * We potentially swap coordinates to make sure Y1 >= Y2


.STPY

 LDY Y1                 \ Set A = Y = Y1
 TYA

 LDX X1                 \ Set X = X1

 CPY Y2                 \ If Y1 >= Y2, jump down to LI15, as the coordinates are
 BCS LI15               \ already in the order that we want

 DEC SWAP               \ Otherwise decrement SWAP from 0 to &FF, to denote that
                        \ we are swapping the coordinates around

 LDA X2                 \ Swap the values of X1 and X2
 STA X1
 STX X2

 TAX                    \ Set X = X1

 LDA Y2                 \ Swap the values of Y1 and Y2
 STA Y1
 STY Y2

 TAY                    \ Set Y = A = Y1

.LI15

                        \ By this point we know the line is vertical-ish and
                        \ Y1 >= Y2, so we're going from top to bottom as we go
                        \ from Y1 to Y2

Code variation 2 of 9Related to the screen mode

Tap on a block to expand it, and tap it again to revert.

Cassette, Flight, Docked
Master
6502SP
Electron
 LSR A                  \ Set A = A >> 3
 LSR A                  \       = y div 8
 LSR A                  \
                        \ So A now contains the number of the character row
                        \ that will contain the (X1, Y1) pixel

 ORA #&60               \ As A < 32, this effectively adds &60 to A, which gives
                        \ us the screen address of the character row (as each
                        \ character row takes up 256 bytes, and the first
                        \ character row is at screen address &6000, or page &60)

 STA SCH                \ Store the page number of the character row in SCH, so
                        \ the high byte of SC is set correctly for drawing the
                        \ start of our line

 TXA                    \ Set A = bits 3-7 of X1
 AND #%11111000
 LDA ylookup,Y          \ Look up the page number of the character row that
 STA SC+1               \ contains the pixel with the y-coordinate in Y1, and
                        \ store it in the high byte of SC(1 0) at SC+1, so the
                        \ high byte of SC is set correctly for drawing our line

 TXA                    \ Set A = 2 * bits 2-6 of X1
 AND #%11111100         \
 ASL A                  \ and shift bit 7 of X1 into the C flag
IF _SNG45 OR _EXECUTIVE OR _SOURCE_DISC_BUILD

 LDA ylookup,Y          \ Look up the page number of the character row that
 STA SC+1               \ contains the pixel with the y-coordinate in Y1, and
                        \ store it in the high byte of SC(1 0) at SC+1, so the
                        \ high byte of SC is set correctly for drawing our line

ELIF _SOURCE_DISC_FILES

 LSR A                  \ Set A = A / 4, clear bit 0 and add &40, so this sets
 LSR A                  \ A to &40 + (Y1 / 4) rounded down down to a multiple
 LSR A                  \ of 2
 ASL A                  \
 ADC #&40               \ The addition works because the third LSR A shifts a
                        \ zero into bit 7 of A, and the ASL A then shift that
                        \ zero into the C flag

 STA SC+1               \ Store the result in the high byte of SC(1 0) at SC+1,
                        \ which sets SC(1 0) to the the page number of the
                        \ character row that contains the pixel with the
                        \ y-coordinate in Y1, as screen memory starts at &4000
                        \ and there are two pages (512 bytes) per pixel line in
                        \ the custom screen mode used in the space view

ENDIF

 TXA                    \ Set A = 2 * bits 2-6 of X1
 AND #%11111100         \
 ASL A                  \ and shift bit 7 of X1 into the C flag
                        \ We now calculate the address of the character block
                        \ containing the pixel (X1, Y1) and put it in SC(1 0),
                        \ as follows:
                        \
                        \   SC = &5800 + (Y1 div 8 * 256) + (Y1 div 8 * 64) + 32

 LSR A                  \ Set A = A >> 3
 LSR A                  \       = y div 8
 LSR A                  \
                        \ So A now contains the number of the character row
                        \ that will contain the (X1, Y1) pixel

 STA SC+1               \ Set SC+1 = A, so (SC+1 0) = A * 256
                        \                           = char row * 256

 LSR A                  \ Set (A SC) = (A SC) / 4
 ROR SC                 \            = (4 * ((char row * 64) + 32)) / 4
 LSR A                  \            = char row * 64 + 32
 ROR SC

 ADC SC+1               \ Set SC(1 0) = (A SC) + (SC+1 0) + &5800
 ADC #&58               \             = (char row * 64 + 32)
 STA SC+1               \               + char row * 256
                        \               + &5800
                        \
                        \ which is what we want, so SC(1 0) contains the address
                        \ of the first visible pixel on the character row
                        \ containing the point (X1, Y1)

 TXA                    \ Each character block contains 8 pixel rows, so to get
 AND #%11111000         \ the address of the first byte in the character block
                        \ that we need to draw into, as an offset from the start
                        \ of the row, we clear bits 0-2

 ADC SC                 \ And add the result to SC(1 0) to get the character
 STA SC                 \ block on the row we want

 BCC P%+4               \ If the addition of the low bytes overflowed, increment
 INC SC+1               \ the high byte

                        \ So SC(1 0) now contains the address of the first pixel
                        \ in the character block containing the (X1, Y1), taking
                        \ the screen borders into consideration

Code variation 3 of 9Related to the screen mode

This variation is blank in the Electron version.

Cassette, Flight, Docked, 6502SP, Master
 STA SC                 \ Store this value in SC, so SC(1 0) now contains the
                        \ screen address of the far left end (x-coordinate = 0)
                        \ of the horizontal pixel row that we want to draw the
                        \ start of our line on

Code variation 4 of 9Related to the screen mode

This variation is blank in the Cassette, Disc (flight), Disc (docked) and Electron versions.

6502SP, Master
 BCC P%+4               \ If bit 7 of X1 was set, so X1 > 127, increment the
 INC SC+1               \ high byte of SC(1 0) to point to the second page on
                        \ this screen row, as this page contains the right half
                        \ of the row

Code variation 5 of 9Related to the screen mode

This variation is blank in the Electron version.

Tap on a block to expand it, and tap it again to revert.

Cassette, Flight, Docked
6502SP, Master
 TXA                    \ Set X = X1 mod 8, which is the horizontal pixel number
 AND #7                 \ within the character block where the line starts (as
 TAX                    \ each pixel line in the character block is 8 pixels
                        \ wide)
 TXA                    \ Set X = X1 mod 4, which is the horizontal pixel number
 AND #3                 \ within the character block where the line starts (as
 TAX                    \ each pixel line in the character block is 4 pixels
                        \ wide)

Code variation 6 of 9Related to the screen mode

This variation is blank in the Electron version.

Cassette, Flight, Docked, 6502SP, Master
 LDA TWOS,X             \ Fetch a one-pixel byte from TWOS where pixel X is set,
 STA R                  \ and store it in R

Code variation 7 of 9Other (e.g. bug fix, optimisation)

Part 5 of the LOIN routine in the advanced versions uses logarithms to speed up the multiplication.

This variation is blank in the 6502 Second Processor and Master versions.

Cassette, Flight, Docked, Electron
 LDA Y1                 \ Set Y = Y1 mod 8, which is the pixel row within the
 AND #7                 \ character block at which we want to draw the start of
 TAY                    \ our line (as each character block has 8 rows)

Code variation 8 of 9Related to the screen mode

This variation is blank in the Cassette, Disc (flight), Disc (docked), 6502 Second Processor and Master versions.

Electron
 TXA                    \ Set X = X1 mod 8, which is the pixel column within the
 AND #7                 \ character block at which we want to draw the start of
 TAX                    \ our line (as each character block has 8 rows)

 LDA TWOS,X             \ Fetch a mode 4 one-pixel byte with the pixel position
 STA R                  \ at X and store it in R to act as a mask

Code variation 9 of 9Other (e.g. bug fix, optimisation)

Part 5 of the LOIN routine in the advanced versions uses logarithms to speed up the multiplication and the Master version omits half of the logarithm algorithm when compared to the 6502SP version.

Tap on a block to expand it, and tap it again to revert.

Cassette, Flight, Docked, Electron
Master
6502SP
                        \ The following calculates:
                        \
                        \   P = P / Q
                        \     = |delta_x| / |delta_y|
                        \
                        \ using the same shift-and-subtract algorithm that's
                        \ documented in TIS2

 LDA P                  \ Set A = |delta_x|

 LDX #1                 \ Set Q to have bits 1-7 clear, so we can rotate through
 STX P                  \ 7 loop iterations, getting a 1 each time, and then
                        \ getting a 1 on the 8th iteration... and we can also
                        \ use P to catch our result bits into bit 0 each time

.LIL4

 ASL A                  \ Shift A to the left

 BCS LI13               \ If bit 7 of A was set, then jump straight to the
                        \ subtraction

 CMP Q                  \ If A < Q, skip the following subtraction
 BCC LI14

.LI13

 SBC Q                  \ A >= Q, so set A = A - Q

 SEC                    \ Set the C flag to rotate into the result in Q

.LI14

 ROL P                  \ Rotate the counter in P 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)

 BCC LIL4               \ If we still have set bits in P, loop back to TIL2 to
                        \ do the next iteration of 7

                        \ We now have:
                        \
                        \   P = A / Q
                        \     = |delta_x| / |delta_y|
                        \
                        \ and the C flag is set

 LDX Q                  \ Set X = Q + 1
 INX                    \       = |delta_y| + 1
                        \
                        \ We add 1 so we can skip the first pixel plot if the
                        \ line is being drawn with swapped coordinates

 LDA X2                 \ Set A = X2 - X1 (the C flag is set as we didn't take
 SBC X1                 \ the above BCC)

 BCC LFT                \ If X2 < X1 then jump to LFT, as we need to draw the
                        \ line to the left and down
                        \ The following section calculates:
                        \
                        \   P = P / Q
                        \     = |delta_x| / |delta_y|
                        \
                        \ using the log tables at logL and log to calculate:
                        \
                        \   A = log(P) - log(Q)
                        \     = log(|delta_x|) - log(|delta_y|)
                        \
                        \ by first subtracting the low bytes of the logarithms
                        \ from the table at LogL, and then subtracting the high
                        \ bytes from the table at log, before applying the
                        \ antilog to get the result of the division and putting
                        \ it in P

 LDX P                  \ Set X = |delta_x|

 BEQ LIfudge            \ If |delta_x| = 0, jump to LIfudge to return 0 as the
                        \ result of the division

 LDA logL,X             \ Set A = log(P) - log(Q)
 LDX Q                  \       = log(|delta_x|) - log(|delta_y|)
 SEC                    \
 SBC logL,X             \ by first subtracting the low bytes of log(P) - log(Q)

 LDX P                  \ And then subtracting the high bytes of log(P) - log(Q)
 LDA log,X              \ so now A contains the high byte of log(P) - log(Q)
 LDX Q
 SBC log,X

 BCS LIlog3             \ If the subtraction fitted into one byte and didn't
                        \ underflow, then log(P) - log(Q) < 256, so we jump to
                        \ LIlog3 to return a result of 255

 TAX                    \ Otherwise we set A to the A-th entry from the antilog
 LDA alogh,X            \ table so the result of the division is now in A

 JMP LIlog2             \ Jump to LIlog2 to return the result

.LIlog3

 LDA #255               \ The division is very close to 1, so set A to the
                        \ closest possible answer to 256, i.e. 255

.LIlog2

 STA P                  \ Store the result of the division in P, so we have:
                        \
                        \   P = |delta_x| / |delta_y|

.LIfudge

 LDX Q                  \ Set X = Q
                        \       = |delta_y|

 BEQ LIEX7              \ If |delta_y| = 0, jump down to LIEX7 to return from
                        \ the subroutine

 INX                    \ Set X = Q + 1
                        \       = |delta_y| + 1
                        \
                        \ We add 1 so we can skip the first pixel plot if the
                        \ line is being drawn with swapped coordinates

 LDA X2                 \ Set A = X2 - X1
 SEC
 SBC X1

 BCS P%+6               \ If X2 >= X1 then skip the following two instructions

 JMP LFT                \ If X2 < X1 then jump to LFT, as we need to draw the
                        \ line to the left and down

.LIEX7

 RTS                    \ Return from the subroutine
IF _SNG45 OR _EXECUTIVE OR _SOURCE_DISC_BUILD

                        \ The following section calculates:
                        \
                        \   P = P / Q
                        \     = |delta_x| / |delta_y|
                        \
                        \ using the log tables at logL and log to calculate:
                        \
                        \   A = log(P) - log(Q)
                        \     = log(|delta_x|) - log(|delta_y|)
                        \
                        \ by first subtracting the low bytes of the logarithms
                        \ from the table at LogL, and then subtracting the high
                        \ bytes from the table at log, before applying the
                        \ antilog to get the result of the division and putting
                        \ it in P

 LDX P                  \ Set X = |delta_x|

 BEQ LIfudge            \ If |delta_x| = 0, jump to LIfudge to return 0 as the
                        \ result of the division

 LDA logL,X             \ Set A = log(P) - log(Q)
 LDX Q                  \       = log(|delta_x|) - log(|delta_y|)
 SEC                    \
 SBC logL,X             \ by first subtracting the low bytes of log(P) - log(Q)

 BMI LIloG              \ If A > 127, jump to LIloG

 LDX P                  \ And then subtracting the high bytes of log(P) - log(Q)
 LDA log,X              \ so now A contains the high byte of log(P) - log(Q)
 LDX Q
 SBC log,X

 BCS LIlog3             \ If the subtraction fitted into one byte and didn't
                        \ underflow, then log(P) - log(Q) < 256, so we jump to
                        \ LIlog3 to return a result of 255

 TAX                    \ Otherwise we set A to the A-th entry from the antilog
 LDA antilog,X          \ table so the result of the division is now in A

 JMP LIlog2             \ Jump to LIlog2 to return the result

.LIlog3

 LDA #255               \ The division is very close to 1, so set A to the
 BNE LIlog2             \ closest possible answer to 256, i.e. 255, and jump to
                        \ LIlog2 to return the result (this BNE is effectively a
                        \ JMP as A is never zero)

.LIloG

 LDX P                  \ Subtract the high bytes of log(P) - log(Q) so now A
 LDA log,X              \ contains the high byte of log(P) - log(Q)
 LDX Q
 SBC log,X

 BCS LIlog3             \ If the subtraction fitted into one byte and didn't
                        \ underflow, then log(P) - log(Q) < 256, so we jump to
                        \ LIlog3 to return a result of 255

 TAX                    \ Otherwise we set A to the A-th entry from the
 LDA antilogODD,X       \ antilogODD so the result of the division is now in A

.LIlog2

 STA P                  \ Store the result of the division in P, so we have:
                        \
                        \   P = |delta_x| / |delta_y|

ELIF _SOURCE_DISC_FILES

                        \ The following calculates:
                        \
                        \   P = P / Q
                        \     = |delta_x| / |delta_y|
                        \
                        \ using the same shift-and-subtract algorithm that's
                        \ documented in TIS2

 LDA P                  \ Set A = |delta_x|

                        \ We now repeat the following seven instruction block
                        \ eight times, one for each bit in P. In the BBC Micro
                        \ cassette and disc versions of Elite the following is
                        \ done with a loop, but it is marginally faster to
                        \ unroll the loop and have eight copies of the code,
                        \ though it does take up a bit more memory (though that
                        \ isn't a big concern when you have a 6502 Second
                        \ Processor)

 ASL A                  \ Shift A to the left

 BCS LI13               \ If bit 7 of A was set, then jump straight to the
                        \ subtraction

 CMP Q                  \ If A < Q, skip the following subtraction
 BCC LI14

.LI13

 SBC Q                  \ A >= Q, so set A = A - Q

 SEC                    \ Set the C flag to rotate into the result in Q

.LI14

 ROL P                  \ Rotate the counter in P 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)

 ASL A                  \ Repeat for the second time
 BCS P%+6
 CMP Q
 BCC P%+5
 SBC Q
 SEC
 ROL P

 ASL A                  \ Repeat for the third time
 BCS P%+6
 CMP Q
 BCC P%+5
 SBC Q
 SEC
 ROL P

 ASL A                  \ Repeat for the fourth time
 BCS P%+6
 CMP Q
 BCC P%+5
 SBC Q
 SEC
 ROL P

 ASL A                  \ Repeat for the fifth time
 BCS P%+6
 CMP Q
 BCC P%+5
 SBC Q
 SEC
 ROL P

 ASL A                  \ Repeat for the sixth time
 BCS P%+6
 CMP Q
 BCC P%+5
 SBC Q
 SEC
 ROL P

 ASL A                  \ Repeat for the seventh time
 BCS P%+6
 CMP Q
 BCC P%+5
 SBC Q
 SEC
 ROL P

 ASL A                  \ Repeat for the eighth time
 BCS P%+6
 CMP Q
 BCC P%+5
 SBC Q
 SEC
 ROL P

ENDIF

.LIfudge

 LDX Q                  \ Set X = Q
                        \       = |delta_y|

 BEQ LIEX7              \ If |delta_y| = 0, jump down to LIEX7 to return from
                        \ the subroutine

 INX                    \ Set X = Q + 1
                        \       = |delta_y| + 1
                        \
                        \ We add 1 so we can skip the first pixel plot if the
                        \ line is being drawn with swapped coordinates

 LDA X2                 \ Set A = X2 - X1
 SEC
 SBC X1

 BCS P%+6               \ If X2 >= X1 then skip the following two instructions

 JMP LFT                \ If X2 < X1 then jump to LFT, as we need to draw the
                        \ line to the left and down

.LIEX7

 RTS                    \ Return from the subroutine