+ // If all effects have the same size, use that.
+ unsigned output_width = 0, output_height = 0;
+ bool all_inputs_same_size = true;
+
+ 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 (output_width == 0 && output_height == 0) {
+ output_width = input->phase->output_width;
+ output_height = input->phase->output_height;
+ } else if (output_width != input->phase->output_width ||
+ output_height != input->phase->output_height) {
+ all_inputs_same_size = false;
+ }
+ }
+ for (unsigned i = 0; i < phase->effects.size(); ++i) {
+ Effect *effect = phase->effects[i]->effect;
+ if (effect->num_inputs() != 0) {
+ continue;
+ }
+
+ Input *input = static_cast<Input *>(effect);
+ if (output_width == 0 && output_height == 0) {
+ output_width = input->get_width();
+ output_height = input->get_height();
+ } else if (output_width != input->get_width() ||
+ output_height != input->get_height()) {
+ all_inputs_same_size = false;
+ }
+ }
+
+ if (all_inputs_same_size) {
+ assert(output_width != 0);
+ assert(output_height != 0);
+ phase->output_width = output_width;
+ phase->output_height = output_height;
+ return;
+ }
+
+ // If not, fit all the inputs into the current aspect, and select the largest one.
+ output_width = 0;
+ output_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);
+ size_rectangle_to_fit(input->phase->output_width, input->phase->output_height, &output_width, &output_height);
+ }
+ for (unsigned i = 0; i < phase->effects.size(); ++i) {
+ Effect *effect = phase->effects[i]->effect;
+ if (effect->num_inputs() != 0) {
+ continue;
+ }
+
+ Input *input = static_cast<Input *>(effect);
+ size_rectangle_to_fit(input->get_width(), input->get_height(), &output_width, &output_height);
+ }
+ assert(output_width != 0);
+ assert(output_height != 0);
+ phase->output_width = output_width;
+ phase->output_height = output_height;
+}
+
+void EffectChain::sort_all_nodes_topologically()
+{
+ nodes = topological_sort(nodes);
+}
+
+std::vector<Node *> EffectChain::topological_sort(const std::vector<Node *> &nodes)
+{
+ std::set<Node *> nodes_left_to_visit(nodes.begin(), nodes.end());
+ std::vector<Node *> sorted_list;
+ for (unsigned i = 0; i < nodes.size(); ++i) {
+ topological_sort_visit_node(nodes[i], &nodes_left_to_visit, &sorted_list);
+ }
+ reverse(sorted_list.begin(), sorted_list.end());
+ return sorted_list;
+}
+
+void EffectChain::topological_sort_visit_node(Node *node, std::set<Node *> *nodes_left_to_visit, std::vector<Node *> *sorted_list)
+{
+ if (nodes_left_to_visit->count(node) == 0) {
+ return;
+ }
+ nodes_left_to_visit->erase(node);
+ for (unsigned i = 0; i < node->outgoing_links.size(); ++i) {
+ topological_sort_visit_node(node->outgoing_links[i], nodes_left_to_visit, sorted_list);
+ }
+ sorted_list->push_back(node);
+}
+
+void EffectChain::find_color_spaces_for_inputs()
+{
+ for (unsigned i = 0; i < nodes.size(); ++i) {
+ Node *node = nodes[i];
+ if (node->disabled) {
+ continue;
+ }
+ if (node->incoming_links.size() == 0) {
+ Input *input = static_cast<Input *>(node->effect);
+ node->output_color_space = input->get_color_space();
+ node->output_gamma_curve = input->get_gamma_curve();
+
+ Effect::AlphaHandling alpha_handling = input->alpha_handling();
+ switch (alpha_handling) {
+ case Effect::OUTPUT_BLANK_ALPHA:
+ node->output_alpha_type = ALPHA_BLANK;
+ break;
+ case Effect::INPUT_AND_OUTPUT_ALPHA_PREMULTIPLIED:
+ node->output_alpha_type = ALPHA_PREMULTIPLIED;
+ break;
+ case Effect::OUTPUT_ALPHA_POSTMULTIPLIED:
+ node->output_alpha_type = ALPHA_POSTMULTIPLIED;
+ break;
+ case Effect::DONT_CARE_ALPHA_TYPE:
+ default:
+ assert(false);
+ }
+
+ if (node->output_alpha_type == ALPHA_PREMULTIPLIED) {
+ assert(node->output_gamma_curve == GAMMA_LINEAR);
+ }
+ }
+ }
+}
+
+// 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_all_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;
+ }
+ }
+
+ // The conversion effects already have their outputs set correctly,
+ // so leave them alone.
+ if (node->effect->effect_type_id() != "ColorspaceConversionEffect") {
+ node->output_color_space = color_space;
+ }
+ if (node->effect->effect_type_id() != "GammaCompressionEffect" &&
+ node->effect->effect_type_id() != "GammaExpansionEffect") {
+ node->output_gamma_curve = gamma_curve;
+ }
+ }
+}
+
+// Propagate alpha information as far as we can in the graph.
+// Similar to propagate_gamma_and_color_space().
+void EffectChain::propagate_alpha()
+{
+ // We depend on going through the nodes in order.
+ sort_all_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_alpha_type != ALPHA_INVALID);
+ continue;
+ }
+
+ // The alpha multiplication/division effects are special cases.
+ if (node->effect->effect_type_id() == "AlphaMultiplicationEffect") {
+ assert(node->incoming_links.size() == 1);
+ assert(node->incoming_links[0]->output_alpha_type == ALPHA_POSTMULTIPLIED);
+ node->output_alpha_type = ALPHA_PREMULTIPLIED;
+ continue;
+ }
+ if (node->effect->effect_type_id() == "AlphaDivisionEffect") {
+ assert(node->incoming_links.size() == 1);
+ assert(node->incoming_links[0]->output_alpha_type == ALPHA_PREMULTIPLIED);
+ node->output_alpha_type = ALPHA_POSTMULTIPLIED;
+ continue;
+ }
+
+ // GammaCompressionEffect and GammaExpansionEffect are also a special case,
+ // because they are the only one that _need_ postmultiplied alpha.
+ if (node->effect->effect_type_id() == "GammaCompressionEffect" ||
+ node->effect->effect_type_id() == "GammaExpansionEffect") {
+ assert(node->incoming_links.size() == 1);
+ if (node->incoming_links[0]->output_alpha_type == ALPHA_BLANK) {
+ node->output_alpha_type = ALPHA_BLANK;
+ } else if (node->incoming_links[0]->output_alpha_type == ALPHA_POSTMULTIPLIED) {
+ node->output_alpha_type = ALPHA_POSTMULTIPLIED;
+ } else {
+ node->output_alpha_type = ALPHA_INVALID;
+ }
+ continue;
+ }
+
+ // Only inputs can have unconditional alpha output (OUTPUT_BLANK_ALPHA
+ // or OUTPUT_ALPHA_POSTMULTIPLIED), and they have already been
+ // taken care of above. Rationale: Even if you could imagine
+ // e.g. an effect that took in an image and set alpha=1.0
+ // unconditionally, it wouldn't make any sense to have it as
+ // e.g. OUTPUT_BLANK_ALPHA, since it wouldn't know whether it
+ // got its input pre- or postmultiplied, so it wouldn't know
+ // whether to divide away the old alpha or not.
+ Effect::AlphaHandling alpha_handling = node->effect->alpha_handling();
+ assert(alpha_handling == Effect::INPUT_AND_OUTPUT_ALPHA_PREMULTIPLIED ||
+ alpha_handling == Effect::DONT_CARE_ALPHA_TYPE);
+
+ // If the node has multiple inputs, check that they are all valid and
+ // the same.
+ bool any_invalid = false;
+ bool any_premultiplied = false;
+ bool any_postmultiplied = false;
+
+ for (unsigned j = 0; j < node->incoming_links.size(); ++j) {
+ switch (node->incoming_links[j]->output_alpha_type) {
+ case ALPHA_INVALID:
+ any_invalid = true;
+ break;
+ case ALPHA_BLANK:
+ // Blank is good as both pre- and postmultiplied alpha,
+ // so just ignore it.
+ break;
+ case ALPHA_PREMULTIPLIED:
+ any_premultiplied = true;
+ break;
+ case ALPHA_POSTMULTIPLIED:
+ any_postmultiplied = true;
+ break;
+ default:
+ assert(false);
+ }
+ }
+
+ if (any_invalid) {
+ node->output_alpha_type = ALPHA_INVALID;
+ continue;
+ }
+
+ // Inputs must be of the same type.
+ if (any_premultiplied && any_postmultiplied) {
+ node->output_alpha_type = ALPHA_INVALID;
+ continue;
+ }
+
+ if (alpha_handling == Effect::INPUT_AND_OUTPUT_ALPHA_PREMULTIPLIED) {
+ // If the effect has asked for premultiplied alpha, check that it has got it.
+ if (any_postmultiplied) {
+ node->output_alpha_type = ALPHA_INVALID;
+ } else {
+ // In some rare cases, it might be advantageous to say
+ // that blank input alpha yields blank output alpha.
+ // However, this would cause a more complex Effect interface
+ // an effect would need to guarantee that it doesn't mess with
+ // blank alpha), so this is the simplest.
+ node->output_alpha_type = ALPHA_PREMULTIPLIED;
+ }
+ } else {
+ // OK, all inputs are the same, and this effect is not going
+ // to change it.
+ assert(alpha_handling == Effect::DONT_CARE_ALPHA_TYPE);
+ if (any_premultiplied) {
+ node->output_alpha_type = ALPHA_PREMULTIPLIED;
+ } else if (any_postmultiplied) {
+ node->output_alpha_type = ALPHA_POSTMULTIPLIED;
+ } else {
+ node->output_alpha_type = ALPHA_BLANK;
+ }
+ }
+ }
+}
+
+bool EffectChain::node_needs_colorspace_fix(Node *node)
+{
+ if (node->disabled) {
+ return false;
+ }
+ if (node->effect->num_inputs() == 0) {
+ return false;
+ }
+
+ // propagate_gamma_and_color_space() has already set our output
+ // to COLORSPACE_INVALID if the inputs differ, so we can rely on that.
+ if (node->output_color_space == COLORSPACE_INVALID) {
+ return true;
+ }
+ return (node->effect->needs_srgb_primaries() && node->output_color_space != COLORSPACE_sRGB);
+}
+
+// Fix up color spaces so that there are no COLORSPACE_INVALID nodes left in
+// the graph. Our strategy is not always optimal, but quite simple:
+// Find an effect that's as early as possible where the inputs are of
+// unacceptable colorspaces (that is, either different, or, if the effect only
+// wants sRGB, not sRGB.) Add appropriate conversions on all its inputs,
+// propagate the information anew, and repeat until there are no more such
+// effects.
+void EffectChain::fix_internal_color_spaces()
+{
+ unsigned colorspace_propagation_pass = 0;
+ bool found_any;
+ do {
+ found_any = false;
+ for (unsigned i = 0; i < nodes.size(); ++i) {
+ Node *node = nodes[i];
+ if (!node_needs_colorspace_fix(node)) {
+ continue;