texture_cache: back large sparse 2D images by sparse block

Mario Kart World's nine world-sized masks (R8 16384x16384, RG16 and
R16 8192x8192, 170-341 MB each) live in sparse regions the game maps
its own memory into, a few MiB of each. Since a mapped tile counts as
written, the texture cache backed and uploaded each mask in full: about
2.9 GB of device memory, and a whole-mask upload for every tile the
game streamed in.

Such images (single layer, one texel per block, colour, in a sparse
region, 32 MiB or more) are now unbacked SparseTiles images. The
texture cache records the guest ranges written to them; Image::BindTiles
gives the host sparse blocks under those ranges memory, and only those
rectangles are unswizzled, a row of whole GOB blocks at a time, and
uploaded. A new image starts with the tiles the game maps there (nx2:gpu
216 now records them per 64 KiB), or the written blocks where it maps
none. Unmapped tiles keep their blocks and are loaded as zeros.

Checked against the full unswizzle on 400 ordinary game images (row
padding, mip chains, odd sizes): no row differs. Not on AMD drivers,
which cannot sample images with unbound memory.

Mario Kart World title screen, 150 s, against backing the masks whole:
dedicated VRAM 6.6 -> 6.2 GB, shared 1.0 -> 0.3 GB, peak 8.2 -> 6.9 GB.

1 files changed, 204 insertions, 0 deletions

diff --git a/src/video_core/texture_cache/util.cpp b/src/video_core/texture_cache/util.cpp
index ef34019a08..0e1acba813 100644
--- a/src/video_core/texture_cache/util.cpp
+++ b/src/video_core/texture_cache/util.cpp
@@ -929,6 +929,210 @@ boost::container::small_vector<BufferImageCopy, 16> UnswizzleImage(Tegra::Memory
     return copies;
 }
 
+namespace {
+// One level of a single-layer 2D block-linear image of 1x1-texel blocks, laid out as
+// UnswizzleImage reads it: rows of blocks, each block one GOB wide and 2^block_height GOBs tall.
+struct BlockLinearLevel {
+    u32 offset;         ///< Into the image
+    u32 width;          ///< Texels
+    u32 height;
+    u32 block_height;   ///< Log2 of the GOBs a block is tall
+    u32 block_texels;   ///< Texels across a block
+    u32 block_rows;     ///< Texel rows in a block
+    u32 block_bytes;
+    u32 blocks_per_row;
+};
+
+std::vector<BlockLinearLevel> BlockLinearLevels(const ImageInfo& info) {
+    const LevelInfo level_info = MakeLevelInfo(info);
+    const u32 bpp_log2 = BytesPerBlockLog2(info.format);
+    const Extent2D gob = GobSize(bpp_log2, info.block.height, info.tile_width_spacing);
+    std::vector<BlockLinearLevel> levels;
+    u32 offset = 0;
+    for (s32 level = 0; level < info.resources.levels; ++level) {
+        const Extent3D level_size = AdjustMipSize(info.size, level);
+        const Extent3D num_tiles = AdjustTileSize(level_size, level_info.tile_size);
+        const Extent3D block =
+            AdjustMipBlockSize(num_tiles, level_info.block, level, level_info.num_levels);
+        const u32 stride_alignment = StrideAlignment(num_tiles, info.block, gob, bpp_log2);
+        const u32 stride = Common::AlignUpLog2(num_tiles.width, stride_alignment) << bpp_log2;
+        levels.push_back({
+            .offset = offset,
+            .width = level_size.width,
+            .height = level_size.height,
+            .block_height = block.height,
+            .block_texels = GOB_SIZE_X >> bpp_log2,
+            .block_rows = GOB_SIZE_Y << block.height,
+            .block_bytes = GOB_SIZE << block.height,
+            .blocks_per_row = Common::DivCeilLog2(stride, GOB_SIZE_X_SHIFT),
+        });
+        offset += CalculateLevelSize(level_info, level);
+    }
+    return levels;
+}
+
+// Rows of blocks a rectangle covers, and its blocks across.
+struct RectBlocks {
+    u32 first_row;
+    u32 last_row;
+    u32 first_block;
+    u32 num_blocks;
+};
+
+RectBlocks BlocksOf(const BlockLinearLevel& level, const LevelRect& rect) {
+    const u32 first_block = rect.x / level.block_texels;
+    return {
+        .first_row = rect.y / level.block_rows,
+        .last_row = (rect.y + rect.height - 1) / level.block_rows,
+        .first_block = first_block,
+        .num_blocks = (std::min)(Common::DivCeil(rect.width, level.block_texels),
+                                 level.blocks_per_row - first_block),
+    };
+}
+
+u32 BlockRowTexelRows(const BlockLinearLevel& level, u32 row) {
+    return (std::min)(level.block_rows, level.height - row * level.block_rows);
+}
+} // Anonymous namespace
+
+std::vector<LevelRect> SparseTileRects(const ImageInfo& info,
+                                       std::span<const std::pair<u64, u64>> ranges, u32 tile_width,
+                                       u32 tile_height, s32 tail_level) {
+    std::vector<LevelRect> rects;
+    const std::vector<BlockLinearLevel> levels = BlockLinearLevels(info);
+    const u64 image_end = CalculateLevelBytes(
+        CalculateLevelSizes(MakeLevelInfo(info), info.resources.levels), info.resources.levels);
+    for (s32 index = 0; index < static_cast<s32>(levels.size()); ++index) {
+        const BlockLinearLevel& level = levels[index];
+        const u64 level_end =
+            index + 1 < static_cast<s32>(levels.size()) ? levels[index + 1].offset : image_end;
+        const auto overlaps = [&](const std::pair<u64, u64>& range) {
+            return range.first < level_end && range.first + range.second > level.offset;
+        };
+        if (index >= tail_level) {
+            if (std::ranges::any_of(ranges, overlaps)) {
+                rects.push_back({index, 0, 0, level.width, level.height});
+            }
+            continue;
+        }
+        const u32 tiles_x = Common::DivCeil(level.width, tile_width);
+        const u32 tiles_y = Common::DivCeil(level.height, tile_height);
+        std::vector<bool> touched(size_t{tiles_x} * tiles_y);
+        for (const auto& range : ranges) {
+            if (!overlaps(range)) {
+                continue;
+            }
+            const u64 begin = (std::max<u64>)(range.first, level.offset) - level.offset;
+            const u64 end = (std::min<u64>)(range.first + range.second, level_end) - level.offset;
+            const u64 first = begin / level.block_bytes;
+            const u64 last = (end - 1) / level.block_bytes;
+            for (u64 row = first / level.blocks_per_row; row <= last / level.blocks_per_row; ++row) {
+                const u64 row_start = row * level.blocks_per_row;
+                const u64 low = (std::max)(first, row_start) - row_start;
+                const u64 high = (std::min)(last, row_start + level.blocks_per_row - 1) - row_start;
+                const u64 x0 = low * level.block_texels;
+                const u64 y0 = row * level.block_rows;
+                if (x0 >= level.width || y0 >= level.height) {
+                    continue;
+                }
+                const u64 x1 = (std::min<u64>)((high + 1) * level.block_texels, level.width);
+                const u64 y1 = (std::min<u64>)(y0 + level.block_rows, level.height);
+                for (u64 ty = y0 / tile_height; ty <= (y1 - 1) / tile_height; ++ty) {
+                    for (u64 tx = x0 / tile_width; tx <= (x1 - 1) / tile_width; ++tx) {
+                        touched[ty * tiles_x + tx] = true;
+                    }
+                }
+            }
+        }
+        for (u32 ty = 0; ty < tiles_y; ++ty) {
+            for (u32 tx = 0; tx < tiles_x;) {
+                if (!touched[size_t{ty} * tiles_x + tx]) {
+                    ++tx;
+                    continue;
+                }
+                const u32 first_tile = tx;
+                while (tx < tiles_x && touched[size_t{ty} * tiles_x + tx]) {
+                    ++tx;
+                }
+                const u32 x = first_tile * tile_width;
+                const u32 y = ty * tile_height;
+                rects.push_back({
+                    .level = index,
+                    .x = x,
+                    .y = y,
+                    .width = (std::min)(tx * tile_width, level.width) - x,
+                    .height = (std::min)(y + tile_height, level.height) - y,
+                });
+            }
+        }
+    }
+    return rects;
+}
+
+size_t UnswizzledRectsBytes(const ImageInfo& info, std::span<const LevelRect> rects) {
+    const std::vector<BlockLinearLevel> levels = BlockLinearLevels(info);
+    const u32 bpp_log2 = BytesPerBlockLog2(info.format);
+    size_t bytes = 0;
+    for (const LevelRect& rect : rects) {
+        const BlockLinearLevel& level = levels[rect.level];
+        const RectBlocks blocks = BlocksOf(level, rect);
+        for (u32 row = blocks.first_row; row <= blocks.last_row; ++row) {
+            bytes += (size_t{blocks.num_blocks * level.block_texels} << bpp_log2) *
+                     BlockRowTexelRows(level, row);
+        }
+    }
+    return bytes;
+}
+
+std::vector<BufferImageCopy> UnswizzleImageRects(Tegra::MemoryManager& gpu_memory,
+                                                 GPUVAddr gpu_addr, const ImageInfo& info,
+                                                 std::span<const LevelRect> rects,
+                                                 std::span<u8> output) {
+    const std::vector<BlockLinearLevel> levels = BlockLinearLevels(info);
+    const u32 bpp_log2 = BytesPerBlockLog2(info.format);
+    std::vector<BufferImageCopy> copies;
+    std::vector<u8> swizzled;
+    size_t output_offset = 0;
+    for (const LevelRect& rect : rects) {
+        const BlockLinearLevel& level = levels[rect.level];
+        const RectBlocks blocks = BlocksOf(level, rect);
+        const u32 width = blocks.num_blocks * level.block_texels;
+        const size_t row_bytes = size_t{blocks.num_blocks} * level.block_bytes;
+        for (u32 row = blocks.first_row; row <= blocks.last_row; ++row) {
+            // A row of whole blocks is laid out like an image of that width on its own.
+            const u32 texel_rows = BlockRowTexelRows(level, row);
+            const size_t bytes = (size_t{width} << bpp_log2) * texel_rows;
+            const GPUVAddr row_addr = gpu_addr + level.offset +
+                                      u64{row} * level.blocks_per_row * level.block_bytes +
+                                      u64{blocks.first_block} * level.block_bytes;
+            swizzled.assign(row_bytes, 0);
+            gpu_memory.ReadBlockUnsafe(row_addr, swizzled.data(), row_bytes);
+            UnswizzleTexture(output.subspan(output_offset, bytes), swizzled, 1U << bpp_log2, width,
+                             texel_rows, 1, level.block_height, 0, 0,
+                             gpu_memory.UsesNativeTiling());
+            const u32 row_y = row * level.block_rows;
+            const u32 y0 = (std::max)(rect.y, row_y);
+            const u32 y1 = (std::min)(rect.y + rect.height, row_y + texel_rows);
+            copies.push_back(BufferImageCopy{
+                .buffer_offset = output_offset + ((size_t{y0 - row_y} * width) << bpp_log2),
+                .buffer_size = bytes,
+                .buffer_row_length = width,
+                .buffer_image_height = texel_rows,
+                .image_subresource =
+                    {
+                        .base_level = rect.level,
+                        .base_layer = 0,
+                        .num_layers = 1,
+                    },
+                .image_offset = {static_cast<s32>(rect.x), static_cast<s32>(y0), 0},
+                .image_extent = {rect.width, y1 - y0, 1},
+            });
+            output_offset += bytes;
+        }
+    }
+    return copies;
+}
+
 void ConvertedLayout(const ImageInfo& info, std::span<BufferImageCopy> copies) {
     // Same offsets and sizes as ConvertImage below.
     const auto recompression = Settings::GetAstcRecompression();