includes/historyblob/DiffHistoryBlob.php

   1 <?php
   2 /**
   3  * Efficient concatenated text storage.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  * http://www.gnu.org/copyleft/gpl.html
  19  *
  20  * @file
  21  */
  22
  23 /**
  24  * Diff-based history compression
  25  * Requires xdiff 1.5+ and zlib
  26  */
  27 class DiffHistoryBlob implements HistoryBlob {
  28         /** @var array Uncompressed item cache */
  29         public $mItems = [];
  30
  31         /** @var int Total uncompressed size */
  32         public $mSize = 0;
  33
  34         /**
  35          * @var array Array of diffs. If a diff D from A to B is notated D = B - A,
  36          * and Z is an empty string:
  37          *
  38          *              { item[map[i]] - item[map[i-1]]   where i > 0
  39          *    diff[i] = {
  40          *              { item[map[i]] - Z                where i = 0
  41          */
  42         public $mDiffs;
  43
  44         /** @var array The diff map, see above */
  45         public $mDiffMap;
  46
  47         /** @var int The key for getText()
  48          */
  49         public $mDefaultKey;
  50
  51         /** @var string Compressed storage */
  52         public $mCompressed;
  53
  54         /** @var bool True if the object is locked against further writes */
  55         public $mFrozen = false;
  56
  57         /**
  58          * @var int The maximum uncompressed size before the object becomes sad
  59          * Should be less than max_allowed_packet
  60          */
  61         public $mMaxSize = 10000000;
  62
  63         /** @var int The maximum number of text items before the object becomes sad */
  64         public $mMaxCount = 100;
  65
  66         /** Constants from xdiff.h */
  67         const XDL_BDOP_INS = 1;
  68         const XDL_BDOP_CPY = 2;
  69         const XDL_BDOP_INSB = 3;
  70
  71         function __construct() {
  72                 if ( !function_exists( 'gzdeflate' ) ) {
  73                         throw new MWException( "Need zlib support to read or write DiffHistoryBlob\n" );
  74                 }
  75         }
  76
  77         /**
  78          * @throws MWException
  79          * @param string $text
  80          * @return int
  81          */
  82         function addItem( $text ) {
  83                 if ( $this->mFrozen ) {
  84                         throw new MWException( __METHOD__ . ": Cannot add more items after sleep/wakeup" );
  85                 }
  86
  87                 $this->mItems[] = $text;
  88                 $this->mSize += strlen( $text );
  89                 $this->mDiffs = null; // later
  90                 return count( $this->mItems ) - 1;
  91         }
  92
  93         /**
  94          * @param string $key
  95          * @return string
  96          */
  97         function getItem( $key ) {
  98                 return $this->mItems[$key];
  99         }
 100
 101         /**
 102          * @param string $text
 103          */
 104         function setText( $text ) {
 105                 $this->mDefaultKey = $this->addItem( $text );
 106         }
 107
 108         /**
 109          * @return string
 110          */
 111         function getText() {
 112                 return $this->getItem( $this->mDefaultKey );
 113         }
 114
 115         /**
 116          * @throws MWException
 117          */
 118         function compress() {
 119                 if ( !function_exists( 'xdiff_string_rabdiff' ) ) {
 120                         throw new MWException( "Need xdiff 1.5+ support to write DiffHistoryBlob\n" );
 121                 }
 122                 if ( isset( $this->mDiffs ) ) {
 123                         // Already compressed
 124                         return;
 125                 }
 126                 if ( $this->mItems === [] ) {
 127                         return;
 128                 }
 129
 130                 // Create two diff sequences: one for main text and one for small text
 131                 $sequences = [
 132                         'small' => [
 133                                 'tail' => '',
 134                                 'diffs' => [],
 135                                 'map' => [],
 136                         ],
 137                         'main' => [
 138                                 'tail' => '',
 139                                 'diffs' => [],
 140                                 'map' => [],
 141                         ],
 142                 ];
 143                 $smallFactor = 0.5;
 144
 145                 $mItemsCount = count( $this->mItems );
 146                 for ( $i = 0; $i < $mItemsCount; $i++ ) {
 147                         $text = $this->mItems[$i];
 148                         if ( $i == 0 ) {
 149                                 $seqName = 'main';
 150                         } else {
 151                                 $mainTail = $sequences['main']['tail'];
 152                                 if ( strlen( $text ) < strlen( $mainTail ) * $smallFactor ) {
 153                                         $seqName = 'small';
 154                                 } else {
 155                                         $seqName = 'main';
 156                                 }
 157                         }
 158                         $seq =& $sequences[$seqName];
 159                         $tail = $seq['tail'];
 160                         $diff = $this->diff( $tail, $text );
 161                         $seq['diffs'][] = $diff;
 162                         $seq['map'][] = $i;
 163                         $seq['tail'] = $text;
 164                 }
 165                 unset( $seq ); // unlink dangerous alias
 166
 167                 // Knit the sequences together
 168                 $tail = '';
 169                 $this->mDiffs = [];
 170                 $this->mDiffMap = [];
 171                 foreach ( $sequences as $seq ) {
 172                         if ( $seq['diffs'] === [] ) {
 173                                 continue;
 174                         }
 175                         if ( $tail === '' ) {
 176                                 $this->mDiffs[] = $seq['diffs'][0];
 177                         } else {
 178                                 $head = $this->patch( '', $seq['diffs'][0] );
 179                                 $this->mDiffs[] = $this->diff( $tail, $head );
 180                         }
 181                         $this->mDiffMap[] = $seq['map'][0];
 182                         $diffsCount = count( $seq['diffs'] );
 183                         for ( $i = 1; $i < $diffsCount; $i++ ) {
 184                                 $this->mDiffs[] = $seq['diffs'][$i];
 185                                 $this->mDiffMap[] = $seq['map'][$i];
 186                         }
 187                         $tail = $seq['tail'];
 188                 }
 189         }
 190
 191         /**
 192          * @param string $t1
 193          * @param string $t2
 194          * @return string
 195          */
 196         function diff( $t1, $t2 ) {
 197                 # Need to do a null concatenation with warnings off, due to bugs in the current version of xdiff
 198                 # "String is not zero-terminated"
 199                 Wikimedia\suppressWarnings();
 200                 $diff = xdiff_string_rabdiff( $t1, $t2 ) . '';
 201                 Wikimedia\restoreWarnings();
 202                 return $diff;
 203         }
 204
 205         /**
 206          * @param string $base
 207          * @param string $diff
 208          * @return bool|string
 209          */
 210         function patch( $base, $diff ) {
 211                 if ( function_exists( 'xdiff_string_bpatch' ) ) {
 212                         Wikimedia\suppressWarnings();
 213                         $text = xdiff_string_bpatch( $base, $diff ) . '';
 214                         Wikimedia\restoreWarnings();
 215                         return $text;
 216                 }
 217
 218                 # Pure PHP implementation
 219
 220                 $header = unpack( 'Vofp/Vcsize', substr( $diff, 0, 8 ) );
 221
 222                 # Check the checksum if hash extension is available
 223                 $ofp = $this->xdiffAdler32( $base );
 224                 if ( $ofp !== false && $ofp !== substr( $diff, 0, 4 ) ) {
 225                         wfDebug( __METHOD__ . ": incorrect base checksum\n" );
 226                         return false;
 227                 }
 228                 if ( $header['csize'] != strlen( $base ) ) {
 229                         wfDebug( __METHOD__ . ": incorrect base length\n" );
 230                         return false;
 231                 }
 232
 233                 $p = 8;
 234                 $out = '';
 235                 while ( $p < strlen( $diff ) ) {
 236                         $x = unpack( 'Cop', substr( $diff, $p, 1 ) );
 237                         $op = $x['op'];
 238                         ++$p;
 239                         switch ( $op ) {
 240                                 case self::XDL_BDOP_INS:
 241                                         $x = unpack( 'Csize', substr( $diff, $p, 1 ) );
 242                                         $p++;
 243                                         $out .= substr( $diff, $p, $x['size'] );
 244                                         $p += $x['size'];
 245                                         break;
 246                                 case self::XDL_BDOP_INSB:
 247                                         $x = unpack( 'Vcsize', substr( $diff, $p, 4 ) );
 248                                         $p += 4;
 249                                         $out .= substr( $diff, $p, $x['csize'] );
 250                                         $p += $x['csize'];
 251                                         break;
 252                                 case self::XDL_BDOP_CPY:
 253                                         $x = unpack( 'Voff/Vcsize', substr( $diff, $p, 8 ) );
 254                                         $p += 8;
 255                                         $out .= substr( $base, $x['off'], $x['csize'] );
 256                                         break;
 257                                 default:
 258                                         wfDebug( __METHOD__ . ": invalid op\n" );
 259                                         return false;
 260                         }
 261                 }
 262                 return $out;
 263         }
 264
 265         /**
 266          * Compute a binary "Adler-32" checksum as defined by LibXDiff, i.e. with
 267          * the bytes backwards and initialised with 0 instead of 1. See T36428.
 268          *
 269          * @param string $s
 270          * @return string|bool False if the hash extension is not available
 271          */
 272         function xdiffAdler32( $s ) {
 273                 if ( !function_exists( 'hash' ) ) {
 274                         return false;
 275                 }
 276
 277                 static $init;
 278                 if ( $init === null ) {
 279                         $init = str_repeat( "\xf0", 205 ) . "\xee" . str_repeat( "\xf0", 67 ) . "\x02";
 280                 }
 281
 282                 // The real Adler-32 checksum of $init is zero, so it initialises the
 283                 // state to zero, as it is at the start of LibXDiff's checksum
 284                 // algorithm. Appending the subject string then simulates LibXDiff.
 285                 return strrev( hash( 'adler32', $init . $s, true ) );
 286         }
 287
 288         function uncompress() {
 289                 if ( !$this->mDiffs ) {
 290                         return;
 291                 }
 292                 $tail = '';
 293                 $mDiffsCount = count( $this->mDiffs );
 294                 for ( $diffKey = 0; $diffKey < $mDiffsCount; $diffKey++ ) {
 295                         $textKey = $this->mDiffMap[$diffKey];
 296                         $text = $this->patch( $tail, $this->mDiffs[$diffKey] );
 297                         $this->mItems[$textKey] = $text;
 298                         $tail = $text;
 299                 }
 300         }
 301
 302         /**
 303          * @return array
 304          */
 305         function __sleep() {
 306                 $this->compress();
 307                 if ( $this->mItems === [] ) {
 308                         $info = false;
 309                 } else {
 310                         // Take forward differences to improve the compression ratio for sequences
 311                         $map = '';
 312                         $prev = 0;
 313                         foreach ( $this->mDiffMap as $i ) {
 314                                 if ( $map !== '' ) {
 315                                         $map .= ',';
 316                                 }
 317                                 $map .= $i - $prev;
 318                                 $prev = $i;
 319                         }
 320                         $info = [
 321                                 'diffs' => $this->mDiffs,
 322                                 'map' => $map
 323                         ];
 324                 }
 325                 if ( isset( $this->mDefaultKey ) ) {
 326                         $info['default'] = $this->mDefaultKey;
 327                 }
 328                 $this->mCompressed = gzdeflate( serialize( $info ) );
 329                 return [ 'mCompressed' ];
 330         }
 331
 332         function __wakeup() {
 333                 // addItem() doesn't work if mItems is partially filled from mDiffs
 334                 $this->mFrozen = true;
 335                 $info = unserialize( gzinflate( $this->mCompressed ) );
 336                 unset( $this->mCompressed );
 337
 338                 if ( !$info ) {
 339                         // Empty object
 340                         return;
 341                 }
 342
 343                 if ( isset( $info['default'] ) ) {
 344                         $this->mDefaultKey = $info['default'];
 345                 }
 346                 $this->mDiffs = $info['diffs'];
 347                 if ( isset( $info['base'] ) ) {
 348                         // Old format
 349                         $this->mDiffMap = range( 0, count( $this->mDiffs ) - 1 );
 350                         array_unshift( $this->mDiffs,
 351                                 pack( 'VVCV', 0, 0, self::XDL_BDOP_INSB, strlen( $info['base'] ) ) .
 352                                 $info['base'] );
 353                 } else {
 354                         // New format
 355                         $map = explode( ',', $info['map'] );
 356                         $cur = 0;
 357                         $this->mDiffMap = [];
 358                         foreach ( $map as $i ) {
 359                                 $cur += $i;
 360                                 $this->mDiffMap[] = $cur;
 361                         }
 362                 }
 363                 $this->uncompress();
 364         }
 365
 366         /**
 367          * Helper function for compression jobs
 368          * Returns true until the object is "full" and ready to be committed
 369          *
 370          * @return bool
 371          */
 372         function isHappy() {
 373                 return $this->mSize < $this->mMaxSize
 374                         && count( $this->mItems ) < $this->mMaxCount;
 375         }
 376
 377 }