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