Pack arbitrary number of bits

Question

What would be a good way of packing an arbitrary number of bits? I have sentences which are known to only contain certain characters and want to encrypt. Hence an option is to use fewer bits to represent these characters and encrypt the characters in the process.

I looked at std::bitset, but it requires me to specify the size of the bitset as a constant, which will not do.

I would also like to know how the packed bits can then be converted back to characters to obscure the output.

ie if I pack A to 1000 and B to 0100, the resultant 8 bits of packing is 1000 0100 which is another character.

Btw, this is not supposed to be a strong form of encryption at all

Answer 1

What you are looking for is a dynamic_bitset. It is like std::bitset but it can change its size dynamically.

Also, you can use std::vector<bool> which will do what you need as a side effect of slightly unfortunate historical decision to implement it as a bitset.

Hope it helps. Good Luck!

Answer 2

If you're literally only encoding an alphabet of sixteen letters (say A-P), then you can build a lookup table:

unsigned char table[256] = {};
table['A'] = 0x0;
table['B'] = 0x1;
// ...
table['P'] = 0xF;

Now you can encode every two letters x and y as:

table[x] * 0x10 + table[y]

You should probably combine this with a unique-padding scheme to pad your input data up to an even number of letters (some variant of PKCS padding should work).

Answer 3

"I would also like to know how the packed bits can then be converted back to characters" This is basic coding theory. You probably want a Huffman encoding, which is an encoding without shared prefixes. So, if A is 1000, then there is no code 100 nor 10001.

You can therefore organize the symbols in a binary tree. Use the compressed bits to walk from the root down to the leaf nodes, going left for 0 or right for 1. When you get to a leaf node, emit the character stored there, and start at the the root again.