How to use bitfields that make up a sorting key without falling into UB?

Question

Let's say I want to have the following bitfield:

struct SortingKey {
    uint8_t a: 2;
    uint8_t b: 4;
    uint8_t c: 2;
}

To use a simple integer comparison, I may need to wrap it into an union like this and use value for sorting:

union UnionSortKey {
    SortingKey key;
    uint8_t value;
}

However, in C++, reading an inactive union member is Undefined Behaviour. How can I guarantee that I do not fall into UB but keeping a simple integer comparison?

What about writing a custom comparator lambda function or class to pass to the sort algorithm? Question remains: How to interpret the fields according their significance (HSB, LSB)? — πάντα ῥεῖ, Oct 18 '20 at 15:18
If you want to stay within standard C++, without any reliance on how bitfields are laid out, then you have to combine them into an integer with shifts: `a | (b << 2) | (c << 6)`. Don't use a union. — Nate Eldredge, Oct 18 '20 at 15:19
@NateEldredge I did not think of this. Thank you! Can you make this an answer? :') — Raildex, Oct 18 '20 at 15:22

Jarod42 · Accepted Answer · 2020-11-16T19:11:49.973

You can't use union for type punning,

In C++20, you might use default operator <=>

struct SortingKey {
    uint8_t a: 2;
    uint8_t b: 4;
    uint8_t c: 2;

    auto operator <=>(const SortingKey&) const = default;
};

Before, you have to provide the conversion/comparison manually:

bool compare(SortingKey lhs, SortingKey rhs)
{
    if (lhs.a != rhs.a) return lhs.a < rhs.a;
    if (lhs.b != rhs.b) return lhs.b < rhs.b;
    return lhs.c < rhs.c;
}

or

bool compare(SortingKey lhs, SortingKey rhs)
{
    auto to_u8 = [](SortingKey s) -> std::uint8_t{ return s.c << 6 | s.b << 2 | s.a; };
    return to_u8(lhs) < to_u8(rhs);
}

If you are lucky (bitfield is implementation specific, so...), your compiler might do a simple comparison of underlying type.

(clang succeeds to do that optimization with "correct" order).

or, if you don't have padding bit/byte, you might use memcpy/memcmp (which succeeds to be optimized)

bool compare(SortingKey lhs, SortingKey rhs)
{
    auto to_u8 = [](SortingKey s) -> std::uint8_t{
        std::uint8_t c; memcpy(&c, &s, 1); return c;
    };
    return to_u8(lhs) < to_u8(rhs);
}

or

bool compare(SortingKey lhs, SortingKey rhs)
{
    return memcmp(&lhs, &rhs, 1) < 0;
}

Demo

How to use bitfields that make up a sorting key without falling into UB?

1 Answers1

Linked