Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I needed a variadic function to pack and unpack bits into integer types. This is my first attempt:

template<typename T>
constexpr T pack(bool b)
{
    return b;
}

template<typename T, typename... Types>
constexpr T pack(bool b, Types... args)
{
    return (b << sizeof...(Types)) | pack<T>(args...);
}

template<typename T, typename... Types>
void unpack(T packed, bool& b1)
{
    b1 = packed & 1;
}

template<typename T, typename... Types>
void unpack(T packed, bool& b1, Types&... args)
{
    b1 = packed & (1 << sizeof...(Types));
    unpack(packed, args...);
}

Usage example:

int main(void)
{
    std::cout << pack<int>(1, 0, 0, 1, 0, 1, 1, 0) << std::endl; // 150
    std::cout << pack<int>(1, 0, 1) << std::endl; // 5
    int val = pack<int>(1, 0, 1);
    bool b1, b2, b3;
    unpack(val, b1, b2, b3);
    std::cout << b1 << " " << b2 << " " << b3 << std::endl; // 1 0 1
}

Does this code contain any bugs, can it be improved, and are variadic templates used appropriately here (I still don't master their syntax)?

UPDATE: I removed the unnecessary template parameter in the two arguments unpack overload. I also tried to implement compile-time checks to prevent overflows:

template<typename T>
constexpr T pack(bool b)
{
    return b;
}

template<typename T, typename... Types>
constexpr T pack(bool b, Types... args)
{
    static_assert(std::is_integral<T>::value, "The pack type is not an integral type");
    static_assert(sizeof(T) * 8 >= 1 + sizeof...(Types), "The pack type is not large enough to store the bits you have passed");
    return (b << sizeof...(Types)) | pack<T>(args...);
}

template<typename T>
void unpack(T packed, bool& b)
{
    b = packed & 1;
}

template<typename T, typename... Types>
void unpack(T packed, bool& b, Types&... args)
{
    static_assert(std::is_integral<T>::value, "The pack type is not an integral type");
    static_assert(sizeof(T) * 8 >= 1 + sizeof...(Types), "The pack type is not large enough to provide the bits you have requested");
    b = packed & (1 << sizeof...(Types));
    unpack(packed, args...);
}
share|improve this question
    
Two minor things I see: 1.) Replace each std::endl with "\n" 2.) In C++, main() doesn't need a void parameter. –  Jamal Apr 4 at 17:50
    
OK, thanks. Anything about the core parts? –  gd1 Apr 4 at 17:52
    
Nothing that I can see. I'm not familiar with variadic templates. –  Jamal Apr 4 at 17:53
add comment

2 Answers 2

Missing overflow check

One serious flaw that I see in this code is that the user needs to determine the number of parameters to unpack. This is a no go for a function whose output depends on a runtime input. Even worse there is no check that would tell the user that the actual number overflows the number of bits given to be unpacked into.

One possible solution would be to return an std::vector<bool> to fit the whole number.

The other solution would be to retain the current interface but to introduce error notification (by exception or return code).

Unnecessary template parameter

Another thing regarding the unpack function: It seems that you don't need the Types parameter in the recursion end, so it becomes:

template<typename T>
void unpack(T packed, bool& b1)
{
    b1 = packed & 1;
}

Naming

The function parameter names could be better. I assume b1 is only appropriate in the top level call of the function. I cannot decide on a better name now, but it should indicate that it is the current bit. Likewise, args should be named remainingBits or something like this.

share|improve this answer
    
The unnecessary template parameter is a plain oversight. About the rest I will think about it - I will never use a vector, this is exactly the point of this exercise, but if there is a way to make things more robust without a vector, I'll pursue it. About the naming, I have often seen "head" and "tail" but I don't find them quite appropriate. –  gd1 Apr 4 at 18:00
    
If it is only for the sake of making it "static" then you could make the packed parameter a template parameter, thus removing the possibility of runtime values that forbid the use of the specific parameter list. –  Nobody Apr 4 at 18:04
    
The pack() function needs to be evaluable also at compile-time (provided the passed arguments are), and actually it should be now - I hope the compiler is able to understand it - so that you can even use it in a switch case. The unpack() function should accept whatever packed value at runtime. I will really think about this, but while I consider very valuable writing robust code, I think this is one of the cases in which the client should be really aware of what it's doing. The performance of this should be no worse than a handcrafted sequence of bitwise operations. –  gd1 Apr 4 at 18:09
    
It is hard to be aware of the value of runtime variables if you don't check them. And if you check them beforehand you might forget to update the check together with the function call. Best way is to let the function itself do the checking and report an error if there is one. I find it a fairly harsh decision to put the burden onto the user of this function. –  Nobody Apr 4 at 18:12
    
We have vector's operator[] that doesn't necessarily check the boundaries (and many implementations don't), and virtually any function in the C++ standard library is prone to undefined behavior. This thing should perform as fast as it can and I do not want to introduce any branching, not to mention dynamic memory allocation. (PS: I forgot... +1 for your excellent answer) –  gd1 Apr 4 at 18:17
show 15 more comments

I guess you are aware of std::bitset and you have your own reasons for doing this. Your pack seems fine, but unpack requires the user to set up a particular number of bool variables, which is not convenient. An alternative could be to use an std::array for the output:

template<size_t N>
using size = std::integral_constant<size_t, N>;

template<size_t N, typename T>
void unpack(size<N>, array<bool, N>& a, T) { }

template<size_t I, size_t N, typename T>
void unpack(size<I>, array<bool, N>& a, T packed)
{
    a[N-I-1] = (packed & (1 << I)) != 0;
    unpack(size<I+1>(), a, packed);
}

template<typename T>
std::array<bool, 8*sizeof(T)>
unpack(T packed)
{
    std::array<bool, 8*sizeof(T)> a = {};
    unpack(size<0>(), a, packed);
    return a;
}

which can be used like this

int val = pack<int>(1, 0, 1);
std::cout << unpack(val) << std::endl;
// prints 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

assuming a simple streaming operator

template<typename S, typename T, size_t N>
S& operator<<(S& s, const std::array<T, N>& a)
{
    for (auto i : a)
        s << i << " ";
    return s;
}

This way you know for sure there is no overflow in the output.

Now, std::vector is another alternative for output that may benefit from its compact std::vector<bool> specialization (and std::bitset of course). On the other hand, using std::array, one may obtain a really constexpr version of unpack, without recursion. pack may similarly be non-recursive, remaining constexpr. If you like this potential, I can elaborate.


Update: constexpr version

It turns out pack is quite tricky to make non-recursive and constexpr, but as promised, here is a non-recursive, constexpr version of unpack (complete, live example):

template <size_t... N>
struct sizes { using type = sizes <N...>; };

template<size_t N, size_t... I, typename T>
constexpr std::array<bool, N>
unpack(sizes<I...>, T packed)
{
    return std::array<bool, N>{{(packed & (1 << (N-I-1))) != 0 ...}};
}

template<size_t N, typename T>
constexpr std::array<bool, N>
unpack(T packed)
{
    return unpack<N>(typename Range<N>::type(), packed);
}

template<typename T, size_t N = 8*sizeof(T)>
constexpr std::array<bool, N>
unpack(T packed) { return unpack<N>(packed); }

where Range<N> contains sequence 0,...N-1 and is defined here. Now you can use it like this:

int val = pack<int>(1, 0, 1);

// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
std::cout << unpack(val) << std::endl;

// 0 0 0 0 0 1 0 1
std::cout << unpack<8>(val) << std::endl;

The first version returns the entire array needed to represent the precision of the given (integral) type. The second allows you to specify a shorter length for the array; the remaining (leftmost) bits are discarded.

share|improve this answer
    
Altough I am not the OP I would like to hear about the constexpr version of unpack :) –  Nobody Apr 4 at 18:43
    
Well obviously yes. –  gd1 Apr 4 at 18:44
    
Ok, I will be back as soon as possible... :-) –  iavr Apr 4 at 18:46
    
@gd1 Sorry, I forgot, it's just a shortcut. See edit for the definition. –  iavr Apr 4 at 18:49
    
@Nobody,gd1 Updated with constexpr unpack. –  iavr Apr 4 at 19:43
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.