Going long periods between blog posts has always been fairly par for the course for me, but this last break was pretty excessive even by my standards. Two years is really just too long! Of course, shortly after that last post I ended up getting a job at 343 Industries (which is, incidentally, amazing!) and I can’t really blog about what I do at work, which lead to said hiatus. What are you going to do? Go two years between blog posts, apparently.
Anyway, the last two years have predominantly been writing HLSL, and that’s been great and I love my job, but recently I’ve been starting to worry that my C++ is getting rusty. Can’t let that happen, how would I feel superior to other programmers if I’m not pro at C++? Right? Right! So, with Halo 5 shipped I’ve had a little more free time and a thought occurred to me that got me jump started back into writing some “real” code. It’s a little bit of utility around a bitfield class, and I think that it’s useful, but I also couldn’t find any real reference to anyone else having done it. That either means that I’m an absolute genius or there are very legitimate reasons why no one does what I’m about to show and I’m just not seeing them. Which feels pretty likely, but you tell me!
So, I started with a bitfield class that just used an unsigned int as storage and had pretty basic bit and bulk getters and setters. Nothing super fancy, but effective for what I was doing with it. The next logical step was to template the storage type, and that was easy, which gave me the following code.
template <typename t_field>
class Bitflag
{
public:
//Default Constructor
Bitflag() : m_flags(0) {}
//Initial Value Constructor
Bitflag(t_field pFlags) : m_flags(pFlags) {}
//Bit Get
bool Get(t_field pIndex) const {
return ((m_flags & pIndex) == 0) ? false : true;
}
//Bulk Get
t_field Get() const {
return m_flags;
}
//Bit Set
void Set(t_field pIndex, bool pState) {
// Optimized based on information found at
// https://graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching
// Safe to squelch this warning
#pragma warning(push)
#pragma warning(disable : 4804)
m_flags = (m_flags & ~pIndex) | (-pState & pIndex);
#pragma warning(pop)
}
//Bulk Set
void Set(t_field pFlags) {
m_flags = pFlags;
}
private:
t_field m_flags;
};
And for the purpose of what I’m actually blogging about, the Bitflag class never actually gets any fancier or more complicated. Instead, I looked at what I had, and I realized that rather than really using the flexibility of the templated type to optimize storage size for the class, I just got lazy and slapped every usage with unsigned int. Which just took me back to where I was before I even templated the class. The hell, right? This lead me to the question, “Could I write code that, given the size of the flag set I want to be able to store in a Bitflag, would always set the templated type to the smallest appropriate type?” And if the answer was yes, then it could serve a few purposes; actually optimize my storage size, automatically change if necessary as the size of the represented flag set changed, automatically change if necessary as I compiled on other platforms where storage sizes might be different. That sounded great, so I dove into it, and it turns out that the answer is indeed yes.
I’ll start with the code that I ended up writing, and then I’ll explain what it’s doing, why I had it do that, and where it might go next.
#define BITFLAG_SIZE(val) BitflagHelpers::bitflag_type_selector<val>::value_type
namespace BitflagHelpers
{
static const int g_bits_per_byte = 8;
static const int g_undefined_ushort = -1;
static const int g_undefined_uint = -2;
static const int g_undefined_ulong = -3;
static const int g_undefined_ulonglong = -4;
template <int t>
struct bitflag_type
{
typedef int type;
};
// Be careful with this case when it comes to serialization
template <>
struct bitflag_type<sizeof(unsigned char) * g_bits_per_byte>
{
typedef unsigned char type;
};
// We protect from doubled specialization in the case that a type is
// the same size as the previous type by setting that instantiation
// to a negative global value. Remove the warning for specing a
// signed value into an unsigned type. Do something better later?
#pragma warning(push)
#pragma warning(disable : 4309)
template <>
struct bitflag_type<(sizeof(unsigned short) != sizeof(unsigned char))
? (sizeof(unsigned short) * g_bits_per_byte) : (g_undefined_ushort)>
{
typedef unsigned short type;
};
template <>
struct bitflag_type<(sizeof(unsigned int) != sizeof(unsigned short))
? (sizeof(unsigned int) * g_bits_per_byte) : (g_undefined_uint)>
{
typedef unsigned int type;
};
template <>
struct bitflag_type<(sizeof(unsigned long) != sizeof(unsigned int))
? (sizeof(unsigned long) * g_bits_per_byte) : (g_undefined_ulong)>
{
typedef unsigned long type;
};
template <>
struct bitflag_type<(sizeof(unsigned long long) != sizeof(unsigned long))
? (sizeof(unsigned long long) * g_bits_per_byte) : (g_undefined_ulonglong)>
{
typedef unsigned long long type;
};
#pragma warning(pop)
template <int t>
struct bitflag_type_selector
{
typedef
typename std::conditional<(t <= sizeof(unsigned char) * g_bits_per_byte),
bitflag_type<sizeof(unsigned char) * g_bits_per_byte>::type,
typename std::conditional<(t <= sizeof(unsigned short) * g_bits_per_byte),
bitflag_type<sizeof(unsigned short) * g_bits_per_byte>::type,
typename std::conditional<(t <= sizeof(unsigned int) * g_bits_per_byte),
bitflag_type<sizeof(unsigned int) * g_bits_per_byte>::type,
typename std::conditional<(t <= sizeof(unsigned long) * g_bits_per_byte),
bitflag_type<sizeof(unsigned long) * g_bits_per_byte>::type,
bitflag_type<sizeof(unsigned long long) * g_bits_per_byte>::type>::type>::type>::type>::type value_type;
};
}
So, the idea is that when you have a Bitflag variable, rather than specifying a type, you give it the BITFLAG_SIZE macro with the size of the flag set you want to be able to store. So, instead of something like Bitflag<unsigned int> flags, you’d write something like Bitflag<BITFLAG_SIZE(28)> flags. Under the hood, the macro uses a set of templates that take advantage of the C/C++ language standard that doesn’t define specific sizes for unsigned integral types, just relations; it says that unsigned char <= unsigned short <= unsigned int <= unsigned long <= unsigned long long. Everything else works because of those relationships.
The bitflag_type specializations all check to make sure that any two adjacent types don’t have the same size, and set the specialization to a special value in that case to prevent double specialization, which would cause a compile failure. In the case of Win64, unsigned int and unsigned long are both 32 bits, so the unsigned long spec ends up being -3 instead of 32. And then it never gets used as a result, which is perfectly fine.
The final piece was the bitflag_type_selector, which makes use of std::conditional to allow the template specializations to be assigned to ranges. Without that, it’d be pretty tedious to write all the code that’d allow anything but exact size matches to the types to be paired to the proper specialization of bitflag_type. So, yay for std::conditional!
One thing to watch out for here is data serialization for a Bitflag that’s using an unsigned char for its storage. Take the case of a flag mask of 33. That will get serialized as 33 by any basic serialization scheme for an unsigned short, unsigned int, unsigned long, or unsigned long long, which is great. But, for an unsigned char, it will see 3 and 3, which probably isn’t what you wanted. It’s solvable for sure, but I feel it’s worth mentioning. I did look into using uint8_t, but it turns out that this is very implementation specific, and a lot of implementations are just typedef’s of unsigned char anyway.
While not a requirement of this setup by any means, I like to store my flag sets in enumerations. So, for me, the next step was to be able to feed the enumeration into the BITFLAG_SIZE macro and always get the right size. I ended up doing that (with more templates), and that will be the subject of the next blog post. One that hopefully comes sooner than this one did! I guess we’ll see, I tend to have a problem keeping up with my desired posting schedule.
But that is the end of this post. Hopefully you found this useful, and hopefully I’m not insane and/or stupid. I welcome any feedback, and you are certainly welcome to use the code provided in whatever project you want. If you do, I’d love to know about it! Here’s the file if you just want to download it instead of copy/pasting the various blocks I posted above: Bitflag.hpp.
I’d also like to thank Brennan Conroy and Robert Francis for dealing with a full day of my inane ramblings and providing useful insight while I worked on this. I probably wouldn’t be making this post if it wasn’t for their help.
I mention it at the end of the post, too, but thank you to Brennan Conroy and Robert B Francis for dealing with me while I worked through this and for providing some quality feedback. You guys are the best!
Have you found any real benefit to doing this over using std::bitset? With padding yours would usually just be padded to 4 or 8 byte alignment anyway unless you’re packing a few of them together, at which point it seems bitset would not really have a downside.
So, valid concerns.
I’ll start by saying that it isn’t like I was using std::bitset, finally threw my hands in the air and said it sucked, wrote something better, profiled the results, and can prove what I did is better. Absolutely none of that happened. I wrote Bitflag originally sophomore year at DigiPen, and I’ve made small changes to it over time as needs arose. Since I have it, I like to use it if it fits my needs, and it always seems to.
That said, all I can really say is that it’s different. I think some of those differences make Bitflag better than std::bitset, but again, I have absolutely no data and analysis to back that up. And some of it is also up to personal preference and/or usage case.
std::bitset, like anything else, is implementation dependent. In a lot of (all?) implementations, it is an array of some type of unsigned integral type. In MSVC, it either makes an array of ulong or ulonglong, depending on platform. It then creates a proxy type so that it can first index to the proxy, and then index to the correct bit inside that proxy. Even if you only need an array of 1 element, std::bitset is still doing those indirections, and my Bitflag isn’t. However, if you need more than 64 flags, Bitflag isn’t going to work for you without modification, and then you might as well use std::bitset probably. Down that same logic road, there is the difference that Bitflag doesn’t allocate flag storage to the heap like std::bitset will, which may or may not matter to you.
std::bitset also provides a lot of functionality that Bitflag doesn’t because I never needed it so I never wrote it. Maybe that functionality could be written better without the overly generic requirements of std::bitset, maybe not. I doubt anyone will ever invest the time to do it and find out. If they did, I doubt it’d be overly worthwhile.
The padding issue is valid. For my use, I’m not doing better than std::bitset on this front, but I’m also not doing worse. If I compiled for platforms with different byte alignment, I will then likely be doing better than std::bitset, at least if I compile with MSVC. I’m going to guess that statement is more or less true for all modern compilers, but I know that it’s true for MSVC.
So, really, end of the day, I did it because I wanted to. There’s a high chance that it is completely irrelevant in the face of other options, like std::bitset.
And I forgot two pieces to this.
#1 Before I started the template autosizing, I did look into std::bitset as possibly doing what I wanted, but in the end it wasn’t a 100% fit, so I opted to move forward and do what I did.
#2 If Bitflag is irrelevant, I want to know that. And if it’s not and it helps someone, I want to know that, too. And I want to talk about it with people along the way, so feel free to tell me if anything in there is crazytown. I don’t think it is, but, you tell me.