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) & 1) ) item = item->previous;
42 if( item && !(number_of(item) & 1) ) item = item->previous;
46 UndoStackItem *UndoStack::get_current_redo()
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;
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 ) {
65 while( current->next ) remove(last);
68 // delete oldest 2 undos if necessary
69 if( total() > UNDOLEVELS ) {
70 for( int i=0; i<2; ++i ) {
71 UndoStackItem *second = first->next;
75 if( !second->is_key() ) {
76 temp_data = second->get_data();
80 // Convert new first to key buffer.
81 if( !second->is_key() ) {
82 second->set_data(temp_data);
91 UndoStackItem* UndoStack::pull_next()
93 // use first entry if none
97 // use next entry if there is a next entry
100 // don't change current if there is no next entry
108 void UndoStack::dump(FILE *fp)
110 fprintf(fp,"UndoStack::dump\n");
111 UndoStackItem *current = last;
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; }
123 // These difference routines are straight out of the Heroinediff/Heroinepatch
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.
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.
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
149 // Minimum size of transposed block.
150 // Smaller transpositions should be included in the same difference record.
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,
160 unsigned char *new_data,
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));
171 unsigned char *new_result_ptr = new_result + (*result_size);
172 *(int32_t*)new_result_ptr = new_offset;
174 *(int32_t*)new_result_ptr = new_size;
176 *(int32_t*)new_result_ptr = old_size;
179 memcpy(new_result_ptr, new_data, new_size);
180 (*result_size) += record_size;
181 (*result) = new_result;
187 static unsigned char* get_difference_fast(unsigned char *before,
189 unsigned char *after,
194 unsigned char *result = new unsigned char[4];
197 // Store size of new buffer
198 *(int32_t*)result = after_len;
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;
206 if( last_difference_after < after ||
207 last_difference_before < before ) break;
208 if( *last_difference_after != *last_difference_before ) {
211 last_difference_after--;
212 last_difference_before--;
214 last_difference_after++;
215 last_difference_before++;
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;
223 // Scan forward for first difference
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 ) {
236 // Get length of difference.
237 unsigned char *before_difference_start = before_ptr;
238 unsigned char *after_difference_start = after_ptr;
241 while( *before_ptr != *after_ptr &&
242 before_ptr < last_difference_before &&
243 after_ptr < last_difference_after ) {
248 // Finished comparing if either pointer hits its last difference
249 if( before_ptr >= last_difference_before ||
250 after_ptr >= last_difference_after ) {
252 before_ptr = last_difference_before;
253 after_ptr = last_difference_after;
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;
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);
269 // Create difference record
270 append_record(&result, result_len, after_difference_start,
271 after_start, after_len, before_len);
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)
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);
293 static unsigned char* apply_difference(unsigned char *before, int before_len,
294 unsigned char *patch, int patch_len, int *result_len)
296 unsigned char *patch_ptr = patch;
297 *result_len = *(int32_t*)patch_ptr;
299 unsigned char *patch_end = patch + patch_len;
300 //unsigned char *before_end = before + before_len;
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;
309 unsigned char *after_data;
310 int after_offset, after_size, before_size;
312 get_record(&patch_ptr, patch_end,
313 &after_data, &after_offset, &after_size, &before_size);
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;
323 memcpy(result_ptr, after_data, after_size);
324 result_ptr += after_size;
325 before_ptr += before_size;
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);
339 UndoStackItem::UndoStackItem()
340 : ListItem<UndoStackItem>()
342 description = data = 0;
346 session_filename = 0;
349 UndoStackItem::~UndoStackItem()
351 delete [] description;
353 delete [] session_filename;
356 void UndoStackItem::set_description(char *description)
358 delete [] this->description;
359 this->description= 0;
360 this->description = new char[strlen(description) + 1];
361 strcpy(this->description, description);
364 void UndoStackItem::set_filename(char *filename)
366 delete [] session_filename;
367 this->session_filename = cstrdup(filename);
370 char* UndoStackItem::get_filename()
372 return session_filename;
376 const char* UndoStackItem::get_description()
384 int UndoStackItem::has_data()
386 return data_size ? 1 : 0;
389 void UndoStackItem::set_data(char *data)
391 delete [] this->data;
395 // Search for key buffer within interval
397 UndoStackItem *current = this;
399 for( int i=0; i<UNDO_KEY_INTERVAL && current; ++i ) {
400 if( current->key && current->has_data() ) {
408 int new_size = strlen(data) + 1;
411 // Reconstruct previous data for difference
412 char *prev_buffer = previous->get_data();
413 int prev_size = prev_buffer ? strlen(prev_buffer) + 1 : 0;
416 // printf("UndoStackItem::set_data 1\n");
417 this->data = (char*)get_difference_fast((unsigned char*)prev_buffer,
419 (unsigned char*)data,
423 //printf("UndoStackItem::set_data 2 %jd\n", timer.get_difference());
426 // FILE *test1 = fopen("/tmp/undo1", "w");
427 // fwrite(prev_buffer, prev_size, 1, test1);
429 // FILE *test2 = fopen("/tmp/undo2", "w");
430 // fwrite(data, new_size, 1, test2);
432 // FILE *test3 = fopen("/tmp/undo2.diff", "w");
433 // fwrite(this->data, this->data_size, 1, test3);
436 //printf("UndoStackItem::set_data 3 %d %d\n", new_size, this->data_size);
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;
447 // Reconstruct current data from difference
449 char *test_buffer = (char*)apply_difference((unsigned char*)prev_buffer,
451 (unsigned char*)this->data,
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);
459 // FILE *test2 = fopen("/tmp/undo2", "w");
460 // fwrite(data, new_size, 1, test2);
462 // FILE *test3 = fopen("/tmp/undo2.diff", "w");
463 // fwrite(this->data, this->data_size, 1, test3);
465 // FILE *test4 = fopen("/tmp/undo3", "w");
466 // fwrite(test_buffer, test_size, 1, test4);
469 printf("UndoStackItem::set_data: incremental undo failed!\n");
471 delete [] this->data;
475 delete [] test_buffer;
480 delete [] prev_buffer;
485 this->data_size = new_size;
486 this->data = new char[this->data_size];
487 memcpy(this->data, data, this->data_size);
492 char* UndoStackItem::get_incremental_data()
497 int UndoStackItem::get_incremental_size()
502 int UndoStackItem::get_size()
507 char* UndoStackItem::get_data()
509 // Find latest key buffer
510 UndoStackItem *current = this;
511 while( current && !current->key )
514 printf("UndoStackItem::get_data: no key buffer found!\n");
518 // This is the key buffer
519 if( current == this ) {
520 char *result = new char[data_size];
521 memcpy(result, data, data_size);
526 char *current_data = current->get_data();
527 int current_size = current->get_size();
530 // Do incremental updates
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;
537 if( current == this )
540 current_data = new_data;
541 current_size = new_size;
546 // Never hit this object.
547 delete [] current_data;
548 printf("UndoStackItem::get_data: lost starting object!\n");
552 int UndoStackItem::is_key()
557 void UndoStackItem::set_flags(uint64_t flags)
559 this->load_flags = flags;
562 uint64_t UndoStackItem::get_flags()
567 void UndoStackItem::set_creator(void *creator)
569 this->creator = creator;
572 void* UndoStackItem::get_creator()