Wednesday, July 09, 2008

Byte padding

Byte padding / stuffing:

If you have a byte array of length l, how can you pad it by any number say x?

Normal obvious way is below.
if (l%x == 0) return 0 
else return (x - (l%x))

However, if x is a power of 2, a faster approach is to get the two's complement (2C) of length l and capture the least significant bits.

i.e.
(l*-1)&(x-1)

l=5, x=4

00000101 //5
11111011 //-5
00000011 //4-1=3
00000011 //-5&3 = 3

So, for l=5 you need 3 bytes to pad.

l=7, x=4

00000111 //7
11111001 //-7
00000011 //4-1=3
00000001 //-7&3 = 1

So, for l=7 you need 1 bytes to pad.

It only works for x which is a power of 2. For other x, you have to go by the normal obvious method.

Check if  x is a power of 2 this way:
bool isPowerOf2(x):
    return x != 0 && (x & (x-1)) == 0

[Hat tip to JvE]

No comments:

Post a Comment