Hacker News new | comments | show | ask | jobs | submit login
Type-safe Bitmasks in C++ (gpfault.net)
97 points by nice_byte 3 months ago | hide | past | web | favorite | 40 comments



> Note that we don't explicitly set [enum values] to be powers of two

> return 1 << static_cast<underlying_type>(o);

Relying on default enum values to and automagically converting these into power of two bit masks is very brittle, and can create unexpected bugs and interoperability problems. The mask values change if the enum changes, unused bits in the middle of the bitmask are hard to handle, and the bit order is assumed with the first item being the LSB. The last point is particularly relevant given the NES buttons example, because it uses a bit order opposite to how the controller data is usually read[1]. This article defines

    #define BTN_A      0x01  /* 00000001 in binary */
    #define BTN_B      0x02  /* 00000010 in binary */
    /* ... */
    #define BTN_RIGHT  0x80  /* 10000000 */
The standard controller[2] state is sent from a shift register in the controller one bit at a time. This is usually read by the program as 8 reads from the I/O port, and shifted into a button state bitmask. E.g. something like:

    n = 8;
    buttons = 0;
    while(buttons--) {
        buttons = buttons << 1;
        buttons |= (CONTROLLER_1_IO_PORT & 0x01);
    }
With the buttons being read in the order [A, B, ..., RIGHT], the recommended bitmask is:

    BUTTON_A        = 1 << 7
    BUTTON_B        = 1 << 6
    /* ... */
    BUTTON_RIGHT    = 1 << 0
Obviously this is a minor mistake in a (probably untested) example. I just want to highlight how easily this type of "clever" - but brittle - coding style can introduce errors. Defining bit values (and other externally defined magic numbers) explicitly in e.g. a defined-to-be-canonical header file (which might be just those 8 #defines) is much safer and easier to debug/maintain. Then wrap those explicitly defined values into the C++ template for type safety or other fancy features.

[1] https://wiki.nesdev.com/w/index.php/Controller_Reading

[2] https://wiki.nesdev.com/w/index.php/Standard_controller


Oh, the NES controller bit order is 100% arbitrary. There's no standard - it all depends on if the programmer decided to write a ROL or ROR instruction that day.

But I agree with your point.


You meant:

    while (n--)


Defining bit values (and other externally defined magic numbers) explicitly in e.g. a defined-to-be-canonical header file (which might be just those 8 #defines) is much safer and easier to debug/maintain

I'm all for modern C++, but this is correct, at least IME with embedded systems. You're overall better off sticking with C-style if working at an abstraction level where the interface itself uses bitmasks. At this point you're manipulating memory manually which is (a) C's wheelhouse and (b) where type safety becomes largely irrelevant.

There is a lot to be said for using custom enum class implementations (e.g. http://www.drdobbs.com/when-enum-just-isnt-enough-enumeratio...) but it isn't clear to me how this kind of thing benefits bitmasks when the goal is presumably absolute maximum efficiency.


Something simpler is to put all bitmask enums in a namespace and use ADL to find the operators. Like this: https://pastebin.com/raw/ANh93JnN

Personally though, I wouldn't use this safety in most code. You'd have to be in some pretty serious shit for these templates to reduce mental overload rather than add it.


I think it reduces some mental load because it documents the interface: you don't have to look up which flags are valid for which functions, the types tell you.

Plus, with a small amount extra code you can do things like iterate over all the flags that are set etc.


The best way to iterate and do stuff with enums that I know is this way:

    enum {
        FOO_A,
        FOO_B,
        FOO_C,
        NUM_FOOS,
    };

    struct FooInfo {
        int kind;  // FOO_??
        const char *str;
        const char *long;
    };

    static const struct FooInfo fooInfo[NUM_FOOS] = {
        { FOO_A, "FOO_A", "The A of all the foos" },
        { FOO_B, "FOO_B", "The B of all the foos" },
        { FOO_C, "FOO_C", "The C of all the foos" },
    };

    for (int i = 0; i < NUM_FOOS; i++) {
        printf("Got #%d, %s. Description: %s\n",
               fooInfo[i].kind, fooInfo[i].str, fooInfo[i].long);
    }

More goodies:

    // if you want to use them as bitmasks
    // (but only few enums are used this way)
    enum {
        FOO_A_BIT = 1 << FOO_A,
        FOO_B_BIT = 1 << FOO_B,
        FOO_C_BIT = 1 << FOO_C,
    };

    // if you want to make strings out of C symbols, you
    // can also use a macro like this:
    #define FOOINFO(name, long) { name, #name, long },
    static const struct FooInfo fooInfo[NUM_FOOS] = {
        FOOINFO( FOO_A, "The A of all the foos" ),
        FOOINFO( FOO_B, "The B of all the foos" ),
        FOOINFO( FOO_C, "The C of all the foos" ),
    };


Both of these suffer from the potential maintenance problem of duplicating the list of enumerated values.

You can avoid that by using the X-Macro pattern, but that's quite heavy-handed and tedious to do if you have a lot of different enums.

It also doesn't use "enum class" which means that the namespace will be polluted unnecessarily.


I've read about X-Macros, but I don't really like many-line #defines. Another way is to autogenerate the enum definition + value table form from a single table represented as text. But I don't find the duplication to be much of a problem anyway, since mistakes (which are rare enough) don't go undetected for a long time.

I don't like namespaces. With namespaces a thing is known under one name here but not somewhere else. I find it really hard - in terms of mental overhead, and it also makes use of crude tools like grep much less effective.

I've never had any problems with name collisions, while applying only very little discipline. In my experience it's mostly a theoretical problem. (Btw., namespace names could conflict as well ;-> )


> I've never had any problems with name collisions, while applying only very little discipline.

Oh boy, you need to apply more than a little discipline. I applied only very little discipline once and defined a macro which I properly namespaced (or so I thought) e.g. ACME_SOMETHING. After quite a bit of debugging I realized that in one compilation unit a variable assigned with ACME_SOMETHING had a different value than it would get in all other compilation units. As it turns out my very little discipline wasn't enough and one of the system headers had a ACME_SOMETHING-define to that other value!


I would say two disagreeing definitions baked in is in the first place a problem with the C compilation process in general. I haven't hit that particular problem you describe, but I've seen xpdf fail in glorious ways because there were two versions of a "GlobalParams" structure. For years bug fixes kept trickling in, "fixing" various unexplainable misbehaviours. At some point someone noticed that it could all be traced back to the problem that various parts of the program were disagreeing what GlobalParams really was.

In that case the reason was that xpdf linked against libpoppler, a library that had been forked off xpdf itself. So it was really about two versions of "the same" structure.

In your case there might always have been two entirely different things (I don't know?), but anyway I expect a good compilation process two catch those cases such that the worst that could happen is a compilation error.


> I don't like namespaces. With namespaces a thing is known under one name here but not somewhere else.

I like namespaces for this exact reason. Basically, never ever use "using namespace foo" or namespace aliasing and always fully qualify your symbols "foo::bar". Now I always know where something is coming from.

> it also makes use of crude tools like grep much less effective.

It also makes grepping much simpler. For example, I can grep a file for "std::" to find all standard library symbols used.

As a side benefit, while I said above never to use namespace aliasing, I did recently come across a situation where it was actually beneficial. The code in question was using std:: containers, but it would have been nice to be able to optionally use EASTL containers instead (which are mostly drop-in replacements with different performance characteristics). One simple way to do this would be to use a different namespace in place of std:: (I'm gonna just say foo:: for this example) and then do something like this:

    #ifdef USE_EASTL
    namespace foo = eastl;
    #include <eastl headers>
    #else
    namespace foo = std;
    #include <std headers>
    #endif
> (Btw., namespace names could conflict as well ;-> )

Sure, but they can be aliased.


> never ever use "using namespace foo" or namespace aliasing and always fully qualify your symbols "foo::bar". Now I always know where something is coming from.

That's why I think they are silly. At this point, nothing gained vs simple prefixes. ONLY lost the ease of certainty that what you say actually holds true. And in fact, on the implementation side it usually doesn't hold true - I've rarely seen a namespaced implementation that uses full qualification.

Moreover "std::" is one character more, and a lot more noise, than "std_". Moreover in other common namespace syntaxes (like "std.") you still have the disadvantage that the namespace really is a separate lexical name (you could also write "std . foo" - it's logically, but not lexically, the same thing as "std.foo").

In conclusion, it's just a lot of unnecessary complexity. A complex solution looking for a problem.

> It also makes grepping much simpler. For example, I can grep a file for "std::"

With properly prefixed symbols you can do that as well. And more generally, you compile a list of symbols to grep for, or use other patterns (like std::.* tty .* or whatever) that likely don't match such an artificial namespace exactly. (In other words, namespaces are another opportunity for an implementor to get paralysed by choices he has to make, and another opportunity to be overly presupposing of how its API should be used by callers).

> As a side benefit, ...

Yeah I know I'm sounding a bit snarky now, but that's what linkers were invented for.


>> (Btw., namespace names could conflict as well ;-> )

> Sure, but they can be aliased.

Even worse! It defeats "Now I always know where something is coming from." See my other comment here about "GlobalParams".


Do enums change often enough for this to be a problem though? Often just adding a comment reminding to keep the enums in sync is enough.


Obviously it depends on the particulars of any given project, but if you're deriving more than just the string names of the enum values it may be worth it.

Using X-macros can sometimes reduce boilerplate hugely simply through avoiding switch statements on the enum values.


I think "often" is an exaggeration, but even if it did work that regularly, what about the times it doesn't?

Meanwhile, you're sat in front of a computer. Its entire job is to keep on top of stuff like this. Why not use it?


Because it's harder to do it in a complicated formal way than simply do it in the most straightforward way. If a type of mistake happens only very rarely and is typically easy to detect, it's almost certainly not a good idea to worry about it. You pay each time you express something using the more complicated formalism, and each time you work on parts that somehow have to deal with the more complicated artifact, and only every Nth time there is a marginal gain from using it.


In the abstract, sure - it's not uncommon for projects to start to become consumed by their own infrastructure. But I've never seen X-macro enum stuff contribute to that.

(This does of course presuppose that you really want to be able to always get the string name of an enum values. I've found this to be reliably the case, if only for logging purposes, but I've only got my own experience to go on.)


Nice technique, however, they don't allow you to do everything that a bitmask does. For example, there is no way to clear a flag, or to select a subset of flags.

That is, given:

  enum class Button {
    A, B, Select, Start, Up, Down, Right, Left
  };
There is no way to define:

  bitmask<Button> controller_state { Button::A | Button::B };
And then to find out if either of these buttons are pressed. The only way to do it is:

  bool fn2(bitmask<Button> controller_state)
  {
    return controller_state & Button::A || controller_state & Button::B;
  }
which _does_ generate the optimal code for checking if either is set. However you can't do something like

  void handleDirectionButtons(bitmask<Button> controller_state);
and then call that with something like:

  bitmask<Button> direction_buttons { Button::Up | Button::Down | Button::Right | Button::Left };
  handleDirectionButtons(state & directionButtons)
Of course, this could be added, see https://godbolt.org/g/48asye

You could also do something similar for the ~ case as well, however that would end up looking a bit uglier, as you would need to create more bit masks, something like:

  ~bitmask(Button::Up) & ~bitmask(Button::Down)
For an example, see https://godbolt.org/g/wN2xUV


That's doing it the hard way. This is the language-standard way:

    struct gamecontroller { 
        bool up: 1;
        bool down: 1;
        bool left: 1;
        bool right: 1;
        bool a: 1;
        bool b: 1;
        bool x: 1;
        bool y: 1;
        };
That's a structure with a size of one byte. Bit fields work just fine in C and C++, yet many programmers don't know this.


Unfortunately this cannot be used to pack an integer that is sent over the wire or to produce a register for a hardware peripheral. Basically this is not a valid substitution for most use cases of bit packing and can only be used to save a bytes of memory without reverting to undefined behavior. ie, casting this memory to a byte/int is undefined. The language does not define that the first field will be the lsb, msb or some arbitrary bit. The reason "many programmers don't know this" is because its a mostly useless language feature.


Portability is a problem. There is this:

Microsoft Specific

The ordering of data declared as bit fields is from low to high bit.

END Microsoft Specific[1]

In practice, everybody does it that way.

For fields only one byte wide, this isn't an issue for major compilers. NTP has been using this for decades without problems. But for structs more than one byte wide, there are little-endian/big endian problems. Just like with the numeric types.

This is only an issue if you intend to write the bitfield to a network, file, or device. Locally, you usually don't care about the representation.

[1] https://docs.microsoft.com/en-gb/cpp/cpp/cpp-bit-fields


The OP also is not a valid substitution for "most" (by what metric, anyway?) uses of bit packing.

The network wire doesn't need a C++ ABI-compatible object, and clearly isn't portable when communicating between systems running different software.

For transmitting data over network, convert from local format to network format in transit.

> can only be used to save a bytes of memory

Yes, that's what "packing" is for.


I think you are missing my points. This language feature cannot be used to eg, create a TCP header. It has nothing to do with the C++ ABI. And no, bit packing is not for memory saving, eg MISRA disallows bitpacking for the purpose of space saving.


That had been brought up elsewhere. Let me just copy-paste my response:

"I think enums allow a bit more flexibility. For example, if you need to store a piece of data that indicates which option to set, it's easier to do with an enum (can't store the "name" of the bitfield, and you're not permitted to take its address or offset either IIRC). I also like the 'Option1 | Option2 | ... ' syntax for creating bitmasks on the fly (not sure how you'd achieve that with bitfields)"


Does the OP offer benefits over the :1 way?


Bitfields would be, in theory, safer still: no manual bit-twiddling to begin with and also quite straightforward usage. Unfortunately, they are (and I guess will remain) underspecified as far as portability is concerned.

You can, of course, do something similar with member functions, e.g.

  class controller
  {
    unsigned value;
    static constexpr unsigned BTN_A = 0x01;
    ...
  public:
    bool a() const { return value & BTN_A; }
    void a(bool set) { if (set) value |= BTN_A; else value &= ~BTN_A; }
  };


This is pretty similar to what I've done in the past


This is all good and nice.

But in my opinion it violates principle of least surprise: when I encounter any enum, am I able to OR two values? These do not seem like flags, is this correct usage?

When a function expects bitmask<T>, I should know that T is just flag positions. But when I do not have some API point, only enum, how am I supposed to know that?

Plus, in case of interop with other languages, even with C, I will have Button::B == 2 in CPP, and BUTTON_B == 4 in C (or Button.B == 4 in Java). This of course adds to confusion...


With C++17 I would vote for using static_assert and constexpr if for type validation instead of SFINAE with enable_if.

Other than that, nice article.


From the first comment on the page:

"The non-member function operator overloads that return bitmask<option_type> will not be considered for overload resolution if the enums are in a different namespace than the bitmask definition. The template deduction of operator| would not be sufficient since it does not trigger ADL from outside the namespace -- the overload must be available from within the scope where it used. This effectively requires a using directive or declaration to make them visible to participate in resolution (and at which, this will attempt to participate in resolution of any enum type where it may be considered a better match)."

Is this correct? Because if it is, C++ is bonkers...


C++ ADL is pretty bonkers indeed, or at least somewhat surprising if you don't know the rules very well. Thing is without ADL some patterns would be a lot harder to write (or use).

I personally dislike overloading very much so I'm probably not the best person to defend it though.


Deep dark arcane corner-cases in C++? Say it ain't so!


The fact that this relies on overloading an operator for every enum makes this a complete non-starter as is in any professional codebase unfortunately. That can be fixed with a trait type though.


edit: did not read correctly: https://godbolt.org/g/XjdL7i

-

    uint8_t controller_state = BTN_A | BTN_B;
if I read correctly this example would not be possible anymore right?

    bitmask<Button> controller_state = Button::A | Button::B;
or

    bitmask<Button> controller_state { Button::A | Button::B };
won't work.


that's what the operator| at the end is for


The article claims no runtime overhead, but my understanding is that despite the consexpr that function needs to be evaluated at runtime because the inputs are unknown?


In many cases the input is known at compile time.

For example instead of

    #define BTN_A      0x01
you have

   bitmask<Button>(A)
Both of these are known at compile time and they are equivalent.


Constexpr aside any modern optomizer will handle this easily. Constexpr is more for allowing results to be passed to templates, static_assert, etc.. and less about optimization imo




Applications are open for YC Winter 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: