// Copyright 2013 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#extension GL_KHR_shader_subgroup_arithmetic : enable

layout(local_size_x = 512, local_size_y = 1) in;
layout(std430) buffer;

#include <impeller/path.glsl>

layout(binding = 0) buffer Quads {
  uint count;
  QuadData data[];
}
quads;

layout(binding = 1) buffer Polyline {
  uint count;
  vec2 data[];
}
polyline;

uniform Config {
  float tolerance;
}
config;

shared uint point_counts[512];
shared uint count_sums[512];

uint ComputePosition(uint index) {
  if (index < gl_SubgroupSize) {
    return count_sums[index];
  }
  int position = -1;
  uint count_sum = count_sums[index];
  do {
    position += int(gl_SubgroupSize);
    count_sum += count_sums[position];
  } while (position < index);
  return count_sum;
}

void main() {
  uint ident = gl_GlobalInvocationID.x;
  QuadData quad;
  QuadDecomposition decomposition;
  if (ident < quads.count) {
    quad = quads.data[ident];
    decomposition = DecomposeQuad(quad, config.tolerance);
    point_counts[ident] = uint(decomposition.line_count);
  }

  barrier();

  if (decomposition.line_count == 0) {
    return;
  }
  count_sums[ident] = subgroupInclusiveAdd(point_counts[ident]);

  polyline.count = ComputePosition(quads.count - 1) + 1;
  polyline.data[0] = quads.data[0].p1;

  // In theory this could be unrolled into a separate shader, but in practice
  // line_count usually pretty low and currently lack benchmark data to show
  // how much it would even help.
  uint position = ComputePosition(ident);
  uint offset = position - uint(decomposition.line_count);
  for (uint i = 1; i < decomposition.line_count; i += 1) {
    polyline.data[offset + i] = GenerateLineFromQuad(quad, i, decomposition);
  }
  polyline.data[position] = quad.p2;
}