The black magic of GDI+

One of the things I am most ashamed of on Quivi is its speed when opening large images (which are not uncommon nowadays, specially with digital photos). It’s embarrassing that the lame Windows Picture and Fax Viewer is lightning fast when opening those images!

I’ve always wondered how the Viewer did that. I’ve searched about it in the past but could never find anything about it. Then one of these days I was browsing the Wikipedia page about the Viewer and there I learned that it uses GDI+.

GDI+ is a C++ library, but it is built upon a flat C API which I could easily use in Python via ctypes. Long story short, I was able to modify Quivi to add support for viewing images with GDI+. And the result was amazing!

What about Linux? Well, something “equivalent” to GDI+ would be Cairo, so I did some tests with it too (luckily, support for it was included in wxPython recently).

Here are the results for the time to load a huge 5704px x 5659px PNG image and rescale it to 1/20 of its size:

Time to load and scale a PNG image
Library Time (s)
FreeImage 10.38
PIL 9.90
GDI+ 2.22
Cairo (from FreeImage) 3.60
Cairo (direct) 3.28

The reason for the two Cairo timings is that it supports reading directly from a PNG file but for e.g. JPG files you need to read the image with another library and to the format Cairo uses. I’ve used FreeImage to load the image and converted it to a Cairo surface.

Here are the results for the time to load and scaling the same image, but as a JPG:

Time to load and scale a JPG image
Library Time (s)
FreeImage 6.91
PIL 8.38
GDI+ 0.19
Cairo (from FreeImage) 1.43

Scary! How does GDI+ manages to do that? According to Wikipedia it uses hardware acceleration… Cairo doesn’t lag begind considering that the scaling only takes 0.015 (!) but I did notice that even its best quality scaling isn’t so good in comparison to the others, which is kinda odd.

Anyway, I’ll try to release a new version of Quivi with GDI+ and Cairo support soon. Stay tuned.

The Frobenius endomorphism with finite fields

The Frobenius endomorphism is defined as:

\Phi(x)=x^p

where p is the characteristic of the ring you’re working with. Simple, right?

If you’re working with a field with prime order, then Frobenius is actually the identity map. Since the order of the multiplicative subgroup is p, when you raise to the power of p you get back to x due to Fermat’s little theorem. Things get more interesting when you’re working with a extension field (i.e. a field which order is a prime power).

I’m studying pairings for my master’s degree and the Frobenius endomorphism appears all the time in their computation. For example, you need to do a “final exponentation” which can be split in multiple exponentiations, and some of them are to the power of p. This is good because powering to p is “easy” due to Frobenius, or at least all the papers I read said so. But for a while I couldn’t see why, and that’s the reason I’m posting this. It’s really easy; it’s just not that obvious to see why.

Continue reading The Frobenius endomorphism with finite fields

Quivi for Linux released

I’ve just released the Linux version of Quivi:

Quivi is an image viewer (specialized for comic/manga reading) for Windows which supports many file formats and compressed (zip, rar) files. It is aimed for fast & easy file browsing with keyboard or mouse.

It was working on Linux for a while, but now it’s “official”. I’ve released a .deb package which was tested on Ubuntu and may work on Debian. There’s also, of course, the source code, which requires some dependencies to be installed. You can grab both at the download page.

Help on packaging is much welcome, since I don’t have any experience releasing stuff for Linux. And please tell me if there is anything wrong with the release.

Visualizing group structure with colored addition/multiplication tables

When working with finite fields, if the number of elements is a prime power p^m with m > 1, you can represent the elements as polynomials with degree m-1 and do the field addition and multiplication modulo a irreducible polynomial with degree m.

The field GF(5) is composed by the numbers 0 to 4. We don’t need to represent its elements as polynomials since m=1. Addition is done modulo 5 and multiplication also modulo 5. So 2 + 3 = 0; 4 * 2 = 3; and so on. This is the addition table for GF(5):

Multiplicative table of integers modulo 5

The rows, top down, represent 0 to 4. The columns, right to left, represent 0 to 4. Each square is the result of the addition of the respective numbers in the row / column it belongs to. Black is 0, purple is 1, red is 2, orange is 3, yellow is 4.

Continue reading Visualizing group structure with colored addition/multiplication tables