[GRUEDORF] Kiri's Devblog

[ExpiredPopsicle]

I’m awful at paying attention to Discord and forums, so I didn’t realize y’all had started GRUEDORF! I suppose that means I’m losing terribly right now, so I’m going to jump into it right away.

Unfortunately, this meant fixing some stuff on my blog, a monstrosity built out of python and wsgi by someone without a clue. But at least it’s like the fourth major rewrite of it, so it’s almost manageable now.

So my main update is that I fixed my blog again. Adding support for drafts, some caching in a spot where it probably really needed it, and the ability to publish updates without rebuilding an entire Docker image.

My other update is one I had originally planned to use as a GRUEDORF update, but it’s probably a little to big for this forum, and has a bit of a backstory…

<rambling_backstory>

So, some time ago I spent an entire year working on building a scripting language with C-like syntax from scratch. I consider it basically “done” and… actually kinda good? (At least for what I wanted it to do.) I still hack on it now and then when I get the urge to improve it, and there is a TODO list to work through, but it is largely “done” and I can drop it into random projects as a library when I need a scripting language.

Years later, I found my self at Google. Miserably at Google, I might add. I wanted out. I started interviewing at game companies, desperate to get back into something interesting. This wasn’t quit up to the point where I got hit by the Stadia mass layoff, but I still wanted to get the hell out of there.

One company I interviewed at, as part of the interview process, wanted me to do a presentation to their programming team. The topic was to be pretty much anything I wanted. There were two things in my life at the time that I was super passionate about, had been investing most of my spare time on, and knew better than most people.

One was my DOS game, and DOS programming in general. It’s a fun topic, and you can really get into the gritty details about the hardware and the OS. I’ve even given a presentation about it to some UCSC kids. Problem is, if I’m giving a presentation to a company’s entire programming team, that’s likely to include at least a few older game devs who actually worked on DOS games. I’d have to be super careful not to hand-wave over some important detail, or I’d be embarrassed from being called out. (Turns out I was right, and there were some older programmers in the crowd!)

The other thing was Ninkasi, my scripting language. I chose that. Because even if I made some missteps in it, I could explain why I made those missteps, and describe what I’d do now if I had to re-do the project from scratch. It’s the kind of thing that works really well to fill up interview time. It’s also a pretty big project, and talking about it can easily fill up an hour. I ended up with 49 slides for a one-hour presentation, meaning that I had to sprint basically through slides.

The interview went great. Didn’t get the job, but that was because they weren’t yet set up for remote work from California. Oh well. I got pretty good feedback otherwise.

</rambling_backstory>

Fast-forward to today. The Ninkasi slides from the interview are still the majority of the documentation that exists for Ninkasi. (I wasn’t great at documenting stuff.) So I spent some time transcribing everything into a big Markdown document (my blog’s content is just a bunch of .md files under the hood).

Anyway, that transcription is now (finally) up right here! https://expiredpopsicle.com/articles/2021-08-02-Ninkasi/Ninkasi.html

Now I’m going to go and fix some bugs on the server that I just discovered while pushing the final version to prod (yay).

[ExpiredPopsicle]

Made a new post on my main blog: Deluxe Paint Gradient Fills

---

tags: grafx2

Deluxe Paint Gradient Fills

So I watched Mark Ferrari’s entire GDC talk “

”. It’s a fantastic talk by one of the greatest pixel artists alive today. He talks about a lot of his work, and spends a section of the video going into some details about his techniques.

I tried to follow along as best I could in his tutorial sections using Grafx2. Unfortunately, there are a few things that Deluxe Paint and/or Pro Motion can do that Grafx2 still can’t. One of those things I’d really like to use is Deluxe Paint’s gradient fill modes.

So I’ve been trying to dissect the way Deluxe Paint does its shape-conforming gradient fills, and seeing if I can implement them myself in Grafx2. (Grafx2 also a has an existing feature request that mentions this functionality: Add more flexible gradients)

Here’s what I’m up against:

Findings

“Contour” fill

• A centerpoint is selected by the user.
• For every point to be filled:
  • Find a the point along the edge that’s the furthest away from
    the center point, where the point to be filled lies in between
    it and the center point.
  • Where A is a vector for the the centerpoint,
    B is the edge point, and C is the point
    to be filled.
  • The point along the gradient to use, t, is in the range of 0
    through 1, and calculated as… t = ||C - A|| /
    ||B - A||
  • This is just an inverse-lerp. We want to see how far along the line
    between A and B we are, and that determines where along the
    gradient we are.

The key here to replicating some of DP’s odd behavior is that it’s always using the most distant edge. This is why DP’s fills look a little weird when the fill wraps around curves (where it has multiple edges to choose from along some lines coming from the center.

From our top-right example, we can see how this breaks down. The gradient is being done based on the most distant edge, so it’s affected by the hook shape.

And the bottom-right example. We can clearly see where it’s preferring far edges to interpolate to.

“Highlight” fill

I believe this is identical to “Countour”, but with a different mapping to the actual gradient. t may be affected by a curve, similar to a gamma curve. So I’m not going to cover this one here.

“Ridges” fill

• For every pixel…
  • find the nearest edges on the left and right (straight
    left/right).
  • Do the inverse lerp described in the “Contour” fill. A is the
    nearest left edge, B is the nearest right edge, and C is
    the point being filled.
  • This one also looks weird when it goes around corners.

“Linear” fill

This is a pretty basic linear gradient fill. Grafx2 already supports this, so it’s only here for completeness.

• Pick a center point (A) and an offset (B).
• For every point to be filled:
  • Project that point onto the vector A - B, to make
    point C.
  • Do an inverted lerp with A, B, and C as above.

“Circular” fill

This is a basic radial gradient. Grafx2 already does this, too, so we won’t get into it.

“Shape” fill

This one is like the “contour” fill, except that it uses a line instead of a single centerpoint. We’ll do the same math as before, but with an extra projection. Rather than a single mid-point, as used in the “contour” mode, we need to use an entire line.

It’ll work exactly the same as the contour gradient, except that we need to find the closest point along a given center line, and use that as the A vector in the equation.

Results

So far I’ve only worked on figuring out the “contour” fill mode. My results are looking pretty promising, though! Here’s what my prototype spits out with the same image input (slightly different points selected as centers):

It doesn’t match the DP results exactly, but that’s more a matter of correctly mapping the gradient to color values than anything to do with the technique.

Next update on this topic will probably focus on the “shaped” mode and optimizations.

[ExpiredPopsicle]

This week I mostly just hacked on my dungeon crawler. So far it’s all UI work and juggling mock-ups. The level generator now actually generates levels as 3D blocks in the scene instead of just printing out to the console, too.

The current plan is to get some generic badguys or training dummies in the level and make some actual attack powers. That’s going to involve some groundwork for those systems.

The game’s slowly transitioning from an ugly mockup to a functional game.

[ExpiredPopsicle]

Grafx2 Panning

I’ve been spending the last year working (off-and-on) on some changes to Grafx2!

Grafx2, for anyone not aware of it, is an old piece of pixel art software from the 90s, for doing 256 color art. It closely mimics Deluxe Paint, for those familiar with it.

There are a few weird aspects of the UI (attributable to the fact that it’s from the 90s), but the biggest issue I have with it is the limited ability to pan around the image. As of this writing, Grafx2 doesn’t let you move the visible area in a way that would let you center the upper-left corner of the image. You can’t pan further to the left than the point where the left edge touches the left side of the screen (or window). Similarly for the top edge and vertical panning.

Thankfully, Grafx2 is also open-source! So I figured “oh! Why don’t I just go in and fix that?”

The result was a lot more work than I bargained for. But it’s finally starting to show results. You can now pan the image around a lot more freely in Grafx2!

I have a branch that, while the code is SUPER MESSY and spills out a ton of warnings, it’s still functional. Almost everything works (except one of the many pixel scaling modes, as of this writing).

My current “panning” branch is available right here. Feel free to give it a whirl! Please, please, please let me know if you find any bugs specific to the panning branch!

The messy details

This change touches a LOT of code.

• Many tools had their own (redundant) clipping implementation, so a lot of that has been shifted out into some common clipping functions.
• A lot of the existing global variables that describe the usable/visible area have been swapped out with more descriptive names, with dedicated clip area structures.
• Many variables throughout the application needed to be converted into signed types.
• Every single pixel scaling mode has separate redundant code that needed an update. The redundancy here would be difficult to factor out, because a lot of these functions - being low-level blitters and such - need to avoid any extra function call overhead.

Remaining work

The code is extremely messy at the moment, and needs a ton of cleanup, but everything is currently working. At least, on PC.

It still needs testing on all the other platforms Grafx2 runs on. This is largely due to switching around some integer data types that might end up with different sizes or signedness on other platforms with different data models.

(Original article from my blog here.)

[ExpiredPopsicle]

Ninkasi Bug Fixes

I spent a bit of time hacking on Ninkasi code this weekend!

I got rid of one terrible idea I implemented, replaced it with something much better, fixed one crash bug, and two potential coroutine-related memory leaks!

Removing One Ugly Anti-feature

First order of business was to change the object-function-call stupidity I put in there forever ago. It’s an anti-feature I never should have considered. Here’s how it went:

An object can have values inside of it assigned to functions, like so:

function testFunc(testValue)
{
    print("Value passed in: ", testValue, "\n");
}

var ob = object();
ob["foo"] = testFunc;

Previously, these functions can be called like so:

ob.foo();

When called in this manner, the object itself is inserted as the first argument to the function. This is roughly equivalent to the following code:

{
    var _temp = ob.foo;
    _temp(ob);
}

And the output of this is, predictably:

Value passed in: <object:0>

The problem with this is that there’s no way to distinguish between when you want the object to be inserted as the first argument to a function and when you do not.

My reasoning at the time I developed this “feature” was sketchy at best, so I finally got around to cutting it out. Now there is no special case considered for calling a function directly from an object’s field using ‘.’.

Now this code…

function testFunc(testValue)
{
    print("Value passed in: ", testValue, "\n");
}

var ob = object();
ob["foo"] = testFunc;

ob.foo();

… is a runtime error, as it should be:

error:
test.nks:14: Incorrect argument count for function call. Expected: 1 Found: 0

To replace this feature, because still like some aspects of it, I have stolen and repurposed C’s indirection operator. The following code acts the way ob.foo() acted before:

ob->foo();

Which is equivalent to:

ob.foo(ob);

This gets us back to the original result:

Value passed in: <object:0>

But now you get to decide if you want to call a function on an object without the object itself being added in as an argument, by using the -> or the ..

One Crash Bug

Callable Objects

First, an explanation of the feature this affected:

Callable objects in Ninkasi are a little oddity I thought it would be useful to throw in. It’s sort of a halfway point to actual closures.

Objects may be called as functions through the use of specially-named fields.

Take the following code:

var ob = newobject;
ob._exec = function(foo) {
    print("foo: ", foo, "\n");
};
ob._data = "blah blah blah";
ob();

The output of this code is:

foo: blah blah blah

It’s that simple. Set an object’s _exec field to a function, set an object’s _data field to a value, and you may call the object itself as though it were a function.

This code…

ob();

… is equivalent to this code…

ob._exec(ob._data);

You can even add extra arguments after the _data one, which is inserted first:

var ob = object();
ob._exec = function(foo, bar) {
    print("foo: ", foo, ", ", bar, "\n");
};
ob._data = "blah blah blah";
ob("whatever");

Output:

foo: blah blah blah, whatever

The Bug

This feature does, unfortunately, involve some weird shifting-around of stack data.

This part wasn’t thought out super-well, so bare with me here.

The setup for the function-call operator involves pushing the function ID onto the stack, followed by all the function arguments, followed by an integer indicating the number of arguments there are.

Here’s what the stack will look like for a normal 3-parameter function call, at the time the call opcode executes (with stack indices relative to the top of the stack):

index | value       | type
------------------------------
-6    | ...         |
-5    | function-ID | function
-4    | arg0        | any type
-3    | arg1        | any type
-2    | arg2        | any type
-1    | 3           | integer

We have the function ID, followed by the arguments, followed by an argument count.

In order for the _data field to always be first, we need the stack to look like this:

index | value       | type
------------------------------
-7    | ...         |
-6    | function-ID | function
-5    | _data       | any type
-4    | arg0        | any type
-3    | arg1        | any type
-2    | arg2        | any type
-1    | 4           | integer

That just involves inserting the _data into the stack, shifting everything forward by 1, and adding 1 to the argument count entry.

I know this is probably tickling everyone’s inefficient-VM sense, but this feature was kind of an afterthought for my personal toy language, so be nice.

Anyway, our bug today was in the code to shift the stack data around. The argument count coming into the function call opcode could be larger than the stack, and it would happily underrun the bottom of the stack, leading to your usual C buffer overrun/underrun type of error. That code is also not the prettiest code in the world, leading me to think I was either tired or in a rush when I wrote it. Let’s have a look…

// Make room for the _data contents on the stack.
nkiVmStackPush_internal(vm);

// Shift everything up the stack.
for(i = argumentCount; i >= 1; i--) {
  vm->currentExecutionContext->stack.values[
    vm->currentExecutionContext->stack.size - argumentCount - 2 + i + 1] =
    vm->currentExecutionContext->stack.values[
      vm->currentExecutionContext->stack.size - argumentCount - 2 + i];
}

Yikes.

How to Setup This Bug

So here’s an interesting thing: You can’t.

Well, let me be more clear, you can’t if you’re using the scripting language directly. This is purely a vulnerability exposed through the binary state snapshots.

I haven’t actually reverse-engineered AFL’s crash output for this one, to be entirely honest, but my thinking is that the bad executable just pushes a bad argument count onto the stack before doing a normal callable-object call.

The Fix

First, I know what you’re going to say. How dare I not have a system in place to protect against these kinds of overrun/underruns, when it’s so easy to check for!? That usually comes after “why the hell are you using C89 for this project when it’s absolutely prone to these kinds of errors!?” followed by a recommendation that I switch to Rust.

The thing is, though, I do have a way of safely interacting with the stack. I’m just not using it here because… uh… reasons?

The stoage space allocated to the stack only doubles in size when it reallocates, so, given that the stack capacity is always a power of two, it’s pretty easy to just mask off the lowest some-number-of bits for stack indices going into the array. I even store that stack mask, and use it like I actually know what I’m doing in most spots!

The fix (along with some much-needed cleanup) look like this:

struct NKVMStack *stack = &(vm->currentExecutionContext->stack);
struct NKValue *stackValues;
nkuint32_t stackSize;
nkuint32_t stackMask;
nkuint32_t stackSizeMinusArguments;

// Make room for the _data contents on the stack.
nkiVmStackPush_internal(vm);

stackValues = stack->values;
stackSize = stack->size;
stackMask = stack->indexMask;
stackSizeMinusArguments = stackSize - argumentCount - 2;

// Shift everything up the stack.
for(i = argumentCount; i >= 1; i--) {
    stackValues[(stackSizeMinusArguments + i + 1) & stackMask] =
      stackValues[(stackSizeMinusArguments + i) & stackMask];
}

This also throws in a few extra variables to cut down on those giant globs of indirection and indexing inside the loop, potentially offering a speedup on compilers that can’t optimize out those redundant operations (not that it’s a particularly fast piece of
code to begin with).

Memory Leaks

I’m not going to get into too much detail with this one, because it’s pretty simple. A failure during coroutine creation would make the program allocate the storage space needed for the coroutine’s execution context (including stack, program counter, etc) and then
fail to set the pointer to store it, causing it to leak.

The fix is just to check for those failures and clean up the mess when it does.

Memory still Tracked

So with this leak still have a backup system in place for these. Allocations inside the VM are actually tracked and easily cleaned up during deallocation of the VM object itself. It’s not a C memory leak, it’s just a leak of VM address space, more or less.

When the VM’s address space is exhausted, it will bail out with its own internal allocation error and can still be cleaned up by the hosting application. So as far as the stability of the hosting application is concerned, and in relation to potentially hostile script code, this isn’t a “real” threat. It does suck for long-running scripts, though.

Final Thoughts

AFL is great. Valgrind is awesome, too. All these issues found today were through those two tools. Thinking you can write secure code without them or some equivalent to them is hubris in its purest form.

The issues with coroutine setup here are definitely showing my lack of testing after writing the coroutine code. The callable object issues are something I wasn’t expecting, because that code’s been in there forever.

Ninkasi may never be perfect and vulnerability-proof, but at least it got a little bit closer today, and I’m pretty happy with that.