Dan Tillberg

For a recent project, I've been trying to integrate XML messaging into a Python gateway for a web service. I've been finding that the marriage of the two is not very Pythonic.

The problem is that I don't really like having code lying around that looks like this (exaggerated a little):

doc.getElementsByTagName('response')[0].getElementsByTagName('status')[0].getElementsByTagName('desc')[0].firstChild.data

That is obscene. This is the 21st century. And I'm using Python, not COBOL.

I want to use:

doc['response']['status']['desc']

to do the same thing. I think that with a little restriction on XML, that can be done.

The idea is to build a tree from Python dictionaries, lists, and strings. Attributes are not permitted. Sibling nodes with the same tag are permitted; this feature is too valuable to discard, though it does break the pure tree model.

Here is some sample XML and the tree I would build from it:

<?xml version="1.0" ?>
<response>
  <status>
    <type>OKAY</type>
    <desc>Everything is just fine.</desc>
  </status>
  <time>5:43 PM</time>
</response>

{'response': {'status': {'type': 'OKAY', 'desc': 'Everything is just fine.'}, 'time':'5:43 PM'}}

While trying to figure out the oft-repeated question, "Have I seen it or not?," I stumbled across http://www.romeoandjuliet.com/, seemingly unmodified from its original design when the movie was released in 1996. While we usually have to refer to the Wayback Machine for retro websites, this site has been caught in a time warp for twelve years, with some poor computer serving up the same unchanged pages for over a decade. It even has the same static banner ad for Volcano, a movie that came out the next year (1997).

As part of a new image analysis project, I wanted to convert an RGB image to HSV (hue/saturation/value). The basic math behind the transform isn't too complex, and if you're curious, I learned everything I need to know on wikipedia. The challenge I put to myself was to do this transform all in vector math (4 pixels at a time) and as efficiently as possible.

The easiest way (aside from throwing vectors to the side) to do this would be to pull red, green, and blue values into their own 4x32-bit float vectors, performing all of the math using floats. It took a fair bit of tinkering, but I finally managed to come up with a solution I can live with.

The basic setup of the problem is that, to start, I have a 16-byte vector containing 4 pixels, with pixels ordered as: 0xBBGGRR00. The alpha component (0's) is ignored. Note that this may be the opposite of the typical byte order. I'm working between a Windows client and the PS3 and have chosen to ignore byte-reordering for pixels to make my life a little easier. The output should be a 16-byte vector containing those same pixels converted to HSV, ordered as 0xVVSSHH00. The possible range for all values should be 0...255. Hues are as ordered/numbered in the wikipedia article.

A significant trick that helps to do a lot of cool things with vectors involves using bit rotations. For example, to find the sum of the values in a four-element vector, you can do it in two vector sums and two rotates, like this:

First, add the vector to a copy of itself in which each value is rotated one place to the left:

	A	B	C	D
+	B	C	D	A
=	A+B	B+C	C+D	D+A

Next, add that vector to a copy of itself in which each value is rotated two places to the left:

	A+B	B+C	C+D	D+A
+	C+D	D+A	A+B	B+C
=	(A+B)+(C+D)	(B+C)+(D+A)	(C+D)+(A+B)	(D+A)+(B+C)
=	A+B+C+D	A+B+C+D	A+B+C+D	A+B+C+D

The same trick works for finding the largest value: just replace A + B with max(A, B), and you'll find results that look like max(max(B, C), max(D, A)).

In the code below, I use this with a vector of four pixels in BGR0 form, using vector unsigned int rotations that rotate each 32-bit integer element of the vector (as opposed to rotating the whole 128-bit quadword). This is essential to processing all four pixels simultaneously.

The next thing to note is that I use some tricky code to calculate the correct factors for the hue. Depending on whether red, green, or blue has the maximum value, the factor could be either (G - B), (B - R), or (R - G). We cannot compute all twelve of these differences (three per pixel) simultaneously. Even if we wanted to, the SPU does not support 8-bit subtraction. It does, however, support an operation which takes the absolute 8-bit difference. I combine this result with a vector indicating whether the result is positive or negative (from a "compare greater" operation). After selecting the results that correspond to the max RGB values (there are only four - one per pixel), I invert any results that should be negative (by subtracting them from 0).

Anyway, read on for the source code...

Slashdot alerted me to the release of a new "top 500" list for supercomputers around the world. The new heavyweight champion, located at Los Alamos National Laboratory in New Mexico, USA, is built from a hybrid of AMD Opteron processors (about 6500) for I/O/management and IBM Cell processors (about 12,000) for computation.