// SPDX-License-Identifier: Apache-2.0 OR MIT OR Unlicense

// The element processing stage, first in the pipeline.
//
// This stage is primarily about applying transforms and computing bounding
// boxes. It is organized as a scan over the input elements, producing
// annotated output elements.

#version 450
#extension GL_GOOGLE_include_directive : enable

#include "mem.h"
#include "setup.h"

#define N_ROWS 4
#define WG_SIZE 32
#define LG_WG_SIZE 5
#define PARTITION_SIZE (WG_SIZE * N_ROWS)

layout(local_size_x = WG_SIZE, local_size_y = 1) in;

layout(set = 0, binding = 1) readonly buffer ConfigBuf {
    Config conf;
};

layout(set = 0, binding = 2) readonly buffer SceneBuf {
    uint[] scene;
};

// It would be better to use the Vulkan memory model than
// "volatile" but shooting for compatibility here rather
// than doing things right.
layout(set = 0, binding = 3) volatile buffer StateBuf {
    uint part_counter;
    uint[] state;
};

#include "scene.h"
#include "state.h"
#include "annotated.h"
#include "pathseg.h"
#include "tile.h"

#define StateBuf_stride (4 + 2 * State_size)

StateRef state_aggregate_ref(uint partition_ix) {
    return StateRef(4 + partition_ix * StateBuf_stride);
}

StateRef state_prefix_ref(uint partition_ix) {
    return StateRef(4 + partition_ix * StateBuf_stride + State_size);
}

uint state_flag_index(uint partition_ix) {
    return partition_ix * (StateBuf_stride / 4);
}

// These correspond to X, A, P respectively in the prefix sum paper.
#define FLAG_NOT_READY 0
#define FLAG_AGGREGATE_READY 1
#define FLAG_PREFIX_READY 2

#define FLAG_SET_LINEWIDTH 1
#define FLAG_SET_BBOX 2
#define FLAG_RESET_BBOX 4
#define FLAG_SET_FILL_MODE 8
// Fill modes take up the next bit. Non-zero fill is 0, stroke is 1.
#define LG_FILL_MODE 4
#define FILL_MODE_BITS 1
#define FILL_MODE_MASK (FILL_MODE_BITS << LG_FILL_MODE)

// This is almost like a monoid (the interaction between transformation and
// bounding boxes is approximate)
State combine_state(State a, State b) {
    State c;
    c.bbox.x = min(a.mat.x * b.bbox.x, a.mat.x * b.bbox.z) + min(a.mat.z * b.bbox.y, a.mat.z * b.bbox.w) + a.translate.x;
    c.bbox.y = min(a.mat.y * b.bbox.x, a.mat.y * b.bbox.z) + min(a.mat.w * b.bbox.y, a.mat.w * b.bbox.w) + a.translate.y;
    c.bbox.z = max(a.mat.x * b.bbox.x, a.mat.x * b.bbox.z) + max(a.mat.z * b.bbox.y, a.mat.z * b.bbox.w) + a.translate.x;
    c.bbox.w = max(a.mat.y * b.bbox.x, a.mat.y * b.bbox.z) + max(a.mat.w * b.bbox.y, a.mat.w * b.bbox.w) + a.translate.y;
    if ((a.flags & FLAG_RESET_BBOX) == 0 && b.bbox.z <= b.bbox.x && b.bbox.w <= b.bbox.y) {
        c.bbox = a.bbox;
    } else if ((a.flags & FLAG_RESET_BBOX) == 0 && (b.flags & FLAG_SET_BBOX) == 0 &&
        (a.bbox.z > a.bbox.x || a.bbox.w > a.bbox.y))
    {
        c.bbox.xy = min(a.bbox.xy, c.bbox.xy);
        c.bbox.zw = max(a.bbox.zw, c.bbox.zw);
    }
    // It would be more concise to cast to matrix types; ah well.
    c.mat.x = a.mat.x * b.mat.x + a.mat.z * b.mat.y;
    c.mat.y = a.mat.y * b.mat.x + a.mat.w * b.mat.y;
    c.mat.z = a.mat.x * b.mat.z + a.mat.z * b.mat.w;
    c.mat.w = a.mat.y * b.mat.z + a.mat.w * b.mat.w;
    c.translate.x = a.mat.x * b.translate.x + a.mat.z * b.translate.y + a.translate.x;
    c.translate.y = a.mat.y * b.translate.x + a.mat.w * b.translate.y + a.translate.y;
    c.linewidth = (b.flags & FLAG_SET_LINEWIDTH) == 0 ? a.linewidth : b.linewidth;
    c.flags = (a.flags & (FLAG_SET_LINEWIDTH | FLAG_SET_BBOX | FLAG_SET_FILL_MODE)) | b.flags;
    c.flags |= (a.flags & FLAG_RESET_BBOX) >> 1;
    uint fill_mode = (b.flags & FLAG_SET_FILL_MODE) == 0 ? a.flags : b.flags;
    fill_mode &= FILL_MODE_MASK;
    c.flags = (c.flags & ~FILL_MODE_MASK) | fill_mode;
    c.path_count = a.path_count + b.path_count;
    c.pathseg_count = a.pathseg_count + b.pathseg_count;
    c.trans_count = a.trans_count + b.trans_count;
    return c;
}

State map_element(ElementRef ref) {
    // TODO: it would *probably* be more efficient to make the memory read patterns less
    // divergent, though it would be more wasted memory.
    uint tag = Element_tag(ref).tag;
    State c;
    c.bbox = vec4(0.0, 0.0, 0.0, 0.0);
    c.mat = vec4(1.0, 0.0, 0.0, 1.0);
    c.translate = vec2(0.0, 0.0);
    c.linewidth = 1.0; // TODO should be 0.0
    c.flags = 0;
    c.path_count = 0;
    c.pathseg_count = 0;
    c.trans_count = 0;
    switch (tag) {
    case Element_Line:
        LineSeg line = Element_Line_read(ref);
        c.bbox.xy = min(line.p0, line.p1);
        c.bbox.zw = max(line.p0, line.p1);
        c.pathseg_count = 1;
        break;
    case Element_Quad:
        QuadSeg quad = Element_Quad_read(ref);
        c.bbox.xy = min(min(quad.p0, quad.p1), quad.p2);
        c.bbox.zw = max(max(quad.p0, quad.p1), quad.p2);
        c.pathseg_count = 1;
        break;
    case Element_Cubic:
        CubicSeg cubic = Element_Cubic_read(ref);
        c.bbox.xy = min(min(cubic.p0, cubic.p1), min(cubic.p2, cubic.p3));
        c.bbox.zw = max(max(cubic.p0, cubic.p1), max(cubic.p2, cubic.p3));
        c.pathseg_count = 1;
        break;
    case Element_FillColor:
    case Element_FillLinGradient:
    case Element_FillImage:
    case Element_BeginClip:
        c.flags = FLAG_RESET_BBOX;
        c.path_count = 1;
        break;
    case Element_EndClip:
        c.path_count = 1;
        break;
    case Element_SetLineWidth:
        SetLineWidth lw = Element_SetLineWidth_read(ref);
        c.linewidth = lw.width;
        c.flags = FLAG_SET_LINEWIDTH;
        break;
    case Element_Transform:
        Transform t = Element_Transform_read(ref);
        c.mat = t.mat;
        c.translate = t.translate;
        c.trans_count = 1;
        break;
    case Element_SetFillMode:
        SetFillMode fm = Element_SetFillMode_read(ref);
        c.flags = FLAG_SET_FILL_MODE | (fm.fill_mode << LG_FILL_MODE);
        break;
    }
    return c;
}

// Get the bounding box of a circle transformed by the matrix into an ellipse.
vec2 get_linewidth(State st) {
    // See https://www.iquilezles.org/www/articles/ellipses/ellipses.htm
    return 0.5 * st.linewidth * vec2(length(st.mat.xz), length(st.mat.yw));
}

shared State sh_state[WG_SIZE];

shared uint sh_part_ix;
shared State sh_prefix;
shared uint sh_flag;

void main() {
    State th_state[N_ROWS];
    // Determine partition to process by atomic counter (described in Section
    // 4.4 of prefix sum paper).
    if (gl_LocalInvocationID.x == 0) {
        sh_part_ix = atomicAdd(part_counter, 1);
    }
    barrier();
    uint part_ix = sh_part_ix;

    uint ix = part_ix * PARTITION_SIZE + gl_LocalInvocationID.x * N_ROWS;
    ElementRef ref = ElementRef(ix * Element_size);

    th_state[0] = map_element(ref);
    for (uint i = 1; i < N_ROWS; i++) {
        // discussion question: would it be faster to load using more coherent patterns
        // into thread memory? This is kinda strided.
        th_state[i] = combine_state(th_state[i - 1], map_element(Element_index(ref, i)));
    }
    State agg = th_state[N_ROWS - 1];
    sh_state[gl_LocalInvocationID.x] = agg;
    for (uint i = 0; i < LG_WG_SIZE; i++) {
        barrier();
        if (gl_LocalInvocationID.x >= (1 << i)) {
            State other = sh_state[gl_LocalInvocationID.x - (1 << i)];
            agg = combine_state(other, agg);
        }
        barrier();
        sh_state[gl_LocalInvocationID.x] = agg;
    }

    State exclusive;
    exclusive.bbox = vec4(0.0, 0.0, 0.0, 0.0);
    exclusive.mat = vec4(1.0, 0.0, 0.0, 1.0);
    exclusive.translate = vec2(0.0, 0.0);
    exclusive.linewidth = 1.0; //TODO should be 0.0
    exclusive.flags = 0;
    exclusive.path_count = 0;
    exclusive.pathseg_count = 0;
    exclusive.trans_count = 0;

    // Publish aggregate for this partition
    if (gl_LocalInvocationID.x == WG_SIZE - 1) {
        State_write(state_aggregate_ref(part_ix), agg);
        if (part_ix == 0) {
            State_write(state_prefix_ref(part_ix), agg);
        }
    }
    // Write flag with release semantics; this is done portably with a barrier.
    memoryBarrierBuffer();
    if (gl_LocalInvocationID.x == WG_SIZE - 1) {
        uint flag = FLAG_AGGREGATE_READY;
        if (part_ix == 0) {
            flag = FLAG_PREFIX_READY;
        }
        state[state_flag_index(part_ix)] = flag;
    }
    if (part_ix != 0) {
        // step 4 of paper: decoupled lookback
        uint look_back_ix = part_ix - 1;

        State their_agg;
        uint their_ix = 0;
        while (true) {
            // Read flag with acquire semantics.
            if (gl_LocalInvocationID.x == WG_SIZE - 1) {
                sh_flag = state[state_flag_index(look_back_ix)];
            }
            // The flag load is done only in the last thread. However, because the
            // translation of memoryBarrierBuffer to Metal requires uniform control
            // flow, we broadcast it to all threads.
            barrier();
            memoryBarrierBuffer();
            uint flag = sh_flag;

            if (flag == FLAG_PREFIX_READY) {
                if (gl_LocalInvocationID.x == WG_SIZE - 1) {
                    State their_prefix = State_read(state_prefix_ref(look_back_ix));
                    exclusive = combine_state(their_prefix, exclusive);
                }
                break;
            } else if (flag == FLAG_AGGREGATE_READY) {
                if (gl_LocalInvocationID.x == WG_SIZE - 1) {
                    their_agg = State_read(state_aggregate_ref(look_back_ix));
                    exclusive = combine_state(their_agg, exclusive);
                }
                look_back_ix--;
                their_ix = 0;
                continue;
            }
            // else spin

            if (gl_LocalInvocationID.x == WG_SIZE - 1) {
                // Unfortunately there's no guarantee of forward progress of other
                // workgroups, so compute a bit of the aggregate before trying again.
                // In the worst case, spinning stops when the aggregate is complete.
                ElementRef ref = ElementRef((look_back_ix * PARTITION_SIZE + their_ix) * Element_size);
                State s = map_element(ref);
                if (their_ix == 0) {
                    their_agg = s;
                } else {
                    their_agg = combine_state(their_agg, s);
                }
                their_ix++;
                if (their_ix == PARTITION_SIZE) {
                    exclusive = combine_state(their_agg, exclusive);
                    if (look_back_ix == 0) {
                        sh_flag = FLAG_PREFIX_READY;
                    } else {
                        look_back_ix--;
                        their_ix = 0;
                    }
                }
            }
            barrier();
            flag = sh_flag;
            if (flag == FLAG_PREFIX_READY) {
                break;
            }
        }
        // step 5 of paper: compute inclusive prefix
        if (gl_LocalInvocationID.x == WG_SIZE - 1) {
            State inclusive_prefix = combine_state(exclusive, agg);
            sh_prefix = exclusive;
            State_write(state_prefix_ref(part_ix), inclusive_prefix);
        }
        memoryBarrierBuffer();
        if (gl_LocalInvocationID.x == WG_SIZE - 1) {
            state[state_flag_index(part_ix)] = FLAG_PREFIX_READY;
        }
    }
    barrier();
    if (part_ix != 0) {
        exclusive = sh_prefix;
    }

    State row = exclusive;
    if (gl_LocalInvocationID.x > 0) {
        State other = sh_state[gl_LocalInvocationID.x - 1];
        row = combine_state(row, other);
    }
    for (uint i = 0; i < N_ROWS; i++) {
        State st = combine_state(row, th_state[i]);

        // Here we read again from the original scene. There may be
        // gains to be had from stashing in shared memory or possibly
        // registers (though register pressure is an issue).
        ElementRef this_ref = Element_index(ref, i);
        ElementTag tag = Element_tag(this_ref);
        uint fill_mode = fill_mode_from_flags(st.flags >> LG_FILL_MODE);
        bool is_stroke = fill_mode == MODE_STROKE;
        switch (tag.tag) {
        case Element_Line:
            LineSeg line = Element_Line_read(this_ref);
            PathCubic path_cubic;
            path_cubic.p0 = line.p0;
            path_cubic.p1 = mix(line.p0, line.p1, 1.0 / 3.0);
            path_cubic.p2 = mix(line.p1, line.p0, 1.0 / 3.0);
            path_cubic.p3 = line.p1;
            path_cubic.path_ix = st.path_count;
            path_cubic.trans_ix = st.trans_count;
            if (is_stroke) {
                path_cubic.stroke = get_linewidth(st);
            } else {
                path_cubic.stroke = vec2(0.0);
            }
            PathSegRef path_out_ref = PathSegRef(conf.pathseg_alloc.offset + (st.pathseg_count - 1) * PathSeg_size);
            PathSeg_Cubic_write(conf.pathseg_alloc, path_out_ref, fill_mode, path_cubic);
            break;
        case Element_Quad:
            QuadSeg quad = Element_Quad_read(this_ref);
            path_cubic.p0 = quad.p0;
            path_cubic.p1 = mix(quad.p1, quad.p0, 1.0 / 3.0);
            path_cubic.p2 = mix(quad.p1, quad.p2, 1.0 / 3.0);
            path_cubic.p3 = quad.p2;
            path_cubic.path_ix = st.path_count;
            path_cubic.trans_ix = st.trans_count;
            if (is_stroke) {
                path_cubic.stroke = get_linewidth(st);
            } else {
                path_cubic.stroke = vec2(0.0);
            }
            path_out_ref = PathSegRef(conf.pathseg_alloc.offset + (st.pathseg_count - 1) * PathSeg_size);
            PathSeg_Cubic_write(conf.pathseg_alloc, path_out_ref, fill_mode, path_cubic);
            break;
        case Element_Cubic:
            CubicSeg cubic = Element_Cubic_read(this_ref);
            path_cubic.p0 = cubic.p0;
            path_cubic.p1 = cubic.p1;
            path_cubic.p2 = cubic.p2;
            path_cubic.p3 = cubic.p3;
            path_cubic.path_ix = st.path_count;
            path_cubic.trans_ix = st.trans_count;
            if (is_stroke) {
                path_cubic.stroke = get_linewidth(st);
            } else {
                path_cubic.stroke = vec2(0.0);
            }
            path_out_ref = PathSegRef(conf.pathseg_alloc.offset + (st.pathseg_count - 1) * PathSeg_size);
            PathSeg_Cubic_write(conf.pathseg_alloc, path_out_ref, fill_mode, path_cubic);
            break;
        case Element_FillColor:
            FillColor fill = Element_FillColor_read(this_ref);
            AnnoColor anno_fill;
            anno_fill.rgba_color = fill.rgba_color;
            if (is_stroke) {
                vec2 lw = get_linewidth(st);
                anno_fill.bbox = st.bbox + vec4(-lw, lw);
                anno_fill.linewidth = st.linewidth * sqrt(abs(st.mat.x * st.mat.w - st.mat.y * st.mat.z));
            } else {
                anno_fill.bbox = st.bbox;
                anno_fill.linewidth = 0.0;
            }
            AnnotatedRef out_ref = AnnotatedRef(conf.anno_alloc.offset + (st.path_count - 1) * Annotated_size);
            Annotated_Color_write(conf.anno_alloc, out_ref, fill_mode, anno_fill);
            break;
        case Element_FillLinGradient:
            FillLinGradient lin = Element_FillLinGradient_read(this_ref);
            AnnoLinGradient anno_lin;
            anno_lin.index = lin.index;
            vec2 p0 = st.mat.xy * lin.p0.x + st.mat.zw * lin.p0.y + st.translate;
            vec2 p1 = st.mat.xy * lin.p1.x + st.mat.zw * lin.p1.y + st.translate;
            vec2 dxy = p1 - p0;
            float scale = 1.0 / (dxy.x * dxy.x + dxy.y * dxy.y);
            float line_x = dxy.x * scale;
            float line_y = dxy.y * scale;
            anno_lin.line_x = line_x;
            anno_lin.line_y = line_y;
            anno_lin.line_c = -(p0.x * line_x + p0.y * line_y);
            // TODO: consider consolidating bbox calculation
            if (is_stroke) {
                vec2 lw = get_linewidth(st);
                anno_lin.bbox = st.bbox + vec4(-lw, lw);
                anno_lin.linewidth = st.linewidth * sqrt(abs(st.mat.x * st.mat.w - st.mat.y * st.mat.z));
            } else {
                anno_lin.bbox = st.bbox;
                anno_lin.linewidth = 0.0;
            }
            out_ref = AnnotatedRef(conf.anno_alloc.offset + (st.path_count - 1) * Annotated_size);
            Annotated_LinGradient_write(conf.anno_alloc, out_ref, fill_mode, anno_lin);
            break;
        case Element_FillImage:
            FillImage fill_img = Element_FillImage_read(this_ref);
            AnnoImage anno_img;
            anno_img.index = fill_img.index;
            anno_img.offset = fill_img.offset;
            if (is_stroke) {
                vec2 lw = get_linewidth(st);
                anno_img.bbox = st.bbox + vec4(-lw, lw);
                anno_img.linewidth = st.linewidth * sqrt(abs(st.mat.x * st.mat.w - st.mat.y * st.mat.z));
            } else {
                anno_img.bbox = st.bbox;
                anno_img.linewidth = 0.0;
            }
            out_ref = AnnotatedRef(conf.anno_alloc.offset + (st.path_count - 1) * Annotated_size);
            Annotated_Image_write(conf.anno_alloc, out_ref, fill_mode, anno_img);
            break;
        case Element_BeginClip:
            Clip begin_clip = Element_BeginClip_read(this_ref);
            AnnoBeginClip anno_begin_clip;
            // This is the absolute bbox, it's been transformed during encoding.
            anno_begin_clip.bbox = begin_clip.bbox;
            if (is_stroke) {
                vec2 lw = get_linewidth(st);
                anno_begin_clip.linewidth = st.linewidth * sqrt(abs(st.mat.x * st.mat.w - st.mat.y * st.mat.z));
            } else {
                anno_fill.linewidth = 0.0;
            }
            out_ref = AnnotatedRef(conf.anno_alloc.offset + (st.path_count - 1) * Annotated_size);
            Annotated_BeginClip_write(conf.anno_alloc, out_ref, fill_mode, anno_begin_clip);
            break;
        case Element_EndClip:
            Clip end_clip = Element_EndClip_read(this_ref);
            // This bbox is expected to be the same as the begin one.
            AnnoEndClip anno_end_clip = AnnoEndClip(end_clip.bbox);
            out_ref = AnnotatedRef(conf.anno_alloc.offset + (st.path_count - 1) * Annotated_size);
            Annotated_EndClip_write(conf.anno_alloc, out_ref, anno_end_clip);
            break;
        case Element_Transform:
            TransformSeg transform = TransformSeg(st.mat, st.translate);
            TransformSegRef trans_ref = TransformSegRef(conf.trans_alloc.offset + (st.trans_count - 1) * TransformSeg_size);
            TransformSeg_write(conf.trans_alloc, trans_ref, transform);
            break;
        }
    }
}