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