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 "undostack.h"
  27 #include <string.h>
  28
  29 UndoStack::UndoStack() : List<UndoStackItem>()
  30 {
  31         current = 0;
  32 }
  33
  34 UndoStack::~UndoStack()
  35 {
  36 }
  37
  38 UndoStackItem *UndoStack::get_current_undo()
  39 {
  40         UndoStackItem *item = current;
  41         if( item &&  (number_of(item) & 1) ) item = item->previous;
  42         if( item && !(number_of(item) & 1) ) item = item->previous;
  43         return item;
  44 }
  45
  46 UndoStackItem *UndoStack::get_current_redo()
  47 {
  48         UndoStackItem *item = current ? current : first;
  49         if( item &&  (number_of(item) & 1) ) item = item->next;
  50         if( item && !(number_of(item) & 1) ) item = item->next;
  51         return item;
  52 }
  53
  54
  55 UndoStackItem* UndoStack::push()
  56 {
  57 // current is only 0 if before first undo
  58         if( current )
  59                 current = insert_after(current);
  60         else
  61                 current = insert_before(first);
  62
  63 // delete future undos if necessary
  64         if( current && current->next ) {
  65                 while( current->next ) remove(last);
  66         }
  67
  68 // delete oldest 2 undos if necessary
  69         if( total() > UNDOLEVELS ) {
  70                 for( int i=0; i<2; ++i ) {
  71                         UndoStackItem *second = first->next;
  72                         char *temp_data = 0;
  73
  74
  75                         if( !second->is_key() ) {
  76                                 temp_data = second->get_data();
  77                         }
  78                         remove(first);
  79
  80 // Convert new first to key buffer.
  81                         if( !second->is_key() ) {
  82                                 second->set_data(temp_data);
  83                         }
  84                         delete [] temp_data;
  85                 }
  86         }
  87
  88         return current;
  89 }
  90
  91 UndoStackItem* UndoStack::pull_next()
  92 {
  93 // use first entry if none
  94         if( !current )
  95                 current = first;
  96         else
  97 // use next entry if there is a next entry
  98         if( current->next )
  99                 current = NEXT;
 100 // don't change current if there is no next entry
 101         else
 102                 return 0;
 103
 104         return current;
 105 }
 106
 107
 108 void UndoStack::dump(FILE *fp)
 109 {
 110         fprintf(fp,"UndoStack::dump\n");
 111         UndoStackItem *current = last;
 112 // Dump most recent
 113         for( int i=0; current && i<16; ++i,current=PREVIOUS ) {
 114                 fprintf(fp,"  %d %p %s %04jx %c\n", i, current, current->get_description(),
 115                         current->get_flags(), current == this->current ? '*' : ' ');
 116 //char fn[BCSTRLEN]; sprintf(fn,"/tmp/undo%d", i); FILE *fp = fopen(fn,"w");
 117 //if( fp ) { char *cp=current->get_data(); fwrite(cp,strlen(cp),1,fp); fclose(fp); delete [] cp; }
 118         }
 119 }
 120
 121
 122
 123 // These difference routines are straight out of the Heroinediff/Heroinepatch
 124 // utilities.
 125
 126
 127 // We didn't want to use the diff program because that isn't efficient enough
 128 // to compress EDL's.  This program also handles binary data.
 129
 130 // Algorithm 1:
 131 // Search from beginning for first difference.
 132 // Count everything up to first difference as equal.
 133 // Determine length of different block by searching for transposition with most
 134 // similar characters.
 135 // For every byte in different block, search for occurrence of
 136 // transposed copy longer than a record header in remaining old buffer.
 137 // If no match is found, add 1 to the different block length and try the next
 138 // byte.  Once the most similar match is found, store the changed data leading up to it in the
 139 // difference record.
 140 // This can be real slow if there is a large transposition early in the file.
 141
 142 // Algorithm 2:
 143 // Search backwards from end of both files for last difference.
 144 // Count all data from last same bytes as a transposition.
 145 // Search forwards from start of both files until last same bytes
 146 // for differences.
 147
 148
 149 // Minimum size of transposed block.
 150 // Smaller transpositions should be included in the same difference record.
 151 #define MIN_TRANS 16
 152
 153 // Format for difference records.
 154 // The first 4 bytes are the offset of the change.
 155 // The next 4 bytes are the number of bytes of new data.
 156 // The next 4 bytes are the number of bytes of old data replaced.
 157 // The new data follows.
 158 static void append_record(unsigned char **result,
 159         int *result_size,
 160         unsigned char *new_data,
 161         int new_offset,
 162         int new_size,
 163         int old_size)
 164 {
 165         if( new_size || old_size ) {
 166                 int record_size = new_size + 12;
 167                 unsigned char *new_result = new unsigned char[(*result_size) + record_size];
 168                 memcpy(new_result, (*result), (*result_size));
 169                 delete [] (*result);
 170
 171                 unsigned char *new_result_ptr = new_result + (*result_size);
 172                 *(int32_t*)new_result_ptr = new_offset;
 173                 new_result_ptr += 4;
 174                 *(int32_t*)new_result_ptr = new_size;
 175                 new_result_ptr += 4;
 176                 *(int32_t*)new_result_ptr = old_size;
 177                 new_result_ptr += 4;
 178
 179                 memcpy(new_result_ptr, new_data, new_size);
 180                 (*result_size) += record_size;
 181                 (*result) = new_result;
 182         }
 183 }
 184
 185
 186
 187 static unsigned char* get_difference_fast(unsigned char *before,
 188                 int before_len,
 189                 unsigned char *after,
 190                 int after_len,
 191                 int *result_len,
 192                 int verbose)
 193 {
 194         unsigned char *result = new unsigned char[4];
 195         *result_len = 4;
 196
 197 // Store size of new buffer
 198         *(int32_t*)result = after_len;
 199
 200
 201
 202 // Get last different bytes
 203         unsigned char *last_difference_after = after + after_len - 1;
 204         unsigned char *last_difference_before = before + before_len - 1;
 205         for(;;) {
 206                 if( last_difference_after < after ||
 207                         last_difference_before < before ) break;
 208                 if( *last_difference_after != *last_difference_before ) {
 209                         break;
 210                 }
 211                 last_difference_after--;
 212                 last_difference_before--;
 213         }
 214         last_difference_after++;
 215         last_difference_before++;
 216
 217         int done = 0;
 218         unsigned char *before_ptr = before;
 219         unsigned char *after_ptr = after;
 220         unsigned char *before_end = before + before_len;
 221         unsigned char *after_end = after + after_len;
 222
 223 // Scan forward for first difference
 224         while( !done ) {
 225                 if( before_ptr < before_end &&
 226                         after_ptr < after_end ) {
 227 // Both characters equal
 228                         if( *before_ptr == *after_ptr &&
 229                                 before_ptr < last_difference_before &&
 230                                 after_ptr < last_difference_after ) {
 231                                 before_ptr++;
 232                                 after_ptr++;
 233                         }
 234                         else {
 235 // Characters differ
 236 // Get length of difference.
 237                                 unsigned char *before_difference_start = before_ptr;
 238                                 unsigned char *after_difference_start = after_ptr;
 239
 240
 241                                 while( *before_ptr != *after_ptr &&
 242                                     before_ptr < last_difference_before &&
 243                                     after_ptr < last_difference_after ) {
 244                                         before_ptr++;
 245                                         after_ptr++;
 246                                 }
 247
 248 // Finished comparing if either pointer hits its last difference
 249                                 if( before_ptr >= last_difference_before ||
 250                                         after_ptr >= last_difference_after ) {
 251                                         done = 1;
 252                                         before_ptr = last_difference_before;
 253                                         after_ptr = last_difference_after;
 254                                 }
 255
 256                                 int after_start = after_difference_start - after;
 257                                 int before_start = before_difference_start - before;
 258                                 int after_len = after_ptr - after_difference_start;
 259                                 int before_len = before_ptr - before_difference_start;
 260
 261                                 if( verbose ) {
 262                                         char string[1024];
 263                                         memcpy(string, after_difference_start, MIN(after_len, 40));
 264                                         string[MIN(after_len, 40)] = 0;
 265                                         printf("after_offset=0x%x before_offset=0x%x after_size=%d before_size=%d \"%s\"\n",
 266                                                 after_start, before_start, after_len, before_len, string);
 267                                 }
 268
 269 // Create difference record
 270                                 append_record(&result, result_len, after_difference_start,
 271                                         after_start, after_len, before_len);
 272                         }
 273                 }
 274                 else
 275                         done = 1;
 276         }
 277         return result;
 278 }
 279
 280 static void get_record(unsigned char **patch_ptr, unsigned char *patch_end,
 281         unsigned char **after_data, int *after_offset, int *after_size, int *before_size)
 282 {
 283         (*after_data) = 0;
 284         if( (*patch_ptr) < patch_end ) {
 285                 (*after_offset) = *(int32_t*)(*patch_ptr);  (*patch_ptr) += 4;
 286                 (*after_size) = *(int32_t*)(*patch_ptr);    (*patch_ptr) += 4;
 287                 (*before_size) = *(int32_t*)(*patch_ptr);   (*patch_ptr) += 4;
 288                 (*after_data) = (*patch_ptr);               (*patch_ptr) += (*after_size);
 289         }
 290 }
 291
 292
 293 static unsigned char* apply_difference(unsigned char *before, int before_len,
 294                 unsigned char *patch, int patch_len, int *result_len)
 295 {
 296         unsigned char *patch_ptr = patch;
 297         *result_len = *(int32_t*)patch_ptr;
 298         patch_ptr += 4;
 299         unsigned char *patch_end = patch + patch_len;
 300         //unsigned char *before_end = before + before_len;
 301
 302         unsigned char *result = new unsigned char[*result_len];
 303         unsigned char *result_ptr = result;
 304         unsigned char *result_end = result + *result_len;
 305         unsigned char *before_ptr = before;
 306
 307         int done = 0;
 308         while( !done ) {
 309                 unsigned char *after_data;
 310                 int after_offset, after_size, before_size;
 311
 312                 get_record(&patch_ptr, patch_end,
 313                         &after_data, &after_offset, &after_size, &before_size);
 314
 315                 if( after_data ) {
 316                         int result_offset = result_ptr - result;
 317                         if( after_offset > result_offset ) {
 318                                 int skip_size = after_offset - result_offset;
 319                                 memcpy(result_ptr, before_ptr, skip_size);
 320                                 result_ptr += skip_size;
 321                                 before_ptr += skip_size;
 322                         }
 323                         memcpy(result_ptr, after_data, after_size);
 324                         result_ptr += after_size;
 325                         before_ptr += before_size;
 326                 }
 327                 else {
 328 // All data from before_ptr to end of result buffer is identical
 329                         if( result_end - result_ptr > 0 )
 330                                 memcpy(result_ptr, before_ptr, result_end - result_ptr);
 331                         done = 1;
 332                 }
 333         }
 334
 335         return result;
 336 }
 337
 338
 339 UndoStackItem::UndoStackItem()
 340  : ListItem<UndoStackItem>()
 341 {
 342         description = data = 0;
 343         data_size = 0;
 344         key = 0;
 345         creator = 0;
 346         session_filename = 0;
 347 }
 348
 349 UndoStackItem::~UndoStackItem()
 350 {
 351         delete [] description;
 352         delete [] data;
 353         delete [] session_filename;
 354 }
 355
 356 void UndoStackItem::set_description(char *description)
 357 {
 358         delete [] this->description;
 359         this->description= 0;
 360         this->description = new char[strlen(description) + 1];
 361         strcpy(this->description, description);
 362 }
 363
 364 void UndoStackItem::set_filename(char *filename)
 365 {
 366         delete [] session_filename;
 367         this->session_filename = cstrdup(filename);
 368 }
 369
 370 char* UndoStackItem::get_filename()
 371 {
 372         return session_filename;
 373 }
 374
 375
 376 const char* UndoStackItem::get_description()
 377 {
 378         if( description )
 379                 return description;
 380         else
 381                 return "";
 382 }
 383
 384 int UndoStackItem::has_data()
 385 {
 386         return data_size ? 1 : 0;
 387 }
 388
 389 void UndoStackItem::set_data(char *data)
 390 {
 391         delete [] this->data;
 392         this->data = 0;
 393         this->data_size = 0;
 394
 395 // Search for key buffer within interval
 396         int need_key = 1;
 397         UndoStackItem *current = this;
 398         this->key = 0;
 399         for( int i=0; i<UNDO_KEY_INTERVAL && current; ++i ) {
 400                 if( current->key && current->has_data() ) {
 401                         need_key = 0;
 402                         break;
 403                 }
 404                 else
 405                         current = PREVIOUS;
 406         }
 407
 408         int new_size = strlen(data) + 1;
 409
 410         if( !need_key ) {
 411 // Reconstruct previous data for difference
 412                 char *prev_buffer = previous->get_data();
 413                 int prev_size = prev_buffer ? strlen(prev_buffer) + 1 : 0;
 414 // Timer timer;
 415 // timer.update();
 416 // printf("UndoStackItem::set_data 1\n");
 417                 this->data = (char*)get_difference_fast((unsigned char*)prev_buffer,
 418                         prev_size,
 419                         (unsigned char*)data,
 420                         new_size,
 421                         &this->data_size,
 422                         0);
 423 //printf("UndoStackItem::set_data 2 %jd\n", timer.get_difference());
 424
 425 // Testing
 426 // FILE *test1 = fopen("/tmp/undo1", "w");
 427 // fwrite(prev_buffer, prev_size, 1, test1);
 428 // fclose(test1);
 429 // FILE *test2 = fopen("/tmp/undo2", "w");
 430 // fwrite(data, new_size, 1, test2);
 431 // fclose(test2);
 432 // FILE *test3 = fopen("/tmp/undo2.diff", "w");
 433 // fwrite(this->data, this->data_size, 1, test3);
 434 // fclose(test3);
 435 //
 436 //printf("UndoStackItem::set_data 3 %d %d\n", new_size, this->data_size);
 437
 438 // Diff was bigger than original.
 439 // Happens if a lot of tiny changes happened and the record headers
 440 // took more space than the changes.
 441                 if( this->data_size > new_size ) {
 442                         delete [] this->data;
 443                         this->data_size = 0;
 444                         need_key = 1;
 445                 }
 446                 else {
 447 // Reconstruct current data from difference
 448                         int test_size;
 449                         char *test_buffer = (char*)apply_difference((unsigned char*)prev_buffer,
 450                                 prev_size,
 451                                 (unsigned char*)this->data,
 452                                 this->data_size,
 453                                 &test_size);
 454                         if( test_size != new_size ||
 455                                 memcmp(test_buffer, data, test_size) ) {
 456 // FILE *test1 = fopen("/tmp/undo1", "w");
 457 // fwrite(prev_buffer, prev_size, 1, test1);
 458 // fclose(test1);
 459 // FILE *test2 = fopen("/tmp/undo2", "w");
 460 // fwrite(data, new_size, 1, test2);
 461 // fclose(test2);
 462 // FILE *test3 = fopen("/tmp/undo2.diff", "w");
 463 // fwrite(this->data, this->data_size, 1, test3);
 464 // fclose(test3);
 465 // FILE *test4 = fopen("/tmp/undo3", "w");
 466 // fwrite(test_buffer, test_size, 1, test4);
 467 // fclose(test4);
 468
 469                                 printf("UndoStackItem::set_data: incremental undo failed!\n");
 470                                 need_key = 1;
 471                                 delete [] this->data;
 472                                 this->data_size = 0;
 473                                 this->data = 0;
 474                         }
 475                         delete [] test_buffer;
 476
 477                 }
 478
 479
 480                 delete [] prev_buffer;
 481         }
 482
 483         if( need_key ) {
 484                 this->key = 1;
 485                 this->data_size = new_size;
 486                 this->data = new char[this->data_size];
 487                 memcpy(this->data, data, this->data_size);
 488         }
 489         return;
 490 }
 491
 492 char* UndoStackItem::get_incremental_data()
 493 {
 494         return data;
 495 }
 496
 497 int UndoStackItem::get_incremental_size()
 498 {
 499         return data_size;
 500 }
 501
 502 int UndoStackItem::get_size()
 503 {
 504         return data_size;
 505 }
 506
 507 char* UndoStackItem::get_data()
 508 {
 509 // Find latest key buffer
 510         UndoStackItem *current = this;
 511         while( current && !current->key )
 512                 current = PREVIOUS;
 513         if( !current ) {
 514                 printf("UndoStackItem::get_data: no key buffer found!\n");
 515                 return 0;
 516         }
 517
 518 // This is the key buffer
 519         if( current == this ) {
 520                 char *result = new char[data_size];
 521                 memcpy(result, data, data_size);
 522                 return result;
 523         }
 524
 525 // Get key buffer
 526         char *current_data = current->get_data();
 527         int current_size = current->get_size();
 528         current = NEXT;
 529         while( current ) {
 530 // Do incremental updates
 531                 int new_size;
 532                 char *new_data = (char*)apply_difference((unsigned char*)current_data, current_size,
 533                         (unsigned char*)current->get_incremental_data(),
 534                         current->get_incremental_size(), &new_size);
 535                 delete [] current_data;
 536
 537                 if( current == this )
 538                         return new_data;
 539                 else {
 540                         current_data = new_data;
 541                         current_size = new_size;
 542                         current = NEXT;
 543                 }
 544         }
 545
 546 // Never hit this object.
 547         delete [] current_data;
 548         printf("UndoStackItem::get_data: lost starting object!\n");
 549         return 0;
 550 }
 551
 552 int UndoStackItem::is_key()
 553 {
 554         return key;
 555 }
 556
 557 void UndoStackItem::set_flags(uint64_t flags)
 558 {
 559         this->load_flags = flags;
 560 }
 561
 562 uint64_t UndoStackItem::get_flags()
 563 {
 564         return load_flags;
 565 }
 566
 567 void UndoStackItem::set_creator(void *creator)
 568 {
 569         this->creator = creator;
 570 }
 571
 572 void* UndoStackItem::get_creator()
 573 {
 574         return creator;
 575 }
 576