+ // Which effects have already been completed in this phase?
+ // We need to keep track of it, as an effect with multiple outputs
+ // could otherwise be calculate multiple times.
+ std::set<Node *> completed_effects;
+
+ // Effects in the current phase, as well as inputs (outputs from other phases
+ // that we depend on). Note that since we start iterating from the end,
+ // the effect list will be in the reverse order.
+ std::vector<Node *> this_phase_inputs;
+ std::vector<Node *> this_phase_effects;
+
+ // Effects that we have yet to calculate, but that we know should
+ // be in the current phase.
+ std::stack<Node *> effects_todo_this_phase;
+
+ // Effects that we have yet to calculate, but that come from other phases.
+ // We delay these until we have this phase done in its entirety,
+ // at which point we pick any of them and start a new phase from that.
+ std::stack<Node *> effects_todo_other_phases;
+
+ effects_todo_this_phase.push(output);
+
+ for ( ;; ) { // Termination condition within loop.
+ if (!effects_todo_this_phase.empty()) {
+ // OK, we have more to do this phase.
+ Node *node = effects_todo_this_phase.top();
+ effects_todo_this_phase.pop();
+
+ // This should currently only happen for effects that are phase outputs,
+ // and we throw those out separately below.
+ assert(completed_effects.count(node) == 0);
+
+ this_phase_effects.push_back(node);
+ completed_effects.insert(node);
+
+ // Find all the dependencies of this effect, and add them to the stack.
+ std::vector<Node *> deps = node->incoming_links;
+ assert(node->effect->num_inputs() == deps.size());
+ for (unsigned i = 0; i < deps.size(); ++i) {
+ bool start_new_phase = false;
+
+ // FIXME: If we sample directly from a texture, we won't need this.
+ if (node->effect->needs_texture_bounce()) {
+ start_new_phase = true;
+ }
+
+ if (deps[i]->outgoing_links.size() > 1 && deps[i]->effect->num_inputs() > 0) {
+ // More than one effect uses this as the input,
+ // and it is not a texture itself.
+ // The easiest thing to do (and probably also the safest
+ // performance-wise in most cases) is to bounce it to a texture
+ // and then let the next passes read from that.
+ start_new_phase = true;
+ }
+
+ if (deps[i]->effect->changes_output_size()) {
+ start_new_phase = true;
+ }
+
+ if (start_new_phase) {
+ effects_todo_other_phases.push(deps[i]);
+ this_phase_inputs.push_back(deps[i]);
+ } else {
+ effects_todo_this_phase.push(deps[i]);
+ }
+ }
+ continue;
+ }
+
+ // No more effects to do this phase. Take all the ones we have,
+ // and create a GLSL program for it.
+ if (!this_phase_effects.empty()) {
+ reverse(this_phase_effects.begin(), this_phase_effects.end());
+ phases.push_back(compile_glsl_program(this_phase_inputs, this_phase_effects));
+ this_phase_effects.back()->phase = phases.back();
+ this_phase_inputs.clear();
+ this_phase_effects.clear();
+ }
+ assert(this_phase_inputs.empty());
+ assert(this_phase_effects.empty());
+
+ // If we have no effects left, exit.
+ if (effects_todo_other_phases.empty()) {
+ break;
+ }
+
+ Node *node = effects_todo_other_phases.top();
+ effects_todo_other_phases.pop();
+
+ if (completed_effects.count(node) == 0) {
+ // Start a new phase, calculating from this effect.
+ effects_todo_this_phase.push(node);
+ }
+ }
+
+ // Finally, since the phases are found from the output but must be executed
+ // from the input(s), reverse them, too.
+ std::reverse(phases.begin(), phases.end());
+}
+
+void EffectChain::output_dot(const char *filename)
+{
+ FILE *fp = fopen(filename, "w");
+ if (fp == NULL) {
+ perror(filename);
+ exit(1);
+ }
+
+ fprintf(fp, "digraph G {\n");
+ for (unsigned i = 0; i < nodes.size(); ++i) {
+ fprintf(fp, " n%ld [label=\"%s\"];\n", (long)nodes[i], nodes[i]->effect->effect_type_id().c_str());
+ for (unsigned j = 0; j < nodes[i]->outgoing_links.size(); ++j) {
+ std::vector<std::string> labels;
+
+ if (nodes[i]->outgoing_links[j]->effect->needs_texture_bounce()) {
+ labels.push_back("needs_bounce");
+ }
+ if (nodes[i]->effect->changes_output_size()) {
+ labels.push_back("resize");
+ }
+
+ switch (nodes[i]->output_color_space) {
+ case COLORSPACE_INVALID:
+ labels.push_back("spc[invalid]");
+ break;
+ case COLORSPACE_REC_601_525:
+ labels.push_back("spc[rec601-525]");
+ break;
+ case COLORSPACE_REC_601_625:
+ labels.push_back("spc[rec601-625]");
+ break;
+ default:
+ break;
+ }
+
+ switch (nodes[i]->output_gamma_curve) {
+ case GAMMA_INVALID:
+ labels.push_back("gamma[invalid]");
+ break;
+ case GAMMA_sRGB:
+ labels.push_back("gamma[sRGB]");
+ break;
+ case GAMMA_REC_601: // and GAMMA_REC_709
+ labels.push_back("gamma[rec601/709]");
+ break;
+ default:
+ break;
+ }
+
+ if (labels.empty()) {
+ fprintf(fp, " n%ld -> n%ld;\n", (long)nodes[i], (long)nodes[i]->outgoing_links[j]);
+ } else {
+ std::string label = labels[0];
+ for (unsigned k = 1; k < labels.size(); ++k) {
+ label += ", " + labels[k];
+ }
+ fprintf(fp, " n%ld -> n%ld [label=\"%s\"];\n", (long)nodes[i], (long)nodes[i]->outgoing_links[j], label.c_str());
+ }
+ }
+ }
+ fprintf(fp, "}\n");
+
+ fclose(fp);
+}
+
+void EffectChain::find_output_size(Phase *phase)
+{
+ Node *output_node = phase->effects.back();
+
+ // If the last effect explicitly sets an output size,
+ // use that.
+ if (output_node->effect->changes_output_size()) {
+ output_node->effect->get_output_size(&phase->output_width, &phase->output_height);
+ return;
+ }
+
+ // If not, look at the input phases, if any. We select the largest one
+ // (really assuming they all have the same aspect currently), by pixel count.
+ if (!phase->inputs.empty()) {
+ unsigned best_width = 0, best_height = 0;
+ for (unsigned i = 0; i < phase->inputs.size(); ++i) {
+ Node *input = phase->inputs[i];
+ assert(input->phase->output_width != 0);
+ assert(input->phase->output_height != 0);
+ if (input->phase->output_width * input->phase->output_height > best_width * best_height) {
+ best_width = input->phase->output_width;
+ best_height = input->phase->output_height;
+ }
+ }
+ assert(best_width != 0);
+ assert(best_height != 0);
+ phase->output_width = best_width;
+ phase->output_height = best_height;
+ return;
+ }
+
+ // OK, no inputs. Just use the global width/height.
+ // TODO: We probably want to use the texture's size eventually.
+ phase->output_width = width;
+ phase->output_height = height;
+}
+
+void EffectChain::sort_nodes_topologically()
+{
+ std::set<Node *> visited_nodes;
+ std::vector<Node *> sorted_list;
+ for (unsigned i = 0; i < nodes.size(); ++i) {
+ if (nodes[i]->incoming_links.size() == 0) {
+ topological_sort_visit_node(nodes[i], &visited_nodes, &sorted_list);
+ }
+ }
+ reverse(sorted_list.begin(), sorted_list.end());
+ nodes = sorted_list;
+}
+
+void EffectChain::topological_sort_visit_node(Node *node, std::set<Node *> *visited_nodes, std::vector<Node *> *sorted_list)
+{
+ if (visited_nodes->count(node) != 0) {
+ return;
+ }
+ visited_nodes->insert(node);
+ for (unsigned i = 0; i < node->outgoing_links.size(); ++i) {
+ topological_sort_visit_node(node->outgoing_links[i], visited_nodes, sorted_list);
+ }
+ sorted_list->push_back(node);
+}
+
+// Propagate gamma and color space information as far as we can in the graph.
+// The rules are simple: Anything where all the inputs agree, get that as
+// output as well. Anything else keeps having *_INVALID.
+void EffectChain::propagate_gamma_and_color_space()
+{
+ // We depend on going through the nodes in order.
+ sort_nodes_topologically();
+
+ for (unsigned i = 0; i < nodes.size(); ++i) {
+ Node *node = nodes[i];
+ if (node->disabled) {
+ continue;
+ }
+ assert(node->incoming_links.size() == node->effect->num_inputs());
+ if (node->incoming_links.size() == 0) {
+ assert(node->output_color_space != COLORSPACE_INVALID);
+ assert(node->output_gamma_curve != GAMMA_INVALID);
+ continue;
+ }
+
+ ColorSpace color_space = node->incoming_links[0]->output_color_space;
+ GammaCurve gamma_curve = node->incoming_links[0]->output_gamma_curve;
+ for (unsigned j = 1; j < node->incoming_links.size(); ++j) {
+ if (node->incoming_links[j]->output_color_space != color_space) {
+ color_space = COLORSPACE_INVALID;
+ }
+ if (node->incoming_links[j]->output_gamma_curve != gamma_curve) {
+ gamma_curve = GAMMA_INVALID;
+ }