611b175c9ef5e6d99f4a8d2538fdf48df30fcc2a
[blender.git] / source / blender / blenkernel / intern / sequencer.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * Contributor(s): 
22  * - Blender Foundation, 2003-2009
23  * - Peter Schlaile <peter [at] schlaile [dot] de> 2005/2006
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/sequencer.c
29  *  \ingroup bke
30  */
31
32 #include <stddef.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <math.h>
36
37 #include "MEM_guardedalloc.h"
38 #include "MEM_CacheLimiterC-Api.h"
39
40 #include "DNA_sequence_types.h"
41 #include "DNA_movieclip_types.h"
42 #include "DNA_mask_types.h"
43 #include "DNA_scene_types.h"
44 #include "DNA_anim_types.h"
45 #include "DNA_object_types.h"
46 #include "DNA_sound_types.h"
47
48 #include "BLI_math.h"
49 #include "BLI_fileops.h"
50 #include "BLI_listbase.h"
51 #include "BLI_path_util.h"
52 #include "BLI_string.h"
53 #include "BLI_threads.h"
54 #include "BLI_utildefines.h"
55
56 #include "BKE_animsys.h"
57 #include "BKE_global.h"
58 #include "BKE_image.h"
59 #include "BKE_main.h"
60 #include "BKE_sequencer.h"
61 #include "BKE_movieclip.h"
62 #include "BKE_fcurve.h"
63 #include "BKE_scene.h"
64 #include "BKE_mask.h"
65
66 #include "RNA_access.h"
67
68 #include "RE_pipeline.h"
69
70 #include <pthread.h>
71
72 #include "IMB_imbuf.h"
73 #include "IMB_imbuf_types.h"
74 #include "IMB_colormanagement.h"
75
76 #include "BKE_context.h"
77 #include "BKE_sound.h"
78
79 #ifdef WITH_AUDASPACE
80 #  include "AUD_C-API.h"
81 #endif
82
83 static ImBuf *seq_render_strip_stack(SeqRenderData context, ListBase *seqbasep, float cfra, int chanshown);
84 static ImBuf *seq_render_strip(SeqRenderData context, Sequence *seq, float cfra);
85 static void seq_free_animdata(Scene *scene, Sequence *seq);
86 static ImBuf *seq_render_mask(SeqRenderData context, Mask *mask, float nr, short make_float);
87
88 /* **** XXX ******** */
89 #define SELECT 1
90 ListBase seqbase_clipboard;
91 int seqbase_clipboard_frame;
92 SequencerDrawView sequencer_view3d_cb = NULL; /* NULL in background mode */
93
94 #if 0  /* unused function */
95 static void printf_strip(Sequence *seq)
96 {
97         fprintf(stderr, "name: '%s', len:%d, start:%d, (startofs:%d, endofs:%d), "
98                 "(startstill:%d, endstill:%d), machine:%d, (startdisp:%d, enddisp:%d)\n",
99                 seq->name, seq->len, seq->start, seq->startofs, seq->endofs, seq->startstill, seq->endstill, seq->machine,
100                 seq->startdisp, seq->enddisp);
101
102         fprintf(stderr, "\tseq_tx_set_final_left: %d %d\n\n", seq_tx_get_final_left(seq, 0),
103                 seq_tx_get_final_right(seq, 0));
104 }
105 #endif
106
107 int BKE_sequencer_base_recursive_apply(ListBase *seqbase, int (*apply_func)(Sequence *seq, void *), void *arg)
108 {
109         Sequence *iseq;
110         for (iseq = seqbase->first; iseq; iseq = iseq->next) {
111                 if (BKE_sequencer_recursive_apply(iseq, apply_func, arg) == -1)
112                         return -1;  /* bail out */
113         }
114         return 1;
115 }
116
117 int BKE_sequencer_recursive_apply(Sequence *seq, int (*apply_func)(Sequence *, void *), void *arg)
118 {
119         int ret = apply_func(seq, arg);
120
121         if (ret == -1)
122                 return -1;  /* bail out */
123
124         if (ret && seq->seqbase.first)
125                 ret = BKE_sequencer_base_recursive_apply(&seq->seqbase, apply_func, arg);
126
127         return ret;
128 }
129
130 /*********************** alloc / free functions *************************/
131
132 /* free */
133
134 static void free_proxy_seq(Sequence *seq)
135 {
136         if (seq->strip && seq->strip->proxy && seq->strip->proxy->anim) {
137                 IMB_free_anim(seq->strip->proxy->anim);
138                 seq->strip->proxy->anim = NULL;
139         }
140 }
141
142 static void seq_free_strip(Strip *strip)
143 {
144         strip->us--;
145         if (strip->us > 0)
146                 return;
147         if (strip->us < 0) {
148                 printf("error: negative users in strip\n");
149                 return;
150         }
151
152         if (strip->stripdata) {
153                 MEM_freeN(strip->stripdata);
154         }
155
156         if (strip->proxy) {
157                 if (strip->proxy->anim) {
158                         IMB_free_anim(strip->proxy->anim);
159                 }
160
161                 MEM_freeN(strip->proxy);
162         }
163         if (strip->crop) {
164                 MEM_freeN(strip->crop);
165         }
166         if (strip->transform) {
167                 MEM_freeN(strip->transform);
168         }
169
170         MEM_freeN(strip);
171 }
172
173 /* only give option to skip cache locally (static func) */
174 static void BKE_sequence_free_ex(Scene *scene, Sequence *seq, const int do_cache)
175 {
176         if (seq->strip)
177                 seq_free_strip(seq->strip);
178
179         if (seq->anim)
180                 IMB_free_anim(seq->anim);
181
182         if (seq->type & SEQ_TYPE_EFFECT) {
183                 struct SeqEffectHandle sh = BKE_sequence_get_effect(seq);
184
185                 sh.free(seq);
186         }
187
188         if (seq->sound) {
189                 ((ID *)seq->sound)->us--; 
190         }
191
192         /* clipboard has no scene and will never have a sound handle or be active */
193         if (scene) {
194                 Editing *ed = scene->ed;
195
196                 if (ed->act_seq == seq)
197                         ed->act_seq = NULL;
198
199                 if (seq->scene_sound && ELEM(seq->type, SEQ_TYPE_SOUND_RAM, SEQ_TYPE_SCENE))
200                         sound_remove_scene_sound(scene, seq->scene_sound);
201
202                 seq_free_animdata(scene, seq);
203         }
204
205         /* free modifiers */
206         BKE_sequence_modifier_clear(seq);
207
208         /* free cached data used by this strip,
209          * also invalidate cache for all dependent sequences
210          *
211          * be _very_ careful here, invalidating cache loops over the scene sequences and
212          * assumes the listbase is valid for all strips, this may not be the case if lists are being freed.
213          * this is optional BKE_sequence_invalidate_cache
214          */
215         if (do_cache) {
216                 if (scene) {
217                         BKE_sequence_invalidate_cache(scene, seq);
218                 }
219         }
220
221         MEM_freeN(seq);
222 }
223
224 void BKE_sequence_free(Scene *scene, Sequence *seq)
225 {
226         BKE_sequence_free_ex(scene, seq, TRUE);
227 }
228
229 /* cache must be freed before calling this function
230  * since it leaves the seqbase in an invalid state */
231 static void seq_free_sequence_recurse(Scene *scene, Sequence *seq)
232 {
233         Sequence *iseq, *iseq_next;
234
235         for (iseq = seq->seqbase.first; iseq; iseq = iseq_next) {
236                 iseq_next = iseq->next;
237                 seq_free_sequence_recurse(scene, iseq);
238         }
239
240         BKE_sequence_free_ex(scene, seq, FALSE);
241 }
242
243
244 Editing *BKE_sequencer_editing_get(Scene *scene, int alloc)
245 {
246         if (alloc) {
247                 BKE_sequencer_editing_ensure(scene);
248         }
249         return scene->ed;
250 }
251
252 static void seq_free_clipboard_recursive(Sequence *seq_parent)
253 {
254         Sequence *seq, *nseq;
255
256         for (seq = seq_parent->seqbase.first; seq; seq = nseq) {
257                 nseq = seq->next;
258                 seq_free_clipboard_recursive(seq);
259         }
260
261         BKE_sequence_free_ex(NULL, seq_parent, FALSE);
262 }
263
264 void BKE_sequencer_free_clipboard(void)
265 {
266         Sequence *seq, *nseq;
267
268         for (seq = seqbase_clipboard.first; seq; seq = nseq) {
269                 nseq = seq->next;
270                 seq_free_clipboard_recursive(seq);
271         }
272         seqbase_clipboard.first = seqbase_clipboard.last = NULL;
273 }
274
275 Editing *BKE_sequencer_editing_ensure(Scene *scene)
276 {
277         if (scene->ed == NULL) {
278                 Editing *ed;
279
280                 ed = scene->ed = MEM_callocN(sizeof(Editing), "addseq");
281                 ed->seqbasep = &ed->seqbase;
282         }
283
284         return scene->ed;
285 }
286
287 void BKE_sequencer_editing_free(Scene *scene)
288 {
289         Editing *ed = scene->ed;
290         Sequence *seq;
291
292         if (ed == NULL)
293                 return;
294
295         /* this may not be the active scene!, could be smarter about this */
296         BKE_sequencer_cache_cleanup();
297
298         SEQ_BEGIN (ed, seq)
299         {
300                 /* handle cache freeing above */
301                 BKE_sequence_free_ex(scene, seq, FALSE);
302         }
303         SEQ_END
304
305         BLI_freelistN(&ed->metastack);
306
307         MEM_freeN(ed);
308
309         scene->ed = NULL;
310 }
311
312 /*********************** sequencer pipeline functions *************************/
313
314 SeqRenderData BKE_sequencer_new_render_data(Main *bmain, Scene *scene, int rectx, int recty, int preview_render_size)
315 {
316         SeqRenderData rval;
317
318         rval.bmain = bmain;
319         rval.scene = scene;
320         rval.rectx = rectx;
321         rval.recty = recty;
322         rval.preview_render_size = preview_render_size;
323         rval.motion_blur_samples = 0;
324         rval.motion_blur_shutter = 0;
325
326         return rval;
327 }
328
329 /* ************************* iterator ************************** */
330 /* *************** (replaces old WHILE_SEQ) ********************* */
331 /* **************** use now SEQ_BEGIN () SEQ_END ***************** */
332
333 /* sequence strip iterator:
334  * - builds a full array, recursively into meta strips
335  */
336
337 static void seq_count(ListBase *seqbase, int *tot)
338 {
339         Sequence *seq;
340
341         for (seq = seqbase->first; seq; seq = seq->next) {
342                 (*tot)++;
343
344                 if (seq->seqbase.first)
345                         seq_count(&seq->seqbase, tot);
346         }
347 }
348
349 static void seq_build_array(ListBase *seqbase, Sequence ***array, int depth)
350 {
351         Sequence *seq;
352
353         for (seq = seqbase->first; seq; seq = seq->next) {
354                 seq->depth = depth;
355
356                 if (seq->seqbase.first)
357                         seq_build_array(&seq->seqbase, array, depth + 1);
358
359                 **array = seq;
360                 (*array)++;
361         }
362 }
363
364 static void seq_array(Editing *ed, Sequence ***seqarray, int *tot, int use_pointer)
365 {
366         Sequence **array;
367
368         *seqarray = NULL;
369         *tot = 0;
370
371         if (ed == NULL)
372                 return;
373
374         if (use_pointer)
375                 seq_count(ed->seqbasep, tot);
376         else
377                 seq_count(&ed->seqbase, tot);
378
379         if (*tot == 0)
380                 return;
381
382         *seqarray = array = MEM_mallocN(sizeof(Sequence *) * (*tot), "SeqArray");
383         if (use_pointer)
384                 seq_build_array(ed->seqbasep, &array, 0);
385         else
386                 seq_build_array(&ed->seqbase, &array, 0);
387 }
388
389 void BKE_seqence_iterator_begin(Editing *ed, SeqIterator *iter, int use_pointer)
390 {
391         memset(iter, 0, sizeof(*iter));
392         seq_array(ed, &iter->array, &iter->tot, use_pointer);
393
394         if (iter->tot) {
395                 iter->cur = 0;
396                 iter->seq = iter->array[iter->cur];
397                 iter->valid = 1;
398         }
399 }
400
401 void BKE_seqence_iterator_next(SeqIterator *iter)
402 {
403         if (++iter->cur < iter->tot)
404                 iter->seq = iter->array[iter->cur];
405         else
406                 iter->valid = 0;
407 }
408
409 void BKE_seqence_iterator_end(SeqIterator *iter)
410 {
411         if (iter->array)
412                 MEM_freeN(iter->array);
413
414         iter->valid = 0;
415 }
416
417 static int metaseq_start(Sequence *metaseq)
418 {
419         return metaseq->start + metaseq->startofs;
420 }
421
422 static int metaseq_end(Sequence *metaseq)
423 {
424         return metaseq->start + metaseq->len - metaseq->endofs;
425 }
426
427 static void seq_update_sound_bounds_recursive_rec(Scene *scene, Sequence *metaseq, int start, int end)
428 {
429         Sequence *seq;
430
431         /* for sound we go over full meta tree to update bounds of the sound strips,
432          * since sound is played outside of evaluating the imbufs, */
433         for (seq = metaseq->seqbase.first; seq; seq = seq->next) {
434                 if (seq->type == SEQ_TYPE_META) {
435                         seq_update_sound_bounds_recursive_rec(scene, seq, maxi(start, metaseq_start(seq)),
436                                                               mini(end, metaseq_end(seq)));
437                 }
438                 else if (ELEM(seq->type, SEQ_TYPE_SOUND_RAM, SEQ_TYPE_SCENE)) {
439                         if (seq->scene_sound) {
440                                 int startofs = seq->startofs;
441                                 int endofs = seq->endofs;
442                                 if (seq->startofs + seq->start < start)
443                                         startofs = start - seq->start;
444
445                                 if (seq->start + seq->len - seq->endofs > end)
446                                         endofs = seq->start + seq->len - end;
447
448                                 sound_move_scene_sound(scene, seq->scene_sound, seq->start + startofs,
449                                                        seq->start + seq->len - endofs, startofs);
450                         }
451                 }
452         }
453 }
454
455 static void seq_update_sound_bounds_recursive(Scene *scene, Sequence *metaseq)
456 {
457         seq_update_sound_bounds_recursive_rec(scene, metaseq, metaseq_start(metaseq), metaseq_end(metaseq));
458 }
459
460 void BKE_sequence_calc_disp(Scene *scene, Sequence *seq)
461 {
462         if (seq->startofs && seq->startstill)
463                 seq->startstill = 0;
464         if (seq->endofs && seq->endstill)
465                 seq->endstill = 0;
466         
467         seq->startdisp = seq->start + seq->startofs - seq->startstill;
468         seq->enddisp = seq->start + seq->len - seq->endofs + seq->endstill;
469         
470         seq->handsize = 10.0;  /* 10 frames */
471         if (seq->enddisp - seq->startdisp < 10) {
472                 seq->handsize = (float)(0.5 * (seq->enddisp - seq->startdisp));
473         }
474         else if (seq->enddisp - seq->startdisp > 250) {
475                 seq->handsize = (float)((seq->enddisp - seq->startdisp) / 25);
476         }
477
478         if (ELEM(seq->type, SEQ_TYPE_SOUND_RAM, SEQ_TYPE_SCENE)) {
479                 BKE_sequencer_update_sound_bounds(scene, seq);
480         }
481         else if (seq->type == SEQ_TYPE_META)
482                 seq_update_sound_bounds_recursive(scene, seq);
483 }
484
485 void BKE_sequence_calc(Scene *scene, Sequence *seq)
486 {
487         Sequence *seqm;
488         int min, max;
489
490         /* check all metas recursively */
491         seqm = seq->seqbase.first;
492         while (seqm) {
493                 if (seqm->seqbase.first) BKE_sequence_calc(scene, seqm);
494                 seqm = seqm->next;
495         }
496
497         /* effects and meta: automatic start and end */
498
499         if (seq->type & SEQ_TYPE_EFFECT) {
500                 /* pointers */
501                 if (seq->seq2 == NULL)
502                         seq->seq2 = seq->seq1;
503                 if (seq->seq3 == NULL)
504                         seq->seq3 = seq->seq1;
505
506                 /* effecten go from seq1 -> seq2: test */
507
508                 /* we take the largest start and smallest end */
509
510                 // seq->start = seq->startdisp = MAX2(seq->seq1->startdisp, seq->seq2->startdisp);
511                 // seq->enddisp = MIN2(seq->seq1->enddisp, seq->seq2->enddisp);
512
513                 if (seq->seq1) {
514                         /* XXX These resets should not be necessary, but users used to be able to
515                          *     edit effect's length, leading to strange results. See [#29190] */
516                         seq->startofs = seq->endofs = seq->startstill = seq->endstill = 0;
517                         seq->start = seq->startdisp = MAX3(seq->seq1->startdisp, seq->seq2->startdisp, seq->seq3->startdisp);
518                         seq->enddisp = MIN3(seq->seq1->enddisp, seq->seq2->enddisp, seq->seq3->enddisp);
519                         /* we cant help if strips don't overlap, it wont give useful results.
520                          * but at least ensure 'len' is never negative which causes bad bugs elsewhere. */
521                         if (seq->enddisp < seq->startdisp) {
522                                 /* simple start/end swap */
523                                 seq->start = seq->enddisp;
524                                 seq->enddisp = seq->startdisp;
525                                 seq->startdisp = seq->start;
526                                 seq->flag |= SEQ_INVALID_EFFECT;
527                         }
528                         else {
529                                 seq->flag &= ~SEQ_INVALID_EFFECT;
530                         }
531
532                         seq->len = seq->enddisp - seq->startdisp;
533                 }
534                 else {
535                         BKE_sequence_calc_disp(scene, seq);
536                 }
537         }
538         else {
539                 if (seq->type == SEQ_TYPE_META) {
540                         seqm = seq->seqbase.first;
541                         if (seqm) {
542                                 min =  MAXFRAME * 2;
543                                 max = -MAXFRAME * 2;
544                                 while (seqm) {
545                                         if (seqm->startdisp < min) min = seqm->startdisp;
546                                         if (seqm->enddisp > max) max = seqm->enddisp;
547                                         seqm = seqm->next;
548                                 }
549                                 seq->start = min + seq->anim_startofs;
550                                 seq->len = max - min;
551                                 seq->len -= seq->anim_startofs;
552                                 seq->len -= seq->anim_endofs;
553                         }
554                         seq_update_sound_bounds_recursive(scene, seq);
555                 }
556                 BKE_sequence_calc_disp(scene, seq);
557         }
558 }
559
560 /* note: caller should run calc_sequence(scene, seq) after */
561 void BKE_sequence_reload_new_file(Scene *scene, Sequence *seq, int lock_range)
562 {
563         char str[FILE_MAX];
564         int prev_startdisp = 0, prev_enddisp = 0;
565         /* note: don't rename the strip, will break animation curves */
566
567         if (ELEM7(seq->type,
568                   SEQ_TYPE_MOVIE, SEQ_TYPE_IMAGE, SEQ_TYPE_SOUND_RAM,
569                   SEQ_TYPE_SCENE, SEQ_TYPE_META, SEQ_TYPE_MOVIECLIP, SEQ_TYPE_MASK) == 0)
570         {
571                 return;
572         }
573
574         if (lock_range) {
575                 /* keep so we don't have to move the actual start and end points (only the data) */
576                 BKE_sequence_calc_disp(scene, seq);
577                 prev_startdisp = seq->startdisp;
578                 prev_enddisp = seq->enddisp;
579         }
580
581         switch (seq->type) {
582                 case SEQ_TYPE_IMAGE:
583                 {
584                         /* Hack? */
585                         size_t olen = MEM_allocN_len(seq->strip->stripdata) / sizeof(StripElem);
586
587                         seq->len = olen;
588                         seq->len -= seq->anim_startofs;
589                         seq->len -= seq->anim_endofs;
590                         if (seq->len < 0) {
591                                 seq->len = 0;
592                         }
593                         break;
594                 }
595                 case SEQ_TYPE_MOVIE:
596                         BLI_join_dirfile(str, sizeof(str), seq->strip->dir,
597                                          seq->strip->stripdata->name);
598                         BLI_path_abs(str, G.main->name);
599
600                         if (seq->anim) IMB_free_anim(seq->anim);
601                         seq->anim = openanim(str, IB_rect | ((seq->flag & SEQ_FILTERY) ? IB_animdeinterlace : 0), seq->streamindex);
602
603                         if (!seq->anim) {
604                                 return;
605                         }
606
607                         seq->len = IMB_anim_get_duration(seq->anim, seq->strip->proxy ? seq->strip->proxy->tc : IMB_TC_RECORD_RUN);
608         
609                         seq->anim_preseek = IMB_anim_get_preseek(seq->anim);
610
611                         seq->len -= seq->anim_startofs;
612                         seq->len -= seq->anim_endofs;
613                         if (seq->len < 0) {
614                                 seq->len = 0;
615                         }
616                         break;
617                 case SEQ_TYPE_MOVIECLIP:
618                         if (seq->clip == NULL)
619                                 return;
620
621                         seq->len = BKE_movieclip_get_duration(seq->clip);
622
623                         seq->len -= seq->anim_startofs;
624                         seq->len -= seq->anim_endofs;
625                         if (seq->len < 0) {
626                                 seq->len = 0;
627                         }
628                         break;
629                 case SEQ_TYPE_MASK:
630                         if (seq->mask == NULL)
631                                 return;
632                         seq->len = BKE_mask_get_duration(seq->mask);
633                         seq->len -= seq->anim_startofs;
634                         seq->len -= seq->anim_endofs;
635                         if (seq->len < 0) {
636                                 seq->len = 0;
637                         }
638                         break;
639                 case SEQ_TYPE_SOUND_RAM:
640 #ifdef WITH_AUDASPACE
641                         if (!seq->sound)
642                                 return;
643                         seq->len = ceil(AUD_getInfo(seq->sound->playback_handle).length * FPS);
644                         seq->len -= seq->anim_startofs;
645                         seq->len -= seq->anim_endofs;
646                         if (seq->len < 0) {
647                                 seq->len = 0;
648                         }
649 #else
650                         return;
651 #endif
652                         break;
653                 case SEQ_TYPE_SCENE:
654                 {
655                         seq->len = (seq->scene) ? seq->scene->r.efra - seq->scene->r.sfra + 1 : 0;
656                         seq->len -= seq->anim_startofs;
657                         seq->len -= seq->anim_endofs;
658                         if (seq->len < 0) {
659                                 seq->len = 0;
660                         }
661                         break;
662                 }
663         }
664
665         free_proxy_seq(seq);
666
667         if (lock_range) {
668                 BKE_sequence_tx_set_final_left(seq, prev_startdisp);
669                 BKE_sequence_tx_set_final_right(seq, prev_enddisp);
670                 BKE_sequence_single_fix(seq);
671         }
672         
673         BKE_sequence_calc(scene, seq);
674 }
675
676 void BKE_sequencer_sort(Scene *scene)
677 {
678         /* all strips together per kind, and in order of y location ("machine") */
679         ListBase seqbase, effbase;
680         Editing *ed = BKE_sequencer_editing_get(scene, FALSE);
681         Sequence *seq, *seqt;
682
683         
684         if (ed == NULL)
685                 return;
686
687         seqbase.first = seqbase.last = NULL;
688         effbase.first = effbase.last = NULL;
689
690         while ( (seq = ed->seqbasep->first) ) {
691                 BLI_remlink(ed->seqbasep, seq);
692
693                 if (seq->type & SEQ_TYPE_EFFECT) {
694                         seqt = effbase.first;
695                         while (seqt) {
696                                 if (seqt->machine >= seq->machine) {
697                                         BLI_insertlinkbefore(&effbase, seqt, seq);
698                                         break;
699                                 }
700                                 seqt = seqt->next;
701                         }
702                         if (seqt == NULL)
703                                 BLI_addtail(&effbase, seq);
704                 }
705                 else {
706                         seqt = seqbase.first;
707                         while (seqt) {
708                                 if (seqt->machine >= seq->machine) {
709                                         BLI_insertlinkbefore(&seqbase, seqt, seq);
710                                         break;
711                                 }
712                                 seqt = seqt->next;
713                         }
714                         if (seqt == NULL)
715                                 BLI_addtail(&seqbase, seq);
716                 }
717         }
718
719         BLI_movelisttolist(&seqbase, &effbase);
720         *(ed->seqbasep) = seqbase;
721 }
722
723 static int clear_scene_in_allseqs_cb(Sequence *seq, void *arg_pt)
724 {
725         if (seq->scene == (Scene *)arg_pt)
726                 seq->scene = NULL;
727         return 1;
728 }
729
730 void BKE_sequencer_clear_scene_in_allseqs(Main *bmain, Scene *scene)
731 {
732         Scene *scene_iter;
733
734         /* when a scene is deleted: test all seqs */
735         for (scene_iter = bmain->scene.first; scene_iter; scene_iter = scene_iter->id.next) {
736                 if (scene_iter != scene && scene_iter->ed) {
737                         BKE_sequencer_base_recursive_apply(&scene_iter->ed->seqbase, clear_scene_in_allseqs_cb, scene);
738                 }
739         }
740 }
741
742 typedef struct SeqUniqueInfo {
743         Sequence *seq;
744         char name_src[SEQ_NAME_MAXSTR];
745         char name_dest[SEQ_NAME_MAXSTR];
746         int count;
747         int match;
748 } SeqUniqueInfo;
749
750 static void seqbase_unique_name(ListBase *seqbasep, SeqUniqueInfo *sui)
751 {
752         Sequence *seq;
753         for (seq = seqbasep->first; seq; seq = seq->next) {
754                 if (sui->seq != seq && strcmp(sui->name_dest, seq->name + 2) == 0) {
755                         /* SEQ_NAME_MAXSTR - 2 for prefix, -1 for \0, -4 for the number */
756                         BLI_snprintf(sui->name_dest, sizeof(sui->name_dest), "%.59s.%03d",  sui->name_src, sui->count++);
757                         sui->match = 1; /* be sure to re-scan */
758                 }
759         }
760 }
761
762 static int seqbase_unique_name_recursive_cb(Sequence *seq, void *arg_pt)
763 {
764         if (seq->seqbase.first)
765                 seqbase_unique_name(&seq->seqbase, (SeqUniqueInfo *)arg_pt);
766         return 1;
767 }
768
769 void BKE_seqence_base_unique_name_recursive(ListBase *seqbasep, Sequence *seq)
770 {
771         SeqUniqueInfo sui;
772         char *dot;
773         sui.seq = seq;
774         BLI_strncpy(sui.name_src, seq->name + 2, sizeof(sui.name_src));
775         BLI_strncpy(sui.name_dest, seq->name + 2, sizeof(sui.name_dest));
776
777         sui.count = 1;
778         sui.match = 1; /* assume the worst to start the loop */
779
780         /* Strip off the suffix */
781         if ((dot = strrchr(sui.name_src, '.'))) {
782                 *dot = '\0';
783                 dot++;
784
785                 if (*dot)
786                         sui.count = atoi(dot) + 1;
787         }
788
789         while (sui.match) {
790                 sui.match = 0;
791                 seqbase_unique_name(seqbasep, &sui);
792                 BKE_sequencer_base_recursive_apply(seqbasep, seqbase_unique_name_recursive_cb, &sui);
793         }
794
795         BLI_strncpy(seq->name + 2, sui.name_dest, sizeof(seq->name) - 2);
796 }
797
798 static const char *give_seqname_by_type(int type)
799 {
800         switch (type) {
801                 case SEQ_TYPE_META:       return "Meta";
802                 case SEQ_TYPE_IMAGE:      return "Image";
803                 case SEQ_TYPE_SCENE:      return "Scene";
804                 case SEQ_TYPE_MOVIE:      return "Movie";
805                 case SEQ_TYPE_MOVIECLIP:  return "Clip";
806                 case SEQ_TYPE_MASK:       return "Mask";
807                 case SEQ_TYPE_SOUND_RAM:  return "Audio";
808                 case SEQ_TYPE_CROSS:      return "Cross";
809                 case SEQ_TYPE_GAMCROSS:   return "Gamma Cross";
810                 case SEQ_TYPE_ADD:        return "Add";
811                 case SEQ_TYPE_SUB:        return "Sub";
812                 case SEQ_TYPE_MUL:        return "Mul";
813                 case SEQ_TYPE_ALPHAOVER:  return "Alpha Over";
814                 case SEQ_TYPE_ALPHAUNDER: return "Alpha Under";
815                 case SEQ_TYPE_OVERDROP:   return "Over Drop";
816                 case SEQ_TYPE_WIPE:       return "Wipe";
817                 case SEQ_TYPE_GLOW:       return "Glow";
818                 case SEQ_TYPE_TRANSFORM:  return "Transform";
819                 case SEQ_TYPE_COLOR:      return "Color";
820                 case SEQ_TYPE_MULTICAM:   return "Multicam";
821                 case SEQ_TYPE_ADJUSTMENT: return "Adjustment";
822                 case SEQ_TYPE_SPEED:      return "Speed";
823                 default:
824                         return NULL;
825         }
826 }
827
828 const char *BKE_sequence_give_name(Sequence *seq)
829 {
830         const char *name = give_seqname_by_type(seq->type);
831
832         if (!name) {
833                 if (seq->type < SEQ_TYPE_EFFECT) {
834                         return seq->strip->dir;
835                 }
836                 else {
837                         return "Effect";
838                 }
839         }
840         return name;
841 }
842
843 /*********************** DO THE SEQUENCE *************************/
844
845 static void make_black_ibuf(ImBuf *ibuf)
846 {
847         unsigned int *rect;
848         float *rect_float;
849         int tot;
850
851         if (ibuf == NULL || (ibuf->rect == NULL && ibuf->rect_float == NULL)) {
852                 return;
853         }
854
855         tot = ibuf->x * ibuf->y;
856
857         rect = ibuf->rect;
858         rect_float = ibuf->rect_float;
859
860         if (rect) {
861                 memset(rect, 0, tot * sizeof(char) * 4);
862         }
863
864         if (rect_float) {
865                 memset(rect_float, 0, tot * sizeof(float) * 4);
866         }
867 }
868
869 static void multibuf(ImBuf *ibuf, float fmul)
870 {
871         char *rt;
872         float *rt_float;
873
874         int a, mul, icol;
875
876         mul = (int)(256.0f * fmul);
877         rt = (char *)ibuf->rect;
878         rt_float = ibuf->rect_float;
879
880         if (rt) {
881                 a = ibuf->x * ibuf->y;
882                 while (a--) {
883
884                         icol = (mul * rt[0]) >> 8;
885                         if (icol > 254) rt[0] = 255; else rt[0] = icol;
886                         icol = (mul * rt[1]) >> 8;
887                         if (icol > 254) rt[1] = 255; else rt[1] = icol;
888                         icol = (mul * rt[2]) >> 8;
889                         if (icol > 254) rt[2] = 255; else rt[2] = icol;
890                         icol = (mul * rt[3]) >> 8;
891                         if (icol > 254) rt[3] = 255; else rt[3] = icol;
892                         
893                         rt += 4;
894                 }
895         }
896         if (rt_float) {
897                 a = ibuf->x * ibuf->y;
898                 while (a--) {
899                         rt_float[0] *= fmul;
900                         rt_float[1] *= fmul;
901                         rt_float[2] *= fmul;
902                         rt_float[3] *= fmul;
903                         
904                         rt_float += 4;
905                 }
906         }
907 }
908
909 static float give_stripelem_index(Sequence *seq, float cfra)
910 {
911         float nr;
912         int sta = seq->start;
913         int end = seq->start + seq->len - 1;
914
915         if (seq->type & SEQ_TYPE_EFFECT) {
916                 end = seq->enddisp;
917         } 
918
919         if (end < sta) {
920                 return -1;
921         }
922
923         if (seq->flag & SEQ_REVERSE_FRAMES) {
924                 /*reverse frame in this sequence */
925                 if (cfra <= sta) nr = end - sta;
926                 else if (cfra >= end) nr = 0;
927                 else nr = end - cfra;
928         }
929         else {
930                 if (cfra <= sta) nr = 0;
931                 else if (cfra >= end) nr = end - sta;
932                 else nr = cfra - sta;
933         }
934         
935         if (seq->strobe < 1.0f) seq->strobe = 1.0f;
936         
937         if (seq->strobe > 1.0f) {
938                 nr -= fmodf((double)nr, (double)seq->strobe);
939         }
940
941         return nr;
942 }
943
944 StripElem *BKE_sequencer_give_stripelem(Sequence *seq, int cfra)
945 {
946         StripElem *se = seq->strip->stripdata;
947
948         if (seq->type == SEQ_TYPE_IMAGE) {
949                 /* only IMAGE strips use the whole array, MOVIE strips use only the first element,
950                  * all other strips don't use this...
951                  */
952
953                 int nr = (int) give_stripelem_index(seq, cfra);
954
955                 if (nr == -1 || se == NULL)
956                         return NULL;
957         
958                 se += nr + seq->anim_startofs;
959         }
960         return se;
961 }
962
963 static int evaluate_seq_frame_gen(Sequence **seq_arr, ListBase *seqbase, int cfra)
964 {
965         Sequence *seq;
966         int totseq = 0;
967
968         memset(seq_arr, 0, sizeof(Sequence *) * (MAXSEQ + 1));
969
970         seq = seqbase->first;
971         while (seq) {
972                 if (seq->startdisp <= cfra && seq->enddisp > cfra) {
973                         seq_arr[seq->machine] = seq;
974                         totseq++;
975                 }
976                 seq = seq->next;
977         }
978
979         return totseq;
980 }
981
982 int BKE_sequencer_evaluate_frame(Scene *scene, int cfra)
983 {
984         Editing *ed = BKE_sequencer_editing_get(scene, FALSE);
985         Sequence *seq_arr[MAXSEQ + 1];
986
987         if (ed == NULL)
988                 return 0;
989
990         return evaluate_seq_frame_gen(seq_arr, ed->seqbasep, cfra);
991 }
992
993 static int video_seq_is_rendered(Sequence *seq)
994 {
995         return (seq && !(seq->flag & SEQ_MUTE) && seq->type != SEQ_TYPE_SOUND_RAM);
996 }
997
998 static int get_shown_sequences(ListBase *seqbasep, int cfra, int chanshown, Sequence **seq_arr_out)
999 {
1000         Sequence *seq_arr[MAXSEQ + 1];
1001         int b = chanshown;
1002         int cnt = 0;
1003
1004         if (b > MAXSEQ) {
1005                 return 0;
1006         }
1007
1008         if (evaluate_seq_frame_gen(seq_arr, seqbasep, cfra)) {
1009                 if (b == 0) {
1010                         b = MAXSEQ;
1011                 }
1012                 for (; b > 0; b--) {
1013                         if (video_seq_is_rendered(seq_arr[b])) {
1014                                 break;
1015                         }
1016                 }
1017         }
1018         
1019         chanshown = b;
1020
1021         for (; b > 0; b--) {
1022                 if (video_seq_is_rendered(seq_arr[b])) {
1023                         if (seq_arr[b]->blend_mode == SEQ_BLEND_REPLACE) {
1024                                 break;
1025                         }
1026                 }
1027         }
1028
1029         for (; b <= chanshown && b >= 0; b++) {
1030                 if (video_seq_is_rendered(seq_arr[b])) {
1031                         seq_arr_out[cnt++] = seq_arr[b];
1032                 }
1033         }
1034
1035         return cnt;
1036 }
1037
1038 /*********************** proxy management *************************/
1039
1040 typedef struct SeqIndexBuildContext {
1041         struct IndexBuildContext *index_context;
1042
1043         int tc_flags;
1044         int size_flags;
1045         int quality;
1046
1047         Main *bmain;
1048         Scene *scene;
1049         Sequence *seq, *orig_seq;
1050 } SeqIndexBuildContext;
1051
1052 #define PROXY_MAXFILE (2 * FILE_MAXDIR + FILE_MAXFILE)
1053
1054 static IMB_Proxy_Size seq_rendersize_to_proxysize(int size)
1055 {
1056         if (size >= 100) {
1057                 return IMB_PROXY_NONE;
1058         }
1059         if (size >= 99) {
1060                 return IMB_PROXY_100;
1061         }
1062         if (size >= 75) {
1063                 return IMB_PROXY_75;
1064         }
1065         if (size >= 50) {
1066                 return IMB_PROXY_50;
1067         }
1068         return IMB_PROXY_25;
1069 }
1070
1071 static double seq_rendersize_to_scale_factor(int size)
1072 {
1073         if (size >= 99) {
1074                 return 1.0;
1075         }
1076         if (size >= 75) {
1077                 return 0.75;
1078         }
1079         if (size >= 50) {
1080                 return 0.50;
1081         }
1082         return 0.25;
1083 }
1084
1085 static void seq_open_anim_file(Sequence *seq)
1086 {
1087         char name[FILE_MAX];
1088         StripProxy *proxy;
1089
1090         if (seq->anim != NULL) {
1091                 return;
1092         }
1093
1094         BLI_join_dirfile(name, sizeof(name),
1095                          seq->strip->dir, seq->strip->stripdata->name);
1096         BLI_path_abs(name, G.main->name);
1097         
1098         seq->anim = openanim(name, IB_rect | ((seq->flag & SEQ_FILTERY) ? IB_animdeinterlace : 0), seq->streamindex);
1099
1100         if (seq->anim == NULL) {
1101                 return;
1102         }
1103
1104         proxy = seq->strip->proxy;
1105
1106         if (proxy == NULL) {
1107                 return;
1108         }
1109
1110         if (seq->flag & SEQ_USE_PROXY_CUSTOM_DIR) {
1111                 char dir[FILE_MAX];
1112                 BLI_strncpy(dir, seq->strip->proxy->dir, sizeof(dir));
1113                 BLI_path_abs(dir, G.main->name);
1114
1115                 IMB_anim_set_index_dir(seq->anim, dir);
1116         }
1117 }
1118
1119
1120 static int seq_proxy_get_fname(Sequence *seq, int cfra, int render_size, char *name)
1121 {
1122         int frameno;
1123         char dir[PROXY_MAXFILE];
1124
1125         if (!seq->strip->proxy) {
1126                 return FALSE;
1127         }
1128
1129         /* MOVIE tracks (only exception: custom files) are now handled 
1130          * internally by ImBuf module for various reasons: proper time code
1131          * support, quicker index build, using one file instead
1132          * of a full directory of jpeg files, etc. Trying to support old
1133          * and new method at once could lead to funny effects, if people
1134          * have both, a directory full of jpeg files and proxy avis, so
1135          * sorry folks, please rebuild your proxies... */
1136
1137         if (seq->flag & (SEQ_USE_PROXY_CUSTOM_DIR | SEQ_USE_PROXY_CUSTOM_FILE)) {
1138                 BLI_strncpy(dir, seq->strip->proxy->dir, sizeof(dir));
1139         }
1140         else if (seq->type == SEQ_TYPE_IMAGE) {
1141                 BLI_snprintf(dir, PROXY_MAXFILE, "%s/BL_proxy", seq->strip->dir);
1142         }
1143         else {
1144                 return FALSE;
1145         }
1146
1147         if (seq->flag & SEQ_USE_PROXY_CUSTOM_FILE) {
1148                 BLI_join_dirfile(name, PROXY_MAXFILE,
1149                                  dir, seq->strip->proxy->file);
1150                 BLI_path_abs(name, G.main->name);
1151
1152                 return TRUE;
1153         }
1154
1155         /* generate a separate proxy directory for each preview size */
1156
1157         if (seq->type == SEQ_TYPE_IMAGE) {
1158                 BLI_snprintf(name, PROXY_MAXFILE, "%s/images/%d/%s_proxy", dir, render_size,
1159                              BKE_sequencer_give_stripelem(seq, cfra)->name);
1160                 frameno = 1;
1161         }
1162         else {
1163                 frameno = (int)give_stripelem_index(seq, cfra) + seq->anim_startofs;
1164                 BLI_snprintf(name, PROXY_MAXFILE, "%s/proxy_misc/%d/####", dir, render_size);
1165         }
1166
1167         BLI_path_abs(name, G.main->name);
1168         BLI_path_frame(name, frameno, 0);
1169
1170         strcat(name, ".jpg");
1171
1172         return TRUE;
1173 }
1174
1175 static ImBuf *seq_proxy_fetch(SeqRenderData context, Sequence *seq, int cfra)
1176 {
1177         char name[PROXY_MAXFILE];
1178         IMB_Proxy_Size psize = seq_rendersize_to_proxysize(context.preview_render_size);
1179         int size_flags;
1180         int render_size = context.preview_render_size;
1181
1182         /* dirty hack to distinguish 100% render size from PROXY_100 */
1183         if (render_size == 99) {
1184                 render_size = 100;
1185         }
1186
1187         if (!(seq->flag & SEQ_USE_PROXY)) {
1188                 return NULL;
1189         }
1190
1191         size_flags = seq->strip->proxy->build_size_flags;
1192
1193         /* only use proxies, if they are enabled (even if present!) */
1194         if (psize == IMB_PROXY_NONE || ((size_flags & psize) != psize)) {
1195                 return NULL;
1196         }
1197
1198         if (seq->flag & SEQ_USE_PROXY_CUSTOM_FILE) {
1199                 int frameno = (int)give_stripelem_index(seq, cfra) + seq->anim_startofs;
1200                 if (seq->strip->proxy->anim == NULL) {
1201                         if (seq_proxy_get_fname(seq, cfra, render_size, name) == 0) {
1202                                 return NULL;
1203                         }
1204  
1205                         seq->strip->proxy->anim = openanim(name, IB_rect, 0);
1206                 }
1207                 if (seq->strip->proxy->anim == NULL) {
1208                         return NULL;
1209                 }
1210  
1211                 seq_open_anim_file(seq);
1212
1213                 frameno = IMB_anim_index_get_frame_index(seq->anim, seq->strip->proxy->tc, frameno);
1214
1215                 return IMB_anim_absolute(seq->strip->proxy->anim, frameno, IMB_TC_NONE, IMB_PROXY_NONE);
1216         }
1217  
1218         if (seq_proxy_get_fname(seq, cfra, render_size, name) == 0) {
1219                 return NULL;
1220         }
1221
1222         if (BLI_exists(name)) {
1223                 return IMB_loadiffname(name, IB_rect);
1224         }
1225         else {
1226                 return NULL;
1227         }
1228 }
1229
1230 static void seq_proxy_build_frame(SeqRenderData context, Sequence *seq, int cfra, int proxy_render_size)
1231 {
1232         char name[PROXY_MAXFILE];
1233         int quality;
1234         int rectx, recty;
1235         int ok;
1236         ImBuf *ibuf;
1237
1238         if (!seq_proxy_get_fname(seq, cfra, proxy_render_size, name)) {
1239                 return;
1240         }
1241
1242         ibuf = seq_render_strip(context, seq, cfra);
1243
1244         rectx = (proxy_render_size * context.scene->r.xsch) / 100;
1245         recty = (proxy_render_size * context.scene->r.ysch) / 100;
1246
1247         if (ibuf->x != rectx || ibuf->y != recty) {
1248                 IMB_scalefastImBuf(ibuf, (short)rectx, (short)recty);
1249         }
1250
1251         /* depth = 32 is intentionally left in, otherwise ALPHA channels
1252          * won't work... */
1253         quality = seq->strip->proxy->quality;
1254         ibuf->ftype = JPG | quality;
1255
1256         /* unsupported feature only confuses other s/w */
1257         if (ibuf->planes == 32)
1258                 ibuf->planes = 24;
1259
1260         BLI_make_existing_file(name);
1261         
1262         ok = IMB_saveiff(ibuf, name, IB_rect | IB_zbuf | IB_zbuffloat);
1263         if (ok == 0) {
1264                 perror(name);
1265         }
1266
1267         IMB_freeImBuf(ibuf);
1268 }
1269
1270 SeqIndexBuildContext *BKE_sequencer_proxy_rebuild_context(Main *bmain, Scene *scene, Sequence *seq)
1271 {
1272         SeqIndexBuildContext *context;
1273         Sequence *nseq;
1274
1275         if (!seq->strip || !seq->strip->proxy) {
1276                 return NULL;
1277         }
1278
1279         if (!(seq->flag & SEQ_USE_PROXY)) {
1280                 return NULL;
1281         }
1282
1283         context = MEM_callocN(sizeof(SeqIndexBuildContext), "seq proxy rebuild context");
1284
1285         nseq = BKE_sequence_dupli_recursive(scene, scene, seq, 0);
1286
1287         context->tc_flags   = nseq->strip->proxy->build_tc_flags;
1288         context->size_flags = nseq->strip->proxy->build_size_flags;
1289         context->quality    = nseq->strip->proxy->quality;
1290
1291         context->bmain = bmain;
1292         context->scene = scene;
1293         context->orig_seq = seq;
1294         context->seq = nseq;
1295
1296         if (nseq->type == SEQ_TYPE_MOVIE) {
1297                 seq_open_anim_file(nseq);
1298
1299                 if (nseq->anim) {
1300                         context->index_context = IMB_anim_index_rebuild_context(nseq->anim,
1301                                 context->tc_flags, context->size_flags, context->quality);
1302                 }
1303         }
1304
1305         return context;
1306 }
1307
1308 void BKE_sequencer_proxy_rebuild(SeqIndexBuildContext *context, short *stop, short *do_update, float *progress)
1309 {
1310         SeqRenderData render_context;
1311         Sequence *seq = context->seq;
1312         Scene *scene = context->scene;
1313         int cfra;
1314
1315         if (seq->type == SEQ_TYPE_MOVIE) {
1316                 if (context->index_context) {
1317                         IMB_anim_index_rebuild(context->index_context, stop, do_update, progress);
1318                 }
1319
1320                 return;
1321         }
1322
1323         if (!(seq->flag & SEQ_USE_PROXY)) {
1324                 return;
1325         }
1326
1327         /* that's why it is called custom... */
1328         if (seq->flag & SEQ_USE_PROXY_CUSTOM_FILE) {
1329                 return;
1330         }
1331
1332         /* fail safe code */
1333
1334         render_context = BKE_sequencer_new_render_data(context->bmain, context->scene,
1335                                             (scene->r.size * (float) scene->r.xsch) / 100.0f + 0.5f,
1336                                             (scene->r.size * (float) scene->r.ysch) / 100.0f + 0.5f, 100);
1337
1338         for (cfra = seq->startdisp + seq->startstill;  cfra < seq->enddisp - seq->endstill; cfra++) {
1339                 if (context->size_flags & IMB_PROXY_25) {
1340                         seq_proxy_build_frame(render_context, seq, cfra, 25);
1341                 }
1342                 if (context->size_flags & IMB_PROXY_50) {
1343                         seq_proxy_build_frame(render_context, seq, cfra, 50);
1344                 }
1345                 if (context->size_flags & IMB_PROXY_75) {
1346                         seq_proxy_build_frame(render_context, seq, cfra, 75);
1347                 }
1348                 if (context->size_flags & IMB_PROXY_100) {
1349                         seq_proxy_build_frame(render_context, seq, cfra, 100);
1350                 }
1351
1352                 *progress = (float) cfra / (seq->enddisp - seq->endstill - seq->startdisp + seq->startstill);
1353                 *do_update = TRUE;
1354
1355                 if (*stop || G.is_break)
1356                         break;
1357         }
1358 }
1359
1360 void BKE_sequencer_proxy_rebuild_finish(SeqIndexBuildContext *context, short stop)
1361 {
1362         if (context->index_context) {
1363                 IMB_close_anim_proxies(context->seq->anim);
1364                 IMB_close_anim_proxies(context->orig_seq->anim);
1365                 IMB_anim_index_rebuild_finish(context->index_context, stop);
1366         }
1367
1368         seq_free_sequence_recurse(context->scene, context->seq);
1369
1370         MEM_freeN(context);
1371 }
1372
1373 /*********************** color balance *************************/
1374
1375 static StripColorBalance calc_cb(StripColorBalance *cb_)
1376 {
1377         StripColorBalance cb = *cb_;
1378         int c;
1379
1380         for (c = 0; c < 3; c++) {
1381                 cb.lift[c] = 2.0f - cb.lift[c];
1382         }
1383
1384         if (cb.flag & SEQ_COLOR_BALANCE_INVERSE_LIFT) {
1385                 for (c = 0; c < 3; c++) {
1386                         /* tweak to give more subtle results
1387                          * values above 1.0 are scaled */
1388                         if (cb.lift[c] > 1.0f)
1389                                 cb.lift[c] = pow(cb.lift[c] - 1.0f, 2.0) + 1.0;
1390
1391                         cb.lift[c] = 2.0f - cb.lift[c];
1392                 }
1393         }
1394
1395         if (cb.flag & SEQ_COLOR_BALANCE_INVERSE_GAIN) {
1396                 for (c = 0; c < 3; c++) {
1397                         if (cb.gain[c] != 0.0f) {
1398                                 cb.gain[c] = 1.0f / cb.gain[c];
1399                         }
1400                         else {
1401                                 cb.gain[c] = 1000000; /* should be enough :) */
1402                         }
1403                 }
1404         }
1405
1406         if (!(cb.flag & SEQ_COLOR_BALANCE_INVERSE_GAMMA)) {
1407                 for (c = 0; c < 3; c++) {
1408                         if (cb.gamma[c] != 0.0f) {
1409                                 cb.gamma[c] = 1.0f / cb.gamma[c];
1410                         }
1411                         else {
1412                                 cb.gamma[c] = 1000000; /* should be enough :) */
1413                         }
1414                 }
1415         }
1416
1417         return cb;
1418 }
1419
1420 /* note: lift is actually 2-lift */
1421 MINLINE float color_balance_fl(float in, const float lift, const float gain, const float gamma, const float mul)
1422 {
1423         float x = (((in - 1.0f) * lift) + 1.0f) * gain;
1424
1425         /* prevent NaN */
1426         if (x < 0.f)
1427                 x = 0.f;
1428
1429         return powf(x, gamma) * mul;
1430 }
1431
1432 static void make_cb_table_byte(float lift, float gain, float gamma,
1433                                unsigned char *table, float mul)
1434 {
1435         int y;
1436
1437         for (y = 0; y < 256; y++) {
1438                 float v = color_balance_fl((float)y * (1.0f / 255.0f), lift, gain, gamma, mul);
1439
1440                 table[y] = FTOCHAR(v);
1441         }
1442 }
1443
1444 static void make_cb_table_float(float lift, float gain, float gamma,
1445                                 float *table, float mul)
1446 {
1447         int y;
1448
1449         for (y = 0; y < 256; y++) {
1450                 float v = color_balance_fl((float)y * (1.0f / 255.0f), lift, gain, gamma, mul);
1451
1452                 table[y] = v;
1453         }
1454 }
1455
1456 static void color_balance_byte_byte(StripColorBalance *cb_, unsigned char *rect, unsigned char *mask_rect, int width, int height, float mul)
1457 {
1458         unsigned char cb_tab[3][256];
1459         int c;
1460         unsigned char *p = rect;
1461         unsigned char *e = p + width * 4 * height;
1462         unsigned char *m = mask_rect;
1463
1464         StripColorBalance cb = calc_cb(cb_);
1465
1466         for (c = 0; c < 3; c++) {
1467                 make_cb_table_byte(cb.lift[c], cb.gain[c], cb.gamma[c], cb_tab[c], mul);
1468         }
1469
1470         while (p < e) {
1471                 if (m) {
1472                         float t[3] = {m[0] / 255.0f, m[1] / 255.0f, m[2] / 255.0f};
1473
1474                         p[0] = p[0] * (1.0f - t[0]) + t[0] * cb_tab[0][p[0]];
1475                         p[1] = p[1] * (1.0f - t[1]) + t[1] * cb_tab[1][p[1]];
1476                         p[2] = p[2] * (1.0f - t[2]) + t[2] * cb_tab[2][p[2]];
1477
1478                         m += 4;
1479                 }
1480                 else {
1481                         p[0] = cb_tab[0][p[0]];
1482                         p[1] = cb_tab[1][p[1]];
1483                         p[2] = cb_tab[2][p[2]];
1484                 }
1485                 
1486                 p += 4;
1487         }
1488 }
1489
1490 static void color_balance_byte_float(StripColorBalance *cb_, unsigned char *rect, float *rect_float, unsigned char *mask_rect, int width, int height, float mul)
1491 {
1492         float cb_tab[4][256];
1493         int c, i;
1494         unsigned char *p = rect;
1495         unsigned char *e = p + width * 4 * height;
1496         unsigned char *m = mask_rect;
1497         float *o;
1498         StripColorBalance cb;
1499
1500         o = rect_float;
1501
1502         cb = calc_cb(cb_);
1503
1504         for (c = 0; c < 3; c++) {
1505                 make_cb_table_float(cb.lift[c], cb.gain[c], cb.gamma[c], cb_tab[c], mul);
1506         }
1507
1508         for (i = 0; i < 256; i++) {
1509                 cb_tab[3][i] = ((float)i) * (1.0f / 255.0f);
1510         }
1511
1512         while (p < e) {
1513                 if (m) {
1514                         float t[3] = {m[0] / 255.0f, m[1] / 255.0f, m[2] / 255.0f};
1515
1516                         p[0] = p[0] * (1.0f - t[0]) + t[0] * cb_tab[0][p[0]];
1517                         p[1] = p[1] * (1.0f - t[1]) + t[1] * cb_tab[1][p[1]];
1518                         p[2] = p[2] * (1.0f - t[2]) + t[2] * cb_tab[2][p[2]];
1519
1520                         m += 4;
1521                 }
1522                 else {
1523                         o[0] = cb_tab[0][p[0]];
1524                         o[1] = cb_tab[1][p[1]];
1525                         o[2] = cb_tab[2][p[2]];
1526                 }
1527
1528                 o[3] = cb_tab[3][p[3]];
1529
1530                 p += 4; o += 4;
1531         }
1532 }
1533
1534 static void color_balance_float_float(StripColorBalance *cb_, float *rect_float, float *mask_rect_float, int width, int height, float mul)
1535 {
1536         float *p = rect_float;
1537         float *e = rect_float + width * 4 * height;
1538         float *m = mask_rect_float;
1539         StripColorBalance cb = calc_cb(cb_);
1540
1541         while (p < e) {
1542                 int c;
1543                 for (c = 0; c < 3; c++) {
1544                         float t = color_balance_fl(p[c], cb.lift[c], cb.gain[c], cb.gamma[c], mul);
1545
1546                         if (m)
1547                                 p[c] = p[c] * (1.0f - m[c]) + t * m[c];
1548                         else
1549                                 p[c] = t;
1550                 }
1551
1552                 p += 4;
1553                 if (m)
1554                         m += 4;
1555         }
1556 }
1557
1558 typedef struct ColorBalanceInitData {
1559         StripColorBalance *cb;
1560         ImBuf *ibuf;
1561         float mul;
1562         ImBuf *mask;
1563         short make_float;
1564 } ColorBalanceInitData;
1565
1566 typedef struct ColorBalanceThread {
1567         StripColorBalance *cb;
1568         float mul;
1569
1570         int width, height;
1571
1572         unsigned char *rect, *mask_rect;
1573         float *rect_float, *mask_rect_float;
1574
1575         short make_float;
1576 } ColorBalanceThread;
1577
1578 static void color_balance_init_handle(void *handle_v, int start_line, int tot_line, void *init_data_v)
1579 {
1580         ColorBalanceThread *handle = (ColorBalanceThread *) handle_v;
1581         ColorBalanceInitData *init_data = (ColorBalanceInitData *) init_data_v;
1582         ImBuf *ibuf = init_data->ibuf;
1583         ImBuf *mask = init_data->mask;
1584
1585         int offset = 4 * start_line * ibuf->x;
1586
1587         memset(handle, 0, sizeof(ColorBalanceThread));
1588
1589         handle->cb = init_data->cb;
1590         handle->mul = init_data->mul;
1591         handle->width = ibuf->x;
1592         handle->height = tot_line;
1593         handle->make_float = init_data->make_float;
1594
1595         if (ibuf->rect)
1596                 handle->rect = (unsigned char *) ibuf->rect + offset;
1597
1598         if (ibuf->rect_float)
1599                 handle->rect_float = ibuf->rect_float + offset;
1600
1601         if (mask) {
1602                 if (mask->rect)
1603                         handle->mask_rect = (unsigned char *) mask->rect + offset;
1604
1605                 if (mask->rect_float)
1606                         handle->mask_rect_float = mask->rect_float + offset;
1607         }
1608         else {
1609                 handle->mask_rect = NULL;
1610                 handle->mask_rect_float = NULL;
1611         }
1612 }
1613
1614 static void *color_balance_do_thread(void *thread_data_v)
1615 {
1616         ColorBalanceThread *thread_data = (ColorBalanceThread *) thread_data_v;
1617         StripColorBalance *cb = thread_data->cb;
1618         int width = thread_data->width, height = thread_data->height;
1619         unsigned char *rect = thread_data->rect;
1620         unsigned char *mask_rect = thread_data->mask_rect;
1621         float *rect_float = thread_data->rect_float;
1622         float *mask_rect_float = thread_data->mask_rect_float;
1623         float mul = thread_data->mul;
1624
1625         if (rect_float) {
1626                 color_balance_float_float(cb, rect_float, mask_rect_float, width, height, mul);
1627         }
1628         else if (thread_data->make_float) {
1629                 color_balance_byte_float(cb, rect, rect_float, mask_rect, width, height, mul);
1630         }
1631         else {
1632                 color_balance_byte_byte(cb, rect, mask_rect, width, height, mul);
1633         }
1634
1635         return NULL;
1636 }
1637
1638 ImBuf *BKE_sequencer_render_mask_input(SeqRenderData context, int mask_input_type, Sequence *mask_sequence, Mask *mask_id, int cfra, int make_float)
1639 {
1640         ImBuf *mask_input = NULL;
1641
1642         if (mask_input_type == SEQUENCE_MASK_INPUT_STRIP) {
1643                 if (mask_sequence) {
1644                         mask_input = seq_render_strip(context, mask_sequence, cfra);
1645
1646                         if (make_float) {
1647                                 if (!mask_input->rect_float)
1648                                         IMB_float_from_rect(mask_input);
1649                         }
1650                         else {
1651                                 if (!mask_input->rect)
1652                                         IMB_rect_from_float(mask_input);
1653                         }
1654                 }
1655         }
1656         else if (mask_input_type == SEQUENCE_MASK_INPUT_ID) {
1657                 mask_input = seq_render_mask(context, mask_id, cfra, make_float);
1658         }
1659
1660         return mask_input;
1661 }
1662
1663 void BKE_sequencer_color_balance_apply(StripColorBalance *cb, ImBuf *ibuf, float mul, short make_float, ImBuf *mask_input)
1664 {
1665         ColorBalanceInitData init_data;
1666
1667         if (!ibuf->rect_float && make_float)
1668                 imb_addrectfloatImBuf(ibuf);
1669
1670         init_data.cb = cb;
1671         init_data.ibuf = ibuf;
1672         init_data.mul = mul;
1673         init_data.mask = NULL;
1674         init_data.make_float = make_float;
1675         init_data.mask = mask_input;
1676
1677         IMB_processor_apply_threaded(ibuf->y, sizeof(ColorBalanceThread), &init_data,
1678                                  color_balance_init_handle, color_balance_do_thread);
1679
1680         /* color balance either happens on float buffer or byte buffer, but never on both,
1681          * free byte buffer if there's float buffer since float buffer would be used for
1682          * color balance in favor of byte buffer
1683          */
1684         if (ibuf->rect_float && ibuf->rect)
1685                 imb_freerectImBuf(ibuf);
1686 }
1687
1688 /*
1689  *  input preprocessing for SEQ_TYPE_IMAGE, SEQ_TYPE_MOVIE, SEQ_TYPE_MOVIECLIP and SEQ_TYPE_SCENE
1690  *
1691  *  Do all the things you can't really do afterwards using sequence effects
1692  *  (read: before rescaling to render resolution has been done)
1693  *
1694  *  Order is important!
1695  *
1696  *  - Deinterlace
1697  *  - Crop and transform in image source coordinate space
1698  *  - Flip X + Flip Y (could be done afterwards, backward compatibility)
1699  *  - Promote image to float data (affects pipeline operations afterwards)
1700  *  - Color balance (is most efficient in the byte -> float
1701  *    (future: half -> float should also work fine!)
1702  *    case, if done on load, since we can use lookup tables)
1703  *  - Premultiply
1704  */
1705
1706 int BKE_sequencer_input_have_to_preprocess(SeqRenderData UNUSED(context), Sequence *seq, float UNUSED(cfra))
1707 {
1708         float mul;
1709
1710         if (seq->flag & (SEQ_FILTERY | SEQ_USE_CROP | SEQ_USE_TRANSFORM | SEQ_FLIPX | SEQ_FLIPY | SEQ_MAKE_PREMUL | SEQ_MAKE_FLOAT)) {
1711                 return TRUE;
1712         }
1713
1714         mul = seq->mul;
1715
1716         if (seq->blend_mode == SEQ_BLEND_REPLACE) {
1717                 mul *= seq->blend_opacity / 100.0f;
1718         }
1719
1720         if (mul != 1.0f) {
1721                 return TRUE;
1722         }
1723
1724         if (seq->sat != 1.0f) {
1725                 return TRUE;
1726         }
1727
1728         if (seq->modifiers.first) {
1729                 return TRUE;
1730         }
1731                 
1732         return FALSE;
1733 }
1734
1735 static ImBuf *input_preprocess(SeqRenderData context, Sequence *seq, float cfra, ImBuf *ibuf,
1736                                int is_proxy_image, int is_preprocessed)
1737 {
1738         float mul;
1739
1740         ibuf = IMB_makeSingleUser(ibuf);
1741
1742         if ((seq->flag & SEQ_FILTERY) &&
1743             !ELEM(seq->type, SEQ_TYPE_MOVIE, SEQ_TYPE_MOVIECLIP))
1744         {
1745                 IMB_filtery(ibuf);
1746         }
1747
1748         if (seq->flag & (SEQ_USE_CROP | SEQ_USE_TRANSFORM)) {
1749                 StripCrop c = {0};
1750                 StripTransform t = {0};
1751                 int sx, sy, dx, dy;
1752                 double xscale = 1.0;
1753                 double yscale = 1.0;
1754
1755                 if (is_proxy_image) {
1756                         double f = seq_rendersize_to_scale_factor(context.preview_render_size);
1757
1758                         if (f != 1.0) {
1759                                 IMB_scalefastImBuf(ibuf, ibuf->x / f, ibuf->y / f);
1760                         }
1761                 }
1762
1763                 if (seq->flag & SEQ_USE_CROP && seq->strip->crop) {
1764                         c = *seq->strip->crop;
1765                 }
1766                 if (seq->flag & SEQ_USE_TRANSFORM && seq->strip->transform) {
1767                         t = *seq->strip->transform;
1768                 }
1769
1770                 xscale = context.scene->r.xsch ? ((double) context.rectx / (double) context.scene->r.xsch) : 1.0;
1771                 yscale = context.scene->r.ysch ? ((double) context.recty / (double) context.scene->r.ysch) : 1.0;
1772
1773                 c.left *= xscale; c.right *= xscale;
1774                 c.top *= yscale; c.bottom *= yscale;
1775
1776                 t.xofs *= xscale; t.yofs *= yscale;
1777
1778                 sx = ibuf->x - c.left - c.right;
1779                 sy = ibuf->y - c.top - c.bottom;
1780                 dx = sx;
1781                 dy = sy;
1782
1783                 if (seq->flag & SEQ_USE_TRANSFORM) {
1784                         if (is_preprocessed) {
1785                                 dx = context.rectx;
1786                                 dy = context.recty;
1787                         }
1788                         else {
1789                                 dx = context.scene->r.xsch;
1790                                 dy = context.scene->r.ysch;
1791                         }
1792                 }
1793
1794                 if (c.top  + c.bottom >= ibuf->y ||
1795                     c.left + c.right  >= ibuf->x ||
1796                     t.xofs >= dx || t.yofs >= dy)
1797                 {
1798                         make_black_ibuf(ibuf);
1799                 }
1800                 else {
1801                         ImBuf *i = IMB_allocImBuf(dx, dy, 32, ibuf->rect_float ? IB_rectfloat : IB_rect);
1802
1803                         IMB_rectcpy(i, ibuf, t.xofs, t.yofs, c.left, c.bottom, sx, sy);
1804                         
1805                         IMB_freeImBuf(ibuf);
1806
1807                         ibuf = i;
1808                 }
1809         } 
1810
1811         if (seq->flag & SEQ_FLIPX) {
1812                 IMB_flipx(ibuf);
1813         }
1814         
1815         if (seq->flag & SEQ_FLIPY) {
1816                 IMB_flipy(ibuf);
1817         }
1818
1819         if (seq->sat != 1.0f) {
1820                 IMB_saturation(ibuf, seq->sat);
1821         }
1822
1823         mul = seq->mul;
1824
1825         if (seq->blend_mode == SEQ_BLEND_REPLACE) {
1826                 mul *= seq->blend_opacity / 100.0f;
1827         }
1828
1829         if (seq->flag & SEQ_MAKE_FLOAT) {
1830                 if (!ibuf->rect_float) {
1831                         IMB_colormanagement_imbuf_to_sequencer_space(ibuf, TRUE);
1832                 }
1833
1834                 if (ibuf->rect) {
1835                         imb_freerectImBuf(ibuf);
1836                 }
1837         }
1838
1839         if (mul != 1.0f) {
1840                 multibuf(ibuf, mul);
1841         }
1842
1843         if (seq->flag & SEQ_MAKE_PREMUL) {
1844                 if (ibuf->planes == 32 && ibuf->zbuf == NULL) {
1845                         IMB_premultiply_alpha(ibuf);
1846                 }
1847         }
1848
1849         if (ibuf->x != context.rectx || ibuf->y != context.recty) {
1850                 if (context.scene->r.mode & R_OSA) {
1851                         IMB_scaleImBuf(ibuf, (short)context.rectx, (short)context.recty);
1852                 }
1853                 else {
1854                         IMB_scalefastImBuf(ibuf, (short)context.rectx, (short)context.recty);
1855                 }
1856         }
1857
1858         if (seq->modifiers.first) {
1859                 ImBuf *ibuf_new = BKE_sequence_modifier_apply_stack(context, seq, ibuf, cfra);
1860
1861                 if (ibuf_new != ibuf) {
1862                         IMB_freeImBuf(ibuf);
1863                         ibuf = ibuf_new;
1864                 }
1865         }
1866
1867         return ibuf;
1868 }
1869
1870 static ImBuf *copy_from_ibuf_still(SeqRenderData context, Sequence *seq, float nr)
1871 {
1872         ImBuf *rval = NULL;
1873         ImBuf *ibuf = NULL;
1874
1875         if (nr == 0) {
1876                 ibuf = BKE_sequencer_cache_get(context, seq, seq->start, SEQ_STRIPELEM_IBUF_STARTSTILL);
1877         }
1878         else if (nr == seq->len - 1) {
1879                 ibuf = BKE_sequencer_cache_get(context, seq, seq->start, SEQ_STRIPELEM_IBUF_ENDSTILL);
1880         }
1881
1882         if (ibuf) {
1883                 rval = IMB_dupImBuf(ibuf);
1884                 IMB_freeImBuf(ibuf);
1885         }
1886
1887         return rval;
1888 }
1889
1890 static void copy_to_ibuf_still(SeqRenderData context, Sequence *seq, float nr, ImBuf *ibuf)
1891 {
1892         if (nr == 0 || nr == seq->len - 1) {
1893                 /* we have to store a copy, since the passed ibuf
1894                  * could be preprocessed afterwards (thereby silently
1895                  * changing the cached image... */
1896                 ibuf = IMB_dupImBuf(ibuf);
1897
1898                 if (nr == 0) {
1899                         BKE_sequencer_cache_put(context, seq, seq->start, SEQ_STRIPELEM_IBUF_STARTSTILL, ibuf);
1900                 } 
1901
1902                 if (nr == seq->len - 1) {
1903                         BKE_sequencer_cache_put(context, seq, seq->start, SEQ_STRIPELEM_IBUF_ENDSTILL, ibuf);
1904                 }
1905
1906                 IMB_freeImBuf(ibuf);
1907         }
1908 }
1909
1910 /*********************** strip rendering functions  *************************/
1911
1912 typedef struct RenderEffectInitData {
1913         struct SeqEffectHandle *sh;
1914         SeqRenderData context;
1915         Sequence *seq;
1916         float cfra, facf0, facf1;
1917         ImBuf *ibuf1, *ibuf2, *ibuf3;
1918
1919         ImBuf *out;
1920 } RenderEffectInitData;
1921
1922 typedef struct RenderEffectThread {
1923         struct SeqEffectHandle *sh;
1924         SeqRenderData context;
1925         Sequence *seq;
1926         float cfra, facf0, facf1;
1927         ImBuf *ibuf1, *ibuf2, *ibuf3;
1928
1929         ImBuf *out;
1930         int start_line, tot_line;
1931 } RenderEffectThread;
1932
1933 static void render_effect_execute_init_handle(void *handle_v, int start_line, int tot_line, void *init_data_v)
1934 {
1935         RenderEffectThread *handle = (RenderEffectThread *) handle_v;
1936         RenderEffectInitData *init_data = (RenderEffectInitData *) init_data_v;
1937
1938         handle->sh = init_data->sh;
1939         handle->context = init_data->context;
1940         handle->seq = init_data->seq;
1941         handle->cfra = init_data->cfra;
1942         handle->facf0 = init_data->facf0;
1943         handle->facf1 = init_data->facf1;
1944         handle->ibuf1 = init_data->ibuf1;
1945         handle->ibuf2 = init_data->ibuf2;
1946         handle->ibuf3 = init_data->ibuf3;
1947         handle->out = init_data->out;
1948
1949         handle->start_line = start_line;
1950         handle->tot_line = tot_line;
1951 }
1952
1953 static void *render_effect_execute_do_thread(void *thread_data_v)
1954 {
1955         RenderEffectThread *thread_data = (RenderEffectThread *) thread_data_v;
1956
1957         thread_data->sh->execute_slice(thread_data->context, thread_data->seq, thread_data->cfra,
1958                                        thread_data->facf0, thread_data->facf1, thread_data->ibuf1,
1959                                        thread_data->ibuf2, thread_data->ibuf3, thread_data->start_line,
1960                                        thread_data->tot_line, thread_data->out);
1961
1962         return NULL;
1963 }
1964
1965 static ImBuf *seq_render_effect_execute_threaded(struct SeqEffectHandle *sh, SeqRenderData context, Sequence *seq,
1966                                                  float cfra, float facf0, float facf1,
1967                                                  ImBuf *ibuf1, ImBuf *ibuf2, ImBuf *ibuf3)
1968 {
1969         RenderEffectInitData init_data;
1970         ImBuf *out = sh->init_execution(context, ibuf1, ibuf2, ibuf3);
1971
1972         init_data.sh = sh;
1973         init_data.context = context;
1974         init_data.seq = seq;
1975         init_data.cfra = cfra;
1976         init_data.facf0 = facf0;
1977         init_data.facf1 = facf1;
1978         init_data.ibuf1 = ibuf1;
1979         init_data.ibuf2 = ibuf2;
1980         init_data.ibuf3 = ibuf3;
1981         init_data.out = out;
1982
1983         IMB_processor_apply_threaded(out->y, sizeof(RenderEffectThread), &init_data,
1984                                  render_effect_execute_init_handle, render_effect_execute_do_thread);
1985
1986         return out;
1987 }
1988
1989 static ImBuf *seq_render_effect_strip_impl(SeqRenderData context, Sequence *seq, float cfra)
1990 {
1991         float fac, facf;
1992         int early_out;
1993         int i;
1994         struct SeqEffectHandle sh = BKE_sequence_get_effect(seq);
1995         FCurve *fcu = NULL;
1996         ImBuf *ibuf[3];
1997         Sequence *input[3];
1998         ImBuf *out = NULL;
1999
2000         ibuf[0] = ibuf[1] = ibuf[2] = NULL;
2001
2002         input[0] = seq->seq1; input[1] = seq->seq2; input[2] = seq->seq3;
2003
2004         if (!sh.execute && !(sh.execute_slice && sh.init_execution)) {
2005                 /* effect not supported in this version... */
2006                 out = IMB_allocImBuf(context.rectx, context.recty, 32, IB_rect);
2007                 return out;
2008         }
2009
2010         if (seq->flag & SEQ_USE_EFFECT_DEFAULT_FADE) {
2011                 sh.get_default_fac(seq, cfra, &fac, &facf);
2012                 
2013                 if ((context.scene->r.mode & R_FIELDS) == 0)
2014                         facf = fac;
2015         }
2016         else {
2017                 fcu = id_data_find_fcurve(&context.scene->id, seq, &RNA_Sequence, "effect_fader", 0, NULL);
2018                 if (fcu) {
2019                         fac = facf = evaluate_fcurve(fcu, cfra);
2020                         if (context.scene->r.mode & R_FIELDS) {
2021                                 facf = evaluate_fcurve(fcu, cfra + 0.5f);
2022                         }
2023                 }
2024                 else {
2025                         fac = facf = seq->effect_fader;
2026                 }
2027         }
2028
2029         early_out = sh.early_out(seq, fac, facf);
2030
2031         switch (early_out) {
2032                 case EARLY_NO_INPUT:
2033                         out = sh.execute(context, seq, cfra, fac, facf, NULL, NULL, NULL);
2034                         break;
2035                 case EARLY_DO_EFFECT:
2036                         for (i = 0; i < 3; i++) {
2037                                 if (input[i])
2038                                         ibuf[i] = seq_render_strip(context, input[i], cfra);
2039                         }
2040
2041                         if (ibuf[0] && ibuf[1]) {
2042                                 if (sh.multithreaded)
2043                                         out = seq_render_effect_execute_threaded(&sh, context, seq, cfra, fac, facf, ibuf[0], ibuf[1], ibuf[2]);
2044                                 else
2045                                         out = sh.execute(context, seq, cfra, fac, facf, ibuf[0], ibuf[1], ibuf[2]);
2046                         }
2047                         break;
2048                 case EARLY_USE_INPUT_1:
2049                         if (input[0]) {
2050                                 ibuf[0] = seq_render_strip(context, input[0], cfra);
2051                         }
2052                         if (ibuf[0]) {
2053                                 if (BKE_sequencer_input_have_to_preprocess(context, seq, cfra)) {
2054                                         out = IMB_dupImBuf(ibuf[0]);
2055                                 }
2056                                 else {
2057                                         out = ibuf[0];
2058                                         IMB_refImBuf(out);
2059                                 }
2060                         }
2061                         break;
2062                 case EARLY_USE_INPUT_2:
2063                         if (input[1]) {
2064                                 ibuf[1] = seq_render_strip(context, input[1], cfra);
2065                         }
2066                         if (ibuf[1]) {
2067                                 if (BKE_sequencer_input_have_to_preprocess(context, seq, cfra)) {
2068                                         out = IMB_dupImBuf(ibuf[1]);
2069                                 }
2070                                 else {
2071                                         out = ibuf[1];
2072                                         IMB_refImBuf(out);
2073                                 }
2074                         }
2075                         break;
2076         }
2077
2078         for (i = 0; i < 3; i++) {
2079                 IMB_freeImBuf(ibuf[i]);
2080         }
2081
2082         if (out == NULL) {
2083                 out = IMB_allocImBuf(context.rectx, context.recty, 32, IB_rect);
2084         }
2085
2086         return out;
2087 }
2088
2089 static ImBuf *seq_render_movieclip_strip(SeqRenderData context, Sequence *seq, float nr)
2090 {
2091         ImBuf *ibuf = NULL;
2092         MovieClipUser user;
2093         float tloc[2], tscale, tangle;
2094
2095         if (!seq->clip) {
2096                 return NULL;
2097         }
2098
2099         memset(&user, 0, sizeof(MovieClipUser));
2100         
2101         BKE_movieclip_user_set_frame(&user, nr + seq->anim_startofs);
2102
2103         user.render_size = MCLIP_PROXY_RENDER_SIZE_FULL;
2104
2105         switch (seq_rendersize_to_proxysize(context.preview_render_size)) {
2106                 case IMB_PROXY_NONE:
2107                         user.render_size = MCLIP_PROXY_RENDER_SIZE_FULL;
2108                         break;
2109                 case IMB_PROXY_100:
2110                         user.render_size = MCLIP_PROXY_RENDER_SIZE_100;
2111                         break;
2112                 case IMB_PROXY_75:
2113                         user.render_size = MCLIP_PROXY_RENDER_SIZE_75;
2114                         break;
2115                 case IMB_PROXY_50:
2116                         user.render_size = MCLIP_PROXY_RENDER_SIZE_50;
2117                         break;
2118                 case IMB_PROXY_25:
2119                         user.render_size = MCLIP_PROXY_RENDER_SIZE_25;
2120                         break;
2121         }
2122
2123         if (seq->clip_flag & SEQ_MOVIECLIP_RENDER_UNDISTORTED) {
2124                 user.render_flag = MCLIP_PROXY_RENDER_UNDISTORT;
2125         }
2126
2127         if (seq->clip_flag & SEQ_MOVIECLIP_RENDER_STABILIZED) {
2128                 ibuf = BKE_movieclip_get_stable_ibuf(seq->clip, &user, tloc, &tscale, &tangle, 0);
2129         }
2130         else {
2131                 ibuf = BKE_movieclip_get_ibuf_flag(seq->clip, &user, 0, MOVIECLIP_CACHE_SKIP);
2132         }
2133
2134         return ibuf;
2135 }
2136
2137
2138 static ImBuf *seq_render_mask(SeqRenderData context, Mask *mask, float nr, short make_float)
2139 {
2140         /* TODO - add option to rasterize to alpha imbuf? */
2141         ImBuf *ibuf = NULL;
2142         float *maskbuf;
2143         int i;
2144
2145         if (!mask) {
2146                 return NULL;
2147         }
2148         else {
2149                 Mask *mask_temp;
2150                 MaskRasterHandle *mr_handle;
2151
2152                 mask_temp = BKE_mask_copy_nolib(mask);
2153
2154                 BKE_mask_evaluate(mask_temp, mask->sfra + nr, TRUE);
2155
2156                 maskbuf = MEM_mallocN(sizeof(float) * context.rectx * context.recty, __func__);
2157
2158                 mr_handle = BKE_maskrasterize_handle_new();
2159
2160                 BKE_maskrasterize_handle_init(mr_handle, mask_temp, context.rectx, context.recty, TRUE, TRUE, TRUE);
2161
2162                 BKE_mask_free(mask_temp);
2163                 MEM_freeN(mask_temp);
2164
2165                 BKE_maskrasterize_buffer(mr_handle, context.rectx, context.recty, maskbuf);
2166
2167                 BKE_maskrasterize_handle_free(mr_handle);
2168         }
2169
2170
2171         if (make_float) {
2172                 /* pixels */
2173                 float *fp_src;
2174                 float *fp_dst;
2175
2176                 ibuf = IMB_allocImBuf(context.rectx, context.recty, 32, IB_rectfloat);
2177
2178                 fp_src = maskbuf;
2179                 fp_dst = ibuf->rect_float;
2180                 i = context.rectx * context.recty;
2181                 while (--i) {
2182                         fp_dst[0] = fp_dst[1] = fp_dst[2] = *fp_src;
2183                         fp_dst[3] = 1.0f;
2184
2185                         fp_src += 1;
2186                         fp_dst += 4;
2187                 }
2188         }
2189         else {
2190                 /* pixels */
2191                 float *fp_src;
2192                 unsigned char *ub_dst;
2193
2194                 ibuf = IMB_allocImBuf(context.rectx, context.recty, 32, IB_rect);
2195
2196                 fp_src = maskbuf;
2197                 ub_dst = (unsigned char *)ibuf->rect;
2198                 i = context.rectx * context.recty;
2199                 while (--i) {
2200                         ub_dst[0] = ub_dst[1] = ub_dst[2] = (unsigned char)(*fp_src * 255.0f); /* already clamped */
2201                         ub_dst[3] = 255;
2202
2203                         fp_src += 1;
2204                         ub_dst += 4;
2205                 }
2206         }
2207
2208         MEM_freeN(maskbuf);
2209
2210         return ibuf;
2211 }
2212
2213 static ImBuf *seq_render_mask_strip(SeqRenderData context, Sequence *seq, float nr)
2214 {
2215         short make_float = seq->flag & SEQ_MAKE_FLOAT;
2216
2217         return seq_render_mask(context, seq->mask, nr, make_float);
2218 }
2219
2220 static ImBuf *seq_render_scene_strip(SeqRenderData context, Sequence *seq, float nr)
2221 {
2222         ImBuf *ibuf = NULL;
2223         float frame;
2224         float oldcfra;
2225         Object *camera;
2226         ListBase oldmarkers;
2227         
2228         /* Old info:
2229          * Hack! This function can be called from do_render_seq(), in that case
2230          * the seq->scene can already have a Render initialized with same name,
2231          * so we have to use a default name. (compositor uses scene name to
2232          * find render).
2233          * However, when called from within the UI (image preview in sequencer)
2234          * we do want to use scene Render, that way the render result is defined
2235          * for display in render/imagewindow
2236          *
2237          * Hmm, don't see, why we can't do that all the time,
2238          * and since G.is_rendering is uhm, gone... (Peter)
2239          */
2240
2241         /* New info:
2242          * Using the same name for the renders works just fine as the do_render_seq()
2243          * render is not used while the scene strips are rendered.
2244          *
2245          * However rendering from UI (through sequencer_preview_area_draw) can crash in
2246          * very many cases since other renders (material preview, an actual render etc.)
2247          * can be started while this sequence preview render is running. The only proper
2248          * solution is to make the sequencer preview render a proper job, which can be
2249          * stopped when needed. This would also give a nice progress bar for the preview
2250          * space so that users know there's something happening.
2251          *
2252          * As a result the active scene now only uses OpenGL rendering for the sequencer
2253          * preview. This is far from nice, but is the only way to prevent crashes at this
2254          * time.
2255          *
2256          * -jahka
2257          */
2258
2259         int rendering = G.is_rendering;
2260         int doseq;
2261         int doseq_gl = G.is_rendering ? /*(scene->r.seq_flag & R_SEQ_GL_REND)*/ 0 : /*(scene->r.seq_flag & R_SEQ_GL_PREV)*/ 1;
2262         int have_seq = FALSE;
2263         Scene *scene;
2264
2265         /* don't refer to seq->scene above this point!, it can be NULL */
2266         if (seq->scene == NULL) {
2267                 return NULL;
2268         }
2269
2270         scene = seq->scene;
2271         frame = scene->r.sfra + nr + seq->anim_startofs;
2272
2273         have_seq = (scene->r.scemode & R_DOSEQ) && scene->ed && scene->ed->seqbase.first;
2274
2275         oldcfra = scene->r.cfra;
2276         scene->r.cfra = frame;
2277
2278         if (seq->scene_camera)  
2279                 camera = seq->scene_camera;
2280         else {  
2281                 BKE_scene_camera_switch_update(scene);
2282                 camera = scene->camera;
2283         }
2284
2285         if (have_seq == FALSE && camera == NULL) {
2286                 scene->r.cfra = oldcfra;
2287                 return NULL;
2288         }
2289
2290         /* prevent eternal loop */
2291         doseq = context.scene->r.scemode & R_DOSEQ;
2292         context.scene->r.scemode &= ~R_DOSEQ;
2293         
2294 #ifdef DURIAN_CAMERA_SWITCH
2295         /* stooping to new low's in hackyness :( */
2296         oldmarkers = scene->markers;
2297         scene->markers.first = scene->markers.last = NULL;
2298 #else
2299         (void)oldmarkers;
2300 #endif
2301         
2302         if (sequencer_view3d_cb && BLI_thread_is_main() && doseq_gl && (scene == context.scene || have_seq == 0) && camera) {
2303                 char err_out[256] = "unknown";
2304                 /* for old scened this can be uninitialized,
2305                  * should probably be added to do_versions at some point if the functionality stays */
2306                 if (context.scene->r.seq_prev_type == 0)
2307                         context.scene->r.seq_prev_type = 3 /* == OB_SOLID */;
2308
2309                 /* opengl offscreen render */
2310                 BKE_scene_update_for_newframe(context.bmain, scene, scene->lay);
2311                 ibuf = sequencer_view3d_cb(scene, camera, context.rectx, context.recty,
2312                                            IB_rect, context.scene->r.seq_prev_type, TRUE, err_out);
2313                 if (ibuf == NULL) {
2314                         fprintf(stderr, "seq_render_scene_strip failed to get opengl buffer: %s\n", err_out);
2315                 }
2316         }
2317         else {
2318                 Render *re = RE_GetRender(scene->id.name);
2319                 RenderResult rres;
2320
2321                 /* XXX: this if can be removed when sequence preview rendering uses the job system */
2322                 if (rendering || context.scene != scene) {
2323                         if (re == NULL)
2324                                 re = RE_NewRender(scene->id.name);
2325                         
2326                         RE_BlenderFrame(re, context.bmain, scene, NULL, camera, scene->lay, frame, FALSE);
2327
2328                         /* restore previous state after it was toggled on & off by RE_BlenderFrame */
2329                         G.is_rendering = rendering;
2330                 }
2331                 
2332                 RE_AcquireResultImage(re, &rres);
2333                 
2334                 if (rres.rectf) {
2335                         ibuf = IMB_allocImBuf(rres.rectx, rres.recty, 32, IB_rectfloat);
2336                         memcpy(ibuf->rect_float, rres.rectf, 4 * sizeof(float) * rres.rectx * rres.recty);
2337                         if (rres.rectz) {
2338                                 addzbuffloatImBuf(ibuf);
2339                                 memcpy(ibuf->zbuf_float, rres.rectz, sizeof(float) * rres.rectx * rres.recty);
2340                         }
2341
2342                         /* float buffers in the sequencer are not linear */
2343                         ibuf->profile = IB_PROFILE_LINEAR_RGB;
2344                         IMB_colormanagement_imbuf_to_sequencer_space(ibuf, FALSE);
2345                 }
2346                 else if (rres.rect32) {
2347                         ibuf = IMB_allocImBuf(rres.rectx, rres.recty, 32, IB_rect);
2348                         memcpy(ibuf->rect, rres.rect32, 4 * rres.rectx * rres.recty);
2349                 }
2350                 
2351                 RE_ReleaseResultImage(re);
2352                 
2353                 // BIF_end_render_callbacks();
2354         }
2355         
2356         /* restore */
2357         context.scene->r.scemode |= doseq;
2358         
2359         scene->r.cfra = oldcfra;
2360
2361         if (frame != oldcfra)
2362                 BKE_scene_update_for_newframe(context.bmain, scene, scene->lay);
2363         
2364 #ifdef DURIAN_CAMERA_SWITCH
2365         /* stooping to new low's in hackyness :( */
2366         scene->markers = oldmarkers;
2367 #endif
2368
2369         return ibuf;
2370 }
2371
2372 static ImBuf *do_render_strip_uncached(SeqRenderData context, Sequence *seq, float cfra)
2373 {
2374         ImBuf *ibuf = NULL;
2375         float nr = give_stripelem_index(seq, cfra);
2376         int type = (seq->type & SEQ_TYPE_EFFECT && seq->type != SEQ_TYPE_SPEED) ? SEQ_TYPE_EFFECT : seq->type;
2377         int use_preprocess = BKE_sequencer_input_have_to_preprocess(context, seq, cfra);
2378         char name[FILE_MAX];
2379
2380         switch (type) {
2381                 case SEQ_TYPE_META:
2382                 {
2383                         ImBuf *meta_ibuf = NULL;
2384
2385                         if (seq->seqbase.first)
2386                                 meta_ibuf = seq_render_strip_stack(context, &seq->seqbase, seq->start + nr, 0);
2387
2388                         if (meta_ibuf) {
2389                                 ibuf = meta_ibuf;
2390                                 if (ibuf && use_preprocess) {
2391                                         ImBuf *i = IMB_dupImBuf(ibuf);
2392
2393                                         IMB_freeImBuf(ibuf);
2394
2395                                         ibuf = i;
2396                                 }
2397                         }
2398
2399                         break;
2400                 }
2401
2402                 case SEQ_TYPE_SPEED:
2403                 {
2404                         ImBuf *child_ibuf = NULL;
2405
2406                         float f_cfra;
2407                         SpeedControlVars *s = (SpeedControlVars *)seq->effectdata;
2408
2409                         BKE_sequence_effect_speed_rebuild_map(context.scene, seq, 0);
2410
2411                         /* weeek! */
2412                         f_cfra = seq->start + s->frameMap[(int)nr];
2413
2414                         child_ibuf = seq_render_strip(context, seq->seq1, f_cfra);
2415
2416                         if (child_ibuf) {
2417                                 ibuf = child_ibuf;
2418                                 if (ibuf && use_preprocess) {
2419                                         ImBuf *i = IMB_dupImBuf(ibuf);
2420
2421                                         IMB_freeImBuf(ibuf);
2422
2423                                         ibuf = i;
2424                                 }
2425                         }
2426                         break;
2427                 }
2428
2429                 case SEQ_TYPE_EFFECT:
2430                 {
2431                         ibuf = seq_render_effect_strip_impl(context, seq, seq->start + nr);
2432                         break;
2433                 }
2434
2435                 case SEQ_TYPE_IMAGE:
2436                 {
2437                         StripElem *s_elem = BKE_sequencer_give_stripelem(seq, cfra);
2438
2439                         if (s_elem) {
2440                                 BLI_join_dirfile(name, sizeof(name), seq->strip->dir, s_elem->name);
2441                                 BLI_path_abs(name, G.main->name);
2442                         }
2443
2444                         if (s_elem && (ibuf = IMB_loadiffname(name, IB_rect))) {
2445                                 /* we don't need both (speed reasons)! */
2446                                 if (ibuf->rect_float && ibuf->rect)
2447                                         imb_freerectImBuf(ibuf);
2448
2449                                 /* all sequencer color is done in SRGB space, linear gives odd crossfades */
2450                                 if (ibuf->profile == IB_PROFILE_LINEAR_RGB)
2451                                         IMB_colormanagement_imbuf_to_sequencer_space(ibuf, FALSE);
2452
2453                                 copy_to_ibuf_still(context, seq, nr, ibuf);
2454
2455                                 s_elem->orig_width  = ibuf->x;
2456                                 s_elem->orig_height = ibuf->y;
2457                         }
2458                         break;
2459                 }
2460
2461                 case SEQ_TYPE_MOVIE:
2462                 {
2463                         seq_open_anim_file(seq);
2464
2465                         if (seq->anim) {
2466                                 IMB_anim_set_preseek(seq->anim, seq->anim_preseek);
2467
2468                                 ibuf = IMB_anim_absolute(seq->anim, nr + seq->anim_startofs,
2469                                                          seq->strip->proxy ? seq->strip->proxy->tc : IMB_TC_RECORD_RUN,
2470                                                          seq_rendersize_to_proxysize(context.preview_render_size));
2471
2472                                 /* we don't need both (speed reasons)! */
2473                                 if (ibuf && ibuf->rect_float && ibuf->rect)
2474                                         imb_freerectImBuf(ibuf);
2475                                 if (ibuf) {
2476                                         seq->strip->stripdata->orig_width = ibuf->x;
2477                                         seq->strip->stripdata->orig_height = ibuf->y;
2478                                 }
2479                         }
2480                         copy_to_ibuf_still(context, seq, nr, ibuf);
2481                         break;
2482                 }
2483
2484                 case SEQ_TYPE_SCENE:
2485                 {
2486                         /* scene can be NULL after deletions */
2487                         ibuf = seq_render_scene_strip(context, seq, nr);
2488
2489                         /* Scene strips update all animation, so we need to restore original state.*/
2490                         BKE_animsys_evaluate_all_animation(context.bmain, context.scene, cfra);
2491
2492                         copy_to_ibuf_still(context, seq, nr, ibuf);
2493                         break;
2494                 }
2495
2496                 case SEQ_TYPE_MOVIECLIP:
2497                 {
2498                         ibuf = seq_render_movieclip_strip(context, seq, nr);
2499
2500                         if (ibuf && use_preprocess) {
2501                                 ImBuf *i = IMB_dupImBuf(ibuf);
2502
2503                                 IMB_freeImBuf(ibuf);
2504
2505                                 ibuf = i;
2506                         }
2507
2508                         copy_to_ibuf_still(context, seq, nr, ibuf);
2509                         break;
2510                 }
2511
2512                 case SEQ_TYPE_MASK:
2513                 {
2514                         /* ibuf is alwats new */
2515                         ibuf = seq_render_mask_strip(context, seq, nr);
2516
2517                         copy_to_ibuf_still(context, seq, nr, ibuf);
2518                         break;
2519                 }
2520         }
2521
2522         return ibuf;
2523 }
2524
2525 static ImBuf *seq_render_strip(SeqRenderData context, Sequence *seq, float cfra)
2526 {
2527         ImBuf *ibuf = NULL;
2528         int use_preprocess = BKE_sequencer_input_have_to_preprocess(context, seq, cfra);
2529         int is_proxy_image = FALSE;
2530         float nr = give_stripelem_index(seq, cfra);
2531         /* all effects are handled similarly with the exception of speed effect */
2532         int type = (seq->type & SEQ_TYPE_EFFECT && seq->type != SEQ_TYPE_SPEED) ? SEQ_TYPE_EFFECT : seq->type;
2533         int is_preprocessed = !ELEM3(type, SEQ_TYPE_IMAGE, SEQ_TYPE_MOVIE, SEQ_TYPE_SCENE);
2534
2535         ibuf = BKE_sequencer_cache_get(context, seq, cfra, SEQ_STRIPELEM_IBUF);
2536
2537         /* currently, we cache preprocessed images in SEQ_STRIPELEM_IBUF,
2538          * but not(!) on SEQ_STRIPELEM_IBUF_ENDSTILL and ..._STARTSTILL */
2539         if (ibuf)
2540                 use_preprocess = FALSE;
2541
2542         if (ibuf == NULL)
2543                 ibuf = copy_from_ibuf_still(context, seq, nr);
2544
2545         if (ibuf == NULL) {
2546                 ibuf = BKE_sequencer_preprocessed_cache_get(context, seq, cfra, SEQ_STRIPELEM_IBUF);
2547
2548                 if (ibuf == NULL) {
2549                         /* MOVIECLIPs have their own proxy management */
2550                         if (ibuf == NULL && seq->type != SEQ_TYPE_MOVIECLIP) {
2551                                 ibuf = seq_proxy_fetch(context, seq, cfra);
2552                                 is_proxy_image = (ibuf != NULL);
2553                         }
2554
2555                         if (ibuf == NULL)
2556                                 ibuf = do_render_strip_uncached(context, seq, cfra);
2557
2558                         if (ibuf)
2559                                 BKE_sequencer_preprocessed_cache_put(context, seq, cfra, SEQ_STRIPELEM_IBUF, ibuf);
2560                 }
2561         }
2562
2563         if (ibuf == NULL)
2564                 ibuf = IMB_allocImBuf(context.rectx, context.recty, 32, IB_rect);
2565
2566         if (ibuf->x != context.rectx || ibuf->y != context.recty)
2567                 use_preprocess = TRUE;
2568
2569         if (use_preprocess)
2570                 ibuf = input_preprocess(context, seq, cfra, ibuf, is_proxy_image, is_preprocessed);
2571
2572         BKE_sequencer_cache_put(context, seq, cfra, SEQ_STRIPELEM_IBUF, ibuf);
2573
2574         return ibuf;
2575 }
2576
2577 /*********************** strip stack rendering functions *************************/
2578
2579 static int seq_must_swap_input_in_blend_mode(Sequence *seq)
2580 {
2581         int swap_input = FALSE;
2582
2583         /* bad hack, to fix crazy input ordering of 
2584          * those two effects */
2585
2586         if (ELEM3(seq->blend_mode, SEQ_TYPE_ALPHAOVER, SEQ_TYPE_ALPHAUNDER, SEQ_TYPE_OVERDROP)) {
2587                 swap_input = TRUE;
2588         }
2589         
2590         return swap_input;
2591 }
2592
2593 static int seq_get_early_out_for_blend_mode(Sequence *seq)
2594 {
2595         struct SeqEffectHandle sh = BKE_sequence_get_blend(seq);
2596         float facf = seq->blend_opacity / 100.0f;
2597         int early_out = sh.early_out(seq, facf, facf);
2598         
2599         if (ELEM(early_out, EARLY_DO_EFFECT, EARLY_NO_INPUT)) {
2600                 return early_out;
2601         }
2602
2603         if (seq_must_swap_input_in_blend_mode(seq)) {
2604                 if (early_out == EARLY_USE_INPUT_2) {
2605                         return EARLY_USE_INPUT_1;
2606                 }
2607                 else if (early_out == EARLY_USE_INPUT_1) {
2608                         return EARLY_USE_INPUT_2;
2609                 }
2610         }
2611         return early_out;
2612 }
2613
2614 static ImBuf *seq_render_strip_stack(SeqRenderData context, ListBase *seqbasep, float cfra, int chanshown)
2615 {
2616         Sequence *seq_arr[MAXSEQ + 1];
2617         int count;
2618         int i;
2619         ImBuf *out = NULL;
2620
2621         count = get_shown_sequences(seqbasep, cfra, chanshown, (Sequence **)&seq_arr);
2622
2623         if (count == 0) {
2624                 return NULL;
2625         }
2626
2627 #if 0 /* commentind since this breaks keyframing, since it resets the value on draw */
2628         if (scene->r.cfra != cfra) {
2629                 /* XXX for prefetch and overlay offset!..., very bad!!! */
2630                 AnimData *adt = BKE_animdata_from_id(&scene->id);
2631                 BKE_animsys_evaluate_animdata(scene, &scene->id, adt, cfra, ADT_RECALC_ANIM);
2632         }
2633 #endif
2634
2635         out = BKE_sequencer_cache_get(context, seq_arr[count - 1],  cfra, SEQ_STRIPELEM_IBUF_COMP);
2636
2637         if (out) {
2638                 return out;
2639         }
2640         
2641         if (count == 1) {
2642                 out = seq_render_strip(context, seq_arr[0], cfra);
2643                 out->colormanage_flags |= IMB_COLORMANAGE_NOLINEAR_FLOAT;
2644
2645                 BKE_sequencer_cache_put(context, seq_arr[0], cfra, SEQ_STRIPELEM_IBUF_COMP, out);
2646
2647                 return out;
2648         }
2649
2650         for (i = count - 1; i >= 0; i--) {
2651                 int early_out;
2652                 Sequence *seq = seq_arr[i];
2653
2654                 out = BKE_sequencer_cache_get(context, seq, cfra, SEQ_STRIPELEM_IBUF_COMP);
2655
2656                 if (out) {
2657                         break;
2658                 }
2659                 if (seq->blend_mode == SEQ_BLEND_REPLACE) {
2660                         out = seq_render_strip(context, seq, cfra);
2661                         break;
2662                 }
2663
2664                 early_out = seq_get_early_out_for_blend_mode(seq);
2665
2666                 switch (early_out) {
2667                         case EARLY_NO_INPUT:
2668                         case EARLY_USE_INPUT_2:
2669                                 out = seq_render_strip(context, seq, cfra);
2670                                 break;
2671                         case EARLY_USE_INPUT_1:
2672                                 if (i == 0) {
2673                                         out = IMB_allocImBuf(context.rectx, context.recty, 32, IB_rect);
2674                                 }
2675                                 break;
2676                         case EARLY_DO_EFFECT:
2677                                 if (i == 0) {
2678                                         out = seq_render_strip(context, seq, cfra);
2679                                 }
2680
2681                                 break;
2682                 }
2683                 if (out) {
2684                         break;
2685                 }
2686         }
2687
2688         BKE_sequencer_cache_put(context, seq_arr[i], cfra, SEQ_STRIPELEM_IBUF_COMP, out);
2689
2690         i++;
2691
2692         for (; i < count; i++) {
2693                 Sequence *seq = seq_arr[i];
2694
2695                 if (seq_get_early_out_for_blend_mode(seq) == EARLY_DO_EFFECT) {
2696                         struct SeqEffectHandle sh = BKE_sequence_get_blend(seq);
2697                         ImBuf *ibuf1 = out;
2698                         ImBuf *ibuf2 = seq_render_strip(context, seq, cfra);
2699
2700                         float facf = seq->blend_opacity / 100.0f;
2701                         int swap_input = seq_must_swap_input_in_blend_mode(seq);
2702
2703                         if (swap_input) {
2704                                 if (sh.multithreaded)
2705                                         out = seq_render_effect_execute_threaded(&sh, context, seq, cfra, facf, facf, ibuf2, ibuf1, NULL);
2706                                 else
2707                                         out = sh.execute(context, seq, cfra, facf, facf, ibuf2, ibuf1, NULL);
2708                         }
2709                         else {
2710                                 if (sh.multithreaded)
2711                                         out = seq_render_effect_execute_threaded(&sh, context, seq, cfra, facf, facf, ibuf1, ibuf2, NULL);
2712                                 else
2713                                         out = sh.execute(context, seq, cfra, facf, facf, ibuf1, ibuf2, NULL);
2714                         }
2715                 
2716                         IMB_freeImBuf(ibuf1);
2717                         IMB_freeImBuf(ibuf2);
2718                 }
2719
2720                 BKE_sequencer_cache_put(context, seq_arr[i], cfra, SEQ_STRIPELEM_IBUF_COMP, out);
2721         }
2722
2723         out->colormanage_flags |= IMB_COLORMANAGE_NOLINEAR_FLOAT;
2724
2725         return out;
2726 }
2727
2728 /*
2729  * returned ImBuf is refed!
2730  * you have to free after usage!
2731  */
2732
2733 ImBuf *BKE_sequencer_give_ibuf(SeqRenderData context, float cfra, int chanshown)
2734 {
2735         Editing *ed = BKE_sequencer_editing_get(context.scene, FALSE);
2736         int count;
2737         ListBase *seqbasep;
2738         
2739         if (ed == NULL) return NULL;
2740
2741         count = BLI_countlist(&ed->metastack);
2742         if ((chanshown < 0) && (count > 0)) {
2743                 count = MAX2(count + chanshown, 0);
2744                 seqbasep = ((MetaStack *)BLI_findlink(&ed->metastack, count))->oldbasep;
2745         }
2746         else {
2747                 seqbasep = ed->seqbasep;
2748         }
2749
2750         return seq_render_strip_stack(context, seqbasep, cfra, chanshown);
2751 }
2752
2753 ImBuf *BKE_sequencer_give_ibuf_seqbase(SeqRenderData context, float cfra, int chanshown, ListBase *seqbasep)
2754 {
2755         return seq_render_strip_stack(context, seqbasep, cfra, chanshown);
2756 }
2757
2758
2759 ImBuf *BKE_sequencer_give_ibuf_direct(SeqRenderData context, float cfra, Sequence *seq)
2760 {
2761         return seq_render_strip(context, seq, cfra);
2762 }
2763
2764 /* *********************** threading api ******************* */
2765
2766 static ListBase running_threads;
2767 static ListBase prefetch_wait;
2768 static ListBase prefetch_done;
2769
2770 static pthread_mutex_t queue_lock          = PTHREAD_MUTEX_INITIALIZER;
2771 static pthread_mutex_t wakeup_lock         = PTHREAD_MUTEX_INITIALIZER;
2772 static pthread_cond_t wakeup_cond          = PTHREAD_COND_INITIALIZER;
2773
2774 //static pthread_mutex_t prefetch_ready_lock = PTHREAD_MUTEX_INITIALIZER;
2775 //static pthread_cond_t  prefetch_ready_cond = PTHREAD_COND_INITIALIZER;
2776
2777 static pthread_mutex_t frame_done_lock     = PTHREAD_MUTEX_INITIALIZER;
2778 static pthread_cond_t frame_done_cond      = PTHREAD_COND_INITIALIZER;
2779
2780 static volatile int seq_thread_shutdown = TRUE; 
2781 static volatile int seq_last_given_monoton_cfra = 0;
2782 static int monoton_cfra = 0;
2783
2784 typedef struct PrefetchThread {
2785         struct PrefetchThread *next, *prev;
2786         
2787         Scene *scene;
2788         struct PrefetchQueueElem *current;
2789         pthread_t pthread;
2790         int running;
2791         
2792 } PrefetchThread;
2793
2794 typedef struct PrefetchQueueElem {
2795         struct PrefetchQueueElem *next, *prev;
2796         
2797         int rectx;
2798         int recty;
2799         float cfra;
2800         int chanshown;
2801         int preview_render_size;
2802
2803         int monoton_cfra;
2804
2805         ImBuf *ibuf;
2806 } PrefetchQueueElem;
2807
2808 void BKE_sequencer_give_ibuf_prefetch_request(SeqRenderData context, float cfra, int chanshown)
2809 {
2810         PrefetchQueueElem *e;
2811         if (seq_thread_shutdown) {
2812                 return;
2813         }
2814
2815         e = MEM_callocN(sizeof(PrefetchQueueElem), "prefetch_queue_elem");
2816         e->rectx = context.rectx;
2817         e->recty = context.recty;
2818         e->cfra = cfra;
2819         e->chanshown = chanshown;
2820         e->preview_render_size = context.preview_render_size;
2821         e->monoton_cfra = monoton_cfra++;
2822
2823         pthread_mutex_lock(&queue_lock);
2824         BLI_addtail(&prefetch_wait, e);
2825         pthread_mutex_unlock(&queue_lock);
2826         
2827         pthread_mutex_lock(&wakeup_lock);
2828         pthread_cond_signal(&wakeup_cond);
2829         pthread_mutex_unlock(&wakeup_lock);
2830 }
2831
2832 ImBuf *BKE_sequencer_give_ibuf_threaded(SeqRenderData context, float cfra, int chanshown)
2833 {
2834         PrefetchQueueElem *e = NULL;
2835         int found_something = FALSE;
2836
2837         if (seq_thread_shutdown) {
2838                 return BKE_sequencer_give_ibuf(context, cfra, chanshown);
2839         }
2840
2841         while (!e) {
2842                 int success = FALSE;
2843                 pthread_mutex_lock(&queue_lock);
2844
2845                 for (e = prefetch_done.first; e; e = e->next) {
2846                         if (cfra == e->cfra &&
2847                             chanshown == e->chanshown &&
2848                             context.rectx == e->rectx &&
2849                             context.recty == e->recty &&
2850                             context.preview_render_size == e->preview_render_size)
2851                         {
2852                                 success = TRUE;
2853                                 found_something = TRUE;
2854                                 break;
2855                         }
2856                 }
2857
2858                 if (!e) {
2859                         for (e = prefetch_wait.first; e; e = e->next) {
2860                                 if (cfra == e->cfra &&
2861                                     chanshown == e->chanshown &&
2862                                     context.rectx == e->rectx &&
2863                                     context.recty == e->recty &&
2864                                     context.preview_render_size == e->preview_render_size)
2865                                 {
2866                                         found_something = TRUE;
2867                                         break;
2868                                 }
2869                         }
2870                 }
2871
2872                 if (!e) {
2873                         PrefetchThread *tslot;
2874
2875                         for (tslot = running_threads.first;
2876                              tslot;
2877                              tslot = tslot->next)
2878                         {
2879                                 if (tslot->current &&
2880                                     cfra == tslot->current->cfra &&
2881                                     chanshown == tslot->current->chanshown &&
2882                                     context.rectx == tslot->current->rectx &&
2883                                     context.recty == tslot->current->recty &&
2884                                     context.preview_render_size == tslot->current->preview_render_size)
2885                                 {
2886                                         found_something = TRUE;
2887                                         break;
2888                                 }
2889                         }
2890                 }
2891
2892                 /* e->ibuf is unrefed by render thread on next round. */
2893
2894                 if (e) {
2895                         seq_last_given_monoton_cfra = e->monoton_cfra;
2896                 }
2897
2898                 pthread_mutex_unlock(&queue_lock);
2899
2900                 if (!success) {
2901                         e = NULL;
2902
2903                         if (!found_something) {
2904                                 fprintf(stderr, "SEQ-THREAD: Requested frame not in queue ???\n");
2905                                 break;
2906                         }
2907                         pthread_mutex_lock(&frame_done_lock);
2908                         pthread_cond_wait(&frame_done_cond, &frame_done_lock);
2909                         pthread_mutex_unlock(&frame_done_lock);
2910                 }
2911         }
2912         
2913         return e ? e->ibuf : NULL;
2914 }
2915
2916 /* Functions to free imbuf and anim data on changes */
2917
2918 static void free_anim_seq(Sequence *seq)
2919 {
2920         if (seq->anim) {
2921                 IMB_free_anim(seq->anim);
2922                 seq->anim = NULL;
2923         }
2924 }
2925
2926 /* check whether sequence cur depends on seq */
2927 int BKE_sequence_check_depend(Sequence *seq, Sequence *cur)
2928 {
2929         if (cur->seq1 == seq || cur->seq2 == seq || cur->seq3 == seq)
2930                 return TRUE;
2931
2932         /* sequences are not intersecting in time, assume no dependency exists between them */
2933         if (cur->enddisp < seq->startdisp || cur->startdisp > seq->enddisp)
2934                 return FALSE;
2935
2936         /* checking sequence is below reference one, not dependent on it */
2937         if (cur->machine < seq->machine)
2938                 return FALSE;
2939
2940         /* sequence is not blending with lower machines, no dependency here occurs
2941          * check for non-effects only since effect could use lower machines as input
2942          */
2943         if ((cur->type & SEQ_TYPE_EFFECT) == 0 &&
2944                     ((cur->blend_mode == SEQ_BLEND_REPLACE) ||
2945                  (cur->blend_mode == SEQ_TYPE_CROSS && cur->blend_opacity == 100.0f)))
2946         {
2947                 return FALSE;
2948         }
2949
2950         return TRUE;
2951 }
2952
2953 static void sequence_invalidate_cache(Scene *scene, Sequence *seq, int invalidate_preprocess)
2954 {
2955         Editing *ed = scene->ed;
2956         Sequence *cur;
2957
2958         /* invalidate cache for current sequence */
2959         BKE_sequencer_cache_cleanup_sequence(seq);
2960
2961         if (invalidate_preprocess)
2962                 BKE_sequencer_preprocessed_cache_cleanup_sequence(seq);
2963
2964         /* invalidate cache for all dependent sequences */
2965         SEQ_BEGIN (ed, cur)
2966         {
2967                 if (cur == seq)
2968                         continue;
2969
2970                 if (BKE_sequence_check_depend(seq, cur)) {
2971                         BKE_sequencer_cache_cleanup_sequence(cur);
2972                         BKE_sequencer_preprocessed_cache_cleanup_sequence(cur);
2973                 }
2974         }
2975         SEQ_END
2976 }
2977
2978 void BKE_sequence_invalidate_cache(Scene *scene, Sequence *seq)
2979 {
2980         sequence_invalidate_cache(scene, seq, TRUE);
2981 }
2982
2983 void BKE_sequence_invalidate_cache_for_modifier(Scene *scene, Sequence *seq)
2984 {
2985         sequence_invalidate_cache(scene, seq, FALSE);
2986 }
2987
2988 void BKE_sequencer_free_imbuf(Scene *scene, ListBase *seqbase, int for_render)
2989 {
2990         Sequence *seq;
2991
2992         BKE_sequencer_cache_cleanup();
2993
2994         for (seq = seqbase->first; seq; seq = seq->next) {
2995                 if (for_render && CFRA >= seq->startdisp && CFRA <= seq->enddisp) {
2996                         continue;
2997                 }
2998
2999                 if (seq->strip) {
3000                         if (seq->type == SEQ_TYPE_MOVIE) {
3001                                 free_anim_seq(seq);
3002                         }
3003                         if (seq->type == SEQ_TYPE_SPEED) {
3004                                 BKE_sequence_effect_speed_rebuild_map(scene, seq, 1);
3005                         }
3006                 }
3007                 if (seq->type == SEQ_TYPE_META) {
3008                         BKE_sequencer_free_imbuf(scene, &seq->seqbase, for_render);
3009                 }
3010                 if (seq->type == SEQ_TYPE_SCENE) {
3011                         /* FIXME: recurs downwards, 
3012                          * but do recurs protection somehow! */
3013                 }
3014         }
3015         
3016 }
3017
3018 static int update_changed_seq_recurs(Scene *scene, Sequence *seq, Sequence *changed_seq, int len_change, int ibuf_change)
3019 {
3020         Sequence *subseq;
3021         int free_imbuf = 0;
3022         
3023         /* recurs downwards to see if this seq depends on the changed seq */
3024         
3025         if (seq == NULL)
3026                 return 0;
3027         
3028         if (seq == changed_seq)
3029                 free_imbuf = 1;
3030         
3031         for (subseq = seq->seqbase.first; subseq; subseq = subseq->next)
3032                 if (update_changed_seq_recurs(scene, subseq, changed_seq, len_change, ibuf_change))
3033                         free_imbuf = TRUE;
3034         
3035         if (seq->seq1)
3036                 if (update_changed_seq_recurs(scene, seq->seq1, changed_seq, len_change, ibuf_change))
3037                         free_imbuf = TRUE;
3038         if (seq->seq2 && (seq->seq2 != seq->seq1))
3039                 if (update_changed_seq_recurs(scene, seq->seq2, changed_seq, len_change, ibuf_change))
3040                         free_imbuf = TRUE;
3041         if (seq->seq3 && (seq->seq3 != seq->seq1) && (seq->seq3 != seq->seq2))
3042                 if (update_changed_seq_recurs(scene, seq->seq3, changed_seq, len_change, ibuf_change))
3043                         free_imbuf = TRUE;
3044         
3045         if (free_imbuf) {
3046                 if (ibuf_change) {
3047                         if (seq->type == SEQ_TYPE_MOVIE)
3048                                 free_anim_seq(seq);
3049                         if (seq->type == SEQ_TYPE_SPEED) {
3050                                 BKE_sequence_effect_speed_rebuild_map(scene, seq, 1);
3051                         }
3052                 }
3053                 
3054                 if (len_change)
3055                         BKE_sequence_calc(scene, seq);
3056         }
3057         
3058         return free_imbuf;
3059 }
3060
3061 void BKE_sequencer_update_changed_seq_and_deps(Scene *scene, Sequence *changed_seq, int len_change, int ibuf_change)
3062 {
3063         Editing *ed = BKE_sequencer_editing_get(scene, FALSE);
3064         Sequence *seq;
3065         
3066         if (ed == NULL) return;
3067         
3068         for (seq = ed->seqbase.first; seq; seq = seq->next)
3069                 update_changed_seq_recurs(scene, seq, changed_seq, len_change, ibuf_change);
3070 }
3071
3072 /* seq funcs's for transforming internally
3073  * notice the difference between start/end and left/right.
3074  *
3075  * left and right are the bounds at which the sequence is rendered,
3076  * start and end are from the start and fixed length of the sequence.
3077  */
3078 static int seq_tx_get_start(Sequence *seq)
3079 {
3080         return seq->start;
3081 }
3082 static int seq_tx_get_end(Sequence *seq)
3083 {
3084         return seq->start + seq->len;
3085 }
3086
3087 int BKE_sequence_tx_get_final_left(Sequence *seq, int metaclip)
3088 {
3089         if (metaclip && seq->tmp) {
3090                 /* return the range clipped by the parents range */
3091                 return maxi(BKE_sequence_tx_get_final_left(seq, 0), BKE_sequence_tx_get_final_left((Sequence *)seq->tmp, TRUE));
3092         }
3093         else {
3094                 return (seq->start - seq->startstill) + seq->startofs;
3095         }
3096
3097 }
3098 int BKE_sequence_tx_get_final_right(Sequence *seq, int metaclip)
3099 {
3100         if (metaclip && seq->tmp) {
3101                 /* return the range clipped by the parents range */
3102                 return mini(BKE_sequence_tx_get_final_right(seq, 0), BKE_sequence_tx_get_final_right((Sequence *)seq->tmp, TRUE));
3103         }
3104         else {
3105                 return ((seq->start + seq->len) + seq->endstill) - seq->endofs;
3106         }
3107 }
3108
3109 void BKE_sequence_tx_set_final_left(Sequence *seq, int val)
3110 {
3111         if (val < (seq)->start) {
3112                 seq->startstill = abs(val - (seq)->start);
3113                 seq->startofs = 0;
3114         }
3115         else {
3116                 seq->startofs = abs(val - (seq)->start);
3117                 seq->startstill = 0;
3118         }
3119 }
3120
3121 void BKE_sequence_tx_set_final_right(Sequence *seq, int val)
3122 {
3123         if (val > (seq)->start + (seq)->len) {
3124                 seq->endstill = abs(val - (seq->start + (seq)->len));
3125                 seq->endofs = 0;
3126         }
3127         else {
3128                 seq->endofs = abs(val - ((seq)->start + (seq)->len));
3129                 seq->endstill = 0;
3130         }
3131 }
3132
3133 /* used so we can do a quick check for single image seq
3134  * since they work a bit differently to normal image seq's (during transform) */
3135 int BKE_sequence_single_check(Sequence *seq)
3136 {
3137         return ((seq->len == 1) &&
3138                 (seq->type == SEQ_TYPE_IMAGE ||
3139                  ((seq->type & SEQ_TYPE_EFFECT) &&
3140                   BKE_sequence_effect_get_num_inputs(seq->type) == 0)));
3141 }
3142
3143 /* check if the selected seq's reference unselected seq's */
3144 int BKE_sequence_base_isolated_sel_check(ListBase *seqbase)
3145 {
3146         Sequence *seq;
3147         /* is there more than 1 select */
3148         int ok = FALSE;
3149
3150         for (seq = seqbase->first; seq; seq = seq->next) {
3151                 if (seq->flag & SELECT) {
3152                         ok = TRUE;
3153                         break;
3154                 }
3155         }
3156
3157         if (ok == FALSE)
3158                 return FALSE;
3159
3160         /* test relationships */
3161         for (seq = seqbase->first; seq; seq = seq->next) {
3162                 if ((seq->type & SEQ_TYPE_EFFECT) == 0)
3163                         continue;
3164
3165                 if (seq->flag & SELECT) {
3166                         if ( (seq->seq1 && (seq->seq1->flag & SELECT) == 0) ||
3167                              (seq->seq2 && (seq->seq2->flag & SELECT) == 0) ||
3168                              (seq->seq3 && (seq->seq3->flag & SELECT) == 0) )
3169                         {
3170                                 return FALSE;
3171                         }
3172                 }
3173                 else {
3174                         if ( (seq->seq1 && (seq->seq1->flag & SELECT)) ||
3175                              (seq->seq2 && (seq->seq2->flag & SELECT)) ||
3176                              (seq->seq3 && (seq->seq3->flag & SELECT)) )
3177                         {
3178                                 return FALSE;
3179                         }
3180                 }
3181         }
3182
3183         return TRUE;
3184 }
3185
3186 /* use to impose limits when dragging/extending - so impossible situations don't happen
3187  * Cant use the SEQ_LEFTSEL and SEQ_LEFTSEL directly because the strip may be in a metastrip */
3188 void BKE_sequence_tx_handle_xlimits(Sequence *seq, int leftflag, int rightflag)
3189 {
3190         if (leftflag) {
3191                 if (BKE_sequence_tx_get_final_left(seq, 0) >= BKE_sequence_tx_get_final_right(seq, 0)) {
3192                         BKE_sequence_tx_set_final_left(seq, BKE_sequence_tx_get_final_right(seq, 0) - 1);
3193                 }
3194
3195                 if (BKE_sequence_single_check(seq) == 0) {
3196                         if (BKE_sequence_tx_get_final_left(seq, 0) >= seq_tx_get_end(seq)) {
3197                                 BKE_sequence_tx_set_final_left(seq, seq_tx_get_end(seq) - 1);
3198                         }
3199
3200                         /* dosnt work now - TODO */
3201 #if 0
3202                         if (seq_tx_get_start(seq) >= seq_tx_get_final_right(seq, 0)) {
3203                                 int ofs;
3204                                 ofs = seq_tx_get_start(seq) - seq_tx_get_final_right(seq, 0);
3205                                 seq->start -= ofs;
3206                                 seq_tx_set_final_left(seq, seq_tx_get_final_left(seq, 0) + ofs);
3207                         }
3208 #endif
3209                 }
3210         }
3211
3212         if (rightflag) {
3213                 if (BKE_sequence_tx_get_final_right(seq, 0) <= BKE_sequence_tx_get_final_left(seq, 0)) {
3214                         BKE_sequence_tx_set_final_right(seq, BKE_sequence_tx_get_final_left(seq, 0) + 1);
3215                 }
3216
3217                 if (BKE_sequence_single_check(seq) == 0) {
3218                         if (BKE_sequence_tx_get_final_right(seq, 0) <= seq_tx_get_start(seq)) {
3219                                 BKE_sequence_tx_set_final_right(seq, seq_tx_get_start(seq) + 1);
3220                         }
3221                 }
3222         }
3223
3224         /* sounds cannot be extended past their endpoints */
3225         if (seq->type == SEQ_TYPE_SOUND_RAM) {
3226                 seq->startstill = 0;
3227                 seq->endstill = 0;
3228         }
3229 }
3230
3231 void BKE_sequence_single_fix(Sequence *seq)
3232 {
3233         int left, start, offset;
3234         if (!BKE_sequence_single_check(seq))
3235                 return;
3236
3237         /* make sure the image is always at the start since there is only one,
3238          * adjusting its start should be ok */
3239         left = BKE_sequence_tx_get_final_left(seq, 0);
3240         start = seq->start;
3241         if (start != left) {
3242                 offset = left - start;
3243                 BKE_sequence_tx_set_final_left(seq, BKE_sequence_tx_get_final_left(seq, 0) - offset);
3244                 BKE_sequence_tx_set_final_right(seq, BKE_sequence_tx_get_final_right(seq, 0) - offset);
3245                 seq->start += offset;
3246         }
3247 }
3248
3249 int BKE_sequence_tx_test(Sequence *seq)
3250 {
3251         return (seq->type < SEQ_TYPE_EFFECT) || (BKE_sequence_effect_get_num_inputs(seq->type) == 0);
3252 }
3253
3254 static int seq_overlap(Sequence *seq1, Sequence *seq2)
3255 {
3256         return (seq1 != seq2 && seq1->machine == seq2->machine &&
3257                 ((seq1->enddisp <= seq2->startdisp) || (seq1->startdisp >= seq2->enddisp)) == 0);
3258 }
3259
3260 int BKE_sequence_test_overlap(ListBase *seqbasep, Sequence *test)
3261 {
3262         Sequence *seq;
3263
3264         seq = seqbasep->first;
3265         while (seq) {
3266                 if (seq_overlap(test, seq))
3267                         return 1;
3268
3269                 seq = seq->next;
3270         }
3271 &n