This is continuation of posts: 

Challenge: Decode raw bytes

Decode data from raw bytes to some data structure which is easy to use and is resource friendly.

You get  n  bytes of data in which in each byte there is  0bFDDDFDDD  where  F  is some flag and  DDD  represents data. Lets assume you get pointer to data and number of bytes to read. Each  FDDD  represents individual data pack.

Please propose data structures and some code which will do decoding. In the end I would like to be able to check  F  flag and i.e. print value of  DDD  without hassle.

What we already achieved?

In previous posts we already implement some code which fulfills our requirements. Solution is not the best but it do what it suppose to be doing. Lets look on the code (it is modified a little bit):

As we previously noticed it has issues which probable can be corrected:

  • size of  Pack  is 2 bytes (16 bits) but it contain information which can be stored in 4 bits – can we introduce data structure which will consume less space in memory?
  • what we are really doing in  decode  function is iterating over half bytes – unfortunately we can only iterate over bytes – that’s why we cannot use  std::transform  function to achieve transformation of raw bytes into  Pack  structs. Can we introduce something which will allow us to iterate over every 4 bits in bytes of data.
  • is this code following CppCoreGuidelines?
  • what can we do to make it safer?
  • can we improve something using C++17 standard?

Lets try to handle first point.

Saving resources

Currently struct Pack  take as 4 times more space than it could in ideal situation.

Unfortunately we cannot build data structure which will take less space than one byte (8 bits) – at least I don’t know architecture which can do that.

But maybe there is a way to limit size of Pack  structure to 1 byte?  First thing which came to my mind was bitfields – as we are working with bits, right? So I tried:

Unfortunately during compilation I got warning:

Warning points to:

And program output change from:

into this:

What is good is that sizeof Pack  decrease to 1 byte but results are completely wrong. Checking what is this warning all about did not help me to understand (taken from here):

‘type’ : forcing value to bool ‘true’ or ‘false’ (performance warning)

This warning is generated when a value that is not bool is assigned or coerced into type bool. Typically, this message is caused by assigning int variables to bool variables where the int variable contains only values true and false, and could be redeclared as type bool. If you cannot rewrite the expression to use type bool, then you can add “!=0” to the expression, which gives the expression type bool. Casting the expression to type bool will not disable the warning, which is by design.

The following sample generates C4800:

I google for some help and I found another solution for this problem: Use the same type for all bitfields in a struct or class on Mozilla C++ Portability Guide. I change Pack  to:
and it start to work – only issue is that you don’t work with bool  type anymore but with 1bit unsigned number. In practice it work the same as 0 is implicitly casted to false and 1 to true. So whenever you use Pack::flag  when you expected bool it will work.

Warning description force me to think about what is going on in the create_pack  function. To be sure that compiler point me to correct line I change it into some expanded version (which force me to remove constexpr specifier):

To my surprise everything start to work! Don’t know why Visual treat it differently. In second implementation nevertheless I created Pack inside function scope local copy will be removed by optimizer thanks to RVO (Return Value Optimization).

So there are at least 2 ways of solving this issue – one of them is even recommended by Mozilla. Choose whatever is more preferable in your situation.

Summary 1

Thanks to bit fields we safe 50% of resources which were used before.

Can we do better? I believe that we can – we can eliminate dynamic allocation which is done inside vector::reserve. To make it visible lets solve second issue: iterate over every 4 bits in bytes of data.

Be explicit

Lets look on decode  function and on what is later going on with data returned from it.

We do all of this only to do:

So to sum it up we reserve 2*size  bytes of data only to iterate over it and handle it without hassle. In general it is good thing but if we could skip dynamic allocation it will make everything much butter.

Lets try to use boost::range  library to solve that problem. On the beginning lets assume that we have data packs in 8 bits instead of 4 bits – it will make our example simpler.

Using boost::range we can rewrite this code into:

Of course it does not produce std::vector<Pack>  but it creates range (using make_iterator_range_n  make_iterator_range_n ) which allows to iterate over bytes stored in data  pointer. After we create iterator range we pack it into transformed adapter – which will call create_pack  on every point which will be dereferenced using iterator from packed range.

Thanks to auto we don’t need to change rest of the code later code

will still work :). We still have working code but we don’t have dynamic allocation!

We successfully solve easy problem so lets back to original problem – iterating over each 4 bits. boost::range  library or even Eric Nieblers Range-v3 library don’t have anything which can be used to iterate over bits instead of bytes or objects. Fortunately boost::range  library gives us solutions to implement ranges ourselves – lets implement range which will traverse over 4 bits in byte range. I will use  boost::iterator_facade to implement it. After reading boost documentation and spending some time on trying to implement it I end up with implementation listed below (I believe it could be achieved in easier way – I would like to see some proposals):

increment , equal , dereference  methods and friendship to  boost::iterator_core_access are needed for this solution to work properly – we have now iterator able to iterate over bits. Now we need to use it to define range – we can do that using another boost::range tool:  boost::make_iterator_range . Now decode  function can be rewritten to:

We can introduce helper function to make it even simpler:

Complete source code looks like this:

And produce output:

Save resource summary

We succesfuly solve 2 out of 5 points mentioned on the beginning of this post. Points left are:

  • is this code following CppCoreGuidelines?
  • what can we do to make it safer?
  • can we improve something using C++17 standard?

If you have any proposals feel free to put it in the comments below this post (if you would like to put some code please remember to put it in  <pre></pre> tags.

Another issue came to my mind during preparation of this post – I would like to implement this solution using Eric Nieblers Range-v3 library and GSL. If anyone interested in doing that please let me know – we can post it together.

About 

Service Delivery Manager and Scrum Master at Sii Poland company.

Since 2007 C++ enthusiast. C++11/14 evangelist - learn modern ways of developing in C++. Teaching TDD and agile way of coding.

  • googleplus
  • linkedin
  • twitter

One comment on “Bitwise operations – part 3 – save resources

Leave a Reply