• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
DanBerliner

Working with a C++ data type on a bit by bit level

29 posts in this topic

I am using C++, I have no decided on a graphics library so I am open to anything that works on Windows and *nix if it makes my life easier. This is more of a theory question though so I don't think it will be relevant which one I am using.

While it is not a game, I am writing a program that allows the user to create a one color overlay over an image with a paintbrush. My first major issue is storing all that data, the program will mainly be used on projectors running at sizes as large as 1920x1080, meaning that it will use a minimum of 1.98mb of data at any given time. My issue is this: there is no one bit data type, the smallest C++ data type is 32 bits. While 1.98mb of data in memory isn't an issue at any level, having 63.4mb of data would be just inefficient. As an electrical engineer I am familiar with binary and know that each int can hold 32 pixels of data, my problem is working with an int in terms of bits.

My question is how would I discern which bits are what? I would need (for instance) the number 2800169371 to correspond to its binary value, 10100110111001110011000110011011, where 1 is on and 0 is off. I would have to go though each bit and see if it on or off.
0

Share this post


Link to post
Share on other sites
[quote name='Dan Berliner' timestamp='1302119750' post='4795179']
there is no one bit data type, the smallest C++ data type is 32 bits.[/quote]int is 32 bits.
char is 8 bits.
short is 16.

[quote]my problem is working with an int in terms of bits.[/quote]
See std::vector<bool>.

It should be specialized to use one bit per value, while working like a regular array.
1

Share this post


Link to post
Share on other sites
[quote name='Antheus' timestamp='1302120255' post='4795183']
int is 32 bits.
char is 8 bits.
short is 16.
[/quote]
My mistake there

[quote name='Antheus' timestamp='1302120255' post='4795183']
See std::vector<bool>.

It should be specialized to use one bit per value, while working like a regular array.
[/quote]
I recall reading somewhere that bool was longer than 1 bit, after googling it again I see that I was incorrect. Thanks.

For people who may come here looking for the original requested solution (perhaps for a different issue), the following function will tell you if a bit is on or off in an int data type (you can modify it to use any fundamental data type:
[code]
bool isBitOn(int place, int &subject)
{
return ((subject & 1<<place)==0 ? false : true);
}
[/code]
1

Share this post


Link to post
Share on other sites
Its usually easier to use a seperate variable for each component and combining them, than remembering huge numbers for each colour.

unsigned int red = 128;
unsigned int green = 0;
unsigned int blue = 255;
unsigned int alpha = 255;

You can put them all together into an int with some bitwise operators

unsigned int colour = 0;
colour |= (red << 24);
colour |= (green << 16);
colour |= (blue << 8);
colour |= |= alpha;

You can do the opposite to get each individua l component back

red = 0xff000000 & colour; // only want the red bits, so mask the others out
red = red >> 24;

green = 0x00ff0000 & colour;
green = green >> 16;

I'm slightly rusty so it may have mistakes. Your just packing each different component into one int, most significant bytes being red in what I've done. Of course it all depends on what bytes are considered to be what, I've gone for RGBA but you see lots of combination (BRGA etc). No need to deal with individual bits (unless you have to). You can do individual bits in a similar way. Take a look at bitwise operators [url="http://www.cprogramming.com/tutorial/bitwise_operators.html"]http://www.cprogramming.com/tutorial/bitwise_operators.html[/url] .
1

Share this post


Link to post
Share on other sites
[quote name='Nanoha' timestamp='1302120800' post='4795190']
Its usually easier to use a seperate variable for each component and combining them, than remembering huge numbers for each colour.

unsigned int red = 128;
unsigned int green = 0;
unsigned int blue = 255;
unsigned int alpha = 255;

You can put them all together into an int with some bitwise operators

unsigned int colour = 0;
colour |= (red << 24);
colour |= (green << 16);
colour |= (blue << 8);
colour |= |= alpha;

You can do the opposite to get each individua l component back

red = 0xff000000 & colour; // only want the red bits, so mask the others out
red = red >> 24;

green = 0x00ff0000 & colour;
green = green >> 16;

I'm slightly rusty so it may have mistakes. Your just packing each different component into one int, most significant bytes being red in what I've done. Of course it all depends on what bytes are considered to be what, I've gone for RGBA but you see lots of combination (BRGA etc). No need to deal with individual bits (unless you have to). You can do individual bits in a similar way. Take a look at bitwise operators [url="http://www.cprogramming.com/tutorial/bitwise_operators.html"]http://www.cprogramm..._operators.html[/url] .
[/quote]

The program don't allow for more than black and transparent so a 1 bit value per pixel is all that is needed. Thanks for the explanation though.
0

Share this post


Link to post
Share on other sites
[quote name='Dan Berliner' timestamp='1302120771' post='4795189']
I recall reading somewhere that bool was longer than 1 bit, after googling it again I see that I was incorrect. Thanks.[/quote]
bool does indeed take more than one bit. At the very least it takes one byte, and it may take more. However, std::vector<bool> is implemented in some clever way and will store bits compactly, just as you want.
1

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1302123405' post='4795210']
[quote name='Dan Berliner' timestamp='1302120771' post='4795189']
I recall reading somewhere that bool was longer than 1 bit, after googling it again I see that I was incorrect. Thanks.[/quote]
bool does indeed take more than one bit. At the very least it takes one byte, and it may take more. However, std::vector<bool> is implemented in some clever way and will store bits compactly, just as you want.
[/quote]

Great, so now I cant read. After looking another time I see it is 1 byte, not one bit.

I will go with std::vector<bool>, I currently have a proof of concept written up with simple bools in an array and it is seeing some performance issues on the slow computer running it.
0

Share this post


Link to post
Share on other sites
What about the std::bitset data type. I have never used it but I thought this was specifically to work with bits.

So you can do std::bitset <32> myInt;

This is what c++ says about bitset
[quote]
A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1, true or false, ...).[/quote]
[url="http://www.cplusplus.com/reference/stl/bitset/"]http://www.cplusplus.com/reference/stl/bitset/[/url]
0

Share this post


Link to post
Share on other sites
[quote name='gretty' timestamp='1302126817' post='4795236']
What about the std::bitset data type. I have never used it but I thought this was specifically to work with bits.

So you can do std::bitset <32> myInt;

This is what c++ says about bitset
[quote]
A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1, true or false, ...).[/quote]
[url="http://www.cplusplus.com/reference/stl/bitset/"]http://www.cplusplus...nce/stl/bitset/[/url]
[/quote]

Size is defined at compile time.

bitset is:[code]template < size_t N > struct bitset {
char data[N / 8 + 1];
};[/code]


Interestingly enough, this would be something where JIT-based languages could run circles around C++. Unfortunately, Java refuses to add value objects. But it would allow a given instance to generate fully specialized and static code based on run-time parameters.
0

Share this post


Link to post
Share on other sites
What about multi dimensional vectors? Would the same advantage apply to a multi dimensional vector? The math gets a little more annoying if it is one dimensional going over a two dimensional screen.
0

Share this post


Link to post
Share on other sites
[quote name='Dan Berliner' timestamp='1302137979' post='4795293']
What about multi dimensional vectors? Would the same advantage apply to a multi dimensional vector? The math gets a little more annoying if it is one dimensional going over a two dimensional screen.
[/quote]


The simplest way to deal with multi-dimensional arrays is to use an underlying one-dimensional array and translate your multiple indices into a single index.

[code] std::vector<bool> image(false, 1920*1080);
image[x+y*1080] = true;[/code]
0

Share this post


Link to post
Share on other sites
[quote name='Antheus' timestamp='1302120255' post='4795183']int is 32 bits.
char is 8 bits.
short is 16.
[/quote]

Actually char is 8bit in 99% of all environments, and from there it's char < short <= int (not perfectly sure about about where it's < and <=). You will most likely find short to be 16bit most of the time and long to be 32bit, while int is the "natural" size for your platform (which happens to be 64bit if you compile for 64bit and 16bit for some old 16bit machines). Never make assumptions about the size of types, that's why there's a stdint header with all the int8_t typedefs (and a ton of #ifdefs).



[quote name='Nanoha']
unsigned int colour = 0;
colour |= (red << 24);
colour |= (green << 16);
colour |= (blue << 8);
colour |= |= alpha;
[/quote]

You realize that you can let the compiler do that kind of thing? (Including a somewhat silly use of union for interchangeable usage.

[code]
union
{
uint32_t color;
struct
{
uint32_t red : 8;
uint32_t green : 8;
uint32_t blue : 8;
uint32_t alpha : 8;
}
};
[/code]

Though I honestly see little point in doing that over using using one uint8_t per channel in the first place.

While I would stick with vector<bool>, it wouldn't be that hard to use an array and get the bits yourself. Depending on the used type (unsigned int might be the most efficient), all you have to do is use your bit index and get the word and bit of that word ( i/sizeof(unsigned) and i%sizeof(unsigned) ). Somebody will point out that "it's teh fasta using bit fiddling", ie i>>4 and i&0xfffffff, but I haven't seen a compiler for a while that wasn't smart enough to turn / and % into bit operations for power of two operands.
0

Share this post


Link to post
Share on other sites
[quote name='Trienco' timestamp='1302151859' post='4795353']
Actually char is 8bit in 99% of all environments, and from there it's char < short <= int (not perfectly sure about about where it's < and <=).
[/quote]
In the current version of the C++ standard, it's char <= short <= int <= long with 8 <= char, 16 <= short, 32 <= long. It's perfectly possible for an implementation to have 32-bit everything (and at least one annoying embedded platform is that way).
0

Share this post


Link to post
Share on other sites
[quote]I recall reading somewhere that bool was longer than 1 bit, after googling it again I see that I was incorrect. Thanks.[/quote]

sizeof(bool) is generally equal to sizeof(int), due to the fact that most platforms are unable to access individual bits and have alignment restrictions on other datatypes. However std::vector<bool> is specifically designed to pack the elements as tightly as possible, and incurs an [b]instruction overhead[/b] in doing so. If you need to set a lot of bits at once and are worried about performance, you might want to avoid using the subscript operator.

0

Share this post


Link to post
Share on other sites
[quote]
sizeof(bool) is generally equal to sizeof(int), due to the fact that most platforms are unable to access individual bits and have alignment restrictions on other datatypes. [/quote]
I think you are mistaking the padded size of the variable with the sizeof(variable).

sizeof(bool) is normally equal to sizeof(char), which is defined as 1 and is most commonly 8 bits. However, the compiler padding will often mean that an individual boolean value is allocated a word of space by itself. However, contiguous booleans will be tightly packed by most compilers.
0

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1302143152' post='4795315']
[quote name='Dan Berliner' timestamp='1302137979' post='4795293']
What about multi dimensional vectors? Would the same advantage apply to a multi dimensional vector? The math gets a little more annoying if it is one dimensional going over a two dimensional screen.
[/quote]


The simplest way to deal with multi-dimensional arrays is to use an underlying one-dimensional array and translate your multiple indices into a single index.

[code] std::vector<bool> image(false, 1920*1080);
image[x+y*1080] = true;[/code]
[/quote]

I've done that, but just to iterate though an 800*600 (480,000) element vector takes my computer about 570-590ms. I have a pretty high end machine so that's unacceptably slow. It's just a simple iteration loop where it adds one to a int variable; the actual program will have to do significantly more than that per loop. When I was using an array of bool for the same sized screen it took about 47ms while drawing. Unless there is some way to optimize this considerably I dont see vectors as being a possible solution even if they can do the one bit thing.
0

Share this post


Link to post
Share on other sites
Which compiler did you use for that benchmark? Some compilers create extra code even in release mode when using standard library templates. For example some versions of MSVC will enable _SECURE_SCL in release, which can significantly slow things down.
0

Share this post


Link to post
Share on other sites
[quote name='SiCrane' timestamp='1302222371' post='4795759']
Which compiler did you use for that benchmark? Some compilers create extra code even in release mode when using standard library templates. For example some versions of MSVC will enable _SECURE_SCL in release, which can significantly slow things down.
[/quote]

I'm using MSVC, I'll look into optimizing on that compiler.
0

Share this post


Link to post
Share on other sites
Would something like this work?

[code]


template <int SIZE_IN_BITS>
class BitArray
{
char bytes[SIZE_IN_BITS/8];

public:

BitArray()
{
memset(bytes,0,sizeof(bytes));
}

void SetBit(int bit)
{
int index = bit / 8;
int offset = bit % 8;

char mask = 1 << offset;

bytes[index] |= mask;
}

void ClearBit(int bit)
{
int index = bit / 8;
int offset = bit % 8;

char mask = 0xFF & ~(1 << offset);

bytes[index] &= mask;
}

bool GetBit(int bit)
{
int index = bit / 8;
int offset = bit % 8;

char mask = 1 << offset;

return (bytes[index] & mask) == mask;
}
};

[/code]

EDIT: You probably want to make the internal array heap allocated if it's going to be large but the idea is the same...
0

Share this post


Link to post
Share on other sites
[quote name='Dan Berliner' timestamp='1302219094' post='4795740']
I've done that, but just to iterate though an 800*600 (480,000) element vector takes my computer about 570-590ms.[/quote]

Not saying it's the one and only reason, but if you want it to be FAST, you should go back to using int. Something that neatly fits the machines register size and doesn't require bitmasking and shifting for every access (though I'd expect no shifting and simply comparing with 0 after masking).

Keep in mind that the image you want to place your overlay on is apparently the same size and is also stored uncompressed as pixel data in memory, meaning it's also at least 24bit per pixel (unless it's scaled and your overlay has its own independent resolution). If storing is your issue, maybe you could use a simple compression like run length encoding (depending on how complex your overlays will get).
0

Share this post


Link to post
Share on other sites
[quote name='Dan Berliner' timestamp='1302219094' post='4795740']
I've done that, but just to iterate though an 800*600 (480,000) element vector takes my computer about 570-590ms.[/quote]

That comes out to about 3000 cycles per pixel. Something is not right... It should be at least two orders of magnitude faster. Perhaps you can post some short code that shows the slowness?
0

Share this post


Link to post
Share on other sites
[quote name='doesnotcompute' timestamp='1302226064' post='4795774']
Would something like this work?
...

EDIT: You probably want to make the internal array heap allocated if it's going to be large but the idea is the same...
[/quote]

I think this is a bad idea as it just duplicates std::bitset except less efficiently. Also, your implementation has a serious bug since you're rounding down the size of the data array.


Also, isn't std::vector<bool> deprecated? I'd say use std::bitset instead.
0

Share this post


Link to post
Share on other sites
[quote name='Storyyeller' timestamp='1302273102' post='4795967']
Also, isn't std::vector<bool> deprecated? I'd say use std::bitset instead.[/quote]
I don't think so. There have been proposals to deprecate it, though. The size of a std::bitset has to be known at compile time, which makes it a poor substitute for std::vector<bool>. A more reasonable substitute would be boost::dynamic_bitset.
0

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1302266330' post='4795932']
[quote name='Dan Berliner' timestamp='1302219094' post='4795740']
I've done that, but just to iterate though an 800*600 (480,000) element vector takes my computer about 570-590ms.[/quote]

That comes out to about 3000 cycles per pixel. Something is not right... It should be at least two orders of magnitude faster. Perhaps you can post some short code that shows the slowness?
[/quote]

I unfortunately don't have the exact code anymore but it was very simple. It was a vector<bool> that was 800*600 in length (it was one dimensional). I then used a simple iterator to go though it in a for loop. Inside the for loop I incremented an int by 1, I didn't even draw a pixel.
0

Share this post


Link to post
Share on other sites
In Debug mode or Release mode? Did you try it with _SECURE_SCL disabled on older MSVC versions, as SiCrane mentioned?
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0