--- /dev/null
+<?php
+
+namespace Cdb\Reader;
+
+use Cdb\Exception;
+use Cdb\Reader;
+use Cdb\Util;
+
+/**
+ * This is a port of D.J. Bernstein's CDB to PHP. It's based on the copy that
+ * appears in PHP 5.3.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ * http://www.gnu.org/copyleft/gpl.html
+ *
+ * @file
+ */
+
+/**
+ * CDB reader class
+ */
+class PHP extends Reader {
+
+ /** @var string The file name of the CDB file. **/
+ protected $fileName;
+
+ /** @var string First 2048b of CDB file, containing pointers to hash table. **/
+ protected $index;
+
+ /** @var int Offset in file where value of found key starts. **/
+ protected $dataPos;
+
+ /** @var int Byte length of found key's value. **/
+ protected $dataLen;
+
+ /** @var int File position indicator when iterating over keys. **/
+ protected $keyIterPos = 2048;
+
+ /** @var int Offset in file where hash tables start. **/
+ protected $keyIterStop;
+
+ /** @var string Read buffer for CDB file. **/
+ protected $buf;
+
+ /** @var int File offset where read buffer starts. **/
+ protected $bufStart;
+
+ /** @var int File handle position indicator **/
+ protected $filePos = 2048;
+
+ /**
+ * Constructor.
+ *
+ * @param string $fileName
+ * @throws Exception If CDB file cannot be opened or if it contains fewer
+ * than 2048 bytes of data.
+ */
+ public function __construct( $fileName ) {
+ $this->fileName = $fileName;
+ $this->handle = fopen( $fileName, 'rb' );
+ if ( !$this->handle ) {
+ throw new Exception( 'Unable to open CDB file "' . $this->fileName . '".' );
+ }
+ $this->index = fread( $this->handle, 2048 );
+ if ( strlen( $this->index ) !== 2048 ) {
+ throw new Exception( 'CDB file contains fewer than 2048 bytes of data.' );
+ }
+ }
+
+ /**
+ * Close the handle on the CDB file.
+ */
+ public function close() {
+ if ( isset( $this->handle ) ) {
+ fclose( $this->handle );
+ }
+ unset( $this->handle );
+ }
+
+ /**
+ * Get the value of a key.
+ *
+ * @param mixed $key
+ * @return bool|string The key's value or false if not found.
+ */
+ public function get( $key ) {
+ // strval is required
+ if ( $this->find( strval( $key ) ) ) {
+ return $this->read( $this->dataPos, $this->dataLen );
+ }
+
+ return false;
+ }
+
+ /**
+ * Read data from the CDB file.
+ *
+ * @throws Exception When attempting to read past the end of the file.
+ * @param int $start Start reading from this position.
+ * @param int $len Number of bytes to read.
+ * @return string Read data.
+ */
+ protected function read( $start, $len ) {
+ $end = $start + $len;
+
+ // The first 2048 bytes are the lookup table, which is read into
+ // memory on initialization.
+ if ( $end <= 2048 ) {
+ return substr( $this->index, $start, $len );
+ }
+
+ // Read data from the internal buffer first.
+ $bytes = '';
+ if ( $this->buf && $start >= $this->bufStart ) {
+ $bytes .= substr( $this->buf, $start - $this->bufStart, $len );
+ $bytesRead = strlen( $bytes );
+ $len -= $bytesRead;
+ $start += $bytesRead;
+ } else {
+ $bytesRead = 0;
+ }
+
+ if ( !$len ) {
+ return $bytes;
+ }
+
+ // Many reads are sequential, so the file position indicator may
+ // already be in the right place, in which case we can avoid the
+ // call to fseek().
+ if ( $start !== $this->filePos ) {
+ if ( fseek( $this->handle, $start ) === -1 ) {
+ // This can easily happen if the internal pointers are incorrect
+ throw new Exception(
+ 'Seek failed, file "' . $this->fileName . '" may be corrupted.' );
+ }
+ }
+
+ $buf = fread( $this->handle, max( $len, 1024 ) );
+ if ( $buf === false ) {
+ $buf = '';
+ }
+
+ $bytes .= substr( $buf, 0, $len );
+ if ( strlen( $bytes ) !== $len + $bytesRead ) {
+ throw new Exception(
+ 'Read from CDB file failed, file "' . $this->fileName . '" may be corrupted.' );
+ }
+
+ $this->filePos = $end;
+ $this->bufStart = $start;
+ $this->buf = $buf;
+
+ return $bytes;
+ }
+
+ /**
+ * Unpack an unsigned integer and throw an exception if it needs more than 31 bits.
+ *
+ * @param int $pos Position to read from.
+ * @throws Exception When the integer cannot be represented in 31 bits.
+ * @return int
+ */
+ protected function readInt31( $pos = 0 ) {
+ $uint31 = $this->readInt32( $pos );
+ if ( $uint31 > 0x7fffffff ) {
+ throw new Exception(
+ 'Error in CDB file "' . $this->fileName . '", integer too big.' );
+ }
+
+ return $uint31;
+ }
+
+ /**
+ * Unpack a 32-bit integer.
+ *
+ * @param int $pos
+ * @return int
+ */
+ protected function readInt32( $pos = 0 ) {
+ static $lookups;
+
+ if ( !$lookups ) {
+ $lookups = array();
+ for ( $i = 1; $i < 256; $i++ ) {
+ $lookups[ chr( $i ) ] = $i;
+ }
+ }
+
+ $buf = $this->read( $pos, 4 );
+
+ $rv = 0;
+
+ if ( $buf[0] !== "\x0" ) {
+ $rv = $lookups[ $buf[0] ];
+ }
+ if ( $buf[1] !== "\x0" ) {
+ $rv |= ( $lookups[ $buf[1] ] << 8 );
+ }
+ if ( $buf[2] !== "\x0" ) {
+ $rv |= ( $lookups[ $buf[2] ] << 16 );
+ }
+ if ( $buf[3] !== "\x0" ) {
+ $rv |= ( $lookups[ $buf[3] ] << 24 );
+ }
+
+ return $rv;
+ }
+
+ /**
+ * Search the CDB file for a key.
+ *
+ * Sets `dataLen` and `dataPos` properties if successful.
+ *
+ * @param string $key
+ * @return bool Whether the key was found.
+ */
+ protected function find( $key ) {
+ $keyLen = strlen( $key );
+
+ $u = Util::hash( $key );
+ $upos = ( $u << 3 ) & 2047;
+ $hashSlots = $this->readInt31( $upos + 4 );
+ if ( !$hashSlots ) {
+ return false;
+ }
+ $hashPos = $this->readInt31( $upos );
+ $keyHash = $u;
+ $u = Util::unsignedShiftRight( $u, 8 );
+ $u = Util::unsignedMod( $u, $hashSlots );
+ $u <<= 3;
+ $keyPos = $hashPos + $u;
+
+ for ( $i = 0; $i < $hashSlots; $i++ ) {
+ $hash = $this->readInt32( $keyPos );
+ $pos = $this->readInt31( $keyPos + 4 );
+ if ( !$pos ) {
+ return false;
+ }
+ $keyPos += 8;
+ if ( $keyPos == $hashPos + ( $hashSlots << 3 ) ) {
+ $keyPos = $hashPos;
+ }
+ if ( $hash === $keyHash ) {
+ if ( $keyLen === $this->readInt31( $pos ) ) {
+ $dataLen = $this->readInt31( $pos + 4 );
+ $dataPos = $pos + 8 + $keyLen;
+ $foundKey = $this->read( $pos + 8, $keyLen );
+ if ( $foundKey === $key ) {
+ // Found
+ $this->dataLen = $dataLen;
+ $this->dataPos = $dataPos;
+
+ return true;
+ }
+ }
+ }
+ }
+
+ return false;
+ }
+
+ /**
+ * Check if a key exists in the CDB file.
+ *
+ * @param string $key
+ * @return bool Whether the key exists.
+ */
+ public function exists( $key ) {
+ return $this->find( strval( $key ) );
+ }
+
+ /**
+ * Get the first key from the CDB file and reset the key iterator.
+ *
+ * @return string|bool Key, or false if no keys in file.
+ */
+ public function firstkey() {
+ $this->keyIterPos = 4;
+
+ if ( !$this->keyIterStop ) {
+ $pos = INF;
+ for ( $i = 0; $i < 2048; $i+= 8 ) {
+ $pos = min( $this->readInt31( $i ), $pos );
+ }
+ $this->keyIterStop = $pos;
+ }
+
+ $this->keyIterPos = 2048;
+ return $this->nextkey();
+ }
+
+ /**
+ * Get the next key from the CDB file.
+ *
+ * @return string|bool Key, or false if no more keys.
+ */
+ public function nextkey() {
+ if ( $this->keyIterPos >= $this->keyIterStop ) {
+ return false;
+ }
+ $keyLen = $this->readInt31( $this->keyIterPos );
+ $dataLen = $this->readInt31( $this->keyIterPos + 4 );
+ $key = $this->read( $this->keyIterPos + 8, $keyLen );
+ $this->keyIterPos += 8 + $keyLen + $dataLen;
+
+ return $key;
+ }
+}