fix shuttle for Termux/Android too
[goodguy/cinelerra.git] / 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 "filexml.h"
27 #include "undostack.h"
28 #include <string.h>
29
30 // undo can be incremental or direct, from key to current
31 //#define UNDO_INCREMENTAL
32
33 UndoStack::UndoStack() : List<UndoStackItem>()
34 {
35         current = 0;
36 }
37
38 UndoStack::~UndoStack()
39 {
40 }
41
42 UndoStackItem *UndoStack::get_current_undo()
43 {
44         UndoStackItem *item = current;
45         if( item &&  (number_of(item) & 1) ) item = item->previous;
46         if( item && !(number_of(item) & 1) ) item = item->previous;
47         return item;
48 }
49
50 UndoStackItem *UndoStack::get_current_redo()
51 {
52         UndoStackItem *item = current ? current : first;
53         if( item &&  (number_of(item) & 1) ) item = item->next;
54         if( item && !(number_of(item) & 1) ) item = item->next;
55         return item;
56 }
57
58
59 UndoStackItem* UndoStack::push()
60 {
61 // delete oldest 2 undos if necessary
62         while( total() > UNDOLEVELS ) {
63                 UndoStackItem *item = first, *key = item;
64 #ifdef UNDO_INCREMENTAL
65                 for( int i=2; --i>=0; item=item->next );
66 #else
67                 for( int i=2; --i>=0; item=item->next )
68                         if( item->is_key() ) key = item;
69 #endif
70                 char *data = !item->is_key() ? key->get_data() : 0;
71                 while( first != item ) {
72                         if( current == first ) current = first->next;
73                         delete first;
74                 }
75                 if( data ) {
76                         item->set_data(data);
77                         delete [] data;
78                 }
79         }
80
81 // current is only 0 if before first undo
82         current = current ? insert_after(current) : insert_before(first);
83 // delete future undos if necessary
84         while( current->next ) remove(last);
85         return current;
86 }
87
88 UndoStackItem* UndoStack::pull_next()
89 {
90 // use first entry if none
91         if( !current )
92                 current = first;
93         else
94 // use next entry if there is a next entry
95         if( current->next )
96                 current = NEXT;
97 // don't change current if there is no next entry
98         else
99                 return 0;
100
101         return current;
102 }
103
104
105 void UndoStack::dump(FILE *fp)
106 {
107         fprintf(fp,"UndoStack::dump\n");
108         UndoStackItem *current = last;
109 // Dump most recent
110         for( int i=0; current && i<32; ++i,current=PREVIOUS ) {
111                 fprintf(fp,"%c %2d %14p %-24s %8d %04jx %c\n", current->is_key() ? 'k' : ' ',
112                         i, current, current->get_description(), current->get_size(),
113                         current->get_flags(), current == this->current ? '*' : ' ');
114 //char fn[BCSTRLEN]; sprintf(fn,"/tmp/undo%d", i); FILE *fp = fopen(fn,"w");
115 //if( fp ) { char *cp=current->get_data(); fwrite(cp,strlen(cp),1,fp); fclose(fp); delete [] cp; }
116         }
117 }
118
119 class undo_record {
120 public:
121         int32_t new_ofs;
122         int32_t new_len;
123         int32_t old_len;
124 };
125
126 static unsigned char* apply_difference(unsigned char *before, int before_len,
127                 unsigned char *patch, int patch_len, int *result_len)
128 {
129         XMLBuffer xbfr((const char *)patch, patch_len, 0);
130         int32_t len = 0;
131         xbfr.read((char *)&len, sizeof(len));
132         char *result = new char[len];
133         char *rp = result, *bp = (char*)before;
134
135         while( xbfr.itell() < patch_len ) {
136                 undo_record urecd;
137                 xbfr.read((char*)&urecd, sizeof(urecd));
138                 int ofs = rp - result;
139                 if( urecd.new_ofs > ofs ) {
140                         int sz = urecd.new_ofs - ofs;
141                         memcpy(rp, bp, sz);
142                         bp += sz;  rp += sz;
143                 }
144                 if( urecd.new_len > 0 )
145                         xbfr.read(rp, urecd.new_len);
146                 bp += urecd.old_len;  rp += urecd.new_len;
147         }
148
149 // All data from before_ptr to end of result buffer is identical
150         int sz = bp - (char *)before;
151         if( (before_len-=sz) > 0 ) {
152                 memcpy(rp, bp, before_len);
153                 rp += before_len;
154         }
155
156         *result_len = rp - result;
157         return (unsigned char *)result;
158 }
159
160 UndoStackItem::UndoStackItem()
161  : ListItem<UndoStackItem>()
162 {
163         description = data = 0;
164         data_size = 0;
165         key = 0;
166         creator = 0;
167         session_filename = 0;
168 }
169
170 UndoStackItem::~UndoStackItem()
171 {
172         delete [] description;
173         delete [] data;
174         delete [] session_filename;
175 }
176
177 void UndoStackItem::set_description(char *description)
178 {
179         delete [] this->description;
180         this->description= 0;
181         this->description = new char[strlen(description) + 1];
182         strcpy(this->description, description);
183 }
184
185 void UndoStackItem::set_filename(char *filename)
186 {
187         delete [] session_filename;
188         this->session_filename = cstrdup(filename);
189 }
190
191 char* UndoStackItem::get_filename()
192 {
193         return session_filename;
194 }
195
196
197 const char* UndoStackItem::get_description()
198 {
199         if( description )
200                 return description;
201         else
202                 return "";
203 }
204
205 // undo diff
206
207 UndoHash::UndoHash(char *txt, int len, UndoHash *nxt)
208 {
209         this->txt = txt;
210         this->len = len;
211         this->nxt = nxt;
212         line[va] = line[vb] = -1;
213         occurs[va] = occurs[vb] = 0;
214 }
215 UndoHash::~UndoHash()
216 {
217 }
218
219 UndoHashTable::UndoHashTable()
220 {
221         for( int i=0; i<hash_sz; ++i ) table[i] = 0;
222         bof = new UndoHash(0, 0, 0);
223         eof = new UndoHash(0, 0, 0);
224 }
225 UndoHashTable::~UndoHashTable()
226 {
227         delete bof;
228         delete eof;
229         for( int i=0; i<hash_sz; ++i ) {
230                 for( UndoHash *nxt=0, *hp=table[i]; hp; hp=nxt ) {
231                         nxt = hp->nxt;  delete hp;
232                 }
233         }
234 }
235
236 UndoHash *UndoHashTable::add(char *txt, int len)
237 {
238         uint8_t *bp = (uint8_t *)txt;
239         int v = 0;
240         for( int i=len; --i>=0; ++bp ) {
241                 v = (v<<1) + *bp;
242                 v = (v + (v>>hash_sz2)) & hash_sz1;
243         }
244         UndoHash *hp = table[v];
245         while( hp && strncmp(hp->txt,txt,len) ) hp = hp->nxt;
246         if( !hp ) {
247                 hp = new UndoHash(txt, len, table[v]);
248                 table[v] = hp;
249         }
250         return hp;
251 }
252
253 UndoLine::UndoLine(UndoHash *hash, char *tp)
254 {
255         this->txt = tp;  this->len = 0;
256         this->hash = hash;
257         hash->occurs[va] = hash->occurs[vb] = 1;
258 }
259
260 UndoLine::UndoLine(UndoHashTable *hash, char *txt, int len)
261 {
262         this->txt = txt;  this->len = len;
263         this->hash = hash->add(txt, len);
264 }
265 UndoLine::~UndoLine()
266 {
267 }
268
269 int UndoLine::eq(UndoLine *ln)
270 {
271         return hash == ln->hash ? 1 : 0;
272 }
273
274 void UndoVersion::scan_lines(UndoHashTable *hash, char *sp, char *ep)
275 {
276         for( int line=1; sp<ep; ++line ) {
277                 char *txt = sp;
278                 while( sp<ep && *sp++ != '\n' );
279                 UndoLine *ln = new UndoLine(hash, txt, sp-txt);
280                 ln->hash->line[ver] = line;
281                 ++ln->hash->occurs[ver];
282                 append(ln);
283         }
284 }
285
286
287 void UndoStackItem::set_data(char *data)
288 {
289         delete [] this->data;  this->data = 0;
290         this->data_size = 0;   this->key = 0;
291         int data_size = strlen(data)+1;
292
293         UndoStackItem *current = this;
294 // Search for key buffer within interval
295         for( int i=UNDO_KEY_INTERVAL; --i>=0 && current && !current->key; current=PREVIOUS );
296
297         int need_key = current ? 0 : 1;
298 // setting need_key = 1 forces all undo data items to key (not diffd)
299 //      int need_key = 1;
300         char *prev = 0;  int prev_size = 0;
301         if( !need_key ) {
302 #ifdef UNDO_INCREMENTAL
303                 prev = previous->get_data();
304                 prev_size = prev ? strlen(prev)+1 : 0;
305 #else
306                 prev = current->data;
307                 prev_size = current->data_size;
308 #endif
309                 int min_size = data_size/16;
310 // if the previous is a sizable incremental diff
311                 if( previous && !previous->key &&
312                     previous->data_size > min_size ) {
313 //  and this minimum diff distance is a lot different, need key
314                         int dist = abs(data_size - prev_size);
315                         if( abs(dist - previous->data_size) > min_size )
316                                 need_key = 1;
317                 }
318         }
319         if( !need_key ) {
320                 int bfr_size = BCTEXTLEN;
321                 char *bfr = new char[bfr_size];
322                 XMLBuffer xbfr(bfr_size, bfr, 1);
323                 xbfr.write((char*)&data_size, sizeof(data_size));
324                 UndoHashTable hash;
325                 UndoVersion alines(va), blines(vb);
326                 char *asp = data, *aep = asp + data_size-1;
327                 char *bsp = prev, *bep = bsp + prev_size-1;
328                 alines.append(new UndoLine(hash.bof, asp));
329                 blines.append(new UndoLine(hash.bof, bsp));
330                 alines.scan_lines(&hash, asp, aep);
331                 blines.scan_lines(&hash, bsp, bep);
332                 int asz = alines.size(), bsz = blines.size();
333 // trim matching suffix
334                 while( asz > 0 && bsz > 0 && alines[asz-1]->eq(blines[bsz-1]) ) {
335                         aep = alines[--asz]->txt;  alines.remove_object();
336                         bep = blines[--bsz]->txt;  blines.remove_object();
337                 }
338 // include for matching last item
339                 alines.append(new UndoLine(hash.eof, aep));
340                 blines.append(new UndoLine(hash.eof, bep));
341                 hash.eof->line[va] = asz++;
342                 hash.eof->line[vb] = bsz++;
343
344                 int ai = 0, bi = 0;
345                 while( ai < asz || bi < bsz ) {
346 // skip running match
347                         if( alines[ai]->eq(blines[bi]) ) { ++ai;  ++bi;  continue; }
348                         char *adp = alines[ai]->txt, *bdp = blines[bi]->txt;
349 // find best unique match
350                         int ma = asz, mb = bsz;
351                         int mx = ma + mb + 1;
352                         for( int ia=ai; ia<asz && ia-ai<mx; ++ia ) {
353                                 UndoHash *ah = alines[ia]->hash;
354                                 if( ah->occurs[va] != 1 || ah->occurs[vb] != 1 ) continue;
355                                 int m = (ah->line[va] - ai) + (ah->line[vb] - bi);
356                                 if( m >= mx ) continue;
357                                 ma = ah->line[va];  mb = ah->line[vb];  mx = m;
358                         }
359 // trim suffix
360                         while( ma > 0 && mb > 0 && alines[ma-1]->eq(blines[mb-1]) ) { --ma;  --mb; }
361                         char *ap = alines[ma]->txt, *bp = blines[mb]->txt;
362                         ai = ma;  bi = mb;
363                         undo_record urecd;
364                         urecd.new_ofs = adp - data;
365                         urecd.new_len = ap - adp;
366                         urecd.old_len = bp - bdp;
367                         xbfr.write((const char*)&urecd, sizeof(urecd));
368                         xbfr.write((const char*)adp, urecd.new_len);
369                 }
370
371                 int64_t pos = xbfr.otell();
372                 if( abs(data_size-prev_size) < pos/2 ) {
373                         this->data = new char[this->data_size = pos];
374                         xbfr.iseek(0);
375                         xbfr.read(this->data, pos);
376 #if 1
377                         int test_size = 0;
378                         char *test_data = (char*)apply_difference(
379                                 (unsigned char *)prev, prev_size,
380                                 (unsigned char *)this->data, this->data_size,
381                                 &test_size);
382                         if( test_size != data_size || memcmp(test_data, data, test_size) ) {
383                                 printf("UndoStackItem::set_data: *** incremental undo failed!\n");
384                                 delete [] this->data;  this->data = 0;  this->data_size = 0;
385                                 need_key = 1;
386                         }
387                         delete [] test_data;
388 #endif
389                 }
390                 else
391                         need_key = 1;
392         }
393
394 #ifdef UNDO_INCREMENTAL
395         delete [] prev;
396 #endif
397         if( need_key ) {
398                 this->key = 1;
399                 this->data = new char[this->data_size = data_size];
400                 memcpy(this->data, data, this->data_size);
401         }
402 }
403
404 char* UndoStackItem::get_data()
405 {
406 // Find latest key buffer
407         UndoStackItem *current = this;
408         while( current && !current->key )
409                 current = PREVIOUS;
410         if( !current ) {
411                 printf("UndoStackItem::get_data: no key buffer found!\n");
412                 return 0;
413         }
414
415 // This is the key buffer
416         if( current == this ) {
417                 char *result = new char[data_size];
418                 memcpy(result, data, data_size);
419                 return result;
420         }
421 #ifdef UNDO_INCREMENTAL
422 // Get key buffer
423         char *current_data = current->get_data();
424         int current_size = current->data_size;
425         current = NEXT;
426         while( current ) {
427 // Do incremental updates
428                 int new_size;
429                 char *new_data = (char*)apply_difference(
430                         (unsigned char*)current_data, current_size,
431                         (unsigned char*)current->data, current->data_size,
432                         &new_size);
433                 delete [] current_data;
434
435                 if( current == this )
436                         return new_data;
437                 current_data = new_data;
438                 current_size = new_size;
439                 current = NEXT;
440         }
441 // Never hit this object.
442         delete [] current_data;
443         printf("UndoStackItem::get_data: lost starting object!\n");
444         return 0;
445 #else
446         int new_size;
447         char *new_data = (char*)apply_difference(
448                 (unsigned char*)current->data, current->data_size,
449                 (unsigned char*)this->data, this->data_size, &new_size);
450         return new_data;
451 #endif
452 }
453
454 int UndoStackItem::is_key()
455 {
456         return key;
457 }
458
459 int UndoStackItem::get_size()
460 {
461         return data_size;
462 }
463
464 void UndoStackItem::set_flags(uint64_t flags)
465 {
466         this->load_flags = flags;
467 }
468
469 uint64_t UndoStackItem::get_flags()
470 {
471         return load_flags;
472 }
473
474 void UndoStackItem::set_creator(void *creator)
475 {
476         this->creator = creator;
477 }
478
479 void* UndoStackItem::get_creator()
480 {
481         return creator;
482 }
483
484 void UndoStackItem::save(FILE *fp)
485 {
486         fwrite(&key,1,sizeof(key),fp);
487         fwrite(&load_flags,1,sizeof(load_flags),fp);
488         fwrite(&data_size,1,sizeof(data_size),fp);
489         fwrite(data,1,data_size,fp);
490         for( char *bp=session_filename; *bp; ++bp ) fputc(*bp, fp);
491         fputc(0, fp);
492         for( char *bp=description; *bp; ++bp ) fputc(*bp, fp);
493         fputc(0, fp);
494 }
495
496 void UndoStackItem::load(FILE *fp)
497 {
498         fread(&key,1,sizeof(key),fp);
499         fread(&load_flags,1,sizeof(load_flags),fp);
500         fread(&data_size,1,sizeof(data_size),fp);
501         fread(data=new char[data_size],1,data_size,fp);
502         char filename[BCTEXTLEN], descr[BCTEXTLEN];
503         char *bp = filename, *ep = bp+sizeof(filename)-1;
504         for( int ch; bp<ep && (ch=fgetc(fp))>0; ++bp ) *bp = ch;
505         *bp = 0;
506         session_filename = cstrdup(filename);
507         bp = descr;  ep = bp+sizeof(descr)-1;
508         for( int ch; bp<ep && (ch=fgetc(fp))>0; ++bp ) *bp = ch;
509         *bp = 0;
510         description = cstrdup(descr);
511 //printf("read undo key=%d,flags=%jx,data_size=%d,data=%p,file=%s,descr=%s\n",
512 // key, load_flags, data_size, data, session_filename, description);
513 }
514
515 void UndoStack::save(FILE *fp)
516 {
517         for( UndoStackItem *item=first; item; item=item->next ) {
518                 int is_current = item == current ? 1 : 0;
519                 fwrite(&is_current,1,sizeof(is_current),fp);
520                 item->save(fp);
521 //              if( item == current ) break; // stop at current
522         }
523 }
524
525 void UndoStack::load(FILE *fp)
526 {
527         while( last ) delete last;
528         current = 0;
529         UndoStackItem *current_item = 0;
530         int is_current = 0;
531         while( fread(&is_current,1,sizeof(is_current),fp) == sizeof(is_current) ) {
532                 UndoStackItem *item = push();
533                 item->load(fp);
534                 if( is_current ) current_item = item;
535         }
536         if( current_item ) current = current_item;
537 }
538