Class PackedBitArraysPer8
Operations with bit arrays packed into byte[] Java arrays.
This is a reduced analog of PackedBitArrays
class, using byte values
for packing bits instead of long values AlgART bit arrays do not use this class,
but it can be useful in external modules, where bits are packed into bytes.
The maximal length of bit arrays supported by this class is 234-8. All indexes and lengths passed to methods of this class must not exceed this value.
In all methods of this class, it's supposed that the bit #k in a packed byte[] array is the bit #(k%8) in the byte element array[k/8]. In other words, the bit #k (false or true value) can be extracted by the following operator:
(array[k >>> 3] & (1 << (k & 7))) != 0
and can be set or cleared by the following operators:
if (newValue) // we need to set bit #k to 1 array[k >>> 3] |= 1 << (k & 7); else // we need to clear bit #k to 0 array[k >>> 3] &= ~(1 << (k & 7));
You may use getBit(byte[], long)
and setBit(byte[], long, boolean)
, implementing
the equivalent code.
If any method of this class modifies some portion of an element of a packed byte[] Java array, i.e. modifies less than all 8 its bits, then all accesses to this byte element are performed inside a single synchronized block, using the following instruction:
synchronized (array) { // accessing to some element array[k] }
(See an example in comments to setBit(byte[], long, boolean)
method.)
If all 8 bits of the element are written, or if the bits are read only, then no synchronization is performed.
Such behavior allows to simultaneously work with non-overlapping fragments of a packed bit array
from several threads (different fragments for different threads), as if it would be a usual Java array.
This class cannot be instantiated.
- Author:
- Daniel Alievsky
-
Method Summary
Modifier and TypeMethodDescriptionstatic long
cardinality
(byte[] src, long fromIndex, long toIndex) Returns the number of high bits (1) in the given fragment of the given packed bit array.static void
copyBits
(byte[] dest, long destPos, byte[] src, long srcPos, long count) Copies count bits, packed in src array, starting from the bit #srcPos, to packed dest array, starting from the bit #destPos.static void
fillBits
(byte[] dest, long destPos, long count, boolean value) Fills count bits in the packed dest array, starting from the bit #destPos, by the specified value.static boolean
getBit
(byte[] src, long index) Returns the bit #index in the packed src bit array.static boolean
getBitInReverseOrder
(byte[] src, long index) Returns the bit #index in the packed src bit array for a case, when the bits are packed in each byte in the reverse order: highest bit first, lowest bit last.static long
getBits
(byte[] src, long srcPos, int count) Returns the sequence of count bits (maximum 64 bits), starting from the bit #srcPos, in the packed src bit array.static long
getBitsInReverseOrder
(byte[] src, long srcPos, int count) Returns the sequence of count bits (maximum 64 bits), starting from the bit #srcPos, in the packed src bit array for a case, when the bits are packed in each byte in the reverse order: highest bit first, lowest bit last.static void
packBits
(byte[] dest, long destPos, boolean[] src, int srcPos, int count) Copies count bits from src array, starting from the element #srcPos, to packed dest array, starting from the bit #destPos.static long
packedLength
(long unpackedLength) Returns (unpackedLength + 7) >>> 3: the minimal number of byte values allowing to store unpackedLength bits.static void
reverseBitsOrderInEachByte
(byte[] bytes) Equivalent toreverseBitOrder
(bytes, 0, bytes.length).static void
reverseBitsOrderInEachByte
(byte[] bytes, int pos, int count) Inverts bits order in all bytes in the specified array.static void
setBit
(byte[] dest, long index, boolean value) Sets the bit #index in the packed dest bit array.static void
setBitInReverseOrder
(byte[] dest, long index, boolean value) Sets the bit #index in the packed dest bit array for a case, when the bits are packed in each byte in the reverse order: highest bit first, lowest bit last.static byte[]
toByteArray
(long[] packedBitArray, long packedBitArrayLength) Unpacks long[] array to byte[], so that the bits, stored in the result array according the rules of this class, will be identical to bits stored in the source array according the rules ofPackedBitArrays
.static long[]
toLongArray
(byte[] byteArray) Packs byte array to long[], so that the bits, stored in the result array according the rules ofPackedBitArrays
class, will be identical to bits stored in the source array according the rules of this class.static long[]
toLongArray
(ByteBuffer byteBuffer) Exact analog oftoLongArray(byte[])
method, but the original bytes are stored in ByteBuffer instead of byte[] array.static void
unpackBits
(boolean[] dest, int destPos, byte[] src, long srcPos, int count) Copies count bits, packed in src array, starting from the bit #srcPos, to dest boolean array, starting from the element #destPos.static long
unpackedLength
(byte[] array) Returns ((long) array.length) << 3: the maximal number of bits that can be stored in the specified array.
-
Method Details
-
unpackedLength
public static long unpackedLength(byte[] array) Returns ((long) array.length) << 3: the maximal number of bits that can be stored in the specified array.- Parameters:
array
- byte[] array.- Returns:
- 8 * (long) array.length
- Throws:
NullPointerException
- if the argument is null.
-
packedLength
public static long packedLength(long unpackedLength) Returns (unpackedLength + 7) >>> 3: the minimal number of byte values allowing to store unpackedLength bits.- Parameters:
unpackedLength
- the number of bits (the length of bit array).- Returns:
- (unpackedLength + 7) >>> 3 (the length of corresponding byte[] array).
-
getBit
public static boolean getBit(byte[] src, long index) Returns the bit #index in the packed src bit array. Equivalent to the following expression:(src[(int)(index >>> 3)] & (1 << (index & 7))) != 0;
- Parameters:
src
- the source array (bits are packed in byte values).index
- index of the returned bit.- Returns:
- the bit at the specified index.
- Throws:
NullPointerException
- if src is null.IndexOutOfBoundsException
- if this method cause access of data outside array bounds.
-
setBit
public static void setBit(byte[] dest, long index, boolean value) Sets the bit #index in the packed dest bit array. Equivalent to the following operators:synchronized (dest) { if (value) dest[(int)(index >>> 3)] |= 1 << (index & 7); else dest[(int)(index >>> 3)] &= ~(1 << (index & 7)); }
- Parameters:
dest
- the destination array (bits are packed in long values).index
- index of the written bit.value
- new bit value.- Throws:
NullPointerException
- if dest is null.IndexOutOfBoundsException
- if this method cause access of data outside array bounds.
-
getBits
public static long getBits(byte[] src, long srcPos, int count) Returns the sequence of count bits (maximum 64 bits), starting from the bit #srcPos, in the packed src bit array.More precisely, the bit #(srcPos+k) will be returned in the bit #k of the returned long value R: the first bit #srcPos will be equal to R&1, the following bit #(srcPos+1) will be equal to (R>>1)&1, etc. If count=0, the result is 0.
The same result can be calculated using the following loop:
long result = 0; for (int k = 0; k < count; k++) { final long bit =
PackedBitArraysPer8.getBit
(src, srcPos + k) ? 1L : 0L; result |= bit << k; }But this function works significantly faster, if count is greater than 1.
Note: unlike the loop listed above, this function does not throw exception for too large indexes of bits after the end of the array (≥8*src.length); instead, all bits outside the array are considered zero. (But negative indexes are not allowed.)
- Parameters:
src
- the source array (bits are packed in byte values).srcPos
- position of the first bit read in the source array.count
- the number of bits to be unpacked (must be >=0 and <64).- Returns:
- the sequence of count bits.
- Throws:
NullPointerException
- if src argument is null.IndexOutOfBoundsException
- if srcPos < 0.IllegalArgumentException
- if count < 0 or count > 64.
-
getBitInReverseOrder
public static boolean getBitInReverseOrder(byte[] src, long index) Returns the bit #index in the packed src bit array for a case, when the bits are packed in each byte in the reverse order: highest bit first, lowest bit last. Equivalent to the following expression:(src[(int)(index >>> 3)] & (1 << (7 - (index & 7)))) != 0;
This bit order is used, for example, in TIFF format when storing binary images or image with less than 8 bits per channel.
- Parameters:
src
- the source array (bits are packed in byte values in reverse order 76543210).index
- index of the returned bit.- Returns:
- the bit at the specified index.
- Throws:
NullPointerException
- if src is null.IndexOutOfBoundsException
- if this method cause access of data outside array bounds.- See Also:
-
setBitInReverseOrder
public static void setBitInReverseOrder(byte[] dest, long index, boolean value) Sets the bit #index in the packed dest bit array for a case, when the bits are packed in each byte in the reverse order: highest bit first, lowest bit last. Equivalent to the following operators:synchronized (dest) { final int bitIndex = 7 - ((int) index & 7); if (value) dest[(int)(index >>> 3)] |= (1 << bitIndex); else dest[(int)(index >>> 3)] &= ~(1 << bitIndex); }
- Parameters:
dest
- the destination array (bits are packed in long values).index
- index of the written bit.value
- new bit value.- Throws:
NullPointerException
- if dest is null.IndexOutOfBoundsException
- if this method cause access of data outside array bounds.- See Also:
-
getBitsInReverseOrder
public static long getBitsInReverseOrder(byte[] src, long srcPos, int count) Returns the sequence of count bits (maximum 64 bits), starting from the bit #srcPos, in the packed src bit array for a case, when the bits are packed in each byte in the reverse order: highest bit first, lowest bit last.More precisely, the bit #(srcPos+k), that can be read by the call
getBitInReverseOrder
(src, srcPos+k), will be returned in the bit #(count-1-k) (in direct order) of the returned long value R, i.e. it is equal to (R>>(count-1-k))&1. If count=0, the result is 0.The same result can be calculated using the following loop:
long result = 0; for (int k = 0; k < count; k++) { final long bit =
PackedBitArraysPer8.getBitInReverseOrder
(src, srcPos + k) ? 1L : 0L; result |= bit << (count - 1 - k); }But this function works significantly faster, if count is greater than 1.
Note: unlike the loop listed above, this function does not throw exception for too large indexes of bits after the end of the array (≥8*src.length); instead, all bits outside the array are considered zero. (But negative indexes are not allowed.)
This bit order is used, for example, in TIFF format when storing binary images or image with less than 8 bits per channel.
- Parameters:
src
- the source array (bits are packed in byte values).srcPos
- position of the first bit read in the source array.count
- the number of bits to be unpacked (must be >=0 and <64).- Returns:
- the sequence of count bits.
- Throws:
NullPointerException
- if src argument is null.IndexOutOfBoundsException
- if srcPos < 0.IllegalArgumentException
- if count < 0 or count > 64.
-
toLongArray
public static long[] toLongArray(byte[] byteArray) Packs byte array to long[], so that the bits, stored in the result array according the rules ofPackedBitArrays
class, will be identical to bits stored in the source array according the rules of this class.The length of created array will be (byteArray.length + 7) / 8. The bytes of the returned long values are just the bytes of the source array, packed in little-endian order. If byteArray.length is not divisible by 8, the unused high bytes of the last long element will be zero.
- Parameters:
byteArray
- byte array, supposedly storing packed bits according the rules of this class.- Returns:
- long array, storing the same packed bits according the rules of
PackedBitArrays
. - Throws:
NullPointerException
- if the argument is null.
-
toLongArray
Exact analog oftoLongArray(byte[])
method, but the original bytes are stored in ByteBuffer instead of byte[] array. If b is some byte[] array, then the following calls are equivalent:toLongArray
(ByteBuffer.wrap(b))toLongArray
(b)This method works with a duplicate of the specified ByteBuffer and, so, does not modify its settings like position and limit. Note that the byte order in the passes ByteBuffer is ignored: the bytes are always packed into long values in little-endian order.
- Parameters:
byteBuffer
- bytes, supposedly storing packed bits according the rules of this class.- Returns:
- long array, storing the same packed bits according the rules of
PackedBitArrays
. - Throws:
NullPointerException
- if the argument is null.
-
toByteArray
public static byte[] toByteArray(long[] packedBitArray, long packedBitArrayLength) Unpacks long[] array to byte[], so that the bits, stored in the result array according the rules of this class, will be identical to bits stored in the source array according the rules ofPackedBitArrays
. The actual length of the passed bit array should be specified in packedBitArrayLength argument.The length of created array will be
PackedBitArraysPer8.packedLength
(packedBitArrayLength). The bytes of the returned array are just the bytes of the source long values, packed in little-endian order.- Parameters:
packedBitArray
- long> array, supposedly storing packed bits according the rules ofPackedBitArrays
class.packedBitArrayLength
- the number of packed bits.- Returns:
- byte[] array, storing the same packed bits according the rules of this class.
- Throws:
IllegalArgumentException
- if packedBitArrayLength is negative or too large: greater than packedBitArray.length*64 or 2^34−1 (in the latter case, the required length of the returned array exceeds Java limit 2^31).
-
copyBits
public static void copyBits(byte[] dest, long destPos, byte[] src, long srcPos, long count) Copies count bits, packed in src array, starting from the bit #srcPos, to packed dest array, starting from the bit #destPos.This method works correctly even if src == dest and the copied areas overlap, i.e. if Math.abs(destPos - srcPos) < count. More precisely, in this case the copying is performed as if the bits at positions srcPos..srcPos+count-1 were first unpacked to a temporary boolean[] array with count elements and then the contents of the temporary array were packed into positions destPos..destPos+count-1.
- Parameters:
dest
- the destination array (bits are packed in byte values).destPos
- position of the first bit written in the destination array.src
- the source array (bits are packed in byte values).srcPos
- position of the first bit read in the source array.count
- the number of bits to be copied (must be >=0).- Throws:
NullPointerException
- if either src or dest is null.IndexOutOfBoundsException
- if copying would cause access of data outside array bounds.
-
packBits
public static void packBits(byte[] dest, long destPos, boolean[] src, int srcPos, int count) Copies count bits from src array, starting from the element #srcPos, to packed dest array, starting from the bit #destPos.- Parameters:
dest
- the destination array (bits are packed in byte values).destPos
- position of the first bit written in the destination array.src
- the source array (unpacked boolean values).srcPos
- position of the first bit read in the source array.count
- the number of bits to be packed (must be >=0).- Throws:
NullPointerException
- if either src or dest is null.IndexOutOfBoundsException
- if copying would cause access of data outside array bounds.
-
unpackBits
public static void unpackBits(boolean[] dest, int destPos, byte[] src, long srcPos, int count) Copies count bits, packed in src array, starting from the bit #srcPos, to dest boolean array, starting from the element #destPos.- Parameters:
dest
- the destination array (unpacked boolean values).destPos
- position of the first bit written in the destination array.src
- the source array (bits are packed in byte values).srcPos
- position of the first bit read in the source array.count
- the number of bits to be unpacked (must be >=0).- Throws:
NullPointerException
- if either src or dest is null.IndexOutOfBoundsException
- if copying would cause access of data outside array bounds.
-
fillBits
public static void fillBits(byte[] dest, long destPos, long count, boolean value) Fills count bits in the packed dest array, starting from the bit #destPos, by the specified value. Be careful: the second int argument in this method is the number of filled element, but not the end filled index as in java.util.Arrays.fill methods.- Parameters:
dest
- the destination array (bits are packed in byte values).destPos
- position of the first bit written in the destination array.count
- the number of bits to be filled (must be >=0).value
- new value of all filled bits (false means the bit 0, true means the bit 1).- Throws:
NullPointerException
- if dest is null.IndexOutOfBoundsException
- if filling would cause access of data outside array bounds.
-
cardinality
public static long cardinality(byte[] src, long fromIndex, long toIndex) Returns the number of high bits (1) in the given fragment of the given packed bit array.- Parameters:
src
- the source packed bit array.fromIndex
- the initial checked bit index in array, inclusive.toIndex
- the end checked bit index in array, exclusive.- Returns:
- the number of high bits (1) in the given fragment of the given packed bit array.
- Throws:
NullPointerException
- if the src argument is null.IndexOutOfBoundsException
- if fromIndex or toIndex are negative, if toIndex is greater than src.length*8, or if fromIndex is greater than startIndex
-
reverseBitsOrderInEachByte
public static void reverseBitsOrderInEachByte(byte[] bytes) Equivalent toreverseBitOrder
(bytes, 0, bytes.length).- Parameters:
bytes
- array to be processed.- Throws:
NullPointerException
- if bytes is null.
-
reverseBitsOrderInEachByte
public static void reverseBitsOrderInEachByte(byte[] bytes, int pos, int count) Inverts bits order in all bytes in the specified array.Equivalent to the following loop:
for (int i = 0; i < count; i++) { bytes[pos + i] = (byte) (
Integer.reverse
(bytes[pos + i] & 0xFF) >>> 24);This method can be useful if you have an array of bits, packed into bytes in reverse order: (b>>7)&1, (b>>6)&1, (b>>5)&1, (b>>4)&1, (b>>3)&1, (b>>2)&1, (b>>1)&1, b&1 (highest bits first) for each byte b. You should reverse the bit order in such an array before using other methods of this class or, for simple cases, use the methods
getBitInReverseOrder(byte[], long)
andsetBitInReverseOrder(byte[], long, boolean)
.- Parameters:
bytes
- array to be processed.- Throws:
NullPointerException
- if bytes is null.IllegalArgumentException
- if count is negative.IndexOutOfBoundsException
- if processing would cause access of data outside the array.
-