CODEWITHSUNDEEP
c++algorithmalignment
Clayton Hughes
Clayton Hughes

Reputation: 1045

Algorithm for determining Alignment of elements in C/C++ structs

Okay, Allow me to re-ask the question, as none of the answers got at what I was really interested in (apologies if whole-scale editing of the question like this is a faux-paus).

A few points:

Let's make a function called pack, which takes as input an integer, called alignment, and a tuple of integers, called elements. It outputs another integer, called size.

The function works as follows:

int pack (int alignment, int[] elements)
{
  total_size = 0;

  foreach( element in elements )
  {
    while( total_size % min(alignment, element) != 0 ) { ++total_size; }
    total_size += element;
  }

  while( total_size % packing != 0 ) { ++total_size; }

  return total_size;
}

I think what I want to ask is "what is the inverse of this function?", but I'm not sure whether inversion is the correct term--I don't remember ever dealing with inversions of functions with multiple inputs, so I could just be using a term that doesn't apply.

Something like what I want (sort of) exists; here I provide pseudo code for a function we'll call determine_align. The function is a little naive, though, as it just calls pack over and over again with different inputs until it gets an answer it expects (or fails).

int determine_align(int total_size, int[] elements)
{
  for(packing = 1,2,4,...,64) // expected answers.
  {
    size_at_cur_packing = pack(packing, elements);

    if(actual_size == size_at_cur_packing)
    {
      return packing;
    }
  }

  return unknown;
}

So the question is, is there a better implementation of determine_align?

Thanks,

Upvotes: 0

Views: 2326

Answers (7)

Christian Lindig
Christian Lindig

Reputation: 1246

I'm not sure what you want to achieve here. As Pavel Minaev said, alignment is handled by a compiler which in turn is constrained by a platform's Application Binary Interface for data that is made accessible to code compiled by a different compiler. The following paper discusses the problem in the context of a compiler that needs to implement calling conventions:

Christian Lindig and Norman Ramsey. Declarative Composition of Stack Frames. In Evelyn Duesterwald, editors, Proc. of the 14th International Conference on Compiler Construction, Springer, LNCS 2985, 2004.

Upvotes: 0

Michael Burr
Michael Burr

Reputation: 340496

I'm honestly not sure what you're trying to do, and I'm probably completely misunderstanding what you're looking for, but if you want to simply determine what the alignment requirement of a struct is, the following macro might be helpful:

#define ALIGNMENT_OF( t ) offsetof( struct { char x; t test; }, test )

To determine the alignment of your foo structure, you can do:

ALIGNMENT_OF( foo);

If this isn't what you're ultimately tring to do, it might be possible that the macro might help in whatever algorithm you do come up with.

Upvotes: 2

Steve K
Steve K

Reputation: 2202

If the problem is just that you want to guarantee a particular alignment, that is easy. For a particular alignment=2^n:

void* p = malloc( sizeof( _foo ) + alignment -1 );
p = (void*) ( ( (char*)(p) + alignment - 1 ) & ~alignment );

I've neglected to save to original p returned from malloc. If you intend to free this memory, you need to save that pointer somewhere.

Upvotes: 0

CB Bailey
CB Bailey

Reputation: 793199

When choosing how to pack members into a struct an implementation doesn't have to follow the sort of scheme that you describe in your algorithm although it is a common one. (i.e. minimum of sizeof type being aligned and preferred machine alignment size.)

You don't have to compare overall size of a struct to determine the padding that has been applied to individual struct members, though. The standard macro offsetof will give the byte offset from the start of the struct of any individual struct member.

Upvotes: 5

HowdyHowdyHowdy
HowdyHowdyHowdy

Reputation: 1211

I let the compiler do the alignment for me.

In gcc, 

typedef struct _foo
{
    u8 v1  __attribute__((aligned(4)));
    u16 v2 __attribute__((aligned(4)));
    u32 v3 __attribute__((aligned(8)));
    u8 v1  __attribute__((aligned(4)));
} foo;

Edit: Note that sizeof(foo) will return the correct value including any padding.

Edit2: And offsetof(foo, v2) also works. Given these two functions/macros, you can figure out everything you need to know about the layout of the struct in memory.

Upvotes: 3

Pavel Minaev
Pavel Minaev

Reputation: 101655

Alignment of struct members in C/C++ is entirely implementation-defined. There are a few guarantees there, but I don't see how they would help you.

Thus, there's no generic way to do what you want. In the context of a particular implementation, you should refer to the documentation of that implementation that covers this (if it is covered).

Upvotes: 7

MSN
MSN

Reputation: 54634

You need to pad based on the alignment of the next field and then pad the last element based on the maximum alignment you've seen in the struct. Note that the actual alignment of a field is the minimum of its natural alignment and the packing for that struct. I.e., if you have a struct packed at 4 bytes, a double will be aligned to 4 bytes, even though its natural alignment is 8.

You can make your inner loop faster with total_size+= total_size % min(packing, element.size); You can optimize it further if packing and element.size is a power of two.

Upvotes: 0

Related Questions