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
12 * Common functions for readers and writers
16 * Do a sum of 32-bit signed integers with 2's complement overflow.
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.
23 public static function sumWithOverflow( $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;
31 // Strip off the carry bit
32 $carry = ($sum & 0x40000000) >> 30;
33 $sum = $sum & 0x3fffffff;
35 // Get the last two bits
36 $highA = self
::unsignedShiftRight( $a, 30 );
37 $highB = self
::unsignedShiftRight( $b, 30 );
40 $highSum = $carry +
$highA +
$highB;
43 $sum = $sum |
( $highSum << 30 );
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
52 public static function unsignedMod( $a, $b ) {
54 $m = ( $a & 0x7fffffff ) %
$b +
2 * ( 0x40000000 %
$b );
62 * Shift a signed integer right as if it were unsigned
64 public static function unsignedShiftRight( $a, $b ) {
69 return ( ( $a & 0x7fffffff ) >> $b ) |
( 0x40000000 >> ( $b - 1 ) );
75 public static function hash( $s ) {
77 for ( $i = 0; $i < strlen( $s ); $i++
) {
78 $h = self
::sumWithOverflow( $h, $h << 5 ) ^
ord( $s[$i] );
87 class CdbReader_PHP
extends CdbReader
{
88 /** The file handle */
91 /* number of hash slots searched under this key */
94 /* initialized if loop is nonzero */
97 /* initialized if loop is nonzero */
100 /* initialized if loop is nonzero */
103 /* initialized if loop is nonzero */
106 /* initialized if findNext() returns true */
109 /* initialized if cdb_findnext() returns 1 */
112 function __construct( $fileName ) {
113 $this->handle
= fopen( $fileName, 'rb' );
114 if ( !$this->handle
) {
115 throw new MWException( 'Unable to open DB file "' . $fileName . '"' );
121 fclose( $this->handle
);
122 unset( $this->handle
);
125 public function get( $key ) {
126 // strval is required
127 if ( $this->find( strval( $key ) ) ) {
128 return $this->read( $this->dlen
, $this->dpos
);
134 protected function match( $key, $pos ) {
135 $buf = $this->read( strlen( $key ), $pos );
136 return $buf === $key;
139 protected function findStart() {
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.' );
149 if ( $length == 0 ) {
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' );
161 * Unpack an unsigned integer and throw an exception if it needs more than 31 bits
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' );
172 * Unpack a 32-bit signed integer
174 protected function unpackSigned( $s ) {
175 $data = unpack( 'va/vb', $s );
176 return $data['a'] |
( $data['b'] << 16 );
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
) {
187 $this->hpos
= $this->unpack31( substr( $buf, 0, 4 ) );
189 $u = CdbFunctions
::unsignedShiftRight( $u, 8 );
190 $u = CdbFunctions
::unsignedMod( $u, $this->hslots
);
192 $this->kpos
= $this->hpos +
$u;
195 while ( $this->loop
< $this->hslots
) {
196 $buf = $this->read( 8, $this->kpos
);
197 $pos = $this->unpack31( substr( $buf, 4 ) );
203 if ( $this->kpos
== $this->hpos +
( $this->hslots
<< 3 ) ) {
204 $this->kpos
= $this->hpos
;
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 ) ) {
212 $this->dlen
= $this->unpack31( substr( $buf, 4 ) );
213 $this->dpos
= $pos +
8 +
$keyLen;
221 protected function find( $key ) {
223 return $this->findNext( $key );
230 class CdbWriter_PHP
extends CdbWriter
{
231 var $handle, $realFileName, $tmpFileName;
234 var $numEntries, $pos;
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 . '"' );
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' );
251 function __destruct() {
252 if ( isset( $this->handle
) ) {
257 public function set( $key, $value ) {
258 if ( strval( $key ) === '' ) {
259 // DBA cross-check hack
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 ) );
268 public function close() {
270 fclose( $this->handle
);
271 if ( wfIsWindows() ) {
272 unlink( $this->realFileName
);
274 if ( !rename( $this->tmpFileName
, $this->realFileName
) ) {
275 throw new MWException( 'Unable to move the new CDB file into place.' );
277 unset( $this->handle
);
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.' );
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' );
292 $this->pos
= $newpos;
295 protected function addend( $keylen, $datalen, $h ) {
296 $this->hplist
[] = array(
303 $this->posplus( $keylen );
304 $this->posplus( $datalen );
307 protected function addbegin( $keylen, $datalen ) {
308 if ( $keylen > 0x7fffffff ) {
309 throw new MWException( __METHOD__
.': key length too long' );
311 if ( $datalen > 0x7fffffff ) {
312 throw new MWException( __METHOD__
.': data length too long' );
314 $buf = pack( 'VV', $keylen, $datalen );
315 $this->write( $buf );
318 protected function finish() {
319 // Hack for DBA cross-check
320 $this->hplist
= array_reverse( $this->hplist
);
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'] ];
328 // Fill in $starts with the *end* indexes
331 for ( $i = 0; $i < 256; ++
$i ) {
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;
345 for ( $i = 0; $i < 256; ++
$i ) {
346 $count = $counts[$i];
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 );
353 $hashtable = array();
354 for ( $u = 0; $u < $len; ++
$u ) {
355 $hashtable[$u] = array( 'h' => 0, 'p' => 0 );
358 // Fill the hashtable, using the next empty slot if the hashed slot
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 )
367 $hashtable[$where] = $hp;
370 // Write the hashtable
371 for ( $u = 0; $u < $len; ++
$u ) {
373 $hashtable[$u]['h'] & 0xffff,
374 CdbFunctions
::unsignedShiftRight( $hashtable[$u]['h'], 16 ),
375 $hashtable[$u]['p'] );
376 $this->write( $buf );
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' );
386 $this->write( $final );