size = $size; $this->bits = new SplFixedArray(($this->size + 31) >> 3); } /** * Gets the size in bits. * * @return integer */ public function getSize() { return $this->size; } /** * Gets the size in bytes. * * @return integer */ public function getSizeInBytes() { return ($this->size + 7) >> 3; } /** * Ensures that the array has a minimum capacity. * * @param integer $size * @return void */ public function ensureCapacity($size) { if ($size > count($this->bits) << 5) { $this->bits->setSize(($size + 31) >> 5); } } /** * Gets a specific bit. * * @param integer $i * @return boolean */ public function get($i) { return ($this->bits[$i >> 5] & (1 << ($i & 0x1f))) !== 0; } /** * Sets a specific bit. * * @param integer $i * @return void */ public function set($i) { $this->bits[$i >> 5] = $this->bits[$i >> 5] | 1 << ($i & 0x1f); } /** * Flips a specific bit. * * @param integer $i * @return void */ public function flip($i) { $this->bits[$i >> 5] ^= 1 << ($i & 0x1f); } /** * Gets the next set bit position from a given position. * * @param integer $from * @return integer */ public function getNextSet($from) { if ($from >= $this->size) { return $this->size; } $bitsOffset = $from >> 5; $currentBits = $this->bits[$bitsOffset]; $bitsLength = count($this->bits); $currentBits &= ~((1 << ($from & 0x1f)) - 1); while ($currentBits === 0) { if (++$bitsOffset === $bitsLength) { return $this->size; } $currentBits = $this->bits[$bitsOffset]; } $result = ($bitsOffset << 5) + BitUtils::numberOfTrailingZeros($currentBits); return $result > $this->size ? $this->size : $result; } /** * Gets the next unset bit position from a given position. * * @param integer $from * @return integer */ public function getNextUnset($from) { if ($from >= $this->size) { return $this->size; } $bitsOffset = $from >> 5; $currentBits = ~$this->bits[$bitsOffset]; $bitsLength = count($this->bits); $currentBits &= ~((1 << ($from & 0x1f)) - 1); while ($currentBits === 0) { if (++$bitsOffset === $bitsLength) { return $this->size; } $currentBits = ~$this->bits[$bitsOffset]; } $result = ($bitsOffset << 5) + BitUtils::numberOfTrailingZeros($currentBits); return $result > $this->size ? $this->size : $result; } /** * Sets a bulk of bits. * * @param integer $i * @param integer $newBits * @return void */ public function setBulk($i, $newBits) { $this->bits[$i >> 5] = $newBits; } /** * Sets a range of bits. * * @param integer $start * @param integer $end * @return void * @throws Exception\InvalidArgumentException */ public function setRange($start, $end) { if ($end < $start) { throw new Exception\InvalidArgumentException('End must be greater or equal to start'); } if ($end === $start) { return; } $end--; $firstInt = $start >> 5; $lastInt = $end >> 5; for ($i = $firstInt; $i <= $lastInt; $i++) { $firstBit = $i > $firstInt ? 0 : $start & 0x1f; $lastBit = $i < $lastInt ? 31 : $end & 0x1f; if ($firstBit === 0 && $lastBit === 31) { $mask = 0x7fffffff; } else { $mask = 0; for ($j = $firstBit; $j < $lastBit; $j++) { $mask |= 1 << $j; } } $this->bits[$i] = $this->bits[$i] | $mask; } } /** * Clears the bit array, unsetting every bit. * * @return void */ public function clear() { $bitsLength = count($this->bits); for ($i = 0; $i < $bitsLength; $i++) { $this->bits[$i] = 0; } } /** * Checks if a range of bits is set or not set. * * @param integer $start * @param integer $end * @param integer $value * @return boolean * @throws Exception\InvalidArgumentException */ public function isRange($start, $end, $value) { if ($end < $start) { throw new Exception\InvalidArgumentException('End must be greater or equal to start'); } if ($end === $start) { return; } $end--; $firstInt = $start >> 5; $lastInt = $end >> 5; for ($i = $firstInt; $i <= $lastInt; $i++) { $firstBit = $i > $firstInt ? 0 : $start & 0x1f; $lastBit = $i < $lastInt ? 31 : $end & 0x1f; if ($firstBit === 0 && $lastBit === 31) { $mask = 0x7fffffff; } else { $mask = 0; for ($j = $firstBit; $j <= $lastBit; $j++) { $mask |= 1 << $j; } } if (($this->bits[$i] & $mask) !== ($value ? $mask : 0)) { return false; } } return true; } /** * Appends a bit to the array. * * @param boolean $bit * @return void */ public function appendBit($bit) { $this->ensureCapacity($this->size + 1); if ($bit) { $this->bits[$this->size >> 5] = $this->bits[$this->size >> 5] | (1 << ($this->size & 0x1f)); } $this->size++; } /** * Appends a number of bits (up to 32) to the array. * * @param integer $value * @param integer $numBits * @return void * @throws Exception\InvalidArgumentException */ public function appendBits($value, $numBits) { if ($numBits < 0 || $numBits > 32) { throw new Exception\InvalidArgumentException('Num bits must be between 0 and 32'); } $this->ensureCapacity($this->size + $numBits); for ($numBitsLeft = $numBits; $numBitsLeft > 0; $numBitsLeft--) { $this->appendBit((($value >> ($numBitsLeft - 1)) & 0x01) === 1); } } /** * Appends another bit array to this array. * * @param BitArray $other * @return void */ public function appendBitArray(self $other) { $otherSize = $other->getSize(); $this->ensureCapacity($this->size + $other->getSize()); for ($i = 0; $i < $otherSize; $i++) { $this->appendBit($other->get($i)); } } /** * Makes an exclusive-or comparision on the current bit array. * * @param BitArray $other * @return void * @throws Exception\InvalidArgumentException */ public function xorBits(self $other) { $bitsLength = count($this->bits); $otherBits = $other->getBitArray(); if ($bitsLength !== count($otherBits)) { throw new Exception\InvalidArgumentException('Sizes don\'t match'); } for ($i = 0; $i < $bitsLength; $i++) { $this->bits[$i] = $this->bits[$i] ^ $otherBits[$i]; } } /** * Converts the bit array to a byte array. * * @param integer $bitOffset * @param integer $numBytes * @return SplFixedArray */ public function toBytes($bitOffset, $numBytes) { $bytes = new SplFixedArray($numBytes); for ($i = 0; $i < $numBytes; $i++) { $byte = 0; for ($j = 0; $j < 8; $j++) { if ($this->get($bitOffset)) { $byte |= 1 << (7 - $j); } $bitOffset++; } $bytes[$i] = $byte; } return $bytes; } /** * Gets the internal bit array. * * @return SplFixedArray */ public function getBitArray() { return $this->bits; } /** * Reverses the array. * * @return void */ public function reverse() { $newBits = new SplFixedArray(count($this->bits)); for ($i = 0; $i < $this->size; $i++) { if ($this->get($this->size - $i - 1)) { $newBits[$i >> 5] = $newBits[$i >> 5] | (1 << ($i & 0x1f)); } } $this->bits = newBits; } /** * Returns a string representation of the bit array. * * @return string */ public function __toString() { $result = ''; for ($i = 0; $i < $this->size; $i++) { if (($i & 0x07) === 0) { $result .= ' '; } $result .= $this->get($i) ? 'X' : '.'; } return $result; } }