iframe-proxy | Sunbelt Computer Software

765 lines (683 loc) · 20.2 KB
 * chdemko\BitArray\BitArray class
 * @author    Christophe Demko <chdemko@gmail.com>
 * @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;
Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

BitArray.php

Latest commit

History

BitArray.php

File metadata and controls
