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