Page 1 of 1

Linux port of reconstruction-of-zzt

Posted: Wed Mar 25, 2020 1:50 pm
by The Mysterious KM
The other day, I happened upon a Hacker News article about the Reconstruction of ZZT, and I thought, why not try to port it so it can run natively without emulators?

To make long stories short, here's what I ended up with: https://github.com/kristomu/linux-reconstruction-of-zzt. It's still all text mode, so now you can play ZZT through SSH :-)

There are still some bugs, but it works well enough that I can run complex worlds. Like Preposterous Machines, whose Mandelbrot renderer finishes in 50 minutes on my computer. I'll be working on it more now and then to try to get rid of the bugs, but ultimately I think ZZT needs to be implemented from scratch in another language, with reconstruction-of-zzt as a reference implementation.

Re: Linux port of reconstruction-of-zzt

Posted: Wed Mar 25, 2020 5:11 pm
by asie
Hey!

There has actually been a separate attempt to do the same spearheaded by GreaseMonkey - see zoo64. You might also want to submit any patches for the Pascal code you make to OpenZoo, which is a collection of said patches.

I'm working on a C reimplementation of the ZZT engine as a pluggable library called "libzoo", myself, and it will hopefully be released fairly soon.

Re: Linux port of reconstruction-of-zzt

Posted: Thu Apr 16, 2020 8:53 pm
by The Mysterious KM
Almost a month later, and I got sucked into trying to make my port as robust as possible, and experimenting with fuzz testers while doing so :-)

I've been adding commits to fix a lot of crashes and hangs, and the port now easily reads files that KevEdit segfaults on or gives up on. It also recovers corrupted Super Lock last boards as if there was nothing out of the ordinary. (This is all in the "fuzz" branch on github.)

Some architectural limitations are manifesting themselves in multiple bugs, and I thought it might be useful to know about them if you're reimplementing the engine. Mainly:

- There are tons of unprotected reads and writes to board data, and creatures with funny stepX/stepY parameters can scribble all over memory. I've remedied most of it by adding bounds checks wherever a write or read might occur, but I'm coming to think that for a reimplementation, it might be better to let all board access go through read()/write()/compare functions where read() returns a special sentinel board tile when outside of bounds; this board tile can't be written anywhere in bounds (write() just ignores it), and compare always returns false when comparing something out of bounds to something in bounds.

- There's another broad class of bugs involving statIds being invalidated, e.g. a star is the last item with stats on a board and crushes a lion with a lower stats index as part of pushing boulders when moving towards the player. Then after the lion is crushed, all stats with indices higher than the lion are moved one step down, but the LionTick code still uses the old statId which now points outside of Board.StatCount. I'm thinking that the best reimplementation of the stats list would be a linked list, because any node can be removed from it without disturbing any other node. Then you'd need translation functions that translate node pointers to id numbers when saving (for Follower and Leader). In my patches, I don't yet want to do major architectural changes. I've been trying to pass new statIds back through the stack of functions when destruction invalidates them (e.g. from the push function) instead, but it's a pain and extremely ugly.

Re: Linux port of reconstruction-of-zzt

Posted: Fri Apr 17, 2020 7:58 am
by asie
The main problem is that with ZZT (as opposed to Super ZZT, which got a lot less fine-tuning and trickery), you really need to do your best to keep compatibility at 100%, including the bugs, as not only does nobody have a complete list of community-used bugs, new ones are being found and used constantly (for instance, the Museum of ZZT Discord recently found a way to transfer data across loaded worlds by using a bug to destroy board edges around the loaded board, which are not cleared by merely reloading worlds). It might be that emulation and Turbo Pascal binaries will remain the most common route for the foreseeable future.

In libzoo, at least for the time being, the bugs I'm fixing are ones which can directly lead to a crash - other bugs unfortunately have to be preserved for full accuracy.

Re: Linux port of reconstruction-of-zzt

Posted: Fri Apr 17, 2020 10:26 am
by The Mysterious KM
Yes, that's what my position has been as well: anything that leads to a crash or a hang can be fixed. Everything else should be left the way it is.

For instance, I let tile reads/writes write to the edge around the board (that which remains in place when switching from one board to another) be allowed, even though it would be easier to limit reads and writes to the visible viewport.

Or in another example, picking up a black key would cause a crash (since my build has range-checking enabled). So I deliberately added code to show the
'.-'#5'....\'#4'Blue '#5'Green '#4'Cyan '#3'Red '#6'Yellow '#5'White' message when picking up a key, and then alter the eighth bit of the gems counter.

So yes, I'm aware of the need for backwards compatibility :-) That's why I suggested that the out-of-bounds tiles be a special sort that can't be duplicated and can't be put in bounds, instead of just being say, a solid. If it were just a solid, then duplicators with large step values could duplicate solids onto the board where they couldn't in DOS. I would have to check that duplicators with large step don't duplicate anything in DOS, but it seems a reasonable approach.

Strictly speaking, it will be impossible to ensure perfect compatibility, so there will always be some judgement involved. I wouldn't be surprised if you could do a targeted buffer overflow in DOS ZZT by arranging writes to unallocated memory in the right way, and thus execute arbitrary code. Any patch that stops out-of-bounds writes would break that functionality. I think that is acceptable.

You have a point, though, regarding the linked list idea. It would cause different behavior. If the object that's getting its stat ID invalidated is the last object on the list, then the reference will simply be out of bounds, and nothing changes by making the invalidation not happen. If it's not the last object, you could imagine the stat ID now referring to some object that can't move on its own (e.g. a scroll), and then the MoveStat call will make it move anyway if it has just the right xstep and ystep.

It might be useful to have test cases for weird ZZT behavior because it's hard to tell what could change the behavior. Or perhaps connect a fuzzer to original (Linux-ported) ZZT and any reimplementation in parallel, and check if the board state is equal after one cycle, two cycles, three cycles,... for a crafted input.

Re: Linux port of reconstruction-of-zzt

Posted: Fri Apr 17, 2020 7:34 pm
by zzo38
asie wrote: (for instance, the Museum of ZZT Discord recently found a way to transfer data across loaded worlds by using a bug to destroy board edges around the loaded board, which are not cleared by merely reloading worlds)
Is this something using conveyors? I have found a way to do what you described much in the past involving conveyors, and I don't know if that is the same thing or not (since I do not use Discord, and do not want to; I would rather use IRC and NNTP).
The Mysterious KM wrote:
Fri Apr 17, 2020 10:26 am
Yes, that's what my position has been as well: anything that leads to a crash or a hang can be fixed. Everything else should be left the way it is.
Agreed for anything that affects the behaviour of the game. Things which do not affect the behaviour of the game could be changed if wanted, such as displaying file modification times in the restore game menu; however, if you do not want to change these things, that is OK, too.
Or in another example, picking up a black key would cause a crash (since my build has range-checking enabled). So I deliberately added code to show the
'.-'#5'....\'#4'Blue '#5'Green '#4'Cyan '#3'Red '#6'Yellow '#5'White' message when picking up a key, and then alter the eighth bit of the gems counter.
For compatibility, it will need to act in the same way (I am not sure if just altering bit8 is enough or not; it depends on the behaviour of out of range booleans in Turbo Pascal, which is something I have not tested), although I do not think it is required for the message to be the same; writing "black key" would probably also be acceptable.
It might be useful to have test cases for weird ZZT behavior because it's hard to tell what could change the behavior. Or perhaps connect a fuzzer to original (Linux-ported) ZZT and any reimplementation in parallel, and check if the board state is equal after one cycle, two cycles, three cycles,... for a crafted input.
Note that some cases involve random numbers, although not all cases do. The current tick value is also randomized. However, there are many behaviours that can be tested, in my own ZZTPTT world (which also mentions some ways to take advantage of these bugs), and also another "conformance test" world file I have seen (although it appears to be incomplete).

Re: Linux port of reconstruction-of-zzt

Posted: Sat Apr 18, 2020 7:28 am
by asie
zzo38 wrote:
Fri Apr 17, 2020 7:34 pm
Is this something using conveyors? I have found a way to do what you described much in the past involving conveyors, and I don't know if that is the same thing or not (since I do not use Discord, and do not want to; I would rather use IRC and NNTP).
It is not; I don't, however, remember the details perfectly.

Regarding IRC and NNTP - I'd love to use IRC as well over Discord, however I also admit that the only way to get features desired by common users on chatrooms (such as searchable history or mobile persistence) requires either administration knowledge and a 24/7 machine (ZNC) or an existing service with a freemium model (such as IRCCloud). Unfortunately, Discord (and Slack, and other mobile-era services) have the upper hand here, and free software solutions for solving this problem (XMPP, Matrix) have difficulty catching on outside of corporate silos (I'm mostly referring to Google's experimenting with XMPP here). While "power-user-heavy" places like programming or free software-dedicated IRC channels exist, most users will trade convienence over freedom - and free software is still comparatively inconvienent.

Re: Linux port of reconstruction-of-zzt

Posted: Sat Apr 18, 2020 9:45 pm
by The Mysterious KM
zzo38 wrote:
Fri Apr 17, 2020 7:34 pm
Is this something using conveyors? I have found a way to do what you described much in the past involving conveyors, and I don't know if that is the same thing or not (since I do not use Discord, and do not want to; I would rather use IRC and NNTP).
I think the easiest way to modify the edge is to use anything that can overwrite tiles, along with specially crafted xstep/ystep parameters. Then something to the effect of #put opp flow lion ought to work. Checking might be harder - perhaps a duplicator duplicating from the edge.
zzo38 wrote:
Fri Apr 17, 2020 7:34 pm
Agreed for anything that affects the behaviour of the game. Things which do not affect the behaviour of the game could be changed if wanted, such as displaying file modification times in the restore game menu; however, if you do not want to change these things, that is OK, too.
Good point; I hadn't considered those. I've made some QoL patches to my port - in particular, that the editor supports all sorts of international characters and home/end do what they're meant to.

On that note, it's also fine to change game code if it can't change anything in practice. E.g. I put a check into the game loop that crashes the game if there's no player or monitor at the coordinates given by stat 0. This simply converts hangs (where the player gets destroyed and can't accept keyboard input) into crashes, which are easier to diagnose. And since I want neither crashes nor hangs, this additional check shouldn't make a difference because it should never be triggered to begin with.
zzo38 wrote:
Fri Apr 17, 2020 7:34 pm
For compatibility, it will need to act in the same way (I am not sure if just altering bit8 is enough or not; it depends on the behaviour of out of range booleans in Turbo Pascal, which is something I have not tested), although I do not think it is required for the message to be the same; writing "black key" would probably also be acceptable.
It's kind of strange. If you have at least 256 gems, then you count as having the black key, otherwise not. This is the case even if the eighth bit is off, e.g. if you have 1024 gems. I suspect "internally", it's just checking whether the upper byte (bits 8 to 16) is nonzero. Getting the key increases your counter by 256, and unlocking the door decreases it by the same amount.

Re: Linux port of reconstruction-of-zzt

Posted: Sat Apr 18, 2020 11:11 pm
by asie
The Mysterious KM wrote:
Sat Apr 18, 2020 9:45 pm
I suspect "internally", it's just checking whether the upper byte (bits 8 to 16) is nonzero. Getting the key increases your counter by 256, and unlocking the door decreases it by the same amount.
What happens is that the high byte of the Gems counter lives one byte before the beginning of the keys array; so the check is "is nonzero", but getting the key sets the high byte to 1 (and is only possible if the high byte is 0), and unlocking it resets the high byte back to 0 (and is only possible if the high byte is nonzero).