6502.org

For obscure reasons (background below), I got interested in this problem:

We need a relocatable 256 byte 65c02 code sequence where I can safely JSR to any of the 256 locations and have the IP eventually advance to the final location (all roads lead to `rome` ...), without changing any memory location nor the X register.

A naive solution is to fill the 256 locations with NOP ($EA), but that requires an average of 2*128 cycles to get from a random landing point to the end of the region. i.e.
What's the best average number of cycles you can come up with? What if you can't use 65c02 opcodes? I have a version with a ladder of BRA instructions using offsets that are also safe landing instructions which averages about 10-12 cycles.

Background: thinking about more compact literals in TaliForth, which are normally coded as JSR literal_runtime / lsb / msb, i.e. 5 bytes per literal. For byte-sized values, we could instead use JSR (rome - value), capturing the literal value in the JSR address (so 3 bytes instead of 5) which we can peek via the return address on the stack. I don't necessarily think it's a very useful solution but is amusing to think about.

Some mixture of BVC and BVS should, I think, get close to your BRA example.

That sounds optimal, or very close to it. If I understand the situation properly, the return address on the stack will be conveying information about the address of the LIT, not the value of the literal you want to push.

right, after JSR (rome - value) the return stack has the address of MSB, so one byte earlier is the LSB from which we could infer value

I am a little lost here since if you already know the value, why would you need to infer it?

But here is an ideaa. Fill the entire 256 byte page with RTS ($60). Then any location can be caluclated with:

JSR location

...

TSX
LDY $00FF,X
LDA $0100,X

and Y becomes the value if on a page boundary, or if not, then subtract Rome lo-byte from this Y value (lo-byte) to get the infered value. It is assuming that Rome is always at the end of the 256 byte page.

i should have explained the context a bit more. It arises when compiling forth code like "3 2 + .", which results in something like this:
so each literal compiles to 5 bytes (where the `literal` routine uses the caller's return address to grab the 16-bit word and push it on the forth stack, returning 2 bytes further).
Many literals are byte sized, so have been looking for a scheme that would use less space to compile small literals. Obviously a separate `literal_byte` could save one byte by knowing to extract only one trailing byte. The `rome` idea is another probably impractical idea. it would replace `literal` and use the caller's jsr address to infer the literal, so use only 3 bytes per compiled literal, but 'wastes' 256 bytes for the landing pad. Another possibility would be to hijack BRK and use the isr to extract trailing data byte(s). But that seems extreme. other suggestions welcome!

If I understand what you're trying to do, your proposed solution is very general, capable of handing a lot of small values. It might be better to figure out just which ones are likely to be used. Zero and one, perhaps minus one and two as well. Making each one into its own subroutine might save space.

LDA #immediate, PSH, LDA #$00, PHA, RTS (or reverse the order if the high byte should be first) is seven bytes. In 256 bytes there's enough space for 37 routines like that.

Clever coding might get you even more. How many are really common enough to be worth it?

yup, that's true, and the current approach has dedicated words for zero, one, and two iirc.

The Forth I use has a CLIT which is very easy to implement. The routine fills in the hi-byte with a zero for you. And the compiled code is JSR CLIT followed by one byte instead of 2.

Aother idea is create math routines that treats the literal as two single 8-bit bytes instead of a 16-bit word. It would basically compile to:

Not a general solution for all 8 bit values, but for 64 values, one could fill the 256 bytes with: Then call as:
Four bytes per literal in the 256 page. Note that my branch trampoline offset for the first 32 entries may be off a bit, I'm thumb nailing this as I go along Also expecting there to be a specific word for ZERO.

I kind of did this for PLASMA where the first 32 byte codes represent a constant nibble value (no odd byte codes, so had to double it)

Oh, and the Pascal p-code interpreter does this for the first 128 byte codes (constant 0 through 127). The Java VM does something similar for constants -1 to 5.

If you're soliciting extreme suggestions then I am game for the challenge!

What I'll describe is a novel encoding for CLIT (and it's also adaptable for LIT). It's very small and very fast, but there's a unusual requirement which, depending on circumstances, may or may not be deemed acceptable.

Usage is like this... ... and cliteral looks like this. So, yeah... There's no RTS!

Instead, execution jumps to the last byte of the JSR instruction, which of course is its ADH operand... except now it gets digested as an opcode.

And most of you already know this next trick. Certain two-byte instructions opcodes such as CMP immediate -- whose opcode is $C9 -- can be used in place of a BRA when the goal is to skip forward by one byte only. In this case, and using $C9 as an example, the last byte of the JSR instruction is arranged to be $C9, and the CPU parses the $C9 and the one-byte inline parameter as a 2-byte, CMP# instruction. To us, the CMP functions as a NOP. Its only purpose it is to harmlessly guide the CPU to the code that follows the 2-byte CMP# instruction. This all works wonderfully smoothly, but we need cliteral to be mapped to an address whose high-byte is equal to a suitable opcode.

Luckily there are plenty of candidates! CMP#, CPX#, CPY# and BIT# are acceptable because Tali won't mind if the flags get altered. And AFAIK Tali can also tolerate LDY#; likewise LDA#, ADC#, SBC#, AND#, ORA# and EOR#.

And, for 65C02, the opcodes $02, $22, $42, $62, $82, $C2 and $E2 are also acceptable, because they are all 2-byte, 2-cycle NOPs. (The 65C02 has other intriguing potential in regard to NOPs; I wrote about that subject here.)

None of the 2-byte instructions mentioned so far will access memory (other than the 2 cycles accessing memory at PC). But at the cost of one or more extra cycles, a bunch of additional candidate 2-byte instructions become available, such as BIT z-pg, LDA z-pg,x and CMP (ind),y. Just be aware that the extra memory accesses can be dangerous if there's I/O in the system whose state may get altered by an unexpected read.

Finally, opcodes for certain three-byte instructions can be used in place of a BRA when the goal is to skip forward by two bytes. This means the inline value after the JSR could be increased to 16-bit (as required by LIT). And, as above, there's a read that occurs which adds delay and could touch I/O.

-- Jeff

this is a nice way to avoid manipulating the return address to make cliteral faster.

in my use case I care more about space than time, so another approach I've been fooling with is to prepend
`jsr literal` before the definition of certain compiled words that are often preceded by a literal, e.g. "+".
When compiling "1 2 +" the compiler would normally generate but if we've defined plus as then it's easy for the compiler to notice that it's just emitted a literal when it's ready to emit "+", and could rewind to instead write: this costs a few bytes per targeted word but often saves 3 bytes (or 4 if you handle cliteral as well). this strategy folds any literal into a subset of words, rather than optimizing a subset of literals for any word. in the code base I looked at you only need to tag a few dozen words with the prefix to fold about 80% of literals away.

TaliForth is very nice, but if you're really all in for the highest code density you're gonna have a hard time beating Charlie's DTC PETTIL, even though he limits himself to the NMOS instruction set. It's no slouch in the speed department either.

Take 2:
You could always fill the page with $4C. At location $4C4C, put a JMP ROME there. Probably pretty hard to stick a jump like that in the middle of the address space like that.

However, I think there are better ways than trying to encode the literal into the JSR address.

Bytecode VM?

the one I use would compile that into 2 bytes:
Maybe in your case a set of JSRs to load small constants to the stack might help? This one has instructions to load 0 through 10 and minus 1, and add 1 through 5. (as well as a few subtracts. 1 through 4) although it's not Forth.

-Gordon