--- /dev/null
+
+/*
+ * CINELERRA
+ * Copyright (C) 2008 Adam Williams <broadcast at earthling dot net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ */
+
+#include "bcsignals.h"
+#include "bctimer.h"
+#include "clip.h"
+#include "cstrdup.h"
+#include "undostack.h"
+#include <string.h>
+
+UndoStack::UndoStack() : List<UndoStackItem>()
+{
+ current = 0;
+}
+
+UndoStack::~UndoStack()
+{
+}
+
+UndoStackItem* UndoStack::push()
+{
+// current is only 0 if before first undo
+ if(current)
+ current = insert_after(current);
+ else
+ current = insert_before(first);
+
+// delete future undos if necessary
+ if(current && current->next)
+ {
+ while(current->next) remove(last);
+ }
+
+// delete oldest 2 undos if necessary
+ if(total() > UNDOLEVELS)
+ {
+ for(int i = 0; i < 2; i++)
+ {
+ UndoStackItem *second = first->next;
+ char *temp_data = 0;
+
+
+ if(!second->is_key())
+ {
+ temp_data = second->get_data();
+ }
+ remove(first);
+
+// Convert new first to key buffer.
+ if(!second->is_key())
+ {
+ second->set_data(temp_data);
+ }
+ delete [] temp_data;
+ }
+ }
+
+ return current;
+}
+
+void UndoStack::pull()
+{
+ if(current) current = PREVIOUS;
+}
+
+UndoStackItem* UndoStack::pull_next()
+{
+// use first entry if none
+ if(!current)
+ current = first;
+ else
+// use next entry if there is a next entry
+ if(current->next)
+ current = NEXT;
+// don't change current if there is no next entry
+ else
+ return 0;
+
+ return current;
+}
+
+
+void UndoStack::dump(FILE *fp)
+{
+ fprintf(fp,"UndoStack::dump\n");
+ UndoStackItem *current = last;
+ int i = 0;
+// Dump most recent
+ while(current && i < 10)
+ {
+ fprintf(fp," %d %p %s %c\n",
+ i++,
+ current,
+ current->get_description(),
+ current == this->current ? '*' : ' ');
+ current = PREVIOUS;
+ }
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+// These difference routines are straight out of the Heroinediff/Heroinepatch
+// utilities.
+
+
+
+
+
+
+// We didn't want to use the diff program because that isn't efficient enough
+// to compress EDL's. This program also handles binary data.
+
+// Algorithm 1:
+// Search from beginning for first difference.
+// Count everything up to first difference as equal.
+// Determine length of different block by searching for transposition with most
+// similar characters.
+// For every byte in different block, search for occurrence of
+// transposed copy longer than a record header in remaining old buffer.
+// If no match is found, add 1 to the different block length and try the next
+// byte. Once the most similar match is found, store the changed data leading up to it in the
+// difference record.
+// This can be real slow if there is a large transposition early in the file.
+
+// Algorithm 2:
+// Search backwards from end of both files for last difference.
+// Count all data from last same bytes as a transposition.
+// Search forwards from start of both files until last same bytes
+// for differences.
+
+
+
+
+
+
+
+
+// Minimum size of transposed block.
+// Smaller transpositions should be included in the same difference record.
+#define MIN_TRANS 16
+
+// Format for difference records.
+// The first 4 bytes are the offset of the change.
+// The next 4 bytes are the number of bytes of new data.
+// The next 4 bytes are the number of bytes of old data replaced.
+// The new data follows.
+static void append_record(unsigned char **result,
+ int *result_size,
+ unsigned char *new_data,
+ int new_offset,
+ int new_size,
+ int old_size)
+{
+ if(new_size || old_size)
+ {
+ int record_size = new_size + 12;
+ unsigned char *new_result = new unsigned char[(*result_size) + record_size];
+ memcpy(new_result, (*result), (*result_size));
+ delete [] (*result);
+
+ unsigned char *new_result_ptr = new_result + (*result_size);
+ *(int32_t*)new_result_ptr = new_offset;
+ new_result_ptr += 4;
+ *(int32_t*)new_result_ptr = new_size;
+ new_result_ptr += 4;
+ *(int32_t*)new_result_ptr = old_size;
+ new_result_ptr += 4;
+
+ memcpy(new_result_ptr, new_data, new_size);
+ (*result_size) += record_size;
+ (*result) = new_result;
+ }
+}
+
+
+
+static unsigned char* get_difference_fast(unsigned char *before,
+ int before_len,
+ unsigned char *after,
+ int after_len,
+ int *result_len,
+ int verbose)
+{
+ unsigned char *result = new unsigned char[4];
+ *result_len = 4;
+
+// Store size of new buffer
+ *(int32_t*)result = after_len;
+
+
+
+// Get last different bytes
+ unsigned char *last_difference_after = after + after_len - 1;
+ unsigned char *last_difference_before = before + before_len - 1;
+ while(1)
+ {
+ if(last_difference_after < after ||
+ last_difference_before < before) break;
+ if(*last_difference_after != *last_difference_before)
+ {
+ break;
+ }
+ last_difference_after--;
+ last_difference_before--;
+ }
+ last_difference_after++;
+ last_difference_before++;
+
+
+
+
+
+
+ int done = 0;
+ unsigned char *before_ptr = before;
+ unsigned char *after_ptr = after;
+ unsigned char *before_end = before + before_len;
+ unsigned char *after_end = after + after_len;
+
+// Scan forward for first difference
+ while(!done)
+ {
+ if(before_ptr < before_end &&
+ after_ptr < after_end)
+ {
+// Both characters equal
+ if(*before_ptr == *after_ptr &&
+ before_ptr < last_difference_before &&
+ after_ptr < last_difference_after)
+ {
+ before_ptr++;
+ after_ptr++;
+ }
+ else
+// Characters differ
+ {
+// Get length of difference.
+ unsigned char *before_difference_start = before_ptr;
+ unsigned char *after_difference_start = after_ptr;
+
+
+ while(*before_ptr != *after_ptr &&
+ before_ptr < last_difference_before &&
+ after_ptr < last_difference_after)
+ {
+ before_ptr++;
+ after_ptr++;
+ }
+
+// Finished comparing if either pointer hits its last difference
+ if(before_ptr >= last_difference_before ||
+ after_ptr >= last_difference_after)
+ {
+ done = 1;
+ before_ptr = last_difference_before;
+ after_ptr = last_difference_after;
+ }
+
+
+
+ int after_start = after_difference_start - after;
+ int before_start = before_difference_start - before;
+ int after_len = after_ptr - after_difference_start;
+ int before_len = before_ptr - before_difference_start;
+
+ if(verbose)
+ {
+ char string[1024];
+ memcpy(string, after_difference_start, MIN(after_len, 40));
+ string[MIN(after_len, 40)] = 0;
+ printf("after_offset=0x%x before_offset=0x%x after_size=%d before_size=%d \"%s\"\n",
+ after_start,
+ before_start,
+ after_len,
+ before_len,
+ string);
+ }
+
+
+// Create difference record
+ append_record(&result,
+ result_len,
+ after_difference_start,
+ after_start,
+ after_len,
+ before_len);
+ }
+ }
+ else
+ done = 1;
+ }
+ return result;
+}
+
+
+
+
+
+
+
+
+
+static void get_record(unsigned char **patch_ptr,
+ unsigned char *patch_end,
+ unsigned char **after_data,
+ int *after_offset,
+ int *after_size,
+ int *before_size)
+{
+ (*after_data) = 0;
+ if((*patch_ptr) < patch_end)
+ {
+ (*after_offset) = *(int32_t*)(*patch_ptr);
+ (*patch_ptr) += 4;
+ (*after_size) = *(int32_t*)(*patch_ptr);
+ (*patch_ptr) += 4;
+ (*before_size) = *(int32_t*)(*patch_ptr);
+ (*patch_ptr) += 4;
+
+ (*after_data) = (*patch_ptr);
+ (*patch_ptr) += (*after_size);
+ }
+}
+
+
+
+
+
+static unsigned char* apply_difference(unsigned char *before,
+ int before_len,
+ unsigned char *patch,
+ int patch_len,
+ int *result_len)
+{
+ unsigned char *patch_ptr = patch;
+ *result_len = *(int32_t*)patch_ptr;
+ patch_ptr += 4;
+ unsigned char *patch_end = patch + patch_len;
+ //unsigned char *before_end = before + before_len;
+
+ unsigned char *result = new unsigned char[*result_len];
+ unsigned char *result_ptr = result;
+ unsigned char *result_end = result + *result_len;
+ unsigned char *before_ptr = before;
+
+ int done = 0;
+ while(!done)
+ {
+ unsigned char *after_data;
+ int after_offset;
+ int after_size;
+ int before_size;
+
+ get_record(&patch_ptr,
+ patch_end,
+ &after_data,
+ &after_offset,
+ &after_size,
+ &before_size);
+
+ if(after_data)
+ {
+ int result_offset = result_ptr - result;
+ if(after_offset > result_offset)
+ {
+ int skip_size = after_offset - result_offset;
+ memcpy(result_ptr, before_ptr, skip_size);
+ result_ptr += skip_size;
+ before_ptr += skip_size;
+ }
+ memcpy(result_ptr, after_data, after_size);
+ result_ptr += after_size;
+ before_ptr += before_size;
+ }
+ else
+ {
+// All data from before_ptr to end of result buffer is identical
+ if(result_end - result_ptr > 0)
+ memcpy(result_ptr, before_ptr, result_end - result_ptr);
+ done = 1;
+ }
+ }
+
+ return result;
+}
+
+
+UndoStackItem::UndoStackItem()
+ : ListItem<UndoStackItem>()
+{
+ description = data = 0;
+ data_size = 0;
+ key = 0;
+ creator = 0;
+ session_filename = 0;
+}
+
+UndoStackItem::~UndoStackItem()
+{
+ delete [] description;
+ delete [] data;
+ delete [] session_filename;
+}
+
+void UndoStackItem::set_description(char *description)
+{
+ delete [] this->description;
+ this->description= 0;
+ this->description = new char[strlen(description) + 1];
+ strcpy(this->description, description);
+}
+
+void UndoStackItem::set_filename(char *filename)
+{
+ delete [] session_filename;
+ this->session_filename = cstrdup(filename);
+}
+
+char* UndoStackItem::get_filename()
+{
+ return session_filename;
+}
+
+
+const char* UndoStackItem::get_description()
+{
+ if(description)
+ return description;
+ else
+ return "";
+}
+
+int UndoStackItem::has_data()
+{
+ return data_size ? 1 : 0;
+}
+
+void UndoStackItem::set_data(char *data)
+{
+ delete [] this->data;
+ this->data = 0;
+ this->data_size = 0;
+
+// Search for key buffer within interval
+ int need_key = 1;
+ UndoStackItem *current = this;
+ this->key = 0;
+ for(int i = 0; i < UNDO_KEY_INTERVAL && current; i++)
+ {
+ if(current->key && current->has_data())
+ {
+ need_key = 0;
+ break;
+ }
+ else
+ current = PREVIOUS;
+ }
+
+ int new_size = strlen(data) + 1;
+
+ if(!need_key)
+ {
+// Reconstruct previous data for difference
+ char *prev_buffer = previous->get_data();
+ int prev_size = prev_buffer ? strlen(prev_buffer) + 1 : 0;
+// Timer timer;
+// timer.update();
+// printf("UndoStackItem::set_data 1\n");
+ this->data = (char*)get_difference_fast((unsigned char*)prev_buffer,
+ prev_size,
+ (unsigned char*)data,
+ new_size,
+ &this->data_size,
+ 0);
+//printf("UndoStackItem::set_data 2 " _LD "\n", timer.get_difference());
+
+// Testing
+// FILE *test1 = fopen("/tmp/undo1", "w");
+// fwrite(prev_buffer, prev_size, 1, test1);
+// fclose(test1);
+// FILE *test2 = fopen("/tmp/undo2", "w");
+// fwrite(data, new_size, 1, test2);
+// fclose(test2);
+// FILE *test3 = fopen("/tmp/undo2.diff", "w");
+// fwrite(this->data, this->data_size, 1, test3);
+// fclose(test3);
+//
+//printf("UndoStackItem::set_data 3 %d %d\n", new_size, this->data_size);
+
+// Diff was bigger than original.
+// Happens if a lot of tiny changes happened and the record headers
+// took more space than the changes.
+ if(this->data_size > new_size)
+ {
+ delete [] this->data;
+ this->data_size = 0;
+ need_key = 1;
+ }
+ else
+ {
+// Reconstruct current data from difference
+ int test_size;
+ char *test_buffer = (char*)apply_difference((unsigned char*)prev_buffer,
+ prev_size,
+ (unsigned char*)this->data,
+ this->data_size,
+ &test_size);
+ if(test_size != new_size ||
+ memcmp(test_buffer, data, test_size))
+ {
+// FILE *test1 = fopen("/tmp/undo1", "w");
+// fwrite(prev_buffer, prev_size, 1, test1);
+// fclose(test1);
+// FILE *test2 = fopen("/tmp/undo2", "w");
+// fwrite(data, new_size, 1, test2);
+// fclose(test2);
+// FILE *test3 = fopen("/tmp/undo2.diff", "w");
+// fwrite(this->data, this->data_size, 1, test3);
+// fclose(test3);
+// FILE *test4 = fopen("/tmp/undo3", "w");
+// fwrite(test_buffer, test_size, 1, test4);
+// fclose(test4);
+
+ printf("UndoStackItem::set_data: incremental undo failed!\n");
+ need_key = 1;
+ delete [] this->data;
+ this->data_size = 0;
+ this->data = 0;
+ }
+ delete [] test_buffer;
+
+ }
+
+
+ delete [] prev_buffer;
+ }
+
+ if(need_key)
+ {
+ this->key = 1;
+ this->data_size = new_size;
+ this->data = new char[this->data_size];
+ memcpy(this->data, data, this->data_size);
+ }
+ return;
+}
+
+
+
+char* UndoStackItem::get_incremental_data()
+{
+ return data;
+}
+
+int UndoStackItem::get_incremental_size()
+{
+ return data_size;
+}
+
+int UndoStackItem::get_size()
+{
+ return data_size;
+}
+
+char* UndoStackItem::get_data()
+{
+// Find latest key buffer
+ UndoStackItem *current = this;
+ while(current && !current->key)
+ current = PREVIOUS;
+ if(!current)
+ {
+ printf("UndoStackItem::get_data: no key buffer found!\n");
+ return 0;
+ }
+
+// This is the key buffer
+ if(current == this)
+ {
+ char *result = new char[data_size];
+ memcpy(result, data, data_size);
+ return result;
+ }
+
+// Get key buffer
+ char *current_data = current->get_data();
+ int current_size = current->get_size();
+ current = NEXT;
+ while(current)
+ {
+// Do incremental updates
+ int new_size;
+ char *new_data = (char*)apply_difference((unsigned char*)current_data,
+ current_size,
+ (unsigned char*)current->get_incremental_data(),
+ current->get_incremental_size(),
+ &new_size);
+ delete [] current_data;
+
+ if(current == this)
+ return new_data;
+ else
+ {
+ current_data = new_data;
+ current_size = new_size;
+ current = NEXT;
+ }
+ }
+
+// Never hit this object.
+ delete [] current_data;
+ printf("UndoStackItem::get_data: lost starting object!\n");
+ return 0;
+}
+
+
+
+
+int UndoStackItem::is_key()
+{
+ return key;
+}
+
+void UndoStackItem::set_flags(uint64_t flags)
+{
+ this->load_flags = flags;
+}
+
+uint64_t UndoStackItem::get_flags()
+{
+ return load_flags;
+}
+
+void UndoStackItem::set_creator(void *creator)
+{
+ this->creator = creator;
+}
+
+void* UndoStackItem::get_creator()
+{
+ return creator;
+}
+
+
+
+
+
+
+
projects / goodguy / history.git / blobdiff