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