Linux port of reconstruction, now in C/C++

NOTE: I HATE A LOT OF YOUR ZZT GAMES, SO WATCH OUT!

Moderators: Commodore, Zenith Nadir

The Mysterious KM
newcomer
Posts: 18
Joined: Wed Mar 25, 2020 12:59 pm

Linux port of reconstruction, now in C/C++

Post by The Mysterious KM »

Happy New Year!

By using a Pascal to C translator and some manual fixup (okay, a lot of manual fixup), I now have a C/C++ port of the Reconstruction of ZZT: https://github.com/kristomu/linux-recon ... tree/cport

I've tested it with both llvm (clang) and g++ on Linux, and it works with both, and runs the Preposterous Mandelbrot renderer fine. There are still some things left to do (mostly related to testing or handling deliberately mangled files), but it should work for most games.

The whole "getting the P to C library compiled" part is sorta fiddly too, so I should try to port everything to native C/C++ structures to get rid of it. If you're compiling under Linux AMD64, it should just work; otherwise you need to compile the .a library for ptoc first - the repo csrc readme.md file has some links to it.

Also note the testcase/ directory that contains a number of worlds that crash or hang ZZT. It could be used for testing other implementations as well - I know some of them crash KevEdit, and there's one that exercises the conveyor bug listed in another post.

Have fun! (And if I forgot to include some source file that I should have and it doesn't compile, let me know... wouldn't be the first time.)
asie
1 full minit uv 1 secend mesiges
Posts: 67
Joined: Sun Mar 17, 2019 4:55 pm

Re: Linux port of reconstruction, now in C/C++

Post by asie »

Hello,

Great work! I've also made a C++ port manually, a few months ago -> https://github.com/asiekierka/openzoo-cpp -> however, that doesn't incorporate most of your bugfixes, or a text mode.

I've also made a C port, and Ben Hoyt made a Go transpiler before. Right now, I'm evaluating if the Nim programming language with its Pascal/Python crossover syntax and metaprogramming capabilities could be a good fit for the project (as I seek to also support Super ZZT, and emulate some arcane features like writing to the ZZT 3.2 memory map using out-of-bounds tile writes - which have been used in proof-of-concepts, but not (yet!) in production). This is why I didn't publish it.

I've also looked at your bugfixes before, and while I'd like to incorporate them, any major changes require great care regarding compatibility - there are a lot of ZZT worlds which misuse bugs as features, or are slightly broken in a way which fails a fuzz test on a modern operating system but works fine in DOS... Thank you, nonetheless!
The Mysterious KM
newcomer
Posts: 18
Joined: Wed Mar 25, 2020 12:59 pm

Re: Linux port of reconstruction, now in C/C++

Post by The Mysterious KM »

I've taken care to not (intentionally) make anything behave differently. The fuzz patches are mostly things that would crash ZZT outright (writes to random memory, infinite recursion board edge bugs, etc.), since the fuzzer only records crashes and hangs.

There are hypothetical instances where the behavior could differ: I imagine a ZZT world could theoretically insert code into running memory and transform itself into Megazeux. I've considered that too much to ask, as any reasonable duplication of such behavior would require a fully fledged x86 emulator.

I'm also working on some way to synchronize the C++ port with FreePascal, so that I could find test cases where they differ and thus make sure they don't. In the longer term, it would be useful to have test cases that pin down the behavior of ZZT in various weird scenarios, so they can be used to verify that independent implementations are bug-compatible (or indeed that I don't diverge from DOS behavior when refactoring). I'd also like to find some sort of agreement on what features are too much to ask and what features are OK, but I don't feel I'm part of the community enough to do so on my own.

In short: I want to be bug-compatible, and I've tried my hardest to be so. I agree that differing behavior would be a bug (within limits). Clearly anything that's used in production should behave identically, or it should be considered a bug.
asie
1 full minit uv 1 secend mesiges
Posts: 67
Joined: Sun Mar 17, 2019 4:55 pm

Re: Linux port of reconstruction, now in C/C++

Post by asie »

The Mysterious KM wrote: Sun Jan 03, 2021 8:51 pm There are hypothetical instances where the behavior could differ: I imagine a ZZT world could theoretically insert code into running memory and transform itself into Megazeux. I've considered that too much to ask, as any reasonable duplication of such behavior would require a fully fledged x86 emulator.
That is too much to ask; but out-of-bounds tile writing (via the "object dies, next stat moves once" trick, once demonstrated by Nanobot) can be used for controlled writes into a chunk of ZZT's engine's memory, and unfortunately it seems - based on discussions in the Discord - that some community members would like to use such functionality in the future.
I'm also working on some way to synchronize the C++ port with FreePascal, so that I could find test cases where they differ and thus make sure they don't. In the longer term, it would be useful to have test cases that pin down the behavior of ZZT in various weird scenarios, so they can be used to verify that independent implementations are bug-compatible (or indeed that I don't diverge from DOS behavior when refactoring). I'd also like to find some sort of agreement on what features are too much to ask and what features are OK, but I don't feel I'm part of the community enough to do so on my own.
For verifying independent implementations, I'd like to recommend what I wanted to do - a combination of .ZZT file and input recording. You might want to consult Mr_Alert - he has been doing research into tool-assisted speedrunning/replays in ZZT, and I want to support that in OpenZoo myself.

As for features, ZZT is about freedom - for example, WiL is making a fork of ZZT which is adding a ton of new engine features called "WeaveZZT". This is my biggest concern with a C/C++ rewrite; these forks need to be then either re-implemented by me as well, or ignored - and they cannot pull in my patches. The primary reason ("blocker") for which I'm moving away from Free Pascal is WebAssembly support.
In short: I want to be bug-compatible, and I've tried my hardest to be so. I agree that differing behavior would be a bug (within limits). Clearly anything that's used in production should behave identically, or it should be considered a bug.
I put the limit before arbitrary code execution; I wanted to put the limit before arbitrary controlled memory reads/writes, but apparently I cannot do that.
The Mysterious KM
newcomer
Posts: 18
Joined: Wed Mar 25, 2020 12:59 pm

Re: Linux port of reconstruction, now in C/C++

Post by The Mysterious KM »

For verifying independent implementations, I'd like to recommend what I wanted to do - a combination of .ZZT file and input recording. You might want to consult Mr_Alert - he has been doing research into tool-assisted speedrunning/replays in ZZT, and I want to support that in OpenZoo myself.
I was thinking of making the Free Pascal code functional (in a way that disturbs the code as little as possible) so that evolving the game state is a matter of calling a function once. Then if, for every conceivable prior state, the state after running one tick agrees with the standard implementation, the game conforms to the standard. But your approach might be less invasive (require fewer changes) because there're so many global variables to ZZT.

A TAS demo file could possibly be augmented with a hash of the board state for every tick or cycle -- if that hash function isn't too slow to execute on every tick or cycle. It would give an exact point of divergence.
As for features, ZZT is about freedom - for example, WiL is making a fork of ZZT which is adding a ton of new engine features called "WeaveZZT". This is my biggest concern with a C/C++ rewrite; these forks need to be then either re-implemented by me as well, or ignored - and they cannot pull in my patches. The primary reason ("blocker") for which I'm moving away from Free Pascal is WebAssembly support.
All the more reason to have the rewrite somehow able to be certified/tested; then it could be used as the starting point... perhaps not in DOS, though.
User avatar
Quantum P.
Level 17 Accordion Thief
Posts: 1433
Joined: Fri Sep 12, 2003 1:41 am
Location: Edmonds, WA
Contact:

Re: Linux port of reconstruction, now in C/C++

Post by Quantum P. »

I like the idea of testcases for ZZT's behavior using known inputs/outputs, especially stuff like hashing in-memory states. Automated testing isn't a panacea, but it would give you a way to measure whether or not the port is accurate.

As for where to draw the line for which bugs to support (arbitrary code execution, arbitrary memory reads/writes, etc), I'll offer a thought experiment. Suppose Sweeney had switched compilers in order to target a similar-but-not-x86 processor, without changing the original Pascal source. What would be the subset of bugs that behave exactly the same between ZZT 3.2 for DOS and that hypothetical port?

Arbitrary code execution would obviously be out, and so would reading/writing to arbitrary locations in memory. But there would be some out-of-bounds memory accesses that would likely be the same between the two editions. For the unmodified Pascal source to be able to read/write ZZT worlds, you can assume stuff like 16-bit numbers are still two's-complement little-endian, and that the order of struct members doesn't change -- but the compiler could still rearrange code/memory in ways that maintained binary compatibility with the original ZZT worlds.

It's still not a precise location to draw the line, but having the question to ask ("Would this bug work as-is if Tim switched compilers?") would allow you to get more rigorous without committing to emulating ZZT's entire memory layout.
The Mysterious KM
newcomer
Posts: 18
Joined: Wed Mar 25, 2020 12:59 pm

Re: Linux port of reconstruction, now in C/C++

Post by The Mysterious KM »

Automated testing isn't a panacea, but it would give you a way to measure whether or not the port is accurate.
Yes, you'd need formal verification if you want to be absolutely sure. Good luck :-)
As for where to draw the line for which bugs to support (arbitrary code execution, arbitrary memory reads/writes, etc), I'll offer a thought experiment. Suppose Sweeney had switched compilers in order to target a similar-but-not-x86 processor, without changing the original Pascal source. What would be the subset of bugs that behave exactly the same between ZZT 3.2 for DOS and that hypothetical port?
That's an interesting experiment. Let's see where it goes:

Since ZZT dumps memory structures directly to disk when saving, the CPU must be 16 bit little endian. (In particular, pointers have the same length as in DOS.) However, the opcodes could differ and the compiler could do more advanced optimization than TP, which means that the code's layout is completely unknown.

So anything that reads from or writes to the code is out. That would include constants inside the code itself (e.g. ranges of a for loop, element constants inside ElementTick or ElementTouch functions). Things that are dynamically allocated (in particular, IoTmpBuf) could be located anywhere in memory. But the relative structure within each variable would be preserved.

Since IoTmpBuf is dynamically allocated, accessing out-of-bounds memory at the time of board serialization/deserialization is out. But World and Board are both static, so reading out of bounds within them (e.g. using duplicators to access whether the board is dark or not) would be OK. I'm not sure how Turbo Pascal arranges its code and data segments, but depending, it may also be OK to access static strings ("Board is dark", "A fake wall", etc), or to access World from Board.

Does that seem right?
User avatar
Quantum P.
Level 17 Accordion Thief
Posts: 1433
Joined: Fri Sep 12, 2003 1:41 am
Location: Edmonds, WA
Contact:

Re: Linux port of reconstruction, now in C/C++

Post by Quantum P. »

That seems about right to me.

Applying this to a couple of out-of-bounds memory bugs I can think of off the top of my head:
  • Weird messages displayed by black keys/doors. IIRC this is caused by black's index being zero and the array of color names starting at one. The stuff before and after ColorNames are just static arrays of constants, so I would expect the message to be the same. Technically the unused bytes at the end of a Pascal string might be undefined, but it's not a huge assumption to say Pascal compilers will typically fill unused space with null bytes.
  • Elements IDs greater than the maximum ID. There are some static variables after the declaration of the ElementDefs array, so I'd expect the first few elements immediately above the maximum ID to behave similarly. But elements with high IDs (e.g., element 255) might go beyond the predictable memory region and behave differently. I think rendering might be the same for all beyond-max elements because the text-rendering code considers everything above a certain ID to be text. But will element 255 be breakable/visible in the dark/kill you when you touch it/etc? Those traits might change.
The Mysterious KM
newcomer
Posts: 18
Joined: Wed Mar 25, 2020 12:59 pm

Re: Linux port of reconstruction, now in C/C++

Post by The Mysterious KM »

Elements IDs greater than the maximum ID. There are some static variables after the declaration of the ElementDefs array, so I'd expect the first few elements immediately above the maximum ID to behave similarly. But elements with high IDs (e.g., element 255) might go beyond the predictable memory region and behave differently. I think rendering might be the same for all beyond-max elements because the text-rendering code considers everything above a certain ID to be text. But will element 255 be breakable/visible in the dark/kill you when you touch it/etc? Those traits might change.
I think every beyond-max tile will crash the game if you touch it or if it's got stats, because the TouchProc and TickProc pointers will point to something that's not the beginning of a function. Apart from that problem, it should be pretty easy to dump the whole table in DOS as if the table were actually that large. The difficult part is finding out how large the table should be. Maybe it'd be best to just dump the whole thing because it's not any harder to code Turbo Pascal to do so than to dump elments 0..100 (say).

I also think that means that any beyond max tiles having stats should be flagged as an error outright on board load. No-stats ones should probably throw an "this is undefined behavior, tell the maker of the world" error dialog when you try to touch them (because DOS would crash). If not compensating for an error would lead to a state that sooner or later ends in a crash no matter what happens, then we can do whatever we want to avoid that state. But I think there should be some notification so that it's clear that the setup would've crashed in DOS, so that world authors don't inadvertently make something that crashes the original.
zzo38
newcomer
Posts: 22
Joined: Sun Dec 15, 2019 11:25 pm

Re: Linux port of reconstruction, now in C/C++

Post by zzo38 »

I think that arbitrary code execution should not be emulated; it should probably check for such things and display an error message in most such cases. This is also true for some cases of arbitrary memory accesses, but some cases of out of bounds memory accesses should be emulated, either by providing a larger buffer, by ignoring the overflow, or by emulating the specific case by special programming; this will have to be decided for each individual case separately, which way is best. (For example, black keys still need to behave the same way by setting the gems, although the message displayed may differ. This may be best implemented by explicitly checking, since the target computer might be big-endian, or might have structure padding; when reading/writing files, the program will need to convert them.) Other bugs will still need to be emulated too (e.g. #PUT will need to fail to work on the bottom row).
Quantum P. wrote: Wed Jan 06, 2021 1:13 amWeird messages displayed by black keys/doors. IIRC this is caused by black's index being zero and the array of color names starting at one. The stuff before and after ColorNames are just static arrays of constants, so I would expect the message to be the same. Technically the unused bytes at the end of a Pascal string might be undefined, but it's not a huge assumption to say Pascal compilers will typically fill unused space with null bytes.
My opinion is that you do not have to emulate the exact same message if you do not want to, I think; you just have to ensure that it does display a message (due to how the stat limit works, displaying a message is required) and that it doesn't crash.
Elements IDs greater than the maximum ID. There are some static variables after the declaration of the ElementDefs array, so I'd expect the first few elements immediately above the maximum ID to behave similarly. But elements with high IDs (e.g., element 255) might go beyond the predictable memory region and behave differently. I think rendering might be the same for all beyond-max elements because the text-rendering code considers everything above a certain ID to be text. But will element 255 be breakable/visible in the dark/kill you when you touch it/etc? Those traits might change.
Actually, the rendering is not necessarily the same either, due to checking the HasDrawProc flag before checking if the the element ID is below or above the minimum text ID, when drawing the text. Best is probably to display an error message and terminate if it loads a board containing such elements (but to allow loading a world containing boards with invalid elements if those boards are never loaded). Since they might be visible in dark, this means that ZZT might crash even if the board is dark, so it should still be an error in a Linux version.

WeaveZZT is a ZZT variant with extra game features, although unfortunately it doesn't have its own world format number or filename extension, making it difficult to selectively enable these features in an emulation (and some of them may conflict with the use of the same words in ordinary ZZT worlds), or to identify the world as a WeaveZZT world if no extra information is provided.

FreeZZT is my own ZZT variant; extra game features which affect the gameplay are selectively enabled depending on the world format number (which is -4 for FreeZZT; I have a list of world format numbers, in case someone registers their own). ZZT variants which do not implement the FreeZZT world format will display the message "You need a newer version of ZZT!" (Reimplementations of ZZT may wish to display a different message, e.g. "This is not a standard ZZT world file" or "This world file is not compatible with [name of implementation]". This is also true of Super ZZT files; if the implementation does not implement Super ZZT, then it would display such a message.)

If you wish to add other enhancements, such as new cheats, command-line switches, displaying date/time of save game files in the restore game menu, etc, that can be done without needing to be selectively enabled; they can be always enabled, since they are not related to the compatibility of world files.

Some things are going to be made different in a Linux version, such as, switches should start with "-" instead of "/", and you should implement "--" to treat the next argument as the file name, just in case the file name starts with a minus sign for some reason. (You might also add a man page, perhaps.)
I have set up a NNTP to discuss ZZT and other stuff.
The Mysterious KM
newcomer
Posts: 18
Joined: Wed Mar 25, 2020 12:59 pm

Re: Linux port of reconstruction, now in C/C++

Post by The Mysterious KM »

Actually, the rendering is not necessarily the same either, due to checking the HasDrawProc flag before checking if the the element ID is below or above the minimum text ID, when drawing the text. Best is probably to display an error message and terminate if it loads a board containing such elements (but to allow loading a world containing boards with invalid elements if those boards are never loaded). Since they might be visible in dark, this means that ZZT might crash even if the board is dark, so it should still be an error in a Linux version.
I tried to dump the out of bounds element defs yesterday, but they depend on the binary code (after being compiled and run through LZEXE), so just adding code to dump them changes what they are. It'll have to be done with the dosbox debugger or something, or every out-of-bounds element should trigger an error when loading the board. Or there's the slow way, by making boards with all the out-of-bounds elements and checking which cause a crash (and which are pushable, can be seen in dark, can be placed under other things, etc).
The Mysterious KM
newcomer
Posts: 18
Joined: Wed Mar 25, 2020 12:59 pm

Re: Linux port of reconstruction, now in C/C++

Post by The Mysterious KM »

I did it :-) I dumped the data with Dosbox.

Here's the info on out-of-bounds elements: https://github.com/kristomu/linux-recon ... o/elements
asie
1 full minit uv 1 secend mesiges
Posts: 67
Joined: Sun Mar 17, 2019 4:55 pm

Re: Linux port of reconstruction, now in C/C++

Post by asie »

I did some research on this due to running into undefined behaviour on the game "Cyber Purge", which tried to use element 69 (nice) in production -> Most of the data is still either in memory which is uninitialized (so can be any value and ZZT won't change it), or set to values which cause crashes.

Let's separate "crashes-on-draw" and "crashes-on-touch/tick" here. There is no safe element ID outside of bounds which doesn't "crash-on-touch/tick"; as that requires TouchProc or TickProc to be initialized to a valid function pointer. However, there can be some safe element IDs which don't "crash-on-draw", as that only requires HasDrawProc (a 1-byte boolean) to be zero. I've looked into a comparison of all potential HasDrawProc positions - and most of them are either in memory ZZT does not write to, or memory ZZT writes a non-zero value to - both types are as such either "might-crash-on-draw" or "will-crash-on-draw". However, an interesting thing happens in the high 230s: the offset part of the segment-offset register wraps around! This means we're now looking at (a) const strings, which ARE initialized and guaranteed not to change, and (b) the transition table, which is likewise initialized and constant.

As such, without proof of this being a complete set, I present to you a list of all "unsafe" element IDs which should be safe to draw:

238, 239, 240, 241, 244, 246, 248, 250, 252, 254

And out of those, four give unique colors not otherwise available:

246, 248, 250, 252 as blinking white, green, red and brown text respectively.

I hope this will put the discussion to rest - no other element IDs are guaranteed to be safe, and ZZT can go from not crashing to crashing with something as simple as a different program running before it.
The Mysterious KM
newcomer
Posts: 18
Joined: Wed Mar 25, 2020 12:59 pm

Re: Linux port of reconstruction, now in C/C++

Post by The Mysterious KM »

That's strange - I wrote a quick and dirty assembler program to fill the area of memory corresponding to ZZT's data segment in DOSBox with 0xFF, and some of the areas you identified as valid stay 0xFF after running ZZT according to the dosbox debug dump.

I ran the program, then ZZT to a custom world, started play, and captured the memory at ds:0 to ds:FFFF (DS=170F on my version of DOSBox). For ZZT 3.2, the elements that have HasDrawProc zero were:

80, 100, 238, 239, 240, 247, 248, 249, and 250.

Just to check, according to my program, the definition for element 241 starts 56783-9788 = 46995 bytes from the start of the definition of element 0. The prefilled 0xFFs are present here, so I get HasDrawProc true, DrawProc FFFF:FFFF.

And here's the fasm code for the fill-memory program, if you'd like to check:

Code: Select all

; Fill 170F:0000 to 170F:FFFF with ffh
; This is used to determine "safe" elements to modify (i.e. that ZZT sets
; pointers to zero for). A different segment may be needed for ZZT 2.0.

	org 100h
	use16

main:
	pusha
	push 0170fh
	pop ds
	xor cx, cx
	dec cx				; is now FFFFh
	xor di, di
looping:
	mov byte ptr di, 0ffh
	inc di
	loop looping

	int 20h
It's pretty slow (and leaks stack, go me!) but gets the job done. Your DOSBox might allocate a different region of memory to ZZT's data segment: just use the debugger to find out which it is.
asie
1 full minit uv 1 secend mesiges
Posts: 67
Joined: Sun Mar 17, 2019 4:55 pm

Re: Linux port of reconstruction, now in C/C++

Post by asie »

The Mysterious KM wrote: Sat Apr 17, 2021 10:18 pm That's strange - I wrote a quick and dirty assembler program to fill the area of memory corresponding to ZZT's data segment in DOSBox with 0xFF, and some of the areas you identified as valid stay 0xFF after running ZZT according to the dosbox debug dump.
I have done mine in a different way - by analyzing where each element landed by hand armed with the ZZT.MAP output from TP5.5 and a Zeta memory dump; in particular, I focused on elements which landed in either the constant area of ZZT's data segment (should match the data in the executable) or the transition table (should be initialized in a constant way).

I might have miscalculated; certainly, your research is done in a way which is more sound (but I'd still exclude IDs 80 and 100). An easy way to confirm one way or the other is check which of our IDs crash upon drawing after filling the memory with 0xFF.
Post Reply