Working with Big Numbers

When you need big integers in C++ you know you can turn to any mature library available online. If that isn't good enough, you can put something together using vectors and other STL goodies.

But if you ever need to find the factorial of 30 in the non-standard Borland TC 2 compiler, then you need...

the bignum<int> template!

The need for this arose because most of the code I wrote in school was for the TC 2 compiler. It uses a different template system, non-standard headers and matches function prototypes differently than GCC. It is also very relaxed about how you use const references. It invariably takes work to port the simplest programs to GCC, so anytime I had to reuse my old TC 2 code this template let me do any useful computation. I've used it many times to work with large numbers - computing factorials, testing primality (Rabin-Miller algorithm) and finding GCDs.

Source: bignum.cpp

It supports overloaded arithmetic operators (+ - * / ++ --), bitwise operators (& | ~ ^ >> <<), iostream I/O (>> <<), all the relational operators and a function to return a boolean value. While + and - are O(n), * and / are O(n^2) for n-byte integers. The code cannot be moved to GCC since it makes assumptions like sizeof(unsigned) being 2 bytes.

When I do eventually rewrite it, I'll probably build it around a vector<type> and let the bignum object manage it's own size dynamically. Moving from a 32 to 64-bit base type would be as simple as :%s/uint32_t/uint64_t/g

Grep replacement using my own Regex library

This one took a lot of testing! I had no idea it would be this much work to rewrite grep (the regex search utility on *nix.) But finally it's at a level of functionality that is actually useful to me.

A regular expression (regex) is a formal syntax that identifies patterns in text. There are variants, such as Perl's regex engine which differs from the Unix standard. I stuck with the Linux grep syntax, since I'm familiar with that. If you're not already using a grep-like utility in Windows, try this one, it's powerful enough to work with directories full of source files (it's especially handy for working with HTML/XML tags.) Moreover, it's a simple library which can be extended or used to build more complex apps.

Source:

regex.cpp (General purpose Regex library)

regex.h

main.cpp (Grep program - uses the Boost Filesystem Library)

The Regex library can also be used in C programs - simply rename the source to regex.c

It supports upto 9 backreferences, case insensitive search and can search any file containing text (it examines the first 1Kb for text characters) in terms of lines or bytes-from-start. It supports numerical ranges, shorthand range symbols like \d, \D and most parts of the standard regex language.

The heart of the program is the B+ tree that is created when a regex is fed into it. This tree then stays in memory while different input strings are matched against it's leaf nodes. The advantage of this NFA-based scheme is that matching at runtime is faster than with a system built on, say, derivatives where the regex string needs to be processed on every input character. Another advantage is that once built, complex regexes can be stored as search trees so they never have to be rebuilt.

It's not a paragon of efficiency - construction is O(n), worst case search performance is O(n^2) over a block of text. Only leaf nodes store data, but every node occupies 16 bytes. Despite this it can search very large directories in seconds.

There is only one issue with the program right now - it is designed for the Linux End-Of-Line scheme (LF). For any other encoding, bytes-from-start shown may be off by upto 10%.

It will probably be a long time before I work on a text manipulation program again... testing for all the edge cases was quite painful.

Bad, bad batchfile...

This set of batchfiles is the product of an evening spent online with nothing to do. I was reading up on the Windows command line, stuff I haven't touched since class 8 or so, and the end result isn't particularly useful (except to show your friends why Autorun should always be disabled on Windows XP.)

To see what it does, copy these files onto a pen drive with the same names:

autorun.inf

grue.bat

hendrix.m3u (This file must not be hidden)

The first batchfile, grue.bat is launched by autorun.inf when you double click on the pen drive. This batchfile opens itself recursively in minimised mode before quitting. It then copies Hendrix.m3u into C:\Documents and Settings\All Users\Start Menu\Programs\Startup, under the name syslock.bat, and then deletes C:\NTDETECT.COM before shutting down. As soon as the user logs in again syslock.bat is launched, which forces a shutdown. Congratulations, you're locked out of your computer!

One problem was that syslock.bat could not be a hidden file if it was to be copied into the startup folder. So I hid it in plain sight as a music playlist with the .M3U extension. There's probably a way to copy hidden files in DOS, but this works well enough for my purposes.

Fixing the damage done by the batchfile is straightforward - remove syslock.bat, then restore NTDETECT.COM (copy it from any other Windows installation.) You could connect the hard disk as a slave to do this but it's easier with BartPE (Preinstalled Environment), or a Linux live CD plus the drivers to write to an NTFS partition.

So there are essentially two things to learn from this:

(1) You can do a lot with batchfiles. Not as much as a shell script in Linux, but it's still neat!

(2) Antiviruses don't consider a batchfile a threat. How would they react to a more malicious script, I wonder.

New & Improved Memory Manager!

Here's something I was supposed to upload weeks ago - a better version of my memory manager (it would have been up sooner if ION wifi worked more often... I never remember this stuff when it does!) This one doesn't partition the available memory on startup - it dynamically sizes blocks, and provides the following replacements for the malloc.h functions:

qmalloc()

qfree()

qcalloc()

qrealloc()

Here is the source:

qmalloc.c

qmalloc.h

I've just used a volatile for locking so it's not threadsafe (read/write may get interleaved.) It should run basic applications without crashing though. See for yourself: Remove 'q' from the function names, compile it to a shared object and replace your system malloc.so on Linux. Alternatively, in your Bash profile you can set LD_PRELOAD to point to this shared object.

As for performance, this is faster than GCC's malloc for simple usecases.

On an unrelated note, if you're one of the unfortunates who have a PSP-2006 G (or any of the PSP 3000s), and want to play homebrew games, here are two useful links. The process has been tried successfully on two different PSPs. Tinkering with the PSP is risky so I'm glad Ishan (roomie) shared what he knew about it.

Review of Skulltag Doom

I've always had a special place in my heart for Doom for many reasons. It introduced millions of gamers to the world of 3D graphics (Chex Quest and Ultima may have preceded it, but neither had an interface as simple and polished as Doom). It was the first action game to hook gamers to internet and LAN play.

But more than anything, I liked the Doom engine because it was a great introduction to what was happening behind the scenes of the game. The characters were simple sprites, the walls were tiled with textures, and all of it was replaceable by custom content. The world was built out of 2D areas called sectors which had a fixed floor and ceiling height. There were no sloped surfaces, no complicated graphical effects, and almost no physics to speak of. The lighting was sector based, and the graphics were rendered by raycasting (since the resolution was low enough for this to be practicable.) All of this made it a joy to download new user-made WADs, or even make a few yourself using simple tools like DoomBuilder. It was, truly, child's play.

So I always like to keep a copy of Doom on my HDD and play it the way some people play Solitaire or Minesweeper. Until recently, I was using the official Windows 95 port of the game. Open source Doom ports have existed for years, but I never saw a reason to switch. Until now.

Skulltag is a multiplayer oriented Doom source port based on GZDoom, and it's a pretty impressive package. Of course, the art is top notch - great level design, plus the new weapons and enemy sprites look great. It plays at a blistering pace, much faster than Quake III Arena (closer in fact, to Quake I.) But what really hooked me about Skulltag was the way they managed to combine the best features of all existing Doom source ports. Skulltag supports both software and OpenGL rendering modes, but remains true to the original game in spite of it's graphical and technical enhancements. For example, a filtering mode is included that smoothens the pixelated graphics without blurring sprites completely. I've tried Zdoom before, and I noticed that hardware accelerated graphics looked significantly better on Skulltag. But it's not just that. Skulltag allows you to play Doom in all it's 2.5D glory while adding amazing touches like dynamic lighting, fake radiosity lighting, transparent surfaces, jump/crouch and the option for Quake style mouselook.

All this new technology is used to great effect. The first time you see a Cacodemon fire a purple, luminescent orb of plasma at you in a dark hallway, or step into a pool of glowing lava, or watch an Archvile resurrect an imp it *just* killed, you WILL pause the game to admire how good it all looks. The outrageous game design elements (pentagrams and baphomets!) that we miss terribly in modern "realistic" games are only accentuated by the new graphical touches.

Not all the improvements are superficial. The netcode is borrowed from csDoom, and supports 32 players as opposed to the 4 that Doom could support in the old days. In addition, Skulltag provides a number of new game modes like Invasion, Capture The Flag, and the titular Skulltag mode. All of these are backed up by well designed and balanced maps. It also has bots, and they offer an adequate challenge. Creating and joining servers is handled by the bundled IDESE application. It's quite easy to use but not exactly feature rich. As a server admin you may want something more sophisticated, like IDE. Skulltag's internal server browser is not as reliable, and it simply didn't work on Windows 7. Stick with IDESE for now.

If you want to take a trip back in time, or just have a LAN party with a bunch of friends, you can't go wrong with Skulltag. It's fast, it's fresh and it's faithful to the original. So go get it now!

11 Ways to Sort an Array!

sort.cpp: http://pastebin.com/f1b85d015

This program contains functions to sort an array of integers in descending order in 11 different ways :-

- Simple sort (Compare every element to every other element)

- Quicksort

- Dual pivot quicksort (The fastest general purpose sort)

- Insertion sort

- Selection sort

- Bubble sort

- Merge sort

- Heap sort

- Count sort (sorts in O(n) time)

- Bucket sort (works on data distributed uniformly across a range)

- Radix sort

The Dual Pivot Quicksort I wrote isn't as efficient as the one written by Vladimir Yaroslavskiy for the java.util.Arrays class, but the performance is better than the other sorting algorithms for large array sizes.

You can modify the code to sort in increasing order by interchanging > and <.

HashTable Template

Arrays, linked lists and other simple data structures do not allow us to search for an object in constant time. One way to solve this problem is using a Hash Table. It uses a hash function to reduce a key identifying the object to it's hash value in O(1) time, which is used to look up the object.

hashtable.cpp: http://pastebin.com/f66301bdd

(Tested on Mingw)

The hash table I have written here is a template. It will work with any of your classes, as long as it has a public field name and pointer to the next node. Collision resolution is done by simple chaining. I used char name[NAME] as the key, but you can use anything you want; just replace all the strcmp() calls by the appropriate comparison function.

I used my own hashing function, so replace it if you must:

hash(): Converts a char array into a hash

key(): Converts the hash into a integer key

hash() gives almost no collisions while key() has less than 10% collision rate. Because the hashtable only stores 1000 pointers, collisions will occur quite often in this particular program (when 1000 strings are entered 40% register as collisions). Obviously you'd want to use a better hashing function before plugging this into any real application.

You may also want to read up on salting the input.

Statistical Estimator - German Tank Problem

This was a little program I wrote to test the accuracy of statistical estimation in solving the German Tank Problem:

"Suppose one is an Allied intelligence analyst during World War II, and one has some serial numbers of captured German tanks. Further, assume that the tanks are numbered sequentially from 1 to N. How does one estimate the total number of tanks?"

The results were surprisingly accurate, giving a standard deviation of less than 10%, when the upper limit was calculated from 10 random numbers within the range.

estimator.cpp : http://pastebin.com/f79223e97

The program was originally written for GCC, but when I tried running it on Mingw (Windows) the rand() function returned only a 16-bit result. So I went for the Boost random number library to get sufficiently large random numbers for the test.

Partitioned Memory Manager

Hello world!

This blog will hopefully be a place where I can share code with friends, talk about programming and technology related stuff, and serve as a repository for my past stuff when I need it later...

To start off, here's something I worked on a while back: A memory allocator that implements the C functions nmalloc and nfree (which basically do the same thing as malloc and free in malloc.h).

nmalloc.c : http://pastebin.com/f72460c04

nmalloc.h : http://pastebin.com/f4a8b27bc

Memory is divided into many partitions by the function nmalloc_init. Each partition has an associated block size. All blocks within one partition have the same length. While this leads to internal fragmentation, it avoids the overhead involved in managing blocks of variable length. The blocks within a partition are chained into 2 linked lists – the Used list and the Free list. Each partition has it’s own pair of linked lists. (The layout of the partitions is provided by the calling program)

If you already know the sizes of objects that will be used in your program, it speeds up allocation considerably. Unfortunately it has considerable space overhead, and isn't exactly thread friendly. I haven't optimised it because the performance was good enough for my purposes :-

O(1) allocation and deallocation when memory partitions are empty, since operations are more or less independent of number of blocks etc. (Typical delay: 2-6 µs)

O(n) allocation and deallocation when partitions start filling up, since smaller blocks must be merged. Time taken becomes proportional to size requested.