4 * Copyright (C) 2008 Adam Williams <broadcast at earthling dot net>
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.
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.
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
22 #include "bcsignals.h"
26 #include "undostack.h"
29 UndoStack::UndoStack() : List<UndoStackItem>()
34 UndoStack::~UndoStack()
38 UndoStackItem *UndoStack::get_current_undo()
40 UndoStackItem *item = current;
41 if( item && (number_of(item) % 2) ) item = item->previous;
42 if( item && !(number_of(item) % 2) ) item = item->previous;
46 UndoStackItem *UndoStack::get_current_redo()
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;
55 UndoStackItem* UndoStack::push()
57 // current is only 0 if before first undo
59 current = insert_after(current);
61 current = insert_before(first);
63 // delete future undos if necessary
64 if(current && current->next)
66 while(current->next) remove(last);
69 // delete oldest 2 undos if necessary
70 if(total() > UNDOLEVELS)
72 for(int i = 0; i < 2; i++)
74 UndoStackItem *second = first->next;
80 temp_data = second->get_data();
84 // Convert new first to key buffer.
87 second->set_data(temp_data);
96 UndoStackItem* UndoStack::pull_next()
98 // use first entry if none
102 // use next entry if there is a next entry
105 // don't change current if there is no next entry
113 void UndoStack::dump(FILE *fp)
115 fprintf(fp,"UndoStack::dump\n");
116 UndoStackItem *current = last;
119 while(current && i < 10)
121 fprintf(fp," %d %p %s %c\n",
124 current->get_description(),
125 current == this->current ? '*' : ' ');
148 // These difference routines are straight out of the Heroinediff/Heroinepatch
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.
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.
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
184 // Minimum size of transposed block.
185 // Smaller transpositions should be included in the same difference record.
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,
195 unsigned char *new_data,
200 if(new_size || old_size)
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));
207 unsigned char *new_result_ptr = new_result + (*result_size);
208 *(int32_t*)new_result_ptr = new_offset;
210 *(int32_t*)new_result_ptr = new_size;
212 *(int32_t*)new_result_ptr = old_size;
215 memcpy(new_result_ptr, new_data, new_size);
216 (*result_size) += record_size;
217 (*result) = new_result;
223 static unsigned char* get_difference_fast(unsigned char *before,
225 unsigned char *after,
230 unsigned char *result = new unsigned char[4];
233 // Store size of new buffer
234 *(int32_t*)result = after_len;
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;
243 if(last_difference_after < after ||
244 last_difference_before < before) break;
245 if(*last_difference_after != *last_difference_before)
249 last_difference_after--;
250 last_difference_before--;
252 last_difference_after++;
253 last_difference_before++;
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;
266 // Scan forward for first difference
269 if(before_ptr < before_end &&
270 after_ptr < after_end)
272 // Both characters equal
273 if(*before_ptr == *after_ptr &&
274 before_ptr < last_difference_before &&
275 after_ptr < last_difference_after)
283 // Get length of difference.
284 unsigned char *before_difference_start = before_ptr;
285 unsigned char *after_difference_start = after_ptr;
288 while(*before_ptr != *after_ptr &&
289 before_ptr < last_difference_before &&
290 after_ptr < last_difference_after)
296 // Finished comparing if either pointer hits its last difference
297 if(before_ptr >= last_difference_before ||
298 after_ptr >= last_difference_after)
301 before_ptr = last_difference_before;
302 after_ptr = last_difference_after;
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;
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",
326 // Create difference record
327 append_record(&result,
329 after_difference_start,
349 static void get_record(unsigned char **patch_ptr,
350 unsigned char *patch_end,
351 unsigned char **after_data,
357 if((*patch_ptr) < patch_end)
359 (*after_offset) = *(int32_t*)(*patch_ptr);
361 (*after_size) = *(int32_t*)(*patch_ptr);
363 (*before_size) = *(int32_t*)(*patch_ptr);
366 (*after_data) = (*patch_ptr);
367 (*patch_ptr) += (*after_size);
375 static unsigned char* apply_difference(unsigned char *before,
377 unsigned char *patch,
381 unsigned char *patch_ptr = patch;
382 *result_len = *(int32_t*)patch_ptr;
384 unsigned char *patch_end = patch + patch_len;
385 //unsigned char *before_end = before + before_len;
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;
395 unsigned char *after_data;
400 get_record(&patch_ptr,
409 int result_offset = result_ptr - result;
410 if(after_offset > result_offset)
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;
417 memcpy(result_ptr, after_data, after_size);
418 result_ptr += after_size;
419 before_ptr += before_size;
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);
434 UndoStackItem::UndoStackItem()
435 : ListItem<UndoStackItem>()
437 description = data = 0;
441 session_filename = 0;
444 UndoStackItem::~UndoStackItem()
446 delete [] description;
448 delete [] session_filename;
451 void UndoStackItem::set_description(char *description)
453 delete [] this->description;
454 this->description= 0;
455 this->description = new char[strlen(description) + 1];
456 strcpy(this->description, description);
459 void UndoStackItem::set_filename(char *filename)
461 delete [] session_filename;
462 this->session_filename = cstrdup(filename);
465 char* UndoStackItem::get_filename()
467 return session_filename;
471 const char* UndoStackItem::get_description()
479 int UndoStackItem::has_data()
481 return data_size ? 1 : 0;
484 void UndoStackItem::set_data(char *data)
486 delete [] this->data;
490 // Search for key buffer within interval
492 UndoStackItem *current = this;
494 for(int i = 0; i < UNDO_KEY_INTERVAL && current; i++)
496 if(current->key && current->has_data())
505 int new_size = strlen(data) + 1;
509 // Reconstruct previous data for difference
510 char *prev_buffer = previous->get_data();
511 int prev_size = prev_buffer ? strlen(prev_buffer) + 1 : 0;
514 // printf("UndoStackItem::set_data 1\n");
515 this->data = (char*)get_difference_fast((unsigned char*)prev_buffer,
517 (unsigned char*)data,
521 //printf("UndoStackItem::set_data 2 %jd\n", timer.get_difference());
524 // FILE *test1 = fopen("/tmp/undo1", "w");
525 // fwrite(prev_buffer, prev_size, 1, test1);
527 // FILE *test2 = fopen("/tmp/undo2", "w");
528 // fwrite(data, new_size, 1, test2);
530 // FILE *test3 = fopen("/tmp/undo2.diff", "w");
531 // fwrite(this->data, this->data_size, 1, test3);
534 //printf("UndoStackItem::set_data 3 %d %d\n", new_size, this->data_size);
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)
541 delete [] this->data;
547 // Reconstruct current data from difference
549 char *test_buffer = (char*)apply_difference((unsigned char*)prev_buffer,
551 (unsigned char*)this->data,
554 if(test_size != new_size ||
555 memcmp(test_buffer, data, test_size))
557 // FILE *test1 = fopen("/tmp/undo1", "w");
558 // fwrite(prev_buffer, prev_size, 1, test1);
560 // FILE *test2 = fopen("/tmp/undo2", "w");
561 // fwrite(data, new_size, 1, test2);
563 // FILE *test3 = fopen("/tmp/undo2.diff", "w");
564 // fwrite(this->data, this->data_size, 1, test3);
566 // FILE *test4 = fopen("/tmp/undo3", "w");
567 // fwrite(test_buffer, test_size, 1, test4);
570 printf("UndoStackItem::set_data: incremental undo failed!\n");
572 delete [] this->data;
576 delete [] test_buffer;
581 delete [] prev_buffer;
587 this->data_size = new_size;
588 this->data = new char[this->data_size];
589 memcpy(this->data, data, this->data_size);
596 char* UndoStackItem::get_incremental_data()
601 int UndoStackItem::get_incremental_size()
606 int UndoStackItem::get_size()
611 char* UndoStackItem::get_data()
613 // Find latest key buffer
614 UndoStackItem *current = this;
615 while(current && !current->key)
619 printf("UndoStackItem::get_data: no key buffer found!\n");
623 // This is the key buffer
626 char *result = new char[data_size];
627 memcpy(result, data, data_size);
632 char *current_data = current->get_data();
633 int current_size = current->get_size();
637 // Do incremental updates
639 char *new_data = (char*)apply_difference((unsigned char*)current_data,
641 (unsigned char*)current->get_incremental_data(),
642 current->get_incremental_size(),
644 delete [] current_data;
650 current_data = new_data;
651 current_size = new_size;
656 // Never hit this object.
657 delete [] current_data;
658 printf("UndoStackItem::get_data: lost starting object!\n");
665 int UndoStackItem::is_key()
670 void UndoStackItem::set_flags(uint64_t flags)
672 this->load_flags = flags;
675 uint64_t UndoStackItem::get_flags()
680 void UndoStackItem::set_creator(void *creator)
682 this->creator = creator;
685 void* UndoStackItem::get_creator()