Align to 32 bits: it works, but how?

[NoCforMe]

In my other thread about creating a BMP from text I incorporated a clever bit of code that does 32-bit alignment. Since the lines of bitmap data must be aligned on DWORD boundaries, this code figures the actual bitmap size including any needed padding. I copped this from some code (C) I found somewhere.

Both examples assume 3 variables, BMPwidth, BMPheight and BMPbpp (color depth).

In C:

Code Select Expand

    actualBMPsize = ((BMPwidth * BMPbpp +31) & ~31) /8 * BMPheight;

which translates easily to assembly language:

Code Select Expand

MOV EAX, BMPwidth
MUL BMPbpp
ADD EAX, 31
AND EAX, NOT 31
SHR EAX, 3
MUL BMPheight
MOV actualBMPsize, EAX

So it works very nicely; no conditional tests or jumps like the code I previously came up with to do the same thing. But I can't for the life of me figure out how. How does this work?

Now you may be shaking your head and saying to yourself "this guy's a dummy". Which in certain ways may be true; I'm actually a fairly smart guy in some ways, but I have a hard time wrapping my head around a lot of things like this. I must have a blind spot somewhere.

I don't even consider this math, more like just arithmetic. So how does it work that adding one less than the alignment amount, and then ANDing the result with the NOT of that amount, give me the magic result?

One note: you'll notice that the code uses ~31, which I'd never seen before and had to look up in my C programmer's ref. Turns out the tilde means ones complement, which I'd never seen before in code. But using NOT as I did works just as well, for not-too-large positive numbers here.

This code would work as well for 64-bit alignment by using 63 instead.

So can someone here please explain how this works? Maybe @raymond?

Thanks in advance.

[Biterider]

Hi
The idea behind this is not that hard to understand. 
If you want to align something, you have to discard the offset (excess bits) from the address or size you want to align. 
This is done with the AND operation. The mask you need is made up of the bits you want to keep. In your case, you need to use "1111111111111111 1111111111100000" as mask, which is NEG 32 or NOT 31.
Trimming these last bits will result in lower addresses/sizes. If you want to have the next alignment point (in excess), you need to add (32 - 1) first.
Looking at your formula in C, there is something fishy there.

Biterider

[NoCforMe]

Thanks. That helps, sort of. But I still don't get how adding (# of desired bits of alignment - 1) works in this scheme.

Wait, I just reread your post. Now it makes sense; if you're going to align something, you need to figure where the next alignment address will be in case padding is needed. Gotcha.

I'd be curious to know what's fishy about the original formula. Is it their use of ones-complement? I found this on the web somewhere, can't remember where.

[jj2007]

Look at it in binary format (there must be a bin$ somewhere, but deb does the job, too):

Code Select Expand

  mov eax, $-123
  deb 4, "org eax", b:eax
  add eax, 31
  deb 4, "add 31", b:eax
  and eax, not 31
  deb 4, "not 31", b:eax
  shr eax, 3
  deb 4, "shr 3", b:eax

Code Select Expand

org eax b:eax           00000000010000000001000001010110
add 31  b:eax           00000000010000000001000001110101
not 31  b:eax           00000000010000000001000001100000
shr 3   b:eax           00000000000010000000001000001100
Btw you can use either not alignvalue or -alignvalue:

Code Select Expand

  deb 4, "not 31", b:not 31
  deb 4, "-32    ", b:-32

Code Select Expand

not 31  b:not 31        11111111111111111111111111100000
-32     b:-32           11111111111111111111111111100000
Attention: if you want to align a stack variable, skip the add reg, 31 step:

Code Select Expand

and esp, -16   ; now you can use movabs xmm0, [esp]

[Biterider]

Hi
Sorry, my fault (the ~ operator is a logical NOT, not NEG as I thought). All is fine.

Think of it this way, if your offset/excess bit is 1, adding (32 - 1) will get you to the next aligned address. Still 32 + (32 - 1) does!
That means that from the first bit to the full 32 bits in excess you will get using the formula the next aligned address.

Biterider

[Biterider]

Hi JJ

Btw you can use either not alignvalue or -alignvalue

That is not correct. it should be (not alignvalue - 1) = -alignvalue.

Code Select Expand

  and eax, NOT 32 - 1
  and eax, -32
Compiled

Code Select Expand

00007FF709F6B0C7 83 E0 E0             and         eax,0FFFFFFE0h 
00007FF709F6B0CA 83 E0 E0             and         eax,0FFFFFFE0h
Biterider

[NoCforMe]

Sorry, my fault (the ~ operator is a logical NOT, not NEG as I thought).

Are your sure? My C Wizard's Programming Reference shows that operator as ones complement.

Maybe it's just a fine point. There's a whole section on that operator:

Bitwise Negation (Ones' Complement)
The bitwise negation operator requires an integral type operand. It produces a ones' complement value of the operand. As such the following relationship is always true for two's complement machines:

   (~x == -(x+1))

The bitwise negation operator facilitates portability of expressions involving different size ints on different machines by avoiding hard-coded constants in bit manipulation expressions. In the following example the first expression works correctly and independently of the machine's int size. The second does not, potentially zeroing the highorder bits on machines of longer int length.

   val = i & (~0x3F);   /*GOOD - sizeof(int) insensitive */

   val = i & (0xFFC0);  /*BAD -  sizeof(int) sensitive   */

[Biterider]

Are your sure? My C Wizard's Programming Reference shows that operator as ones complement.

Not really. I looked here https://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B#:~:text=Outside%20class%20definitions-,Bitwise%20NOT,-~a%0A%3F%3F%2D

Biterider

[NoCforMe]

Hmmm; so Wikipedia** is never wrong?

This page begs to differ, as do many other pages from an online search.

** Wikipedia, the "encyclopedia" that any pimple-faced 7th grader can edit.

[jj2007]

That is not correct. it should be (not alignvalue - 1) = -alignvalue.

You are right, my wording was sloppy (corrected in red below). My code example was correct, though.

Btw you can use either not (alignvalue-1) or -alignvalue:

Code Select Expand

Code Select Expand

  deb 4, "not 31", b:not 31
  deb 4, "-32    ", b:-32Code Select Expand

Code Select Expand

not 31  b:not 31        11111111111111111111111111100000
-32     b:-32           11111111111111111111111111100000

[Biterider]

My code example was correct, though.