What does (size + 7) & ~7 mean?

Question

I'm reading the Multiboot2 specification. You can find it here. Compared to the previous version, it names all of its structures "tags". They're defined like this:

3.1.3 General tag structure

Tags constitutes a buffer of structures following each other padded on u_virt size. Every structure has following format:

    +-------------------+
u16 | type              |
u16 | flags             |
u32 | size              |
    +-------------------+

type is divided into 2 parts. Lower contains an identifier of contents of the rest of the tag. size contains the size of tag including header fields. If bit 0 of flags (also known as optional) is set if bootloader may ignore this tag if it lacks relevant support. Tags are terminated by a tag of type 0 and size 8.

Then later in example code:

for (tag = (struct multiboot_tag *) (addr + 8);
     tag->type != MULTIBOOT_TAG_TYPE_END;
     tag = (struct multiboot_tag *) ((multiboot_uint8_t *) tag
     + ((tag->size + 7) & ~7)))

The last part confuses me. In Multiboot 1, the code was substantially simpler, you could just do multiboot_some_structure * mss = (multiboot_some_structure *) mbi->some_addr and get the members directly, without confusing code like this.

Can somebody explain what ((tag->size + 7) & ~7) means?

Answer 1

As mentioned by chux in his comment, this rounds tag->size up to the nearest multiple of 8.

Let's take a closer look at how that works.

Suppose size is 16:

 00010000         // 16 in binary
+00000111         // add 7
 --------
 00010111         // results in 23

The expression ~7 takes the value 7 and inverts all bits. So:

 00010111         // 23 (from pervious step)
&11111000         // bitwise-AND ~7
 --------
 00010000         // results in 16

Now suppose size is 17:

 00010001         // 17 in binary
+00000111         // add 7
 --------
 00011000         // results in 24

Then:

 00011000         // 24 (from pervious step)
&11111000         // bitwise-AND ~7
 --------
 00011000         // results in 24

So if the lower 3 bits of size are all zero, i.e. a multiple of 8, (size+7)&~7 sets those bits and then clears them, so no net effect. But if any one of those bits is 1, the bit corresponding to 8 gets incremented, then the lower bits are cleared, i.e. the number is rounded up to the nearest multiple of 8.

Answer 2

~ is a bitwise not. & is a bitwise AND assuming 16 bits are used:

7 is 0000 0000 0000 0111

~7 is 1111 1111 1111 1000

Anything and'd with a 0 is 0. Anything and'd with 1 is itself. Thus

N & 0 = 0

N & 1 = N

So when you AND with ~7, you essentially clear the lowest three bits and all of the other bits remain unchanged.

Answer 3

Thanks for @chux for the answer. According to him, it rounds the size up to a multiple of 8, if needed. This is very similar to a technique done in 15bpp drawing code:

//+7/8 will cause this to round up...
uint32_t vbe_bytes_per_pixel = (vbe_bits_per_pixel + 7) / 8;

Here's the reasoning:

Things were pretty simple up to now but some confusion is introduced by the 16bpp format. It's actually 15bpp since the default format is actually RGB 5:5:5 with the top bit of each u_int16 being unused. In this format, each of the red, green and blue colour components is represented by a 5 bit number giving 32 different levels of each and 32786 possible different colours in total (true 16bpp would be RGB 5:6:5 where there are 65536 possible colours). No palette is used for 16bpp RGB images - the red, green and blue values in the pixel are used to define the colours directly.

Answer 4

& ~7 sets the last three bits to 0