Functional thinking

I started reading a book "Learn You a Haskell". It is truly wonderful, explaining complex things in a simple friendly way. Haskell itself seems to be the functional language. It's pureness makes you feel writing math  lemmas and theorems in a formal language, it is a very different feeling from C++/Boo I used to program in.

Surprisingly enough, functional programming makes us care about the goal, or a shape of the result. You answer questions like "What should it look like? What does it consist of?". At the same time, imperative programming involves asking the question "How?" most of the time.

As a first milestone and a practical task in learning Haskell I wrote the Burrows-Wheeler Transformation (BWT). I never thought it could be implemented in just 10 lines (not counting qsort), and remain nicely readable after that:

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort left ++ [x] ++ qsort right
where left = filter (<=x) xs
right = filter (>x) xs
bwt :: String -> (Int,String)
bwt input =
let buildMx [] _ = []
buildMx (x:xs) ch = (x:xs,ch) : buildMx xs x
mx = buildMx input (last input)
sorted = qsort mx
output = map snd sorted
base = head [ i | (i,(s,_))<-zip [0..] sorted, s==input ]
in (base,output)

Suffix sorting in linear time with no extra space

Intro
Suffix array construction (or, more generally, suffix sorting) is an important task of finding the lexical order of all sub-strings of a given string. It is heavily used in data indexing and BWT compression, which I've been doing for a long time to date.
First of all, it was surprising to me to discover that the subject is possible. By linear time I mean O(N) asymptotic execution time, where N is the input array size. By no extra space I mean that the only memory required is for the input array (N bytes), suffix array (4N bytes) and some constant storage (O(1) bytes).

Induction sort (SA-IS) is the key. Authors did a great work of exploring it. The major breakthrough was to use the induction to sort LMS sub-strings, in addition to using it afterwards to recover the order of all other strings. The only thing missing was a proper memory requirement for the algorithm. Authors claim 2N is the worst-case additional memory. Let's see how we can narrow this value down.

Proof
For an input string of size N, let's define M to be the total number of LMS-type suffixes. The memory (R(N,M) machine words) required for a recursive call consists of three sections:

• Suffix storage = M
• Data storage = M
• Radix storage = K(M), where K(M) is the number of unique LMS sub-strings

R(N,M) = M + M + K(M) <= 3M/2

Now, let's split LMS sub-strings according to their length. There can be LMS of size 1. There are L2 of size 2, L3 of size 3, and so on. Let's now define M and N in terms of these numbers:
M = Sum(i){ Li }
N = Sum(i){ i * Li }

We know that LMS of different size can not be equal. Therefore, we can safely split K(M):
K(M) = Sum(i){ K(Li) } = K(L2) + K(L3) + ... + K(Li) + ...
K(Li) <= Li

We know that the maximum number of unique sub-strings of size 2 can not exceed 2^16, which is a rather small number. For the convenience let's name a=L2 and b=L3+L4+...= Sum(i>2){ Li }. It is the time to give a better upper bound to R(N,M):
M = a+b
N = 2L2 + 3L3 + 4L4 + ... <= 2L2 + 3(L2+L3+...) = 2a + 3b
R(N,M) = 2M + K(M) = 2a+2b + K(a) + K(b) <= 2a+2b + 2^16 + b = 2a+3b + 2^16 <= N+O(1)

Well, that's it. By carefully arranging the data in memory and allocating just 2^16 additional words we can perform a recursive call to SA-IS, and, therefore, construct a complete suffix array.

Code
My version of SA-IS is called A7. Advantages to Yuta's SA-IS implementation (v2.4.1):

• 5N is the worst-case memory requirement. It doesn't depend on the input.
• No memory allocation/free calls inside the sorting procedure.
• Data squeezing: using smaller data types for recursion if range allows.
• Cleaner C++ code with more comments.

AI concepts mind dump

I've been thinking about AI structure for at least 7 years already. Thinking a bit and not too often, but steadily advancing. There is an open-source project where I'm doing all the practice, but today I would just like to dump the theory, giving my mind the more free space to advance.

Agent - a subject of AI, has a mind in a form of a neural network (NN).

In a time-step-based approximation an agent takes input from its receptors. The input is going through the NN producing some charge on the actor neurons. One of the actors is chosen each time step to be performed. The result of the action is spread back through NN, adjusting and optimizing the network structure.

Neuron - a base element of the NN, has:

• A list of pointers to output neurons (axons).
• Current charge and response.
• A memory map of stamp->charge.

Weights.

In a classical NN model inputs have different weights. This can be achieved in a uniform weight model (all inputs/outputs of a neuron are equal) if you start adding similar neurons with inputs being a subset of the original neuron inputs. Therefore, I'm going to throw weights off and take each input/output equally strong, distributing the signal uniformly.

Adaptation.

One of the experiments showed me that you can not go on with a static NN structure. You have to add, remove links and other neurons at least logically (one might say that biologically nothing new is created during the thinking  process, but I don't have any proof for that and I don't need it). Therefore, there is no point of adjusting the input weights by the agent adaptation process - pure neuron/link creation/removing heuristic would produce the same result and is required anyway.

Signal.

A neuron is not a function - it's just a multiplexer and a transmitter of the signal (which can me mathematically expressed as a function). Therefore, it has to preserve the total signal strength from inputs to outputs, taking some tiny portion for its efforts.

Memory.

Memory of an agent as a whole is constructed from the charges in the past stored within each neuron. A past charge does not have a time reference, but the mind can scan all neurons charges at once at some particular time stamp. It is still an open question of how these past charges participate in the decision process on an agent.

A long way to OS X

One beautiful morning I decided to try out Mac OS X on my laptop (MSI EX625). There were several reasons:

1. Apple hardware is too expensive.
2. The OS quality is outstanding, while the price is just 40$.
3. Need to try developing for Apple's mobile devices.

First facts I discovered was: "it is possible" and "there is TonyMac boot loader". Alright, I ordered a disk from eBay for 30$, starting to prepare myself mentally for a change.When the disk arrived, I was eager to try out tony's boot loader. Chameleon appeared on the screen, inviting me to start the installation. The first try failed - it couldn't reach the installer window, hanging half the way through.

I searched forums and started trying different boot options. Nothing actually helped. There were several errors on the screen, what confused me a lot, especially because an actual error causing the hang was not mentioned... I tried all possible ATI versions of iBoot (4+) and even PcEfi with no result. I've posted on the forums, waited, searched, but hadn't gotten any replies...

After heavy surfing I found out the actual reason - ATI Radeon Mobility video-cards are not supported! There was a chance that drivers could be released soon, but I couldn't wait, especially an undefined amount of time. I decided to exchange laptops with my wife, leaving old hard-drives. She didn't stop me, so I started to disassemble both laptops immediately, with a help of a small screwdriver. My new laptop was ASUS M51SN, with ultra-compatible GeForce 9500M on board.

Both Linuxes survived this change with honor: my Arch required to change the video driver, while Dina's Ubuntu worked perfectly like nothing changed (though, she updated the driver later). Mac OS X still didn't run out of the box, but required the following options: '-x' for safe mode, 'cpus=1' for proper cpu cores detection. That was sufficient, but I patched the BIOS using a custom version to enable proper CPU detection (the BIOS built-in update utility is awesome!).

Hello, the freaking installer! It wasn't easy at all to get you on the screen! I was happy for a short moment - the installer didn't like my MBR disk at all... Apple supports only GUID & Apple partition tables, intentionally ignoring MBR. There was a solution - to use the external USB disk/flash: to install on it first, and copy the partition to the hard drive directly. My 4Gb flash wasn't enough, and the official website states 5Gb requirements. Borrowing a 8gb USB flash was not enough as well, because the minimum installed configuration took 8.2Gb, what a surprise!

That was a time to sacrifice my precious 1Tb external USB drive. There was no space to backup to, so I decided to trick the installer a bit. I moved the actual data partition +20Gb from the start of the disk, leaving the empty space for the Mac OS image. I backed up the MBR together with first 100Mb of the FAT32, just to make sure the file system structure is saved. In the installer, I re-partitioned the drive into GUID 2 partitions : first 20G for Mac OS and all the rest. The installation went successful, yaw!

I copied the partition to the hard drive and was even able to boot from it: in a safe mode, using the same cd loader. Moreover, putting the old MBR back on the external HDD recovered it instantly, leaving me with a feeling of the epic win :) However, the OS X file system became corrupted each time I booted, forcing me to rewrite it from the image and look forums for an answer...  Posting again and asking for help in the OSX-86 IRC didn't help, leaving me in frustration again...

The sorting of my MBR seemed to be a good idea, if not for the corruption problem, but at least to make the boot loader work on the HDD. Fdisk did the job, but MBR was somehow damaged after that. I looked for a rescue and accidentally issued 'dd' command on the saved 100Mb file from my external drive backup... That was a bi-i-ig mistake, and it seemed to be the worst situation ever: the partition table together with my ext4 file systems were destroyed, so I had no OS to boot and no data to operate!

That's where smart hackers come into play. Asking again on the IRC, I attracted the attention of 'aschar', who listened to my problems and described the way out, in detail. The solution was to use a much less known Nawcom boot loader, that recently gained MBR support. In a day I managed to rebuild the partition table, entering some numbers by hand and using a couple of hack tools (look at testdisk!).

Using the PartedMagic liveCD I prepared the case-sensitive HFS+ partition and started Nawcom's boot loader. From now on, everything was smooth. The boot loader didn't require the safe mode, allowing me to install OS X right into the MBR partition I provided. After reboot, the OS loaded correctly, allowed me to update it to 10.6.4 and install MyHack tools from the same CD. No file system corruption, good driver support (though, sound & wifi are in progress) - and now I'm a happy owner of the Mac OS X laptop!

The end of story. The moral is:

• Always look for alternatives! What is more popular is not always of better quality.
• Always backup, at least MBR! Be careful with 'dd' and 'sudo' in general. Think, then do.
• Don't give up!

OpenGL revenge!

When I started my gaming life, there were many competing graphics API created by software companies & hardware manufacturers:

• Direct3D (all: Microsoft)
• OpenGL (all: open standard, ARB group)
• Glide (3Dfx only)
• MeTaL (S3 only)

The last two performed very well, but only on the corresponding hardware. Unreal Tournament & Deus Ex where the best games to test all these render modes in action.

Time passed, and Glide & Metal silently died, leaving GL competing with D3D, having only a single guard: Id Software. I can only guess what would happened to GL at that time if there was no John Carmack (Id lead programmer)... S3 technology was bought my MS that spread S3TC wisdom all over the word.

OpenGL standard developed very slowly, but easy extension mechanism allowed programmers to use all the new features Direct3D contained, and even more. Microsoft performed a massive information attack on GL (see FUD) leaving only cross-platform games alive.

Now there is XNA, Win7 with its DX11 and hordes of MS fans lurking around with their XBox'es. Other camp primarily consists of Unix/Linux systems, Mac OSX and a bunch of smart embedded devices including PS3. As far as I see, the time of revenge has finally come!

OpenGL ES (at least 2.0) has a very successful design: simple, portable, effective. It was developed by Khronos group that is now pushing forward OpenGL-3 standard. Microsoft was not able to spread it's massive OS on mobile devices, and now we have numerous game-dev companies working on iPhone & PS3 games using OpenGL ES only. Moreover, Linux & Unix community grows: they might not be willing to pay for games, but they are developing exclusively on GL. At the same time, we have Mac OSX users that easily afford themselves buying games, forcing major titles being released for this OS (take Dragon Age for example).

The conclusion is: there is no point to develop your engine primarily for Direct3D unless you want to run on XBox. OpenGL successfully covers all other platforms (there is only a little difference between ES and normal GL nowadays), has a clear extensible design and an open standard. Congratilation, my friends, our victory is close! And the world will be a little better place to live soon :)

P.S. Some people say you don't have to choose and support both API anyway. That's true, but don't forget about the future: your choice may shift the balance in this fight giving an initiative to the hands we can't trust.

Dev Status

A good start to run is to know where we are.

Compression: abandoned.
Pending: dark & archon support.
Ideas: doubling BWT sort on GPU/OpenCL.

Artificial Intelligence: abandoned.
Pending: NN self-development, experiments.
Ideas: rewrite in Boo + OpenTK.

Graphics: active.
Focus: kri, shading, computations.

Work: active.
Focus: physics, fur, water.

Internet: active.
Focus: kvgate.com project storage.

Network: abandoned.
Pending: marian, dracon & farpost support.
Ideas: password hash cracking on GPU.

Well, you can see lots of abandoned areas with interesting projects. What can I say... it's all about games, work & private life. I hope to revive at least some of them in future.

/boot

Welcome everybody!

This blog is not about feeling, neither about research achievements. It's not about anything in particular. It's just a scrapyard of my thoughts willing to be left in digital form (freeing space for more useful ones).

No rules, no promises. Enjoy! :)