X-Git-Url: http://git.cinelerra-gg.org/git/?a=blobdiff_plain;f=cinelerra-5.1%2Fcinelerra%2Fundostack.C;fp=cinelerra-5.1%2Fcinelerra%2Fundostack.C;h=94f16cf9a868403be4d632f20592cd9f69117325;hb=30bdb85eb33a8ee7ba675038a86c6be59c43d7bd;hp=0000000000000000000000000000000000000000;hpb=52fcc46226f9df46f9ce9d0566dc568455a7db0b;p=goodguy%2Fhistory.git

diff --git a/cinelerra-5.1/cinelerra/undostack.C b/cinelerra-5.1/cinelerra/undostack.C
new file mode 100644
index 00000000..94f16cf9
--- /dev/null
+++ b/cinelerra-5.1/cinelerra/undostack.C
@@ -0,0 +1,683 @@
+
+/*
+ * 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;
+}
+
+
+
+
+
+
+