/* Copyright 2022 the SumatraPDF project authors (see AUTHORS file).
   License: GPLv3 */

#include "utils/BaseUtil.h"
#include "utils/ScopedWin.h"
#include "utils/WinUtil.h"
#include "utils/Timer.h"

#include "wingui/UIModels.h"

#include "Settings.h"
#include "DocController.h"
#include "EngineBase.h"
#include "EngineAll.h"
#include "DisplayModel.h"
#include "GlobalPrefs.h"
#include "RenderCache.h"
#include "TextSelection.h"
#include "Theme.h"
#include "PdfDarkMode.h"

#include "utils/Log.h"

#pragma warning(disable : 28159) // silence /analyze: Consider using 'GetTickCount64' instead of 'GetTickCount'

// TODO: remove this and always conserve memory?
/* Define if you want to conserve memory by always freeing cached bitmaps
   for pages not visible. Disabling this might lead to pages not rendering
   due to insufficient (GDI) memory. */
#define CONSERVE_MEMORY

#if defined(CONSERVE_MEMORY)
bool gConserveMemory = true;
#else
bool gConserveMemory = false;
#endif

static DWORD WINAPI RenderCacheThread(LPVOID data);

static bool FixedPageUiUsesCustomRenderColors() {
    if (!gGlobalPrefs) {
        return false;
    }
    ParsedColor* textCol = GetPrefsColor(gGlobalPrefs->fixedPageUI.textColor);
    if (textCol->parsedOk && (textCol->col & 0xFFFFFF) != (WIN_COL_BLACK & 0xFFFFFF)) {
        return true;
    }
    ParsedColor* bgCol = GetPrefsColor(gGlobalPrefs->fixedPageUI.backgroundColor);
    if (bgCol->parsedOk && (bgCol->col & 0xFFFFFF) != (WIN_COL_WHITE & 0xFFFFFF)) {
        return true;
    }
    return false;
}

static bool FixedPageEngineNeedsBitmapRecolor(EngineBase* engine) {
    if (!engine || engine->IsImageCollection()) {
        return false;
    }
    PdfDocumentColorMode mode = GetPdfDocumentColorMode();
    if (mode == PdfDocumentColorMode::Light) {
        return FixedPageUiUsesCustomRenderColors();
    }
    if (mode == PdfDocumentColorMode::Black) {
        return true;
    }
    // Smart
    if (ThemeUsesDarkChrome()) {
        return true;
    }
    if (ThemeUsesOriginalPageColors()) {
        return FixedPageUiUsesCustomRenderColors();
    }
    // Light-Warm Smart: uniform eye-care remap (no per-image preserve).
    return true;
}

static bool IsFixedPageRecolorEngine(EngineBase* engine) {
    if (!engine || engine->IsImageCollection()) {
        return false;
    }
    if (engine->kind == kindEngineDjVu) {
        return true;
    }
    if (engine->kind != kindEngineMupdf) {
        return false;
    }
    return str::EqI(engine->defaultExt, ".pdf") || str::EqI(engine->defaultExt, ".xps");
}

static bool ShouldUpdateBitmapColors(EngineBase* engine, const DarkModeProfile* profile) {
    if (profile) {
        return DarkModeProfileUsesLegacyPostProcess(profile);
    }
    if (!engine || engine->IsImageCollection()) {
        return false;
    }
    if (engine->kind == kindEngineDjVu) {
        return FixedPageEngineNeedsBitmapRecolor(engine);
    }
    return false;
}

static bool ShouldPreserveImagesInSmartMode(const DarkModeProfile* profile) {
    return profile && profile->mode == PageColorMode::PreserveImages && profile->preservePdfImages;
}

static bool ShouldUpdateBitmapColorsLegacy(EngineBase* engine) {
    if (!IsFixedPageRecolorEngine(engine)) {
        return false;
    }
    if (GetPdfDocumentColorMode() == PdfDocumentColorMode::Light) {
        return FixedPageUiUsesCustomRenderColors();
    }
    if (PdfDarkModeUsesObjectLevel() && GetPdfDocumentColorMode() == PdfDocumentColorMode::Auto) {
        return false;
    }
    return FixedPageEngineNeedsBitmapRecolor(engine);
}

static bool ShouldPreserveImagesLegacy(EngineBase* engine) {
    if (GetPdfDocumentColorMode() != PdfDocumentColorMode::Auto) {
        return false;
    }
    if (!ThemeUsesDarkChrome()) {
        return false;
    }
    if (!GetPreservePdfImagesInDarkMode()) {
        return false;
    }
    return ShouldUpdateBitmapColorsLegacy(engine);
}

// Several preserved regions in one tile → keep the largest artwork, drop layout ornaments.
static void FinalizeTileSkipRects(Vec<Rect>& skipRects, Size bmpSize) {
    if (skipRects.Size() <= 1 || bmpSize.dx <= 0 || bmpSize.dy <= 0) {
        return;
    }
    i64 totalArea = (i64)bmpSize.dx * bmpSize.dy;
    if (totalArea <= 0) {
        return;
    }
    i64 skipArea = 0;
    for (Rect& r : skipRects) {
        skipArea += (i64)r.dx * r.dy;
    }
    if (skipRects.Size() > 1 && skipArea * 100 > totalArea * 40) {
        int bestIdx = 0;
        i64 bestArea = 0;
        for (int i = 0; i < skipRects.Size(); i++) {
            i64 a = (i64)skipRects.at(i).dx * skipRects.at(i).dy;
            if (a > bestArea) {
                bestArea = a;
                bestIdx = i;
            }
        }
        Rect keep = skipRects.at(bestIdx);
        skipRects.Clear();
        skipRects.Append(keep);
    }
}

bool gShowTileLayout = false;
int gMaxRenderThreads = 8;

struct RenderThreadData {
    RenderCache* cache;
    int threadIdx;
};

RenderCache::RenderCache() : maxTileSize({GetSystemMetrics(SM_CXSCREEN), GetSystemMetrics(SM_CYSCREEN)}) {
    // enable when debugging RenderCache logic
    // gEnableDbgLog = true;

    isRemoteSession = GetSystemMetrics(SM_REMOTESESSION);
    textColor = WIN_COL_BLACK;
    backgroundColor = WIN_COL_WHITE;

    InitializeCriticalSection(&cacheAccess);
    InitializeCriticalSection(&requestAccess);

    SYSTEM_INFO si;
    GetSystemInfo(&si);
    int numCores = (int)si.dwNumberOfProcessors;
    maxRenderThreads = std::max(gMaxRenderThreads, numCores);
    if (maxRenderThreads > kMaxRenderThreads) {
        maxRenderThreads = kMaxRenderThreads;
    }

    // use a semaphore so each queued request wakes one thread.
    // threads themselves are spawned lazily in Render() when work appears
    // and no idle thread is available -- many sessions only ever need a
    // couple of render threads, so creating 8+ upfront is wasteful.
    startRendering = CreateSemaphoreW(nullptr, 0, INT_MAX, nullptr);
}

RenderCache::~RenderCache() {
    // Signal threads to exit FIRST, then wait for them WITHOUT holding the
    // critical sections. Workers take requestAccess for their idle bookkeeping,
    // so holding it here would deadlock until the WaitForMultipleObjects
    // timeout fires -- after which DeleteCriticalSection on a still-in-use
    // CS would access-violate.
    AtomicBoolSet(&shouldExit, true);

    if (nRenderThreads > 0) {
        // wake all threads waiting on the semaphore
        ReleaseSemaphore(startRendering, nRenderThreads, nullptr);

        // wait for all threads to finish
        DWORD res = WaitForMultipleObjects((DWORD)nRenderThreads, renderThreads, TRUE, 5000);
        if (res == WAIT_TIMEOUT) {
            logf("RenderCache::~RenderCache: threads didn't exit in 5 seconds\n");
        }

        for (int i = 0; i < nRenderThreads; i++) {
            CloseHandle(renderThreads[i]);
        }
    }
    CloseHandle(startRendering);

    // Threads are gone; remaining state inspection is single-threaded.
    bool hasCurReq = false;
    for (int i = 0; i < nRenderThreads; i++) {
        if (curReqs[i]) {
            hasCurReq = true;
        }
    }
    if (hasCurReq || 0 != requestCount || cacheCount != 0) {
        logvf("RenderCache::~RenderCache: hasCurReq: %d, requestCount: %d, cacheCount: %d\n", (int)hasCurReq,
              requestCount, cacheCount);
        ReportIf(true);
    }

    DeleteCriticalSection(&cacheAccess);
    DeleteCriticalSection(&requestAccess);
}

/* Find a bitmap for a page defined by <dm> and <pageNo> and optionally also
   <rotation> and <zoom> in the cache - call DropCacheEntry when you
   no longer need a found entry. */
BitmapCacheEntry* RenderCache::Find(DisplayModel* dm, int pageNo, int rotation, float zoom, TilePosition* tile) {
    ScopedCritSec scope(&cacheAccess);
    rotation = NormalizeRotation(rotation);
    for (int i = 0; i < cacheCount; i++) {
        BitmapCacheEntry* e = cache[i];
        if ((dm == e->dm) && (pageNo == e->pageNo) && (rotation == e->rotation) &&
            (kInvalidZoom == zoom || zoom == e->zoom) && (!tile || e->tile == *tile) &&
            (e->darkModeEpoch == darkModeEpoch)) {
            e->refs++;
            ReportIf(i != e->cacheIdx);
            return e;
        }
    }
    return nullptr;
}

bool RenderCache::Exists(DisplayModel* dm, int pageNo, int rotation, float zoom, TilePosition* tile) {
    BitmapCacheEntry* entry = Find(dm, pageNo, rotation, zoom, tile);
    if (entry) {
        DropCacheEntry(entry);
    }
    return entry != nullptr;
}

bool RenderCache::DropCacheEntry(BitmapCacheEntry* entry) {
    ScopedCritSec scope(&cacheAccess);
    ReportIf(!entry);
    if (!entry) {
        return false;
    }
    int idx = entry->cacheIdx;
    ReportIf(idx < 0);
    ReportIf(idx >= cacheCount);
    if ((idx < 0) || (idx >= cacheCount)) {
        return false;
    }
    ReportIf(entry->refs <= 0);
    --entry->refs;
    if (entry->refs > 0) {
        return false;
    }
    ReportIf(entry->refs != 0);
    ReportIf(cache[idx] != entry);
    logvf("RenderCache::DropCacheEntry: dm: 0x%p, pageNo: %d, rotation: %d, zoom: %.2f\n", entry->dm, entry->pageNo,
          entry->rotation, entry->zoom);

    delete entry;

    // fast removal by replacing freed item with the item at the end
    cache[idx] = nullptr;
    int lastIdx = cacheCount - 1;
    if ((lastIdx >= 0) && (idx != lastIdx)) {
        cache[idx] = cache[lastIdx];
        cache[idx]->cacheIdx = idx;
        cache[lastIdx] = nullptr;
    }
    cacheCount--;
    ReportIf(cacheCount < 0);

    // LogCacheSize();
    return true;
}

bool RenderCache::DropCacheEntryIfNotUsed(BitmapCacheEntry* entry) {
    ScopedCritSec scope(&cacheAccess);
    if (!entry || entry->refs > 1) {
        return false;
    }
    return DropCacheEntry(entry);
}

static bool FreeIfFull(RenderCache* rc, const PageRenderRequest& req) {
    int n = rc->cacheCount;
    if (n < MAX_BITMAPS_CACHED) {
        return true;
    }

    DisplayModel* dm = req.dm;
    // free an invisible page of the same DisplayModel ...
    for (int i = 0; i < n; i++) {
        auto entry = rc->cache[i];
        if (entry->dm == dm && !dm->PageVisibleNearby(entry->pageNo)) {
            bool didDrop = rc->DropCacheEntryIfNotUsed(entry);
            if (didDrop) {
                return true;
            }
        }
    }

    // ... or just the oldest cached page
    for (int i = 0; i < n; i++) {
        auto entry = rc->cache[i];
        if (entry->dm == dm) {
            // don't free pages from the document we're currently displaying
            // as it leads to flicker
            // TODO: it can still flicker if the dm is from a visible tab
            // in a different window, but it's harder to detect
            continue;
        }
        bool didDrop = rc->DropCacheEntryIfNotUsed(entry);
        if (didDrop) {
            return true;
        }
    }
    return false;
}

void RenderCache::Add(PageRenderRequest& req, RenderedBitmap* bmp) {
    ScopedCritSec scope(&cacheAccess);
    ReportIf(!req.dm);

    req.rotation = NormalizeRotation(req.rotation);
    ReportIf(cacheCount > MAX_BITMAPS_CACHED);

    /* It's possible there still is a cached bitmap with different zoom/rotation */
    FreePage(req.dm, req.pageNo, &req.tile);

    bool hasSpace = FreeIfFull(this, req);
    ReportIf(!hasSpace); // TODO: FreeIfFull() might actually fail to free
    ReportIf(cacheCount > MAX_BITMAPS_CACHED);

    // Copy the PageRenderRequest as it will be reused
    auto entry = new BitmapCacheEntry(req.dm, req.pageNo, req.rotation, req.zoom, req.tile, bmp);
    entry->darkModeEpoch = darkModeEpoch;
    entry->cacheIdx = cacheCount;
    cache[cacheCount] = entry;
    cacheCount++;

    // LogCacheSize();
}

static RectF GetTileRect(RectF pagerect, TilePosition tile) {
    ReportIf(tile.res > 30);
    RectF rect;
    rect.dx = pagerect.dx / (1ULL << tile.res);
    rect.dy = pagerect.dy / (1ULL << tile.res);
    rect.x = pagerect.x + tile.col * rect.dx;
    rect.y = pagerect.y + ((1ULL << tile.res) - tile.row - 1) * rect.dy;
    return rect;
}

// get the coordinates of a specific tile
static Rect GetTileRectDevice(EngineBase* engine, int pageNo, int rotation, float zoom, TilePosition tile) {
    RectF mediabox = engine->PageMediabox(pageNo);
    if (tile.res > 0 && tile.res != INVALID_TILE_RES) {
        mediabox = GetTileRect(mediabox, tile);
    }
    RectF pixelbox = engine->Transform(mediabox, pageNo, zoom, rotation);
    return pixelbox.Round();
}

static RectF GetTileRectUser(EngineBase* engine, int pageNo, int rotation, float zoom, TilePosition tile) {
    Rect pixelbox = GetTileRectDevice(engine, pageNo, rotation, zoom, tile);
    return engine->Transform(ToRectF(pixelbox), pageNo, zoom, rotation, true);
}

static Rect GetTileOnScreen(EngineBase* engine, int pageNo, int rotation, float zoom, TilePosition tile,
                            Rect pageOnScreen) {
    Rect bbox = GetTileRectDevice(engine, pageNo, rotation, zoom, tile);
    bbox.Offset(pageOnScreen.x, pageOnScreen.y);
    return bbox;
}

static bool IsTileVisible(DisplayModel* dm, int pageNo, TilePosition tile, float fuzz = 0) {
    if (!dm) {
        return false;
    }
    PageInfo* pageInfo = dm->GetPageInfo(pageNo);
    EngineBase* engine = dm->GetEngine();
    if (!engine || !pageInfo) {
        return false;
    }
    int rotation = dm->GetRotation();
    float zoom = dm->GetZoomSafe(pageNo);
    Rect r = pageInfo->pageOnScreen;
    Rect tileOnScreen = GetTileOnScreen(engine, pageNo, rotation, zoom, tile, r);
    // consider nearby tiles visible depending on the fuzz factor
    tileOnScreen.x -= (int)(tileOnScreen.dx * fuzz * 0.5);
    tileOnScreen.dx = (int)(tileOnScreen.dx * (fuzz + 1));
    tileOnScreen.y -= (int)(tileOnScreen.dy * fuzz * 0.5);
    tileOnScreen.dy = (int)(tileOnScreen.dy * (fuzz + 1));
    Rect screen(Point(), dm->GetViewPort().Size());
    return !tileOnScreen.Intersect(screen).IsEmpty();
}

/* Free all bitmaps in the cache that are of a specific page (or all pages
   of the given DisplayModel, or even all invisible pages). */
void RenderCache::FreePage(DisplayModel* dm, int pageNo, TilePosition* tile) {
    logvf("RenderCache::FreePage: dm: 0x%p, pageNo: %d\n", dm, pageNo);
    ReportIf(!dm || (pageNo == kInvalidPageNo));
    if (!dm || (pageNo == kInvalidPageNo)) {
        return;
    }
    ScopedCritSec scope(&cacheAccess);

    // must go from end becaues freeing changes the cache
    for (int i = cacheCount - 1; i >= 0; i--) {
        BitmapCacheEntry* entry = cache[i];
        bool shouldFree = (entry->dm == dm) && (entry->pageNo == pageNo);
        if (shouldFree && tile) {
            // a given tile of the page or all tiles not rendered at a given resolution
            // (and at resolution 0 for quick zoom previews)
            shouldFree = (entry->tile == *tile ||
                          tile->row == (USHORT)-1 && entry->tile.res > 0 && entry->tile.res != tile->res ||
                          tile->row == (USHORT)-1 && entry->tile.res == 0 && entry->outOfDate);
        }
        if (shouldFree) {
            DropCacheEntryIfNotUsed(entry);
        }
    }
}

void RenderCache::FreeForDisplayModel(DisplayModel* dm) {
    logvf("RenderCache::FreeForDisplayModel: dm: 0x%p\n", dm);
    ScopedCritSec scope(&cacheAccess);
    // must go from end becaues freeing changes the cache
    for (int i = cacheCount - 1; i >= 0; i--) {
        BitmapCacheEntry* entry = cache[i];
        if (entry->dm == dm) {
            DropCacheEntryIfNotUsed(entry);
        }
    }
}

// Keep old tiles visible while replacements for a color-mode change render.
// Their invalid zoom makes normal lookup miss them and queue a fresh render;
// PaintTile() then uses them as the existing stale-preview path.
void RenderCache::KeepForColorTransition(DisplayModel* dm) {
    ScopedCritSec scope(&cacheAccess);
    for (int i = 0; i < cacheCount; i++) {
        BitmapCacheEntry* entry = cache[i];
        if (entry->dm != dm) {
            continue;
        }
        entry->darkModeEpoch = darkModeEpoch;
        entry->zoom = kInvalidZoom;
        entry->outOfDate = true;
    }
}

void RenderCache::FreeNotVisible() {
    // logvf("RenderCache::FreeNotVisible\n");
    ScopedCritSec scope(&cacheAccess);
    // must go from end becaues freeing changes the cache
    for (int i = cacheCount - 1; i >= 0; i--) {
        BitmapCacheEntry* entry = cache[i];
        // all invisible pages resp. page tiles
        bool shouldFree = !entry->dm->PageVisibleNearby(entry->pageNo);
        if (!shouldFree && entry->tile.res > 1) {
            shouldFree = !IsTileVisible(entry->dm, entry->pageNo, entry->tile, 2.0);
        }
        if (shouldFree) {
            DropCacheEntryIfNotUsed(entry);
        }
    }
}

// keep the cached bitmaps for visible pages to avoid flickering during a reload.
// mark invisible pages as out-of-date to prevent inconsistencies
void RenderCache::KeepForDisplayModel(DisplayModel* oldDm, DisplayModel* newDm) {
    ScopedCritSec scope(&cacheAccess);
    for (int i = 0; i < cacheCount; i++) {
        BitmapCacheEntry* entry = cache[i];
        if (entry->dm != oldDm) {
            continue;
        }
        if (oldDm->PageVisible(entry->pageNo)) {
            entry->dm = newDm;
        }
        // make sure that the page is rerendered eventually
        entry->zoom = kInvalidZoom;
        entry->outOfDate = true;
    }
}

// marks all tiles containing rect of pageNo as out of date
void RenderCache::Invalidate(DisplayModel* dm, int pageNo, RectF rect) {
    ScopedCritSec scopeReq(&requestAccess);

    ClearQueueForDisplayModel(dm, pageNo);
    for (int i = 0; i < nRenderThreads; i++) {
        if (curReqs[i] && curReqs[i]->dm == dm && curReqs[i]->pageNo == pageNo) {
            AbortCurrentRequest(i);
        }
    }

    ScopedCritSec scopeCache(&cacheAccess);

    RectF mediabox = dm->GetEngine()->PageMediabox(pageNo);
    for (int i = 0; i < cacheCount; i++) {
        auto e = cache[i];
        if (e->dm == dm && e->pageNo == pageNo && !GetTileRect(mediabox, e->tile).Intersect(rect).IsEmpty()) {
            e->zoom = kInvalidZoom;
            e->outOfDate = true;
        }
    }
}

// determine the count of tiles required for a page at a given zoom level
USHORT RenderCache::GetTileRes(DisplayModel* dm, int pageNo) const {
    auto engine = dm->GetEngine();
    RectF mediabox = engine->PageMediabox(pageNo);
    float zoom = dm->GetZoomSafe(pageNo);
    float zoomVirt = dm->GetZoomVirtual();
    Rect viewPort = dm->GetViewPort();
    int rotation = dm->GetRotation();
    RectF pixelbox = engine->Transform(mediabox, pageNo, zoom, rotation);

    float factorW = (float)pixelbox.dx / (maxTileSize.dx + 1);
    float factorH = (float)pixelbox.dy / (maxTileSize.dy + 1);
    // using the geometric mean instead of the maximum factor
    // so that the tile area doesn't get too small in comparison
    // to maxTileSize (but remains smaller)
    float factorAvg = sqrtf(factorW * factorH);

    // use larger tiles when fitting page or width or when a page is smaller
    // than the visible canvas width/height or when rendering pages
    // without clipping optimizations
    if (zoomVirt == kZoomFitPage || zoomVirt == kZoomFitWidth || pixelbox.dx <= viewPort.dx ||
        pixelbox.dy < viewPort.dy || !engine->HasClipOptimizations(pageNo)) {
        factorAvg /= 2.0;
    }

    USHORT res = 0;
    if (factorAvg > 1.5) {
        res = (USHORT)ceilf(log(factorAvg) / log(2.0f));
    }
    // limit res to 30, so that (1 << res) doesn't overflow for 32-bit signed int
    return std::min(res, (USHORT)30);
}

// get the maximum resolution available for the given page
USHORT RenderCache::GetMaxTileRes(DisplayModel* dm, int pageNo, int rotation) {
    ScopedCritSec scope(&cacheAccess);
    USHORT maxRes = 0;
    for (int i = 0; i < cacheCount; i++) {
        auto e = cache[i];
        if (e->dm == dm && e->pageNo == pageNo && e->rotation == rotation) {
            maxRes = std::max(e->tile.res, maxRes);
        }
    }
    return maxRes;
}

// reduce the size of tiles in order to hopefully use less memory overall
bool RenderCache::ReduceTileSize() {
    logvf("RenderCache::ReduceTileSize: reducing tile size (current: %d x %d)\n", maxTileSize.dx, maxTileSize.dy);
    if (maxTileSize.dx < 200 || maxTileSize.dy < 200) {
        return false;
    }

    ScopedCritSec scope1(&requestAccess);
    ScopedCritSec scope2(&cacheAccess);

    if (maxTileSize.dx > maxTileSize.dy) {
        maxTileSize.dx /= 2;
    } else {
        maxTileSize.dy /= 2;
    }

    // invalidate all rendered bitmaps and all requests
    while (cacheCount > 0) {
        FreeForDisplayModel(cache[0]->dm);
    }
    while (requestCount > 0) {
        ClearQueueForDisplayModel(requests[0].dm);
    }
    for (int i = 0; i < nRenderThreads; i++) {
        AbortCurrentRequest(i);
    }

    return true;
}

void RenderCache::RequestRendering(DisplayModel* dm, int pageNo) {
    TilePosition tile(GetTileRes(dm, pageNo), 0, 0);
    // only honor the request if there's a good chance that the
    // rendered tile will actually be used
    if (tile.res > 1) {
        return;
    }

    RequestRendering(dm, pageNo, tile);
    // render both tiles of the first row when splitting a page in four
    // (which always happens on larger displays for Fit Width)
    if (tile.res == 1 && !IsRenderQueueFull()) {
        tile.col = 1;
        RequestRendering(dm, pageNo, tile, false);
    }
}

/* Render a bitmap for page <pageNo> in <dm>. */
void RenderCache::RequestRendering(DisplayModel* dm, int pageNo, TilePosition tile, bool clearQueueForPage) {
    // logvf("RenderCache::RequestRendering: pageNo %d\n", pageNo);
    ScopedCritSec scope(&requestAccess);
    ReportIf(!dm);
    if (!dm || dm->pauseRendering) {
        return;
    }

    int rotation = NormalizeRotation(dm->GetRotation());
    float zoom = dm->GetZoomSafe(pageNo);

    for (int i = 0; i < nRenderThreads; i++) {
        auto* cr = curReqs[i];
        if (cr && (cr->pageNo == pageNo) && (cr->dm == dm) && (cr->tile == tile)) {
            if ((cr->zoom == zoom) && (cr->rotation == rotation) && !cr->abort) {
                /* we're already rendering exactly the same page */
                return;
            }
            // A matching request can still be in curReqs after
            // CancelRendering() has marked it aborted. It will never publish a
            // bitmap or completion callback, so don't let it suppress the
            // replacement request for the new theme.
            if (!cr->abort) {
                /* Currently rendered page is for the same page but with different zoom
                or rotation, so abort it */
                AbortCurrentRequest(i);
            }
        }
    }

    // clear requests for tiles of different resolution and invisible tiles
    if (clearQueueForPage) {
        ClearQueueForDisplayModel(dm, pageNo, &tile);
    }

    for (int i = 0; i < requestCount; i++) {
        PageRenderRequest* req = &(requests[i]);
        if ((req->pageNo == pageNo) && (req->dm == dm) && (req->tile == tile)) {
            if ((req->zoom == zoom) && (req->rotation == rotation)) {
                /* Request with exactly the same parameters already queued for
                   rendering. Move it to the top of the queue so that it'll
                   be rendered faster. */
                PageRenderRequest tmp;
                tmp = requests[requestCount - 1];
                requests[requestCount - 1] = *req;
                *req = tmp;
            } else {
                /* There was a request queued for the same page but with different
                   zoom or rotation, so only replace this request */
                req->zoom = zoom;
                req->rotation = rotation;
            }
            return;
        }
    }

    if (Exists(dm, pageNo, rotation, zoom, &tile)) {
        /* This page has already been rendered in the correct dimensions
           and isn't about to be rerendered in different dimensions */
        return;
    }

    auto cb = MkMethod1<DisplayModel, PageRenderRequest*, &DisplayModel::RenderFinishedAsync>(dm);
    Render(dm, pageNo, rotation, zoom, &tile, nullptr, cb);
}

void RenderCache::Render(DisplayModel* dm, int pageNo, int rotation, float zoom, RectF pageRect,
                         const Func1<PageRenderRequest*>& callback) {
    bool ok = Render(dm, pageNo, rotation, zoom, nullptr, &pageRect, callback);
    if (!ok) {
        // create a dummy request to notify callback of failure
        PageRenderRequest req;
        req.dm = dm;
        req.pageNo = pageNo;
        req.bmp = nullptr;
        req.errorCode = 1;
        callback.Call(&req);
    }
}

bool RenderCache::Render(DisplayModel* dm, int pageNo, int rotation, float zoom, TilePosition* tile, RectF* pageRect,
                         const Func1<PageRenderRequest*>& renderFinishedCb) {
    logvf("RenderCache::Render: pageNo %d\n", pageNo);
    ReportIf(!dm);
    if (!dm || dm->pauseRendering) {
        return false;
    }
    ReportIf(!renderFinishedCb.IsValid());

    ReportIf(!(tile || pageRect));
    if (!tile && !pageRect) {
        return false;
    }

    ScopedCritSec scope(&requestAccess);
    PageRenderRequest* newRequest;

    /* add request to the queue */
    if (requestCount == MAX_PAGE_REQUESTS) {
        /* queue is full -> remove the oldest items on the queue */
        if (requests[0].renderFinishedCb.IsValid()) {
            requests[0].abort = true;
            requests[0].bmp = nullptr;
            requests[0].errorCode = 0;
            requests[0].renderFinishedCb.Call(&requests[0]);
        }
        memmove(&(requests[0]), &(requests[1]), sizeof(PageRenderRequest) * (MAX_PAGE_REQUESTS - 1));
        newRequest = &(requests[MAX_PAGE_REQUESTS - 1]);
    } else {
        newRequest = &(requests[requestCount]);
        requestCount++;
    }
    ReportIf(requestCount > MAX_PAGE_REQUESTS);

    newRequest->dm = dm;
    newRequest->pageNo = pageNo;
    newRequest->rotation = rotation;
    newRequest->zoom = zoom;
    if (tile) {
        newRequest->pageRect = GetTileRectUser(dm->GetEngine(), pageNo, rotation, zoom, *tile);
        newRequest->tile = *tile;
    } else if (pageRect) {
        newRequest->pageRect = *pageRect;
    } else {
        CrashMe();
    }
    newRequest->abort = false;
    newRequest->abortCookie = nullptr;
    newRequest->timestamp = GetTickCount();
    newRequest->bmp = nullptr;
    newRequest->errorCode = 0;
    newRequest->renderFinishedCb = renderFinishedCb;

    ReleaseSemaphore(startRendering, 1, nullptr);

    // Lazy thread spawn: if no thread is currently waiting and we're below
    // the cap, start a new one. Existing busy threads will pick up the work
    // when they finish their current task.
    if (idleThreads == 0 && nRenderThreads < maxRenderThreads) {
        int idx = nRenderThreads;
        auto* td = new RenderThreadData{this, idx};
        renderThreads[idx] = CreateThread(nullptr, 0, RenderCacheThread, td, 0, nullptr);
        if (renderThreads[idx]) {
            nRenderThreads++;
        } else {
            delete td;
        }
    }

    return true;
}

int RenderCache::GetRenderDelay(DisplayModel* dm, int pageNo, TilePosition tile) {
    ScopedCritSec scope(&requestAccess);

    for (int i = 0; i < nRenderThreads; i++) {
        auto* cr = curReqs[i];
        if (cr && cr->pageNo == pageNo && cr->dm == dm && cr->tile == tile) {
            return GetTickCount() - cr->timestamp;
        }
    }

    for (int i = 0; i < requestCount; i++) {
        if (requests[i].pageNo == pageNo && requests[i].dm == dm && requests[i].tile == tile) {
            return GetTickCount() - requests[i].timestamp;
        }
    }

    return RENDER_DELAY_UNDEFINED;
}

bool RenderCache::GetNextRequest(PageRenderRequest* req, int threadIdx) {
    ScopedCritSec scope(&requestAccess);

    if (requestCount == 0) {
        return false;
    }

    ReportIf(requestCount < 0);
    ReportIf(requestCount > MAX_PAGE_REQUESTS);
    requestCount--;
    *req = requests[requestCount];
    req->darkModeEpoch = darkModeEpoch;
    curReqs[threadIdx] = req;
    ReportIf(requestCount < 0);
    ReportIf(req->abort);

    return true;
}

bool RenderCache::ClearCurrentRequest(int threadIdx) {
    ScopedCritSec scope(&requestAccess);
    if (curReqs[threadIdx]) {
        delete curReqs[threadIdx]->abortCookie;
    }
    curReqs[threadIdx] = nullptr;

    bool isQueueEmpty = requestCount == 0;
    return isQueueEmpty;
}

// Abort queued and in-flight renders for <dm>. Does not block the UI thread;
// the render thread drops stale results when abort is set or darkModeEpoch changes.
void RenderCache::CancelRendering(DisplayModel* dm) {
    ClearQueueForDisplayModel(dm);

    ScopedCritSec scope(&requestAccess);
    for (int i = 0; i < nRenderThreads; i++) {
        if (curReqs[i] && curReqs[i]->dm == dm) {
            AbortCurrentRequest(i);
        }
    }
}

void RenderCache::WaitForRenderingComplete(DisplayModel* dm) {
    if (!dm) {
        return;
    }
    CancelRendering(dm);

    const DWORD timeoutMs = 10000;
    DWORD start = GetTickCount();
    for (;;) {
        bool busy = false;
        {
            ScopedCritSec scope(&requestAccess);
            for (int i = 0; i < nRenderThreads; i++) {
                if (curReqs[i] && curReqs[i]->dm == dm) {
                    busy = true;
                    break;
                }
            }
        }
        if (!busy) {
            return;
        }
        if (GetTickCount() - start > timeoutMs) {
            logf("WaitForRenderingComplete: timed out for dm 0x%p\n", dm);
            CancelRendering(dm);
            return;
        }
        Sleep(1);
    }
}

void RenderCache::ClearQueueForDisplayModel(DisplayModel* dm, int pageNo, TilePosition* tile) {
    ScopedCritSec scope(&requestAccess);
    int reqCount = requestCount;
    int curPos = 0;
    for (int i = 0; i < reqCount; i++) {
        PageRenderRequest* req = &(requests[i]);
        bool shouldRemove = req->dm == dm && (pageNo == kInvalidPageNo || req->pageNo == pageNo) &&
                            (!tile || req->tile.res != tile->res || !IsTileVisible(dm, req->pageNo, *tile, 0.5));
        if (i != curPos) {
            requests[curPos] = requests[i];
        }
        if (shouldRemove) {
            // don't call renderFinishedCb for cleared requests - treat as aborted
            requestCount--;
        } else {
            curPos++;
        }
    }
}

void RenderCache::AbortCurrentRequest(int threadIdx) {
    ScopedCritSec scope(&requestAccess);
    auto* cr = curReqs[threadIdx];
    if (!cr) {
        return;
    }
    if (cr->abortCookie) {
        cr->abortCookie->Abort();
    }
    cr->abort = true;
}

static DWORD WINAPI RenderCacheThread(LPVOID data) {
    auto* td = (RenderThreadData*)data;
    RenderCache* cache = td->cache;
    int threadIdx = td->threadIdx;
    delete td;

    PageRenderRequest req;
    RenderedBitmap* bmp;

    for (;;) {
        if (AtomicBoolGet(&cache->shouldExit)) {
            break;
        }
        if (cache->ClearCurrentRequest(threadIdx)) {
            // Mark ourselves idle so Render() knows whether to spawn a new
            // thread when work appears. Increment before waiting, decrement
            // after waking (whether due to new work or shutdown).
            {
                ScopedCritSec scope(&cache->requestAccess);
                cache->idleThreads++;
            }
            DWORD waitResult = WaitForSingleObject(cache->startRendering, INFINITE);
            {
                ScopedCritSec scope(&cache->requestAccess);
                cache->idleThreads--;
            }
            if (AtomicBoolGet(&cache->shouldExit)) {
                break;
            }
            // Is it not a page render request?
            if (WAIT_OBJECT_0 != waitResult) {
                continue;
            }
        }

        if (!cache->GetNextRequest(&req, threadIdx)) {
            continue;
        }

        if (!req.dm->PageVisibleNearby(req.pageNo) && !req.renderFinishedCb.IsValid()) {
            continue;
        }

        if (req.dm->pauseRendering) {
            // aborted due to pause - do nothing
            continue;
        }

        ReportIf(req.abortCookie != nullptr);
        EngineBase* engine = req.dm->GetEngine();

        RenderPageArgs args(req.pageNo, req.zoom, req.rotation, &req.pageRect, RenderTarget::View, &req.abortCookie);
        DarkModeProfile darkProfile;
        BuildViewDarkModeProfile(engine, &darkProfile);
        if (darkProfile.mode != PageColorMode::Normal) {
            args.darkProfile = &darkProfile;
        }
        auto timeStart = TimeGet();
        bmp = engine->RenderPage(args);
        if (req.abort || req.darkModeEpoch != cache->darkModeEpoch) {
            delete bmp;
            continue;
        }
        auto durMs = TimeSinceInMs(timeStart);
        if (durMs > 100) {
            auto path = engine->FilePath();
            logfa("Slow rendering: %.2f ms, page: %d in '%s'\n", (float)durMs, req.pageNo, path);
        }

        req.bmp = bmp;
        req.errorCode = bmp ? 0 : 1;

        if (bmp) {
            if (req.abort || req.darkModeEpoch != cache->darkModeEpoch) {
                delete bmp;
                continue;
            }
            const DarkModeProfile* profile = args.darkProfile;
            bool legacyPost = false;
            if (engine->kind == kindEngineDjVu && ThemeUsesDarkChrome()) {
                legacyPost = true;
                profile = nullptr;
            } else if (profile) {
                legacyPost = ShouldUpdateBitmapColors(engine, profile);
            } else {
                legacyPost = ShouldUpdateBitmapColorsLegacy(engine);
            }
            if (legacyPost) {
                bool preserve = profile ? ShouldPreserveImagesInSmartMode(profile) : ShouldPreserveImagesLegacy(engine);
                Vec<Rect> skipRects;
                Vec<Rect>* skipRectsPtr = nullptr;
                if (preserve) {
                    Size bmpSize = bmp->GetSize();
                    engine->GetBitmapRecolorSkipRects(req.pageNo, req.zoom, req.rotation, req.pageRect, bmpSize,
                                                      skipRects);
                    FinalizeTileSkipRects(skipRects, bmpSize);
                    if (skipRects.Size() > 0) {
                        skipRectsPtr = &skipRects;
                    }
                }
                COLORREF textCol = profile ? profile->foreground : cache->textColor;
                COLORREF bgCol = profile ? profile->pageBackground : cache->backgroundColor;
                COLORREF linkCol = profile ? profile->linkColor : cache->linkColor;
                UpdateBitmapColors(bmp->GetBitmap(), textCol, bgCol, linkCol, skipRectsPtr);
            }
            cache->Add(req, bmp);
            req.bmp = nullptr; // ownership transferred to cache
        }

        ReportIf(!req.renderFinishedCb.IsValid());
        req.renderFinishedCb.Call(&req);
        ResetTempAllocator();
    }
    logf("RenderCacheThread: exiting\n");
    DestroyTempAllocator();
    return 0;
}

bool RenderCache::PageNeedsMarkupOverlay(DisplayModel* dm, int pageNo) {
    ScopedCritSec scope(&cacheAccess);
    int rotation = dm->GetRotation();
    float zoom = dm->GetZoomSafe(pageNo);
    USHORT targetRes = GetTileRes(dm, pageNo);

    bool anyTargetTile = false;
    for (int i = 0; i < cacheCount; i++) {
        BitmapCacheEntry* e = cache[i];
        if (e->dm != dm || e->pageNo != pageNo || e->rotation != rotation || e->tile.res != targetRes) {
            continue;
        }
        if (e->zoom != zoom) {
            continue;
        }
        anyTargetTile = true;
        if (e->outOfDate) {
            return true;
        }
    }
    return !anyTargetTile;
}

// TODO: conceptually, RenderCache is not the right place for code that paints
//       (this is the only place that knows about Tiles, though)
int RenderCache::PaintTile(HDC hdc, Rect bounds, DisplayModel* dm, int pageNo, TilePosition tile, Rect tileOnScreen,
                           bool renderMissing, bool* renderOutOfDateCue, bool* renderedReplacement) {
    float zoom = dm->GetZoomSafe(pageNo);
    BitmapCacheEntry* entry = Find(dm, pageNo, dm->GetRotation(), zoom, &tile);
    int renderDelay = 0;

    if (!entry) {
        if (!isRemoteSession) {
            BitmapCacheEntry* stale = Find(dm, pageNo, dm->GetRotation(), kInvalidZoom, &tile);
            if (stale && stale->darkModeEpoch == darkModeEpoch) {
                entry = stale;
                if (renderedReplacement) {
                    *renderedReplacement = true;
                }
            } else if (stale) {
                DropCacheEntry(stale);
            }
        }
        renderDelay = GetRenderDelay(dm, pageNo, tile);
        // A color-transition tile can paint an old bitmap while the request
        // that was meant to replace it was canceled by a subsequent redraw.
        // Re-submit here; RequestRendering() coalesces duplicates, whereas
        // waiting for an undefined delay leaves the old colors on screen until
        // a scroll happens to queue the page again.
        if (renderMissing && !IsRenderQueueFull()) {
            RequestRendering(dm, pageNo, tile);
        }
    }
    RenderedBitmap* renderedBmp = entry ? entry->bitmap : nullptr;
    HBITMAP hbmp = renderedBmp ? renderedBmp->GetBitmap() : nullptr;

    if (!hbmp) {
        if (entry && !(renderedBmp && ReduceTileSize())) {
            renderDelay = RENDER_DELAY_FAILED;
        } else if (0 == renderDelay) {
            renderDelay = 1;
        }

        if (entry) {
            DropCacheEntry(entry);
        }
        return renderDelay;
    }

    HDC bmpDC = CreateCompatibleDC(hdc);
    if (bmpDC) {
        Size bmpSize = renderedBmp->GetSize();
        int xSrc = -std::min(tileOnScreen.x, 0);
        int ySrc = -std::min(tileOnScreen.y, 0);
        float factor = std::min(1.0f * bmpSize.dx / tileOnScreen.dx, 1.0f * bmpSize.dy / tileOnScreen.dy);

        HGDIOBJ prevBmp = SelectObject(bmpDC, hbmp);
        int xDst = bounds.x;
        int yDst = bounds.y;
        int dxDst = bounds.dx;
        int dyDst = bounds.dy;
        if (factor != 1.0f) {
            xSrc = (int)(xSrc * factor);
            ySrc = (int)(ySrc * factor);
            int dxSrc = (int)(bounds.dx * factor);
            int dySrc = (int)(bounds.dy * factor);
            StretchBlt(hdc, xDst, yDst, dxDst, dyDst, bmpDC, xSrc, ySrc, dxSrc, dySrc, SRCCOPY);
        } else {
            BitBlt(hdc, xDst, yDst, dxDst, dyDst, bmpDC, xSrc, ySrc, SRCCOPY);
        }

        SelectObject(bmpDC, prevBmp);
        DeleteDC(bmpDC);

        if (gShowTileLayout) {
            HPEN pen = CreatePen(PS_SOLID, 1, RGB(0xff, 0xff, 0x00));
            HGDIOBJ oldPen = SelectObject(hdc, pen);
            DrawRect(hdc, bounds);
            DeletePen(SelectObject(hdc, oldPen));
        }
    }

    if (entry->outOfDate) {
        if (renderOutOfDateCue) {
            *renderOutOfDateCue = true;
        }
        ReportIf(renderedReplacement && !*renderedReplacement);
    }

    DropCacheEntry(entry);
    return 0;
}

static int cmpTilePosition(const void* a, const void* b) {
    const TilePosition *ta = (const TilePosition*)a, *tb = (const TilePosition*)b;
    return ta->res != tb->res ? ta->res - tb->res : ta->row != tb->row ? ta->row - tb->row : ta->col - tb->col;
}

int RenderCache::Paint(HDC hdc, Rect bounds, DisplayModel* dm, int pageNo, PageInfo* pi, bool* renderOutOfDateCue) {
    ReportIf(!pi->isShown || 0.0 == pi->visibleRatio);

#if 0
    auto timeStart = TimeGet();
    defer {
        auto dur = TimeSinceInMs(timeStart);
        logvf("RenderCache::Paint() pageNo: %d, bounds={%d,%d,%d,%d} in %.2f ms\n", pageNo, bounds.x, bounds.y, bounds.dx,
             bounds.dy, dur);
    };
#endif

    if (!dm->ShouldCacheRendering(pageNo)) {
        int rotation = dm->GetRotation();
        float zoom = dm->GetZoomSafe(pageNo);
        bounds = pi->pageOnScreen.Intersect(bounds);

        RectF area = ToRectF(bounds);
        area.Offset(-pi->pageOnScreen.x, -pi->pageOnScreen.y);
        area = dm->GetEngine()->Transform(area, pageNo, zoom, rotation, true);

        RenderPageArgs args(pageNo, zoom, rotation, &area);
        RenderedBitmap* bmp = dm->GetEngine()->RenderPage(args);
        bool success = bmp && bmp->IsValid() && bmp->Blit(hdc, bounds);
        delete bmp;

        return success ? 0 : RENDER_DELAY_FAILED;
    }

    int rotation = dm->GetRotation();
    float zoom = dm->GetZoomSafe(pageNo);
    USHORT targetRes = GetTileRes(dm, pageNo);
    USHORT maxRes = GetMaxTileRes(dm, pageNo, rotation);
    if (maxRes < targetRes) {
        maxRes = targetRes;
    }

    Vec<TilePosition> queue;
    queue.Append(TilePosition(0, 0, 0));
    int renderDelayMin = RENDER_DELAY_UNDEFINED;
    bool neededScaling = false;

    while (queue.size() > 0) {
        TilePosition tile = queue.PopAt(0);
        Rect tileOnScreen = GetTileOnScreen(dm->GetEngine(), pageNo, rotation, zoom, tile, pi->pageOnScreen);
        if (tileOnScreen.IsEmpty()) {
            // display an error message when only empty tiles should be drawn (i.e. on page loading errors)
            renderDelayMin = std::min(RENDER_DELAY_FAILED, renderDelayMin);
            continue;
        }
        tileOnScreen = pi->pageOnScreen.Intersect(tileOnScreen);
        Rect isect = bounds.Intersect(tileOnScreen);
        if (isect.IsEmpty()) {
            continue;
        }

        bool isTargetRes = tile.res == targetRes;
        int renderDelay = PaintTile(hdc, isect, dm, pageNo, tile, tileOnScreen, isTargetRes, renderOutOfDateCue,
                                    isTargetRes ? &neededScaling : nullptr);
        if (!(isTargetRes && 0 == renderDelay) && tile.res < maxRes) {
            queue.Append(TilePosition(tile.res + 1, tile.row * 2, tile.col * 2));
            queue.Append(TilePosition(tile.res + 1, tile.row * 2, tile.col * 2 + 1));
            queue.Append(TilePosition(tile.res + 1, tile.row * 2 + 1, tile.col * 2));
            queue.Append(TilePosition(tile.res + 1, tile.row * 2 + 1, tile.col * 2 + 1));
        }
        if (isTargetRes && renderDelay != 0) {
            neededScaling = true;
        }
        if (renderDelay == RENDER_DELAY_FAILED || renderDelayMin == RENDER_DELAY_FAILED) {
            renderDelayMin = RENDER_DELAY_FAILED;
        } else {
            renderDelayMin = std::min(renderDelay, renderDelayMin);
        }
        // paint tiles from left to right from top to bottom
        if (tile.res > 0 && queue.size() > 0 && tile.res < queue.at(0).res) {
            queue.Sort(cmpTilePosition);
        }
    }

    if (gConserveMemory) {
        if (!neededScaling) {
            if (renderOutOfDateCue) {
                *renderOutOfDateCue = false;
            }
            // free tiles with different resolution
            TilePosition tile(targetRes, (USHORT)-1, 0);
            logvf("RenderCache::Paint: calling FreePage() pageNo: %d\n", pageNo);
            FreePage(dm, pageNo, &tile);
        }
        FreeNotVisible();
    }

    return renderDelayMin;
}

void RenderCache::LogCacheSize() {
    ScopedCritSec scope(&cacheAccess);
    i64 size = 0;
    for (int i = 0; i < cacheCount; i++) {
        BitmapCacheEntry* e = cache[i];
        if (e->bitmap) {
            i64 bs = BlittableBitmapByteSize(e->bitmap);
            size += bs;
        }
    }
    logValueSize("bitmapCache", size);
}
