cinelerra-5.1/cinelerra/undostack.C

   1
   2 /*
   3  * CINELERRA
   4  * Copyright (C) 2008 Adam Williams <broadcast at earthling dot net>
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  */
  21
  22 #include "bcsignals.h"
  23 #include "bctimer.h"
  24 #include "clip.h"
  25 #include "cstrdup.h"
  26 #include "filexml.h"
  27 #include "undostack.h"
  28 #include <string.h>
  29
  30 // undo can be incremental or direct, from key to current
  31 //#define UNDO_INCREMENTAL
  32
  33 UndoStack::UndoStack() : List<UndoStackItem>()
  34 {
  35         current = 0;
  36 }
  37
  38 UndoStack::~UndoStack()
  39 {
  40 }
  41
  42 UndoStackItem *UndoStack::get_current_undo()
  43 {
  44         UndoStackItem *item = current;
  45         if( item &&  (number_of(item) & 1) ) item = item->previous;
  46         if( item && !(number_of(item) & 1) ) item = item->previous;
  47         return item;
  48 }
  49
  50 UndoStackItem *UndoStack::get_current_redo()
  51 {
  52         UndoStackItem *item = current ? current : first;
  53         if( item &&  (number_of(item) & 1) ) item = item->next;
  54         if( item && !(number_of(item) & 1) ) item = item->next;
  55         return item;
  56 }
  57
  58
  59 UndoStackItem* UndoStack::push()
  60 {
  61 // delete oldest 2 undos if necessary
  62         if( total() > UNDOLEVELS ) {
  63                 UndoStackItem *item = first, *key = item;
  64 #ifdef UNDO_INCREMENTAL
  65                 for( int i=2; --i>=0; item=item->next );
  66 #else
  67                 for( int i=2; --i>=0; item=item->next )
  68                         if( item->is_key() ) key = item;
  69 #endif
  70                 char *data = !item->is_key() ? key->get_data() : 0;
  71                 while( first != item ) {
  72                         if( current == first ) current = first->next;
  73                         delete first;
  74                 }
  75                 if( data ) {
  76                         item->set_data(data);
  77                         delete [] data;
  78                 }
  79         }
  80
  81 // current is only 0 if before first undo
  82         current = current ? insert_after(current) : insert_before(first);
  83 // delete future undos if necessary
  84         while( current->next ) remove(last);
  85         return current;
  86 }
  87
  88 UndoStackItem* UndoStack::pull_next()
  89 {
  90 // use first entry if none
  91         if( !current )
  92                 current = first;
  93         else
  94 // use next entry if there is a next entry
  95         if( current->next )
  96                 current = NEXT;
  97 // don't change current if there is no next entry
  98         else
  99                 return 0;
 100
 101         return current;
 102 }
 103
 104
 105 void UndoStack::dump(FILE *fp)
 106 {
 107         fprintf(fp,"UndoStack::dump\n");
 108         UndoStackItem *current = last;
 109 // Dump most recent
 110         for( int i=0; current && i<32; ++i,current=PREVIOUS ) {
 111                 fprintf(fp,"%c %2d %14p %-24s %8d %04jx %c\n", current->is_key() ? 'k' : ' ',
 112                         i, current, current->get_description(), current->get_size(),
 113                         current->get_flags(), current == this->current ? '*' : ' ');
 114 //char fn[BCSTRLEN]; sprintf(fn,"/tmp/undo%d", i); FILE *fp = fopen(fn,"w");
 115 //if( fp ) { char *cp=current->get_data(); fwrite(cp,strlen(cp),1,fp); fclose(fp); delete [] cp; }
 116         }
 117 }
 118
 119 class undo_record {
 120 public:
 121         int32_t new_ofs;
 122         int32_t new_len;
 123         int32_t old_len;
 124 };
 125
 126 static unsigned char* apply_difference(unsigned char *before, int before_len,
 127                 unsigned char *patch, int patch_len, int *result_len)
 128 {
 129         XMLBuffer xbfr((const char *)patch, patch_len, 0);
 130         int32_t len = 0;
 131         xbfr.read((char *)&len, sizeof(len));
 132         char *result = new char[len];
 133         char *rp = result, *bp = (char*)before;
 134
 135         while( xbfr.itell() < patch_len ) {
 136                 undo_record urecd;
 137                 xbfr.read((char*)&urecd, sizeof(urecd));
 138                 int ofs = rp - result;
 139                 if( urecd.new_ofs > ofs ) {
 140                         int sz = urecd.new_ofs - ofs;
 141                         memcpy(rp, bp, sz);
 142                         bp += sz;  rp += sz;
 143                 }
 144                 if( urecd.new_len > 0 )
 145                         xbfr.read(rp, urecd.new_len);
 146                 bp += urecd.old_len;  rp += urecd.new_len;
 147         }
 148
 149 // All data from before_ptr to end of result buffer is identical
 150         int sz = bp - (char *)before;
 151         if( (before_len-=sz) > 0 ) {
 152                 memcpy(rp, bp, before_len);
 153                 rp += before_len;
 154         }
 155
 156         *result_len = rp - result;
 157         return (unsigned char *)result;
 158 }
 159
 160 UndoStackItem::UndoStackItem()
 161  : ListItem<UndoStackItem>()
 162 {
 163         description = data = 0;
 164         data_size = 0;
 165         key = 0;
 166         creator = 0;
 167         session_filename = 0;
 168 }
 169
 170 UndoStackItem::~UndoStackItem()
 171 {
 172         delete [] description;
 173         delete [] data;
 174         delete [] session_filename;
 175 }
 176
 177 void UndoStackItem::set_description(char *description)
 178 {
 179         delete [] this->description;
 180         this->description= 0;
 181         this->description = new char[strlen(description) + 1];
 182         strcpy(this->description, description);
 183 }
 184
 185 void UndoStackItem::set_filename(char *filename)
 186 {
 187         delete [] session_filename;
 188         this->session_filename = cstrdup(filename);
 189 }
 190
 191 char* UndoStackItem::get_filename()
 192 {
 193         return session_filename;
 194 }
 195
 196
 197 const char* UndoStackItem::get_description()
 198 {
 199         if( description )
 200                 return description;
 201         else
 202                 return "";
 203 }
 204
 205 // undo diff
 206
 207 UndoHash::UndoHash(char *txt, int len, UndoHash *nxt)
 208 {
 209         this->txt = txt;
 210         this->len = len;
 211         this->nxt = nxt;
 212         line[va] = line[vb] = -1;
 213         occurs[va] = occurs[vb] = 0;
 214 }
 215 UndoHash::~UndoHash()
 216 {
 217 }
 218
 219 UndoHashTable::UndoHashTable()
 220 {
 221         for( int i=0; i<hash_sz; ++i ) table[i] = 0;
 222         bof = new UndoHash(0, 0, 0);
 223         eof = new UndoHash(0, 0, 0);
 224 }
 225 UndoHashTable::~UndoHashTable()
 226 {
 227         delete bof;
 228         delete eof;
 229         for( int i=0; i<hash_sz; ++i ) {
 230                 for( UndoHash *nxt=0, *hp=table[i]; hp; hp=nxt ) {
 231                         nxt = hp->nxt;  delete hp;
 232                 }
 233         }
 234 }
 235
 236 UndoHash *UndoHashTable::add(char *txt, int len)
 237 {
 238         uint8_t *bp = (uint8_t *)txt;
 239         int v = 0;
 240         for( int i=len; --i>=0; ++bp ) {
 241                 v = (v<<1) + *bp;
 242                 v = (v + (v>>hash_sz2)) & hash_sz1;
 243         }
 244         UndoHash *hp = table[v];
 245         while( hp && strncmp(hp->txt,txt,len) ) hp = hp->nxt;
 246         if( !hp ) {
 247                 hp = new UndoHash(txt, len, table[v]);
 248                 table[v] = hp;
 249         }
 250         return hp;
 251 }
 252
 253 UndoLine::UndoLine(UndoHash *hash, char *tp)
 254 {
 255         this->txt = tp;  this->len = 0;
 256         this->hash = hash;
 257         hash->occurs[va] = hash->occurs[vb] = 1;
 258 }
 259
 260 UndoLine::UndoLine(UndoHashTable *hash, char *txt, int len)
 261 {
 262         this->txt = txt;  this->len = len;
 263         this->hash = hash->add(txt, len);
 264 }
 265 UndoLine::~UndoLine()
 266 {
 267 }
 268
 269 int UndoLine::eq(UndoLine *ln)
 270 {
 271         return hash == ln->hash ? 1 : 0;
 272 }
 273
 274 void UndoVersion::scan_lines(UndoHashTable *hash, char *sp, char *ep)
 275 {
 276         for( int line=1; sp<ep; ++line ) {
 277                 char *txt = sp;
 278                 while( sp<ep && *sp++ != '\n' );
 279                 UndoLine *ln = new UndoLine(hash, txt, sp-txt);
 280                 ln->hash->line[ver] = line;
 281                 ++ln->hash->occurs[ver];
 282                 append(ln);
 283         }
 284 }
 285
 286
 287 void UndoStackItem::set_data(char *data)
 288 {
 289         delete [] this->data;  this->data = 0;
 290         this->data_size = 0;   this->key = 0;
 291         int data_size = strlen(data)+1;
 292
 293         UndoStackItem *current = this;
 294 // Search for key buffer within interval
 295         for( int i=UNDO_KEY_INTERVAL; --i>=0 && current && !current->key; current=PREVIOUS );
 296
 297         int need_key = current ? 0 : 1;
 298 // setting need_key = 1 forces all undo data items to key (not diffd)
 299 //      int need_key = 1;
 300         char *prev = 0;  int prev_size = 0;
 301         if( !need_key ) {
 302 #ifdef UNDO_INCREMENTAL
 303                 prev = previous->get_data();
 304                 prev_size = prev ? strlen(prev)+1 : 0;
 305 #else
 306                 prev = current->data;
 307                 prev_size = current->data_size;
 308 #endif
 309                 int min_size = data_size/16;
 310 // if the previous is a sizable incremental diff
 311                 if( previous && !previous->key &&
 312                     previous->data_size > min_size ) {
 313 //  and this minimum diff distance is a lot different, need key
 314                         int dist = abs(data_size - prev_size);
 315                         if( abs(dist - previous->data_size) > min_size )
 316                                 need_key = 1;
 317                 }
 318         }
 319         if( !need_key ) {
 320                 int bfr_size = BCTEXTLEN;
 321                 char *bfr = new char[bfr_size];
 322                 XMLBuffer xbfr(bfr_size, bfr, 1);
 323                 xbfr.write((char*)&data_size, sizeof(data_size));
 324                 UndoHashTable hash;
 325                 UndoVersion alines(va), blines(vb);
 326                 char *asp = data, *aep = asp + data_size-1;
 327                 char *bsp = prev, *bep = bsp + prev_size-1;
 328                 alines.append(new UndoLine(hash.bof, asp));
 329                 blines.append(new UndoLine(hash.bof, bsp));
 330                 alines.scan_lines(&hash, asp, aep);
 331                 blines.scan_lines(&hash, bsp, bep);
 332                 int asz = alines.size(), bsz = blines.size();
 333 // trim matching suffix
 334                 while( asz > 0 && bsz > 0 && alines[asz-1]->eq(blines[bsz-1]) ) {
 335                         aep = alines[--asz]->txt;  alines.remove_object();
 336                         bep = blines[--bsz]->txt;  blines.remove_object();
 337                 }
 338 // include for matching last item
 339                 alines.append(new UndoLine(hash.eof, aep));
 340                 blines.append(new UndoLine(hash.eof, bep));
 341                 hash.eof->line[va] = asz++;
 342                 hash.eof->line[vb] = bsz++;
 343
 344                 int ai = 0, bi = 0;
 345                 while( ai < asz || bi < bsz ) {
 346 // skip running match
 347                         if( alines[ai]->eq(blines[bi]) ) { ++ai;  ++bi;  continue; }
 348                         char *adp = alines[ai]->txt, *bdp = blines[bi]->txt;
 349 // find best unique match
 350                         int ma = asz, mb = bsz;
 351                         int mx = ma + mb + 1;
 352                         for( int ia=ai; ia<asz && ia-ai<mx; ++ia ) {
 353                                 UndoHash *ah = alines[ia]->hash;
 354                                 if( ah->occurs[va] != 1 || ah->occurs[vb] != 1 ) continue;
 355                                 int m = (ah->line[va] - ai) + (ah->line[vb] - bi);
 356                                 if( m >= mx ) continue;
 357                                 ma = ah->line[va];  mb = ah->line[vb];  mx = m;
 358                         }
 359 // trim suffix
 360                         while( ma > 0 && mb > 0 && alines[ma-1]->eq(blines[mb-1]) ) { --ma;  --mb; }
 361                         char *ap = alines[ma]->txt, *bp = blines[mb]->txt;
 362                         ai = ma;  bi = mb;
 363                         undo_record urecd;
 364                         urecd.new_ofs = adp - data;
 365                         urecd.new_len = ap - adp;
 366                         urecd.old_len = bp - bdp;
 367                         xbfr.write((const char*)&urecd, sizeof(urecd));
 368                         xbfr.write((const char*)adp, urecd.new_len);
 369                 }
 370
 371                 int64_t pos = xbfr.otell();
 372                 if( abs(data_size-prev_size) < pos/2 ) {
 373                         this->data = new char[this->data_size = pos];
 374                         xbfr.iseek(0);
 375                         xbfr.read(this->data, pos);
 376 #if 1
 377                         int test_size = 0;
 378                         char *test_data = (char*)apply_difference(
 379                                 (unsigned char *)prev, prev_size,
 380                                 (unsigned char *)this->data, this->data_size,
 381                                 &test_size);
 382                         if( test_size != data_size || memcmp(test_data, data, test_size) ) {
 383                                 printf("UndoStackItem::set_data: *** incremental undo failed!\n");
 384                                 delete [] this->data;  this->data = 0;  this->data_size = 0;
 385                                 need_key = 1;
 386                         }
 387                         delete [] test_data;
 388 #endif
 389                 }
 390                 else
 391                         need_key = 1;
 392         }
 393
 394 #ifdef UNDO_INCREMENTAL
 395         delete [] prev;
 396 #endif
 397         if( need_key ) {
 398                 this->key = 1;
 399                 this->data = new char[this->data_size = data_size];
 400                 memcpy(this->data, data, this->data_size);
 401         }
 402 }
 403
 404 char* UndoStackItem::get_data()
 405 {
 406 // Find latest key buffer
 407         UndoStackItem *current = this;
 408         while( current && !current->key )
 409                 current = PREVIOUS;
 410         if( !current ) {
 411                 printf("UndoStackItem::get_data: no key buffer found!\n");
 412                 return 0;
 413         }
 414
 415 // This is the key buffer
 416         if( current == this ) {
 417                 char *result = new char[data_size];
 418                 memcpy(result, data, data_size);
 419                 return result;
 420         }
 421 #ifdef UNDO_INCREMENTAL
 422 // Get key buffer
 423         char *current_data = current->get_data();
 424         int current_size = current->data_size;
 425         current = NEXT;
 426         while( current ) {
 427 // Do incremental updates
 428                 int new_size;
 429                 char *new_data = (char*)apply_difference(
 430                         (unsigned char*)current_data, current_size,
 431                         (unsigned char*)current->data, current->data_size,
 432                         &new_size);
 433                 delete [] current_data;
 434
 435                 if( current == this )
 436                         return new_data;
 437                 current_data = new_data;
 438                 current_size = new_size;
 439                 current = NEXT;
 440         }
 441 // Never hit this object.
 442         delete [] current_data;
 443         printf("UndoStackItem::get_data: lost starting object!\n");
 444         return 0;
 445 #else
 446         int new_size;
 447         char *new_data = (char*)apply_difference(
 448                 (unsigned char*)current->data, current->data_size,
 449                 (unsigned char*)this->data, this->data_size, &new_size);
 450         return new_data;
 451 #endif
 452 }
 453
 454 int UndoStackItem::is_key()
 455 {
 456         return key;
 457 }
 458
 459 int UndoStackItem::get_size()
 460 {
 461         return data_size;
 462 }
 463
 464 void UndoStackItem::set_flags(uint64_t flags)
 465 {
 466         this->load_flags = flags;
 467 }
 468
 469 uint64_t UndoStackItem::get_flags()
 470 {
 471         return load_flags;
 472 }
 473
 474 void UndoStackItem::set_creator(void *creator)
 475 {
 476         this->creator = creator;
 477 }
 478
 479 void* UndoStackItem::get_creator()
 480 {
 481         return creator;
 482 }
 483
 484 void UndoStackItem::save(FILE *fp)
 485 {
 486         fwrite(&key,1,sizeof(key),fp);
 487         fwrite(&load_flags,1,sizeof(load_flags),fp);
 488         fwrite(&data_size,1,sizeof(data_size),fp);
 489         fwrite(data,1,data_size,fp);
 490         for( char *bp=session_filename; *bp; ++bp ) fputc(*bp, fp);
 491         fputc(0, fp);
 492         for( char *bp=description; *bp; ++bp ) fputc(*bp, fp);
 493         fputc(0, fp);
 494 }
 495
 496 void UndoStackItem::load(FILE *fp)
 497 {
 498         fread(&key,1,sizeof(key),fp);
 499         fread(&load_flags,1,sizeof(load_flags),fp);
 500         fread(&data_size,1,sizeof(data_size),fp);
 501         fread(data=new char[data_size],1,data_size,fp);
 502         char filename[BCTEXTLEN], descr[BCTEXTLEN];
 503         char *bp = filename, *ep = bp+sizeof(filename)-1;
 504         for( int ch; bp<ep && (ch=fgetc(fp))>0; ++bp ) *bp = ch;
 505         *bp = 0;
 506         session_filename = cstrdup(filename);
 507         bp = descr;  ep = bp+sizeof(descr)-1;
 508         for( int ch; bp<ep && (ch=fgetc(fp))>0; ++bp ) *bp = ch;
 509         *bp = 0;
 510         description = cstrdup(descr);
 511 //printf("read undo key=%d,flags=%jx,data_size=%d,data=%p,file=%s,descr=%s\n",
 512 // key, load_flags, data_size, data, session_filename, description);
 513 }
 514
 515 void UndoStack::save(FILE *fp)
 516 {
 517         for( UndoStackItem *item=first; item; item=item->next ) {
 518                 int is_current = item == current ? 1 : 0;
 519                 fwrite(&is_current,1,sizeof(is_current),fp);
 520                 item->save(fp);
 521 //              if( item == current ) break; // stop at current
 522         }
 523 }
 524
 525 void UndoStack::load(FILE *fp)
 526 {
 527         while( last ) delete last;
 528         current = 0;
 529         UndoStackItem *current_item = 0;
 530         int is_current = 0;
 531         while( fread(&is_current,1,sizeof(is_current),fp) == sizeof(is_current) ) {
 532                 UndoStackItem *item = push();
 533                 item->load(fp);
 534                 if( is_current ) current_item = item;
 535         }
 536         if( current_item ) current = current_item;
 537 }
 538