<?php

/**

* chdemko\BitArray\BitArray class

*

* @author Christophe Demko <[email protected]>

* @copyright Copyright (C) 2012-2024 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;

}

}