Pretty Print Tables

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:

specifierOutput
s or SString of characters
c or CCharacter
d or iSigned decimal integer
uUnsigned decimal integer
oUnsigned octal integer
tTimestamp specified by a time_t value
x or XUnsigned hexadecimal integer
f, F, g or GDecimal 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.

int main(int argc, char* argv[])
{
	struct table_t* table = table_init(stdout, "Test Table", 1);
	table_row(table, "%s%s", "Column 1", "Column 2");
	table_separator(table);
	table_row(table, "%s%s", "String value", "test string");
	table_row(table, "%s%c", "Character value", 'c');
	table_row(table, "%s%d", "Signed integer", -1);
	table_row(table, "%s%u", "Unsigned integer", 42);
	table_row(table, "%s%o", "Octal integer", 511);
	table_row(table, "%s%8x", "Hexadecimal integer", 255);
	table_row(table, "%s%.5f", "Floating point", 3.14159);
	table_row(table, "%s%t", "Timestamp", 0);
	table_commit(table);
	return 0;
}

Produces the following output:

$ ./table.exe
+---------------------------------------------------------------+
| Test Table                                                    |
+---------------------+-----------------------------------------+
| Column 1            | Column 2                                |
+---------------------+-----------------------------------------+
| String value        | test string                             |
| Character value     | c                                       |
| Signed integer      | -1                                      |
| Unsigned integer    | 42                                      |
| Octal integer       | 0777                                    |
| Hexadecimal integer | 0x000000ff                              |
| Floating point      | 3.14159                                 |
| Timestamp           | Thursday, January 01, 1970, 12:00:00 AM |
+---------------------+-----------------------------------------+

The code is free under the MIT license and can be downloaded here.

DjDoom v0.1 Released

Version 0.1 of DjDoom has been released and can be downloaded from here.

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.

Sneaky Issue with Windows API Callbacks

I was messing with the windows multimedia APIs and ran into this strange error running my application:

Run-Time Check Failure #0 - The value of ESP was not properly saved

I was adding a callback used by midiStreamOpen():

static void mid_callback_proc(
      HMIDIOUT hmo,
      UINT wMsg,
      DWORD_PTR dwInstance,
      DWORD_PTR dwParam1,
      DWORD_PTR dwParam2)
{
   ...
}
...
err = midiStreamOpen(
      &p->stream,
      &p->device,
      1,
      (DWORD_PTR)mid_callback_proc,
      (DWORD_PTR)p,
      CALLBACK_FUNCTION);

It seems I forgot the CALLBACK macro in the function definition:

static void CALLBACK mid_callback_proc(
      HMIDIOUT hmo,
      UINT wMsg,
      DWORD_PTR dwInstance,
      DWORD_PTR dwParam1,
      DWORD_PTR dwParam2)
{
   ...
}

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. ]]>

MiniCFG v0.1

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.

Example

# 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 =
without

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.

char* load_setting(struct config* cfg, char* name);

This function retrieves the value for a given name or key. If the name does not exist, NULL is returned. MiniCFG is free under the MIT license and can be downloaded here.]]>

Fun with Buffer Overflows

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.

#include <stdio.h>
void foo()
{
	int* p;
	p = (int*)&p;
	p[offset] = new return address;
	return;
}
int main(int argc, char* argv[])
{
	int x = 0;
	foo();
	x++;
	printf("%dn", x);
	return 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:

// _main
//  401071:       55                      push   %ebp
//  401072:       89 e5                   mov    %esp,%ebp
//  401074:       83 ec 18                sub    $0x18,%esp
//  ... skip unimportant stuff ...
//  40109b:       c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%ebp)
//  4010a2:       e8 a9 ff ff ff          call   401050 <_foo>
//  4010a7:       8d 45 fc                lea    -0x4(%ebp),%eax
//  4010aa:       ff 00                   incl   (%eax)
//  4010ac:       8b 45 fc                mov    -0x4(%ebp),%eax
//  4010af:       89 44 24 04             mov    %eax,0x4(%esp)
//  4010b3:       c7 04 24 00 20 40 00    movl   $0x402000,(%esp)
//  4010ba:       e8 a9 00 00 00          call   401168 <_printf>
//  4010bf:       b8 00 00 00 00          mov    $0x0,%eax
//  4010c4:       c9                      leave
//  4010c5:       c3                      ret

This disassembly is produced using the objdump command objdump -d test.exe. Breaking this down we see: Standard preamble stuff. Don’t worry about this. (yet)

//  401071:       55                      push   %ebp
//  401072:       89 e5                   mov    %esp,%ebp

Allocate space on the stack for our local variables (including x). This also allocates a temporary variable to store the address of our format string constant which we will come back to.

//  401074:       83 ec 18                sub    $0x18,%esp

Set x to 0.

//  40109b:       c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%ebp)

Call foo().

//  4010a2:       e8 a9 ff ff ff          call   401050 <_foo>

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.

//  4010a7:       8d 45 fc                lea    -0x4(%ebp),%eax
//  4010aa:       ff 00                   incl   (%eax)

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:

void foo()
{
	int* p;
	p = (int*)&p;
	p[offset] += 5;
	return;
}

Note, we don’t want to skip these two instructions. They are responsible for putting a copy of x into a parameter already allocated on the stack to be passed to printf().

//  4010ac:       8b 45 fc                mov    -0x4(%ebp),%eax
//  4010af:       89 44 24 04             mov    %eax,0x4(%esp)

This instruction copies the address of our format string into the last reserved variable on the stack which is the first parameter to be passed to printf().

//  4010b3:       c7 04 24 00 20 40 00    movl   $0x402000,(%esp)

Finally, we call printf(), set our return value and exit the application.

//  4010ba:       e8 a9 00 00 00          call   401168 <_printf>
//  4010bf:       b8 00 00 00 00          mov    $0x0,%eax
//  4010c4:       c9                      leave
//  4010c5:       c3                      ret

The last thing we need to find is where the return address is stored on the stack. Let’s look at the disassembly of foo().

//  401050:       55                      push   %ebp
//  401051:       89 e5                   mov    %esp,%ebp
//  401053:       83 ec 04                sub    $0x4,%esp
//  401056:       8d 45 fc                lea    -0x4(%ebp),%eax
//  401059:       89 45 fc                mov    %eax,-0x4(%ebp)
//  40105c:       8b 55 fc                mov    -0x4(%ebp),%edx
//  40105f:       83 c2 08                add    $0x8,%edx
//  401062:       8b 45 fc                mov    -0x4(%ebp),%eax
//  401065:       83 c0 08                add    $0x8,%eax
//  401068:       8b 00                   mov    (%eax),%eax
//  40106a:       83 c0 05                add    $0x5,%eax
//  40106d:       89 02                   mov    %eax,(%edx)
//  40106f:       c9                      leave
//  401070:       c3                      ret

The first two instructions are the preamble which we’ve seen before with main().

//  401050:       55                      push   %ebp
//  401051:       89 e5                   mov    %esp,%ebp

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:

void foo()
{
	int* p;
	p = (int*)&p;
	p[2] += 5;
	return;
}

Running this code produces the following output:

$ ./test.exe

]]>

Sort Algorithms

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.

Bubble Sort

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;
			}
		}
	}
}

Selection Sort

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

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;
		}
	}
}

Shell Sort

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
[[7], [6], [5], [29], [19], [33], [71], [38], [38], [72], [43], [53], [73], [83], [57]] => [[6], [7], [5], [29], [19], [33], [71], [38], [38], [72], [43], [53], [73], [83], [57]] => [[5], [6], [7], [29], [19], [33], [71], [38], [38], [72], [43], [53], [73], [83], [57]] => [[5], [6], [7], [19], [29], [33], [71], [38], [38], [72], [43], [53], [73], [83], [57]] => [[5], [6], [7], [19], [29], [33], [38], [71], [38], [72], [43], [53], [73], [83], [57]] => [[5], [6], [7], [19], [29], [33], [38], [38], [71], [72], [43], [53], [73], [83], [57]] => [[5], [6], [7], [19], [29], [33], [38], [38], [43], [71], [72], [53], [73], [83], [57]] => [[5], [6], [7], [19], [29], [33], [38], [38], [43], [53], [71], [72], [73], [83], [57]] => [[5], [6], [7], [19], [29], [33], [38], [38], [43], [53], [57], [71], [72], [73], [83]]
[5, 6, 7, 19, 29, 33, 38, 38, 43, 53, 57, 71, 72, 73, 83]
endamath

Merge Sort

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)
		return;
	lenl = len / 2;
	lenr = len - lenl;
	l = arr;
	r = arr + lenl;
	merge_sort(l, lenl);
	merge_sort(r, lenr);
	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;
			r++; lenr--;
			l++;
		}
		else
		{
			l++; lenl--;
		}
	}
}

Heap Sort

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[0] is the root node, array[1] is the left child, array [2] is the right child, array [3] is the left child of array[1], array[4] is the right child of array[1], 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;
		}
		else
			break;
	}
}
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;
	heapify(arr, len);
	for(i = len; i > 1; i--)
	{
		swp = arr[0];
		arr[0] = arr[i - 1];
		arr[i - 1] = swp;
		sift_heap(arr, 0, i - 1);
	}
}

Quick Sort

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).

void quick_sort(int* arr, int len)
{
	int i, j, p, swp;
	if(len <= 1)
		return;
	p = 0;
	j = 1;
	for(i = 1; i < len; i++)
	{
		if(arr[i] < arr[p])
		{
			swp = arr[i];
			arr[i] = arr[j];
			arr[j] = swp;
			j++;
		}
	}
	swp = arr[p];
	arr[p] = arr[j - 1];
	arr[j - 1] = swp;
	quick_sort(arr, j);
	quick_sort(arr + j, len - j);
}

Bucket Sort

Bucket sort organizes the data into buckets that hold a range of values, for example 0-10, 11-20, 21-30, etc… Then each bucket is sorted using a different algorithm, in this case, insertion sort.

void bucket_sort(int* arr, int len)
{
	int i, j, k, n, max, **buckets;
	max = arr[0];
	for(i = 1; i < len; i++)
		if(arr[i] > max)
			max = arr[i];
	n = (int)floor(sqrt(max));
	n = max / n;
	buckets = (int**)malloc(sizeof(int*) * (n + 1));
	memset(buckets, 0, sizeof(int*) * (n + 1));
	for(i = 0; i < len; i++)
	{
		if(buckets[arr[i] / n] == NULL)
		{
			buckets[arr[i] / n] = (int*)malloc(sizeof(int) * len);
			memset(buckets[arr[i] / n], -1, sizeof(int) * len);
		}
		for(j = 0; buckets[arr[i] / n][j] != -1; j++);
		buckets[arr[i] / n][j] = arr[i];
	}
	k = 0;
	for(i = 0; i <= n; i++)
	{
		if(buckets[i])
		{
			for(j = 0; buckets[i][j] != -1; j++)
			{
				arr[k++] = buckets[i][j];
			}
			free(buckets[i]);
		}
	}
	free(buckets);
	insertion_sort(arr, len);
}

]]>