How to align a pointer in C
Is there a way to align a pointer in C? Suppose I'm writing data to an array stack (so the pointer goes downward) and I want the next data I write to be 4-aligned so the data is written at a memory location which is a multiple of 4, how would I do that?
I have
uint8_t ary[1024];
ary = ary+1024;
ary -= /* ... */
Now suppose that ary points at location 0x05. I want it to point to 0x04.
Now I could just do
ary -= (ary % 4);
but C doesn't allow modulo on pointers. Is there any solution that is architecture independent?
Solution 1:
Arrays are NOT pointers, despite anything you may have read in misguided answers here (meaning this question in particular or Stack Overflow in general — or anywhere else).
You cannot alter the value represented by the name of an array as shown.
What is confusing, perhaps, is that if ary is a function parameter, it will appear that you can adjust the array:
void function(uint8_t ary[1024])
{
ary += 213; // No problem because ary is a uint8_t pointer, not an array
...
}
Arrays as parameters to functions are different from arrays defined either outside a function or inside a function.
You can do:
uint8_t ary[1024];
uint8_t *stack = ary + 510;
uintptr_t addr = (uintptr_t)stack;
if (addr % 8 != 0)
addr += 8 - addr % 8;
stack = (uint8_t *)addr;
This ensures that the value in stack is aligned on an 8-byte boundary, rounded up. Your question asks for rounding down to a 4-byte boundary, so the code changes to:
if (addr % 4 != 0)
addr -= addr % 4;
stack = (uint8_t *)addr;
Yes, you can do that with bit masks too. Either:
addr = (addr + (8 - 1)) & -8; // Round up to 8-byte boundary
or:
addr &= -4; // Round down to a 4-byte boundary
This only works correctly if the LHS is a power of two — not for arbitrary values. The code with modulus operations will work correctly for any (positive) modulus.
See also: How to allocate aligned memory using only the standard library.
Demo code
Gnzlbg commented:
The code for a power of two breaks if I try to align e.g. uintptr_t(2) up to a 1 byte boundary (both are powers of 2: 2^1 and 2^0). The result is 1 but should be 2 since 2 is already aligned to a 1 byte boundary.
This code demonstrates that the alignment code is OK — as long as you interpret the comments just above correctly (now clarified by the 'either or' words separating the bit masking operations; I got caught when first checking the code).
The alignment functions could be written more compactly, especially without the assertions, but the compiler will optimize to produce the same code from what is written and what could be written. Some of the assertions could be made more stringent, too. And maybe the test function should print out the base address of the stack before doing anything else.
The code could, and maybe should, check that there won't be numeric overflow or underflow with the arithmetic. This would be more likely a problem if you aligned addresses to a multi-megabyte boundary; while you keep under 1 KiB, alignments, you're unlikely to find a problem if you're not attempting to go out of bounds of the arrays you have access to. (Strictly, even if you do multi-megabyte alignments, you won't run into trouble if the result will be within the range of memory allocated to the array you're manipulating.)
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
/*
** Because the test code works with pointers to functions, the inline
** function qualifier is moot. In 'real' code using the functions, the
** inline might be useful.
*/
/* Align upwards - arithmetic mode (hence _a) */
static inline uint8_t *align_upwards_a(uint8_t *stack, uintptr_t align)
{
assert(align > 0 && (align & (align - 1)) == 0); /* Power of 2 */
assert(stack != 0);
uintptr_t addr = (uintptr_t)stack;
if (addr % align != 0)
addr += align - addr % align;
assert(addr >= (uintptr_t)stack);
return (uint8_t *)addr;
}
/* Align upwards - bit mask mode (hence _b) */
static inline uint8_t *align_upwards_b(uint8_t *stack, uintptr_t align)
{
assert(align > 0 && (align & (align - 1)) == 0); /* Power of 2 */
assert(stack != 0);
uintptr_t addr = (uintptr_t)stack;
addr = (addr + (align - 1)) & -align; // Round up to align-byte boundary
assert(addr >= (uintptr_t)stack);
return (uint8_t *)addr;
}
/* Align downwards - arithmetic mode (hence _a) */
static inline uint8_t *align_downwards_a(uint8_t *stack, uintptr_t align)
{
assert(align > 0 && (align & (align - 1)) == 0); /* Power of 2 */
assert(stack != 0);
uintptr_t addr = (uintptr_t)stack;
addr -= addr % align;
assert(addr <= (uintptr_t)stack);
return (uint8_t *)addr;
}
/* Align downwards - bit mask mode (hence _b) */
static inline uint8_t *align_downwards_b(uint8_t *stack, uintptr_t align)
{
assert(align > 0 && (align & (align - 1)) == 0); /* Power of 2 */
assert(stack != 0);
uintptr_t addr = (uintptr_t)stack;
addr &= -align; // Round down to align-byte boundary
assert(addr <= (uintptr_t)stack);
return (uint8_t *)addr;
}
static inline int inc_mod(int x, int n)
{
assert(x >= 0 && x < n);
if (++x >= n)
x = 0;
return x;
}
typedef uint8_t *(*Aligner)(uint8_t *addr, uintptr_t align);
static void test_aligners(const char *tag, Aligner align_a, Aligner align_b)
{
const int align[] = { 64, 32, 16, 8, 4, 2, 1 };
enum { NUM_ALIGN = sizeof(align) / sizeof(align[0]) };
uint8_t stack[1024];
uint8_t *sp = stack + sizeof(stack);
int dec = 1;
int a_idx = 0;
printf("%s\n", tag);
while (sp > stack)
{
sp -= dec++;
uint8_t *sp_a = (*align_a)(sp, align[a_idx]);
uint8_t *sp_b = (*align_b)(sp, align[a_idx]);
printf("old %p, adj %.2d, A %p, B %p\n",
(void *)sp, align[a_idx], (void *)sp_a, (void *)sp_b);
assert(sp_a == sp_b);
sp = sp_a;
a_idx = inc_mod(a_idx, NUM_ALIGN);
}
putchar('\n');
}
int main(void)
{
test_aligners("Align upwards", align_upwards_a, align_upwards_b);
test_aligners("Align downwards", align_downwards_a, align_downwards_b);
return 0;
}
Sample output (partially truncated):
Align upwards
old 0x7fff5ebcf4af, adj 64, A 0x7fff5ebcf4c0, B 0x7fff5ebcf4c0
old 0x7fff5ebcf4be, adj 32, A 0x7fff5ebcf4c0, B 0x7fff5ebcf4c0
old 0x7fff5ebcf4bd, adj 16, A 0x7fff5ebcf4c0, B 0x7fff5ebcf4c0
old 0x7fff5ebcf4bc, adj 08, A 0x7fff5ebcf4c0, B 0x7fff5ebcf4c0
old 0x7fff5ebcf4bb, adj 04, A 0x7fff5ebcf4bc, B 0x7fff5ebcf4bc
old 0x7fff5ebcf4b6, adj 02, A 0x7fff5ebcf4b6, B 0x7fff5ebcf4b6
old 0x7fff5ebcf4af, adj 01, A 0x7fff5ebcf4af, B 0x7fff5ebcf4af
old 0x7fff5ebcf4a7, adj 64, A 0x7fff5ebcf4c0, B 0x7fff5ebcf4c0
old 0x7fff5ebcf4b7, adj 32, A 0x7fff5ebcf4c0, B 0x7fff5ebcf4c0
old 0x7fff5ebcf4b6, adj 16, A 0x7fff5ebcf4c0, B 0x7fff5ebcf4c0
old 0x7fff5ebcf4b5, adj 08, A 0x7fff5ebcf4b8, B 0x7fff5ebcf4b8
old 0x7fff5ebcf4ac, adj 04, A 0x7fff5ebcf4ac, B 0x7fff5ebcf4ac
old 0x7fff5ebcf49f, adj 02, A 0x7fff5ebcf4a0, B 0x7fff5ebcf4a0
old 0x7fff5ebcf492, adj 01, A 0x7fff5ebcf492, B 0x7fff5ebcf492
…
old 0x7fff5ebcf0fb, adj 08, A 0x7fff5ebcf100, B 0x7fff5ebcf100
old 0x7fff5ebcf0ca, adj 04, A 0x7fff5ebcf0cc, B 0x7fff5ebcf0cc
old 0x7fff5ebcf095, adj 02, A 0x7fff5ebcf096, B 0x7fff5ebcf096
Align downwards
old 0x7fff5ebcf4af, adj 64, A 0x7fff5ebcf480, B 0x7fff5ebcf480
old 0x7fff5ebcf47e, adj 32, A 0x7fff5ebcf460, B 0x7fff5ebcf460
old 0x7fff5ebcf45d, adj 16, A 0x7fff5ebcf450, B 0x7fff5ebcf450
old 0x7fff5ebcf44c, adj 08, A 0x7fff5ebcf448, B 0x7fff5ebcf448
old 0x7fff5ebcf443, adj 04, A 0x7fff5ebcf440, B 0x7fff5ebcf440
old 0x7fff5ebcf43a, adj 02, A 0x7fff5ebcf43a, B 0x7fff5ebcf43a
old 0x7fff5ebcf433, adj 01, A 0x7fff5ebcf433, B 0x7fff5ebcf433
old 0x7fff5ebcf42b, adj 64, A 0x7fff5ebcf400, B 0x7fff5ebcf400
old 0x7fff5ebcf3f7, adj 32, A 0x7fff5ebcf3e0, B 0x7fff5ebcf3e0
old 0x7fff5ebcf3d6, adj 16, A 0x7fff5ebcf3d0, B 0x7fff5ebcf3d0
old 0x7fff5ebcf3c5, adj 08, A 0x7fff5ebcf3c0, B 0x7fff5ebcf3c0
old 0x7fff5ebcf3b4, adj 04, A 0x7fff5ebcf3b4, B 0x7fff5ebcf3b4
old 0x7fff5ebcf3a7, adj 02, A 0x7fff5ebcf3a6, B 0x7fff5ebcf3a6
old 0x7fff5ebcf398, adj 01, A 0x7fff5ebcf398, B 0x7fff5ebcf398
…
old 0x7fff5ebcf0f7, adj 01, A 0x7fff5ebcf0f7, B 0x7fff5ebcf0f7
old 0x7fff5ebcf0d3, adj 64, A 0x7fff5ebcf0c0, B 0x7fff5ebcf0c0
old 0x7fff5ebcf09b, adj 32, A 0x7fff5ebcf080, B 0x7fff5ebcf080
Solution 2:
DO NOT USE MODULO!!! IT IS REALLY SLOW!!! Hands down the fastest way to align a pointer is to use 2's complement math. You need to invert the bits, add one, and mask off the 2 (for 32-bit) or 3 (for 64-bit) least significant bits. The result is an offset that you then add to the pointer value to align it. Works great for 32 and 64-bit numbers. For 16-bit alignment just mask the pointer with 0x1 and add that value. Algorithm works identically in any language but as you can see, Embedded C++ is vastly superior than C in every way shape and form.
#include <cstdint>
/** Returns the number to add to align the given pointer to a 8, 16, 32, or 64-bit
boundary.
@author Cale McCollough.
@param ptr The address to align.
@return The offset to add to the ptr to align it. */
template<typename T>
inline uintptr_t MemoryAlignOffset (const void* ptr) {
return ((~reinterpret_cast<uintptr_t> (ptr)) + 1) & (sizeof (T) - 1);
}
/** Word aligns the given byte pointer up in addresses.
@author Cale McCollough.
@param ptr Pointer to align.
@return Next word aligned up pointer. */
template<typename T>
inline T* MemoryAlign (T* ptr) {
uintptr_t offset = MemoryAlignOffset<uintptr_t> (ptr);
char* aligned_ptr = reinterpret_cast<char*> (ptr) + offset;
return reinterpret_cast<T*> (aligned_ptr);
}
For detailed write up and proofs please @see https://github.com/kabuki-starship/kabuki-toolkit/wiki/Fastest-Method-to-Align-Pointers. If you would like to see proof of why you should never use modulo, I invented the world fastest integer-to-string algorithm. The benchmark on the paper shows you the effect of optimizing away just one modulo instruction. Please @see https://github.com/kabuki-starship/kabuki-toolkit/wiki/Engineering-a-Faster-Integer-to-String-Algorithm.
Solution 3:
For some reason I can't use modulo or bitwise operations. In this case:
void *alignAddress = (void*)((((intptr_t)address + align - 1) / align) * align) ;
For C++:
template <int align, typename T>
constexpr T padding(T value)
{
return ((value + align - 1) / align) * align;
}
...
char* alignAddress = reinterpret_cast<char*>(padding<8>(reinterpret_cast<uintptr_t>(address)))
Solution 4:
I'm editing this answer because:
- I had a bug in my original code (I forgot a typecast to
intptr_t), and - I'm replying to Jonathan Leffler's criticism in order to clarify my intent.
The code below is not meant to imply you can change the value of an array (foo). But you can get an aligned pointer into that array, and this example illustrates one way to do it.
#define alignmentBytes ( 1 << 2 ) // == 4, but enforces the idea that that alignmentBytes should be a power of two
#define alignmentBytesMinusOne ( alignmentBytes - 1 )
uint8_t foo[ 1024 + alignmentBytesMinusOne ];
uint8_t *fooAligned;
fooAligned = (uint8_t *)((intptr_t)( foo + alignmentBytesMinusOne ) & ~alignmentBytesMinusOne);