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