Append 1 to 32 bit numbers to a char buffer

Question

I have a char* buffer, that I want to append integers of various bit sizes (between 1 and 32) to.

Thus, I need a function:

void addBits(char *buffer, int bits_appended_so_far, int object, int object_bit_size);

that can move an object of, say, 13 bits to the 470th bit position of buffer.

I could of course shift the bits onto the buffer one by one, but speed is of the essence so it seems like it should be possible to move larger chunks at a time. Is there a standard method to do this? Seems like there should be a standard method, but some googling and SO searching has not given me what I want.

What exactly are you trying to achieve? libgmp allows for direct bit manipulation of arbitrary-sized integers, which may be a nice way to store large bitstrings, or you could consider a `std::vector`... — Kerrek SB, Jun 14 '11 at 16:17
I don't see how vector would help this situation. I don't need dynamic allocation or anything. Just an efficient function for appending an X bit sized object at bit position Y in a char array. X is guaranteed to fit in an int. — Gurgeh, Jun 14 '11 at 16:29
`std::vector` sucks. There's always this feeling that it can be used like a `std::vector`. — David Thornley, Jun 14 '11 at 16:35
See this question: http://stackoverflow.com/questions/5704597/fastest-way-to-write-a-bitstream-on-modern-x86-hardware — Mark Ransom, Jun 14 '11 at 16:50

score 2 · Accepted Answer · answered Jun 14 '11 at 19:41

2

How about something like this:

void addBits(char *buffer, int bits_appended_so_far, int object, int object_bit_size) {
  int* int_buffer = reinterpret_cast<int*>(buffer);

  const int bits_per_int = 8 * sizeof(int);

  int current_int    = bits_appended_so_far / bits_per_int;
  int current_offset = bits_appended_so_far % bits_per_int;

  int_buffer[current_int] |= object << current_offset;
  if( current_offset )
      int_buffer[current_int+1] |= object >> (bits_per_int - current_offset);
}

This assumes that object only has the least significant object_bit_size bits set, otherwise you need to add a step to chop the extra (unwanted) bits off. It also assumes that buffer is initialized to zeros before you start adding the bits.

answered Jun 14 '11 at 19:41

JohnPS

2,518
19
17

That is good enough for me (+1 and accepted), although in general it would not work. Casting a random pointer to int causes Bus Error on some architectures, if it is not DWORD aligned. I once got that bug on SGI. Also it assumes that int object is large enough to handle a left shift of current_offset, which it is not, but it is OK, I'll use a long (it is enough that the code runs on x86_64). – Gurgeh Jun 15 '11 at 09:27
Thanks. I suppose you could avoid the int* cast by breaking the input int object into char-sized parts, then writing each part to the char *buffer separately. (2) The shifts are always less than the number of bits in an int, so should be well-defined, so I don't understand the second part of your comment. Anyway, hope it works or gave you some ideas. – JohnPS Jun 15 '11 at 20:16

score 1 · Answer 2 · answered Jun 14 '11 at 18:12

Align the bits properly in a 32 bit int using shift.
Find the location of the byte in the buffer.
If contents of buffer needs to be preserved, create an int pointer pointing at the relevant byte, then bitwise | the 32-bit int into that location.
If contents need not be preserved, simply memcpy(buffer location, 32-bit int);

score 0 · Answer 3 · answered Jun 14 '11 at 16:29

0

The simplest solution seems to be using a basic memcpy and shifting appropriately if the position is not byte aligned

answered Jun 14 '11 at 16:29

well_then

156
2

That will clobber the bits in the first target byte, but if I handle that special case separately, maybe it is simple enough. – Gurgeh Jun 14 '11 at 16:32
good point! It would clobber your data - I suppose you'd have to shift the data to add in a temporary variable, and and it in (assuming the array is initialized to all 0's).... Or and the shifted data into a temporary variable along with the original data for each byte/word and overwrite the original portion – well_then Jun 14 '11 at 16:54

GJ. · Answer 4 · 2011-06-14T17:23:34.667

0

Standard word sizes are 1,2,4,8 and 16 bytes depend of CPU, so you can shift only 8,16,32,64 or 128 bits at once. There is no standard method!

If you wont to spare with memory space than my proposal is that use as smallest unit one byte instead one bit to avoid bit shifting and speed up function.

EDIT: If memory is priority and bit sizes are between 1 and 32 there is still no problem because most CPUs support more than 1 bit shift at once.

Under x86 you can shif up to 32 bits at once if you are using 32 bit registers.

edited Jun 14 '11 at 17:23

answered Jun 14 '11 at 16:32

GJ.

10,810
2
45
62

No. Memory is priority 1, speed priority 2, and the extra bits really do matter for my application. – Gurgeh Jun 14 '11 at 16:40

Append 1 to 32 bit numbers to a char buffer

4 Answers4

Linked