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.

Omeara

So, I'm curious, why would you do such a thing in assembly? – Moneywort

Because it's a project for a course I'm taking in Assembly ;) – Omeara

you should add the homework tag to questions like this, but this seems pretty reasonable, as it is at a high level, and you are not asking us to do the homework for you. – Moneywort

@Moneywort That's right. I thought of adding that tag but I'm not asking about one of the project's questions. – Omeara

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.

Dirac

Thanks alot Jason. I edited my question and changed rotation to transposition. I agree about the efficiency too. I'll see what I can find about it. – Omeara

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.

Lyly

Thank you Per Larsen. I have a BMP with 256x256 resolution and 96 dpi and the bit depth is 24. How can I know the RGB format of the picture? Is it the Bit Depth? – Omeara

Yeah. 24bit = R 8, G 8, B 8. Such BMPs don't support transparency AFAIK which is why it is 24 and not 32 bit. – Deductive

Thanks DeadMG. So it's a 24-bit RGB. – Omeara