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