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