Tag Archives: Source

Binary Heap

by

Despite lack of activity here I have been very busy programming cool stuff which I hope to get around documenting and sharing with you all.

I need to implement the A* algorythm for one of my projects. Its a fairly common to speed up of the implemention to use a binary heap for the open list because of its O(log(n)) insertion and O(1) removal properties.  As I code it up I thought it would be nice to share my binary heap implementation, something which can be a bit fiddly to get right in practice.  I wrote a little fuzz tester to nuke it, so that I can be fairly sure it works correctly.

Gist: BinaryHeap

I chose to make the size fixed at compile time for simplicity, and becaues I am happy to terminate a pathfinding search that exceeds a fixed open list size, as old school games used to do.  It should however not require much work at all to grow the heap size when a node is pushed when currently at full capacity.

I will also leave you with this picture from my latest project:

isometric

THUMB Disassembler

by

I was recently searching through my hard drive looking for examples that might highlight my love of low level programming, and I present here one such project which is a good example of this.

THUMB is an instruction set that was added to some ARM processors as a way to reduce code size, which is advantageous as ARM typically finds use in very constrained devices.  The processor can switch between two operating modes at the request of the program, switching from decoding ARM instructions to smaller THUMB instructions.

I found THUMB particularly interesting since the instruction set is clean and simple and it might make a nice basis for a virtual machine to execute programs written in it.  My idea was to use programs written in C and compile them to THUMB and then execute them in a virtual machine, the entire process serving as a powerfully scripting system for games.

Ultimately, I switched to a MIPS processor as my basis for this project, but I still got as far as making a THUMB disassembler.  I should point out that this was the first disassembler I ever wrote so it marks a large mile stone for me.  Since then I have made a very nice MIPS disassembler using much of what I learned on this project.  The code for the THUMB disassembler can be found here:

thumb_disassm.cpp

To test a disassembler there needs to be something to feed it.  For that purpose, I compiled a small program in GCC targeted for the THUMB instruction set.  The program is listed below, and is just a nonsense program designed only to be valid so as to generate some instructions:

Continue reading →