This post describes a memory allocation strategy I call a “fixed” size memory pool.

Recently I decided to re-write my virtual machine Drey almost completely in the C programming language, using no external libraries except for the networking via ZeroMQ. This is mostly for fun, to see if I can remember how to program in C again and write a load of low-level stuff (apologies if my C is currently terrible!.)

Drey executes programs written in a much higher level language (typically Scurry), its purpose being to remove all low level details and provide an experience for the author focused on game logic only. As such, the virtual machine implementation must manage the memory itself, not knowing how much of what size memory it will need up front.

Since the system calls malloc/free are relatively slow and will fragment the heap, especially for lots of small object allocations, a memory management system will be required.

(actually, I could probably get away with using malloc since performance doesn’t really matter in Drey, but where’s the fun in that!)

As an entertaining start to the new year, this post will cover the basics of reverse engineering a program and breaking its password protection. Of course, I do not advocate software piracy in any way, and the program in question is called a crackme which is a program designed to broken, with various measures to make it harder for you. They come in different levels of difficulty, the one under the microsope today is a relatively easy one - however, breaking even the simplest program requires a fairly deep understanding of computers, and the process might be quite interesting if you don’t know how it’s done. Let’s have a look at it:

The previous post layed the foundations of creating a language and “compiler” using Racket macros.

This is all very nice, but utimately it is just a bunch of macros. The “language” itself doesn’t have any form of enforced semantics. You can introduce whatever syntax and macros you want, and use them however you like, even if it makes no sense at all.

Whilst this is nice in a way (and can lead to some .. interesting .. “features”) it is often more of a pain than it’s worth. Most of the errors we make in our day to day programming are picked up immediately by the background compiler, or the full compilation. Silly things like “clipboard inheritance” or typos attempting to use bindings that aren’t in scope are high on the list of culprits here.

In this post we will see how Racket can be used to help out by doing some lexical scope “analysis” in a slightly different way from a traditional compiler. We will also see how Racket can redefine its entire notion of function application, which will allow us to introduce some very nifty new syntax into Scurry itself.

This post will be about Racket macros. As a delivery mechanism, I will be using bits of my latest project, which is a virtual machine designed for emulating multiplayer networked board games via ZeroMQ. drey-vm executes compiled bytecode files - much like the CLR or JVM - using an instruction set of my design.

The design of the computer is out of the scope of this post (maybe another post if people are interested in it - let me know in the comments!?) suffice to stay it is written in D and is mostly a stack based computer, supporting functional and imperative programming. It has a string/object dictionary as its primary type,like lua and js.

Much like asi64, I wrote an assembler for the virtual machine in Racket. On top of that assembler I can now build a language (scurry). To start with, I am just creating a Racket language that is still a lisp - Racket has the fantasic power of being able to build macros on macros, gradually introducing higher level syntatic forms. In this way, I don’t really need write an actual compiler. Racket gives me the front end of the compiler for free (being lisp), and the macros-over-assembler method is a very fun and flexibile way to build up a language.

In my last few posts, I detailed some of my experience learning 6502 assembler for the Commodore 64. I started off using DASM, which seems to be quite a nice assembler, severely lacking in documentation. Then I discovered the very awesome KickAssembler, which includes a full blown scripting language on top of java, lots of other very nice features, and great documentation. This made me realise what a powerful modern assembler could be like - and perhaps I could go one step further with it.

Asi64 extends Racket to become a 6502 assembler. No need for scripting languages or half baked macro systems here - you have literally all of Racket and its amazing macro system on your side. It also has direct support for Vice, a popular Commodore 64 emulator, passing your labels and breakpoints along enabling a fluid programming and debugging cycle. Hats off to the fantasic KickAssembler, I have stolen many ideas from it :)

In the last post we discovered how to decode 15-bit symmetric invaders into a chacrater set. This time around we will make them fractal!

The invaders from the last post occupy exactly one character each. The aim is to now select an invader at random, and then draw it one size bigger, using other random invaders as its “pixels” like this

Then, the process can be repeated again, drawing an even bigger invader which is formed by drawing even bigger “pixels” which are composed of the size 2 invaders, like this!

I have recently been getting into programming the Commodore 64. It’s lots of fun to work in such a restricted environment, where you have to use various hardware tricks to achieve your goals. Every machine cycle and byte of memory counts!

I have not programmed in 6502 assembler or the C64 before. I am using the popular C64 emulator WinVice and an assembler called DASM. Having messed around a bit and learnt the basics of the instruction set and the hardware/memory layout, I programmed a couple of effects such as the basic text scroller. I have an idea in mind for my first demo, and part of it revolves around the invader fractal. I have implemented this in various langauages (F# and D being the most recent) and figured it would be a nice fit for the C64.

Invaders

The invader fractal is a very simpe idea, based on the observation that the classic space invaders are symmetrical. Given a 5x5 grid, we can observe that the middle column is static, whilst columns 4 and 5 are columns 1 and 2 flipped around:

This means we can store the information for each row in just 3 bits, multiplied for each row gives us 15 bits to encode an entire invader. 15 bits gives a total of 2^15=32,768 unique invaders. “Real” space invaders are a little bit bigger than 5x5, but we will stick with their smaller cousins.

A LONG TIME AGO, IN A GALAXY FAR AWAY…..

Over the last few days I have been learning Racket, a language derived from Scheme.  The main selling point of Racket is its extensive macro system that lets you do everything from the simplest macros through to redefining the entire language (yes you can even get rid of the parens!).  It is a programming language programming language. In fact, Racket is more of a customisable programming language infrastructure / engine with a default language on top of it.

Though the mystery man Don Syme, Father of F#, is generally heralded for various software based innovations and other computer related things, it transpires he has talents in other unrelated areas…