Best way to store boolean values

[HomineLudens]

Let’s suppose this scenario:
A tiled map for a platform game. Every tile have some kind of bit information to qualify rendering or engine property.
What’s the best way to store this information for Pokitto.
I draft something like this (see below)

struct TileRender
{
  bool FlipH;
  bool FlipV;
  bool Rotate1;
  bool Rotate2;
};

const TileRender map_0_renders[11][14] =
{{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{true,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{true,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{true,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{true,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{true,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
{{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},{false,false,false,false,},},
};

but even if easy to access in code, I’m not sure this is a good optimization for memory consumption. Are bools packed to the nearest byte or any element use one byte?

[Pharap]

bool consumes at minimum an entire byte, and on some systems more if it’s more effort to access a single byte than it is to access a whole register worth of data.
Generally the compiler will err on the side of what’s fast rather than what uses the least space.

To store a bool as a single bit there will always have to be some bit shifting involved. What will differ is whether you handle the shifting yourself, whether the C++ standard library handles it or whether the compiler handles it.

I’ll present the different options in order from preferred to least preferred.

---

Option 1

The easiest way is to just make use of std::bitset.
This is probably the best answer for beginners because it requires no knowledge of bitshifting.

Here’s an example:

#include <bitset>

class TileData
{
private:
	static const size_t flipHOffset = 0;
	static const size_t flipVOffset = 1;
	static const size_t rotate1Offset = 2;
	static const size_t rotate2Offset = 3;

private:
	std::bitset<4> data;
	
public:
	// Make data default to 0
	TileData(void) : data() {}
	
	TileData(bool flipH, bool flipV, bool rotate1, bool rotate2)
	{
		// Version without bitshifting:
		this->data.set(flipHOffset, flipH);
		this->data.set(flipVOffset, flipV);
		this->data.set(rotate1Offset, rotate1);
		this->data.set(rotate2Offset, rotate2);
	
		// Version with bitshifting:
		/*unsgined long value =
			((flipH ? 1 : 0) << flipHOffset) |
			((flipV ? 1 : 0) << flipVOffset) |
			((rotate1 ? 1 : 0) << rotate1Offset) |
			((rotate2 ? 1 : 0) << rotate2Offset);
		this->data = std::bitset<4>(value);*/
	}
	
	bool getFlipH(void) const
	{
		return this->data[flipHOffset];
	}
	
	void setFlipH(bool value)
	{
		return this->data.set(flipHOffset, value);
	}
	
	bool getFlipV(void) const
	{
		return this->data[flipVOffset];
	}
	
	void setFlipV(bool value)
	{
		return this->data.set(flipVOffset, value);
	}
	
	bool getRotate1(void) const
	{
		return this->data[rotate1Offset];
	}
	
	void setRotate1(bool value)
	{
		return this->data.set(rotate1Offset, value);
	}
	
	bool getRotate2(void) const
	{
		return this->data[rotate2Offset];
	}
	
	void setRotate2(bool value)
	{
		return this->data.set(rotate2Offset, value);
	}
};

Usage:

TileData data0 = TileData();
TileData data1 = TileData(true, false, true, false);

---

Option 2

Firstly you can manually implement the bit shifting yourself:

class TileData
{
private:
	static const size_t flipHOffset = 0;
	static const size_t flipVOffset = 1;
	static const size_t rotate1Offset = 2;
	static const size_t rotate2Offset = 3;

private:
	std::uint8_t data;
	
public:
	// Make data default to 0
	TileData(void) : data(0) {}
	
	TileData(bool flipH, bool flipV, bool rotate1, bool rotate2)
	{
		this->data =
			((flipH ? 1 : 0) << flipHOffset) |
			((flipV ? 1 : 0) << flipVOffset) |
			((rotate1 ? 1 : 0) << rotate1Offset) |
			((rotate2 ? 1 : 0) << rotate2Offset);
	}
	
	bool getFlipH(void) const
	{
		return ((this->data & (1 << flipHOffset)) != 0);
	}
	
	void setFlipH(bool value)
	{
		if(value)
			this->data |= (1 << flipHOffset);
		else
			this->data &= ~(1 << flipHOffset);
	}
	
	bool getFlipV(void) const
	{
		return ((this->data & (1 << flipVOffset)) != 0);
	}
	
	void setFlipV(bool value)
	{
		if(value)
			this->data |= (1 << flipVOffset);
		else
			this->data &= ~(1 << flipVOffset);
	}
	
	bool getRotate1(void) const
	{
		return ((this->data & (1 << rotate1Offset)) != 0);
	}
	
	void setRotate1(bool value)
	{
		if(value)
			this->data |= (1 << rotate1Offset);
		else
			this->data &= ~(1 << rotate1Offset);
	}
	
	bool getRotate2(void) const
	{
		return ((this->data & (1 << rotate2Offset)) != 0);
	}
	
	void setRotate2(bool value)
	{
		if(value)
			this->data |= (1 << rotate2Offset);
		else
			this->data &= ~(1 << rotate2Offset);
	}
};

Usage:

TileData data0 = TileData();
TileData data1 = TileData(true, false, true, false);

If all your values are booleans then doing it manually probably won’t save you much.
At most it will potentially use less code if bitset has overheads.
(It may or may not have overheads.)

However, if some of your values are larger than simple booleans, then manual bitshifting can be a big advantage because it gives you greater control over the data.

---

Option 3

Lastly, the final alternative is to use bit fields.
Bit fields have fallen out of favour a bit because they aren’t portable, but if your code is only ever run on the Pokitto and the order of the bits isn’t important then bit fields are another easy way to handle things.

struct TileData
{
	bool flipH : 1;
	bool flipV : 1;
	bool rotate1 : 1;
	bool rotate2 : 1;
	
	TileData(void)
		: flipH(false), flipV(false), rotate1(false), rotate2(false)
	{
	}
	
	TileData(bool flipH, bool flipV, bool rotate1, bool rotate2)
		: flipH(flipH), flipV(flipV), rotate1(rotate1), rotate2(rotate2)
	{
	}
};

Usage:

TileData data0;
TileData data1 = TileData(true, false, true, false);
TileData data2 = { true, false, true, false };

I’ll bet you’re thinking “this option looks much easier”.

I agree that it looks much easier, but this is one of those cases where the laws of the language and compiler implementations can trip people up.

I won’t get into detail about when and how bitfileds can get you into trouble,
but as a rule of thumb, they’re fine if you’re only going to be targeting one system and using one compiler,
but if you can’t guarantee that then they’re best avoided.

[uXe]

To store a bool as a single bit there will always have to be some bit shifting involved.

One nice way around the bit-shifting is ‘bit-banding’ - from https://en.wikipedia.org/wiki/ARM_Cortex-M#Silicon_customization:

“Bit-banding maps a complete word of memory onto a single bit in the bit-band region. For example, writing to an alias word will set or clear the corresponding bit in the bit-band region. This allows every individual bit in the bit-band region to be directly accessible from a word-aligned address, and individual bits to be toggled from C/C++ without performing a read-modify-write sequence of instructions.”

Bit-banding is ‘optional’ on Cortex-M0+ microcontrollers though, so I am not certain if the Pokitto’s LPC11U68 even supports it? I know NXP implements something similar, called ‘Bit Manipulation Engine (BME)’ on at least some of their Cortex-M0+ microcontrollers…

Anyway, if not, then my vote would be for the Pokitto 2 to be able to support this - it would be game-changing for the display buffer!

[Pharap]

Neither the user manual or the data sheet make any mention of it, so I would assume it’s not supported.

Even if it is, I’d personally suggest sticking with bit shifting unless race conditions are an issue or it provides a significant speed or size boost.

[carbonacat]

I prefer using bitfields myself.

How are these non portable by the way? Aren’t they standard, or is it just the same issue with endianness in the end - orders of the bits in memory layout?

[Pharap]

To quote cppreference.

The following properties of bit fields are implementation-defined

• The value that results from assigning or initializing a signed bit field with a value out of range, or from incrementing a signed bit field past its range.
• Everything about the actual allocation details of bit fields within the class object
  • For example, on some platforms, bit fields don’t straddle bytes, on others they do
  • Also, on some platforms, bit fields are packed left-to-right, on others right-to-left
• Whether char, short, int, long, and long long bit fields that aren’t explicitly signed or unsigned are signed or unsigned. (Until C++14)
  • For example, int b:3; may have the range of values 0…7 or -4…3. (Until C++14)

So they behave well in isolation, but you can’t make any assumtions about how the bit fields correspond to actual memory and you couldn’t reliably write them to memory without making your code adapt to both endianness and the behaviour of the compiler.
You could test and then be somewhat sure of what the compiler will do, but you’d have to remember that your code wouldn’t be portable.

It (probably) wouldn’t affect the Pokitto because C++ is used instead of C,
but there’s an interesting read here showing one interesting side effect of bit fields in C (and possibly C++03).