java-topology/defects/melonds-0001/test/melonds-0001-test.cpp

// melonds-0001-test.cpp
// CWE-407: GPU3D soft-renderer RenderScanline O(P * S) per frame in GPU3D_Soft.cpp
//
// SoftRenderer3D::RenderScanline iterates ALL polygons (up to 2048 on NDS) on
// every scanline (192 lines per frame) to test if y >= polygon->YTop && y <
// polygon->YBottom. This gives O(P * S) work per frame where P is polygon count
// and S is scanline count (192).
//
// Fix: sort polygons by YTop before rendering; maintain an active-list swept by
// YTop insertion. Each scanline only visits polygons active at that line, giving
// O(P log P + A_total) where A_total = sum of per-scanline active counts.
//
// Worst-case speedup at P=2048: O(P*S) = 393,216 iterations vs O(P log P +
// P*avg_height) where avg_height << S for typical game geometry.

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <vector>

using s32 = int32_t;

// Minimal polygon representation matching melonDS GPU3D.h
struct Polygon {
    s32 YTop    = 0;
    s32 YBottom = 0;
    bool IsShadowMask = false;
    bool Degenerate   = false;
};

// RendererPolygon stub
struct RendererPolygon {
    Polygon* PolyData = nullptr;
};

static int gRenderCount = 0;

static void RenderPolygonScanline(RendererPolygon* /*rp*/, s32 /*y*/)
{
    gRenderCount++;
}

// ---------- DEFECTIVE: O(P * S) per frame ----------
namespace Defective {
    static int renderFrame(RendererPolygon* polyList, int npolys)
    {
        gRenderCount = 0;
        for (s32 y = 0; y < 192; y++)
        {
            for (int i = 0; i < npolys; i++)
            {
                RendererPolygon* rp = &polyList[i];
                Polygon* polygon = rp->PolyData;
                if (y >= polygon->YTop &&
                    (y < polygon->YBottom ||
                     (y == polygon->YTop && polygon->YBottom == polygon->YTop)))
                {
                    RenderPolygonScanline(rp, y);
                }
            }
        }
        return gRenderCount;
    }
}

// ---------- PATCHED: sort by YTop, active-list sweep ----------
namespace Patched {
    static int renderFrame(RendererPolygon* polyList, int npolys)
    {
        gRenderCount = 0;

        // Sort by YTop ascending.
        std::sort(polyList, polyList + npolys,
            [](const RendererPolygon& a, const RendererPolygon& b) {
                return a.PolyData->YTop < b.PolyData->YTop;
            });

        std::vector<int> active;
        int next = 0;

        for (s32 y = 0; y < 192; y++)
        {
            // Insert polygons starting at this scanline.
            while (next < npolys && polyList[next].PolyData->YTop <= y)
                active.push_back(next++);

            // Render active polygons covering this scanline.
            for (int idx : active)
            {
                RendererPolygon* rp = &polyList[idx];
                Polygon* polygon = rp->PolyData;
                if (y < polygon->YBottom ||
                    (y == polygon->YTop && polygon->YBottom == polygon->YTop))
                {
                    RenderPolygonScanline(rp, y);
                }
            }

            // Prune finished polygons.
            active.erase(
                std::remove_if(active.begin(), active.end(), [&](int idx) {
                    Polygon* p = polyList[idx].PolyData;
                    return y >= p->YBottom &&
                           !(y == p->YTop && p->YBottom == p->YTop);
                }),
                active.end()
            );
        }
        return gRenderCount;
    }
}

// Build a polygon list: P polygons spread uniformly across 192 scanlines.
static void buildPolygons(int P, std::vector<Polygon>& polys,
                           std::vector<RendererPolygon>& rps)
{
    polys.resize(P);
    rps.resize(P);
    for (int i = 0; i < P; i++)
    {
        // Spread polygons uniformly; each spans ~8 scanlines (small sprites, typical game geometry).
        polys[i].YTop    = (i * 192 / P) % 192;
        polys[i].YBottom = std::min(192, polys[i].YTop + 8);
        rps[i].PolyData  = &polys[i];
    }
}

int main()
{
    const int P = 2048; // NDS hardware polygon limit

    std::vector<Polygon> polys;
    std::vector<RendererPolygon> rps_defect, rps_patch;
    buildPolygons(P, polys, rps_defect);
    // Patched version sorts in-place; give it a separate copy.
    std::vector<Polygon> polys2 = polys;
    rps_patch.resize(P);
    for (int i = 0; i < P; i++) rps_patch[i].PolyData = &polys2[i];

    // Correctness: both must call RenderPolygonScanline the same number of times.
    int cnt_defect = Defective::renderFrame(rps_defect.data(), P);
    int cnt_patch  = Patched::renderFrame(rps_patch.data(), P);
    assert(cnt_defect == cnt_patch && "render counts must match");
    printf("PASS correctness: both rendered %d polygon-scanlines for P=%d\n",
           cnt_defect, P);

    // Performance: measure over multiple frames.
    const int FRAMES = 60;
    auto t0 = std::chrono::high_resolution_clock::now();
    for (int f = 0; f < FRAMES; f++) Defective::renderFrame(rps_defect.data(), P);
    auto t1 = std::chrono::high_resolution_clock::now();

    // Re-build patch copy for each frame (sort mutates order).
    double ms_patch = 0;
    for (int f = 0; f < FRAMES; f++)
    {
        std::vector<Polygon> pp = polys;
        std::vector<RendererPolygon> rr(P);
        for (int i = 0; i < P; i++) rr[i].PolyData = &pp[i];
        auto a = std::chrono::high_resolution_clock::now();
        Patched::renderFrame(rr.data(), P);
        auto b = std::chrono::high_resolution_clock::now();
        ms_patch += std::chrono::duration<double, std::milli>(b - a).count();
    }
    double ms_defect = std::chrono::duration<double, std::milli>(t1 - t0).count();
    double ratio = ms_defect / ms_patch;

    printf("Defective: %.2f ms  Patched: %.2f ms  Ratio: %.1fx (P=%d, %d frames)\n",
           ms_defect, ms_patch, ratio, P, FRAMES);

    assert(ratio > 1.5 && "Patched should be at least 1.5x faster");
    printf("PASS performance: %.1fx speedup\n", ratio);
    return 0;
}