Every once in a while, I come across something in someone’s code that is technically correct, but rather odd in such a way that leads me to believe that there are many programmers out there who are not really comfortable with pointers or relations between data types.  An example I’ve run across a few times is something like:

char myString[10];
int myFunction(char* text);
…
int blah = myFunction((char*)myString);

In case you’re wondering what’s odd, myString is already of type “char*”, so the typecast is redundant and misleading.  Someone only looking at the function call might look at it and wonder “Why is myString not a char* in the first place?”.

That brings me to something I’ve heard several people say before, that typecasting can take a lot of time.  Actually, typecasting one pointer type to another pointer type takes literally no time, because they are identical under the hood.  Typecasting a signed integer to an unsigned integer of the same size or vice versa also takes no time for the same reason.  If the compiler is smart, typecasting an integer type to a smaller integer type should also take no time, and the opposite is at most one instruction taking one clock cycle or less.  Typecasting between floating point types can take slightly longer, but still less than 10 clock cycles.  Sometimes, though, you need to operate on the actual representation of a floating point number, which can be gotten like “*((DWORD*)&myFloat)”, which, as confusing as it looks, also takes no time (or almost no time in some situations).

A pointer is an unsigned integer variable with the same size as the current CPU address size, since it holds an address.  If you’re making a 64-bit program, it’s 8 bytes (effectively a QWORD, or unsigned long long); if you’re making a 32-bit program, it’s 4 bytes (effectively a DWORD, or unsigned long).  However, C syntax can make this fairly difficult to see.  For example:

long* pArray;
long* pArray2 = pArray+16;
long* pArray3 = &pArray[16];

In this case, pArray2 is an unsigned integer with a value that is actually 64 more than pArray, not 16 more.  That’s because the C compiler assumes that you mean to get the address of the long at index 16 into the array, not offset 16, and since a long is 4 bytes, index 16 is 64 bytes past the beginning of the array.  As such, pArray3 has the same value as pArray2.  This, though, leads to some more interesting examples:

long elementA = pArray[16];
long elementB = 16[pArray];

Both of these lines are valid, but they may or may not have the same value.  If the compiler assumes that 16 in the latter case is a char*, then the result could be different than if it assumes that it’s a long*.  However, if you find yourself doing the latter, please step away from the keyboard and rethink what you’re doing.  At least it’s not as ambiguous as:

a += a+++++a+a++;

That line is valid in C and Java, and different C compilers will definitely give different results, and Java gives a different result yet again.  (In case you’re curious, it’s a bit easier to read as “a += (a++)+(++a)+(a++);”.)  Now I’m just rambling, though, so let’s get back on track.  I saw a line of code a couple of weeks ago that went something like:

BYTE* data;
...
WORD a = (WORD)(data[6] & 0xFF) + (WORD)(((data[7] & 0xFF)<<8)&0xFFFF);

I actually didn’t realize immediately what the big line was doing (though the real one was even more complicated), because getting a WORD (16 bits) from an array of BYTEs (8 bits) is as simple as either one of the following three lines.

a = data[6] + data[7]<<8;
a = ((WORD*)data)[3];
a = *((WORD*)(data+6));

The first one might be more familiar, and it’s the most similar to the original, but the latter two are actually more intuitive if you’re thinking about what actually needs to happen.  In memory, there are 2 consecutive bytes, with the least significant one first (unless you’re on some embedded system that still uses big-endian).  All you need to do is move those two bytes into variable “a”.  That’s what either of the last two lines does.  The first line gets the value of one byte, gets the value of the other byte and shifts it over a byte, adds the two bytes together to get the number that you had in the first place, and then move it into the variable.  In C, the latter two may look a bit more confusing, but in assembly language, they are much simpler, whereas if you wrote assembly that does something like the first line, people might start to giggle.

Another area of confusion comes with complicated types and the use of “const”, because many are not familiar with how to read the type.

char const * * const myVariable[5];

myVariable is an array of constant pointers to non-constant pointers to constant chars.  The reading of the type starts at the variable name and goes to the right (for the array brackets), then to the left (for the rest).  Added confusion comes with that it is valid to place the first “const” before “char” in the above line, and it would still be an “array of … pointers to constant chars”.  What’s more interesting is that since the name of the array is interpreted as its address, and its address can’t change, myVariable is also a constant pointer to constant pointers to non-constant pointers to constant chars.  Some compilers get very messed up in different ways when trying to deal with typecasts and “const” in different places in a type, but there are usually workarounds to those bugs.  It gets weirder with multi-dimensional arrays, though.  Take, for example:

char my2DArray[123][456];

my2DArray is an array of 123 arrays of 456 chars.  There’s nothing particularly exciting about that.  However, it’s partly equivalent to a constant pointer to constant pointers to chars.  As such, my2DArray[3] is a constant pointer to chars.  The key difference is that my2DArray[3] is not a pointer, in that it is not in memory, it is just an address.  “my2DArray[3]” is actually equivalent to “((const char*)my2DArray)+3*456″.  There is no array of pointers, only a single array of 123*456 chars with some fancy syntax.  That’s why if you pass a multidimensional array as a parameter (which would probably be silly) or pass a pointer to one (which would be less silly), you need to specify the size of all dimensions except the last (though you can have the size be the value of another parameter).  The compiler needs to know what to multiply by when indexing into it.  To sidestep the whole issue, you could use an actual array of pointers to chars or use a single-dimensional array and do the indexing yourself.

I find that in most of these cases, it’s easiest for me to think of things in terms of how it will appear in memory, since then it’s just a matter of finding the right addresses and moving what needs to be moved, but that takes some time to get used to.  Either way, there are a lot of interesting quirks with pointers and other data types.

Code Cortex now has a new website (which will be getting more content over the next month or so).  All future PwnIDE releases will happen there.

Also of note is that the Code Cortex Screensaver has now been released.  It’s fixed at 20 frames per second, and modern CPUs should easily be able to handle it (since an older CPU I was testing on was easily able to run it at more than 20 frames per second after I optimized it).  The source code for it is released as a sample project with PwnIDE, and on Google Code Hosting.  The video tutorial and the heavily debated speed comparison will be coming; I’ve just been side-tracked with a lot of other things.  I’ve implemented and compared versions in assembly, C/C++ (both VisualC++ and GCC), and Java.  The results are quite surprising, but you’ll have to wait a bit longer to see them in the videos.

I recently released what I’m calling PwnIDE 0.2.2b, with many bugs fixed from version 0.2.2.  The reason that it’s not 0.2.3 is that I’ve got 2 particular requirements for 0.2.3, namely proper support for external libraries (e.g. the Windows API) and a new language data format (which shouldn’t change any functionality until 0.2.4).

To support external libraries by parsing include files for those libraries, there also needs to be support for code elements without doc comments.  To support code elements without doc comments, all datatypes need to be identified before variables can be identified properly.  That means the code parser needs to change significantly from it’s current single-pass approach to a multi-pass approach.  Ironically, this should make initially parsing the code significantly faster, solving the long load time problem.  (The reason for that has to do with the observer pattern notifying everything whenever anything is parsed in the single-pass approach.)  This also gives me an excuse to organize the language handling code much better than the current all-in-one-file approach (see MASM.java).  Overall, things should be much better… after a lot of work.

Over the past 4 to 5 months, I have had an HP (Hewlett-Packard) laptop.  It worked fairly normally for a couple of weeks.

Then, the wireless card started not working some of the time.  Then within a few days, it rarely if ever worked.  Many people on the HP support forums seemed to have the same problem.  Apparently there was a problem with the laptop motherboards in the summer, because of which major devices (e.g. the screen) would just fail.  HP then fixed the motherboards… for all devices except the wireless card.

So, I got a USB wireless adapter.  It wasn’t perfect, and didn’t get the greatest reception, but it sufficed until two days ago.  Just two days ago, my laptop wouldn’t boot.  I don’t mean that it got to the Windows loading screen and told me there was a problem.  I don’t mean that it got the the BIOS loading screen and told me that it couldn’t find the OS.  I mean that the screen stays off, not even on and black, but completely off.  The lights on the keyboard light up, the DVD drive does its power on self test, and then after about 20 seconds, it resets and does the same thing again.  Then yesterday, it would stay on for about 1 second.  Today, it won’t turn on at all.

A friend of mine had the same issue with his laptop not booting, but with a brand new HP laptop.  He sent in his laptop to get fixed, and they told him that nothing was wrong with it, then sent it to the wrong person.  In all, it took over a month to get his laptop back, and when he finally got it back, although it would boot, HP had installed Vista, and didn’t give him the registration key for it.

Now I’m going to have to send mine away to get fixed, and so I may lose much of my work on the screen saver.  I got the neurons with a pulsating glow.  Hopefully I can recreate that once I get my laptop back.

The Code Cortex screen saver is coming along better than expected, and if all goes as planned, it should be ready in time for January.  It currently renders 87,000 semi-transparent spheres in the form of the Code Cortex cube of neurons comfortably at 20 frames/second (more than a screen saver really needs) and the rendering is done completely on the CPU.  It needs a processor that supports SSE3, and I’m running it on one of the two cores of my 1.6GHz CPU (I could have it use multiple threads, but it doesn’t need it right now).

It looks mildly cool right now, but hopefully it will look phenomenal and tax the CPU to the max (possibly both cores) once it’s done, and then the comparison with the C and C++ versions will be well worth while.

After a few all-nighters and a bit of banging my head against the wall, PwnIDE Alpha has finally been released.  It’s taken a lot of time and a lot of work, but the results are worth it.

I will be creating a small part of a larger set of video tutorials for PwnIDE over the next few weeks.  Stay tuned; they will make clear the useful features of PwnIDE and how best to use them.  Plus you’ll get a cool screensaver out of it.
There are many parts of it that still do not work for the simple reason that they haven’t been written yet, so I won’t yet accept bug reports.  However, I will accept feature requests, with the disclaimer that I have thought through a very large portion of what will be in PwnIDE Beta and even 1.0, and many things are not as they will be.  I’ve also released a draft paper on the motivations, design, status, and future plans for PwnIDE.  It’s not a full design document, but does give some insight into its operation.

This is a big milestone in a very long road for Code Cortex.  I’m looking forward to the next big steps.  They’ll be pretty awesome if they work out.

The second big D-Wave demo was just a few days ago (November 13th, 2007). This time, they demonstrated some image recognition in conjunction with one of the world’s leading experts thereof, whose image recognition company was recently bought out by Google.

The chip demonstrated this time was a 28-qubit chip, but like on “Whose Line Is It Anyway?”, the points don’t necessarily matter (yet). I don’t know for certain the relevant numbers of this chip, but the relevant numbers of the 16-qubit chip in February (as Geordie presented on his blog back in March) were 6, being the largest number of variables for which any quadratic unconstrained binary optimisation problem of that size can be solved, and 42, being the number of tunable superconducting devices on the chip. In a nutshell, 6 bits of “useful” output and 42x bits of input (the usefulness of which is not as easy to determine, and x being the number of bits of precision). One might ask “Why only 6 useful bits of output when it’s a 16-qubit chip?” but this discrepancy is due to limits on the physics impacting the chip design in ways that I don’t fully understand. As a completely different example of this sort of discrepancy, the “7-qubit” joke made by some research group with NMR (i.e. by constructing a molecule and shooting lasers at it) has only 2 useful bits of output (i.e. the factor 3 in binary is 11) and 4 useful bits of input (i.e. the input number 15 in binary is 1111).

That sort of splitting hairs aside, I’m quite amazed at some of the poorly-written news articles this time around, with gems of illogic like this excerpt from The Guardian:

“Have commercial quantum computers finally arrived? … A Google scientist seems to hope so but, unfortunately, the answer is probably no. Dr Hartmut Neven, Google’s expert on image searching, was involved in a demonstration of quantum computing on Monday - even though most scientists are extremely doubtful that any real quantum computing took place.”

So…… is The Guardian implying that this guy who’s “Google’s expert on image searching” just got hit in the head repeatedly to the point where he believes whatever D-Wave told him? That makes NO SENSE! He’s one of the world’s top experts on image recognition. Give him a bit of credit! Regardless of what this pool of “most scientists” that seem not to have said anything but to The Guardian thinks of D-Wave, some world-class expert on something practical seems to think that D-Wave can help out with this practical application at which he’s an expert! I think any startup company that can get a commendation like that is probably bound for big success. Must…. stop…. ranting…. *sigh*

Anyway, there’s been a lot of confusion among non-experts about what problems D-Wave is and isn’t still facing. By problems, I mean things for which a solution is still unclear. Some of these things that aren’t problems as I’m defining the word here may still take a lot of work, but they have a potential solution known. I’d just like to clear up some of the confusion people have when asking me about D-Wave.

• Cooling a chip to 4 milliKelvin (0.004 degrees Celsius above absolute zero) is not a big problem for D-Wave, since refrigeration technology has come a long way in the past few decades and D-Wave has several experts on this subject.
• Chip fabrication is not a big problem for D-Wave (as far as I know). They could probably have a chip with 100,000 qubits made without much trouble; it just wouldn’t work without having tried chips of smaller sizes first.
• Reducing the size of the whole shebang to a manageable size (e.g. less than room-sized) is probably not a big problem for D-Wave. I don’t know the details of this, but I’m fairly certain that they’ve got it covered.
• Power consumption by the cooling system is not a problem. The cooling system may take a while to cool the chip, but once it’s there, as Geordie has said on his blog several times, very little power is needed.
• Controlling a chip from conventional computers isn’t a problem for D-Wave in one sense, and may or may not be in another (I don’t know the details). The actual communication is not a major problem at all. This sort of thing is, however, why there is a projected huge jump in the number of qubits from a small number like 16 or 28 to a big number like 512 or 1024. It’s not like they are just stating impressive figures for no reason.
• Making use of D-Wave’s system as a client-side programmer shouldn’t be too hard at all. The software team at D-Wave has a pretty good system in place to provide a few simple APIs for programmers (and possibly non-programmers) to make use of the system. You don’t need to understand transistors to program for a conventional computer, so you don’t need to understand qubits to program for a quantum computer.
• Scott Aaronson is not a problem for D-Wave. He is not a physicist of any sort, let alone a quantum physicist, and he doesn’t appear to be a particularly good computer scientist. Computer Science is an APPLIED science, and he seemingly wouldn’t know how to apply any computer science if his life depended on it. If he could produce ANYthing to actually make use of the pointless nonsense he spouts, then he’d be a computer scientist; until then he’s just a surly mathematician and a wannabe computer scientist. (I do think the quantum mechanical analysis of roast beef would’ve been awesome, though.)
• Chip design is probably not a problem for D-Wave, in that every chip-design-related issue that came up while I was at D-Wave got solved before I even knew that it was an issue related to chip design. Saying that they’ve got some good experts on this is an understatement.
• Funding may or may not be a problem for D-Wave. As Geordie (or Herb?) said in some quotation in some article I read, if they don’t get to around 512 qubits by the end of 2008, they could be in trouble.
• The actual quantum physics of it, I haven’t the slightest clue as to whether it’ll be a problem or not, because I don’t understand more than the “dumbed-down” versions of the quantum physics behind the chips. I do know (from some experimental results that will be presented at several universities shortly) that the chips aren’t acting based on classical physics, as Geordie has said on his blog a few times. That doesn’t necessarily mean that there will be speedup from the quantum physics, but it can’t hurt.

D-Wave, in one sense, is actually fairly safe. Supposing the quantum physics doesn’t scale up at all, they can still (much more easily, in fact) have a certain speedup simply from using superconducting components instead of semiconductor components, not to mention an even bigger improvement in computational power units per electrical power unit. Supposing even that fails, they should still have some of the best software in the world for solving these tough problems. If that fails, they’re out of luck, but unless that happens, I’ll be rooting for them, regardless of where I’m working. I may end up back there someday, or if I do a startup with Code Cortex, I may even end up indirectly helping them out.

Anyway, hats off to D-Wave for their second big demo, and I can’t wait to see any video/images of it online. Best of luck on the road ahead.

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.

I’ve had two interviews for Research In Motion this past week, both for interesting positions in the Operating Systems Group there. Both were phone interviews, so the coding questions were a bit awkward to answer over the phone. I thought I’d provide my answers here in case the interviewers happen to look back at my website.

***I have decided that it would be best to instead post about questions that are different from the ones in the interview, but I will save these for another post.***

I’m back home in Deep River again.  I’ll miss D-Wave, but it’s good to be back.

It’s good to see my friends from high school, and I’ll have some more time to work on PwnIDE before school starts.  Hopefully I can get at least basic functionality (i.e. being able to create a project, create files, create functions, edit functions, save) ready by the time I get back to class on the 6th.

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.