Differences

This shows you the differences between two versions of the page.

--- sd:isa [2026/06/16 12:34] – appledog
+++ sd:isa [2026/09/08 04:07] (current) – external edit 127.0.0.1
@@ Line 178: / Line 178: @@
 === Tier 4: Acceleration (LLVM / Forth / Hardware)
-Instructions added to remove work from a specific hot path rather than to add
+Instructions added to remove work from a specific hot path rather than to add expressiveness. Each one has a primary consumer noted below.
-expressiveness. Each one has a primary consumer noted below.
+Canidates for inclusion: LEA, fused CMP-Bcc and CMP-Jcc, conditional move, LD_IDX16, [[#ptrace|PTRACE]] (proposed, see below)
 | #   | hex  | Mnemonic | Example          | Description                                  | Consumer | Flags |
 | 28  | $1C  | [[#movx|MOVSX]]  | MOVSX A, AL      | Move with sign-extend (dst wider than src)   | LLVM     |       |
 | 29  | $1D  | [[#movx|MOVZX]]  | MOVZX A, AL      | Move with zero-extend (dst wider than src)   | LLVM     |       |
+| 60  | $3C  | [[#mac|MAC]]     | MAC Z, Y, BL     | Multiply-accumulate: acc += a * b             | Math     | Z N   |
+| 61  | $3D  | [[#absd|ABSD]]   | ABSD I, A        | Absolute difference: dst = \|dst - src\|        | Math     | Z     |
 | 210 | $D2  | [[#idx|LD_IDXI]] | LDA [BLX + #4]   | Indexed load, signed byte immediate -128..127| LLVM     |       |
 | 211 | $D3  | [[#idx|LD_IDXR]] | LDA [BLX + X]    | Indexed load, register offset                | LLVM     |       |
@@ Line 388: / Line 391: @@
 <wrap #cmpc />
 **''#142 $8E CMPC ELM, FLD, C''** (alias //CMPC3//)\\
-Non-zero byte compare, useful for strings. Compares up to C characters; C returns
+Non-zero byte compare, useful for strings. Compares up to C characters; C returns either the index of the first mismatch or the matched length. Sets ZERO on a full match; otherwise CARRY distinguishes the -1 / +1 ordering.
-either the index of the first mismatch or the matched length. Sets ZERO on a full
-match; otherwise CARRY distinguishes the -1 / +1 ordering.
-CMPC allows early termination when ''byte_a == 0'' -- the C-string "begins with"
+CMPC allows early termination when ''byte_a == 0'' -- the C-string "begins with" semantics. If both strings reach a terminator at the same position with all prior bytes equal, the loop exits matched (Z=1, C=1). Only ''byte_a'' is tested because by that point ''byte_a == byte_b'' is already proven, so ''byte_a == 0'' implies ''byte_b == 0''. This lets CMPC do double duty: fixed-length compare and null-terminated strcmp in one instruction.
-semantics. If both strings reach a terminator at the same position with all prior
-bytes equal, the loop exits matched (Z=1, C=1). Only ''byte_a'' is tested because by
-that point ''byte_a == byte_b`` is already proven, so ''byte_a == 0'' implies
-''byte_b == 0''. This lets CMPC do double duty: fixed-length compare and
-null-terminated strcmp in one instruction.
 <wrap #skpc />
@@ Line 523: / Line 519: @@
 <codify armasm>
-    LDFLX $F000       ; loop start
+    LDFLX $F000       ; 8 byte loop data start
-    LDA #1
+    LDA #1            ; start at 1
-    STA [FLX]
+    STA [FLX]         ; write starting counter at first four bytes
-    LDA #1000
+    LDA #1000         ; go until 1000
-    STA [FLX+4]
+    STA [FLX+4]       ; write finish (until) counter at second four bytes
 loop:
-    LSTEPM
+    LSTEPM            ; INC N1, if N1==N2 set Z=1
     JNZ @loop
 </codify>
-Unlike a DEC loop it counts upward and supports an arbitrary start. It is a kludge
+Unlike a DEC loop it counts upward and supports an arbitrary start. The generalized form of this is [[#lstep|LSTEP]] which counts downwards instead.
-for Forth and has been generalized by [[#lstep|LSTEP]]; once Forth uses LSTEP,
-LSTEPM is a candidate for removal.
+Only used by Forth. It is recommended to use LSTEP instead; this instruction is a canidate for removal.
 <wrap #ttos />
@@ Line 556: / Line 552: @@
     LSTEP C, @loop
 </codify>
+<wrap #mac />
+**''#60 $3C MAC''**\\
+Multiply-accumulate: ''acc += a * b''. Three registers; only the accumulator is
+written. The result takes the accumulator's width, while ''a'' and ''b'' are each
+read at their own -- so ''MAC Z, Y, BL'' is both legal and the common case.
+**Why it exists.** Every tile lookup in a tile game computes
+''row * width + column''. Rogueima does that on every line-of-sight mark, every
+rendered cell and every walkability test; it was the single most executed
+arithmetic sequence in the program. ''MOV / MUL / ADD'' collapses to ''MOV / MAC'',
+and the scratch register the product needed disappears with it.
+<codify armasm>
+    ; ELM = tile_base + (y * width + x) * 2
+    LDB [@level_dim]        ; BL = map width
+    MOV Z, X                ; Z = column
+    MAC Z, Y, BL            ;   + row * width
+    ADD Z, Z                ; two bytes per tile
+    LDELM [@level_tiles]
+    ADD ELM, Z
+</codify>
+**Where else it helps.** Anything shaped ''sum += a * b''. Squared distance is
+two MACs and no temporary at all:
+<codify armasm>
+    LDA #0
+    MAC A, I, I             ; A  = dx*dx
+    MAC A, J, J             ; A += dy*dy
+</codify>
+Also dot products, fixed-point scaling, Horner's rule for polynomials, and the
+inner loop of any filter, matrix or checksum routine.
+**Recognising the pattern.** Look for a ''MUL'' whose result is immediately added
+to something and then never used again, or a ''MOV/MUL/ADD'' trio built around a
+scratch register. If that register exists only to carry the product from the
+multiply to the add, MAC removes the register and an instruction together.
+**Measured.** Adding MAC to rogueima's line-of-sight and tile addressing cut
+.0% off the cost of a turn.
+<wrap #absd />
+**''#61 $3D ABSD''**\\
+Absolute difference: ''dst = |dst - src|''. The result is a magnitude, so N is
+always clear and Z is set exactly when the two operands are equal. ''src'' is
+read at its own width.
+**Why it exists.** Distance work needs the size of a difference, not its sign,
+and getting one without this instruction costs four to six instructions of
+compare, branch, and subtract-the-other-way round -- **per axis**. Rogueima's
+line-of-sight does it twice for every square it examines, a few thousand times
+a turn.
+<codify armasm>
+    ; dx = |x - px|, without a branch in sight
+    LDA #0
+    LDAL [@PX]
+    LDI #0
+    MOV IL, XL
+    ABSD I, A               ; I = |x - px|
+</codify>
+**Where else it helps.** Manhattan and Chebyshev distance, "are these two within
+N of each other", clamping, sorting, collision tests, and difference metrics over
+audio or images. It doubles as a branch-free equality test: Z is set precisely
+when the operands match, so you get ''CMP'' and a magnitude in one go.
+**Recognising the pattern.** Look for a compare followed by two subtractions in
+opposite orders down the two arms of a branch -- any
+''if (a > b) d = a - b; else d = b - a''. That entire shape is one instruction.
+**Measured.** 7.2% off the cost of a turn in rogueima -- more than MAC, because
+the branches it removes were unpredictable ones inside the hottest loop.
+<wrap #ptrace />
+**''PTRACE'' -- PROPOSED, NOT IMPLEMENTED**\\
+//No opcode assigned. This is a specification for review, not a description of
+the machine.//
+Walk a line through a tile array, stopping at the first tile that blocks, and
+optionally marking every tile visited on the way. A PPU instruction in the same
+family as ''PLINE'', and taking its parameters in registers the same way.
+^ ^ ^
+| **in** | ''ELM'' = tile array base |
+| ::: | ''X'',''Y'' = start;  ''I'',''J'' = target |
+| ::: | ''KL'',''KH'' = map width, height (for bounds) |
+| ::: | ''BL'' = bytes per tile;  ''BH'' = offset of the flags byte within a tile |
+| ::: | ''CL'' = block mask;  ''CH'' = set mask |
+| **out** | ''X'',''Y'' = where it stopped |
+| ::: | ''AL'' = tiles visited |
+| ::: | ''Z'' set if it stopped on a blocker, clear if it reached the target |
+At every tile along the line it ORs ''CH'' into the flags byte; if
+''flags & CL'' is non-zero it stops, having marked that tile. It also stops at
+the edge of the array. A ''CH'' of zero traces without marking, which is what a
+projectile or a "can this monster see me" test wants.
+<codify armasm>
+    ; one line-of-sight ray, marking SEEN|VISIBLE and stopping at anything opaque
+    LDELM [@level_tiles]
+    LDB [@level_dim]        ; KL, KH = width, height
+    MOV K, B
+    LDBL #2                 ; two bytes per tile
+    LDBH #1                 ; the flags are the second of them
+    LDCL @TF_OPAQUE         ; what stops the ray
+    LDCH $0C                ; TF_SEEN | TF_VISIBLE
+    LDXL [@PX]
+    LDYL [@PY]
+    LDI [@target_x]
+    LDJ [@target_y]
+    PTRACE
+</codify>
+**Why.** Rogueima's line of sight is 68 rays a turn, and the ray loop is about
+,000 of the 62,577 instructions a turn costs -- 48 ms at 1.3 MIPS. Each ray
+is roughly 540 instructions of Bresenham stepping and per-tile testing. As one
+instruction, a ray becomes "set ''I'',''J''; ''PTRACE''": three instructions
+instead of 540, and a turn drops to roughly 15 ms.
+**Where else.** The masks are what make it general. Projectile and thrown-object
+paths, wand and breath-weapon beams, monster targeting, swept collision in a
+tile platformer, and post-pathfinding line smoothing ("can I walk straight from
+here to there") are all this instruction with different masks and usually a
+''CH'' of zero.
+The application that makes it a platform capability rather than one game's
+helper is a **Wolfenstein-style raycaster**: one ray per screen column through a
+tile map, 320 rays a frame at 60 Hz. In software that is several million
+instructions a second, more than this machine has, so the genre is off the
+table. As an instruction it is about 19,000 a second plus the column drawing.
+**A design fork worth settling first.** Two different things wear similar
+clothes here:
+  * **Bresenham** visits the tiles a line passes through. Symmetric, integer,
+    and what line of sight, projectiles, targeting and collision all want.
+  * **DDA** steps to each grid //boundary// and carries the exact crossing
+    distance. That is what a perspective raycaster needs -- Wolfenstein used it
+    because Bresenham's nearest-tile approximation gives the wrong distance, and
+    a wrong distance is a wrong wall height and a fisheye.
+''PTRACE'' as specified above is the Bresenham walk. A perspective raycaster
+wants a sibling -- ''PCAST''? -- returning a fractional distance and which side
+of the tile was struck, for texture mapping. Trying to make one instruction do
+both would make both worse.
+The name deliberately says the job rather than the algorithm, so that the pair
+reads ''PTRACE''/''PCAST'' rather than ''PBRES''/''PDDA''.
+**Open questions.**
+  - Six registers in is a lot. Is a descriptor block at ''[FLX]'', the way
+    ''LSTEPM'' does it, a better fit for the array parameters, which are
+    level-scoped rather than per-call?
+  - Should it also report the tile it stopped ON versus the last clear tile
+    before it? Line of sight wants the blocker marked; a projectile wants the
+    square in front of it.
+  - Should a zero-length line (start == target) mark the start square?
+**Precedent.** No CPU precedent that I know of, but a strong coprocessor one:
+this is what blitters did. The Amiga blitter (1985) had a hardware Bresenham
+line mode, and the TMS34010 (1986) was a graphics processor with ''LINE'' as an
+instruction. It belongs to that tradition, which is where the rest of the PPU
+already lives.