A while ago I wrote a chunk of code to dump data to a console window in a formatted table. Something like you’d see in a SQL console when doing queries. I’ve finally gotten around to open sourcing it so here’s a description of how to use it and where to find it.
To format data into the table structure, a table must first be initialized using table_init(). The data will be output in either CSV format or a pretty printed table depending on the value of the verbose parameter. Rows are added to the table with the table_row() function. Each column in the row is specified by a position in the format string. For example the first format specifier is the first column, second column two, etc. The total number of columns for a table is determined by the call to table_row() with the highest number of format specifiers. The format parameter for table_row() takes a C style format string. The acceptable format specifiers are a (mostly) subset of the printf() format specifiers with the addition of 't' for a timestamp. Format specifiers:
s or S
String of characters
c or C
d or i
Signed decimal integer
Unsigned decimal integer
Unsigned octal integer
Timestamp specified by a time_t value
x or X
Unsigned hexadecimal integer
f, F, g or G
Decimal floating point
[width].[precision] are also supported. Note that precision defaults to 0 so with floating point values it must always be specified or the value will be truncated to a whole number.
Finally, when data is done being added to the table, it is printed using the table_commit() function.
DjDoom is a reference implementation for the original Doom game engine that I have been working on for a little while. The purpose of this project is to build a playable Doom engine from the original Linux source code with minimal changes necessary to build and run in a Windows environment.
This was created as a learning tool for me and I’m publishing this so it can be a learning tool for others. It is intended that this be a base for others to build and expand on.
I deliberately chose to not use any third party libraries to handle sound, input and graphics and instead used only what is usually available on a typical Windows platform. I use DirectX 8 for graphics and input (including keyboard, mouse and joystick).
The sound utilities took the most effort to write since Windows does not make it easy to play MIDI music and sound effects. Learning to use the Windows Multimedia APIs to play MIDI resulted in a few other articles on this blog.
The game engine is built on Windows using MinGW. You will also need the DirectX 8 SDK. Newer DirectX no longer includes Direct Draw and won’t work for this code. DirectX 8 SDK comes with Windows Game Programming for Dummies, Second Edition which is where I got it from.
The original DooM code was released by iD Software under the GPL. The additions I made are released under a more permissive MIT license.
The CALLBACK macro sets up the correct calling convention for the callback function. By default the calling convention is __cdecl in which the caller is required to clean up the stack. The CALLBACK macro tells the compiler to use the __stdcall calling convention for the callback function in which the called function is responsible for cleaning up the stack. If the callback uses the __cdecl calling convention, the stack is not cleaned up properly which results in the above error. Easy to miss if you’re not paying attention. ]]>
I was in need of a small, light weight configuration utility for some projects I’ve been working on. Most of the utilities I found were really overkill for what I needed. I created MiniCFG as a quick and dirty solution that seems to work well.
MiniCFG is a small set of functions written in C for parsing configuration files. Configuration data is stored as name/value pairs in a config file, one per line. There are no real restrictions on the format for names or values except that the cannot contain hash ‘#’ characters which are used to indicate comments.
# this is an example configuration file
# name/value pairs are delimited by a '=' character
name = value
# the '=' character can exist within a value
line = y = mx + b
# names can contain spaces
foo bar = what's in a name
# comments begin with a hash '#' character
another name = another value # comments can follow a value
# name/value pairs can override previous definitions
name = yet another value
# comments and settings may be preceeded by white space
something = else
# a hash cannot be contained within a name, value or quoted strings
quote = "this is not # what you'd expect"
# a name without a value is legal and will return null
with equal sign =
There are three functions used to access the configuration data:
struct config* open_config(char* filename);
This opens and parses the configuration file.
int close_config(struct config* cfg);
This function closes the configuration data and cleans up any used resources.
A question was asked on stackoverflow.com about using a buffer overflow to clobber the stack and alter the behavior of a program. It’s been a while since I’ve done anything like this so I thought I might give it a shot. This code is based on code snippets shown in the stackoverflow thread. This is very architecture and compiler dependent. If you are following along you may have to adjust accordingly.
p = (int*)&p;
p[offset] = new return address;
int main(int argc, char* argv)
int x = 0;
The idea behind this code is to clobber the stack in function foo() so when foo() returns, the x++ is skipped and 0 is printed. We have two things we need to do to make this happen. First, when a function is called, the address of the instruction immediately following the function is pushed on the stack. This is the address control jumps to when the function is finished executing and returns to the caller. It is this address on the stack that we need to change. Second, we need to know where to return to. To find this value, we need to look at the object code that is created by the compiler. If you are trying this at home, your compiler and produced assembly may be different as the produced output can be very version specific. For this example I’m using Cygwin with gcc version 3.4.4. The following is the disassembly of the object code for the main() function:
When this instruction is executed, the address of the next instruction is pushed onto the stack. In this case it is the address of the lea instruction 4010a7. The next block of instructions increment x. This is the block we want to skip.
These two instructions take up a total of 5 bytes. 3 for the lea instructions and 2 for the incl instruction. Once we find the return address on the stack, we need to increment it by 5. Our updated foo() looks like this:
This pushes the previous base pointer onto the stack and makes the current stack pointer the current base pointer. We know when this function was called, the return address was pushed. It is now “under” the base pointer we just pushed. Next, storage for our local variable p is allocated on the stack.
// 401053: 83 ec 04 sub $0x4,%esp
Our stack should now look something like this:
// ret addr
// old ebp
// esp --> p
Next we store the address of p into p so that p is pointing to itself.
// 401056: 8d 45 fc lea -0x4(%ebp),%eax
// 401059: 89 45 fc mov %eax,-0x4(%ebp)
Now, with p pointing to itself, let’s have another look at the stack and see how we should offset p to get to the return address. Our stack should now look something like this:
// ret addr <-- p + 8
// old ebp <-- p + 4
// esp --> p <-- p
Note that I am using a 32-bit system so addresses and registers are stored as 4 byte values. Whatever address p is pointing to, we have to add 8 to that address. In foo() I declared p as an int * so we can treat p as an array of integers and access index 2 to clobber the return address:
So, I’ve been preparing for some job interviews lately. Of the highly technical nature. These are not the ones where they ask you what you’ve been working on or what your experience is in. These are the ones where they ask you questions to test the depth of your knowledge in Computer Science, algorithms, data structures, theory and practice. Stuff you learned as a first and second year undergrad and haven’t actually put into practice much. Not because you didn’t need to use these concepts or they were of no real importance. Rather because most languages and libraries have these things built in and you don’t normally have to implement them except in the most extreme cases.
I started going over my old college notes (yes, I still have them) to refresh my memory. I was surprised by how much I had forgotten. This post I’ll start with sorting algorithms, mainly as a refresher for me and hopefully this proves helpful to someone else. Each algorithm is implemented as a C function that takes two parameters. The first parameter is an array of integers. The second parameter is the length (number of elements) of the array.
Note that some of these examples do some things that break the actual efficiency of the algorithm (for instance using memmove() in insertion sort). This is done to focus simply on the sort algorithm without having to get into too much detail about implementing more efficient data structures that are more suited to the algorithm. Those instances are noted below.
The first sort is probably the simplest and most straight forward of all the sorts. It is the bubble sort. The bubble sort starts at the beginning of the array and compares the first two values. If the first value is greater than the second, they are swapped. It then compares the second and third elements swapping them if needed and continues with each pair of adjacent values in the array. Once the first pass is complete, the largest value is in the last position in the array. The algorithm starts again and repeats until no values need to be swapped. Bubble sort has an average and worse case performance complexity of `0(n^2)`. Because of this poor performance it is not very useful for large data sets. However, it is easy to understand and easy to implement so it can be useful on smaller data sets in situations where efficiency isn’t terribly important.
void bubble_sort(int* arr, int len)
int i, j, swp;
for(i = 0; i < len; i++)
for(j = 0; j < len - i - 1; j++)
if(arr[j] > arr[j + 1])
swp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swp;
The selection sort starts at the beginning of the data and scans for (selects) the minimum value. Once the minimum value is found, it is swapped with the value in the first position. The algorithm starts again at the second position and repeats. Selection sort also has performance complexity of `0(n^2)`. However, since it performs no more than `n` swaps it performs better than bubble sort.
void selection_sort(int* arr, int len)
int i, j, si, swp;
for(i = 0; i < len - 1; i++)
si = i;
for(j = i + 1; j < len; j++)
if(arr[j] < arr[si])
si = j;
if(si != i)
swp = arr[i];
arr[i] = arr[si];
arr[si] = swp;
Insertion sort is similar to selection sort in that it selects each value and inserts it into its proper place. When an element is inserted into its position, all the following elements must be shifted by one. This algorithm is useful in instances where insertion is fast such as with linked lists or in data that is already mostly sorted. Note that this implementation I use an array using memmove() to make room for the insert. I do this for simplicity to demonstrate the algorithm. I wouldn’t recommend using this on an array in practice.
void insertion_sort(int* arr, int len)
int i, j, si, swp;
for(i = 0; i < len - 1; i++)
si = i;
for(j = i + 1; j < len; j++)
if(arr[j] < arr[si])
si = j;
if(si != i)
swp = arr[si];
memmove(&arr[i + 1], &arr[i], (si - i) * sizeof(int));
arr[i] = swp;
The shell sort is a more advanced sorting algorithm that arranges the input data into a series of columns and then sorts each column using insertion sort. By sorting data in columns, the data is able to be moved over greater distances more quickly than would happen with the standard insertion sort. Here is the algorithm written in C. Following, I’ll walk through an application of the algorithm on a random data set.
void shell_sort(int* arr, int len)
int i, j, gap, swp;
gap = len / 2;
while(gap > 0)
for(i = gap; i < len; i++)
swp = arr[i];
j = i;
while(j >= gap && arr[j - gap] > swp)
arr[j] = arr[j - gap];
j -= gap;
arr[j] = swp;
gap = gap / 2;
The random data set is an array of 15 randomly generated numbers. We first calculate the gap and arrange the data into columns based on the gap. amath [33, 38, 73, 29, 6, 72, 71, 19, 53, 57, 43, 38, 5, 83, 7] l = 15, g = l / 2 = 7 [[33, 38, 73, 29, 6, 72, 71],[19, 53, 57, 43, 38, 5, 83],[7,,,,,,]] endamath In this algorithm we start in the first column and save the 19 in swp. We then check each value in the column above the 19 and if it is greater, move the number down the column by one. Finally we put the number in its correct position, in this case at the beginning of the column which will produce the following: amath [[19, 38, 73, 29, 6, 72, 71],[33, 53, 57, 43, 38, 5, 83],[7,,,,,,]] endamath We repeat for each column: amath [[19, 38, 57, 29, 6, 5, 71],[33, 53, 73, 43, 38, 72, 83],[7,,,,,,]] endamath Note that `j` began with the second element in each column and wraps to the third row (then 4th, etc… depending on how many elements are in each column) which looks at the `7` and puts it in its place. amath [[7, 38, 57, 29, 6, 5, 71],[19, 53, 73, 43, 38, 72, 83],[33,,,,,,]] [7, 38, 57, 29, 6, 5, 71, 19, 53, 73, 43, 38, 72, 83, 33] endamath Notice now that the `7` which was last is now in the first position. Values have the potential to jump great distances quite quickly. Now we recalculate the gap and start again. amath g = g / 2 = 3 [[7, 38, 57], [29, 6, 5], [71, 19, 53], [73, 43, 38], [72, 83, 33]] => [[7, 6, 5], [29, 38, 57], [71, 19, 53], [73, 43, 38], [72, 83, 33]] => [[7, 6, 5], [29, 19, 53], [71, 38, 57], [73, 43, 38], [72, 83, 33]] => [[7, 6, 5], [29, 19, 38], [71, 38, 53], [73, 43, 57], [72, 83, 33]] => [[7, 6, 5], [29, 19, 33], [71, 38, 38], [72, 43, 53], [73, 83, 57]] [7, 6, 5, 29, 19, 33, 71, 38, 38, 72, 43, 53, 73, 83, 57] endamath Finally, when gap is `1`, shell sort is essentially an insertion sort on a mostly sorted array for which it performs well. amath g = g / 2 = 1 [, , , , , , , , , , , , , , ] => [, , , , , , , , , , , , , , ] => [, , , , , , , , , , , , , , ] => [, , , , , , , , , , , , , , ] => [, , , , , , , , , , , , , , ] => [, , , , , , , , , , , , , , ] => [, , , , , , , , , , , , , , ] => [, , , , , , , , , , , , , , ] => [, , , , , , , , , , , , , , ] [5, 6, 7, 19, 29, 33, 38, 38, 43, 53, 57, 71, 72, 73, 83] endamath
Merge sort is an `O(nlogn)` sorting algorithm that gets its name from merging two already sorted list into a single sorted list. The algorithm begins by dividing the data in two and recursively sorting the two sub lists. When the recursive calls return, the sub lists are sorted and can then be merged into a final list. Note, this implementation is inefficient using an inplace array and memmove. In practice, merge sort works best where insertions are inexpensive such as linked lists or copying the two sub arrays into a separate large array.
void merge_sort(int* arr, int len)
int *l, *r;
int i, swp, lenl, lenr;
if(len <= 1)
lenl = len / 2;
lenr = len - lenl;
l = arr;
r = arr + lenl;
for(i = 0; i < len && lenl > 0 && lenr > 0; i++)
if(*l > *r)
swp = *r;
memmove(&arr[i + 1], &arr[i], (r - &arr[i]) * sizeof(int));
arr[i] = swp;
Heap sort uses a heap data structure to determine the minimum or maximum value in the data. The data is first placed in a heap structure, in this example a max-heap. Once in this structure, the largest value is at the top of the heap. The heap here is represented in the array where array is the root node, array is the left child, array  is the right child, array  is the left child of array, array is the right child of array, etc… Once the data is heapified, the largest value (root) is swapped with the last value in the array (its final position) and the array is again heapified (excluding the value in now in its correct position). This process is repeated until the array is completely sorted.
void sift_heap(int* arr, int r, int len)
int c, si, swp;
while(r * 2 + 1 < len)
c = r * 2 + 1;
si = r;
if(arr[si] < arr[c])
si = c;
if(c < len - 1 && arr[si] < arr[c + 1])
si = c + 1;
if(si != r)
swp = arr[r];
arr[r] = arr[si];
arr[si] = swp;
r = si;
void heapify(int* arr, int len)
int i, r, c, si, swp;
for(i = len / 2 - 1; i >= 0; i--)
sift_heap(arr, i, len);
void heap_sort(int* arr, int len)
int i, swp;
for(i = len; i > 1; i--)
swp = arr;
arr = arr[i - 1];
arr[i - 1] = swp;
sift_heap(arr, 0, i - 1);
Quick sort works by choosing an “pivot” element and moving all elements with a value lower than the pivot value before the pivot and all elements higher than the pivot after. Once the values have been moved, the pivot is in its final position and quick sort is recursively called on each sub list before and after the pivot. Quick sort has an average complexity of `O(nlogn)` but can have a worst case `o(n^2)` with poorly chosen pivots (for example if the pivot chosen is always the largest or smallest value).