How can I transpose an image in Assembly?

Question

I'm working on a project and I need to compute something based on the rows and columns of an image. It's easy to take the bits of the rows of the image. However, to take the bits of each column I need to transpose the image so the columns become rows.

I'm using a BMP picture as the input. How many rows X columns are in BMP picture? I'd like to see a pseudocode or something if possible too.

Answer 1

It sounds like you are wanting to perform a matrix transpose which is a little different than rotation. In rotation, the rows may become columns, but either the rows or the columns will be in reverse order depending on the rotation direction. Transposition maintains the original ordering of the rows and columns.

I think using the right algorithm is much more important than whether you use assembly or just C. Rotation by 90 degrees or transposition really boils down to just moving memory. The biggest thing to consider is the effect of cache misses if you use a naive algorithm like this:

for(int x=0; x<width; x++)
{
    for(y=0; y<height; y++)
        out[x][y] = in[y][x];
}

This will cause a lot of cache misses because you are jumping around in the memory a lot. It is more efficient to use a block based approach. Google for "cache efficient matrix transpose".

One place you may be able to make some gains is using SSE instructions to move more than one piece of data at a time. These are available in assembly and in C. Also check out this link. About half way down they have a section on computing a fast matrix transpose.

edit: I just saw your comment that you are doing this for a class in assembly so you can probably disregard most of what I said. I assumed you were looking to squeeze out the best performance since you were using assembly.

Answer 2

It varies. BMPs can have any size (up to a limit), and they can be in different formats too (32-bit RBG, 24-bit RBG, 16-bit paletted, 8-bit paletted, 1-bit monochrome), and so on.

As with most other problems, it's best to write a solution first in the high-level language of your choice and then convert parts or all of it to ASM as needed.

But yes, in its simplest form for this task, which would be the 32-bit RGB format, rotating with some multiple of 90 degress will be like rotating a 2-D array.