6502.org

Posted: **Sun Oct 28, 2018 9:53 pm**

I'd like to talk about creative uses of self modifying code. To start things off, I present some self modifying code from my Forth's kernel:

Code: Select all

// SCAN
HEX
CODE SCAN  ( A1 L1 C -- A2 L2 )
   0= # LDA,  HERE 24 + STA,
   3 # LDA,  SETUP JSR,
   AHEAD,
   BEGIN,
      N 4 + INC,
      0= IF,  N 5 + INC,  THEN,
      N 2+ LDA,
      0= IF,  N 3 + DEC,  THEN,
      N 2+ DEC,
   CS-SWAP THEN,   // AHEAD JUMPS TO HERE
      N 2+ LDA,  N 3 + ORA,
   0= NOT WHILE,
      N 4 + )Y LDA,  N EOR,  .A ASL,
   0= UNTIL,       // STORE DESIRED BRANCH HERE
   THEN,
   DEX,  DEX,
   N 4 + LDA,  0 ,X STA,
   N 5 + LDA,  1 ,X STA,
   N 2+ LDA,  PHA,
   N 3 + LDA,
   PUSH JMP,  END-CODE

CODE SKIP  ( A1 L1 C -- A2 L2 )
   0= NOT # LDA,
   ' SCAN @ 26 + STA,
   ' SCAN @ 5 + JMP,  END-CODE

This line in SCAN

Code: Select all

   0= # LDA,  HERE 24 + STA,

modifies the branch for the UNTIL, loop.
These lines in SKIP

Code: Select all

   0= NOT # LDA,
   ' SCAN @ 26 + STA,

modifies the branch in the same loop.
As chitselb said, Waddya think, sirs?

Posted: **Mon Oct 29, 2018 12:35 am**

JimBoyd wrote:

As chitselb said, Waddya think, sirs?

Glad you got it working, but there's room for improvement, I'd say. There are one or two spots where the code is a little scary (IMO).

To be fair, the sort of tricks you're using are a bit tough to pull off when the assembler is geared toward structured conditionals (such as IF - THEN and BEGIN - UNTIL). You end up being forced to invent workarounds to defeat the assembler's error-checking (which supports the elegant, nested conditionals). I'm not judging -- I've done stuff like this. But some of the ways of doing it turned out to be less ugly than others. That's my $.02 worth in terms of general comment.

Now, specifics:

Code: Select all

   0= # LDA,  HERE 24 + STA,

I don't fully understand this part. Is it Bill Ragsdale's assembler you're using? 0= is both a Forth word and an assembler word. What is the value you intend to load in A? Is it part of a PFA or a CFA, perhaps?

What's clear is that, at run time, the STA (up top) resolves a reference that's further down in the code. You could consider doing it the other way 'round, and doing it at compile time. IOW have code up top that leaves an address on stack or elsewhere, and the resolution would happen further down (writing to the address that was noted earlier). Because at that point the forward reference is resolved you can eliminate the dangerously error-prone 24 + that's used in the code!

(It seems odd and unnecessary that you're resolving the reference at runtime, but maybe you have a reason that I'm missing.)

[ Edit: alright, 0= # LDA, puts an opcode in A, is that it? (Hence the run-time operation.) Some additional commenting wouldn't hurt; this illustrates the point noted below. ]

Self-modifying code is a powerful technique, and it can be done fairly cleanly. The "pro"s can be pretty dramatic, but there are also "con"s to consider, and that's an evaluation that is best done on a case by case basis, IMO.

In most case you'll just modify operands -- not opcodes -- and thus the technique needn't be mind-bendingly complex.

I suspect SMC became stigmatized largely because it requires very careful commenting in the source code, and that effort wasn't always forthcoming. That's one main drawback. The others are:

SMC isn't reentrant
SMC needs to execute from RAM.
SMC might fail due to cache issues (and 6500 family processors obviously are exempt from this concern ).

-- Jeff
[2nd edit: clarity brevity courtesy]

Posted: **Mon Oct 29, 2018 2:50 am**

I'm always interested in SMC, as I think there's a lot of additional capability there that most of us have been neglecting. It does, as Jeff says, require really clear commenting. (Speaking of commenting, Jim, where did the // come from? The only standard ones I know of for Forth are the \ to tell Forth to ignore the rest of the line, and the ( to tell it to ignore everything up to the following ) on the same line.) I hadn't thought of using SMC to modify a branch (since I have not really spent time thinking/working out all the things that could be done with SMC). That's pretty cool. However, I, too, would certainly want the compiler to figure out the offset where to store whatever it is that's being modified.

I'm hoping my work will give me more time next year to take on some of these projects. It goes in waves, and this year has been busier; but I'm on the home stretch for my current work project. [Edit, 6/17/19: SMC article posted, at http://wilsonminesco.com/SelfModCode/ .]

Posted: **Mon Oct 29, 2018 5:15 am**

JimBoyd wrote:

I'd like to talk about creative uses of self modifying code.

Alright, this is pretty creative. I hope it's not too disappointing if I continue to focus on niggly details.

Here's one way to get rid of the hard-coded offset. At compile time we note the address where a dummy instruction operand has been placed; then later the genuine operand gets installed. The address is temporarily held in a variable, which regrettably isn't a very Forth-y way of doing things.

We could keep the address on stack, but the stack already has error-checking items getting pushed and popped, and the gymnastics -- SWAPs and whatnot -- to keep everything straight can get crazy pretty fast (and of course they do nothing to improve readability).

Code: Select all

0 VARIABLE NASTYSTASH // Part of the assembler. A temporary place to put stuff.

Code: Select all

CODE SCAN  ( A1 L1 C -- A2 L2 )
   0= # LDA,  // Get a BNE opcode in A
   6969 STA,  // Store it somewhere (not at 6969; that's a dummy operand to be validated later)
   HERE 2- NASTYSTASH ! // Make a note of where the dummy operand is.
   3 # LDA,  SETUP JSR,
   AHEAD,
   BEGIN,
      N 4 + INC,
      0= IF,  N 5 + INC,  THEN,
      N 2+ LDA,
      0= IF,  N 3 + DEC,  THEN,
      N 2+ DEC,
   CS-SWAP THEN,   // AHEAD JUMPS TO HERE
      N 2+ LDA,  N 3 + ORA,
   0= NOT WHILE,
      N 4 + )Y LDA,  N EOR,  .A ASL,
   HERE            // Address where the next opcode will appear.
   NASTYSTASH @  ! // Fix the STA instruction so it writes here.
   0= UNTIL,
 [ ... ] <snip>

I've only shown one NASTYSTASH variable, but NASTYSTASH2 and NASTYSTASH3 would be handy to have, as I see SKIP also refers to some hard-coded offsets.

You may prefer to give the variables different names than the ones I've chosen.

And luckily they get recycled. As part of the assembler, they have a one-time memory cost (not an incremental cost every time they're used). I apologize if I've drifted off-topic. This post has more to do with working around Ragsdale's structured conditionals than with self-modifying code per se.

Posted: **Mon Oct 29, 2018 6:04 am**

How 'bout a separate SMC stack? It wouldn't need much space.

Posted: **Mon Oct 29, 2018 8:32 pm**

GARTHWILSON wrote:

(Speaking of commenting, Jim, where did the // come from? The only standard ones I know of for Forth are the \ to tell Forth to ignore the rest of the line, and the ( to tell it to ignore everything up to the following ) on the same line.)

Alas, the Commodore 64 lacks a backslash key ( \ ), so I followed the example from Blazin' Forth and defined double slash ( // ) for a comment to the end of the line.
The Forth-83 standard also specifies .( to display the following text up to ) .

Posted: **Mon Oct 29, 2018 8:52 pm**

It's a pity, since the C64 lacks display width already. Is there a way to easily enter characters that aren't on the keyboard? For example, in DOS applications, I hold <Alt> while pressing 2 3 0 to get the Greek letter µ, or hold <Alt> while pressing 2 4 1 to get the ±.

Posted: **Mon Oct 29, 2018 9:16 pm**

Dr Jefyll wrote:

Code: Select all

   0= # LDA,  HERE 24 + STA,

I don't fully understand this part. Is it Bill Ragsdale's assembler you're using? 0= is both a Forth word and an assembler word. What is the value you intend to load in A? Is it part of a PFA or a CFA, perhaps?

Edit: alright, 0= # LDA, puts an opcode in A, is that it? (Hence the run-time operation.) Perhaps this illustrates the point noted below about very careful commenting.

Yes, it puts an opcode in A. The assembler uses Bill Ragsdale's syntax, but the assembler is one I wrote.

Quote:

Self-modifying code is a powerful technique, and it can be done fairly cleanly. Whether it's appropriate or not will depend on the situation -- the advantages and drawbacks needs to evaluated in every prospective instance.

In most case you'll just modify operands -- not opcodes -- and thus the technique needn't be mind-bendingly complex.

I noticed that the only difference between SCAN and SKIP was one byte! the type of branch used at the bottom of the loop. By using SMC I was able to save 40 bytes.
As for dangerous, this is from the source for my Forth kernel. It's built with a metacompiler that I wrote which runs on the Commodore 64. When I first got the idea for this, I tested it by compiling on the host and using SEE to make sure I got the address correct in both SCAN and SKIP.

Code: Select all

SEE SCAN
SCAN
  F44   D0  # LDA
  F46  F6A    STA
  F49    3  # LDA
  F4B  86A    JSR SETUP
  F4E  F5F    JMP
  F51   89    INC  N 4 +
  F53  F57    BNE
  F55   8A    INC  N 5 +
  F57   87    LDA  N 2+
  F59  F5D    BNE
  F5B   88    DEC  N 3 +
  F5D   87    DEC  N 2+
  F5F   87    LDA  N 2+
  F61   88    ORA  N 3 +
  F63  F6C    BEQ
  F65   89 )Y LDA  N 4 +
  F67   85    EOR  N
  F69      .A ASL
  F6A  F51 ^^ BNE
  F6C         DEX
  F6D         DEX
  F6E   89    LDA  N 4 +
  F70    0 ,X STA
  F72   8A    LDA  N 5 +
  F74    1 ,X STA
  F76   87    LDA  N 2+
  F78         PHA
  F79   88    LDA  N 3 +
  F7B  838    JMP PUSH
 OK

SEE SKIP
SKIP
  F87   F0  # LDA
  F89  F6A    STA ' SCAN >BODY 26 +
  F8C  F49    JMP ' SCAN >BODY 5 +
 OK

What makes using the hand calculated offsets worse is that I added labels to my metacompiler before I tried this.

LABEL creates a constant in the host dictionary ( so it doesn't disturb the target code ). The new constant has the address of THERE, the target's HERE in virtual memory ( the Commodore REU ).
I probably should have defined SCAN like this:

Code: Select all

// SCAN
HEX
CODE SCAN  ( A1 L1 C -- A2 L2 )
   0= # LDA,
   LABEL PATCH.ME
   BAD STA,           // STA TO DUMMY ADDRESS 2989
   3 # LDA,  SETUP JSR,
   AHEAD,
   BEGIN,
      N 4 + INC,
      0= IF,  N 5 + INC,  THEN,
      N 2+ LDA,
      0= IF,  N 3 + DEC,  THEN,
      N 2+ DEC,
   CS-SWAP THEN,   // AHEAD JUMPS TO HERE
      N 2+ LDA,  N 3 + ORA,
   0= NOT WHILE,
      N 4 + )Y LDA,  N EOR,  .A ASL,
   HERE PATCH.ME 1+ !
   0= UNTIL,       // STORE DESIRED BRANCH HERE
   THEN,
   DEX,  DEX,
   N 4 + LDA,  0 ,X STA,
   N 5 + LDA,  1 ,X STA,
   N 2+ LDA,  PHA,
   N 3 + LDA,
   PUSH JMP,  END-CODE

And SKIP should have been:

Code: Select all

CODE SKIP  ( A1 L1 C -- A2 L2 )
   0= NOT # LDA,
   ' SCAN @ 3 + @ STA,
   ' SCAN @ 5 + JMP,  END-CODE

SKIP still has hand calculated offsets, but they are small.
Note: I haven't tested this yet.

Quote:

I suspect SMC became stigmatized largely because it requires very careful commenting in the source code, and that effort wasn't always forthcoming. That's one main drawback. The others are:

SMC isn't reentrant
SMC isn't ROM-able.
SMC can entail caching issues (but those don't apply to 6500 family processors).

-- Jeff

Any code definition which uses the scratchpad area N isn't reentrant.
If I was writing this for a ROM-able Forth, I'd have to rewrite a lot more than some SMC.
If I was writing for a different processor family, there is a great deal I'd have to rewrite. I wouldn't think of trying something like this on an intel processor.

Posted: **Mon Oct 29, 2018 9:24 pm**

GARTHWILSON wrote:

It's a pity, since the C64 lacks display width already. Is there a way to easily enter characters that aren't on the keyboard? For example, in DOS applications, I hold <Alt> while pressing 2 3 0 to get the Greek letter µ, or hold <Alt> while pressing 2 4 1 to get the ±.

Not that I'm aware of and it's PETASCII so some of the characters are graphics characters.
On the Commodore 64, the characters look like upper case. using the shift key with one of the keys A-Z produces graphics characters.
shift 'm' does kind of look like a backslash, but if the shift and Commodore keys are pressed what displayed as upper case now looks lower case and the graphics characters now look like upper case characters. Having every comment to the end of the line begin with an upper case 'M' would be odd.

Posted: **Mon Oct 29, 2018 10:00 pm**

Dr Jefyll wrote:

I've only shown one NASTYSTASH variable, but NASTYSTASH2 and NASTYSTASH3 would be handy to have, as I see SKIP also refers to some hard-coded offsets.

My example of how I should have coded SKIP uses much smaller offsets. I don't see a problem with this as long as the offset is around half a dozen bytes or less ( skipping over maybe two instructions ).

Quote:

You may prefer to give the variables different names than the ones I've chosen.

And luckily they get recycled. As part of the assembler, they have a one-time memory cost (not an incremental cost every time they're used).

Using labels in the metacompiler has no cost to the target system.

Quote:

I apologize if I've drifted off-topic. This post has more to do with working around Ragsdale's structured conditionals than with self-modifying code per se.

Although my assembler uses Ragsdale's assembler syntax, my conditionals are somewhat different. I tried to make them as much like the high level Forth conditionals as possible for increased flexibility.

Code: Select all

SCR# B 
// ?EXEC NOT ?RANGE BRANCHES
HEX  FORTH DEFINITIONS
: ?EXEC  ( -- )  STATE @
   ABORT" EXECUTION ONLY" ;
ASSEMBLER DEFINITIONS
: NOT  ( CC1 -- CC2 )
   20 XOR ;         // REVERSE TEST
: ?RANGE  ( N -- )
   DUP 0< SWAP ABS +  7F >
   ABORT" BRANCH RANGE EXCEEDED" ;
 50 CONSTANT VS   // OVERFLOW
 90 CONSTANT CS   // CARRY SET
0D0 CONSTANT 0=   // EQUAL TO ZERO
 10 CONSTANT 0<   // LESS THAN ZERO
 90 CONSTANT >=   ;S NOT LESS THAN
>= ONLY CORRECT AFTER SUB, OR CMP,

SCR# C 
// THEN,
HEX
: THEN,  ( ADDR CS -- )
   ?EXEC  11 ?PAIRS
   HERE OVER C@
   IF
      SWAP !
   ELSE
      OVER 1+ -
      DUP ?RANGE SWAP C!
   THEN
; IMMEDIATE

SCR# D 
// IF, AHEAD, ELIF, ELSE,
HEX
: IF,  ( CC -- ADR CS )
   ?EXEC
   C,  HERE 0 C, 11 ; IMMEDIATE
: AHEAD,  ( -- ADR CS )
   ?EXEC
   HERE 1+ 1 JMP, 11 ; IMMEDIATE
: ELIF,  ( ADDR1 CS1 -- ADDR2 CS2 )
   [COMPILE] IF, 2SWAP
   [COMPILE] THEN, ; IMMEDIATE
: ELSE,  ( ADR1 CS -- ADR2 CS )
   [COMPILE] AHEAD, 2SWAP
   [COMPILE] THEN, ; IMMEDIATE
: WHILE,  ( A1 C1 -- A2 C2 A1 C1 )
   [COMPILE] IF, 2SWAP ; IMMEDIATE

SCR# E 
// BEGIN, AGAIN, UNTIL, REPEAT, BRAN,
HEX
: BEGIN,  ( -- ADR CS )  ?EXEC
   HERE  12 ; IMMEDIATE
: AGAIN,  ( ADR CS -- )  ?EXEC
   12 ?PAIRS JMP, ; IMMEDIATE
: UNTIL,  ( ADR CS CC -- ) ?EXEC
   C, 12 ?PAIRS
   HERE 1+ - DUP ?RANGE C,
; IMMEDIATE
: REPEAT,  ( ADR1 CS1 ADR2 CS2 -- )
   [COMPILE] AGAIN,
   [COMPILE] THEN, ; IMMEDIATE
: BRAN,  ( ADR CC -- )
   NOT 12 SWAP
   [COMPILE] UNTIL, ; IMMEDIATE

Notice the definitions of ELIF, ELSE, WHILE, and REPEAT,
BRAN, is used like this:

Code: Select all

CODE ?EXIT  ( FLAG -- )
   INX,  INX,
   0FE ,X LDA,  0FF ,X ORA,
   ' EXIT @ 0= NOT BRAN,
   NEXT JMP,  END-CODE

Since the high level conditionals and the assembler versions use exactly two items on the stack for control flow ( an address and a security code ), I also have the following which work with assembler or high level conditionals:

Code: Select all

SCR# 13 
// CS-DUP CS-DROP CS-SWAP CS-ROT
HEX
CREATE CS-DUP
   -2 ALLOT ' 2DUP @ ,
   IMMEDIATE
CREATE CS-DROP
   -2 ALLOT ' 2DROP @ ,
   IMMEDIATE
CREATE CS-SWAP
   -2 ALLOT ' 2SWAP @ ,
   IMMEDIATE
CREATE CS-ROT
   -2 ALLOT ' 2ROT @ ,
   IMMEDIATE

It is my hope that flexible conditionals and a straight forward way to manipulate the control flow data will make writing self modifying code easier and clearer

GARTHWILSON wrote:

How 'bout a separate SMC stack? It wouldn't need much space.

What about an SMC array? One name with a few places to store addresses.

Code: Select all

   HERE SMC !
        .
        .
        .
   HERE SMC 2+ !
        .
        .
        .
   HERE SMC 4 + !

[Edit: fixed incorrect comment for >= in the assembler]

Posted: **Tue Oct 30, 2018 5:02 pm**

JimBoyd wrote:

Quote:

I suspect SMC became stigmatized largely because it requires very careful commenting in the source code, and that effort wasn't always forthcoming. That's one main drawback. The others are:

SMC isn't reentrant
SMC isn't ROM-able.
SMC can entail caching issues (but those don't apply to 6500 family processors).

-- Jeff

Any code definition which uses the scratchpad area N isn't reentrant.
If I was writing this for a ROM-able Forth, I'd have to rewrite a lot more than some SMC.
If I was writing for a different processor family, there is a great deal I'd have to rewrite. I wouldn't think of trying something like this on an intel processor.

Yup -- understood. ( And W is another case where RAM is used in a non-reentrant way.)

Btw some of my points (like those you quoted here) aren't especially directed at you, in case you're wondering. There's still some FUD out there regarding Self Modifying Code, so whenever the topic comes up I try to shine a light on what the real issues are.

Interesting that you wrote an assembler using Bill Ragsdale's syntax. The code in Bill's version is interesting to say the least! I remember there was one particular word -- UPMODE -- which seemed to demonstrate rather a lot (arguably too much) cleverness!

-- Jeff

ps -- a link: 6502 Assembler in 96 lines of Forth (July 1980)

Posted: **Wed Oct 31, 2018 11:23 am**

I've following this discussion with some interest. I can't say that I have a strong opinion one way or another. Generally, I will fall on the side of avoiding SMC. Many of the reasons given here reinforce the idea that SMC should be avoided.

That being said, there has been a development, not necessarily recent, that appears to resurrect / rely on the use of SMC in every day programming. That development is the increasing reliance on lambda functions, closures, and other similar dynamically created code fragments / functions / procedures or whatever you'd like to call them. I see these dynamically created functions as SMC in the same sense as the approaches discussed in this thread.

Comments?

Posted: **Wed Oct 31, 2018 2:48 pm**

MichaelM wrote:

Many of the reasons given here reinforce the idea that SMC should be avoided.

Yup -- downsides and upsides. And the tradeoff should be evaluated on a case by case basis, since one situation can differ from another.

( In FIG Forth for 6502 I think there's only one occurrence of Self Modifying Code, and that's in the inner interpreter. The NEXT sequence is essentially a double-indirect jump. The 65xx instruction set doesn't directly support that, so instead a JMP (ind) is used, and the two-byte operand that follows the $6C opcode gets modified before the JMP (ind) is executed.

Along similar lines, I've read that some early computers lacked indexed address mode, so the programmers did indexing simply by coding the access to use absolute address mode. Then at runtime other code would compute the desired effective address and write that EA to the operand field of the absolute-mode instruction before it executed. It's typical of how SMC can offer escape from between a rock and a hard place. )

Quote:

That being said, there has been a development, not necessarily recent, that appears to resurrect / rely on the use of SMC in every day programming. That development is the increasing reliance on lambda functions, closures, and other similar dynamically created code fragments / functions / procedures or whatever you'd like to call them. I see these dynamically created functions as SMC in the same sense as the approaches discussed in this thread.

That's a good insight, I'd say. Not that I'm an authority on dynamically created functions. I'd be glad to hear more about this.

-- Jeff

Posted: **Wed Oct 31, 2018 5:31 pm**

MichaelM wrote:

ot necessarily recent, that appears to resurrect / rely on the use of SMC in every day programming. That development is the increasing reliance on lambda functions, closures, and other similar dynamically created code fragments / functions / procedures or whatever you'd like to call them. I see these dynamically created functions as SMC in the same sense as the approaches discussed in this thread.

This is completely different, simply by the fact that while you may have some mechanism of create dynamic functions, each instance is unique. You're not changing the functions themselves, you're replacing them.

A, perhaps, more relevant tact is code transformation such as in Java, notably when the code is loaded.

It is common in Java to have class loaders that augment the classes that they are loading. A typical use case it to manifest behaviors via techniques like "Aspect Oriented Programming". Simple examples is adding things like logging around implementations, or collecting statistics.

Most of these will change the byte code of the loaded classes at runtime.

Mind, once loaded, they leave them alone. It's more a part of the "loading and linking" phase than central to the execution of the code.

One could argue that systems like Forth, or any other "image" based system (Smalltalks, Lisps, even BASICs), are contingent on SMC. We just don't consider them such because of the limited, and formal approaches around them.

In Lisp and Smalltalk it's a Lisp and Smalltalk program that's actually changing the running image. In BASIC, it's a bit different as it's simpler to semantically separate the BASIC runtime from the running BASIC program (since the runtime is NOT BASIC).

Lisp, Smalltalk, and Javascript all have some mechanism akin to "eval" that will convert a string in to running code. Historically, the use of such a construct is frowned upon (as it's a bit of a large hammer), but it is available.

Posted: **Wed Oct 31, 2018 6:14 pm**

whartung wrote:

MichaelM wrote:

not necessarily recent, that appears to resurrect / rely on the use of SMC in every day programming. That development is the increasing reliance on lambda functions, closures, and other similar dynamically created code fragments / functions / procedures or whatever you'd like to call them. I see these dynamically created functions as SMC in the same sense as the approaches discussed in this thread.

This is completely different, simply by the fact that while you may have some mechanism of create dynamic functions, each instance is unique. You're not changing the functions themselves, you're replacing them.

At a lunch time discussion with a colleague, we came to the conclusion that the function code was pre-compiled, i.e. static. The operating data of the function was somehow dynamically constructed and at run-time linked to the relevant instruction stream. Can I assume that your definition of SMC is such that since the "functional" behavior is static, then the resulting dynamically constructed function is not SMC in the same sense as possible in FORTH where the instruction stream can be physically changed?

I've avoided these type of functions. It looks like now is a good time to explore how a modern C++ compiler implements these creatures. As I was posing the question above, I lost sight of how the instruction stream might be tied to the data that defines its desired behavior.

6502.org

Self Modifying Code

Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code

Re: Self Modifying Code