net.algart.arrays.PackedBitArraysPer8

public class PackedBitArraysPer8 extends Object

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 2³⁴-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 Type

Method

Description

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.

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 to reverseBitOrder(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 of PackedBitArrays.

static long[]

toLongArray(byte[] byteArray)

Packs byte array to long[], so that the bits, stored in the result array according the rules of PackedBitArrays class, will be identical to bits stored in the source array according the rules of this class.

static long[]

toLongArray(ByteBuffer byteBuffer)

Exact analog of toLongArray(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.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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:
  
  reverseBitsOrderInEachByte(byte[], int, int)
- 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:
  
  reverseBitsOrderInEachByte(byte[], int, int)
- 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 of PackedBitArrays 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
  
  public static long[] toLongArray(ByteBuffer byteBuffer)
  Exact analog of toLongArray(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 of PackedBitArrays. 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 of PackedBitArrays 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.

Class PackedBitArraysPer8

Method Summary

Methods inherited from class java.lang.Object

Method Details

unpackedLength

packedLength

getBit

setBit

getBits

getBitInReverseOrder

setBitInReverseOrder

getBitsInReverseOrder

toLongArray

toLongArray

toByteArray

copyBits

packBits

unpackBits

fillBits

cardinality

reverseBitsOrderInEachByte

reverseBitsOrderInEachByte