I’ve now completed the first version of the PwnOS design document.  Development can move forward now that the design has been fairly well cemented.

The design in the document does not reflect the current state of the code.  Significant differences include that the design is to be for 64-bit code, not 32-bit, and page memory will be managed in 2MB pages by disabling the lowest level of page tables instead of 64KB simulated pages made by handling real pages in groups of 16.  Also, there will be a large, read-only area devoted to libraries common to all processes.

Also included in the document are a brief analysis of high-performance computing and a comparison with other operating systems.

After being informed by a third party that RIM probably prefers to keep interview questions private, (okay, so it was actually much less polite than that, but I won’t hold that against anyone), I’ve decided to post about two questions other than those in my interview, but with slightly similar components to how I answered the otherwise-unrelated questions in my RIM interviews. I haven’t checked whether these answers would compile, since I wouldn’t be able to in an interview.

Question: Write a C function to select k random elements in a random order from a set of n pointers in O(k) time. The original set can be reordered.

void** selectRandom(void** pSet,DWORD n,DWORD k) {
    // Create the array to be returned, null-terminated
    void** pSelected = (void**)malloc((k+1)*sizeof(void*));
    pSelected[k] = NULL;
    DWORD selectedIndex = 0;
    // Select elements until no more needed
    while (k--) {
        DWORD index = (DWORD)((rand()*((QWORD)n))>>32);	// This is more uniform and faster than using modulus
        void*const element = pSet[index];		// Select the edge from the list
        pSet[index] = pSet[--n];			// Remove it by replacing with the last element
        pSelected[selectedIndex++] = element;
    }
    return pSelected;
}

Question: Write a C function to sort an array of floats (i.e. 4-byte floating-point numbers in the appropriate IEEE format) in O(n) time, where n is the number of floats in the array.

The answer needs a bit of explanation first. Positive floating-point numbers when interpreted as integers are in the same numerical order in both cases. e.g. 2.0 > 1.0 and the integer interpretation of 2.0 is greater than the integer interpretation of 1.0. Negative floating-point numbers when interpreted as integers are in the opposite numerical order. e.g. -2.0 < -1.0, but the integer interpretation of -2.0 is less than the integer interpretation of -1.0. Mixed sets of negative and positive numbers results in other special cases. What would be ideal is a constant-time bijective mapping from a floating-point number to an unsigned integer that will maintain perfect ordering through positive and negative numbers. It can be shown that there is exactly one such mapping, and it is simple enough to be constant time.

The mapping is: take the bitwise not of negative numbers, and flip the sign bit of positive numbers. After applying this to all numbers in the array, one can use 4-pass, base-256 radix sort on the numbers as unsigned 32-bit integers, then use the reverse mapping back to floating-point numbers. This works with 6 passes through the array. There is a way to do the full thing with 4 passes through the array, but it’s unsure which would be faster.

Context-sensitive auto-complete now works for some contexts.  Contexts that it doesn’t handle yet will just give you an apology message, since I’m leaving it at that for the Alpha.  It’s also not as flashy as I’m hoping to have it for the Beta, but it’s plenty sufficient for the Alpha.

I’m going to have to take a small break from PwnIDE to work on PwnOS if I’m planning to use PwnOS for my Operating Systems class project, ’cause PwnOS needs a lot more work to get anything up and running.  However, the first draft of the paper on PwnIDE is due at the end of October, so it’ll still be in my mind.  The remaining functionality for PwnIDE Alpha is mostly fixing loose ends, whereas the remaining functionality for PwnOS is a lot.  I’ll make it all work somehow.

It may seem a bit premature to be writing a user interface for PwnOS before it’s fully functional, but thanks to a simple wrapper library I’ve written, it’s now fairly simple to make and test PwnOS interface applications under Windows.

The rudimentary interface application I’ve written (mostly an interface library) is completely in C++, in case anyone was wondering whether you’d be able to make applications for PwnOS in something other than assembly language. I’m considering making a more formal interface library out of it so that:

1. It’ll be worth putting in the (or a new) repository, and
2. Other interfaces and applications will be able to use the same interface library

Here’s a screenshot of the current test interface:

Everything in this is simulated, including the cursor. When running in Windows, the program “thinks” that it’s writing to video memory, when really there’s a full-screen window reading that chunk of memory and writing it to the window 20 times a second. One of the funny things with that is that it’d be quite simple to instead take that chunk of memory and apply it to something like a cube, for Beryl fans.

The button will show 4 different images, one each for up, hover, down, and disabled. The cursor image is decoded from a GIF file, though there’s still a bug decoding GIF files that are much larger, so the background and button images are bitmaps.

I’m more focused on PwnIDE than on PwnOS at the moment, but I’ll try to figure out what to do with this interface library in case anyone’s interested in writing interface or other applications for PwnOS. The classes are quite reminiscent of Java’s interface API, so it shouldn’t be to hard to use and expand.

This blog now updates through wordpress.com, so people can actually post comments.   It also means that it’ll be easier to update, and that I can separate entries into categories for the front, PwnOS, and PwnIDE pages.  Now I’ll be able to give updates on each of the projects more often, and people can subscribe to one or more of them without subscribing to all of them.

There’s still a bug that I might not be able to fix any time soon, which is that when you post a comment, you’ll be redirected to the blog on wordpress.com instead of back here.  The issue is that the SCS web server doesn’t have the HTTP extension to PHP installed, so I can’t make POST requests to wordpress.com.  Hopefully that’s not too much of an issue.  The only other thing is that the dates on older blog entries were lost, so I put them in the message text.

Overall, this should be really handy.