includes/utils/CdbPHP.php

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