0xDEADBEEF

RSS odkazy english edition

IntArray.php

6. 6. 2013

Unboxed int array in PHP

// advanced bit-twiddling

abstract class AbstractIntArray {
  protected $length;
  protected $data;
  protected $typeSize;

  function __construct($length) {
    $this->length = $length;
    $this->data = str_repeat("\0", $length * $this->typeSize);
  }

  protected function checkIndex($idx) {
    if (!is_int($idx))
      throw new \InvalidArgumentException("index must be integer value");

    if ($idx < 0 || $idx >= $this->length)
      throw new \OutOfRangeException("index out of range");
  }

  protected function checkValue($val) {
    if (!is_int($val))
      throw new \InvalidArgumentException("Value must be integer.");
  }

  function getData() {
    return $this->data;
  }
}


/** store unsigned bytes */
final class ByteArray extends AbstractIntArray {
  protected $typeSize = 1;

  function get($idx) {
    $this->checkIndex($idx);

    return ord($this->data[$idx]);
  }

  function put($idx, $val) {
    $this->checkIndex($idx);
    $this->checkValue($val);

    if ($val < 0 || $val > 255)
      throw new \OutOfRangeException();

    $this->data[$idx] = chr($val);
  }
}

final class BitSet extends AbstractIntArray {
  protected $length;
  private $byteArray;

  function __construct($length) {
    $this->length = $length;
    $this->byteArray = new ByteArray(ceil($length / 8));
  }

  function get($idx) {
    $this->checkIndex($idx);

    $byteIdx = (int) ($idx / 8);
    $bitIdx  = $idx % 8;
    $byte = $this->byteArray->get($byteIdx);
    return (($byte >> $bitIdx) & 1) === 1;
  }

  function put($idx, $val) {
    $this->checkIndex($idx);

    if (!is_bool($val))
      throw new \OutOfRangeException();

    $byteIdx = (int) ($idx / 8);
    $bitIdx  = $idx % 8;

    $byte = $this->byteArray->get($byteIdx);
    if ($val) {
      $byte |= (1 << $bitIdx);
    } else {
      $byte &= (0 << $bitIdx);
    }

    $this->byteArray->put($byteIdx, $byte);
  }

  function getData() {
    return $this->byteArray->getData();
  }
}

final class Int32Array extends AbstractIntArray {
  protected $typeSize = 4;

  function get($idx) {
    $this->checkIndex($idx);

    $bytes = substr($this->data, $idx * 4, 4);
    $res = unpack('V', $bytes);
    return $res[1];
  }

  function put($idx, $val) {
    $this->checkIndex($idx);
    $this->checkValue($val);

    $bytes = pack('V', $val);
    $base = $idx * 4;
    for ($i = 0; $i < 4; $i++) {
      $this->data[$base + $i] = $bytes[$i];
    }
  }
}

final class Int64Array extends AbstractIntArray {
  protected $typeSize = 8;

  function get($idx) {
    $this->checkIndex($idx);

    $bytes = substr($this->data, $idx * 8, 8);
    list(, $a, $b) = unpack('V2', $bytes);
    return ($a << 32) + $b;
  }

  function put($idx, $val) {
    $this->checkIndex($idx);
    $this->checkValue($val);

    $a = $val >> 32;
    $b = $val & 0xffffffff;
    $bytes = pack('VV', $a, $b);
    $base = $idx * 8;
    for ($i = 0; $i < 8; $i++) {
      $this->data[$base + $i] = $bytes[$i];
    }
  }
}

Array with 1000000 integers:

Iterating through 1000000 element array:

píše k47 (@kaja47, k47)