Data Structure Alignment

CDataAlignment.java

public class CDataAlignment {
  public static void main(String[] args) throws java.lang.Exception {
    System.out.println(Struct.aligned(1, 1));
    structCharShortDoubleIntTest(1, false);
    structCharShortDoubleIntTest(2, false);
    structCharShortDoubleIntTest(4, false);
    structCharShortDoubleIntTest(8, false);
    structCharShortDoubleIntTest(16, false);
    structCharShortDoubleIntTest(32, false);

    structCharShortDoubleIntTest(1, true);
    structCharShortDoubleIntTest(2, true);
    structCharShortDoubleIntTest(4, true);
    structCharShortDoubleIntTest(8, true);
    structCharShortDoubleIntTest(16, true);
    structCharShortDoubleIntTest(32, true);
  }

  /**
   * <pre>
   *   struct struct_tag {
   *     char char_v;
   *     short short_v __attribute__((aligned(fieldAligment)));
   *     double double_v;
   *     int int_v;
   *   }__attribute__((aligned(structAligment)));
   * </pre>
   */
  static void structCharShortDoubleIntTest(int aligned, boolean packed) {
    Struct st = new Struct(aligned, packed);
    System.out.println("struct st_" + aligned + (packed ? "_packed" : "") + "{");
    System.out.println("  char@" + st.addField(CType.CHAR));
    System.out.println("  short@" + st.addField(CType.SHORT));
    System.out.println("  double@" + st.addField(CType.DOUBLE));
    System.out.println("  int@" + st.addField(CType.INT));
    st.build();
    System.out.println("} // size=" + st.size() + ", alignment=" + st.alignment());
  }

  static void nestedStructTest() {

  }

  public static final boolean isPowerOfTwo(int x) {
    return (x != 0) && 0 == (x & (x - 1));
  }

  public static interface IType {
    public int size();

    public int alignment();
  }

  public static interface IStruct extends IType {

  }

  public static class ArrayType implements IType {
    private final IType componentType;
    private final int size;

    public ArrayType(IType componentType, int count) {
      this.componentType = componentType;
      this.size = componentType.alignment() * count;
    }

    @Override
    public int size() {
      return size;
    }

    @Override
    public int alignment() {
      return componentType.alignment();
    }
  }

  /**
   * <h2>Structure Member Alignment, Padding and Data Packing</h2> <br>
   * A memory address a, is said to be n-byte aligned when a is a multiple of n bytes (where n is a
   * power of 2).
   * 
   * <h3>Alignment requirements</h3><br>
   * Every data type in C/C++ will have alignment requirement (in fact it is mandated by processor
   * architecture, not by language). A processor will have processing word length as that of data
   * bus size. On a 32 bit machine, the processing word size will be 4 bytes. <br>
   * typical 32 bit machine:
   * 
   * <pre>
   * char         1 byte
   * short int    2 bytes
   * int          4 bytes
   * double       8 bytes
   * </pre>
   * 
   * <h3>Computing padding</h3> The following formulas provide the number of padding bytes required
   * to align the start of a data structure (where mod is the modulo operator):
   * 
   * <pre>
   * # pseudo-code, see actual code below
   * padding = (align - (offset mod align)) mod align
   * new offset = offset + padding = offset + (align - (offset mod align)) mod align
   * </pre>
   * 
   * For example, the padding to add to offset 0x59d for a structure aligned to every 4 bytes is 3.
   * The structure will then start at 0x5a0, which is a multiple of 4. Note that when offset already
   * is a multiple of align, the second modulo in (align - (offset mod align)) mod align is required
   * to get a padding of 0.
   * <p/>
   * Since the alignment is by definition a power of two, the modulo operation can be reduced to a
   * bitwise boolean AND operation. The following formulas provide the new offset (where & is a
   * bitwise AND and ~ a bitwise NOT):
   * 
   * <pre>
   * padding = align - (offset & (align - 1)) = (-offset) & (align - 1)
   * new offset = (offset + align - 1) & ~(align - 1)
   * </pre>
   * 
   * <h3>Why In short</h3>
   * <p/>
   * Structure padding is done by the compilers and this depends on the architectures. Some
   * architectures cannot access the data which will be stored on the odd addresses or they may find
   * difficult to access it. This is the reason for padding extra bytes.
   * <p/>
   * Padding will be done by compiler to structure��s members and to the structure as a whole also.
   * Compiler pads structure as whole because this allows each member of structure aligned in array
   * of structures
   * 
   * @see <a href="https://en.wikipedia.org/wiki/Data_structure_alignment">Wikipedia Data structure
   *      alignment</a>
   * @see <a href="http://www.writeulearn.com/structure-padding">structure padding</a>
   */
  public static class Struct implements IStruct {
    private static int DEFAULT_ALIGNMENT = 4;
    private static final boolean DEFAULT_PACKED = false;

    private int sizeInBytes;
    private int alignment;
    /**
     * byte boundary to enforce a structure to be aligned to when packed, which impacts inserted
     * padding bytes following the member so that the next member is aligned to a optimized byte
     * boundary.
     * <p/>
     * Moreover, the whole structures should be padded so that the total structure size is a
     * multiple of the required Alignment specified by {@link #aligned}.
     */
    private final int aligned;
    /**
     * If true, arrange memory for structure members very next to the end of other structure
     * members, while just pad the last structure member. If false,
     */
    private final boolean packed;

    public Struct() {
      this(DEFAULT_ALIGNMENT, DEFAULT_PACKED);
    }

    public Struct(boolean packed) {
      this(DEFAULT_ALIGNMENT, packed);
    }

    public Struct(int aligned) {
      this(aligned, DEFAULT_PACKED);
    }

    public Struct(int aligned, boolean packed) {
      this.aligned = aligned;
      this.packed = packed;
    }

    private int addField(int fieldSize, int fieldAligment) {
      int offset;
      if (packed) {
        offset = sizeInBytes;
      } else {
        offset = aligned(sizeInBytes, fieldAligment);
        if (alignment < fieldAligment) {
          alignment = fieldAligment;
        }
      }
      sizeInBytes = offset + fieldSize;
      return offset;
    }

    public int addField(IType type) {
      return addField(type.size(), type.alignment());
    }

    /**
     * Coerce the calculation into not using the normal alignment of the input type, a pragma like
     * #pragma pack of MS-compiler, attribute packed and aligned of GCC and clang.
     * 
     * <pre>
     *   #pragma pack(push)  // push current alignment to stack
     *   #pragma pack(1)     // set alignment to 1 byte boundary   
     *   struct struct_tag {
     *     char char_v;
     *     short short_v;
     *     double double_v;
     *     int int_v;
     *   };
     *   #pragma pack(pop)   // restore original alignment from stack
     * </pre>
     * 
     * or
     * 
     * <pre>
     *   #pragma pack(push)  // push current alignment to stack
     *    #pragma pack(1)     //set alignment to 1 byte boundary   
     *   struct struct_tag {
     *     char char_v;
     *     short short_v __attribute__((aligned(fieldAligment)));
     *     double double_v;
     *     int int_v;
     *   }__attribute__((aligned(structAligment)));
     * </pre>
     * 
     * Do not do this casually, as it forces the generation of more expensive and slower code.
     * Usually you can save as much memory, or almost as much, with the techniques I describe here.
     * 
     * @param type
     * @param enforcedAligment
     * @return
     * @see <a href="http://www.catb.org/esr/structure-packing/">The Lost Art of C Structure
     *      Packing</a>
     */
    public int addField(IType type, int enforcedAligment) {
      int fieldAligment = type.alignment();
      if (enforcedAligment > fieldAligment) {
        fieldAligment = enforcedAligment; // required
      }
      return addField(type.size(), fieldAligment);
    }

    /** entire structure alignment */
    public Struct build() {
      if (aligned > alignment) {
        alignment = aligned; // required
      }
      sizeInBytes = aligned(sizeInBytes, alignment);
      return this;
    }

    public int aligned() {
      return aligned;
    }

    public boolean isPacked() {
      return packed;
    }

    @Override
    public int size() {
      return sizeInBytes;
    }

    @Override
    public int alignment() {
      return alignment;
    }

    @Override
    public String toString() {
      return "Struct [size=" + sizeInBytes + ", alignment=" + alignment + "]";
    }


    public static final int aligned(int offsetInBytes, int alignInBytes) {
      return (offsetInBytes + alignInBytes - 1) & ~(alignInBytes - 1);
    }

    public static final int padding(int offsetInBytes, int alignInBytes) {
      return (-offsetInBytes) & (alignInBytes - 1);
    }

  }

  /**
   * some types depend on the processor architectures
   */
  public enum CType implements IType {
    CHAR(1, 1), WHCAR(2, 2), SHORT(2, 2), INT(4, 4), LONG(4, 4), LONG_INT(4, 4), LONG_LONG(8, 4), FLOAT(
        4, 4), DOUBLE(8, 8);
    private CType(int size, int aligment) {
      this.size = size;
      this.aligment = aligment;
    }

    @Override
    public int size() {
      return size;
    }

    @Override
    public int alignment() {
      return aligment;
    }

    private final int size;
    private final int aligment;
  }
}

CDataStructureAlignment.cpp

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#if defined(_MSC_VER)
// At least until I upgrace to 2013-era MSVS
typedef int bool; /* typedef enum { false = 0, true = !false } bool; */
#define true 1
#define false 0
#else
/* bool as a macro to  a builtin _Bool data type in C99, but not in C89/90 */
#include <stdbool.h>
#endif

/* @see https://e...content-available-to-author-only...a.org/wiki/Offsetof */
#ifndef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
#endif

/*
 void f(int _UNUSED(argc), char *argv[], char *env[]) {
 UNUSED(argv) UNUSED(env);
 //...
 }
 http://stackoverflow.com/questions/3599160/unused-parameter-warnings-in-c-code
 */
//#if !defined(UNUSED)
#if defined(__GNUC__)
#define _UNUSED(x) x __attribute__((unused))
#elif defined(__LCLINT__)
#define _UNUSED(x) /*@unused@*/ x
#endif
#define UNUSED(x) (void)(x)  /* This works on any compiler*/
//#endif /* !defined(UNUSED) */

#define ALIGNMENT 64

// Alignment requirements
// (typical 32 bit machine)

// char         1 byte
// short int    2 bytes
// int          4 bytes
// double       8 bytes

// structure A
typedef struct structa_tag {
  char c;
  short int s;
} structa_t;

// structure B
typedef struct structb_tag {
  short int s;
  char c;
  int i;
} structb_t;

struct structc_tag {
  char c;
  double d;
  int s;
}__attribute__((aligned(ALIGNMENT)));
//__attribute__((aligned(ALIGNMENT), packed));

// structure C
typedef struct structc_tag structc_t;

// structure D
typedef struct structd_tag {
  double d;
  int s;
  char c;
} structd_t;

typedef struct type_tag type_t;
struct type_tag {
  const char *name;
  const char *ctypename;

  unsigned int aligned; /* __attribute__((aligned(xx))) ; */
  bool packed; /* __attribute__((packed)) ; */

  unsigned int size; /* sizeof */
  unsigned int alignment; /* alignof */
  unsigned int offset; /* offsetof */
  struct type_tag **elements;
};

class IType {
 public:
  virtual unsigned int size() const = 0;
  virtual unsigned int alignment() const = 0;
};

#define DEF_C_TYPE(NAME, TYPE) class C##NANE : public IType{\
public: \
    virtual unsigned int size() const{\
        return sizeof(TYPE);\
    }\
    virtual unsigned int alignment() const{\
        return alignof(TYPE);\
    }\
    const char* name() const{\
        return #TYPE;\
    }\
}

DEF_C_TYPE(CHAR, char);
//DEF_C_TYPE(INT, int);
//DEF_C_TYPE(LONG, long);

//enum
class CType : public IType {
 private:
  const unsigned int sizeInBytes;
  const unsigned int aligmentInBytes;
  const char* zname;

 public:
  CType(unsigned int size, unsigned int alignment, const char* name)
      : sizeInBytes(size),
        aligmentInBytes(alignment),
        zname(name) {
  }

  virtual unsigned int size() const {
    return sizeInBytes;
  }

  virtual unsigned int alignment() const {
    return aligmentInBytes;
  }

  const char* name() const {
    return zname;
  }
};

class CsaType: public IType{
 protected:
 int sizeInBytes;
 public:
 CsaType(){
	sizeInBytes = 0;
 }
  virtual unsigned int size() const {
    return sizeInBytes;
  }

  virtual unsigned int alignment() const {
    return sizeInBytes;
  }
};

class CArrayType : public CsaType {
 private:
  const IType* componentType;

 public:
  CArrayType(IType *elementType, unsigned int count){
	  componentType = elementType;
	  sizeInBytes= elementType->alignment() * count;
  }
};

class CUnionType : public CsaType {
 private:
  unsigned int aligmentInBytes;

 public:
  CUnionType(){
	aligmentInBytes = 0;
  }

  virtual unsigned int alignment() const {
    return aligmentInBytes;
  }
};

/*
 alignof operator (since C++11)
 https://e...content-available-to-author-only...a.org/wiki/C_data_types#Basic_types
 http://e...content-available-to-author-only...e.com/w/cpp/language/alignof
 */
#define DEF_C_TYPE_VAR(NAME, TYPE) CType C_##NAME(sizeof(TYPE), alignof(TYPE), #TYPE)

DEF_C_TYPE_VAR(CHAR, char);
DEF_C_TYPE_VAR(WCHAR, wchar_t);
DEF_C_TYPE_VAR(SHORT, short);
DEF_C_TYPE_VAR(INT, int);
DEF_C_TYPE_VAR(LONG, long);
DEF_C_TYPE_VAR(LONG_LONG, long long);
DEF_C_TYPE_VAR(FLOAT, float);
DEF_C_TYPE_VAR(DOUBLE, double);
DEF_C_TYPE_VAR(LONG_DOUBLE, long double);
DEF_C_TYPE_VAR(VOIDP, void*);

/*
 http://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2
 http://g...content-available-to-author-only...d.edu/~seander/bithacks.html#DetermineIfPowerOf2
 http://w...content-available-to-author-only...y.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/

 Running Time to Check All 232 Integers(What's the pc configure)
 Complement and Compare  6 minutes, 43 seconds
 Decrement and Compare 6 minutes, 51 seconds

 */

static inline bool isPowerOfTwo(unsigned int x) {
  return ((x != 0) && !(x & (x - 1)));
}

/**
https://e...content-available-to-author-only...a.org/wiki/Data_structure_alignment
# pseudo-code, see actual code below
padding = (align - (offset mod align)) mod align
new offset = offset + padding = offset + (align - (offset mod align)) mod align

 */
class Struct : public IType {
 private:
  unsigned int sizeInBytes = 0;
  /**A power of 2, user recommanded*/
  unsigned int _aligned = 0;
  /** = packed ? _aligned : max(_aligned, the one of structure member with a maximum alignment)*/
  unsigned int alignmentInBytes = 0;
  /**
  If true, arrange memory for structure members very next to the end of other structure members, while just pad the last structure member.
  If false, 
  */
  const bool packed;
 private:
  int addField(const unsigned int fieldSize, const unsigned int fieldAligment) {
    int offset;
    if (packed) {
      offset = sizeInBytes;
    } else {
      offset = alignedOffset(sizeInBytes, fieldAligment);
      if (alignmentInBytes < fieldAligment) {
        alignmentInBytes = fieldAligment;
      }
    }

    printf("currentStructSize=%u, addedfield(aligment=%u, size=%u)"
           ", alignedOffset=%d\n",
           sizeInBytes, fieldAligment, fieldSize, offset);

    sizeInBytes = offset + fieldSize;

    return offset;
  }
 public:
  Struct(bool alignPacked = false)
      : packed(alignPacked) {
    _aligned = 4;
  }

  Struct(unsigned int aligned, bool alignPacked = false)
      : packed(alignPacked) {
    assert(isPowerOfTwo(aligned)); /* check if alignment is a power of 2 bytes*/
    _aligned = aligned;
  }

  int addField(IType &type) {
    return addField(type.size(), type.alignment());
  }

  int addField(IType &type, const unsigned int enforcedAligment) {
    unsigned int fieldAligment = type.alignment();
    if (enforcedAligment > fieldAligment) {
      fieldAligment = enforcedAligment;  //required
    }
    return addField(type.size(), fieldAligment);
  }

  /** entire structure alignment */
  const Struct& build() {

    if (_aligned > alignmentInBytes) {
      alignmentInBytes = _aligned;  //required
    }
    sizeInBytes = alignedOffset(sizeInBytes, alignmentInBytes);
    return *this;
  }

  virtual unsigned int size() const {
    return sizeInBytes;
  }

  virtual unsigned int alignment() const {
    return alignmentInBytes;
  }

  unsigned int aligned() const {
    return _aligned;
  }

  bool isPacked() const {
    return packed;
  }

  static int alignedOffset(const int offsetInBytes,
                           const unsigned int alignInBytes) {
    return (offsetInBytes + alignInBytes - 1) & ~(alignInBytes - 1);
  }
  static unsigned int padding(const int offsetInBytes, const int alignInBytes) {
    return (-offsetInBytes) & (alignInBytes - 1);
  }
};

void printCType(CType &ctype) {
  printf("size = %2d, alignment = %2d, of %s\n", ctype.size(),
         ctype.alignment(), ctype.name());
}

void printAlignedInfo(const unsigned int st_aligned) {
  printf("=========================\n");
  Struct st(st_aligned, true);
  printf("%s %d\n", C_CHAR.name(), st.addField(C_CHAR));
  printf("%s %d\n", C_SHORT.name(), st.addField(C_SHORT));
  printf("%s %d\n", C_DOUBLE.name(), st.addField(C_DOUBLE));
  printf("%s %d\n", C_INT.name(), st.addField(C_INT));
  st.build();
  printf("st(aligned=%ld) size=%ld, aligment=%ld\n", st_aligned, st.size(),
         st.alignment());
}

void printAlignedOffsetTest(const int offsetInBytes,
                            const unsigned int alignInBytes) {
  printf("alignedOffset(%d, %u)=%u\n", offsetInBytes, alignInBytes,
         Struct::alignedOffset(offsetInBytes, alignInBytes));
}

int main(int _UNUSED(argc), char *argv[], char *env[]) {
  UNUSED(argv);
  UNUSED(env);

  printCType(C_CHAR);
  printCType(C_WCHAR);
  printCType(C_SHORT);
  printCType(C_INT);
  printCType(C_LONG);
  printCType(C_LONG_LONG);
  printCType(C_FLOAT);
  printCType(C_DOUBLE);
  printCType(C_LONG_DOUBLE);
  printCType(C_VOIDP);

  // printf("sizeof(structa_t) = %u\n", offsetof(structa_t, a));

  printf("sizeof(structa_t) = %ld\n", sizeof(structa_t));
  printf("sizeof(structb_t) = %ld\n", sizeof(structb_t));
  printf("sizeof(structc_t) = %ld\n", sizeof(structc_t));
  printf("sizeof(structd_t) = %ld\n", sizeof(structd_t));

  printf("%u-aligned struct size=%ld, layout: char@%ld, double@%ld, int@%ld\n",
  ALIGNMENT,
         sizeof(structc_t), offsetof(structc_t, c), offsetof(structc_t, d),
         offsetof(structc_t, s));
  /*
   // processor architecture
   sizeof(structa_t) = 4
   sizeof(structb_t) = 8
   sizeof(structc_t) = 24
   sizeof(structd_t) = 16
   */

   // https://c...content-available-to-author-only...t.co/2014/11/25/variadic-macros-tricks/
  //__attribute__((aligned(ALIGNMENT), packed));
#define DEF_STRUCT_TO_PRINT(ST_NAME, ALIGN, T1, N1, T2, N2, T3, N3, T4, N4) struct ST_NAME{ \
  T1 N1; \
  T2 N2; \
  T3 N3; \
  T4 N4; \
}__attribute__((aligned(ALIGN), packed)) ; \
type_t ST_NAME##_elements[] = {\
  {#N1, #T1, 0, false, sizeof(T1), alignof(T1), offsetof(struct ST_NAME, N1), NULL}\
  ,{#N2, #T2, 0, false, sizeof(T2), alignof(T2), offsetof(struct ST_NAME, N2), NULL}\
  ,{#N1, #T3, 0, false, sizeof(T3), alignof(T3), offsetof(struct ST_NAME, N3), NULL}\
  ,{#N1, #T4, 0, false, sizeof(T4), alignof(T4), offsetof(struct ST_NAME, N4), NULL}\
};\
type_t *pp##ST_NAME##_elements[5] = {\
    ST_NAME##_elements\
  ,ST_NAME##_elements + 1\
  ,ST_NAME##_elements + 2\
  ,ST_NAME##_elements + 3\
  ,NULL\
};\
type_t st_##ST_NAME = {#ST_NAME, #ST_NAME, ALIGN, false, sizeof(struct ST_NAME), alignof(struct ST_NAME), 0, pp##ST_NAME##_elements};\
printf("%u-aligned struct sizeof=%ld, alignof=%ld, layout: "#T1"@%ld, "#T2"@%ld, "#T3"@%ld, "#T4"@%ld\n", \
ALIGN, sizeof(struct ST_NAME), alignof(struct ST_NAME), \
offsetof(struct ST_NAME, N1), offsetof(struct ST_NAME, N2), \
offsetof(struct ST_NAME, N3), offsetof(struct ST_NAME, N4))

#define DEF_STRUCT_TO_PRINT2(ST_NAME, ALIGN)  DEF_STRUCT_TO_PRINT(ST_NAME, ALIGN,\
char, char_v, short, short_v, double, double_v, int, int_v)

  //DEF_STRUCT_TO_PRINT2(st0, 0); //error: requested alignment is not a positive power of 2
  DEF_STRUCT_TO_PRINT2(st1, 1);
  DEF_STRUCT_TO_PRINT2(st2, 2);
  DEF_STRUCT_TO_PRINT2(st4, 4);
  DEF_STRUCT_TO_PRINT2(st8, 8);
  DEF_STRUCT_TO_PRINT2(st16, 16);
  DEF_STRUCT_TO_PRINT2(st32, 32);

  printf("enforce the second field to be aligned to 4 bytes boundary\n");
#define ST_ALIGNMENT 2
  struct st_tag {
    char char_v;
    short short_v __attribute__((aligned(1)));
    double double_v;
    int int_v;
  }__attribute__((aligned(ST_ALIGNMENT)));
  printf(
      "%u-aligned struct size=%ld, layout: char@%ld, short@%ld, double@%ld, int@%ld\n",
      ST_ALIGNMENT,
      sizeof(struct st_tag), offsetof(struct st_tag, char_v),
      offsetof(struct st_tag, short_v), offsetof(struct st_tag, double_v),
      offsetof(struct st_tag, int_v));

  printAlignedInfo(1);
  printAlignedInfo(2);
  printAlignedInfo(4);
  printAlignedInfo(8);
  printAlignedInfo(16);
  printAlignedInfo(32);

  printAlignedOffsetTest(20, 16);
  printAlignedOffsetTest(15, 2);
  return 0;
}

/*
 //https://msdn.microsoft.com/zh-cn/library/45t0s5f4.aspx
 // Expression Value
 __alignof( char ) // = 1
 __alignof( short ) // = 2
 __alignof( int ) // = 4
 __alignof( __int64 ) // = 8
 __alignof( float ) // = 4
 __alignof( double )// = 8
 __alignof( char* ) // = 4

 typedef struct { int a; double b; } S; // __alignof(S) == 8
 typedef __declspec(align(32)) struct { int a; } S; //__alignof(S) = 32

 */

IType.java

package ss.jn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public interface IType {
	/**
	 * The size in bytes of this type.
	 * 
	 * @return An integer
	 */
	public int size();

	/**
	 * The native alignment of this type, in bytes
	 * 
	 * @return An integer
	 */
	public int alignment();

	/** real type */
	public IType type();

	public interface ICompositeType extends IType {

	}

	/**
	 * some types depend on the processor architectures
	 */
	public enum CType implements IType {
		CHAR(1, 1), WHCAR(4, 4), SHORT(2, 2), INT(4, 4), LONG(4, 4), LONG_INT(4, 4), LONG_LONG(8, 4), FLOAT(4, 4), DOUBLE(8, 8), LONG_DOUBLE(
				12, 4), VOID_PTR(4, 4), SIZE_T(4, 4), INT8(1), INT16(2), INT32(4), INT64(8);

		private CType(int size) {
			this.size = size;
			this.aligment = size;
		}

		private CType(int size, int aligment) {
			// Jn.types[ordinal()];
			this.size = size;
			this.aligment = aligment;
		}

		@Override
		public int size() {
			return size;
		}

		@Override
		public int alignment() {
			return aligment;
		}

		@Override
		public CType type() {
			return this;
		}

		@Override
		public String toString() {
			return name() + "{" + size() + "/" + alignment() + "}";
		}

		public ArrayType arrayType(int count) {
			return new ArrayType(this, count);
		}

		private final int size;
		private final int aligment;
	}

	public static class ArrayType extends WrappedType implements ICompositeType {
		protected final int size;

		public ArrayType(IType componentType, int count) {
			super(componentType);
			size = componentType.alignment() * count;
		}

		@Override
		public int size() {
			return size;
		}

		public int count() {
			return size / type.alignment();
		}

		@Override
		public String toString() {
			return type + "[" + size + "]";
		}
	}

	public static class StructType extends Type implements ICompositeType {
		/** Alignment rules depends on the processor architectures */
		protected static int DEFAULT_ALIGNMENT = 1;
		protected static final boolean DEFAULT_PACKED = false;

		protected final int alignment;

		public StructType(int size, int alignment) {
			super(size);
			this.alignment = alignment;
		}

		@Override
		public int alignment() {
			return alignment;
		}
	}

	public static class UnionType extends StructType implements ICompositeType {
		public UnionType(int size, int alignment) {
			super(size, alignment);
		}
	}

	static class Type implements IType {
		protected final int size;

		Type() {
			size = 0;
		}

		Type(int size) {
			this.size = size;
		}

		@Override
		public int size() {
			return size;
		}

		@Override
		public int alignment() {
			return size;
		}

		public int offset() {
			return 0;
		}

		public int id() {
			return 0;
		}

		@Override
		public IType type() {
			return this;
		}

		@Override
		public String toString() {
			IType type = type();
			return type.getClass().getSimpleName() + "{" + type.size() + "/" + type.alignment() + "}";
		}
	}

	static class WrappedType implements IType {
		protected final IType type;

		public WrappedType(IType type) {
			this.type = type;
		}

		@Override
		public int size() {
			return type.size();
		}

		@Override
		public int alignment() {
			return type.alignment();
		}

		@Override
		public IType type() {
			return type;
		}
	}

	/**
	 * StructType, ArrayType, CType
	 */
	static class TypeComponent extends WrappedType {
		protected final int offset;

		public TypeComponent(IType type, int offset) {
			super(type);
			this.offset = offset;
		}

		public int offset() {
			return offset;
		}

		@Override
		public IType type() {
			return type;
		}

		@Override
		public String toString() {
			return type.toString() + "@" + offset;
		}
	}

	public static class Struct extends StructType implements ICompositeType {
		protected final TypeComponent[] elements;

		public Struct(int size, int alignment, TypeComponent[] elements) {
			super(size, alignment);
			this.elements = elements;
		}

		/**
		 * Composite types: the number of array elements, the number of Union/Structure members
		 */
		public int count() {
			return elements.length;
		}

		@Override
		public String toString() {
			return super.toString() + ", elements=" + Arrays.toString(elements);
		}

		public static class StructTypeDefiner {
			private int size;
			private int alignment;
			/**
			 * byte boundary to enforce a structure to be aligned to when packed, which impacts inserted padding bytes following the
			 * member so that the next member is aligned to a optimized byte boundary.
			 * <p/>
			 * Moreover, the whole structures should be padded so that the total structure size is a multiple of the required
			 * Alignment specified by {@link #aligned}.
			 */
			private final int aligned;
			/**
			 * If true, arrange memory for structure members very next to the end of other structure members, while just pad the last
			 * structure member. If false,
			 */
			private final boolean packed;

			public StructTypeDefiner() {
				this(StructType.DEFAULT_ALIGNMENT, StructType.DEFAULT_PACKED);
			}

			public StructTypeDefiner(boolean packed) {
				this(StructType.DEFAULT_ALIGNMENT, packed);
			}

			public StructTypeDefiner(int aligned) {
				this(aligned, StructType.DEFAULT_PACKED);
			}

			public StructTypeDefiner(int aligned, boolean packed) {
				if (!isPowerOfTwo(aligned)) {
					throw new IllegalArgumentException("requested alignment is not a positive power of 2");
				}
				this.aligned = aligned;
				this.packed = packed;
			}

			protected int addField(int fieldSize, int fieldAligment) {
				int offset;
				if (packed) {
					offset = size;
				} else {
					offset = alignedOffset(size, fieldAligment);
					if (alignment < fieldAligment) {
						alignment = fieldAligment;
					}
				}
				size = offset + fieldSize;
				return offset;
			}

			public int addField(IType type) {
				return addField(type.size(), type.alignment());
			}

			/**
			 * Coerce the calculation into not using the normal alignment of the input type, a pragma like #pragma pack of
			 * MS-compiler, attribute packed and aligned of GCC and clang.
			 * 
			 * <pre>
			 *   #pragma pack(push)  // push current alignment to stack
			 *   #pragma pack(1)     // set alignment to 1 byte boundary   
			 *   struct struct_tag {
			 *     char char_v;
			 *     short short_v;
			 *     double double_v;
			 *     int int_v;
			 *   };
			 *   #pragma pack(pop)   // restore original alignment from stack
			 * </pre>
			 * 
			 * or
			 * 
			 * <pre>
			 *   #pragma pack(push)  // push current alignment to stack
			 *    #pragma pack(1)     //set alignment to 1 byte boundary   
			 *   struct struct_tag {
			 *     char char_v;
			 *     short short_v __attribute__((aligned(fieldAligment)));
			 *     double double_v;
			 *     int int_v;
			 *   }__attribute__((aligned(structAligment)));
			 * </pre>
			 * 
			 * Do not do this casually, as it forces the generation of more expensive and slower code. Usually you can save as much
			 * memory, or almost as much, with the techniques I describe here.
			 * 
			 * @param type
			 * @param enforcedAligment
			 * @return
			 * @see <a href="http://www.catb.org/esr/structure-packing/">The Lost Art of C Structure Packing</a>
			 */
			public int addField(IType type, int enforcedAligment) {
				int fieldAligment = type.alignment();
				if (enforcedAligment > fieldAligment) {
					fieldAligment = enforcedAligment; // required
				}
				return addField(type.size(), fieldAligment);
			}

			/** entire structure alignment */
			public StructType build() {
				if (aligned > alignment) {
					alignment = aligned; // required
				}
				size = alignedOffset(size, alignment);
				return new StructType(size, alignment);
			}

			public int aligned() {
				return aligned;
			}

			public boolean isPacked() {
				return packed;
			}

			public int size() {
				return size;
			}

			public int alignment() {
				return alignment;
			}
		}

		public static class StructBuilder extends StructTypeDefiner {
			List<TypeComponent> elements = new ArrayList<TypeComponent>();

			@Override
			public int addField(IType type) {
				int offset = super.addField(type);
				elements.add(new TypeComponent(type, offset));
				return offset;
			}

			@Override
			public int addField(IType type, int enforcedAligment) {
				int offset = super.addField(type, enforcedAligment);
				elements.add(new TypeComponent(type, offset));
				return offset;
			}

			@Override
			public Struct build() {
				StructType sttype = super.build();
				return new Struct(sttype.size, sttype.alignment, elements.toArray(new TypeComponent[elements.size()]));
			}
		}

		/**
		 * Check whether the input paramter x is a positive power of 2.
		 * 
		 * @param x
		 * @return true if x is a positive power of 2, otherwise false.
		 */
		public static final boolean isPowerOfTwo(int x) {
			return (x > 0) && 0 == (x & (x - 1));
		}

		public static final int alignedOffset(int offsetInBytes, int alignInBytes) {
			return (offsetInBytes + alignInBytes - 1) & ~(alignInBytes - 1);
		}

		public static final int padding(int offsetInBytes, int alignInBytes) {
			return (-offsetInBytes) & (alignInBytes - 1);
		}

		public static void main2(String[] args) {
			// struct Dirent {
			// /** ino_t d_ino; Inode number, uint64_t */
			// long d_ino;
			// /** off_t d_off; Not an offset; see below, int64_t */
			// long d_off;
			// /** Length of this record, unsigned short */
			// short d_reclen;
			// /** Type of file; not supported by all filesystem types , unsigned char */
			// char d_type;
			// /** char d_name[256]; Null-terminated filename */
			// String d_name;
			// }

			StructTypeDefiner st_dirent_def = new StructBuilder();
			int inoFieldOffset = st_dirent_def.addField(CType.INT64);
			int offFieldOffset = st_dirent_def.addField(CType.INT64);
			int reclenFieldOffset = st_dirent_def.addField(CType.SHORT);
			int typeFieldOffset = st_dirent_def.addField(CType.CHAR);
			int nameFieldOffset = st_dirent_def.addField(CType.CHAR.arrayType(256));// 19;

			System.out.println("ino@" + inoFieldOffset);
			System.out.println("off@" + offFieldOffset);
			System.out.println("reclen@" + reclenFieldOffset);
			System.out.println("type@" + typeFieldOffset);
			System.out.println("name@" + nameFieldOffset);
			StructType st_dirent = st_dirent_def.build();
			System.out.println(st_dirent);
		}
	}
}