Tuesday, March 3, 2015

Rounding up to page size

I was surprised yesterday to see an experienced programmer check in a terribly contorted piece of code to round a byte size up to the next page boundary.  Furthermore it still managed to be wrong.  Here is how to do it:

size_t page_size = getpagesize(); // Power of 2
total_size = total_size + ((page_size-1)&-total_size);

There are entire books on the subject but if you have to learn formula after formula by heart a book probably won't do much other than fill your head with things that still won't quite be what you need in the heat of battle.  Much better to understand why it is obvious:  Numbers mod m form an additive group, so normal addition and subtraction rules apply.  You wish to add something to total_size to get zero mod m? If x+total_size == 0 then x == -total_size (mod m).  Using (page_size-1)&... is a way of saying (mod 2**n) that frees us from the rather unnatural convention in computers for how modulo is computed that would otherwise give us a negative value, thereby rounding down, as this code does:

size_t page_size = getpagesize(); // Power of 2
total_size = total_size + (-total_size)%page_size;

By the way, the same logic works modulo any base.  To round down to the nearest 100:

rounded = value +(-value)%100;

Have fun, and kick ass in the small things as well as the big ones! :-)

No comments:

Post a Comment