How to store many small integers into a byte array?

Question

Im making a online game, and as in many online games i will need loads of data being transfered via internet, so i need to be able to compress data efficiently.

For instance i want to send from my client to the server my character coordinates.

Edit: yeah bad example, let me change the values...

X coordinate(say -32 to 32).(65 diferent possible values) Y coordinate(-32 to 32).(65 diferent possible values) Z coordinate(-16 to 16).(33 diferent possible values)

i know that X was stored before Y that was stored before Z on the byte array before sending.

i know in the server that X cannot be lower than -31 nor higher than 32, the same for the other values.

65*65*33 = 139.425 diferent possible combinations of values for the 3 numbers = 17 bits.

7 + 7 + 5 = 19 bits.

so if i were to store X in the first 7 bits, then Y in the next 7 bits and then Z in the next 5 bits it would take 19 bits and i would be able to read them back in the other side with ease, but since all the posible combinations of values those 3 numbers can take would only take 17 bits to store i feel like im losing space here. Is there a good way to compress those 3 numbers using less than 19 bits?

of course 19 bits and 17 bits both need 3 bytes, but if it were 17 bits and 15 bits it would make a huge diference.

Answer 1

Many languages support bit-packing, but I don't see the advantage here. Each value is smaller than a byte, and the same number of bytes would be required whether or not they were packed, so you may as well save the small amount of time it would take to pack/unpack the values and just handle them unpacked.

Answer 2

Variable integer compression is used in Google's Protocol Buffers. It is called varint, and is pretty simple.

http://code.google.com/apis/protocolbuffers/docs/encoding.html#varints

Answer 3

I believe what you are after is a coding algorithm, not a compression algorithm. To compress those numbers you should know some extra information about these numbers.

For a coding algorithm: You have 65*65*33=139.425 different possible values. Log2(139.425) ~ 17.09 therefore you would need at least 18 bits to code any of these possible values. A simple coding scheme would be just like you said:

Value = Z*65*65 + Y*65 + X

Then to decode it:

X = Value % 65
Y = (Value/65) % 65
Z = (Value/65/65) % 33

Now Value is an integer. If you want to store it in a byte array you could split that integer into 3 bytes:

Byte1 = Value & 255;
Byte2 = (Value>>8) & 255;
Byte3 = (Value>>16) & 255;

Answer 4

I found this variant of BitSet that uses compression, you should take a look at it. The author claims that the algorithm is optimized for query speed, not for space, but that it is always more space efficient than Java's BitSet class. I think that if you are sending a high volume of coords over the wire you might see the improvement compared to just serializing the bits to a BitSet and then convert to a byte[].