Metaprogramming to optimize the storage / runtime algorithm, C ++

Question

I would like to generalize bitwise operators in C ++ without thinking that the underlying structure is an array.

As an instance ... if I want to represent 86 bits, I would use a structure / structure class, for example:

typedef struct { uint64_t x[1]; uint16_t y[1]; uint8_t z[1]; } sampleStruct; 

Instead, if I wanted to allocate 160 bits, I would use a structure such as:

 typedef struct { uint64_t x[2]; uint32_t y[1]; } sampleStruct; 

I think that a trivial but not optimal storage solution would be to assume that all the pieces are homogeneous and give off a minimum of those st it covers the size that I realize, however, even with regard to exercises, I prefer the way I showed.

It seems to me that I should use metaprogramming to solve the problem, so I should correctly identify

 template <int I> typedef sampleStruct { //something } 

However, I am not a great expert in metaprogramming C ++ templates, so I would like to understand what would be the best way to implement a different type of struct var I. I know how to choose the best "cover" for my length would be something like this:

 N64 = I/64; RemN = I%64; if(0 < RemN <= 8) { add uint8_t var; } else if (8 < RemN <= 16) { add uint16_t var; } else if (16 < RemN <= 24) { add uint16_t var; add uint8_t var; } else { //Similarly handle the other cases from 24 < RemN < 64 } 

What can I do to achieve what I want to do?

I also assume that the correct arrays will achieve slightly better performance compared to another possible implementation.

Hoping this is clear enough ... (Assume C ++ 11 or later).

Answer 1

It is possible, but quite a lot of typing text is present there. The problem is that C ++ does not provide a way of metaprogramming to omit a data element (see, for example, Conditional inclusion / exclusion of data members inside class templates ), so you have to specialize in its presence or absence:

 template<int N64, bool P32, bool P16, bool P8> struct sampleStructImpl; template<int I> using sampleStruct = sampleStructImpl<I/64, (I%64 >= 32), (I%32 >= 16), (I%16 >= 8)>; 

Various partial specializations (total 8) are as follows:

 template<int N64> struct sampleStructImpl<N64, true, true, true> { std::uint64_t x[N64]; std::uint32_t y; std::uint16_t z; std::uint8_t w; }; template<int N64> struct sampleStructImpl<N64, true, true, false> { std::uint64_t x[N64]; std::uint32_t y; std::uint16_t z; // omit std::uint8_t w; }; // 6 more partial specializations... 

Also, since zero-length arrays are illegal, if you want I values ​​to be less than 64, you will need to point N64 to zero:

 template<> struct sampleStructImpl<0, true, true, true> { // omit std::uint64_t x[0]; std::uint32_t y; std::uint16_t z; std::uint8_t w; }; // 7 more specializations... 

It would be much easier to use std::array<std::uint8_t, (I + 7) / 8> , possibly with the alignas modifier alignas to 64-bit alignment.

Answer 2

Wouldn't it be simpler to use only the uint8_t array, for example:

 template <int I> struct sampleStruct { std::uint8_t v[(I % 8)? (I / 8) + 1 : (I / 8)]; }; 

As you mentioned the bits, I assume that you are not accessing the individual members x,y,z (it is not clear how you will gain access to the base bits.)

It is possible to do what you want, but you should use inheritance as follows:

 template <int I> struct largeBlock { std::uint64_t x[I]; }; template <> struct largeBlock<0> { }; template <int I> struct mediumBlock { std::uint16_t y[I]; }; template <> struct mediumBlock<0> { }; template <int I> struct smallBlock { std::uint8_t z[(I / 8) + ((I % 8) ? 1 : 0) ]; }; template <> struct smallBlock<0> { }; template <int I> struct sampleStruct : largeBlock<I / 64>, mediumBlock<(I % 64) / 16>, smallBlock<(I % 16)> { }; 

Now your operations should be implemented in terms of calls to basic objects ...