A broken Sapphire Radeon HD 4850 somehow ended up in my possession. I didn’t know what was the problem, so I tried to plug it in in a mobo I just had lying around, running the nightly oneiric.

The card showed up fine in lspci. I didn’t try using it with the open-source drivers, as I’m not interested in putting a display on it. Instead I wanted to play around a little with OpenCL, so I went for the closed-source Catalyst driver. (This was a few days ago, when 11.6 was the newest version around - I haven’t tried it with the latest 11.7 or with the 11.8 preview versions.)

The driver didn’t start, X choked on this error:

(EE) PPLIB: PP_Initialize() failed.

Since the driver is not open-sourced, googling around didn’t reveal any usable source code on PP_Initialize. So I turned to objdump.

$ objdump -CRd fglrx_drv.so

This revealed a few things about PP_Initialize. (I don’t think I should post any dumps here, as I believe that would violate copyright laws.) I assumed it returns a status code, so I tried overloading it and returning a different status code instead:

$ gcc -shared -fPIC -o preload.so preload.c -ldl
$ LD_PRELOAD="`pwd`/preload.so" startx

This will start the X server but with our library preloaded. With a status code of zero, the server now continued the loading of the driver, but of course other errors have emerged. So I ended up overriding a couple more functions.

I was wondering if maybe PPLIB is part of the code that manages PowerPlay functions, and if maybe just disabling it all and setting the fan speed manually to 100% would give me a result.

Well, I was wrong. The only thing I gained was some experience with objdump, reverse-engineering, some C and assembly. After disassembling the card itself, I noticed that one of the conductors on the GPU seemed to be burned out - probably causing card initialization to fail.

I also learned that when pre-loading with LD_PRELOAD, the overriding function should accept the same number of arguments as the overriding function, otherwise crap will be left on the stack, messing up the rest of the code. To figure out how many parameters a function takes, it is usually enough to fund it in the objdump output, look at the assembly, and count how many things are popped off the stack before returning.

The pops usually occur around the top of the function body, just before the ret statement, so no need to follow any jumps. Note to discard stack pointer registers, %ebp and/or %esp.

Another thing I’ve learned playing around with GPUs is the fact that X has to be running in order for OpenCL to work on a card. No displays are necessary, but the Device sections in xorg.conf need to reference the proprietary drivers (as the open-source ones don’t provide OpenCL support at the moment).

Exponentiation of large numbers can easily be implemented using exponentiation by squaring, which greatly reduces the number of steps it is needed for a given imput. Computing large exponents modulo a number is even faster and requires less memory, as it reduces the size of the resulting integer.

The following implementation works for both Python 3 and python 2 (although in Python 3 it will run faster):

Due to the modulo, the resulting function will be very fast: for example, it calculates mesq(3**5**7, 11**17**3, 69) in a matter of milliseconds.

To get the idea behind, set the debug keyword argument to True. This will show you how it actually calculates the result:

>>> mesq(7, 30, 5, True)
(7**30)%5 =
((7%5)**30)%5 =
((((7%5)**16)%5)*(((7%5)**8)%5)*(((7%5)**4)%5)*(((7%5)**2)%5))%5 =
((((((((((7%5)**2)%5)**2)%5)**2)%5)**2)%5)* \
 (((((((7%5)**2)%5)**2)%5)**2)%5)* \
 (((((7%5)**2)%5)**2)%5)* \
 (((7%5)**2)%5) \
)%5 =
4

And finally, if you’re wondering where would you need madular exponentiation, well, it comes in handy for example when generating Pratt certificates.

Update

Do not actually use this code. This is just an example. A way faster implementation is the built-in pow(), which also accepts a third argument (the modulo).

My lovely girlfriend now wife and I have attended the first four days of Buschenschanksprint 2011, in the beautiful hills and vineyards of Berghausen, in Styria, Austria.

We had some great time, visited some Buschenschänke, and, of course, wrote a lot of code. I mostly worked on code that was related to the project I’m working on. Nevertheless, during the sprint we’ve implemented a new library, a YAML connector for the YAFOWIL form/widget library, called yafowil.yaml. I also contributed a patch to rod.recipe.appengine, which is already publisted on PyPI.

We’ve also fixed a few small bugs in cone.app and cone.tile, AnneGilles and rnix improved the documentation/tutorial, Gogo worked on the axg stack, and AnneGilles showed us a tutorial on their new S3-compliant database.

This was the sprint location…

…and this was the view from the location.

Inspired by Ivan Vanderbyl’s implementation, I also put together a progress bar, in pure CSS. The transition of the blue bar is also done with CSS, only the text is being updated with JavaScript. The animation is done using JavaScript to make sure it synchronizes nicely with the percentage text. It is also possible to animate it with pure CSS though.

The full code is in one simple HTML file, available in the public domain. Demo code can be found here.

Tested with:

• Chromium/Chrome 12
• Firefox 4
• Opera 11
• Android Browser (Froyo, with minor style glitches)

Today I had some free time, so I played around with the OpenStreetMap API. It turns out it’s quite easy to draw 3D-looking buildings on a canvas. After an hour or two of coding, I was able to render actual buildings from the OSM database:

Buildings rendered on a canvas

On the above picture, red buildings are “primary” ones (i.e. ones with an address or a house number), while the grey ones are “secondary”. A demo version of the canvas map can be seen here (but only by people with decent browsers).

As a comparison, here’s how Mapnik renders the same data:

Same map rendered by Mapnik

Even nicer is the result when it is drawn over Mapnik’s tiles:

The two images merged together

The above result could be improved by not rendering any of the buildings by Mapnik, only the ground, & the roads. Then the canvas renderer could just place everything else on top of the Mapnik layer (including amenities and other interactive elements).

While maps rendered on the server side are more compatible with old browsers, canvas-based maps can be made more interactive (e.g. hovering or clicking on a building could highlight it and pop up a message with the complete address or relevant information). Other projects, such as Cartagen, are capable of rendering a high variety of objects, not just buildings, but they still require a lot of improvements, for example the display of road names is note very optimal.

Hopefully, as more browsers support HTML5 and canvas by the day, people will implement great interactive applications using this technology.

Yesterday I figured I’ll try to factor the first few numbers greater than 10¹⁰⁰⁰⁰⁰⁰⁰⁰ (or at least find their smallest divisors). The idea was to see how hard it is to find the divisors of the first few hundred 100,000,001-digit numbers.

I took a pretty simple approach: for each prime number p, calculate 10¹⁰⁰⁰⁰⁰⁰⁰⁰%p (the remainder after dividing by p). Then I used the result to create a partial sieve. After the first 300,000 primes, I still couldn’t find a divisor for 10¹⁰⁰⁰⁰⁰⁰⁰⁰+37.

Update

10¹⁰⁰⁰⁰⁰⁰⁰⁰+37 is divisible by 6,870,527 (the 468,407th prime). The next one without a known divisor is 10⁹⁹⁹⁹⁹⁹⁹⁹+69 (tried to divide by the first 2,348,559 primes, no factors found so far).

Here’s the smallest prime divisor for the first few 100,000,001-digit integers (I = 10¹⁰⁰⁰⁰⁰⁰⁰⁰):

.------------------.
| number | divisor |
---------+----------
|      I |       2 |
|  1 + I |   10753 |
|  2 + I |       2 |
|  3 + I |       7 |
|  4 + I |       2 |
|  5 + I |       3 |
|  6 + I |       2 |
|  7 + I |     113 |
|  8 + I |       2 |
|  9 + I |     197 |
| 10 + I |       2 |
| 11 + I |       3 |
| 12 + I |       2 |
| 13 + I |      29 |
| 14 + I |       2 |
| 15 + I |       5 |
| 16 + I |       2 |
| 17 + I |       3 |
| 18 + I |       2 |
| 19 + I |    2087 |
| 20 + I |       2 |
| 21 + I |      11 |
| 22 + I |       2 |
| 23 + I |       3 |
| 24 + I |       2 |
| 25 + I |       5 |
| 26 + I |       2 |
| 27 + I |      37 |
| 28 + I |       2 |
| 29 + I |       3 |
| 30 + I |       2 |
| 31 + I |       7 |
| 32 + I |       2 |
| 33 + I |      17 |
| 34 + I |       2 |
| 35 + I |       3 |
| 36 + I |       2 |
| 37 + I | 6870527 |
| 38 + I |       2 |
| 39 + I |     139 |
| 40 + I |       2 |
| 41 + I |       3 |
| 42 + I |       2 |
| 43 + I |      11 |
| 44 + I |       2 |
| 45 + I |       5 |
| 46 + I |       2 |
| 47 + I |       3 |
| 48 + I |       2 |
| 49 + I |      13 |
| 50 + I |       2 |
| 51 + I |      71 |
| 52 + I |       2 |
| 53 + I |       3 |
| 54 + I |       2 |
| 55 + I |       5 |
| 56 + I |       2 |
| 57 + I |      31 |
| 58 + I |       2 |
| 59 + I |       3 |
| 60 + I |       2 |
| 61 + I |      59 |
| 62 + I |       2 |
| 63 + I |  399389 |
| 64 + I |       2 |
| 65 + I |       3 |
| 66 + I |       2 |
| 67 + I |      17 |
| 68 + I |       2 |
'------------------'