src/BitArray/BitArray.php
<?php
/**
* chdemko\BitArray\BitArray class
*
* @author Christophe Demko <chdemko@gmail.com>
* @copyright Copyright (C) 2012-2023 Christophe Demko. All rights reserved.
*
* @license BSD 3-Clause License
*
* This file is part of the php-bitarray package https://github.com/chdemko/php-bitarray
*/
// Declare chdemko\BitArray namespace
namespace chdemko\BitArray;
/**
* Array of bits
*
* @package BitArray
*
* @property-read integer $count The number of bits set to true
* @property-read integer $size The number of bits
*
* @since 1.0.0
*/
class BitArray implements \ArrayAccess, \Countable, \IteratorAggregate, \JsonSerializable
{
/**
* @var integer[] Number of bits for each value between 0 and 255
*/
private static $count = array(
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
);
/**
* @var integer[] Mask for restricting complements
*/
private static $restrict = array(255, 1, 3, 7, 15, 31, 63, 127);
/**
* @var string Underlying data
*
* @since 1.0.0
*/
private $data;
/**
* @var integer Size of the bit array
*
* @since 1.0.0
*/
private $size;
/**
* Create a new bit array of the given size
*
* @param integer $size The BitArray size
* @param boolean $default The default value for bits
*
* @since 1.0.0
*/
protected function __construct($size = 0, $default = false)
{
$this->size = (int) $size;
if ($default) {
$this->data = str_repeat(chr(255), (int) ceil($this->size / 8));
$this->restrict();
} else {
$this->data = str_repeat(chr(0), (int) ceil($this->size / 8));
}
}
/**
* Remove useless bits for simplifying count operation.
*
* @return BitArray $this for chaining
*
* @since 1.2.0
*/
protected function restrict()
{
$length = strlen($this->data);
if ($length > 0) {
$this->data[$length - 1] = chr(ord($this->data[$length - 1]) & self::$restrict[$this->size % 8]);
}
return $this;
}
/**
* Clone a BitArray
*
* @return void
*
* @since 1.0.0
*/
public function __clone()
{
$this->data = str_repeat($this->data, 1);
}
/**
* Convert the object to a string
*
* @return string String representation of this object
*
* @since 1.0.0
*/
public function __toString()
{
$string = str_repeat('0', $this->size);
for ($offset = 0; $offset < $this->size; $offset++) {
if (ord($this->data[(int) ($offset / 8)]) & (1 << $offset % 8)) {
$string[$offset] = '1';
}
}
return $string;
}
/**
* Magic get method
*
* @param string $property The property
*
* @throws RuntimeException If the property does not exist
*
* @return mixed The value associated to the property
*
* @since 1.0.0
*/
public function __get($property)
{
switch ($property) {
case 'size':
return $this->size;
case 'count':
return $this->count();
default:
throw new \RuntimeException('Undefined property');
}
}
/**
* Test the existence of an index
*
* @param integer $offset The offset
*
* @return boolean The truth value
*
* @since 1.0.0
*/
public function offsetExists($offset): bool
{
return is_int($offset) && $offset >= 0 && $offset < $this->size;
}
/**
* Get the truth value for an index
*
* @param integer $offset The offset
*
* @return boolean The truth value
*
* @throws OutOfRangeException Argument index must be an positive integer lesser than the size
*
* @since 1.0.0
*/
public function offsetGet($offset): bool
{
if ($this->offsetExists($offset)) {
return (bool) (ord($this->data[(int) ($offset / 8)]) & (1 << $offset % 8));
} else {
throw new \OutOfRangeException('Argument offset must be a positive integer lesser than the size');
}
}
/**
* Set the truth value for an index
*
* @param integer $offset The offset
* @param boolean $value The truth value
*
* @return void
*
* @throws OutOfRangeException Argument index must be an positive integer lesser than the size
*
* @since 1.0.0
*/
public function offsetSet($offset, $value): void
{
if ($this->offsetExists($offset)) {
$index = (int) ($offset / 8);
if ($value) {
$this->data[$index] = chr(ord($this->data[$index]) | (1 << $offset % 8));
} else {
$this->data[$index] = chr(ord($this->data[$index]) & ~(1 << $offset % 8));
}
} else {
throw new \OutOfRangeException('Argument index must be a positive integer lesser than the size');
}
}
/**
* Unset the existence of an index
*
* @param integer $offset The index
*
* @return void
*
* @throws RuntimeException Values cannot be unset
*
* @since 1.0.0
*/
public function offsetUnset($offset): void
{
throw new \RuntimeException('Values cannot be unset');
}
/**
* Return the number of true bits
*
* @return integer The number of true bits
*
* @since 1.0.0
*/
public function count(): int
{
$count = 0;
for ($index = 0, $length = strlen($this->data); $index < $length; $index++) {
$count += self::$count[ord($this->data[$index])];
}
return $count;
}
/**
* Transform the object to an array
*
* @return array Array of values
*
* @since 1.1.0
*/
public function toArray()
{
$array = array();
for ($index = 0; $index < $this->size; $index++) {
$array[] = (bool) (ord($this->data[(int) ($index / 8)]) & (1 << $index % 8));
}
return $array;
}
/**
* Serialize the object
*
* @return array Array of values
*
* @since 1.0.0
*/
public function jsonSerialize(): array
{
return $this->toArray();
}
/**
* Get an iterator
*
* @return Iterator Iterator
*
* @since 1.0.0
*/
public function getIterator(): Iterator
{
return new Iterator($this);
}
/**
* Return the size
*
* @return integer The size
*
* @since 1.0.0
*/
public function size()
{
return $this->size;
}
/**
* Copy bits directly from a BitArray
*
* @param BitArray $bits A BitArray to copy
* @param int $index Starting index for destination
* @param int $offset Starting index for copying
* @param int $size Copy size
*
* @return BitArray This object for chaining
*
* @throws OutOfRangeException Argument index must be an positive integer lesser than the size
*
* @since 1.1.0
*/
public function directCopy(BitArray $bits, $index = 0, $offset = 0, $size = 0)
{
if ($offset > $index) {
for ($i = 0; $i < $size; $i++) {
$this[$i + $index] = $bits[$i + $offset];
}
} else {
for ($i = $size - 1; $i >= 0; $i--) {
$this[$i + $index] = $bits[$i + $offset];
}
}
return $this;
}
/**
* Copy bits from a BitArray
*
* * if index is non-negative, the index parameter is used as it is,
* keeping its real value between 0 and size-1;
* * if index is negative, the index parameter starts from the end,
* keeping its real value between 0 and size-1.
*
* * if offset is non-negative, the offset parameter is used as it is,
* keeping its positive value between 0 and size-1;
* * if offset is negative, the offset parameter starts from the end,
* keeping its real value between 0 and size-1.
*
* * if size is given and is positive, then the copy will copy size elements.
* * if the bits argument is shorter than the size, then only the available elements will be copied.
* * if size is given and is negative, then the copy starts from the end.
* * if size is omitted, then the copy will have everything from offset up
* until the end of the bits argument.
*
* @param BitArray $bits A BitArray to copy
* @param int $index Starting index for destination.
* @param int $offset Starting index for copying.
* @param mixed $size Copy size.
*
* @return BitArray This object for chaining
*
* @since 1.1.0
*/
public function copy(BitArray $bits, $index = 0, $offset = 0, $size = null)
{
$index = $this->getRealOffset($index);
$offset = $bits->getRealOffset($offset);
$size = $bits->getRealSize($offset, $size);
if ($size > $this->size - $index) {
$size = $this->size - $index;
}
return $this->directCopy($bits, $index, $offset, $size);
}
/**
* Get the real offset using a positive or negative offset
*
* * If offset is non-negative, the offset parameter is used as it is,
* keeping its real value between 0 and size-1.
* * if offset is negative, the offset parameter starts from the end,
* keeping its real value between 0 and size-1.
*
* @param int $offset The offset
*
* @return integer The real offset
*
* @since 1.1.0
*/
protected function getRealOffset($offset)
{
$offset = (int) $offset;
if ($offset < 0) {
// Start from the end
$offset = $this->size + $offset;
if ($offset < 0) {
$offset = 0;
}
} elseif ($offset > $this->size) {
$offset = $this->size;
}
return $offset;
}
/**
* Get the real offset using a positive or negative offset
*
* * if size is given and is positive, then the real size will be between 0 and the current size-1.
* * if size is given and is negative, then the real size starts from the end.
* * if size is omitted, then the size goes until the end of the BitArray.
*
* @param int $offset The real offset.
* @param mixed $size The size
*
* @return integer The real size
*
* @since 1.1.0
*/
protected function getRealSize($offset, $size)
{
if ($size === null) {
$size = $this->size - $offset;
} else {
$size = (int) $size;
if ($size < 0) {
$size = $this->size + $size - $offset;
if ($size < 0) {
$size = 0;
}
} elseif ($size > $this->size - $offset) {
$size = $this->size - $offset;
}
}
return $size;
}
/**
* Create a new BitArray from an integer
*
* @param integer $size Size of the BitArray
* @param boolean $default The default value for bits
*
* @return BitArray A new BitArray
*
* @since 1.0.0
*/
public static function fromInteger($size, $default = false)
{
return new BitArray($size, (bool) $default);
}
/**
* Create a new BitArray from a sequence of bits.
*
* @param integer $size Size of the BitArray
* @param integer $values The values for the bits
*
* @return BitArray A new BitArray
*
* @since 1.2.0
*/
public static function fromDecimal($size, $values = 0)
{
$php_bit_size = PHP_INT_SIZE * 8;
$size = min((int) $size, $php_bit_size);
$values <<= ($php_bit_size - $size);
$bits = new BitArray($size);
for ($i = 0; $i < ceil($size / 8); $i++) {
$value = ($values & (0xff << ($php_bit_size - 8))) >> ($php_bit_size - 8);
$reverse = 0;
for ($j = 0; $j < 8; $j++) {
if ($value & (1 << $j)) {
$reverse |= 1 << (7 - $j);
}
}
$bits->data[$i] = chr($reverse);
$values <<= 8;
}
return $bits;
}
/**
* Create a new BitArray from a traversable
*
* @param mixed $traversable A traversable and countable
*
* @return BitArray A new BitArray
*
* @since 1.0.0
*/
public static function fromTraversable($traversable)
{
$bits = new BitArray(count($traversable));
$offset = 0;
$ord = 0;
foreach ($traversable as $value) {
if ($value) {
$ord |= 1 << $offset % 8;
}
if ($offset % 8 === 7) {
$bits->data[(int) ($offset / 8)] = chr($ord);
$ord = 0;
}
$offset++;
}
if ($offset % 8 !== 0) {
$bits->data[(int) ($offset / 8)] = chr($ord);
}
return $bits;
}
/**
* Create a new BitArray from a bit string
*
* @param string $string A bit string
*
* @return BitArray A new BitArray
*
* @since 1.0.0
*/
public static function fromString($string)
{
$bits = new BitArray(strlen($string));
$ord = 0;
for ($offset = 0; $offset < $bits->size; $offset++) {
if ($string[$offset] !== '0') {
$ord |= 1 << $offset % 8;
}
if ($offset % 8 === 7) {
$bits->data[(int) ($offset / 8)] = chr($ord);
$ord = 0;
}
}
if ($offset % 8 !== 0) {
$bits->data[(int) ($offset / 8)] = chr($ord);
}
return $bits;
}
/**
* Create a new BitArray from json
*
* @param string $json A json encoded value
*
* @return BitArray A new BitArray
*
* @since 1.0.0
*/
public static function fromJson($json)
{
return self::fromTraversable(json_decode($json));
}
/**
* Create a new BitArray using a slice
*
* * if offset is non-negative, the slice will start at that offset in the bits argument.
* * if offset is negative, the slice will start from the end of the bits argument.
*
* * if size is given and is positive, then the slice will have up to that many elements in it.
* * if the bits argument is shorter than the size, then only the available elements will be present.
* * if size is given and is negative,
* then the slice will stop that many elements from the end of the bits argument.
* * if size is omitted,
* then the slice will have everything from offset up until the end of the bits argument.
*
* @param BitArray $bits A BitArray to get the slice
* @param int $offset The offset
* @param mixed $size The size
*
* @return BitArray A new BitArray
*
* @since 1.1.0
*/
public static function fromSlice(BitArray $bits, $offset = 0, $size = null)
{
$offset = $bits->getRealOffset($offset);
$size = $bits->getRealSize($offset, $size);
$slice = new BitArray($size);
return $slice->directCopy($bits, 0, $offset, $size);
}
/**
* Create a new BitArray using the concat operation
*
* @param BitArray $bits1 A BitArray
* @param BitArray $bits2 A BitArray
*
* @return BitArray A new BitArray
*
* @since 1.1.0
*/
public static function fromConcat(BitArray $bits1, BitArray $bits2)
{
$size = $bits1->size + $bits2->size;
$concat = new BitArray($size);
$concat->directCopy($bits1, 0, 0, $bits1->size);
$concat->directCopy($bits2, $bits1->size, 0, $bits2->size);
return $concat;
}
/**
* Complement the bit array
*
* @return BitArray This object for chaining
*
* @since 1.0.0
*/
public function applyComplement()
{
$length = strlen($this->data);
for ($index = 0; $index < $length; $index++) {
$this->data[$index] = chr(~ ord($this->data[$index]));
}
return $this->restrict();
}
/**
* Or with an another bit array
*
* @param BitArray $bits A bit array
*
* @return BitArray This object for chaining
*
* @throws InvalidArgumentException Argument must be of equal size
*
* @since 1.0.0
*/
public function applyOr(BitArray $bits)
{
if ($this->size == $bits->size) {
$length = strlen($this->data);
for ($index = 0; $index < $length; $index++) {
$this->data[$index] = chr(ord($this->data[$index]) | ord($bits->data[$index]));
}
return $this;
} else {
throw new \InvalidArgumentException('Argument must be of equal size');
}
}
/**
* And with an another bit array
*
* @param BitArray $bits A bit array
*
* @return BitArray This object for chaining
*
* @throws InvalidArgumentException Argument must be of equal size
*
* @since 1.0.0
*/
public function applyAnd(BitArray $bits)
{
if ($this->size == $bits->size) {
$length = strlen($this->data);
for ($index = 0; $index < $length; $index++) {
$this->data[$index] = chr(ord($this->data[$index]) & ord($bits->data[$index]));
}
return $this;
} else {
throw new \InvalidArgumentException('Argument must be of equal size');
}
}
/**
* Xor with an another bit array
*
* @param BitArray $bits A bit array
*
* @return BitArray This object for chaining
*
* @throws InvalidArgumentException Argument must be of equal size
*
* @since 1.0.0
*/
public function applyXor(BitArray $bits)
{
if ($this->size == $bits->size) {
$length = strlen($this->data);
for ($index = 0; $index < $length; $index++) {
$this->data[$index] = chr(ord($this->data[$index]) ^ ord($bits->data[$index]));
}
return $this;
} else {
throw new \InvalidArgumentException('Argument must be of equal size');
}
}
/**
* Shift a bit array.
*
* Negative value means the shifting is done right to left
* while positive value means the shifting is done left to right.
*
* @param int $size Size to shift.
*
* @param boolean $value Value to shift
*
* @return BitArray $this for chaining
*
* @since 1.2.0
*/
public function shift($size = 1, $value = false)
{
$size = (int) $size;
if ($size > 0) {
$min = min($this->size, $size);
for ($i = $this->size - 1; $i >= $min; $i--) {
$this[$i] = $this[$i - $min];
}
for ($i = 0; $i < $min; $i++) {
$this[$i] = $value;
}
} else {
$min = min($this->size, -$size);
for ($i = 0; $i < $this->size - $min; $i++) {
$this[$i] = $this[$i + $min];
}
for ($i = $this->size - $min; $i < $this->size; $i++) {
$this[$i] = $value;
}
}
return $this;
}
}