[Summary view] [Print] [Text view]

   1  <?php
   2  /**
   3   * This is a port of D.J. Bernstein's CDB to PHP. It's based on the copy that
   4   * appears in PHP 5.3. Changes are:
   5   *    * Error returns replaced with exceptions
   6   *    * Exception thrown if sizes or offsets are between 2GB and 4GB
   7   *    * Some variables renamed
   8   *
   9   * This program is free software; you can redistribute it and/or modify
  10   * it under the terms of the GNU General Public License as published by
  11   * the Free Software Foundation; either version 2 of the License, or
  12   * (at your option) any later version.
  13   *
  14   * This program is distributed in the hope that it will be useful,
  15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  17   * GNU General Public License for more details.
  18   *
  19   * You should have received a copy of the GNU General Public License along
  20   * with this program; if not, write to the Free Software Foundation, Inc.,
  21   * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  22   * http://www.gnu.org/copyleft/gpl.html
  23   *
  24   * @file
  25   */
  26  
  27  /**
  28   * Common functions for readers and writers
  29   */
  30  class CdbFunctions {
  31      /**
  32       * Take a modulo of a signed integer as if it were an unsigned integer.
  33       * $b must be less than 0x40000000 and greater than 0
  34       *
  35       * @param int $a
  36       * @param int $b
  37       *
  38       * @return int
  39       */
  40  	public static function unsignedMod( $a, $b ) {
  41          if ( $a & 0x80000000 ) {
  42              $m = ( $a & 0x7fffffff ) % $b + 2 * ( 0x40000000 % $b );
  43  
  44              return $m % $b;
  45          } else {
  46              return $a % $b;
  47          }
  48      }
  49  
  50      /**
  51       * Shift a signed integer right as if it were unsigned
  52       * @param int $a
  53       * @param int $b
  54       * @return int
  55       */
  56  	public static function unsignedShiftRight( $a, $b ) {
  57          if ( $b == 0 ) {
  58              return $a;
  59          }
  60          if ( $a & 0x80000000 ) {
  61              return ( ( $a & 0x7fffffff ) >> $b ) | ( 0x40000000 >> ( $b - 1 ) );
  62          } else {
  63              return $a >> $b;
  64          }
  65      }
  66  
  67      /**
  68       * The CDB hash function.
  69       *
  70       * @param string $s
  71       *
  72       * @return int
  73       */
  74  	public static function hash( $s ) {
  75          $h = 5381;
  76          $len = strlen( $s );
  77          for ( $i = 0; $i < $len; $i++ ) {
  78              $h5 = ( $h << 5 ) & 0xffffffff;
  79              // Do a 32-bit sum
  80              // Inlined here for speed
  81              $sum = ( $h & 0x3fffffff ) + ( $h5 & 0x3fffffff );
  82              $h =
  83                  (
  84                      ( $sum & 0x40000000 ? 1 : 0 )
  85                      + ( $h & 0x80000000 ? 2 : 0 )
  86                      + ( $h & 0x40000000 ? 1 : 0 )
  87                      + ( $h5 & 0x80000000 ? 2 : 0 )
  88                      + ( $h5 & 0x40000000 ? 1 : 0 )
  89                  ) << 30
  90                  | ( $sum & 0x3fffffff );
  91              $h ^= ord( $s[$i] );
  92              $h &= 0xffffffff;
  93          }
  94  
  95          return $h;
  96      }
  97  }
  98  
  99  /**
 100   * CDB reader class
 101   */
 102  class CdbReaderPHP extends CdbReader {
 103      /** The filename */
 104      protected $fileName;
 105  
 106      /* number of hash slots searched under this key */
 107      protected $loop;
 108  
 109      /* initialized if loop is nonzero */
 110      protected $khash;
 111  
 112      /* initialized if loop is nonzero */
 113      protected $kpos;
 114  
 115      /* initialized if loop is nonzero */
 116      protected $hpos;
 117  
 118      /* initialized if loop is nonzero */
 119      protected $hslots;
 120  
 121      /* initialized if findNext() returns true */
 122      protected $dpos;
 123  
 124      /* initialized if cdb_findnext() returns 1 */
 125      protected $dlen;
 126  
 127      /**
 128       * @param string $fileName
 129       * @throws CdbException
 130       */
 131  	public function __construct( $fileName ) {
 132          $this->fileName = $fileName;
 133          $this->handle = fopen( $fileName, 'rb' );
 134          if ( !$this->handle ) {
 135              throw new CdbException( 'Unable to open CDB file "' . $this->fileName . '".' );
 136          }
 137          $this->findStart();
 138      }
 139  
 140  	public function close() {
 141          if ( isset( $this->handle ) ) {
 142              fclose( $this->handle );
 143          }
 144          unset( $this->handle );
 145      }
 146  
 147      /**
 148       * @param mixed $key
 149       * @return bool|string
 150       */
 151  	public function get( $key ) {
 152          // strval is required
 153          if ( $this->find( strval( $key ) ) ) {
 154              return $this->read( $this->dlen, $this->dpos );
 155          } else {
 156              return false;
 157          }
 158      }
 159  
 160      /**
 161       * @param string $key
 162       * @param int $pos
 163       * @return bool
 164       */
 165  	protected function match( $key, $pos ) {
 166          $buf = $this->read( strlen( $key ), $pos );
 167  
 168          return $buf === $key;
 169      }
 170  
 171  	protected function findStart() {
 172          $this->loop = 0;
 173      }
 174  
 175      /**
 176       * @throws CdbException
 177       * @param int $length
 178       * @param int $pos
 179       * @return string
 180       */
 181  	protected function read( $length, $pos ) {
 182          if ( fseek( $this->handle, $pos ) == -1 ) {
 183              // This can easily happen if the internal pointers are incorrect
 184              throw new CdbException(
 185                  'Seek failed, file "' . $this->fileName . '" may be corrupted.' );
 186          }
 187  
 188          if ( $length == 0 ) {
 189              return '';
 190          }
 191  
 192          $buf = fread( $this->handle, $length );
 193          if ( $buf === false || strlen( $buf ) !== $length ) {
 194              throw new CdbException(
 195                  'Read from CDB file failed, file "' . $this->fileName . '" may be corrupted.' );
 196          }
 197  
 198          return $buf;
 199      }
 200  
 201      /**
 202       * Unpack an unsigned integer and throw an exception if it needs more than 31 bits
 203       * @param string $s
 204       * @throws CdbException
 205       * @return mixed
 206       */
 207  	protected function unpack31( $s ) {
 208          $data = unpack( 'V', $s );
 209          if ( $data[1] > 0x7fffffff ) {
 210              throw new CdbException(
 211                  'Error in CDB file "' . $this->fileName . '", integer too big.' );
 212          }
 213  
 214          return $data[1];
 215      }
 216  
 217      /**
 218       * Unpack a 32-bit signed integer
 219       * @param string $s
 220       * @return int
 221       */
 222  	protected function unpackSigned( $s ) {
 223          $data = unpack( 'va/vb', $s );
 224  
 225          return $data['a'] | ( $data['b'] << 16 );
 226      }
 227  
 228      /**
 229       * @param string $key
 230       * @return bool
 231       */
 232  	protected function findNext( $key ) {
 233          if ( !$this->loop ) {
 234              $u = CdbFunctions::hash( $key );
 235              $buf = $this->read( 8, ( $u << 3 ) & 2047 );
 236              $this->hslots = $this->unpack31( substr( $buf, 4 ) );
 237              if ( !$this->hslots ) {
 238                  return false;
 239              }
 240              $this->hpos = $this->unpack31( substr( $buf, 0, 4 ) );
 241              $this->khash = $u;
 242              $u = CdbFunctions::unsignedShiftRight( $u, 8 );
 243              $u = CdbFunctions::unsignedMod( $u, $this->hslots );
 244              $u <<= 3;
 245              $this->kpos = $this->hpos + $u;
 246          }
 247  
 248          while ( $this->loop < $this->hslots ) {
 249              $buf = $this->read( 8, $this->kpos );
 250              $pos = $this->unpack31( substr( $buf, 4 ) );
 251              if ( !$pos ) {
 252                  return false;
 253              }
 254              $this->loop += 1;
 255              $this->kpos += 8;
 256              if ( $this->kpos == $this->hpos + ( $this->hslots << 3 ) ) {
 257                  $this->kpos = $this->hpos;
 258              }
 259              $u = $this->unpackSigned( substr( $buf, 0, 4 ) );
 260              if ( $u === $this->khash ) {
 261                  $buf = $this->read( 8, $pos );
 262                  $keyLen = $this->unpack31( substr( $buf, 0, 4 ) );
 263                  if ( $keyLen == strlen( $key ) && $this->match( $key, $pos + 8 ) ) {
 264                      // Found
 265                      $this->dlen = $this->unpack31( substr( $buf, 4 ) );
 266                      $this->dpos = $pos + 8 + $keyLen;
 267  
 268                      return true;
 269                  }
 270              }
 271          }
 272  
 273          return false;
 274      }
 275  
 276      /**
 277       * @param mixed $key
 278       * @return bool
 279       */
 280  	protected function find( $key ) {
 281          $this->findStart();
 282  
 283          return $this->findNext( $key );
 284      }
 285  }
 286  
 287  /**
 288   * CDB writer class
 289   */
 290  class CdbWriterPHP extends CdbWriter {
 291      protected $hplist;
 292  
 293      protected $numentries;
 294  
 295      protected $pos;
 296  
 297      /**
 298       * @param string $fileName
 299       */
 300  	public function __construct( $fileName ) {
 301          $this->realFileName = $fileName;
 302          $this->tmpFileName = $fileName . '.tmp.' . mt_rand( 0, 0x7fffffff );
 303          $this->handle = fopen( $this->tmpFileName, 'wb' );
 304          if ( !$this->handle ) {
 305              $this->throwException(
 306                  'Unable to open CDB file "' . $this->tmpFileName . '" for write.' );
 307          }
 308          $this->hplist = array();
 309          $this->numentries = 0;
 310          $this->pos = 2048; // leaving space for the pointer array, 256 * 8
 311          if ( fseek( $this->handle, $this->pos ) == -1 ) {
 312              $this->throwException( 'fseek failed in file "' . $this->tmpFileName . '".' );
 313          }
 314      }
 315  
 316      /**
 317       * @param string $key
 318       * @param string $value
 319       */
 320  	public function set( $key, $value ) {
 321          if ( strval( $key ) === '' ) {
 322              // DBA cross-check hack
 323              return;
 324          }
 325          $this->addbegin( strlen( $key ), strlen( $value ) );
 326          $this->write( $key );
 327          $this->write( $value );
 328          $this->addend( strlen( $key ), strlen( $value ), CdbFunctions::hash( $key ) );
 329      }
 330  
 331      /**
 332       * @throws CdbException
 333       */
 334  	public function close() {
 335          $this->finish();
 336          if ( isset( $this->handle ) ) {
 337              fclose( $this->handle );
 338          }
 339          if ( $this->isWindows() && file_exists( $this->realFileName ) ) {
 340              unlink( $this->realFileName );
 341          }
 342          if ( !rename( $this->tmpFileName, $this->realFileName ) ) {
 343              $this->throwException( 'Unable to move the new CDB file into place.' );
 344          }
 345          unset( $this->handle );
 346      }
 347  
 348      /**
 349       * @throws CdbException
 350       * @param string $buf
 351       */
 352  	protected function write( $buf ) {
 353          $len = fwrite( $this->handle, $buf );
 354          if ( $len !== strlen( $buf ) ) {
 355              $this->throwException( 'Error writing to CDB file "' . $this->tmpFileName . '".' );
 356          }
 357      }
 358  
 359      /**
 360       * @throws CdbException
 361       * @param int $len
 362       */
 363  	protected function posplus( $len ) {
 364          $newpos = $this->pos + $len;
 365          if ( $newpos > 0x7fffffff ) {
 366              $this->throwException(
 367                  'A value in the CDB file "' . $this->tmpFileName . '" is too large.' );
 368          }
 369          $this->pos = $newpos;
 370      }
 371  
 372      /**
 373       * @param int $keylen
 374       * @param int $datalen
 375       * @param int $h
 376       */
 377  	protected function addend( $keylen, $datalen, $h ) {
 378          $this->hplist[] = array(
 379              'h' => $h,
 380              'p' => $this->pos
 381          );
 382  
 383          $this->numentries++;
 384          $this->posplus( 8 );
 385          $this->posplus( $keylen );
 386          $this->posplus( $datalen );
 387      }
 388  
 389      /**
 390       * @throws CdbException
 391       * @param int $keylen
 392       * @param int $datalen
 393       */
 394  	protected function addbegin( $keylen, $datalen ) {
 395          if ( $keylen > 0x7fffffff ) {
 396              $this->throwException( 'Key length too long in file "' . $this->tmpFileName . '".' );
 397          }
 398          if ( $datalen > 0x7fffffff ) {
 399              $this->throwException( 'Data length too long in file "' . $this->tmpFileName . '".' );
 400          }
 401          $buf = pack( 'VV', $keylen, $datalen );
 402          $this->write( $buf );
 403      }
 404  
 405      /**
 406       * @throws CdbException
 407       */
 408  	protected function finish() {
 409          // Hack for DBA cross-check
 410          $this->hplist = array_reverse( $this->hplist );
 411  
 412          // Calculate the number of items that will be in each hashtable
 413          $counts = array_fill( 0, 256, 0 );
 414          foreach ( $this->hplist as $item ) {
 415              ++$counts[255 & $item['h']];
 416          }
 417  
 418          // Fill in $starts with the *end* indexes
 419          $starts = array();
 420          $pos = 0;
 421          for ( $i = 0; $i < 256; ++$i ) {
 422              $pos += $counts[$i];
 423              $starts[$i] = $pos;
 424          }
 425  
 426          // Excessively clever and indulgent code to simultaneously fill $packedTables
 427          // with the packed hashtables, and adjust the elements of $starts
 428          // to actually point to the starts instead of the ends.
 429          $packedTables = array_fill( 0, $this->numentries, false );
 430          foreach ( $this->hplist as $item ) {
 431              $packedTables[--$starts[255 & $item['h']]] = $item;
 432          }
 433  
 434          $final = '';
 435          for ( $i = 0; $i < 256; ++$i ) {
 436              $count = $counts[$i];
 437  
 438              // The size of the hashtable will be double the item count.
 439              // The rest of the slots will be empty.
 440              $len = $count + $count;
 441              $final .= pack( 'VV', $this->pos, $len );
 442  
 443              $hashtable = array();
 444              for ( $u = 0; $u < $len; ++$u ) {
 445                  $hashtable[$u] = array( 'h' => 0, 'p' => 0 );
 446              }
 447  
 448              // Fill the hashtable, using the next empty slot if the hashed slot
 449              // is taken.
 450              for ( $u = 0; $u < $count; ++$u ) {
 451                  $hp = $packedTables[$starts[$i] + $u];
 452                  $where = CdbFunctions::unsignedMod(
 453                      CdbFunctions::unsignedShiftRight( $hp['h'], 8 ), $len );
 454                  while ( $hashtable[$where]['p'] ) {
 455                      if ( ++$where == $len ) {
 456                          $where = 0;
 457                      }
 458                  }
 459                  $hashtable[$where] = $hp;
 460              }
 461  
 462              // Write the hashtable
 463              for ( $u = 0; $u < $len; ++$u ) {
 464                  $buf = pack( 'vvV',
 465                      $hashtable[$u]['h'] & 0xffff,
 466                      CdbFunctions::unsignedShiftRight( $hashtable[$u]['h'], 16 ),
 467                      $hashtable[$u]['p'] );
 468                  $this->write( $buf );
 469                  $this->posplus( 8 );
 470              }
 471          }
 472  
 473          // Write the pointer array at the start of the file
 474          rewind( $this->handle );
 475          if ( ftell( $this->handle ) != 0 ) {
 476              $this->throwException( 'Error rewinding to start of file "' . $this->tmpFileName . '".' );
 477          }
 478          $this->write( $final );
 479      }
 480  
 481      /**
 482       * Clean up the temp file and throw an exception
 483       *
 484       * @param string $msg
 485       * @throws CdbException
 486       */
 487  	protected function throwException( $msg ) {
 488          if ( $this->handle ) {
 489              fclose( $this->handle );
 490              unlink( $this->tmpFileName );
 491          }
 492          throw new CdbException( $msg );
 493      }
 494  }