Post by edorfaus in Code sharing megathread

Viewing post in Code sharing megathread

It's not a small feat? Aw, but I tried to make it as small as I could... ;)

As for efficiency, well, mine might be more space efficient than yours regarding image size (though not in program size), but it wouldn't take much to make yours far more time efficient (as in fast). Simply remove the MOVI/PMOV/MOVO triplet and replace the IFJMP/JMP combo with the opposite IFJMP, and it would be down to a very tight 4 instructions per pixel. (To be honest, I've been wondering if this easy optimization opportunity was left in as an easter egg.) I don't think anything tighter (aka faster) than that is possible with the current instruction set, at least without ending up in an infinite loop (which might also cause a black pixel at 0,0). And as a bonus, yours can do animations. All that, in just 11 instructions (if you also move the DATACs). And unlike mine it doesn't assume the initial values of the registers - if it did, it could be just 8.

Besides, while your image format is larger than mine, I don't think it is anywhere near as bad as the image format I came up with in my youth. This was in the DOS era, on an 80286 I believe (16-bit real mode), and I had discovered the (probably 0xA000) memory segment for the video memory, but didn't really understand how it worked. I had library routines that let me draw to the screen, but I wanted to save the drawn image to disk and then load it again later. The obvious way was to do a simple memory dump/restore. I don't remember the exact details, but I think that the image didn't fit inside the offsets of that first segment, so I had to loop through both the segments and offsets until I had enough data for the entire image. So far so good, but in my ignorance I looped through the full 16-bit range of the offsets, for each of the relevant segments. What I hadn't realized is that the segment size was 16, not 64K. Which means that the segment:offset address A000:0010 refers to the same memory location as A001:0000 does. In other words, there ended up being a lot of redundant information in that image file format, and for no good reason... (These days, I'm not sure whether to be more embarrassed or amused.)

The idea about loadable levels is a good one. It also gave me a kinda similar idea: loadable peripherals (to be attached to SETDATA/GETDATA ports). Using something like embedded Lua, it could be possible for people to write their own peripherals (could even have an in-game editor if you wanted to), that could do nearly anything - expanded memory, a coprocessor (8087 anyone?), a port multiplexer, even some kind of networking (fake or real). Imagine a custom mode where you have two (or more) TC-06 computers, and a homegrown peripheral for networking them together. :D (Oooh.... Or a multi-processor machine. Imagine the chaos (and obfuscated code) you could generate by "self"-modifying the code the other CPUs are running, in realtime... :) )

I'm not sure if such custom peripherals could provide "physical" objects for the 3D environment, for user interaction, as I don't know enough about gamedev/3D/etc. to say whether it would be realistic to do that via such a scripting language - but many possible peripherals wouldn't really need that anyway. Of course, if it can be done... virtual blinkenlights anyone? :)

Those peripherals wouldn't necessarily be intended to make the player's life easier either - someone could e.g. make a disk peripheral that it takes a few cycles to read from or write to, like it does for real disks, and then the player has to handle that response time in their code to succeed on that (custom) level.

CliffracerX6 years ago

I wish it was an easter egg! I'm still learning my way around Assembly, and that was genuinely the best win screen I could think of at the time. One thing worth noting about IFJMP and JMP - they will immediately run whatever they jump to, essentially meaning they take no clock cycles. Realistic? Probably not. But an important quality of life feature? Definitely. At the low speeds the TC-06 runs at, every IFJMP requiring a full clock cycle just to get to whatever it's supposed to run would have a drastic performance impact.

As for image format sizing, honestly, I'd just say to have a giggle about it. Everyone does goofy stuff when they're still learning their way around computers - I know I did! Took an embarrassingly long time for me to learn that file formats are more than their extension - I got started with modding Morrowind waaaaay back in the day, and I, on several occasions, tried to make "models" by renaming various image files and such. Wasn't till a bit later that I found Blender and got started actually modeling.

On modded peripherals? I'd love to. Adding new 3d ones might be harder, but I think it'd be doable. I KNOW I want to ship a functioning network peripheral (or several) for use in the base game, and then work on making some kind of internet system go with it (like TCP/IP) - making the grand finale of the built-in levels be an actual hacking mission or something would be super cool. Given my noobness at Assembly, I have a feeling it wouldn't be that hard to break, even for the average player. As a bonus, with actual over-the-internet support for the network peripheral, you could even engage in hacking battles with other players, which would probably be tons of fun.

edorfaus6 years ago

... Heh. You just led me to finding an easily reproduced crash. (Well, I can reproduce it easily anyway, and I expect you can too.)

One of my first thoughts on hearing that fact about IFJMP/JMP was not so much that it wasn't realistic (which it indeed isn't), but that it was risky. So I decided to test what I had in mind, to see what effect it would actually have. I figured it could be anything from already being handled, to locking up in an infinite loop, to crashing (which is what it turned out to be).

Up to you how to fix this (assuming you don't want to keep that crash), there are ways to do it without making these instructions take a cycle. (Though those ways are probably more complicated to implement, depending on how your code works right now - I haven't really looked at it.)

I'll also note that this crash only happens with JMP - the equivalent test case with IFJMP seems to take a cycle on each instruction in the debugger, and doesn't crash the game without the debugger either. As far as I can tell, it takes a cycle whether or not the condition matches. So, are you sure it isn't just JMP that has this behaviour?

Test steps: with the computer selected, enter the following program, compile it, compile to ROM, and start the computer. (If in debug mode, click the step button.)

JMP 0 1
JMP 2 1

Expected result: Game continues to work fine; virtual computer can be turned off to change the program, etc.. (If in debug mode, debugger continues to work.)

Actual result: Game crashes with a "Segmentation fault" message in the terminal (not in the log file).

CliffracerX6 years ago

Huh, maybe IFJMP doesn't auto-run what it jumps to after all? I'll have a look at that later.

As for the crash - that's...odd. I understand why it's crashing (function recursion and all), but I'd expect it to just lock up and stop responding, rather than have a segmentation fault. Best idea I've got would probably be to have it automatically halt and stop execution if a given clock cycle for the TC-06 takes more than a certain amount of time, or maybe if a certain function runs more than a certain number of times per tick. I'm loathe to add an op-code limiter, considering it would, well, limit possible programs, but...it might be necessary. Or I just say it's a feature, not a bug? Putting in stuff that will obviously blow up the computer should, well, blow up the computer.

I have a feeling why it crashes is that it makes temporary variables (a lot, actually) in each function, and when that function's getting run recursively, the data piles up fast, so fast the garbage collector can't catch up, and thusly, the program segfaults a moment later when it runs out of memory to put stuff in.

edorfaus6 years ago(+1)

I kind of mostly expected it to lock up as well, actually, but that's not what I got.

About blowing up the computer; in any regular computer, this kind of loop wouldn't actually blow it up - it would just make it sit there apparently doing nothing, while actually working very hard (at changing the instruction pointer).

With the semantics of immediately running the targeted instructions, I can see it being a problem for the TC-06 though - but since those semantics aren't documented, and no other computer works that way, having JMP work that way here is rather unexpected. Having it blow up the computer is thus not obvious, and would probably surprise most developers.

While my test case is indeed obvious, that's because it was constructed to be (for demonstration purposes), and was already in a context where we talked about the JMP semantics. I can easily see some player accidentally creating such a loop if they're not careful enough while changing their program - and if the game crashes, then their program is probably lost, so they can't really figure out what the problem was later, either. They're more likely to think the game just crashed on its own, not due to the program they put in.

So if you want it to blow up the computer, maybe detect it and blow up the virtual computer instead of the game itself?

(Come to think of it, these semantics might be the cause of some trouble I had with figuring out how the jump offsets work by looking in the debugger - if, after executing a JMP instruction, it shows that the next instruction to be executed is the one _after_ the one I was trying to jump to, then the most obvious explanation seems to be that the jump offset was wrong, not that the computer already executed the targeted instruction. I'm not sure if this was really it, though, because I think I've mostly been using IFJMP, not so much JMP.)

About the crash; if you're using recursion for JMP, then it's probably a stack overflow - that's a common reason for getting a segmentation fault, especially if the system uses guard pages to protect the rest of the program's memory from such overflows.

A stack overflow is not something GC can help with, not just because all of those objects are still technically reachable (it must assume the recursed-into method will return eventually), but because the call stack contains not just the pointers to those objects, but also other things like the return address, which obviously can't be removed anyway before the called method returns. (Unless you used proper tail recursion, but I don't know if .NET/Mono supports that.) So even if you didn't have any local temporary variables, an infinite recursion would still overflow the stack, though it would probably take longer to do so (as in, freeze a bit first, then crash, instead of crashing quickly).

As for how to fix it without introducing limitations, I'll suggest a solution I've used to protect similarly recursive code: keep a set of states, initially empty, and check if that set already contains the state I'm about to call from/to - if it does, then abort to avoid a loop, otherwise, add the state and do the call.

The most tricky bit is usually to figure out what that state should be, especially to maintain reasonable performance - but here I think it's actually pretty easy. As far as I can tell, none of the JMP instructions can modify any state that any of the JMP instructions depend on to figure out where they're going to jump to. (And if you hit a non-JMP instruction, which could change that state, then you're done jumping anyway.) So the only state that seems to matter is which JMP instruction you're about to execute, which is completely determined by its address, which is a simple integer. I don't expect a (rather small) set of integers to cause any performance issues.

To be specific, I think that you can keep a set of addresses, which starts out empty at the start of a clock cycle - and when you're about to execute a JMP instruction, you first check to see if its address is already in the set. If it is, then you have already executed this instruction in this clock cycle, so you're in a loop. In that case, don't actually do the jump, just return. Otherwise, you add the address to the set, and do the jump (aka recursive call).

I believe this would have the effect of making the computer seem to stop at the first instruction in the loop, since it would go around the loop and find the same instruction, and stop there. Then, the next clock cycle, it would do the same thing again, stopping at the same place.

(Note that you can't just keep the address of the first JMP of the clock cycle, since that might be jumping into a loop that it isn't itself a part of.)

With this solution, the computer would at most go through every instruction in memory once per clock cycle (if they're all a big loop), which wouldn't be good if you have a custom mode with a lot of memory, but would at least be better than an infinite recursion. If that computer has enough memory, you could still overflow the stack that way, but that's impossible to avoid with a recursive solution (without tail recursion anyway).

Of course, this is just a suggestion for your consideration. You might have better ideas. (Also, feel free to tell me to shut up if you'd prefer to figure out how to do things on your own (or at least without me butting in).)

P.S. I just remembered - the TIS-100 has an explicit "Halt and Catch Fire" instruction. IIRC it just rebooted the (virtual) computer though. I think there was an achievement for finding (and running) it.

P.P.S. I just thought of an even simpler test case. "JMP 0 0". Which sounds like the kind of thing I might put in as a placeholder, intending to look up the numbers I need to insert later. Which it would be easy to forget to actually do...

CliffracerX6 years ago

So it wouldn't blow your COMPUTER up, but your fans might fly to pieces trying to cool it down. :p

I'll include a documentation update with the next update - JMP and IFJMP should definitely have some more detailing, both on the running functions/explodey aspect, and just in general, considering they're both heavily influenced by Redcode and thusly likely to confuse folks.

I know it's not immediately related to the JMP discussion, but should I think about adding an auto-save whenever you compile a program? E.G, to [ProgramName].autosave.casm? That way if your game explodes, you're not gonna lose your code. Same for the drive, maybe do an autosave of it at regular intervals?

An in-game flame-out animation might be kinda fun - if it detects the loop, the halt light comes on and steam comes outta the box.

public List<int> runAddresses; //assume it's initialized elsewhere
public int currentCounter; //self-evident
public int[] RAM; //self-evident
void TimedUpdate() //this runs at the computer's clockrate to execute code and such
{
    //code surrounding halts and such goes here
    runAddresses.Clear();
    DoProcess();
}
void DoProcess() //this actually executes op-codes & whatnot
{
    runAddresses.Add(currentCounter);
    int data,opCode,arguments; //data is the memory data at RAM[currentCounter], and arguments is the last 28 bits of said data
    //insert all the other functions and such
    if(opCode==4) //JMP
    {
        int destAddress; //assume this is set by reading the arguments & whatnot
        if(runAddresses.Contains(destAddress))
        {
            DoFlameout();
        }
    }
}

Rough pseudocode for how to integrate the recursive loop prevention as you suggested it. Clear the list of run addresses before running op-codes, and add the current program counter to the list of run addresses at the beginning of the op-code-runner function. If the list of run addresses contains whatever JMP is supposed to be jumping to, cause a flame-out animation & halt the processor, rather than running it.

This SHOULD catch all possible recursive JMP loops that'd cause a stack overflow, without breaking things like the Blinkenlights loop. Only situation I can think of would be something with self-modifying code looping, but...that shouldn't even be an issue (since a non-JMP call will reset the list of addresses) in the current version of the game. A multithreaded two-core version of the TC-06 could encounter problems with that, if your modification was happening on the other processor, though. :/

I do appreciate the suggestions & bug reports - thank you for providing them!

(As for halting and catching fire - I think that should literally just be "run JMP 0 0 for a special surprise" or something :P)

edorfaus6 years ago(+1)

Some kind of auto-save would probably be a good idea, yes - much like for a text editor, since it includes one - and I do agree that it should not auto-save by overwriting the proper (manual) save file(s). I believe the approach you suggest should work - not sure if it's the best one, or whether it should be a game-wide auto-save file, I suppose it depends on how/when you want to detect and load it. (As in, on game start, or when a user tries to load a previous save, or when they re-enter a level with any auto-save file, or what. Also consider asking first instead of just loading, in case the auto-save itself got corrupted enough to crash the game when loaded.) Whether to auto-save the entire game state in one file, or several, probably depends on what features you want to have as well - e.g. if you want to allow save/load of disk state separately from program or level, keeping them separate (and separately restorable) is probably better, but keeping the entire auto-save in one file would probably be easier if you (maybe later) find you want to save other parts of the game state as well (e.g. which stage of a tutorial the player was at).

To be honest, I think that's the largest and in many ways most difficult part of creating something like this - deciding how exactly you want it to work, to be properly user-friendly. I don't have any real answers for that part, it's not really my field - so you should consider anything I say about it to be just suggestions for things to consider when you make your own decisions about it.

Your pseudocode is pretty much it, yes - or close enough anyway. (Assuming the recursion only happens in the else branch of the inner if.) Not exactly what I had in mind (ends up halting at a different instruction), but I believe it should work.

Actually, come to think of it, assuming that no instruction should be able to be repeated (via recursion) in the same clock cycle without a flameout, there's a slightly simpler and safer variant that would catch loops of any instruction, not just a JMP. The additional safety comes from the code being concentrated in fewer places, and not needing to be duplicated for each relevant instruction.

... (the rest is same as before...)
void DoProcess() //this actually executes op-codes & whatnot
{
    if(runAddresses.Contains(currentCounter))
    {
        DoFlameout();
        return;
    }
    runAddresses.Add(currentCounter);
    ... code for each instruction goes here, no further checks needed...
}

Of course, if you ever add any instructions that should be able to re-run the same address immediately (e.g. an "overwrite self and immediately re-execute" instruction), this won't work and you'd have to spread it out per instruction again. But I'd suggest against adding something like that, since it's rather dangerous (it could overwrite itself with itself, and then there's a loop again. Better to say that the overwrite requires a clock cycle, even if the implicit jump-to-self that follows doesn't).

And yes, this solution would somewhat limit a two-core version of the PC, but logically, if such a loop would break a single-core CPU, then it should also break the core that ran the loop in a two-core setup as well, even if the other core would still work afterwards. (Which it might not, since the first core breaking might also break something on the motherboard that the second core needs to function.) It's also easy to work around - just ensure that your busy loop includes a non-JMP instruction to give the second core a moment between instructions to modify the first core's memory. (It's kind of arguable whether it matters which of the two instructions it modifies...) Or use IFJMP instead, since that's not instant. (Unless you intend to make it be?)

itch.io

Viewing post in Code sharing megathread