#include "ttf_internal.h"
#include <string_utils.h>

// 轮廓 → 线段转换
//
// TrueType 轮廓遍历：对每对连续点，发射直线或二次贝塞尔曲线。
// 两个连续的非曲线点会触发合成一个曲线中点。
//
// 所有坐标全程使用 26.6 定点数。
void ttf_outline_to_segments(const ttf_outline_t* outline,
    ttf_seg_t* segs, SUINT32* num_segs)
{
    *num_segs = 0;
    f26_6 syn_x[256];
    f26_6 syn_y[256];
    int n_syn = 0;

    for (SUINT16 ci = 0; ci < outline->num_contours; ci++) {
        SUINT16 first = outline->first[ci];
        SUINT16 last  = outline->last[ci];
        int n_pts = last - first + 1;
        if (n_pts < 2) continue;

        f26_6  lx[1024];
        f26_6  ly[1024];
        SUINT8 on_c[1024];
        for (int i = 0; i < n_pts; i++) {
            lx[i]   = outline->x[first + i];
            ly[i]   = outline->y[first + i];
            on_c[i] = outline->on_curve[first + i];
        }

        // First on-curve point
        int start = 0;
        while (start < n_pts && !on_c[start]) start++;
        if (start == n_pts) start = 0;  // all off-curve (rare) — keep going

        int anchor  = start;
        int pending = -1;

        #define GET_X(i) ((i) < n_pts ? lx[(i)] : syn_x[(i) - n_pts])
        #define GET_Y(i) ((i) < n_pts ? ly[(i)] : syn_y[(i) - n_pts])
        #define PUSH_LINE(a, b) do {                                      \
            ttf_seg_t* __s = &segs[(*num_segs)++];                       \
            __s->x0 = GET_X(a); __s->y0 = GET_Y(a);                      \
            __s->x1 = GET_X(b); __s->y1 = GET_Y(b);                      \
            __s->cx = __s->x0; __s->cy = __s->y0; __s->is_line = 1;      \
        } while (0)
        #define PUSH_QUAD(a, c, b) do {                                  \
            ttf_seg_t* __s = &segs[(*num_segs)++];                       \
            __s->x0 = GET_X(a); __s->y0 = GET_Y(a);                      \
            __s->x1 = GET_X(b); __s->y1 = GET_Y(b);                      \
            __s->cx = GET_X(c); __s->cy = GET_Y(c); __s->is_line = 0;    \
        } while (0)

        for (int step = 0; step < n_pts; step++) {
            int cur = (start + step) % n_pts;
            if (step == 0) { anchor = cur; continue; }
            if (on_c[cur]) {
                if (pending < 0) {
                    PUSH_LINE(anchor, cur);
                } else {
                    PUSH_QUAD(anchor, pending, cur);
                    pending = -1;
                }
                anchor = cur;
            } else {
                if (pending < 0) {
                    pending = cur;
                } else {
                    int syn_idx = n_pts + n_syn;
                    syn_x[n_syn] = (GET_X(pending) + GET_X(cur)) >> 1;
                    syn_y[n_syn] = (GET_Y(pending) + GET_Y(cur)) >> 1;
                    n_syn++;
                    PUSH_QUAD(anchor, pending, syn_idx);
                    anchor  = syn_idx;
                    pending = cur;
                }
            }
        }
        if (pending >= 0) {
            PUSH_QUAD(anchor, pending, start);
        } else if (anchor != start) {
            PUSH_LINE(anchor, start);
        }

        #undef GET_X
        #undef GET_Y
        #undef PUSH_LINE
        #undef PUSH_QUAD
    }
}

// 整数平方根（牛顿法）
static SUINT32 isqrt_u64(SUINT64 n) {
    if (n == 0) return 0;
    SUINT32 x = (n > 0xFFFFFFFFu) ? 0xFFFFu : (SUINT32)n;
    SUINT32 y = (x + 1) >> 1;
    while (y < x) { x = y; y = (x + (SUINT32)(n / x)) >> 1; }
    return x;
}

// 扫描线填充 + 子像素超采样
//
// 对每个输出行，运行 N 条子扫描线，偏移为 (k+0.5)/N。
// 对每条子扫描线 y，收集所有 x 交点，排序后交替填充 x 对。
// 对 N 个子采样求和得到每个像素的覆盖率 [0, N]。
void ttf_rasterize(const ttf_seg_t* segs, SUINT32 num_segs,
    SSINT32 x0, SSINT32 y0, SUINT32 w, SUINT32 h,
    SUINT8* coverage, SUINT32 N)
{
    // 清空覆盖率缓冲区
    for (SUINT32 i = 0; i < w * h; i++) coverage[i] = 0;

    // 交点 x 缓冲区（每扫描线，最大可能数 = num_segs）
    f26_6 xs[2048];
    if (num_segs > 2048) num_segs = 2048;

    for (SUINT32 row = 0; row < h; row++) {
        for (SUINT32 k = 0; k < N; k++) {
            // Sub-scanline y, in 26.6, with y = 0 at glyph top
            f26_6 sy = (f26_6)((row * 64) + ((k * 2 + 1) * 64) / (SSINT32)(N * 2));
            // ^ y center of subpixel k: (k + 0.5) * 64 / N
            //   = ((2k+1) * 64) / (2N)
            // For N=5: k=0 -> 6.4, k=1 -> 19.2, etc.

            SUINT32 nxs = 0;
            for (SUINT32 s = 0; s < num_segs; s++) {
                const ttf_seg_t* g = &segs[s];
                if (g->is_line) {
                    f26_6 y0s = g->y0;
                    f26_6 y1s = g->y1;
                    if (y0s == y1s) continue;  // horizontal — skip
                    // t = (sy - y0s) / (y1s - y0s)  in (0, 1)
                    if (((y0s < sy) && (y1s < sy)) ||
                        ((y0s > sy) && (y1s > sy))) continue;
                    f26_6 t = f26_div(sy - y0s, y1s - y0s);
                    if (t <= 0 || t >= F26_ONE) continue;
                    f26_6 x = g->x0 + f26_mul(t, g->x1 - g->x0);
                    xs[nxs++] = x;
                } else {
                    // Quadratic: y(t) = (1-t)^2 y0 + 2(1-t)t cy + t^2 y1
                    //   a t^2 + b t + c = 0
                    //   a = y1 - 2 cy + y0
                    //   b = 2 (cy - y0)
                    //   c = y0 - sy
                    SSINT64 a = (SSINT64)g->y1 - 2 * (SSINT64)g->cy + (SSINT64)g->y0;
                    SSINT64 b = 2 * ((SSINT64)g->cy - (SSINT64)g->y0);
                    SSINT64 c = (SSINT64)g->y0 - (SSINT64)sy;
                    SSINT32 t0_valid = 0, t1_valid = 0;
                    f26_6 t0 = 0, t1 = 0;
                    if (a == 0) {
                        // Linear
                        if (b == 0) continue;
                        f26_6 t = f26_div((f26_6)(-c), (f26_6)b);
                        if (t > 0 && t < F26_ONE) { t0 = t; t0_valid = 1; }
                    } else {
                        SSINT64 disc = b * b - 4 * a * c;
                        if (disc < 0) continue;
                        SUINT32 sq = isqrt_u64((SUINT64)disc);
                        // 26.6 roots: t = (-b ± sqrt(disc)) / (2a)
                        // All in 26.6 fp.
                        // t = (-b ± sq) / (2a); both numerator and denom in 26.6 units
                        // Use f26_div: t_26_6 = ((-b ± sq) << 6) / (2a)
                        SSINT64 denom = 2 * a;
                        if (denom == 0) continue;
                        SSINT64 num0 = -b + (SSINT64)sq;
                        SSINT64 num1 = -b - (SSINT64)sq;
                        t0 = (f26_6)(num0 == 0 ? 0 : (num0 << 6) / denom);
                        t1 = (f26_6)(num1 == 0 ? 0 : (num1 << 6) / denom);
                        if (t0 > 0 && t0 < F26_ONE) t0_valid = 1;
                        if (t1 > 0 && t1 < F26_ONE) t1_valid = 1;
                    }
                    if (t0_valid) {
                        // x(t) = (1-t)^2 x0 + 2(1-t)t cx + t^2 x1
                        f26_6 omt = F26_ONE - t0;
                        f26_6 x = f26_mul(f26_mul(omt, omt), g->x0)
                                + f26_mul(2 * f26_mul(omt, t0), g->cx)
                                + f26_mul(f26_mul(t0, t0), g->x1);
                        xs[nxs++] = x;
                    }
                    if (t1_valid) {
                        f26_6 omt = F26_ONE - t1;
                        f26_6 x = f26_mul(f26_mul(omt, omt), g->x0)
                                + f26_mul(2 * f26_mul(omt, t1), g->cx)
                                + f26_mul(f26_mul(t1, t1), g->x1);
                        xs[nxs++] = x;
                    }
                }
            }

            if (nxs < 2) continue;
            // Insertion sort
            for (SUINT32 i = 1; i < nxs; i++) {
                f26_6 v = xs[i]; SUINT32 j = i;
                while (j > 0 && xs[j-1] > v) { xs[j] = xs[j-1]; j--; }
                xs[j] = v;
            }
            // Deduplicate: merge intersections within 1/16 pixel (4 in 26.6)
            SUINT32 nxd = 0;
            for (SUINT32 i = 0; i < nxs; i++) {
                if (nxd > 0 && (xs[i] - xs[nxd - 1]) < 4) {
                    continue;
                }
                xs[nxd++] = xs[i];
            }
            nxs = nxd;
            // Fill alternating pairs
            for (SUINT32 i = 0; i + 1 < nxs; i += 2) {
                f26_6 xa = xs[i];
                f26_6 xb = xs[i+1];
                if (xa == xb) continue;
                SSINT32 c0 = F26_FLOOR(xa);
                SSINT32 c1 = F26_FLOOR(xb);
                if (c0 == c1) continue;
                if (c0 < 0) c0 = 0;
                if (c1 > (SSINT32)w) c1 = (SSINT32)w;
                for (SSINT32 x = c0; x < c1; x++) {
                    if (x >= 0 && x < (SSINT32)w) coverage[row * w + x]++;
                }
            }
        }
    }
    // 覆盖率转换在调用端通过 N 完成
    (void)x0; (void)y0;
}
