Pack one bit into byte or something like that, how?

[BytePtr]

Hi.

Let's take simple BYTE (0..255).
And let's say it contains some value like: 30 or even maximum value: 255.
Is it possible to pack one additional byte value into this? AND/OR-ing or whatever the operators are.

In my case, additional values are: 0,1,2,3 and 4. Just one of them.
I need to pack them into this BYTE.

I don't even know if it's possible. I know if i add one more to 255, it's overflow. But if i just AND/OR additional value into it, will this work?
Value probably changes during packing additional stuff into it, but it's okay, if i can retrieve both values, like they were before packing.


Thanks in advance for any help.

[jj2007]

You have 8 bits, so you can pack any combination of
1+7
2+6
3+5
4+4

Take 3+5:
00000111=1+2+4=7
00011111=1+2+4+8+16=31
So the max value of the first number is 7, while the second can reach 31.

packing:
mov eax, 6
mov edx, 27
shl edx, 3
add eax, edx

unpacking:
mov edx, eax
and eax, 7
shr edx, 3

[dedndave]

two ways come to mind

you can pack 3 of em the hard way:
25*N3 + 5*N2 + N1

or 2 of em the easy way
16*N2 + N1

to get really hard, you can pack 22 of em into 7 bytes   :P

[BytePtr]

Thank you very much for your replies. I will try to make it work and will see how it comes out.
If i will integrate it to my code and it starts working i will let you know.

[BytePtr]

Thank you once again.
I integrated into my app and it's working just perfectly. Got what i needed.
If you want jj2007 and dedndave i will add you to my app about box.

You helped me many times here.

Thank you both once again.

[BytePtr]

Ok, seems i encountered some problem.

You said:
"So the max value of the first number is 7, while the second can reach 31."


I got that limit of 31 when packed the stuff, without packing additional stuff into the X (0..255) i got correct results. To the end.
What is wrong?
So if i have variable X with maximum value over 31, i can't pack anything to it anymore?

In my another test app, the stuff worked correctly until i packed the 0,1,2,3 or 4 into it.
Then it limited to 31 and then started again from 0.

[dedndave]

if you have a value whose range is 0 to 31, it requires 5 bits to store it
2⁵ = 32 (5 bits may represent up to 32 unique values)

each byte has 8 bits

if you have several values with the same range, you can use more bytes and pack more values
for example, we can pack (8) 5-bit values into 5 bytes (40 bits)

also - if you have one value with a range of 0 to 7 and another value with a range of 0 to 31, you can pack them both into 1 byte
2³ = 8 (3 bits may represent up to 8 unique values)

tell us the range of all the values you want to pack

[jj2007]

       mov eax, 111b     ; same as mov eax, 7 in decimal notation
eax=   00000111=1+2+4=7
       mov edx, 11111b   ; same as mov edx, 31
edx=   00011111=1+2+4+8+16=31
       shl edx, 3        ; move the set bits to the left
edx=   11111000
       add eax, edx
       00000111
       11111000 +
eax=   11111111 = 255

[BytePtr]

Ok, i will explain again: I work with 3D coordinates in my OpenGL app. X, Y and Z
X,Y minimum value can be 0, maximum value can be 255.
Z can hold values 0..7.

If i read X,Y,Z in my OpenGL app, i get coordinates of my objects of course. But into this X coordinate i would like to pack also the simple number, let's call it ID value. The ID value can only be one of these numbers: 0,1,2,3 or 4.
So the X coordinate should also hold the ID number in it.
Later if i need X coordinate, i will unpack the value packed in it and will take the X value, and if i need the ID value.
Seems that the BYTE which can hold values up to 255, is unable to hold also my ID value.

I can also work with UNSIGNED_INT's, if need to. No problem.  I guess.
If it will make things easier and makes them work.

Maybe im wrong. I will take a look into my other test app i made, and will see if it's my code or it's just doesn't fit.
Will also look, if it limits the same way.

EDIT yes, i discovered that my second test app also limit's X coordinate to 31 only. After i have unpacked it.
But it should not limit it. It must be allowed to go up to 255.

Guys, don't be mad on me. Im just learning the bit packing and similar things.

[qWord]

Seems that the BYTE which can hold values up to 255, is unable to hold also my ID value.

simply use a fourth variable that holds the ID  :wink

[dedndave]

Jochen is showing you the basics   :U
works great if everything is orthoganal

several years ago, i wanted to pack some text files
upper case - 26
lower case - 26
numbers - 10

that's 62 different values
if you add space and period, you're all done
64 values would fit into 6 bits

the next step is 7 bits
i wasn't happy with the "compression ratio", but you could have 128 unique characters

so - i wanted something in between
got out the calculator and figured out that i could pack up to 85 unique characters with a little better compression

but - shifting bits wouldn't do it
you have to multiply and divide
it was a lesson in Horner's Rule (Ling Long Kai Fang   :P )
although, i didn't know Horner or Ling at the time

essentially, i made a base-85 numbering system

in base-10, we put digits together like this
D_N*10^N + D_N-1*10^N-1 ... + D₃*10³ + D₂*10² + D₁*10¹

my packed system looked like this
D₆*85⁶ + D₅*85⁵ + D₄*85⁴ + D₃*85³ + D₂*85² + D₁*85¹

i got 6 base-85 "digits" in 5 bytes   :P

[jj2007]

Ok, so you have X, Y, Z with 0...255, and ID. You can't avoid another byte for the ID, unless you can reduce the range for one of the others.
For performance reasons, you should 4 bytes = one DWORD anyway. Do you have a good reason for being stingy with data size?

[dedndave]

the problem you have is that you a set of 3 values
not much packing to be done, unless you want to pack 8 sets of values together   :P

i.e. (8) 3-D coordinates (which would normally require 24 bytes) can be packed into a group of 19 bytes

with the ID - just pack the 3-bit Z value with the 3-bit ID   :P
ok - you lose a couple bits
on the bright side, you could expand the system to accomodate 5-bit ID's (0-31)

in 3 bytes, you can get the ID, X, Y, and Z

that may save you some space
but - performance is likely to be improved by using 4 bytes, anyways
that is because the 32-bit world likes to access memory 32-bits at a time   :bg

[FORTRANS]

Hi,

   If the X and Y values need to hold 0 to 255, they fill a byte.
No space left over to pack more data into the byte.  If the Z
value is 1 to 7 it requires three bits.  The ID holds 1 to 4 so it
requires three bits for a single ID.  You can pack the ID and
the Z value into one byte if wanted.  You can use four bits each
and treat the byte as a 2 digit packed BCD value.

   If you have oodles of ID values you can pack them as Dave
showed by compressing three into one byte.

Regards,

Steve N.

[BytePtr]

ID holds 0..4. (1--5 if you want).
So they fit into Z?


Why im picky about data type, is because the OpenGL function i work is glColor3ub.
In other words, unsigned byte. It seems to stop working correctly if supply him something else.
In my app each object has color derived from X,Y,Z. So for ex: X0,Y0,Z0 are all RGB 0,0,0, so, this object has coordinates of 0,0,0.
If X1, Y0, Z0, then color of this object is RGB 1,0,0. glColor3ub just does all that, the only function that i found which paints my objects to color derived from X,Y,Z.

But each object has that ID number, so when reading coordinates, i also need this ID. Without packing stuff together, it seems to get too complicated.


Thanks for all the replies so far. I will try with Z.