Programming Z80 using only printable characters - a challenge

I’ve been mulling over a challenge in constrained programming - an application has recently come to light which might benefit from printable Z80 code. That is, I was thinking of CALLING code embedded in a REM statement on an Amstrad CPC (emulator here), to act as a bootstrap for this coprocessor adapter by @Revaldinho:

image

A REM statement should be a convenient and dense way to get a little bit of machine code into a machine, but whereas Sinclair’s machines allow easy entry of pretty much any byte value into a REM, I think Locomotive Basic doesn’t. And whereas I’m familiar with the x86 being programmed using only bytes in the range 0x20 to 0x7e, it seems a little challenging on the Z80.

According to this opcode map, we do get all sorts of register moves and load and store, and inc and dec, and even a doubling operator, as well as a small handful of conditional jumps. And we get a complement instruction. But for a backward jump, or a return, or an IN, we will need an unprintable byte, so I think we’re forced to construct or modify some code bytes in a preamble.

Hmm, but it might turn out that the resultant REM statement is so long that a simple Basic equivalent will be easier to type in… as this is only a first bootstrap, performance isn’t an issue. For example:

FOR A=1024 TO 1048
POKE A,INP(&FD80)
NEXT
CALL 1024

(I’m deliberately keeping this very simple: open-loop communication with no checking, and just pulling a specific constant number of bytes. The coprocessor provides the bytes, and they form the second level of bootstrap which can run a bit more robustly and generally, to load the third level, or maybe the application.)

See also the previous discussion in Communications on Toshiba T1000 laptop, where we found several links about programming the x86 using only printable ASCII (or even, only ECHOable ASCII). And for entertainment here’s a video about a 20 page text file which contains its own source code, its rationale, and is also a DOS application:

2 Likes

This is a fascinating “little” problem: Stepping up to Turing complete. Do you have any means of assembling and storing additional instruction codes?

A place to look for prior art may be TRS 80 Model 100 archives: the Model 100 had a compatible 8085 and the original modem software was good for transferring printable characters only. (Most utilities to address this were written in BASIC.)

Another idea: using integer arrays in BASIC. These were usually stored sequentially as 16-bit (double-byte) arrays in memory. If you can figure out the absolute address of an array (which may be easy for the very first variable defined, even if there’s no command to get a RAM-pointer), you can put any code in it, since it will accept aribitrary numerical values. (You’ll have to resort to negative numbers for any values involving the sign bit of the first byte of an individual integer value, though.) Then just run the code from its known address in variable RAM.

(This is also a nice trick for passing complex data between BASIC and any ML routines or even for modifying ML code from within BASIC by a simple assignment.)

I was once considering similar for a simple drawing routine in a cross-plattform BASIC game, (As it turned out. assignments of any kind [including POKE] in MS BASIC are that slow that any speed advantages from doing it in ML [as compared to using the serial OUT command] were vanishing instantly, so I never used it.)
See Retrochallenge 2016/01: M10 – PC-8201A Maze War (E-09) for details.

1 Like

I am toying with ideas of using the Basic program as data, or even as code - for example the line numbers are bytes I can control, and there might be tokens with useful byte values, if the line is syntactically acceptable. It even seems possible that integer constants appear in memory as binary.
Technical information about Locomotive BASIC

1 Like

Using line numbers as a resource is quite ingenious, as is the entire idea of a valid BASIC program that’s also the ML runtime! It won’t be especially elegant ML code, but it may be good enough for some kind of initial loader.

Edit (rather off-topic): this may be the proposition for an interesting C64 programming contest, BASIC programs that double as their own sprite data, no extras allowed.

1 Like

As long as the Z-80 program knows where it loads into memory (so it may self-modify) it is theoretically possible.

L register can be loaded with any value simply by loading with a base value and supplying sufficient INC L or DEC L alterations. Though we can be far more efficient applying ADD HL,HL.

We can load L register into any other 8 bit register. So DE can be loaded with any memory location. Therefore we can fill a chunk of memory with any bootstrap code we like. Just fill a code block after then end of our constructor code and fall into it.

For a larger program to be ASCII encoded I’d think a two (or maybe three) stage bootstrap would be best. Here’s what I came up with for a decoder that will take two safe bytes and output any byte:

lp: ld  a,(hl)
    add a,(hl)   ; $86
    inc hl
    add a,(hl)   ; $86
    inc hl
    ld  (de),a   ; $12
    inc e        ; $13
    jr  nz,lp    ; $F7

$86 is easy to generate. $12 is harder but then we get $13 for free. This loop will output 128 bytes of code. If that’s not enough for the application then we could use it to encode an even larger program with much tighter packing – say at least 6 bits per safe byte.

The suggested bootstrap code is small enough that simply patching it will suffice. Start with this code. It gets more data than the BASIC program which I assume will not be a problem. It makes for a simpler loop which minimizes fixups:

	ld	hl,$400
	ld	bc,$fd80
lp:	in	a,(c)		; $ED $78
	ld	(hl),a
	inc	l
	jr	nz,lp		; $FA
	jp	(hl)		; $E9

Fix up all the unsafe bytes. For convenience I’ve assumed that the program starts at a very convenient $4040. Add extra code as necessary if the load address is not so nice.

	org	$4040
start:
	ld	l,$76
	add	hl,hl
	inc	l
	ld	d,l
	ld	hl,lp
	ld	(hl),d

	ld	hl,$747D
	add	hl,hl
	inc	h
	ld	d,h
	ld	e,l
	ld	hl,js+1
	ld	(hl),e
	inc	hl
	ld	(hl),d

	ld	hl,$7E40
	add	hl,hl
	inc	h
	ld	b,h
	ld	c,l

	ld	hl,$2020
	add	hl,hl		; $4040
	inc	h   		; $4140
	add	hl,hl		; $8280
	add	hl,hl		; $0500
	dec	h

lp:	;in	a,(c)		; $ED $78
	defb	$20,$78
	ld	(hl),a
	inc	l
js:	;jr	nz,lp		; $FA
	;jp	(hl)		; $E9
	defb	' '

Or in its pure ASCII form (don’t forget the space at the end!):

.v),U!e@r!}t)$T]!j@s#r!@~)$DM!  )$))% xw, 

FOR A=1024 TO 1048:POKE A,INP(&FD80):NEXT:CALL 1024

Adding the REM, CALL and such it may be shorter though I know I’d rather type the BASIC code.

Since there must be a keyboard buffer I would think this could do:

CALL 1234:.v),U!e@r!}t)$T]!j@s#r!@~)$DM!  )$))% xw, 

Where 1234 is the start address of the program.

Seems likely that CALL will enter the program with HL set to the start of it giving a potential opportunity to save bytes. And there may be ways to save on the calculations of the unsafe bytes.

I like the idea of using BASIC tokens to get more bytes available. You may even be able to take advantage of ROM subroutines.

I’ve been thinking about this sort of thing lately. What’s a minimal bootstrap if the device can help out? For a TRS-80 Model 3 I came up with:

?INP(128)
POKE16406,147:POKE16407,64

The first INP(128) has the side effect of creating a subroutine in RAM that reads port 128 into A and returns. The next two pokes change the keyboard DCB so it uses that subroutine for input. BASIC will drop back to the prompt and start reading in bytes from port 128 as if they were typed on the keyboard. The device can then send whatever BASIC commands it needs to bootstrap.

The Model 3 is a bit of a special case here. First, the ROM creates a RAM subroutine for INP because they didn’t upgrade that from the 8080 version which cannot read from port BC like the Z-80. And it is lucky in that the first poke changes the DCB read address to something safe as the keyboard is scanned before the second POKE. That is purely a matter of luck that the change of the address in two steps can happen.

2 Likes

Wow! That’s very substantial thanks @gp2000!

Very nice little free bit of help there! In my own (vague) thinking I’ve moved away from being too platform-specific, so using Locomotive Basic’s in-memory layout, or using ROM routines (which I hadn’t thought of) now feels like something I wouldn’t want to do.

(And thanks @NoLand for your reply and link to your adventure.)

As noted, then, we need neat ways to construct byte values $ED, $E9, $F8, $80 as well as a distance for a backward branch. And we need to store those bytes into appropriate places, which I think means constructing addresses somewhere near the range $0178 to $0190 - that’s nearabouts where a one-line Basic program lands. I’m not sure where an immediate-mode Basic one-liner lands.

(For the second stage, which is to say the destination to store the downloaded code, I was vaguely thinking of placing the routine at $2020 but it might well be that $4040 is just as handy.)

Construction of any 8 bit value can be done in 5 bytes.

$20 … $7E - two byte LD L,N
$7F … $FD - three bytes: LD L,N/2; ADD HL,HL; INC L if N odd
$FE - four bytes: LD L,$7E; INC L; ADD HL,HL
$FF - five bytes: do $FE; INC L
$00 … $1F - six bytes: consider as binary value xxxyz:
if either y or z is 0 then
LD L,%01000xxx
ADD HL,HL
INC L ; if y == 1
ADD HL,HL
INC L ; if z == 1
otherwise (y == z == 1)
LD L,%01000xxx
ADD HL,HL
ADD HL,HL
DEC L

Keep in mind that LD A,N and LD A,N; CPL give 3 byte encodings which may be helpful if only because the value starts in A register. There may be something to be gained with SCF and DAA for $00 … $09 and $10 … $19. The SCF is needed to set the state of the carry, half carry and N flags. But having established their values you could use DAA directly.

I used your idea of an uncommented line to take advantage of BASIC tokens. On the TRS-80 Model 3 it means that almost all of $80 … $FF becomes available. One expected constraint is that you can’t use, say, A, N, D in sequence since that will be tokenzied. Even if inside a word: TANDY will be tokenized as ‘T’, AND token, ‘Y’. However, most tokens can be broken up by salting in ‘#’ (INC HL), ‘+’ (DEC HL) and many others.

I’d forgotten that it uppercases all data considered for tokenization (i.e., outside a quoted string). Losing ‘a’ … ‘z’ is bad – no stores to (HL). Would bloat most code. There’s some fun tradeoffs, too, in that a $80 … $FF value may be anywhere from 2 to 7 characters to type the full token. Optimizing for length becomes quite tricky.

Its BASIC also lacks the ability to type in these: ~ ] { } \ |

I started thinking about optimizing code sequences for typeability but decided best not to think too much about that.

Update: These are tokens, too: + - * / [ > = <
And I’d forgotten that you can type in [. You get it pressing up arrow which, on the Model I’s non-standard character set was an up-arrow character. The Model III uses ASCII and it show as a left square bracket. In short, the constraints are even more baroque.

Update: Only 5 bytes needed for any byte. Using DEC L the 6 byte sequences for $3, $7, $B, $F, $13, $17, $1B, $1F can be reduced to 5 bytes.

1 Like

Nice constructions!

I had a couple of ideas. One is to store the payload immediately after the one-liner, so we can just fall through. The other is to fetch the awkward backward branch offset as the first byte of the payload.

I found an online disassembler which can take the hex and show us the corresponding code. (Also an online hexdump tool in case one has no command line to hand.) And, to make any progress, an online assembler here.

In the case of a saved one-liner like
10 CALL x: REM xyz
the first byte of the bootstrap, for Locomotive Basic on the CPC, is at 380 decimal, or 0x17C, so that would be my ORG. The code byte offsets are going to be a bit more difficult to construct than the ones following 4040 - which might eat up all the apparent advantage. I need to place the prefix byte for the IN, and to place the first payload byte.

It seems to work out nicely though, and a bit shorter:

FOR A=1024 TO 1048:POKE A,INP(&FD80):NEXT:CALL 1024
.v),U!e@r!}t)$T]!j@s#r!@~)$DM!  )$))% xw, 
.v),U!e@))r!@~)$DM!f@)),@xw, 
10 CALL 380: REM .v),U!e@))r!@~)$DM!f@)),@xw, 

(Again with a trailing space)
It even beats a (very slightly) shortened Basic version:
FOR A=900 TO 933:POKE A,INP(&FD80):NEXT:CALL 900
although I think that version would be a great deal easier to type in!

Here’s the listing:

017C                          .ORG   $17c   
017C                START:    
017C   2E 76                  LD   l,$76     ; create an $ED prefix byte
017E   29                     ADD   hl,hl   
017F   2C                     INC   l        ; $ED in l
0180   55                     LD   d,l   
0181   21 65 40               LD   hl,$4065  ; create fixup address
0184   29                     ADD   hl,hl   
0185   29                     ADD   hl,hl   
0186   72                     LD   (hl),d    ; fixup the IN instruction
0187   21 40 7E               LD   hl,$7E40  ; create the port address $fd80
018A   29                     ADD   hl,hl   
018B   24                     INC   h   
018C   44                     LD   b,h   
018D   4D                     LD   c,l   
018E   21 66 40               LD   hl,$4066  ; create payload address $0199
0191   29                     ADD   hl,hl   
0192   29                     ADD   hl,hl   
0193   2C                     INC   l   
0194   ED 78        LOOP:     IN   a,(c)     ; needs prefix $ED
0196   77                     LD   (hl),a   
0197   2C                     INC   l   
0198   20 FA        BRANCH:   JR   nz,loop   ; backward branch $FA

Clever idea bringing in the backwards branch offset just in time from the device. Also nice to avoid the JP (HL).

I can almost save a byte in the code by noting that the payload address can be calculated from the $ED fixup using 5 x INC HL instructions. Do the BC calculation first. But it moves the fixup address down to $193 which adds a byte to its calculation – same as $194 but with a DEC L or DEC HL added.

Still, the “#####” for the HL increments improves typeability.

It could all work out if the 3 spaces in the line could be dropped:

10 CALL380:REM.v) etc.

Maybe that isn’t legal in Locomotive BASIC?

Could the sequence be entered directly on the command line? The keyboard buffer addresses may be more favorable. It terms of code golf it would save entering the line number and typing RUN.

Thinking about this a bit more there is another potential byte saving. The last few lines are:

      INC L
LOOP: IN  A,(C)
      LD  (HL),A
      INC L
      JR  NZ,LOOP

That could be reduced to:

LOOP: INC L
      IN  A,(C)
      LD  (HL),A
      JR  NZ,LOOP

As long as the boot code loaded from the device ends with a 0. Writing Z-80 code with no zeros tend to be fairly easy what with XOR A available. Or SUB A depending on your accent.

It also means that only 4 x INC HL instructions are needed to move from $ED fixup to the payload.

Well, maybe there are savings to be had. It’s all so delightfully sensitive to the slightest change.

1 Like

Interesting thoughts!

I think it isn’t - I tried this in the emulator.

This might be fruitful but I don’t know where the buffer address is (or how to find it.)

I like this one! Having the next level of bootstrap avoid zero bytes feels like no big constraint.

Ah, yes, trying out the emulator I see that it insists on REM having a space after it. However, it does support ' as an alias which does allow a non-space character immediately after and anything before. :REM --> ' will save four typed characters. Internally it may not be a single token.

Indeed, peeking about I see REM is token 197 and ' is token 1 followed by token 192. Token 1 is : best I can tell. I’ve seen that trick before. Single quote is translated so that it has the statement separator before it so it isn’t a special case but upon LISTing the program it knows to drop the : as it can tell between a single apostrophe and :REM.

Anyhow, using ' will move the start address back one overall.

I think the keyboard buffer is at 64 decimal. Here’s the program I wrote to find it:

10 a=peek(i):i=i+1
20 if a=65+j then j=j+1 else j=0
30 if j=3 then ?i
40 goto 10

run:"ABC"

Some more PEEKing about confirmed the calculation.

That should be quite a boon. The CALL address will be one byte shorter. And once the fixup address is in HL a two-byte safe LD L,n will get you to the payload. If we’re really lucky the $80 that ends up in L after the port calculation can be put into H where ADD HL,HL will get 0 in H. But I think that will only save if the fixup address is divisible by 2.

We’ll lose the INC L saving but can’t win 'em all.

Holding down a key confirms the keyboard buffer is 256 bytes so they should be plenty of space to load the next level bootstrap.

1 Like

Very nifty! With your Basic probe, I think I’ve found that
CALL 73'printable code
should line up correctly.

Looks like it should be CALL 70.

To test this I wrote a small “safe-80” program to put 126 in the top left of the bitmap screen:

	LD	HL,$3040
	ADD	HL,HL
	ADD	HL,HL
	DEC H
	LD	(HL),$7D

On a fresh emulator restart a POKE 49152,126 shows us what to expect. Restart the emulator and do:

CALL 70:!@0))%6}

Amazingly, it doesn’t crash. It must run into a RET or something before going into deep space.

The process of figuring this out was a bit convoluted, but essentially I did this:

10 FOR I=64 TO 80:? PEEK(I);:NEXT
POKE 57,201
CALL 57:RUN'ABC

The abbreviated output was:

131 32 25 57  1 202  1 192 65 66 67

The commented out part starts as offset 72 which will be 70 if the :RUN is removed.

I then picked a safe spot to poke 201 into a BASIC program and found that token 201 is RETURN. Kudos to whoever arranged that the BASIC token value of RETURN is the opcode for the Z-80 RET instruction!

This led to a compelling but not conclusive test:

CALL 69:RETURN

It gets back from the call and complains about the RETURN not having anywhere to return to.

BTW, the tokenization of CALL 57 may look a little odd. It’s because the second generation BASIC interpreters store numbers in binary format. The 25 is a token indicating the number is stored as one byte. I initially looked at a CALL 9999 (having done a POKE 9999,201) which I think was 131 32 26 15 39. The 26 introduces a 2 byte, little-endian number.

Hilariously I chose 57 because I knew 56 ($38) is the standard interrupt vector. I meant to try 55 but for some reason added one instead of subtracting. But it turns out the locations aren’t critical. Why I didn’t chose somewhere near the end of the keyboard buffer is a mystery.

Hmm, so the keyboard buffer is really a tokenised version of the keys typed in? And yet the line doesn’t have to be syntactically correct, only the first :-delimited component?? So, partially tokenised?

Certainly is amusing that RETURN and RET are the same value.

I like the coining of ‘safe-80’!

I imagine the keyboard buffer situation is the same as other BASIC’s. A line input routine takes keystrokes and fills the buffer. When you press ENTER BASIC tokenizes the entire buffer over top itself. It can safely do that since tokenization never expands the input.

Then it checks if the line starts with a digit. If so the line is inserted into the BASIC program. Otherwise the line is executed immediately. Since it is interpreted you only get a syntax error when encountered. Or, put another way, tokenization doesn’t do any syntax checking.

1 Like