Finding the next multiple of eight (implementing tabs)

[osdf_1]

I was developing my keyboard driver when I came across tabs. A tab should move the cursor to the next multiple of eight in a line. So I looked up tab implementations in the Bran's KDT source and found this:

Code: Select all

cursorX = (cursorX + 8) & ~(8 - 1);

(cursorX is the current x position of the cursor)
It feels wrong to copy code I don't understand to my kernel, so can someone explain this code to me?

Thanks

[Alboin]

Hi,

Code: Select all

cursorX = (cursorX + 8) & ~(8 - 1);

The part probably confusing you is the '~(8 - 1)'. (8-1) is 7. 7 in binary is 111. The '~' switches all the bits in the data: all the 1's become 0's and the 0's become 1's. This effectively creates a mask that masks the lower three bits of whatever data it is AND'd against. In this case, it is used to mask (cursorX + 8 ) So, if cursorX was 13, and one wanted to find the next tab, it would be:

(13 + 8 ) & ~7
21 & 0xfffffff8
16

The next tab, is thus 16. This works, because you're simply dropping the bits that holds the offset within your specific alignment. As another example, if you had a virtual address, and wanted to find its base page, all you would have to do is:

v_addr & ~(4096 - 1)

Here, you're dropping the last 12 bits, which holds the offset within a 0x1000 region.

Say, in decimal, that you wanted to find out how many thousands were in the number 9058. Obviously, there are 9. How did you do that? You just got rid of the 58.

Hope that helps,
Alboin

[osdf_1]

That really helped, thanks.

[Combuster]

For completeness sake, I want to add that this trick only works for alignments that are powers of two (indents of 5 or 10 won't work that way).

[Korona]

If your tab width is not a power of 2 you can use the following snippet:

Code: Select all

uint tabwidth = 3;
positionX += tabwidth - positionX % tabwidth;

If tabwidth is a power of two the compiler should be able to replace the modulo operation by an and operation.