JSON

Last October, I wrote a JSON parser in C++ that constructs a document object structure. A visitor class provides convenient access to the document object, and a number of tests validate the parser. I've also relaxed the specification to permit strings without quotation marks assuming they meet the same rules as variables in a C-like programming language. Multi-byte encodings aren't as well-tested or covered.

I'm preparing to make it available under a BSD license. Here's a sample usage scenario from the test suite.


//
// Example JSON usage
//
try {
std::stringstream ss;
json::Parser parser;

// without quotes, and with weird spacing
ss << "{objects:[{id:1, location : [ 0, 0,0]},{id:2,location:[1.25,0.25,4]}]}";

json::Object *object = parser.parse_object(ss);
json::Visitor visitor(object);

json::Visitor obj0 = visitor["objects"][0];
json::Visitor obj1 = visitor["objects"][1];

if ((int)(obj0["id"]) != 1 || (double)(obj0["location"][0]) != 0) {
if (verbose) {
std::cout << "visitor test 0 - failed for obj0\n";
}
passes = false;
}

if ((int)(obj1["id"]) != 2 || (double)(obj1["location"][0]) != 1.25 ||
(double)(obj1["location"][1]) != 0.25 || (double)(obj1["location"][2]) != 4) {
if (verbose) {
std::cout << "visitor test 0 - failed for obj1\n";
}
passes = false;
}

delete object;
}
catch (common::exception &exp) {
passes = false;
std::cout << "parse failed for visitor test 0\n";
std::cout << exp.message << std::endl;
}


Turkey Albondigas

Emma and I are making this tonight: Turkey albondigas soup. It is spectacular.

Posted here for posterity.

Spring 2010

I'm enrolled in two Computer Science courses: CS 6505 for an unneeded grade, and CS 6520 for fun.

In CS6505 on Friday, I was asked to show the rationals are countable. Having seen this problem before, I quickly mapped the rationals onto discrete points in a 2D plane and, while waving hands, showed how they could be counted by spiralling outward from the origin. "There are different classes of infinity," I struggled to explain. The three gentlemen I was sitting with were not necessarily convinced I had done any math or that my explanation was adequate, so I cast about for a better method.

Here it is. Recall that N is the set of natural numbers: {1, 2, 3, ..}, integers are the set Z = {.., -2, -1, 0, 1, 2, ..}, and the rational numbers are numbers that are the ratio of an integer to a natural number. A set is countable iff there exists a mapping to the natural numbers.

Finite sets are of course countable, but showing that infinite sets are countable requires a bit more thought. The integers, for example, may be mapped to natural numbers as follows: let "0" be integer number 1, +1 be integer number 2, -1 be integer number 3, +2 be integer number 4, -2 be integer number 5, and so on. Easy.

Now for the rationals. Consider an integer a represented by the bits (a0 a1 a2 .. an), where a0 is 0 if a is positive and 1 if a is negative, while bits (a1 a2 .. an) denote the absolute value of a. Assume b is an n-bit natural number formed by bits (b1 b2 .. bn). The pair (a, b) represents some rational number. We may now form a string from the bit representation of (a, b) as follows:

(1 a0 a1 b1 a2 b2 a3 b3 .. an bn)

This binary string maps to a unique natural number. Moreover, we see that the set ZxN is a superset of the rationals (-10/5 and -2/1 are the same rational number but distinct in the superset ZxN). Because each element of this superset maps to a unique natural number, it is countable, and therefore the rationals are countable. qed.

My personal take-aways from this experience: (1) writing things down like this rather than drawing visual aids and pointing seems to make people more comfortable, and (2) trying to show something in two slightly different ways is a good exercise.

Southeastern Railway Museum

The day after Christmas, my parents, Emma, and I spent the afternoon at the Southeastern Railway Museum. Their large and growing collection includes a number of cosmetically restored rolling stock from railroads in the Southeast including several large steam locomotives. This post covers some of the photographs from that visit.


Savannah and Atlant #750 - This 4-6-2 "Light Pacific" built in 1910 pulled excursions all around the Southeastern U.S. including one in 1989 that I rode on. It was last operated that year and currently sits on static display, having been cosmetically restored.

Selection sort, 64-bit

Having haphazardly embarked on Agner Fog's informative C++ optimization guide [pdf], I decided it was time to write some x86-64 assembly to gain familiarity with the x86-64 instruction set.

Selection sort is an easy hello-world type application for assembly programming. On a Windows platform, getting Visual Studio and NASM to build a project together demanded a moment's tinkering, so I didn't want to be too ambitious.

The code listing follows. The best part is there is no stack frame to prepare or registers to spill. This doesn't do anything sophisticated like prefetch data, and of course isn't the best algorithm for sorting. It is pretty easy to spot the nested loops.

Posted for your amusement.


section .text code align=16

global selsort

; void selsort(int *A, int N)
;
; A: rcx
; N: rdx
;
selsort:
xor rax, rax

L1:
mov r8, rax
inc r8
mov r10, rax

L2:
cmp r8, rdx
jz L3

mov r11d, dword[rcx+r8*4]
mov r9d, dword[rcx+r10*4]

cmp r9d, r11d
cmova r10, r8

inc r8
jmp L2

L3:
mov r11d, dword[rcx+rax*4]
mov r9d, dword[rcx+r10*4]

cmp r9d, r11d
jge L4

mov dword[rcx+r10*4], r11d
mov dword[rcx+rax*4], r9d

L4:
inc rax
cmp rax, rdx
jnz L1

ret


netherp - share your naughty bits!

At Josh's request, I threw the source code to netherp v2 up on a public Github repository. Here is the URL:

http://github.com/kerrmudgeon/kerrutils/blob/master/netherp

netherp was originally intended to be a minimal-configuration HTTP server for sharing files among two machines of arbitrary make and model. One day a few weeks ago I became enthusiastic about asynchronous I/O and non-threaded server architectures, so I wrote a second version from scratch. It doesn't support HTTP PUT or POST or any method other than GET. There is no authentication, and I suspect there may be ways of compromising it.

Nevertheless, there it is. It's single-threaded, platform-independent [within reason], and relatively fast. On my quad-core 64-bit Linux platform in the lab, I ran http_load requesting a variety of files from my local GPU Ocelot repository ranging in size from a 1kB to 100s of kBs. It handled http_load's maximum of 1,000 requests per second without trouble; in this case, the network was the bottleneck. It has also served a 400 MB file over a residential cable connection, this time running on a Windows machine.

So, it's vetted. It works.

There are several barbaric components that ought to be hastily buried underneath a pile of complexity theory [i.e. the MIME type selector], but this does demonstrate working use of select() which lends some much-needed pedagogical value to this exercise.

Additional comments are certainly welcome.

One other facet of interest is I wanted this to be distributable as source, so I wrote a program to embed binary image files used as logos and icons into the source code of the application. It expresses a binary file as a C++ style array declaration. i.e.:

// 'images/file.png'
const unsigned int image_file[] = {
0x474e5089, 0xa1a0a0d, 0xd000000, 0x52444849,
0x30000000, 0x28000000, 0x608, 0x7987b800,
...
};

May not be the best way, but at least it's out the door.

Frigid Digit

Georgia Tech Sailing Club hosted its intra-club regatta on Saturday. Four 420s sailed out into Lake Lanier and completed a few races. It was very informal, and the light winds made things maddeningly slow at times, although things were never so calm as to prevent deliberate maneuvering.

I didn't win any of the races, but my crew and I came in second place a few times [which doesn't technically matter - sailing rewards winners only]. There are subtle tactical and strategic differences that distinguish experts that I began to pick up on. A strong start is key to dominating a pack of boats - you receive "puffs" of stronger winds earlier and can speed up to stronger positions. Additionally, good positioning and tacking strategies tend to grant a smart skipper right of way during those moments when two boats come upon each other.

There were some tactical matters as well. One boat just seemed to "go faster" in identical wind conditions. Since this regatta consisted of boats of the same class and make, presumably the fastest were those trimmed the best. After we stopped racing, I requested the experienced crews to sail a straight course up wind so that I could follow along and trim sails and crew locations to improve my speed relative to them. That helped considerably to identify the optimal sail positions.

Ralph's Picassa gallery of the day.

Here I am sailing downwind. This is the boring part of the race.

Image

The Nacra catameran that capsized after flying one of its hulls:

Image

Update

While getting my haircut today, I thought about what it might take to determine the optimal strategy for a particular boat under a given set of wind conditions in a regatta. Simplifying assumptions would be:

• uniform wind direction and speed across the entire area


• no other boats to create local calm areas with bad air or force suboptimal maneuvering


• uniform sea state


• ideal sail and boat trim

This hypothetical systematic approach would attempt to minimize total time around a pair of marks. Specifically, this would determine:

• what course to make that minimizes time to reach the upwind mark


• which tack to start on


• when to tack


• whether to "run" or "broad reach" during the downwind leg

Since being at the right place at the right time with the wind on the starboard side is advantageous when encountering other boats, the model might favor a starboard tack at certain points in the course.

It seems like this could be computed given

• an accurate speed model of the Club 420 under typical loading conditions for each point of sail


• performance model of a well-executed tack


• performance model of a well-executed gybe

This would attack the problem that, I suppose, gets answered through intuition and experience by 'good' skippers. Of course, it completely ignores the influence of other boats whose presence could easily compromise a good single-boat strategy. It also assumes the skipper and crew are good enough to maneuver in ways that satisfy the performance models; this depends on training and skill. Nevertheless, it seems like having a good theory here would be a great way to quickly gain a practical intuition that could be deployed out on the water.

Someone get me a performance model!