// Independent educational model. Not an x86 IOMMU or Arm SMMU register format.
// Four levels, 9-bit indices, 4 KiB pages; unsigned 48-bit input addresses.
#include <array>
#include <cstdint>
#include <iostream>
#include <map>
#include <optional>

struct Entry {
    std::uint64_t target = 0;
    bool present = false;
    bool write = false;
};

using Table = std::array<Entry, 512>;
using Tables = std::map<std::uint64_t, Table>;

std::optional<std::uint64_t> translate(const Tables& tables, std::uint64_t root,
                                       std::uint64_t address, bool write)
{
    if (address >> 48) {
        return {}; // Model limit, not a CPU canonical-address check.
    }

    // Walk from the root table down to a 4 KiB frame.
    for (int shift : {39, 30, 21, 12}) {
        if (root & 0xfff) {
            return {};
        }
        auto table = tables.find(root);
        if (table == tables.end()) {
            return {};
        }

        const auto index = (address >> shift) & 0x1ff;
        const auto& entry = table->second[index];

        // Permissions are checked at every level in this model.
        if (!entry.present || (write && !entry.write) || (entry.target & 0xfff)) {
            return {};
        }
        if (shift == 12) {
            return entry.target | (address & 0xfff);
        }
        root = entry.target;
    }
    return {};
}

int main()
{
    // Arrange: three table links and one mapped leaf.
    Tables tables;
    tables[0x1000][0] = {0x2000, true, true};
    tables[0x2000][0] = {0x3000, true, true};
    tables[0x3000][0] = {0x4000, true, true};
    tables[0x4000][1] = {0x9000, true, true};

    // Report every expectation; return nonzero on any failure.
    int failures = 0;
    auto check = [&](bool ok, const char* name) {
        std::cout << (ok ? "PASS " : "FAIL ") << name << '\n';
        failures += !ok;
    };
    auto walk = [&](std::uint64_t a, bool w = false) {
        return translate(tables, 0x1000, a, w);
    };

    // Positive path and page-boundary checks.
    check(walk(0x1234) == std::optional<std::uint64_t>{0x9234}, "page offset preserved");
    check(walk(0x1fff) == std::optional<std::uint64_t>{0x9fff}, "last byte in page");
    check(!walk(0x2000), "next page is unmapped");

    // Negative path: restrict writes at an intermediate level.
    tables[0x2000][0].write = false;
    check(walk(0x1234).has_value(), "read remains permitted");
    check(!walk(0x1234, true), "write denied by intermediate table");
    check(!walk(1ULL << 48), "out-of-model address rejected");
    tables[0x4000][1].target = 0x9001;
    check(!walk(0x1234), "misaligned frame rejected");
    return failures ? 1 : 0;
}