x86(-64) machine code, 17 bytes
A function that simulates a SUBLEQ machine with 8-bit cells, returning to the caller with the array modified. Callable from C with the x86-64 SysV calling convention as void subleq8(int8_t *end, int8_t *aligned_start); (Like a .begin() / .end() range, the end pointer start+length.)
start must be aligned by 256 so its low 8 bits are 0. This allows indexing the array by replacing the low byte with x86 partial-register stuff, instead of needing to zero-extend the guest byte into a separate register and use an indexed addressing mode. (A similar trick is useful on 8-bit systems like AVR where two 8-bit registers form a 16-bit pointer: if you don't cross a 256-byte boundary, you can skip adc into the high byte; if the array is aligned by 256 you can just replace the low byte.)
start must be in the low 32 bits of virtual address space, e.g. the x32 ABI, mmap(MAP_32BIT), or simply a static array (e.g. in .data) in a non-PIE Linux executable. Or if you run the same machine code in 32-bit mode.
;;; array in ESI, aligned by 256 (so the low byte can be replaced to index into it)
;;; end-pointer (array+len) in EDI
subleq8:
89F0 mov eax, esi ; copy high bytes to EAX so merging a new low byte generates an address
.nextinst:
AC lodsb ; fetch address A into AL, forming an x86 pointer in RAX
8A 10 mov dl, [rax] ; deref A
AC lodsb ; fetch address B
28 10 sub [rax], dl ; SUB and set FLAGS
AC lodsb ; fetch branch target address; RSI points at next instruction
0F 4E F0 cmovle esi, eax ; update guest PC according to FLAGS
39 FE cmp esi, edi ; like cmp sil, dil but range-shifted: both regs have the same high bytes
72 F2 jb .nextinst ; len must be at most 127 to still consider *all* negative byte values as unsigned > 0x7f
C3 ret
Instead of checking for the subtraction result being negative or zero, we actually check if [b] was less-or-equal than [a] before the subtraction, using FLAGS set by the sub instruction (like cmp). This is the same as checking the result against 0 if signed overflow didn't happen, otherwise it's the opposite. With Python arbitrary-precision integers, signed overflow is impossible. (There is no x86 FLAGS condition for negative-or-zero so it would take an extra 3 bytes, either for cmp byte [rax], 0 or for cmovs + cmove instead of cmovle. Like most ISAs with signed-compare conditions, x86 does have a le less-or-equal condition that checks SF != OF || ZF in the same predicate.)
Apparently even Wikipedia defines a SUBLEQ OISC in terms of comparing against zero, rather than the usual computer-architecture meaning of a less-or-equal condition after a subtraction. :/ If signed wrap-around (overflow) doesn't happen, the two variants of the architecture are equivalent. Unless / until there's a test-case that requires checking the sign of the result instead of the LE condition generated by subtraction, I'm going to leave my answer this way. I'm pretty confident this is also Turing complete and probably not significantly different for implementing most basic arithmetic, if any of that comes near signed overflow.
The max program length is 127 or 128 bytes if you want any negative address to end the program. 126 is the highest multiple of 3, if your program doesn't do misaligned jumps and doesn't want to keep some data past the end of the last instruction. (It effectively treats the program counter as unsigned, looping do {} while(PC < end), so a negative program counter is an unsigned number in the upper half of range, above any signed-positive length.) Otherwise, max program length = 255, exiting only on PC=255, although that's untested and rollover of the high bytes of RSI could happen, but maybe only with misaligned jumps, e.g. to PC=254 so fetching the full instruction would get to PC=257, with lodsb carrying into the higher bytes of RSI.
(With len limited to 128, misaligned jumps are no problem. e.g. a program might use its first instruction to jump to address 4 and then use the first 4 bytes purely as data, eventually falling off the end when PC = 128.)
Tested with the test-case in the question; it's correct for that but it doesn't AFAIK test for off-by-one errors (<= vs. < in the SUBLEQ operation), or for exiting via a taken branch to a negative or past-the-end address. I think my program is correct, e.g. cmovle treats "equal" the same as "less-than", and the test-case does exercise less-than causing the branch to be taken.
x86(-64) machine code, 21 bytes
Simulates a 32-bit SUBLEQ machine. Writing a 32-bit register zero-extends to the full 64-bit register so even if we were willing to align the SUBLEQ program by 2^32 that wouldn't all the same partial-register trickery.
Even starting at absolute address 0 wouldn't work, because SUBLEQ addressing is in terms of cells, like a word-addressable machine. But x86 is a byte-addressable architecture, so SUBLEQ addresses have to be scaled by 4 to get x86-64 byte offsets since we're using 4-byte cells.
In x86-64 SysV, void subleq32(int32_t *end, int32_t *start). I think the start pointer might need to be 4GiB aligned to properly handle all jumps to negative addresses, since we only compare the low 32 bits after doing x86_address = base + target*4. With a larger base, some negative targets could wrap. And due to the scaling by 4, the most negative value we detect is -2^30. We shift out the high bits of some larger numbers, although some larger-magnitude numbers will happen to have a bit that gets shifted to the sign-bit position, too.
So maybe it's only really able to correctly simulate a 30-bit SUBLEQ machine, or 29-bit or something. But still much more than 8-bit, which is the point.
;; word-addressable SUBLEQ machine, where the components of an instruction are still 1 guest address apart
;; despite them being farther apart in x86-64
;;; base address in ESI
;;; end address in EDI (base+length in bytes, the one-past-end address. An x86 address, not guest words)
subleq32:
89F1 mov ecx, esi ; save the base for later use.
.nextinst:
AD lodsd ; fetch address A
8B1481 mov edx, [rcx+rax*4] ; and deref; we don't need it after this
AD lodsd ; fetch address B
291481 sub [rcx+rax*4], edx ; update [B] and set FLAGS
AD lodsd ; fetch branch target address; RSI points at next instruction for non-taken
7F03 jnle .not_taken
8D3481 lea esi, [rcx+rax*4] ; scale the SUBLEQ target address to an x86 address
.not_taken:
39FE cmp esi, edi
72EE jb .nextinst ; unsigned compare catches negative as well as past-the-end
C3 ret
I also tested this with dd instead of db for the initial array, using GDB print (int[12])prog32 after running, or display the same expression while single-stepping. This was my test caller:
section .data
prog32:
dd 3, 4, 3,
dd 6, 13, 9,
dd 6, 3, -3,
dd 7, 8, 3
prog32_end:
section .text
global _start
_start:
mov edi, prog32_end
mov esi, prog32
call subleq32
int3 ; software breakpoint
xor edi, edi
mov eax, 231
syscall ; x86-64 Linux exit_group(0)
x86(-64) machine code for a byte-addressable SUBLEQ, 17 bytes
Untested, but it's the same logic as the 8-bit version, with the same instructions except 32-bit operand-size. (So writing full registers instead of merging into the low byte).
The SUBLEQ program's cells are 4 SUBLEQ addresses wide, matching the x86 addressing. One way to make the test program run the same is to scale all its starting values by 4, like 12, 16, 12 | 24, 52, 36 | .... If you do misaligned load/store or jumps, it will expose the fact that it's a little-endian machine. (SUBLEQ doesn't have byte loads, only word loads.)
This requires the array to start at absolute address 0. Or in 32-bit mode, DS:0, so you could plausibly imagine some segmented code that sets the DS segment base for passing arrays. (Some "string" instructions use the ES segment, but lodsd uses ds:esi).
;; byte-addressable SUBLEQ machine
;;; base address = 0
;;; end address = len in EDI
subleq32b:
31F6 xor esi, esi ; start address = 0, can't justify having the caller pass it since we depend on it being 0
.nextinst:
AD lodsd ; fetch address A
8B10 mov edx, [rax] ; and deref; we don't need it after this
AD lodsd ; fetch address B
2910 sub [rax], edx ; update [B] and set FLAGS
AD lodsd ; fetch branch target address; RSI points at next instruction for non-taken
0F4EF0 cmovle esi, eax
39FE cmp esi, edi
72F2 jb .nextinst ; unsigned compare catches negative as well as past-the-end
C3 ret
A 16-bit version of this would be highly plausible in 16-bit mode where segmentation is normal, then it wouldn't be too weird to take an array at ds:0. Same machine code except for the ModRM.rm field that encodes [rax]... except there is no [ax] addressing mode, only [bx], [di], or [si] for single-register 16-bit addressing modes that use the DS segment. So that might cost a couple 1-byte xchg instructions, perhaps with BX.
16-bit addressing modes don't allow a scale factor so they're not very convenient for a word-addressable SUBLEQ.
