Basically, you are given an address and you need it to be n-aligned, meaning you need the address to start on a multiple of n. The problem itself, is not a hard concept. The quickest way is to add the address with the alignment and subtract values until it's a multiple of n. You guarantee it's a multiple (or greater than a multiple) because you are adding n to the address.
So a solution to this might be:
uint64_t aligned = address + alignment;
while (aligned%alignment) --aligned;
However, address itself could be already aligned, so if we add by alignment-1, this will suffice to guarantee that it will pick the shortest length for an address-alignment with respect to the address.
uint64_t aligned = address + alignment - 1;
while (aligned%alignment) --aligned;
Adding more stipulations to the limits of alignment such as alignment must be a power of 2.
This simplies things now. We know that if it has to be aligned to be a power of 2, then we know it will be at least even. However, a rule with checking if something is a power of two is this:
int isPowerOf2(uint64_t x) {
return (x & (x-1)) == 0;
}
Therefore, no bits in x and x-1 are the same if x is indeed a power of 2.
Also, if we take address + alignment - 1 to be the initial step in this process, we know that the value will be greater than or equal to a power of 2 where alignment is a power of 2. This implies that if it is greater than or equal to a multiple of alignment, then we can just zero out the bits that alignment - 1 has, since it is required for it to have NO bits in common. And we know that no multiple of a power of 2 can have the (power of 2 - 1) bits set. This reasoning is actually pretty easy, if we add (power of 2 - 1), then it will have a remainder somewhere between 0 and power of 2 - 1; therefore, just zero out the bits that are there. Actually, this is indeed the solution.
uint64_t address_alignment(uint64_t address, uint64_t align) {
return ((address + align - 1) & ~(align - 1));
}
