I have been writing a classic fire demo effect for Uxn. Before it worked, I had to debug several problems, one of which turned out to be a stack balancing error where I forgot to drop the values off the stack at the end of the inner loop.
Writing a function that does not have the expected stack effect is a very common error, and it would be great to be able to detect it automatically. I have found a simple way to detect such errors and found bugs in existing programs with it.
Valgrind is a collection of tools to dynamically analyze binaries. It is frequently used by C and C++ programmers to detect both memory leaks and all kinds of memory corruption errors. Valgrind default "memcheck" tool works by tracing all heap memory allocations and deallocations, and reporting all memory that is not freed by the program when the process exits, as well as other errors such as double free and use of unintialized memory.
For an example, this program leaks memory by allocating it and never freeing:
#include <stdlib.h>
int main() {
char *s = malloc(256);
return 0;
}
Valgrind by default runs memcheck tool and reports memory leak when running this program:
$ cc 1.c $ valgrind ./a.out ==621015== Memcheck, a memory error detector ==621015== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al. ==621015== Using Valgrind-3.25.1 and LibVEX; rerun with -h for copyright info ==621015== Command: ./a.out ==621015== ==621015== ==621015== HEAP SUMMARY: ==621015== in use at exit: 256 bytes in 1 blocks ==621015== total heap usage: 1 allocs, 0 frees, 256 bytes allocated ==621015== ==621015== LEAK SUMMARY: ==621015== definitely lost: 256 bytes in 1 blocks ==621015== indirectly lost: 0 bytes in 0 blocks ==621015== possibly lost: 0 bytes in 0 blocks ==621015== still reachable: 0 bytes in 0 blocks ==621015== suppressed: 0 bytes in 0 blocks ==621015== Rerun with --leak-check=full to see details of leaked memory ==621015== ==621015== For lists of detected and suppressed errors, rerun with: -s ==621015== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
The fix is to free the memory before exiting:
#include <stdlib.h>
int main() {
char *s = malloc(256);
free(s);
return 0;
}
Afterwards, valgrind reports no errors:
$ valgrind ./a.out ==621957== Memcheck, a memory error detector ==621957== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al. ==621957== Using Valgrind-3.25.1 and LibVEX; rerun with -h for copyright info ==621957== Command: ./a.out ==621957== ==621957== ==621957== HEAP SUMMARY: ==621957== in use at exit: 0 bytes in 0 blocks ==621957== total heap usage: 1 allocs, 1 frees, 256 bytes allocated ==621957== ==621957== All heap blocks were freed -- no leaks are possible ==621957== ==621957== For lists of detected and suppressed errors, rerun with: -s ==621957== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
It is pointless to free the memory right before exiting. However, in more complex programs that use nontrivial data structures freeing all the memory demonstrates that the program did not lose the track of allocated memory while running.
Requiring that C program deallocates all memory before exiting makes it easy to catch memory management problems. Similar principle of adding restrictions that are not too limiting but are easy to check can be applied to Uxn.
Uxn implements I/O cooperatively, by giving control to vectors,
which are addresses that CPU jumps to when certain events occur.
The vectors return the control back to the machine with a BRK instruction.
On program start special vector at address 100 (in hex, 256 in decimal)
is given control, which sets up other vectors, such as screen handler or mouse handler,
before executing BRK itself.
It is common in Uxntal, the assembly language of Uxn,
to mark functions with stack effect comments
such as ( a b -- res ), meaning that the function takes two arguments a and b
from the stack and leaves the result res on the stack before returning.
Uxn stacks are circular,
so it does not matter if your functions leave garbage on the stack.
The stack will never run out of space.
However, if the function leaves garbage from intermediate computations on the stack,
its signature essentially becomes ( a b -- garbage res )
and the caller cannot use the stack for intermediate results anymore,
so functions that return to the caller with JMP2r
should make sure to only leave the results on the stack and nothing else.
Vectors have a special signature ( -> ) and I have not seen any vector marked as taking arguments on the stack
or returning values.
Quoting from the page about doors:
To chain operations across vectors, one might try passing the next operation pointer on the stack, but since we cannot be certain which vector will happen next, we can't expect a specific stack state between events.
I have only seen the values passed on the stack between vectors deliberately
in xh,
an utility to convert hexdumps to binary,
which is used during bootstrapping.
This works because the only registered vector is for the console device.
For any graphical program it is unknown if the next vector will be called by a screen, or, for example, mouse device.
As vectors rarely return any values on the stack on purpose, I came to the idea of requiring that the stacks are balanced at the end of each vector, that is when BRK is executed. Implementing this check is very easy in Uxn emulators.
I have patched uxn2 locally with the following patch:
diff --git a/src/uxn2.c b/src/uxn2.c
index 4c44aac..fbaa006 100644
--- a/src/uxn2.c
+++ b/src/uxn2.c
@@ -1041,7 +1041,17 @@ uxn_eval(Uint16 start_pc)
Uint16 pc = start_pc;
for(;;)
switch(ram[pc++]) {
- /* BRK */ case 0x00: return 1;
+ /* BRK */ case 0x00: {
+ if (ptr[0] != 0) {
+ fprintf(stderr, "Unbalanced stack at BRK (pc=%04x): %d\n", pc - 1, ptr[0]);
+ exit(1);
+ }
+ if (ptr[1] != 0) {
+ fprintf(stderr, "Unbalanced return stack at BRK (pc=%04x): %d\n", pc - 1, ptr[1]);
+ exit(1);
+ }
+ return 1;
+ }
/* JCI */ case 0x20: { const Uint16 a=ram[pc]<<8|ram[pc+1]; pc+=2; if(stk[0][--ptr[0]]) pc+=a; } break;
/* JMI */ case 0x40: { const Uint16 a=ram[pc]<<8|ram[pc+1]; pc+=2+a; } break;
/* JSI */ case 0x60: { const Uint16 a=ram[pc]<<8|ram[pc+1]; pc+=2; Px(1,1,pc); pc+=a; } break;
This change already made development of my programs easier
because any time I unbalance the stack in any function,
emulator exited with an error at the next BRK, usually at the end of @on-screen vector.
Using this check I have also found problems in existing programs drifblim (Uxntal assembler) and noodle.
Patch only prints the address of the BRK instruction that failed, so you will need a symbols viewer to find the corresponding insturction in the source code. Symbols files are produced by Drifblim when it assembles the programs.
For xh I also wrote an alternative version
that does not leave any data on the stacks between vector calls
to make bootstrapping work again:
|00 @System/vector $2 &expansion $2 &wst $1 &rst $1 &metadata $2 &r $2 &g $2 &b $2 &debug $1 &state $1
|10 @Console &vector $2 &read $5 &type $1 &write $1 &error $1
|100
@on-reset ( -> )
;on-console .Console/vector DEO2
BRK
@on-console ( -> )
LIT2 04 -Console/type DEI NEQ ?{ LIT2 80 -System/state DEO }
.Console/read DEI
#30 SUB
DUP #0a LTH ?{ #27 SUB
DUP #10 LTH ?{ POP BRK } }
[ LIT2 &door $1 01 ]
OVR EOR ,&door STR
?&low
&high ( -> )
,&mem STR
BRK
&low ( -> )
LIT2 &mem $1 40 SFT ORA
.Console/write DEO
BRK
I started by writing a flame demo effect for Uxn, so getting back to it. Here is the source code:
( Fire demo effect ) |00 @System &vector $2 &pad $6 &r $2 &g $2 &b $2 &debug $1 |20 @Screen &vector $2 &width $2 &height $2 &auto $1 &pad $1 &x $2 &y $2 &addr $2 &pixel $1 &sprite $1 |c0 @DateTime &year $2 &month $1 &day $1 &hour $1 &minute $1 &second $1 &dotw $1 &doty $2 &isdst $1 |100 @on-reset ( -> ) random/#2700 .System/r DEO2 #0c00 .System/g DEO2 #2900 .System/b DEO2 ( 320 x 192 ) #0140 .Screen/width DEO2 #00c0 .Screen/height DEO2 ;on-screen .Screen/vector DEO2 BRK @on-screen ( -> ) #0000 .Screen/x DEO2 ( Skip the upper part of the screen for performance. ) #0020 .Screen/y DEO2 ( Fill the screen with color 0 ) LIT2 80 -Screen/pixel DEO ( Randomize the last invisible row. ) ;randomrow &>randomloop random/create OVR2 STA POP INC2 DUP2 ;pixelend NEQ2 ?&>randomloop POP2 &>loopy #0001 .Screen/x DEO2 &>loopx [ .Screen/x DEI2 .Screen/y DEI2 getpixel ] #00 SWP [ .Screen/x DEI2 #0001 SUB2 .Screen/y DEI2 INC2 getpixel ] #00 SWP ADD2 [ .Screen/x DEI2 .Screen/y DEI2 INC2 getpixel ] #00 SWP ADD2 [ .Screen/x DEI2 INC2 .Screen/y DEI2 INC2 getpixel ] #00 SWP ADD2 ( Average by dividing by 4 and truncate the result to one byte. ) #02 SFT2 NIP .Screen/x DEI2 .Screen/y DEI2 pixeladdr STA ( Draw values above 70 with dithering ) .Screen/x DEI2 .Screen/y DEI2 getpixel #70 GTH .Screen/x DEI2 .Screen/y DEI2 EOR2 NIP #01 AND AND ( Draw values above 75 with solid color ) .Screen/x DEI2 .Screen/y DEI2 getpixel #75 GTH ORA #01 EOR ?{ LIT2 01 -Screen/pixel DEO } .Screen/x DEI2 INC2 .Screen/x DEO2 .Screen/x DEI2 .Screen/width DEI2 #0001 SUB2 NEQ2 ?&>loopx .Screen/y DEI2 INC2 .Screen/y DEO2 .Screen/y DEI2 .Screen/height DEI2 NEQ2 ?&>loopy BRK @pixeladdr ( x* y* -- addr* ) [ .Screen/width DEI2 MUL2 ADD2 ] [ ;pixels ADD2 ] JMP2r @getpixel ( x* y* -- a ) pixeladdr LDA JMP2r ( Random number generator from https://wiki.xxiivv.com/site/uxntal_library.html, specifically https://wiki.xxiivv.com/etc/lib.random.tal.txt ) @random/ ( -- ) [ LIT2 00 -DateTime/second ] DEI ( ) [ LIT2 00 -DateTime/minute ] DEI #60 SFT2 EOR2 ( ) [ LIT2 00 -DateTime/hour ] DEI #c0 SFT2 EOR2 ,&x STR2 [ LIT2 00 -DateTime/hour ] DEI #04 SFT2 ( ) [ LIT2 00 -DateTime/day ] DEI #10 SFT2 EOR2 ( ) [ LIT2 00 -DateTime/month ] DEI #60 SFT2 EOR2 ( ) .DateTime/year DEI2 #a0 SFT2 EOR2 ,&y STR2 JMP2r @random/create ( -- number* ) [ LIT2 &x $2 ] ( ) DUP2 #50 SFT2 EOR2 ( ) DUP2 #03 SFT2 EOR2 ( ) [ LIT2 &y $2 ] ( ) DUP2 ,&x STR2 DUP2 #01 SFT2 EOR2 EOR2 ( ) ,&y STR2k POP JMP2r @pixels $f000 ( 320 x 192 pixels ) @randomrow $140 ( Additional off-screen row for random values ) @pixelend
The program displays 320 x 192 pixels screen. Each value is a single byte represending the "heat". On each frame the last off-screen row is initialized with random numbers, and the rest of the pixels are calculating the average of the current value and three pixels right below. The average is using integer division by 4, so the "heat" does not go all the way to the top.
The values above 0x75 are displayed as solid color flame and the values above 0x70 are displayed with XOR dithering, looking a bit like smoke. There are still two colors unused, but I decided to make the effect 1-bit to see if it is possible.
I recommend running the program itself as static screenshot does not show the effect well, but here it is anyway:
Assembled ROM can also be ran online in uxn5 but for me both in Firefox and Chromium it ran visibly below 60 fps.
Random number generator is taken from the uxntal library,
specifically from lib.random.tal.txt.
Color #202 used for the background is from compudanzas Uxn tutorial
and color #7c9 used for the flame is from noodle.