includes/Cdb_PHP.php

   1 <?php
   2
   3 /**
   4  * This is a port of D.J. Bernstein's CDB to PHP. It's based on the copy that
   5  * appears in PHP 5.3. Changes are:
   6  *    * Error returns replaced with exceptions
   7  *    * Exception thrown if sizes or offsets are between 2GB and 4GB
   8  *    * Some variables renamed
   9  */
  10
  11 /**
  12  * Common functions for readers and writers
  13  */
  14 class CdbFunctions {
  15         /**
  16          * Do a sum of 32-bit signed integers with 2's complement overflow.
  17          *
  18          * PHP has broken plus and minus operators, but the bitwise operators
  19          * (&, |, ^, ~, <<, >>) are all implemented as a simple wrapper around the
  20          * underlying C operator. The algorithm here uses a binary view of addition
  21          * to simulate 32-bit addition using 31-bit registers.
  22          */
  23         public static function sumWithOverflow( $a, $b ) {
  24                 $sum = $a + $b;
  25                 if ( is_float( $sum ) ) {
  26                         // Use the plus operator to do a sum of the lowest 30 bits to produce a 31-bit result
  27                         $lowA = $a & 0x3fffffff;
  28                         $lowB = $b & 0x3fffffff;
  29                         $sum = $lowA + $lowB;
  30
  31                         // Strip off the carry bit
  32                         $carry = ($sum & 0x40000000) >> 30;
  33                         $sum = $sum & 0x3fffffff;
  34
  35                         // Get the last two bits
  36                         $highA = self::unsignedShiftRight( $a, 30 );
  37                         $highB = self::unsignedShiftRight( $b, 30 );
  38
  39                         // Add with carry
  40                         $highSum = $carry + $highA + $highB;
  41
  42                         // Recombine
  43                         $sum = $sum | ( $highSum << 30 );
  44                 }
  45                 return $sum;
  46         }
  47
  48         /**
  49          * Take a modulo of a signed integer as if it were an unsigned integer.
  50          * $b must be less than 0x40000000 and greater than 0
  51          */
  52         public static function unsignedMod( $a, $b ) {
  53                 if ( $a < 0 ) {
  54                         $m = ( $a & 0x7fffffff ) % $b + 2 * ( 0x40000000 % $b );
  55                         return $m % $b;
  56                 } else {
  57                         return $a % $b;
  58                 }
  59         }
  60
  61         /**
  62          * Shift a signed integer right as if it were unsigned
  63          */
  64         public static function unsignedShiftRight( $a, $b ) {
  65                 if ( $b == 0 ) {
  66                         return $a;
  67                 }
  68                 if ( $a < 0 ) {
  69                         return ( ( $a & 0x7fffffff ) >> $b ) | ( 0x40000000 >> ( $b - 1 ) );
  70                 } else {
  71                         return $a >> $b;
  72                 }
  73         }
  74
  75         public static function hash( $s ) {
  76                 $h = 5381;
  77                 for ( $i = 0; $i < strlen( $s ); $i++ ) {
  78                         $h = self::sumWithOverflow( $h, $h << 5 ) ^ ord( $s[$i] );
  79                 }
  80                 return $h;
  81         }
  82 }
  83
  84 /**
  85  * CDB reader class
  86  */
  87 class CdbReader_PHP extends CdbReader {
  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         function __construct( $fileName ) {
 113                 $this->handle = fopen( $fileName, 'rb' );
 114                 if ( !$this->handle ) {
 115                         throw new MWException( 'Unable to open DB file "' . $fileName . '"' );
 116                 }
 117                 $this->findStart();
 118         }
 119
 120         function close() {
 121                 fclose( $this->handle );
 122                 unset( $this->handle );
 123         }
 124
 125         public function get( $key ) {
 126                 // strval is required
 127                 if ( $this->find( strval( $key ) ) ) {
 128                         return $this->read( $this->dlen, $this->dpos );
 129                 } else {
 130                         return false;
 131                 }
 132         }
 133
 134         protected function match( $key, $pos ) {
 135                 $buf = $this->read( strlen( $key ), $pos );
 136                 return $buf === $key;
 137         }
 138
 139         protected function findStart() {
 140                 $this->loop = 0;
 141         }
 142
 143         protected function read( $length, $pos ) {
 144                 if ( fseek( $this->handle, $pos ) == -1 ) {
 145                         // This can easily happen if the internal pointers are incorrect
 146                         throw new MWException( __METHOD__.': seek failed, file may be corrupted.' );
 147                 }
 148
 149                 if ( $length == 0 ) {
 150                         return '';
 151                 }
 152
 153                 $buf = fread( $this->handle, $length );
 154                 if ( $buf === false || strlen( $buf ) !== $length ) {
 155                         throw new MWException( __METHOD__.': read from cdb file failed, file may be corrupted' );
 156                 }
 157                 return $buf;
 158         }
 159
 160         /**
 161          * Unpack an unsigned integer and throw an exception if it needs more than 31 bits
 162          */
 163         protected function unpack31( $s ) {
 164                 $data = unpack( 'V', $s );
 165                 if ( $data[1] > 0x7fffffff ) {
 166                         throw new MWException( __METHOD__.': error in CDB file, integer too big' );
 167                 }
 168                 return $data[1];
 169         }
 170
 171         /**
 172          * Unpack a 32-bit signed integer
 173          */
 174         protected function unpackSigned( $s ) {
 175                 $data = unpack( 'va/vb', $s );
 176                 return $data['a'] | ( $data['b'] << 16 );
 177         }
 178
 179         protected function findNext( $key ) {
 180                 if ( !$this->loop ) {
 181                         $u = CdbFunctions::hash( $key );
 182                         $buf = $this->read( 8, ( $u << 3 ) & 2047 );
 183                         $this->hslots = $this->unpack31( substr( $buf, 4 ) );
 184                         if ( !$this->hslots ) {
 185                                 return false;
 186                         }
 187                         $this->hpos = $this->unpack31( substr( $buf, 0, 4 ) );
 188                         $this->khash = $u;
 189                         $u = CdbFunctions::unsignedShiftRight( $u, 8 );
 190                         $u = CdbFunctions::unsignedMod( $u, $this->hslots );
 191                         $u <<= 3;
 192                         $this->kpos = $this->hpos + $u;
 193                 }
 194
 195                 while ( $this->loop < $this->hslots ) {
 196                         $buf = $this->read( 8, $this->kpos );
 197                         $pos = $this->unpack31( substr( $buf, 4 ) );
 198                         if ( !$pos ) {
 199                                 return false;
 200                         }
 201                         $this->loop += 1;
 202                         $this->kpos += 8;
 203                         if ( $this->kpos == $this->hpos + ( $this->hslots << 3 ) ) {
 204                                 $this->kpos = $this->hpos;
 205                         }
 206                         $u = $this->unpackSigned( substr( $buf, 0, 4 ) );
 207                         if ( $u === $this->khash ) {
 208                                 $buf = $this->read( 8, $pos );
 209                                 $keyLen = $this->unpack31( substr( $buf, 0, 4 ) );
 210                                 if ( $keyLen == strlen( $key ) && $this->match( $key, $pos + 8 ) ) {
 211                                         // Found
 212                                         $this->dlen = $this->unpack31( substr( $buf, 4 ) );
 213                                         $this->dpos = $pos + 8 + $keyLen;
 214                                         return true;
 215                                 }
 216                         }
 217                 }
 218                 return false;
 219         }
 220
 221         protected function find( $key ) {
 222                 $this->findStart();
 223                 return $this->findNext( $key );
 224         }
 225 }
 226
 227 /**
 228  * CDB writer class
 229  */
 230 class CdbWriter_PHP extends CdbWriter {
 231         var $handle, $realFileName, $tmpFileName;
 232
 233         var $hplist;
 234         var $numEntries, $pos;
 235
 236         function __construct( $fileName ) {
 237                 $this->realFileName = $fileName;
 238                 $this->tmpFileName = $fileName . '.tmp.' . mt_rand( 0, 0x7fffffff );
 239                 $this->handle = fopen( $this->tmpFileName, 'wb' );
 240                 if ( !$this->handle ) {
 241                         throw new MWException( 'Unable to open DB file for write "' . $fileName . '"' );
 242                 }
 243                 $this->hplist = array();
 244                 $this->numentries = 0;
 245                 $this->pos = 2048; // leaving space for the pointer array, 256 * 8
 246                 if ( fseek( $this->handle, $this->pos ) == -1 ) {
 247                         throw new MWException( __METHOD__.': fseek failed' );
 248                 }
 249         }
 250
 251         function __destruct() {
 252                 if ( isset( $this->handle ) ) {
 253                         $this->close();
 254                 }
 255         }
 256
 257         public function set( $key, $value ) {
 258                 if ( strval( $key ) === '' ) {
 259                         // DBA cross-check hack
 260                         return;
 261                 }
 262                 $this->addbegin( strlen( $key ), strlen( $value ) );
 263                 $this->write( $key );
 264                 $this->write( $value );
 265                 $this->addend( strlen( $key ), strlen( $value ), CdbFunctions::hash( $key ) );
 266         }
 267
 268         public function close() {
 269                 $this->finish();
 270                 fclose( $this->handle );
 271                 if ( wfIsWindows() ) {
 272                         unlink( $this->realFileName );
 273                 }
 274                 if ( !rename( $this->tmpFileName, $this->realFileName ) ) {
 275                         throw new MWException( 'Unable to move the new CDB file into place.' );
 276                 }
 277                 unset( $this->handle );
 278         }
 279
 280         protected function write( $buf ) {
 281                 $len = fwrite( $this->handle, $buf );
 282                 if ( $len !== strlen( $buf ) ) {
 283                         throw new MWException( 'Error writing to CDB file.' );
 284                 }
 285         }
 286
 287         protected function posplus( $len ) {
 288                 $newpos = $this->pos + $len;
 289                 if ( $newpos > 0x7fffffff ) {
 290                         throw new MWException( 'A value in the CDB file is too large' );
 291                 }
 292                 $this->pos = $newpos;
 293         }
 294
 295         protected function addend( $keylen, $datalen, $h ) {
 296                 $this->hplist[] = array(
 297                         'h' => $h,
 298                         'p' => $this->pos
 299                 );
 300
 301                 $this->numentries++;
 302                 $this->posplus( 8 );
 303                 $this->posplus( $keylen );
 304                 $this->posplus( $datalen );
 305         }
 306
 307         protected function addbegin( $keylen, $datalen ) {
 308                 if ( $keylen > 0x7fffffff ) {
 309                         throw new MWException( __METHOD__.': key length too long' );
 310                 }
 311                 if ( $datalen > 0x7fffffff ) {
 312                         throw new MWException( __METHOD__.': data length too long' );
 313                 }
 314                 $buf = pack( 'VV', $keylen, $datalen );
 315                 $this->write( $buf );
 316         }
 317
 318         protected function finish() {
 319                 // Hack for DBA cross-check
 320                 $this->hplist = array_reverse( $this->hplist );
 321
 322                 // Calculate the number of items that will be in each hashtable
 323                 $counts = array_fill( 0, 256, 0 );
 324                 foreach ( $this->hplist as $item ) {
 325                         ++ $counts[ 255 & $item['h'] ];
 326                 }
 327
 328                 // Fill in $starts with the *end* indexes
 329                 $starts = array();
 330                 $pos = 0;
 331                 for ( $i = 0; $i < 256; ++$i ) {
 332                         $pos += $counts[$i];
 333                         $starts[$i] = $pos;
 334                 }
 335
 336                 // Excessively clever and indulgent code to simultaneously fill $packedTables
 337                 // with the packed hashtables, and adjust the elements of $starts
 338                 // to actually point to the starts instead of the ends.
 339                 $packedTables = array_fill( 0, $this->numentries, false );
 340                 foreach ( $this->hplist as $item ) {
 341                         $packedTables[--$starts[255 & $item['h']]] = $item;
 342                 }
 343
 344                 $final = '';
 345                 for ( $i = 0; $i < 256; ++$i ) {
 346                         $count = $counts[$i];
 347
 348                         // The size of the hashtable will be double the item count.
 349                         // The rest of the slots will be empty.
 350                         $len = $count + $count;
 351                         $final .= pack( 'VV', $this->pos, $len );
 352
 353                         $hashtable = array();
 354                         for ( $u = 0; $u < $len; ++$u ) {
 355                                 $hashtable[$u] = array( 'h' => 0, 'p' => 0 );
 356                         }
 357
 358                         // Fill the hashtable, using the next empty slot if the hashed slot
 359                         // is taken.
 360                         for ( $u = 0; $u < $count; ++$u ) {
 361                                 $hp = $packedTables[$starts[$i] + $u];
 362                                 $where = CdbFunctions::unsignedMod(
 363                                         CdbFunctions::unsignedShiftRight( $hp['h'], 8 ), $len );
 364                                 while ( $hashtable[$where]['p'] )
 365                                         if ( ++$where == $len )
 366                                                 $where = 0;
 367                                 $hashtable[$where] = $hp;
 368                         }
 369
 370                         // Write the hashtable
 371                         for ( $u = 0; $u < $len; ++$u ) {
 372                                 $buf = pack( 'vvV',
 373                                         $hashtable[$u]['h'] & 0xffff,
 374                                         CdbFunctions::unsignedShiftRight( $hashtable[$u]['h'], 16 ),
 375                                         $hashtable[$u]['p'] );
 376                                 $this->write( $buf );
 377                                 $this->posplus( 8 );
 378                         }
 379                 }
 380
 381                 // Write the pointer array at the start of the file
 382                 rewind( $this->handle );
 383                 if ( ftell( $this->handle ) != 0 ) {
 384                         throw new MWException( __METHOD__.': Error rewinding to start of file' );
 385                 }
 386                 $this->write( $final );
 387         }
 388 }