What is the most efficient way in Java to pack bits into byte[] and read it back?

Question

I currently use these two functions to pack and read bits in a byte array. Wondering if anybody has any better ideas or faster ways to do it?

Edited the program with a few more optimization and tabled a few calculations. Currently 100mil Put and Get takes about 12 secs instead of 16 secs now.

If anybody is using the current code make sure the value passed in to Put is a positive number as it's expecting unsigned numbers coming down. If there is interest I can put up signed and unsigned versions.

class BitData
{
    static void Put(byte Data[], final int BitOffset, int NumBits, final int Value)
    {
        final long valLong=(Value&((1L<<NumBits)-1L));
        int posByte=BitOffset>>3;
        int posBit=BitOffset&7;
        int valByte;
        int ModifyBits;

        long lValue;
        int LeftShift;
        ModifyBits=8-posBit;
        if(NumBits<ModifyBits) ModifyBits=NumBits;
        LeftShift=(8-posBit-ModifyBits);
        while(true)
        {
            valByte = Data[posByte];
            if(ModifyBits==8)
            {
                lValue=valLong<<(32-NumBits)>>(24);
                Data[posByte]=(byte)lValue;
            }
            else
            {   
                lValue=valLong<<(32-NumBits)>>(32-ModifyBits)<<LeftShift;
                Data[posByte]=(byte)((valByte & ~(((1<<ModifyBits)-1) << LeftShift)) | lValue);
            }
            NumBits-=ModifyBits;
            if(NumBits==0) break;
            posByte++;          
            ModifyBits=8;
            if(NumBits<ModifyBits) 
            {
                ModifyBits=NumBits;
                LeftShift=(8-ModifyBits);
            }
        }
    }

    static int GetInt(byte Data[], final int BitOffset, int NumBits)
    {       
        int posByte=BitOffset>>3;
        int posBit=BitOffset&7;


        long Value=0;
        int ModifyBits;
        int valByte;
        int LeftShift;
        ModifyBits=8-posBit;
        if(NumBits<ModifyBits) ModifyBits=NumBits;
        LeftShift=(8-posBit-ModifyBits);
        while(true)
        {
            valByte = Data[posByte] & 0xff;
            if(ModifyBits==8) Value+=valByte;
            else Value+=(valByte & ((1<<ModifyBits)-1) << LeftShift) >> LeftShift;              
            NumBits-=ModifyBits;
            if(NumBits==0) break;
            posByte++;
            ModifyBits=8;
            if(NumBits<ModifyBits) 
            {
                ModifyBits=NumBits;
                LeftShift=(8-ModifyBits);
            }
            Value<<=ModifyBits;

        }
        return (int)Value;
    }
}

Gasholder

Have you considered using the built-in java.util.BitSet? – Dumas

Yea tried that first. It was alot slower than this method. It's a server that needs to pack and unpack possibly millions of packets per second so need the fastest possible way to do it. I've done as much optimizations as I could with these two function. Just curious if there is a totally different route I haven't thought of in Java. – Gasholder

Yes. Write it in C and use JNI to interface it to Java. – Dumas

The program needs to be portable also. I'm not familiar with JNI. Can you tell me if the program can still be run on different os servers if I go that route? – Gasholder

I don't know much about JNI. Since the JNI code wouldn't be doing any I/O or interacting with the OS I would expect the differences to be very, very minor. You might get away with one source but would need to distribute a binary for each OS/Hardware combination. – Dumas

Yea that wouldn't work too well for the client. I don't really have any control over what OS they will use or may use in the future. – Gasholder

@JimGarrison - do you have any benchmarking to show that the speedup for a calculation this small will exceed the overheads of making a JNI method call? (To the OP - I think this is bad advice.) – Ilan

@StephenC - Not really. If you've done some benchmarking and think the JNI overhead would swamp the calculation cost then I will withdraw my suggestion. – Dumas

@JimGarrison - I haven't done any benchmarking myself but ... javamex.com/tutorials/jni/overhead.shtml and java.sun.com/docs/books/performance/1st_edition/html/… – Ilan

Answer 1

A totally different route would be to define static table of all possible combinations and perform a lookup instead of calculating results each time. I think thats how they do it in cryptography. array[i] x 3 should be much faster than numBits bitwise operations. It will occupy some heap though.

Stoltz

Will try and table some parts to see if there is a speed increase. – Gasholder

The two tables I added seemed to improve performance by about 7-10 percent. Can't find anything else in the code that is fit to table. 10 percent gain is still nice. – Gasholder