GitCorner

Code

ossartcrafteffectcraft🌐
665bfac0b339
// GPU Content-Aware Fill: the membrane (harmonic) fill and PatchMatch synthesis of
// effectcraft_raster::inpaint, operation for operation (the CPU reference is the oracle; see
// crates/gpu/src/tests/inpaint.rs).
//
// Bindings are the shared ones (common.wgsl): `src` / `aux` are the input textures (an image, a
// coarser level, or the nearest-neighbour field), `out` is the storage texture and `data` is a
// per-pixel float table — the level's flags:
//   * membrane kernels: data[i] = 1 where the pixel is known (the hole's complement);
//   * PatchMatch kernels: data[i] = bit 0 hole, bit 1 near (a pixel whose patch touches the hole).
//
// Parameter block (P.u = u32, P.f = f32):
//   membrane kernels:  u[0] = (w, h, coarseW, coarseH), u[1] = (x0, y0, 0, 0) (dispatch
//                      origin), u[3].x = this level's offset into `data`
//   down kernels:      u[0] = (srcW, srcH, dstW, dstH)
//   PatchMatch kernels: u[0] = (w, h, r, parity), u[1] = (x0, y0, 0, 0) (dispatch origin),
//                       u[2] = (seed, iteration, 0, EM round), f[0] = (sigma², 0, 0, 0)
//   histogram:          u[0] = (w, h, 0, 0), u[1] = (x0, y0, w, h) (target bounds),
//                       f[0].x = the distance range (0: the SDR range 0…4)
// The nearest-neighbour field texture holds one entry per pixel: r, g = source centre ("px"),
// b = SSD distance (inf where unset), a = 1 where the entry is set.

const IMP_INF: f32 = 1e30;

fn imp_flags(i: i32) -> u32 {
    return u32(max(data[i], 0.0));
}

fn imp_hole(i: i32) -> bool {
    return (imp_flags(i) & 1u) != 0u;
}

fn imp_near(i: i32) -> bool {
    return (imp_flags(i) & 2u) != 0u;
}

// A source centre whose patch is fully known and inside the image (Pm::valid_source).
fn imp_valid_source(x: i32, y: i32, w: i32, h: i32, r: i32) -> bool {
    if (x < r || y < r || x + r >= w || y + r >= h) {
        return false;
    }
    return !imp_near(y * w + x);
}

// PatchMatch's hashing rnd (raster::inpaint::rnd), bit for bit: the CPU's random stream is a
// contract of the algorithm, not an implementation detail.
fn imp_rnd(seed: u32, a: u32, b: u32) -> u32 {
    var h = (seed * 0x9E3779B9u) ^ (a * 0x85EBCA6Bu) ^ (b * 0xC2B2AE35u);
    h = h ^ (h >> 16u);
    h = h * 0x7FEB352Du;
    h = h ^ (h >> 15u);
    h = h * 0x846CA68Bu;
    return h ^ (h >> 16u);
}

// SSD of the patch at target (tx, ty) (clipped to the image) against source (sx, sy)
// (Pm::dist). `cap` short-circuits a match that is already worse.
fn imp_dist(tx: i32, ty: i32, sx: i32, sy: i32, w: i32, h: i32, r: i32, cap: f32) -> f32 {
    var d = 0.0;
    var n = 0.0;
    for (var dy = -r; dy <= r; dy = dy + 1) {
        let ty2 = ty + dy;
        if (ty2 < 0 || ty2 >= h) {
            continue;
        }
        let sy2 = sy + dy;
        for (var dx = -r; dx <= r; dx = dx + 1) {
            let tx2 = tx + dx;
            if (tx2 < 0 || tx2 >= w) {
                continue;
            }
            let a = textureLoad(aux, vec2<i32>(tx2, ty2), 0);
            let b = textureLoad(aux, vec2<i32>(sx + dx, sy2), 0);
            let e = a - b;
            d = d + e.x * e.x + e.y * e.y + e.z * e.z + e.w * e.w;
            n = n + 1.0;
        }
        if (d > cap * max(n, 1.0)) {
            return IMP_INF;
        }
    }
    return d / max(n, 1.0);
}

// ---------------------------------------------------------------- membrane

// membrane_core's coarse level: the known-weighted 2×2 average.
@compute @workgroup_size(16, 16)
fn imp_down(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let cw = i32(P.u[0].z);
    let ch = i32(P.u[0].w);
    let cx = i32(gid.x);
    let cy = i32(gid.y);
    if (cx >= cw || cy >= ch) {
        return;
    }
    var s = vec4<f32>(0.0);
    var n = 0.0;
    for (var dy = 0; dy < 2; dy = dy + 1) {
        for (var dx = 0; dx < 2; dx = dx + 1) {
            let fx = 2 * cx + dx;
            let fy = 2 * cy + dy;
            if (fx < w && fy < h && data[i32(P.u[3].x) + fy * w + fx] > 0.5) {
                s = s + textureLoad(src, vec2<i32>(fx, fy), 0);
                n = n + 1.0;
            }
        }
    }
    var v = vec4<f32>(0.0);
    if (n > 0.0) {
        v = s / n;
    }
    textureStore(out, vec2<i32>(cx, cy), v);
}

// membrane_core's coarse-to-fine step: unknown pixels take the nearest coarse value. The fine
// image is copied into `out` first, so writing only the unknown pixels keeps the known ones.
// Dispatched over the unknown pixels' bounds (`P.u[1]`); the coarse level is valid everywhere.
@compute @workgroup_size(16, 16)
fn imp_up(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let cw = i32(P.u[0].z);
    let ch = i32(P.u[0].w);
    let x = i32(P.u[1].x) + i32(gid.x);
    let y = i32(P.u[1].y) + i32(gid.y);
    if (x >= w || y >= h || data[i32(P.u[3].x) + y * w + x] > 0.5) {
        return;
    }
    let cx = min(x / 2, cw - 1);
    let cy = min(y / 2, ch - 1);
    textureStore(out, vec2<i32>(x, y), textureLoad(src, vec2<i32>(cx, cy), 0));
}

// One relaxation of the unknown pixels (membrane_core's Jacobi sweep). `src` is the current
// state and `aux` is unused. Dispatched over the unknown pixels' bounds (`P.u[1]`): known
// pixels never move, so nothing outside them needs writing. Both `src` and `out` are valid
// across the image (the fine level's, a copy of it, or the full downsample).
@compute @workgroup_size(16, 16)
fn imp_jacobi(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let x = i32(P.u[1].x) + i32(gid.x);
    let y = i32(P.u[1].y) + i32(gid.y);
    if (x >= w || y >= h) {
        return;
    }
    var v = textureLoad(src, vec2<i32>(x, y), 0);
    if (data[i32(P.u[3].x) + y * w + x] <= 0.5) {
        var s = vec4<f32>(0.0);
        var n = 0.0;
        if (x > 0) {
            s = s + textureLoad(src, vec2<i32>(x - 1, y), 0);
            n = n + 1.0;
        }
        if (x + 1 < w) {
            s = s + textureLoad(src, vec2<i32>(x + 1, y), 0);
            n = n + 1.0;
        }
        if (y > 0) {
            s = s + textureLoad(src, vec2<i32>(x, y - 1), 0);
            n = n + 1.0;
        }
        if (y + 1 < h) {
            s = s + textureLoad(src, vec2<i32>(x, y + 1), 0);
            n = n + 1.0;
        }
        if (n > 0.0) {
            v = s / n;
        }
    }
    textureStore(out, vec2<i32>(x, y), v);
}

// ---------------------------------------------------------------- PatchMatch

// PatchMatch's pyramid downsample (downsample): the level's image, hole pixels excluded from the
// average, over `out`'s size.
@compute @workgroup_size(16, 16)
fn imp_pm_down(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let cw = i32(P.u[0].z);
    let ch = i32(P.u[0].w);
    let cx = i32(gid.x);
    let cy = i32(gid.y);
    if (cx >= cw || cy >= ch) {
        return;
    }
    var s = vec4<f32>(0.0);
    var n = 0.0;
    for (var dy = 0; dy < 2; dy = dy + 1) {
        for (var dx = 0; dx < 2; dx = dx + 1) {
            let fx = min(2 * cx + dx, w - 1);
            let fy = min(2 * cy + dy, h - 1);
            if (!imp_hole(fy * w + fx)) {
                s = s + textureLoad(src, vec2<i32>(fx, fy), 0);
                n = n + 1.0;
            }
        }
    }
    var v = vec4<f32>(0.0);
    if (n > 0.0) {
        v = s / n;
    }
    textureStore(out, vec2<i32>(cx, cy), v);
}

// PatchMatch's coarse-to-fine step: bilinear upsample of the coarse image into this level's hole
// (patch_fill's upsample loop). The fine image is copied into `out` first.
@compute @workgroup_size(16, 16)
fn imp_pm_up(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let cw = i32(P.u[0].z);
    let ch = i32(P.u[0].w);
    let x = i32(P.u[1].x) + i32(gid.x);
    let y = i32(P.u[1].y) + i32(gid.y);
    if (x >= w || y >= h || !imp_hole(y * w + x)) {
        return;
    }
    let fx = clamp((f32(x) + 0.5) / 2.0 - 0.5, 0.0, f32(cw - 1));
    let fy = clamp((f32(y) + 0.5) / 2.0 - 0.5, 0.0, f32(ch - 1));
    let x0 = i32(floor(fx));
    let y0 = i32(floor(fy));
    let x1 = min(x0 + 1, cw - 1);
    let y1 = min(y0 + 1, ch - 1);
    let tx = fx - f32(x0);
    let ty = fy - f32(y0);
    let a = textureLoad(src, vec2<i32>(x0, y0), 0);
    let b = textureLoad(src, vec2<i32>(x1, y0), 0);
    let c = textureLoad(src, vec2<i32>(x0, y1), 0);
    let d = textureLoad(src, vec2<i32>(x1, y1), 0);
    let top = a + (b - a) * tx;
    let bot = c + (d - c) * tx;
    textureStore(out, vec2<i32>(x, y), top + (bot - top) * ty);
}

// The NNF's coarse-to-fine step: ×2 (patch_fill's nnf upsample).
@compute @workgroup_size(16, 16)
fn imp_nnf_up(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let cw = i32(P.u[0].z);
    let ch = i32(P.u[0].w);
    let x = i32(gid.x);
    let y = i32(gid.y);
    if (x >= w || y >= h) {
        return;
    }
    let cx = min(x / 2, cw - 1);
    let cy = min(y / 2, ch - 1);
    let c = textureLoad(src, vec2<i32>(cx, cy), 0);
    var o = vec4<f32>(0.0);
    if (c.a > 0.5) {
        o = vec4<f32>(c.r * 2.0 + f32(x % 2), c.g * 2.0 + f32(y % 2), 0.0, 1.0);
    }
    textureStore(out, vec2<i32>(x, y), o);
}

// A random valid source centre, by rejection (the CPU draws from its compacted source list; the
// distribution over the valid centres is the same, the stream differs from the list's order).
fn imp_any_source(seed: u32, i: u32, k: u32, w: i32, h: i32, r: i32) -> vec2<i32> {
    for (var n = 0u; n < 32u; n = n + 1u) {
        let a = imp_rnd(seed, i, k + n);
        let x = i32(a % u32(w));
        let y = i32((a >> 16u) % u32(h));
        if (imp_valid_source(x, y, w, h, r)) {
            return vec2<i32>(x, y);
        }
    }
    return vec2<i32>(-1, -1);
}

// A round's initial field: the inherited source where it is still valid, a random one otherwise
// (pm_level's initialise/validate step).
@compute @workgroup_size(16, 16)
fn imp_pm_init(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let r = i32(P.u[0].z);
    let x = i32(P.u[1].x) + i32(gid.x);
    let y = i32(P.u[1].y) + i32(gid.y);
    if (x >= w || y >= h) {
        return;
    }
    let i = y * w + x;
    var o = vec4<f32>(0.0, 0.0, IMP_INF, 0.0);
    if (imp_near(i)) {
        let prev = textureLoad(src, vec2<i32>(x, y), 0);
        var s = vec2<i32>(i32(prev.r), i32(prev.g));
        if (prev.a <= 0.5 || !imp_valid_source(s.x, s.y, w, h, r)) {
            // rnd(seed ^ e, i, 0), the round's random source (see imp_any_source).
            s = imp_any_source(P.u[2].x ^ P.u[2].w, u32(i), 0u, w, h, r);
        }
        if (s.x >= 0) {
            let d = imp_dist(x, y, s.x, s.y, w, h, r, IMP_INF);
            o = vec4<f32>(f32(s.x), f32(s.y), d, 1.0);
        }
    }
    textureStore(out, vec2<i32>(x, y), o);
}

// One propagation pass: every target pixel tries its four neighbours' sources shifted by the
// step that would move that neighbour's match onto this pixel. The checkerboard parity in P.u[0].w
// makes the pass race-free (a pixel of one parity only reads the other's).
@compute @workgroup_size(16, 16)
fn imp_pm_prop(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let r = i32(P.u[0].z);
    let x = i32(P.u[1].x) + i32(gid.x);
    let y = i32(P.u[1].y) + i32(gid.y);
    if (x >= w || y >= h) {
        return;
    }
    let cur = textureLoad(src, vec2<i32>(x, y), 0);
    let i = y * w + x;
    if (!imp_near(i) || ((x + y) & 1) != i32(P.u[0].w)) {
        textureStore(out, vec2<i32>(x, y), cur);
        return;
    }
    var best = vec2<i32>(i32(cur.r), i32(cur.g));
    var bd = cur.b;
    if (cur.a <= 0.5) {
        bd = IMP_INF;
    }
    for (var k = 0; k < 4; k = k + 1) {
        var nx = x;
        var ny = y;
        var sx = 0;
        var sy = 0;
        if (k == 0) {
            nx = x - 1;
            sx = 1;
        } else if (k == 1) {
            nx = x + 1;
            sx = -1;
        } else if (k == 2) {
            ny = y - 1;
            sy = 1;
        } else {
            ny = y + 1;
            sy = -1;
        }
        if (nx < 0 || ny < 0 || nx >= w || ny >= h) {
            continue;
        }
        let n = textureLoad(src, vec2<i32>(nx, ny), 0);
        if (n.a <= 0.5) {
            continue;
        }
        let c = vec2<i32>(i32(n.r) + sx, i32(n.g) + sy);
        if (c.x == best.x && c.y == best.y) {
            continue;
        }
        if (!imp_valid_source(c.x, c.y, w, h, r)) {
            continue;
        }
        let d = imp_dist(x, y, c.x, c.y, w, h, r, bd);
        if (d < bd) {
            bd = d;
            best = c;
        }
    }
    // alpha = the entry is set: `bd` stays INF only if no match was found.
    textureStore(out, vec2<i32>(x, y), vec4<f32>(f32(best.x), f32(best.y), bd, select(0.0, 1.0, bd < IMP_INF)));
}

// The random search (halving radius) and one random source anywhere, after propagation.
@compute @workgroup_size(16, 16)
fn imp_pm_rand(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let r = i32(P.u[0].z);
    let x = i32(P.u[1].x) + i32(gid.x);
    let y = i32(P.u[1].y) + i32(gid.y);
    if (x >= w || y >= h) {
        return;
    }
    let cur = textureLoad(src, vec2<i32>(x, y), 0);
    let i = y * w + x;
    if (!imp_near(i) || cur.a <= 0.5) {
        textureStore(out, vec2<i32>(x, y), cur);
        return;
    }
    var best = vec2<i32>(i32(cur.r), i32(cur.g));
    var bd = cur.b;
    let seed = P.u[2].x;
    let it = P.u[2].y;
    let em = P.u[2].w;
    let iu = u32(i);
    var rad = max(w, h);
    var k = 0u;
    while (rad >= 1) {
        let a = imp_rnd(seed + it * 977u + em * 31u, iu, k);
        let ox = i32(a % u32(2 * rad + 1)) - rad;
        let oy = i32((a >> 16u) % u32(2 * rad + 1)) - rad;
        let c = vec2<i32>(best.x + ox, best.y + oy);
        if (imp_valid_source(c.x, c.y, w, h, r)) {
            let d = imp_dist(x, y, c.x, c.y, w, h, r, bd);
            if (d < bd) {
                bd = d;
                best = c;
            }
        }
        rad = rad / 2;
        k = k + 1u;
    }
    let any = imp_any_source(seed ^ 0xABCDu, iu, it + em * 64u, w, h, r);
    if (any.x >= 0 && (any.x != best.x || any.y != best.y)) {
        let d = imp_dist(x, y, any.x, any.y, w, h, r, bd);
        if (d < bd) {
            bd = d;
            best = any;
        }
    }
    textureStore(out, vec2<i32>(x, y), vec4<f32>(f32(best.x), f32(best.y), bd, select(0.0, 1.0, bd < IMP_INF)));
}

// Carry a round's field back into the nearest-neighbour field (only targets, as on the CPU).
@compute @workgroup_size(16, 16)
fn imp_nnf_store(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let x = i32(gid.x);
    let y = i32(gid.y);
    if (x >= w || y >= h) {
        return;
    }
    let i = y * w + x;
    var o = textureLoad(aux, vec2<i32>(x, y), 0);
    if (imp_near(i)) {
        let f = textureLoad(src, vec2<i32>(x, y), 0);
        o = vec4<f32>(f.r, f.g, 0.0, 1.0);
    }
    textureStore(out, vec2<i32>(x, y), o);
}

// The vote: every hole pixel becomes the distance-weighted mean of the samples its overlapping
// patches carry (pm_level's vote step). `aux` is the current image; the image is copied into
// `out` first, so only hole pixels are written.
@compute @workgroup_size(16, 16)
fn imp_pm_vote(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let r = i32(P.u[0].z);
    let x = i32(P.u[1].x) + i32(gid.x);
    let y = i32(P.u[1].y) + i32(gid.y);
    if (x >= w || y >= h) {
        return;
    }
    let i = y * w + x;
    if (!imp_hole(i)) {
        return;
    }
    let sigma2 = P.f[0].x;
    var acc = vec4<f32>(0.0);
    var wsum = 0.0;
    for (var dy = -r; dy <= r; dy = dy + 1) {
        let py = y + dy;
        if (py < 0 || py >= h) {
            continue;
        }
        for (var dx = -r; dx <= r; dx = dx + 1) {
            let px = x + dx;
            if (px < 0 || px >= w) {
                continue;
            }
            let f = textureLoad(src, vec2<i32>(px, py), 0);
            if (f.a <= 0.5 || f.b >= IMP_INF) {
                continue;
            }
            let s = vec2<i32>(i32(f.r) - dx, i32(f.g) - dy);
            let wt = exp(-f.b / (2.0 * sigma2));
            acc = acc + textureLoad(aux, vec2<i32>(s.x, s.y), 0) * wt;
            wsum = wsum + wt;
        }
    }
    if (wsum > 0.0) {
        textureStore(out, vec2<i32>(x, y), acc / wsum);
    } else {
        textureStore(out, vec2<i32>(x, y), textureLoad(aux, vec2<i32>(x, y), 0));
    }
}

// The workgroup's 1024 distance bins (`imp_hist`); the name is unique across the concatenated
// shader sources because `var<workgroup>` is module scope.
var<workgroup> imp_hist_bins: array<atomic<u32>, 1024>;
// The largest finite distance this dispatch saw (as its f32 bit pattern: positive floats are
// ordered by their bits). `sigma2` uses it to learn whether the frame needs a wider range.
var<workgroup> imp_hist_max: atomic<u32>;

// One workgroup's histogram of the targets' match distances, for the vote's sigma² (the CPU takes
// the 75th percentile of the finite distances). The single workgroup accumulates the whole
// population through the shared atomic bins above.
//
// `P.f[0].x` is the range the bins cover; 0 selects the SDR range 0…4, where an image whose
// channels are all ≤ 1 lives: each channel's squared difference is ≤ 4, so the mean SSD is too.
// Frames with values above 1 (32-bpc HDR) have larger distances, so `sigma2` re-dispatches with
// the observed maximum as the range instead of clamping them to bin 1023, which would report a
// sigma² of ≈ 4 for a distance of 1600 and round the vote's weights to zero. The observed maximum
// rides in bin 0's unused `.g` channel on every dispatch (its `.x` stays the count).
@compute @workgroup_size(256, 1, 1)
fn imp_hist(@builtin(global_invocation_id) gid: vec3<u32>) {
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let x0 = i32(P.u[1].x);
    let y0 = i32(P.u[1].y);
    let bw = i32(P.u[1].z);
    let bh = i32(P.u[1].w);
    let t = gid.x;
    let range = select(4.0, P.f[0].x, P.f[0].x > 0.0);
    let scale = 1024.0 / range;
    if (t == 0u) {
        atomicStore(&imp_hist_max, 0u);
    }
    // One workgroup, so the whole population is counted through shared atomics: a per-thread
    // strided pass would keep only the pixels whose bin selected that thread (a biased ~1/256
    // subsample, correlated with the pixel index).
    for (var i = t; i < 1024u; i = i + 256u) {
        atomicStore(&imp_hist_bins[i], 0u);
    }
    workgroupBarrier();
    let total = u32(max(bw, 0) * max(bh, 0));
    for (var idx = t; idx < total; idx = idx + 256u) {
        let x = x0 + i32(idx) % bw;
        let y = y0 + i32(idx) / bw;
        let i = y * w + x;
        if (!imp_near(i)) {
            continue;
        }
        let f = textureLoad(src, vec2<i32>(x, y), 0);
        if (f.a <= 0.5 || f.b >= IMP_INF) {
            continue;
        }
        atomicMax(&imp_hist_max, bitcast<u32>(f.b));
        // Clamp in f32 before the conversion: a distance far outside the range (a mismatched patch
        // in an HDR frame) would overflow the i32 conversion, which is indeterminate in WGSL.
        let b = u32(clamp(f.b * scale, 0.0, 1023.0));
        atomicAdd(&imp_hist_bins[b], 1u);
    }
    workgroupBarrier();
    // 256 threads × 4 bins cover the histogram.
    for (var j = 0u; j < 4u; j = j + 1u) {
        let bin = t * 4u + j;
        textureStore(out, vec2<i32>(i32(bin), 0), vec4<f32>(f32(atomicLoad(&imp_hist_bins[bin])), 0.0, 0.0, 0.0));
    }
    // Thread 0 is bin 0's only writer, so this store follows the one above. `.g` carries the
    // observed maximum: host readbacks keep the row 1024 texels wide (a 16 KB, 256-aligned copy).
    if (t == 0u) {
        textureStore(out, vec2<i32>(0, 0), vec4<f32>(f32(atomicLoad(&imp_hist_bins[0])), bitcast<f32>(atomicLoad(&imp_hist_max)), 0.0, 0.0));
    }
}

// ---------------------------------------------------------------- block flow (flow completion)

// The block matcher of effectcraft_raster::flow::block_flow(a, b, 8, 6), which the fill uses to
// compute the motion between neighbouring membrane-filled frames before completing it inside the
// holes (`FillBackend::flow`). `src` packs the two frames' luma planes at the current level:
// .x is frame A's, .y is frame B's (`effectcraft_raster::flow::Plane::luma`). The kernels mirror
// the CPU operation for operation, so the field matches the CPU's (crates/gpu/src/tests/inpaint.rs).

// Plane::half of the packed pair: the clamped 2×2 average of each channel.
@compute @workgroup_size(16, 16)
fn imp_fl_half(@builtin(global_invocation_id) gid: vec3<u32>) {
    let cx = i32(gid.x);
    let cy = i32(gid.y);
    if (cx >= i32(P.u[0].z) || cy >= i32(P.u[0].w)) {
        return;
    }
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    var sx = 0.0;
    var sy = 0.0;
    for (var dy = 0; dy < 2; dy = dy + 1) {
        for (var dx = 0; dx < 2; dx = dx + 1) {
            let v = textureLoad(src, vec2<i32>(min(2 * cx + dx, w - 1), min(2 * cy + dy, h - 1)), 0);
            sx = sx + v.x;
            sy = sy + v.y;
        }
    }
    textureStore(out, vec2<i32>(cx, cy), vec4<f32>(sx * 0.25, sy * 0.25, 0.0, 0.0));
}

// Plane::get: the packed luma at (x, y), clamped to the plane.
fn imp_fl_tex(x: i32, y: i32, w: i32, h: i32) -> vec2<f32> {
    let v = textureLoad(src, clamp(vec2<i32>(x, y), vec2<i32>(0, 0), vec2<i32>(w - 1, h - 1)), 0);
    return vec2<f32>(v.x, v.y);
}

// The block match's SAD with A's block already loaded (`la`, row-major): B's luma is the packed
// .y. The sub-pixel kernel's five fits share the window's block, so it is read once; the search
// hoists its own 4×4/8×8 block the same way. The loops' bounds are literals so the backend can
// unroll them and keep the loads in flight — a runtime-bound loop runs an order of magnitude
// slower.
fn imp_fl_sad8h(bx: i32, by: i32, dx: i32, dy: i32, w: i32, h: i32, la: array<f32, 64>) -> f32 {
    var s = 0.0;
    for (var yy = 0; yy < 8; yy = yy + 1) {
        for (var xx = 0; xx < 8; xx = xx + 1) {
            s = s + abs(la[yy * 8 + xx] - imp_fl_tex(bx + xx + dx, by + yy + dy, w, h).y);
        }
    }
    return s;
}

// block_flow_window's coarse-to-fine search at one level: one integer vector per tile, seeded by
// the previous (coarser) level's vector at the tile and its four neighbours. `aux` is that field
// (`P.u[2].x` = 0 at the coarsest level, where the only seed is the zero vector).
@compute @workgroup_size(16, 16)
fn imp_fl_search(@builtin(global_invocation_id) gid: vec3<u32>) {
    let cols = i32(P.u[0].z);
    let rows = i32(P.u[0].w);
    let c = i32(gid.x);
    let r = i32(gid.y);
    if (c >= cols || r >= rows) {
        return;
    }
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let bs = i32(P.u[1].x);
    let k = i32(P.u[1].z);
    let rad = i32(P.u[1].w);
    let lbs = max(i32(P.u[1].y) / k, 4);
    let bx = c * bs / k;
    let by = r * bs / k;
    // The zero vector plus up to five neighbour seeds (the tile and its four neighbours).
    var seeds: array<vec2<i32>, 6>;
    var ns = 0;
    seeds[ns] = vec2<i32>(0, 0);
    ns = ns + 1;
    if (P.u[2].x != 0u) {
        var nbr = array<vec2<i32>, 5>(vec2<i32>(0, 0), vec2<i32>(-1, 0), vec2<i32>(1, 0), vec2<i32>(0, -1), vec2<i32>(0, 1));
        for (var j = 0; j < 5; j = j + 1) {
            let nc = c + nbr[j].x;
            let nr = r + nbr[j].y;
            if (nc >= 0 && nr >= 0 && nc < cols && nr < rows) {
                let pv = textureLoad(aux, vec2<i32>(nc, nr), 0);
                seeds[ns] = vec2<i32>(i32(round(pv.x)) * 2, i32(round(pv.y)) * 2);
                ns = ns + 1;
            }
        }
    }
    // sort_unstable + dedup: distinct seeds in lexicographic (x, then y) order.
    for (var i = 1; i < ns; i = i + 1) {
        let key = seeds[i];
        var j = i - 1;
        while (j >= 0 && (seeds[j].x > key.x || (seeds[j].x == key.x && seeds[j].y > key.y))) {
            seeds[j + 1] = seeds[j];
            j = j - 1;
        }
        seeds[j + 1] = key;
    }
    var m = 0;
    for (var i = 0; i < ns; i = i + 1) {
        if (m == 0 || seeds[i].x != seeds[m - 1].x || seeds[i].y != seeds[m - 1].y) {
            seeds[m] = seeds[i];
            m = m + 1;
        }
    }
    ns = m;
    // A's block is the same for every candidate, so load it once (the unrolled loops keep it in
    // registers) and the search only reads B's shifted block.
    var la4: array<f32, 16>;
    var la8: array<f32, 64>;
    if (lbs >= 8) {
        for (var yy = 0; yy < 8; yy = yy + 1) {
            for (var xx = 0; xx < 8; xx = xx + 1) {
                la8[yy * 8 + xx] = imp_fl_tex(bx + xx, by + yy, w, h).x;
            }
        }
    } else {
        for (var yy = 0; yy < 4; yy = yy + 1) {
            for (var xx = 0; xx < 4; xx = xx + 1) {
                la4[yy * 4 + xx] = imp_fl_tex(bx + xx, by + yy, w, h).x;
            }
        }
    }
    var best = vec2<i32>(0, 0);
    var best_e = 1e30;
    for (var si = 0; si < ns; si = si + 1) {
        let s = seeds[si];
        for (var dy = -rad; dy <= rad; dy = dy + 1) {
            for (var dx = -rad; dx <= rad; dx = dx + 1) {
                let d0 = s.x + dx;
                let d1 = s.y + dy;
                var acc = 0.0;
                if (lbs >= 8) {
                    for (var yy = 0; yy < 8; yy = yy + 1) {
                        for (var xx = 0; xx < 8; xx = xx + 1) {
                            acc = acc + abs(la8[yy * 8 + xx] - imp_fl_tex(bx + xx + d0, by + yy + d1, w, h).y);
                        }
                    }
                } else {
                    for (var yy = 0; yy < 4; yy = yy + 1) {
                        for (var xx = 0; xx < 4; xx = xx + 1) {
                            acc = acc + abs(la4[yy * 4 + xx] - imp_fl_tex(bx + xx + d0, by + yy + d1, w, h).y);
                        }
                    }
                }
                let e = acc + 1e-4 * f32(abs(d0) + abs(d1));
                if (e < best_e) {
                    best_e = e;
                    best = vec2<i32>(d0, d1);
                }
            }
        }
    }
    textureStore(out, vec2<i32>(c, r), vec4<f32>(f32(best.x), f32(best.y), 0.0, 0.0));
}

// The parabola fit of the SAD around the best vector (block_flow_window's sub-pixel step).
fn imp_fl_fit(em: f32, ep: f32, e0: f32) -> f32 {
    let den = em - 2.0 * e0 + ep;
    if (den > 1e-6) {
        return clamp(0.5 * (em - ep) / den, -0.5, 0.5);
    }
    return 0.0;
}

// Sub-pixel refinement at full resolution: `aux` is the integer field of level 0, `src` the
// level-0 packed luma (`P.u[1]` = (tile, window, 0, 0)).
@compute @workgroup_size(16, 16)
fn imp_fl_subpix(@builtin(global_invocation_id) gid: vec3<u32>) {
    let cols = i32(P.u[0].z);
    let rows = i32(P.u[0].w);
    let c = i32(gid.x);
    let r = i32(gid.y);
    if (c >= cols || r >= rows) {
        return;
    }
    let w = i32(P.u[0].x);
    let h = i32(P.u[0].y);
    let bs = i32(P.u[1].x);
    let win = i32(P.u[1].y);
    let bx = c * bs;
    let by = r * bs;
    let f = textureLoad(aux, vec2<i32>(c, r), 0);
    let d = vec2<i32>(i32(round(f.x)), i32(round(f.y)));
    // The window's A block is the same for the five SADs: load it once (the loop is unrolled).
    var la: array<f32, 64>;
    for (var yy = 0; yy < 8; yy = yy + 1) {
        for (var xx = 0; xx < 8; xx = xx + 1) {
            la[yy * 8 + xx] = imp_fl_tex(bx + xx, by + yy, w, h).x;
        }
    }
    let e0 = imp_fl_sad8h(bx, by, d.x, d.y, w, h, la);
    let sx = imp_fl_fit(imp_fl_sad8h(bx, by, d.x - 1, d.y, w, h, la), imp_fl_sad8h(bx, by, d.x + 1, d.y, w, h, la), e0);
    let sy = imp_fl_fit(imp_fl_sad8h(bx, by, d.x, d.y - 1, w, h, la), imp_fl_sad8h(bx, by, d.x, d.y + 1, w, h, la), e0);
    textureStore(out, vec2<i32>(c, r), vec4<f32>(f32(d.x) + sx, f32(d.y) + sy, 0.0, 0.0));
}

// The 3×3 component-wise vector median against outliers (each component sorted on its own).
@compute @workgroup_size(16, 16)
fn imp_fl_median(@builtin(global_invocation_id) gid: vec3<u32>) {
    let cols = i32(P.u[0].z);
    let rows = i32(P.u[0].w);
    let c = i32(gid.x);
    let r = i32(gid.y);
    if (c >= cols || r >= rows) {
        return;
    }
    var xs: array<f32, 9>;
    var ys: array<f32, 9>;
    var n = 0;
    for (var dr = -1; dr <= 1; dr = dr + 1) {
        for (var dc = -1; dc <= 1; dc = dc + 1) {
            let nc = c + dc;
            let nr = r + dr;
            if (nc >= 0 && nr >= 0 && nc < cols && nr < rows) {
                let v = textureLoad(src, vec2<i32>(nc, nr), 0);
                xs[n] = v.x;
                ys[n] = v.y;
                n = n + 1;
            }
        }
    }
    for (var i = 1; i < n; i = i + 1) {
        let kx = xs[i];
        var j = i - 1;
        while (j >= 0 && xs[j] > kx) {
            xs[j + 1] = xs[j];
            j = j - 1;
        }
        xs[j + 1] = kx;
        let ky = ys[i];
        j = i - 1;
        while (j >= 0 && ys[j] > ky) {
            ys[j + 1] = ys[j];
            j = j - 1;
        }
        ys[j + 1] = ky;
    }
    textureStore(out, vec2<i32>(c, r), vec4<f32>(xs[n / 2], ys[n / 2], 0.0, 0.0));
}