dungeon_stream_allocator.cc

Go to the documentation of this file.

#include "zelda3/dungeon/dungeon_stream_allocator.h"
 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <map>
#include <span>
#include <tuple>
#include <utility>
#include <vector>
 
#include "absl/status/status.h"
#include "absl/status/statusor.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "rom/rom.h"
#include "rom/snes.h"
#include "rom/write_fence.h"
#include "util/macro.h"
#include "util/rom_hash.h"
#include "zelda3/dungeon/dungeon_rom_addresses.h"
 
namespace yaze::zelda3 {
namespace {
 
constexpr uint32_t kLoRomBankSize = 0x8000;
constexpr uint32_t kWramMappedPcBegin = 0x3F0000;
constexpr uint32_t kWramMappedPcEnd = 0x400000;
 
bool IntersectsWramMappedPc(uint32_t begin, uint32_t end) {
  return begin < kWramMappedPcEnd && kWramMappedPcBegin < end;
}
 
uint32_t PointerWidth(DungeonPointerEncoding encoding) {
  return encoding == DungeonPointerEncoding::kLong24 ? 3u : 2u;
}
 
bool Contains(const DungeonStreamPcRange& outer,
              const DungeonStreamPcRange& inner) {
  return outer.begin <= inner.begin && inner.end <= outer.end;
}
 
bool Intersects(const DungeonStreamPcRange& a, const DungeonStreamPcRange& b) {
  return a.begin < b.end && b.begin < a.end;
}
 
bool ContainsAddress(const DungeonStreamPcRange& range, uint32_t address) {
  return range.begin <= address && address < range.end;
}
 
absl::StatusOr<std::vector<DungeonStreamPcRange>> NormalizeRanges(
    const std::vector<DungeonStreamPcRange>& input, uint32_t rom_size,
    const char* label, bool allow_empty) {
  if (input.empty() && !allow_empty) {
    return absl::InvalidArgumentError(
        absl::StrCat(label, " must not be empty"));
  }
 
  std::vector<DungeonStreamPcRange> ranges = input;
  std::sort(ranges.begin(), ranges.end(), [](const auto& a, const auto& b) {
    return std::tie(a.begin, a.end) < std::tie(b.begin, b.end);
  });
  std::vector<DungeonStreamPcRange> normalized;
  for (const auto& range : ranges) {
    if (range.begin >= range.end) {
      return absl::InvalidArgumentError(
          absl::StrFormat("%s contains empty/reversed range [0x%06X,0x%06X)",
                          label, range.begin, range.end));
    }
    if (range.end > rom_size) {
      return absl::OutOfRangeError(
          absl::StrFormat("%s range [0x%06X,0x%06X) exceeds ROM size 0x%06X",
                          label, range.begin, range.end, rom_size));
    }
    if (IntersectsWramMappedPc(range.begin, range.end)) {
      return absl::InvalidArgumentError(absl::StrFormat(
          "%s range [0x%06X,0x%06X) maps through SNES WRAM banks $7E/$7F",
          label, range.begin, range.end));
    }
    if (!normalized.empty() && range.begin < normalized.back().end) {
      return absl::InvalidArgumentError(absl::StrFormat(
          "%s ranges overlap at PC 0x%06X", label, range.begin));
    }
    if (!normalized.empty() && range.begin == normalized.back().end) {
      normalized.back().end = range.end;
    } else {
      normalized.push_back(range);
    }
  }
  return normalized;
}
 
absl::Status ValidateAllocationSubset(
    const std::vector<DungeonStreamPcRange>& data_ranges,
    const std::vector<DungeonStreamPcRange>& allocation_ranges) {
  for (const auto& allocation : allocation_ranges) {
    const bool contained = std::any_of(
        data_ranges.begin(), data_ranges.end(),
        [&](const auto& data) { return Contains(data, allocation); });
    if (!contained) {
      return absl::InvalidArgumentError(absl::StrFormat(
          "Allocation range [0x%06X,0x%06X) is not contained in one data "
          "range",
          allocation.begin, allocation.end));
    }
  }
  return absl::OkStatus();
}
 
absl::StatusOr<uint32_t> ReadWordAt(const Rom& rom, uint32_t address) {
  auto result = rom.ReadWord(static_cast<int>(address));
  if (!result.ok()) {
    return result.status();
  }
  return static_cast<uint32_t>(*result);
}
 
absl::StatusOr<uint32_t> ReadLongAt(const Rom& rom, uint32_t address) {
  auto result = rom.ReadLong(static_cast<int>(address));
  if (!result.ok()) {
    return result.status();
  }
  return *result;
}
 
absl::Status ValidateKnownPointerTableSource(
    const Rom& rom, const DungeonStreamLayout& layout) {
  switch (layout.kind) {
    case DungeonStreamKind::kObject: {
      if (layout.pointer_encoding != DungeonPointerEncoding::kLong24) {
        return absl::InvalidArgumentError(
            "Object streams require 24-bit long pointers");
      }
      auto raw = ReadLongAt(rom, kRoomObjectPointer);
      if (!raw.ok()) {
        return raw.status();
      }
      if ((*raw & 0xFFFFu) < 0x8000u ||
          SnesToPc(*raw) != layout.pointer_table_pc) {
        return absl::FailedPreconditionError(absl::StrFormat(
            "Object pointer-table source at PC 0x%06X does not resolve to "
            "configured table PC 0x%06X",
            kRoomObjectPointer, layout.pointer_table_pc));
      }
      return absl::OkStatus();
    }
    case DungeonStreamKind::kSprite: {
      if (layout.pointer_encoding != DungeonPointerEncoding::kFixedBank16 ||
          layout.pointer_bank != 0x09) {
        return absl::InvalidArgumentError(
            "Sprite streams require fixed-bank-16 pointers in bank 0x09");
      }
      auto raw = ReadWordAt(rom, kRoomsSpritePointer);
      if (!raw.ok()) {
        return raw.status();
      }
      if (*raw < 0x8000u ||
          SnesToPc((static_cast<uint32_t>(layout.pointer_bank) << 16) | *raw) !=
              layout.pointer_table_pc) {
        return absl::FailedPreconditionError(absl::StrFormat(
            "Sprite pointer-table source at PC 0x%06X does not resolve to "
            "configured table PC 0x%06X",
            kRoomsSpritePointer, layout.pointer_table_pc));
      }
      return absl::OkStatus();
    }
    case DungeonStreamKind::kPotItem:
      if (layout.pointer_encoding != DungeonPointerEncoding::kFixedBank16 ||
          layout.pointer_bank != 0x01) {
        return absl::InvalidArgumentError(
            "Pot-item streams require fixed-bank-16 pointers in bank 0x01");
      }
      if (layout.pointer_table_pc != kRoomItemsPointers) {
        return absl::FailedPreconditionError(absl::StrFormat(
            "Pot-item pointer table must be the fixed PC table at 0x%06X",
            kRoomItemsPointers));
      }
      return absl::OkStatus();
  }
  return absl::InvalidArgumentError("Unknown dungeon stream kind");
}
 
DungeonStreamPcRange KnownPointerSourceRange(DungeonStreamKind kind) {
  switch (kind) {
    case DungeonStreamKind::kObject:
      return {kRoomObjectPointer, kRoomObjectPointer + 3};
    case DungeonStreamKind::kSprite:
      return {kRoomsSpritePointer, kRoomsSpritePointer + 2};
    case DungeonStreamKind::kPotItem:
      // Pot-item pointers use a fixed table rather than an indirection source.
      return {kRoomItemsPointers, kRoomItemsPointers};
  }
  return {};
}
 
absl::StatusOr<DungeonStreamLayout> ValidateAndNormalizeLayout(
    const Rom& rom, const DungeonStreamLayout& input) {
  if (!rom.is_loaded()) {
    return absl::InvalidArgumentError("ROM not loaded");
  }
  if (rom.size() > std::numeric_limits<uint32_t>::max()) {
    return absl::OutOfRangeError("ROM is too large for PC-native layout");
  }
  if (input.pointer_count == 0 || input.pointer_count > kNumberOfRooms) {
    return absl::InvalidArgumentError(
        absl::StrFormat("Pointer count %u is outside supported range 1..%d",
                        input.pointer_count, kNumberOfRooms));
  }
 
  DungeonStreamLayout layout = input;
  const uint32_t rom_size = static_cast<uint32_t>(rom.size());
  auto data_ranges =
      NormalizeRanges(input.data_ranges, rom_size, "data_ranges", false);
  if (!data_ranges.ok()) {
    return data_ranges.status();
  }
  auto allocation_ranges = NormalizeRanges(input.allocation_ranges, rom_size,
                                           "allocation_ranges", true);
  if (!allocation_ranges.ok()) {
    return allocation_ranges.status();
  }
  layout.data_ranges = std::move(*data_ranges);
  layout.allocation_ranges = std::move(*allocation_ranges);
 
  auto allocation_status =
      ValidateAllocationSubset(layout.data_ranges, layout.allocation_ranges);
  if (!allocation_status.ok()) {
    return allocation_status;
  }
 
  const uint32_t pointer_width = PointerWidth(layout.pointer_encoding);
  const uint64_t table_end =
      static_cast<uint64_t>(layout.pointer_table_pc) +
      static_cast<uint64_t>(layout.pointer_count) * pointer_width;
  if (table_end > rom_size) {
    return absl::OutOfRangeError(
        "Dungeon stream pointer table is out of range");
  }
  const DungeonStreamPcRange pointer_table_range{
      layout.pointer_table_pc, static_cast<uint32_t>(table_end)};
  if (IntersectsWramMappedPc(pointer_table_range.begin,
                             pointer_table_range.end)) {
    return absl::InvalidArgumentError(
        "Dungeon stream pointer table maps through SNES WRAM banks $7E/$7F");
  }
  if (layout.pointer_encoding == DungeonPointerEncoding::kFixedBank16) {
    const uint32_t pointer_table_word =
        PcToSnes(layout.pointer_table_pc) & 0xFFFFu;
    const uint64_t runtime_table_end =
        static_cast<uint64_t>(pointer_table_word) +
        static_cast<uint64_t>(layout.pointer_count) * pointer_width;
    if (runtime_table_end > 0x10000u) {
      return absl::InvalidArgumentError(
          "Fixed-bank-16 pointer table crosses its runtime CPU bank");
    }
  }
 
  const DungeonStreamPcRange pointer_source_range =
      KnownPointerSourceRange(layout.kind);
  if (pointer_source_range.begin < pointer_source_range.end) {
    if (pointer_source_range.end > rom_size) {
      return absl::OutOfRangeError(
          "Live pointer-table source is outside the source ROM");
    }
    if (Intersects(pointer_table_range, pointer_source_range)) {
      return absl::InvalidArgumentError(
          "Dungeon stream pointer table must not overlap the live "
          "pointer-table source");
    }
  }
 
  DungeonStreamPcRange door_pointer_range;
  if (layout.kind == DungeonStreamKind::kObject) {
    const uint64_t door_pointer_end =
        static_cast<uint64_t>(kDoorPointers) +
        static_cast<uint64_t>(kNumberOfRooms) * 3u;
    if (door_pointer_end > rom_size) {
      return absl::OutOfRangeError(
          "Complete object door-pointer table is outside the source ROM");
    }
    door_pointer_range = {kDoorPointers,
                          static_cast<uint32_t>(door_pointer_end)};
    if (Intersects(pointer_table_range, door_pointer_range)) {
      return absl::InvalidArgumentError(
          "Dungeon stream pointer table must not overlap the object "
          "door-pointer table");
    }
  }
 
  for (const auto& data : layout.data_ranges) {
    if (Intersects(pointer_table_range, data)) {
      return absl::InvalidArgumentError(
          "Dungeon stream data ranges must not overlap the pointer table");
    }
    if (pointer_source_range.begin < pointer_source_range.end &&
        Intersects(pointer_source_range, data)) {
      return absl::InvalidArgumentError(
          "Dungeon stream data ranges must not overlap the live "
          "pointer-table source");
    }
    if (door_pointer_range.begin < door_pointer_range.end &&
        Intersects(door_pointer_range, data)) {
      return absl::InvalidArgumentError(
          "Dungeon stream data ranges must not overlap the object "
          "door-pointer table");
    }
  }
 
  auto source_status = ValidateKnownPointerTableSource(rom, layout);
  if (!source_status.ok()) {
    return source_status;
  }
  return layout;
}
 
absl::StatusOr<uint32_t> DecodePointer(const Rom& rom,
                                       const DungeonStreamLayout& layout,
                                       uint32_t room_id) {
  const uint32_t width = PointerWidth(layout.pointer_encoding);
  const uint32_t slot = layout.pointer_table_pc + room_id * width;
  uint32_t snes = 0;
  if (layout.pointer_encoding == DungeonPointerEncoding::kLong24) {
    auto raw = ReadLongAt(rom, slot);
    if (!raw.ok()) {
      return raw.status();
    }
    snes = *raw;
  } else {
    auto raw = ReadWordAt(rom, slot);
    if (!raw.ok()) {
      return raw.status();
    }
    snes = (static_cast<uint32_t>(layout.pointer_bank) << 16) | *raw;
  }
  if ((snes & 0xFFFFu) < 0x8000u) {
    return absl::FailedPreconditionError(absl::StrFormat(
        "Pointer word 0x%04X is not a LoROM address", snes & 0xFFFFu));
  }
  const uint8_t bank = static_cast<uint8_t>((snes >> 16) & 0xFFu);
  if (bank == 0x7E || bank == 0x7F || bank == 0xFE || bank == 0xFF) {
    return absl::FailedPreconditionError(
        absl::StrFormat("Pointer uses SNES WRAM bank or mirror 0x%02X", bank));
  }
  const uint32_t pc = SnesToPc(snes);
  if (pc >= rom.size()) {
    return absl::OutOfRangeError(
        absl::StrFormat("Pointer resolves outside ROM at PC 0x%06X", pc));
  }
  return pc;
}
 
const DungeonStreamPcRange* FindContainingRange(
    const std::vector<DungeonStreamPcRange>& ranges, uint32_t address) {
  auto it =
      std::upper_bound(ranges.begin(), ranges.end(), address,
                       [](uint32_t value, const DungeonStreamPcRange& range) {
                         return value < range.begin;
                       });
  if (it == ranges.begin()) {
    return nullptr;
  }
  --it;
  return ContainsAddress(*it, address) ? &*it : nullptr;
}
 
absl::StatusOr<uint32_t> ParseObjectStream(std::span<const uint8_t> bytes,
                                           uint32_t start, uint32_t limit,
                                           uint32_t* door_list_pc = nullptr) {
  if (start + 2 > limit) {
    return absl::DataLossError("Object stream is missing its two-byte header");
  }
  uint32_t cursor = start + 2;
  for (int list = 0; list < 2; ++list) {
    while (true) {
      if (cursor + 2 > limit) {
        return absl::DataLossError(
            absl::StrFormat("Object list %d has no 0xFFFF terminator", list));
      }
      if (bytes[cursor] == 0xFF && bytes[cursor + 1] == 0xFF) {
        cursor += 2;
        break;
      }
      if (cursor + 3 > limit) {
        return absl::DataLossError(
            absl::StrFormat("Object list %d has a truncated record", list));
      }
      cursor += 3;
    }
  }
 
  bool in_doors = false;
  while (true) {
    if (cursor + 2 > limit) {
      return absl::DataLossError(in_doors ? "Object door list has no terminator"
                                          : "Object list 2 has no door marker");
    }
    if (!in_doors) {
      if (bytes[cursor] == 0xF0 && bytes[cursor + 1] == 0xFF) {
        cursor += 2;
        if (door_list_pc != nullptr) {
          *door_list_pc = cursor;
        }
        in_doors = true;
        continue;
      }
      if (bytes[cursor] == 0xFF && bytes[cursor + 1] == 0xFF) {
        // Canonical vanilla/OOS empty streams may terminate the third list
        // directly without a 0xFFF0 marker. Their door pointer targets this
        // final terminator.
        if (door_list_pc != nullptr) {
          *door_list_pc = cursor;
        }
        return cursor + 2;
      }
      if (cursor + 3 > limit) {
        return absl::DataLossError("Object list 2 has a truncated record");
      }
      cursor += 3;
      continue;
    }
 
    if (bytes[cursor] == 0xFF && bytes[cursor + 1] == 0xFF) {
      return cursor + 2;
    }
    cursor += 2;
  }
}
 
absl::StatusOr<uint32_t> ParseSpriteStream(std::span<const uint8_t> bytes,
                                           uint32_t start, uint32_t limit) {
  if (start >= limit) {
    return absl::DataLossError("Sprite stream is missing its sort byte");
  }
  uint32_t cursor = start + 1;
  while (cursor < limit) {
    if (bytes[cursor] == 0xFF) {
      return cursor + 1;
    }
    if (cursor + 3 > limit) {
      return absl::DataLossError("Sprite stream has a truncated record");
    }
    cursor += 3;
  }
  return absl::DataLossError("Sprite stream has no 0xFF terminator");
}
 
absl::StatusOr<uint32_t> ParsePotItemStream(std::span<const uint8_t> bytes,
                                            uint32_t start, uint32_t limit) {
  uint32_t cursor = start;
  while (true) {
    if (cursor + 2 > limit) {
      return absl::DataLossError("Pot-item stream has no 0xFFFF terminator");
    }
    if (bytes[cursor] == 0xFF && bytes[cursor + 1] == 0xFF) {
      return cursor + 2;
    }
    if (cursor + 3 > limit) {
      return absl::DataLossError("Pot-item stream has a truncated record");
    }
    cursor += 3;
  }
}
 
absl::StatusOr<uint32_t> ParseStream(std::span<const uint8_t> bytes,
                                     DungeonStreamKind kind, uint32_t start,
                                     uint32_t limit) {
  if (limit > bytes.size() || start >= limit) {
    return absl::OutOfRangeError("Dungeon stream parse bounds are invalid");
  }
  switch (kind) {
    case DungeonStreamKind::kObject:
      return ParseObjectStream(bytes, start, limit);
    case DungeonStreamKind::kSprite:
      return ParseSpriteStream(bytes, start, limit);
    case DungeonStreamKind::kPotItem:
      return ParsePotItemStream(bytes, start, limit);
  }
  return absl::InvalidArgumentError("Unknown dungeon stream kind");
}
 
absl::StatusOr<DungeonStreamRecord> ReadFixedBankRoomStream(
    const Rom& rom, int room_id, DungeonStreamKind kind) {
  if (room_id < 0 || room_id >= kNumberOfRooms) {
    return absl::OutOfRangeError(
        "Dungeon stream room is outside the room table");
  }
  if (!rom.is_loaded()) {
    return absl::InvalidArgumentError("ROM not loaded");
  }
  if (rom.size() > std::numeric_limits<uint32_t>::max()) {
    return absl::OutOfRangeError("ROM is too large for PC-native stream reads");
  }
  DungeonStreamLayout layout;
  layout.kind = kind;
  layout.pointer_encoding = DungeonPointerEncoding::kFixedBank16;
  if (kind == DungeonStreamKind::kSprite) {
    layout.pointer_bank = 0x09;
    layout.pointer_table_pc = kRoomsSpritePointer;
    ASSIGN_OR_RETURN(layout.pointer_table_pc, DecodePointer(rom, layout, 0));
  } else {
    layout.pointer_bank = 0x01;
    layout.pointer_table_pc = kRoomItemsPointers;
  }
  const uint32_t table_end = layout.pointer_table_pc + kNumberOfRooms * 2;
  const uint32_t table_bank_end =
      ((layout.pointer_table_pc / kLoRomBankSize) + 1) * kLoRomBankSize;
  if (table_end > rom.size() || table_end > table_bank_end) {
    return absl::OutOfRangeError(
        "Dungeon stream pointer table is truncated or crosses its bank");
  }
  const DungeonStreamPcRange pointer_table{layout.pointer_table_pc, table_end};
  const auto pointer_source = KnownPointerSourceRange(kind);
  if (Intersects(pointer_table, pointer_source)) {
    return absl::FailedPreconditionError(
        "Dungeon stream pointer table overlaps its live pointer source");
  }
  ASSIGN_OR_RETURN(const uint32_t start, DecodePointer(rom, layout, room_id));
  uint32_t limit =
      std::min<uint32_t>(static_cast<uint32_t>(rom.size()),
                         ((start / kLoRomBankSize) + 1) * kLoRomBankSize);
  if (kind == DungeonStreamKind::kSprite && start >= kSpritesDataEmptyRoom &&
      start < kSpritesDataEndExclusive) {
    limit = std::min(limit, static_cast<uint32_t>(kSpritesDataEndExclusive));
  }
  if (kind == DungeonStreamKind::kPotItem && start >= table_end &&
      start < kRoomItemsDataEnd) {
    limit = std::min(limit, static_cast<uint32_t>(kRoomItemsDataEnd));
  }
  for (const auto& metadata : {pointer_table, pointer_source}) {
    if (ContainsAddress(metadata, start)) {
      return absl::FailedPreconditionError(
          "Dungeon stream pointer resolves inside pointer metadata");
    }
    if (metadata.begin > start) {
      limit = std::min(limit, metadata.begin);
    }
  }
  const uint32_t storage_limit = limit;
  for (int other = 0; other < kNumberOfRooms; ++other) {
    const auto address = DecodePointer(rom, layout, other);
    if (address.ok() && *address > start) {
      limit = std::min(limit, *address);
    }
  }
  const std::span<const uint8_t> bytes(rom.data(), rom.size());
  // Vanilla pot lists may end at another room's empty list. That shared
  // terminator is readable, but no record belonging to the next room is.
  // Keep bank, ROM, region and metadata limits strict, and require a complete
  // sequence of three-byte records before the two-byte terminator.
  if (kind == DungeonStreamKind::kPotItem && limit < storage_limit &&
      limit + 2 <= storage_limit && (limit - start) % 3 == 0 &&
      bytes[limit] == 0xFF && bytes[limit + 1] == 0xFF) {
    limit += 2;
  }
  ASSIGN_OR_RETURN(const uint32_t end, ParseStream(bytes, kind, start, limit));
  DungeonStreamRecord record;
  record.room_id = room_id;
  record.pointer_slot_pc = layout.pointer_table_pc + room_id * 2;
  record.data_pc = start;
  record.logical_end_pc = end;
  record.valid = true;
  record.encoded_stream.assign(bytes.begin() + start, bytes.begin() + end);
  return record;
}
 
absl::Status ValidateCompleteEncodedStream(
    DungeonStreamKind kind, const std::vector<uint8_t>& encoded) {
  if (encoded.empty()) {
    return absl::InvalidArgumentError("Replacement stream must not be empty");
  }
  auto logical_end =
      ParseStream(encoded, kind, 0, static_cast<uint32_t>(encoded.size()));
  if (!logical_end.ok()) {
    return logical_end.status();
  }
  if (*logical_end != encoded.size()) {
    return absl::InvalidArgumentError(
        "Replacement stream contains bytes after its logical terminator");
  }
  return absl::OkStatus();
}
 
absl::StatusOr<uint32_t> ObjectDoorListOffset(
    const std::vector<uint8_t>& encoded) {
  uint32_t door_list_pc = std::numeric_limits<uint32_t>::max();
  auto logical_end = ParseObjectStream(
      encoded, 0, static_cast<uint32_t>(encoded.size()), &door_list_pc);
  if (!logical_end.ok()) {
    return logical_end.status();
  }
  if (*logical_end != encoded.size() || door_list_pc >= encoded.size()) {
    return absl::DataLossError(
        "Object stream does not have a valid door-list target");
  }
  return door_list_pc;
}
 
std::vector<DungeonStreamPcRange> UnionIntervals(
    std::vector<DungeonStreamPcRange> intervals) {
  std::sort(intervals.begin(), intervals.end(),
            [](const auto& a, const auto& b) {
              return std::tie(a.begin, a.end) < std::tie(b.begin, b.end);
            });
  std::vector<DungeonStreamPcRange> result;
  for (const auto& interval : intervals) {
    if (result.empty() || interval.begin > result.back().end) {
      result.push_back(interval);
    } else {
      result.back().end = std::max(result.back().end, interval.end);
    }
  }
  return result;
}
 
std::vector<DungeonStreamPcRange> ComplementIntervals(
    const std::vector<DungeonStreamPcRange>& containers,
    const std::vector<DungeonStreamPcRange>& occupied) {
  std::vector<DungeonStreamPcRange> free;
  for (const auto& container : containers) {
    uint32_t cursor = container.begin;
    for (const auto& used : occupied) {
      if (used.end <= cursor) {
        continue;
      }
      if (used.begin >= container.end) {
        break;
      }
      if (used.begin > cursor) {
        free.push_back({cursor, std::min(used.begin, container.end)});
      }
      cursor = std::max(cursor, std::min(used.end, container.end));
      if (cursor >= container.end) {
        break;
      }
    }
    if (cursor < container.end) {
      free.push_back({cursor, container.end});
    }
  }
  return free;
}
 
absl::StatusOr<std::vector<uint8_t>> EncodePointer(
    const DungeonStreamLayout& layout, uint32_t pc) {
  if (pc >= kWramMappedPcBegin && pc < kWramMappedPcEnd) {
    return absl::OutOfRangeError(absl::StrFormat(
        "PC address 0x%06X maps through SNES WRAM banks $7E/$7F", pc));
  }
  const uint32_t snes = PcToSnes(pc);
  if (SnesToPc(snes) != pc || (snes & 0xFFFFu) < 0x8000u) {
    return absl::OutOfRangeError(absl::StrFormat(
        "PC address 0x%06X is not representable as a LoROM pointer", pc));
  }
  if (layout.pointer_encoding == DungeonPointerEncoding::kLong24) {
    return std::vector<uint8_t>{static_cast<uint8_t>(snes & 0xFF),
                                static_cast<uint8_t>((snes >> 8) & 0xFF),
                                static_cast<uint8_t>((snes >> 16) & 0xFF)};
  }
  const uint32_t fixed_snes =
      (static_cast<uint32_t>(layout.pointer_bank) << 16) | (snes & 0xFFFFu);
  if (SnesToPc(fixed_snes) != pc) {
    return absl::OutOfRangeError(absl::StrFormat(
        "PC address 0x%06X is outside fixed pointer bank 0x%02X", pc,
        layout.pointer_bank));
  }
  return std::vector<uint8_t>{static_cast<uint8_t>(snes & 0xFF),
                              static_cast<uint8_t>((snes >> 8) & 0xFF)};
}
 
absl::StatusOr<uint32_t> FindFirstFit(
    const std::vector<DungeonStreamPcRange>& free_intervals,
    const DungeonStreamLayout& layout, uint32_t size) {
  if (size == 0 || size > kLoRomBankSize) {
    return absl::ResourceExhaustedError(
        "Replacement cannot fit in one LoROM bank");
  }
 
  if (layout.pointer_encoding == DungeonPointerEncoding::kFixedBank16) {
    const uint32_t bank_begin =
        SnesToPc((static_cast<uint32_t>(layout.pointer_bank) << 16) | 0x8000u);
    const uint32_t bank_end = bank_begin + kLoRomBankSize;
    for (const auto& interval : free_intervals) {
      const uint32_t begin = std::max(interval.begin, bank_begin);
      const uint32_t end = std::min(interval.end, bank_end);
      if (begin <= end && static_cast<uint64_t>(begin) + size <= end) {
        return begin;
      }
    }
    return absl::ResourceExhaustedError(
        absl::StrFormat("No %u-byte allocation fits fixed pointer bank 0x%02X",
                        size, layout.pointer_bank));
  }
 
  for (const auto& interval : free_intervals) {
    uint32_t candidate = interval.begin;
    while (candidate < interval.end) {
      const uint32_t bank_end =
          ((candidate / kLoRomBankSize) + 1) * kLoRomBankSize;
      const uint32_t usable_end = std::min(interval.end, bank_end);
      if (static_cast<uint64_t>(candidate) + size <= usable_end &&
          EncodePointer(layout, candidate).ok()) {
        return candidate;
      }
      if (bank_end <= candidate) {
        break;
      }
      candidate = bank_end;
    }
  }
  return absl::ResourceExhaustedError(
      absl::StrFormat("No declared free interval fits %u bytes", size));
}
 
void ConsumeInterval(std::vector<DungeonStreamPcRange>* free_intervals,
                     DungeonStreamPcRange consumed) {
  std::vector<DungeonStreamPcRange> next;
  next.reserve(free_intervals->size() + 1);
  for (const auto& interval : *free_intervals) {
    if (!Intersects(interval, consumed)) {
      next.push_back(interval);
      continue;
    }
    if (interval.begin < consumed.begin) {
      next.push_back({interval.begin, consumed.begin});
    }
    if (consumed.end < interval.end) {
      next.push_back({consumed.end, interval.end});
    }
  }
  *free_intervals = std::move(next);
}
 
bool IsSortedUniqueByRoom(const std::vector<DungeonStreamWrite>& writes) {
  for (size_t i = 1; i < writes.size(); ++i) {
    if (writes[i - 1].room_id >= writes[i].room_id) {
      return false;
    }
  }
  return true;
}
 
absl::Status ValidatePlanAgainstInventory(
    const DungeonStreamWritePlan& plan,
    const DungeonStreamInventory& inventory) {
  if (!inventory.ok()) {
    return absl::FailedPreconditionError(
        "Source inventory contains invalid pointers or malformed streams");
  }
  if (plan.source_size != inventory.source_size ||
      plan.source_crc32 != inventory.source_crc32) {
    return absl::AbortedError(
        "Write plan does not match the current inventory snapshot");
  }
  if (plan.payload_writes.empty()) {
    return absl::InvalidArgumentError(
        "Write plan must contain at least one payload write");
  }
  if (!IsSortedUniqueByRoom(plan.payload_writes) ||
      !IsSortedUniqueByRoom(plan.pointer_writes) ||
      (!plan.auxiliary_pointer_writes.empty() &&
       !IsSortedUniqueByRoom(plan.auxiliary_pointer_writes))) {
    return absl::InvalidArgumentError(
        "Write plan must be strictly sorted by room ID");
  }
 
  switch (plan.mode) {
    case DungeonStreamWriteMode::kCopyOnWrite: {
      if (plan.payload_writes.size() != plan.pointer_writes.size()) {
        return absl::InvalidArgumentError(
            "Copy-on-write plan must contain matching payload and pointer "
            "writes");
      }
      const size_t expected_auxiliary_count =
          plan.layout.kind == DungeonStreamKind::kObject
              ? plan.payload_writes.size()
              : 0;
      if (plan.auxiliary_pointer_writes.size() != expected_auxiliary_count) {
        return absl::InvalidArgumentError(
            "Copy-on-write plan has the wrong number of auxiliary pointer "
            "writes");
      }
      break;
    }
    case DungeonStreamWriteMode::kRepackAll:
      if (plan.layout.kind != DungeonStreamKind::kPotItem ||
          plan.layout.pointer_encoding !=
              DungeonPointerEncoding::kFixedBank16) {
        return absl::InvalidArgumentError(
            "Repack-all plans currently support only fixed-bank pot-item "
            "streams");
      }
      if (plan.layout.pointer_count != kNumberOfRooms) {
        return absl::InvalidArgumentError(absl::StrFormat(
            "Pot-item repack requires exactly %d pointers", kNumberOfRooms));
      }
      if (plan.layout.allocation_ranges.size() != 1) {
        return absl::InvalidArgumentError(
            "Pot-item repack requires exactly one normalized allocation "
            "range");
      }
      if (plan.pointer_writes.size() != plan.layout.pointer_count) {
        return absl::InvalidArgumentError(
            "Repack-all plan must update every pointer-table entry");
      }
      if (!plan.auxiliary_pointer_writes.empty()) {
        return absl::InvalidArgumentError(
            "Pot-item repack plan must not contain auxiliary pointers");
      }
      break;
  }
 
  std::vector<DungeonStreamPcRange> planned_payloads;
  planned_payloads.reserve(plan.payload_writes.size());
  std::map<std::vector<uint8_t>, size_t> payload_by_pointer;
  std::map<std::vector<uint8_t>, uint32_t> address_by_payload;
  const uint32_t pointer_width = PointerWidth(plan.layout.pointer_encoding);
  for (size_t i = 0; i < plan.payload_writes.size(); ++i) {
    const auto& payload = plan.payload_writes[i];
    if (payload.room_id >= plan.layout.pointer_count || payload.bytes.empty()) {
      return absl::InvalidArgumentError("Write plan room mapping is invalid");
    }
    auto encoded_status =
        ValidateCompleteEncodedStream(plan.layout.kind, payload.bytes);
    if (!encoded_status.ok()) {
      return encoded_status;
    }
    const uint64_t payload_end64 =
        static_cast<uint64_t>(payload.address) + payload.bytes.size();
    if (payload_end64 > std::numeric_limits<uint32_t>::max()) {
      return absl::OutOfRangeError("Payload write address overflows PC space");
    }
    const DungeonStreamPcRange payload_range{
        payload.address, static_cast<uint32_t>(payload_end64)};
    const uint32_t payload_bank_end =
        ((payload.address / kLoRomBankSize) + 1) * kLoRomBankSize;
    if (payload_range.end > payload_bank_end) {
      return absl::FailedPreconditionError(
          "Planned payload crosses a LoROM bank boundary");
    }
    const auto& allowed_ranges = plan.mode == DungeonStreamWriteMode::kRepackAll
                                     ? plan.layout.allocation_ranges
                                     : inventory.allocatable_free_intervals;
    const bool in_allowed_range = std::any_of(
        allowed_ranges.begin(), allowed_ranges.end(),
        [&](const auto& range) { return Contains(range, payload_range); });
    if (!in_allowed_range) {
      return absl::FailedPreconditionError(absl::StrFormat(
          "Payload for room %u is outside declared allocator-owned %s",
          payload.room_id,
          plan.mode == DungeonStreamWriteMode::kRepackAll ? "repack space"
                                                          : "free space"));
    }
    for (const auto& prior : planned_payloads) {
      if (Intersects(prior, payload_range)) {
        return absl::InvalidArgumentError("Planned payload writes overlap");
      }
    }
    planned_payloads.push_back(payload_range);
 
    auto expected_pointer = EncodePointer(plan.layout, payload.address);
    if (!expected_pointer.ok()) {
      return expected_pointer.status();
    }
    if (!payload_by_pointer.emplace(*expected_pointer, i).second) {
      return absl::InvalidArgumentError(
          "Multiple payload writes encode the same pointer target");
    }
    if (plan.mode == DungeonStreamWriteMode::kRepackAll &&
        !address_by_payload.emplace(payload.bytes, payload.address).second) {
      return absl::InvalidArgumentError(
          "Write plan contains duplicate logical payloads");
    }
 
    if (plan.mode == DungeonStreamWriteMode::kCopyOnWrite) {
      const auto& pointer = plan.pointer_writes[i];
      const uint32_t expected_slot =
          plan.layout.pointer_table_pc + payload.room_id * pointer_width;
      if (pointer.room_id != payload.room_id ||
          pointer.address != expected_slot ||
          pointer.bytes != *expected_pointer) {
        return absl::InvalidArgumentError(
            "Pointer write does not match its planned payload");
      }
    }
    if (plan.mode == DungeonStreamWriteMode::kCopyOnWrite &&
        plan.layout.kind == DungeonStreamKind::kObject) {
      const auto& auxiliary = plan.auxiliary_pointer_writes[i];
      auto door_offset = ObjectDoorListOffset(payload.bytes);
      if (!door_offset.ok()) {
        return door_offset.status();
      }
      auto expected_door_pointer =
          EncodePointer(plan.layout, payload.address + *door_offset);
      if (!expected_door_pointer.ok()) {
        return expected_door_pointer.status();
      }
      const uint32_t expected_door_slot = kDoorPointers + payload.room_id * 3;
      if (auxiliary.room_id != payload.room_id ||
          auxiliary.address != expected_door_slot ||
          auxiliary.bytes != *expected_door_pointer) {
        return absl::InvalidArgumentError(
            "Object door pointer does not match its planned payload");
      }
      if (static_cast<uint64_t>(auxiliary.address) + auxiliary.bytes.size() >
          inventory.source_size) {
        return absl::OutOfRangeError(
            "Object door-pointer write is outside the source ROM");
      }
    }
  }
 
  if (plan.mode == DungeonStreamWriteMode::kRepackAll) {
    std::vector<uint32_t> lowest_room_by_payload(
        plan.payload_writes.size(), std::numeric_limits<uint32_t>::max());
    std::vector<bool> referenced_payloads(plan.payload_writes.size(), false);
    for (uint32_t room_id = 0; room_id < plan.layout.pointer_count; ++room_id) {
      const auto& pointer = plan.pointer_writes[room_id];
      const uint32_t expected_slot =
          plan.layout.pointer_table_pc + room_id * pointer_width;
      if (pointer.room_id != room_id || pointer.address != expected_slot) {
        return absl::InvalidArgumentError(
            "Repack-all pointer writes must cover every room in order");
      }
      const auto payload_it = payload_by_pointer.find(pointer.bytes);
      if (payload_it == payload_by_pointer.end()) {
        return absl::InvalidArgumentError(
            "Repack-all pointer does not target a planned payload");
      }
      const size_t payload_index = payload_it->second;
      referenced_payloads[payload_index] = true;
      lowest_room_by_payload[payload_index] =
          std::min(lowest_room_by_payload[payload_index], room_id);
    }
    for (size_t i = 0; i < plan.payload_writes.size(); ++i) {
      if (!referenced_payloads[i] ||
          plan.payload_writes[i].room_id != lowest_room_by_payload[i]) {
        return absl::InvalidArgumentError(
            "Repack-all payload owner must be its lowest referencing room");
      }
    }
  }
  return absl::OkStatus();
}
 
}  // namespace
 
absl::StatusOr<DungeonStreamRecord> ReadDungeonObjectStream(const Rom& rom,
                                                            int room_id) {
  if (room_id < 0 || room_id >= kNumberOfRooms) {
    return absl::OutOfRangeError(
        "Object stream room is outside the room table");
  }
  DungeonStreamLayout layout;
  layout.pointer_table_pc = kRoomObjectPointer;
  layout.pointer_encoding = DungeonPointerEncoding::kLong24;
  ASSIGN_OR_RETURN(layout.pointer_table_pc, DecodePointer(rom, layout, 0));
  const uint64_t table_end = static_cast<uint64_t>(layout.pointer_table_pc) +
                             static_cast<uint64_t>(kNumberOfRooms) * 3;
  if (table_end > rom.size()) {
    return absl::OutOfRangeError("Object stream pointer table is truncated");
  }
  if (IntersectsWramMappedPc(layout.pointer_table_pc,
                             static_cast<uint32_t>(table_end))) {
    return absl::FailedPreconditionError(
        "Object stream pointer table crosses SNES WRAM banks");
  }
  ASSIGN_OR_RETURN(const uint32_t start, DecodePointer(rom, layout, room_id));
  const DungeonStreamPcRange pointer_table{layout.pointer_table_pc,
                                           static_cast<uint32_t>(table_end)};
  const DungeonStreamPcRange pointer_source{kRoomObjectPointer,
                                            kRoomObjectPointer + 3};
  const DungeonStreamPcRange door_table{kDoorPointers,
                                        kDoorPointers + kNumberOfRooms * 3};
  uint32_t limit =
      std::min<uint32_t>(static_cast<uint32_t>(rom.size()),
                         ((start / kLoRomBankSize) + 1) * kLoRomBankSize);
  const int region_end = GetDungeonObjectDataRegionEnd(start);
  if (region_end >= 0) {
    limit = std::min(limit, static_cast<uint32_t>(region_end));
  }
  for (const auto& table : {pointer_table, pointer_source, door_table}) {
    if (ContainsAddress(table, start)) {
      return absl::FailedPreconditionError(
          "Object stream pointer resolves inside a pointer table");
    }
    if (table.begin > start) {
      limit = std::min(limit, table.begin);
    }
  }
  for (int other = 0; other < kNumberOfRooms; ++other) {
    const auto address = DecodePointer(rom, layout, other);
    if (address.ok() && *address > start) {
      limit = std::min(limit, *address);
    }
  }
  const std::span<const uint8_t> bytes(rom.data(), rom.size());
  ASSIGN_OR_RETURN(const uint32_t end, ParseObjectStream(bytes, start, limit));
  DungeonStreamRecord record;
  record.room_id = room_id;
  record.pointer_slot_pc = layout.pointer_table_pc + room_id * 3;
  record.data_pc = start;
  record.logical_end_pc = end;
  record.valid = true;
  record.encoded_stream.assign(bytes.begin() + start, bytes.begin() + end);
  return record;
}
 
absl::StatusOr<DungeonStreamRecord> ReadDungeonSpriteStream(const Rom& rom,
                                                            int room_id) {
  return ReadFixedBankRoomStream(rom, room_id, DungeonStreamKind::kSprite);
}
 
absl::StatusOr<DungeonStreamRecord> ReadDungeonPotItemStream(const Rom& rom,
                                                             int room_id) {
  return ReadFixedBankRoomStream(rom, room_id, DungeonStreamKind::kPotItem);
}
 
absl::StatusOr<DungeonStreamInventory> InventoryDungeonStreams(
    const Rom& rom, const DungeonStreamLayout& requested_layout) {
  auto normalized_layout = ValidateAndNormalizeLayout(rom, requested_layout);
  if (!normalized_layout.ok()) {
    return normalized_layout.status();
  }
 
  DungeonStreamInventory inventory;
  inventory.layout = std::move(*normalized_layout);
  inventory.source_size = static_cast<uint32_t>(rom.size());
  inventory.source_crc32 =
      util::CalculateCrc32(rom.data(), static_cast<size_t>(rom.size()));
  inventory.streams.reserve(inventory.layout.pointer_count);
 
  const uint32_t pointer_width =
      PointerWidth(inventory.layout.pointer_encoding);
  std::map<uint32_t, std::vector<size_t>> valid_by_start;
  std::vector<DungeonStreamPcRange> occupied;
  const std::span<const uint8_t> bytes(rom.data(), rom.size());
  for (uint32_t room_id = 0; room_id < inventory.layout.pointer_count;
       ++room_id) {
    DungeonStreamRecord record;
    record.room_id = room_id;
    record.pointer_slot_pc =
        inventory.layout.pointer_table_pc + room_id * pointer_width;
 
    auto pointer = DecodePointer(rom, inventory.layout, room_id);
    if (!pointer.ok()) {
      inventory.issues.push_back({DungeonStreamIssueCode::kInvalidPointer,
                                  room_id, 0,
                                  absl::StrCat("Room pointer is invalid: ",
                                               pointer.status().message())});
      inventory.streams.push_back(record);
      continue;
    }
    record.data_pc = *pointer;
    const auto* data_range =
        FindContainingRange(inventory.layout.data_ranges, record.data_pc);
    if (data_range == nullptr) {
      inventory.issues.push_back(
          {DungeonStreamIssueCode::kPointerOutsideDataRanges, room_id,
           record.data_pc,
           absl::StrFormat(
               "Room %u pointer PC 0x%06X is outside declared data ranges",
               room_id, record.data_pc)});
      inventory.streams.push_back(record);
      continue;
    }
 
    const uint32_t bank_end =
        ((record.data_pc / kLoRomBankSize) + 1) * kLoRomBankSize;
    const uint32_t parse_limit = std::min(data_range->end, bank_end);
    auto logical_end =
        ParseStream(bytes, inventory.layout.kind, record.data_pc, parse_limit);
    if (!logical_end.ok()) {
      inventory.issues.push_back(
          {DungeonStreamIssueCode::kMalformedStream, room_id, record.data_pc,
           absl::StrCat("Room stream is malformed: ",
                        logical_end.status().message())});
      inventory.streams.push_back(record);
      continue;
    }
 
    record.logical_end_pc = *logical_end;
    record.valid = true;
    record.encoded_stream.assign(bytes.begin() + record.data_pc,
                                 bytes.begin() + record.logical_end_pc);
    inventory.streams.push_back(record);
    const size_t index = inventory.streams.size() - 1;
    valid_by_start[record.data_pc].push_back(index);
    occupied.push_back({record.data_pc, record.logical_end_pc});
  }
 
  struct UniqueStream {
    uint32_t begin = 0;
    uint32_t end = 0;
    std::vector<uint32_t> room_ids;
  };
  std::vector<UniqueStream> unique;
  unique.reserve(valid_by_start.size());
  for (const auto& [start, indices] : valid_by_start) {
    UniqueStream stream;
    stream.begin = start;
    stream.end = inventory.streams[indices.front()].logical_end_pc;
    for (size_t index : indices) {
      stream.room_ids.push_back(inventory.streams[index].room_id);
    }
    if (stream.room_ids.size() > 1) {
      inventory.aliases.push_back({start, stream.room_ids});
    }
    unique.push_back(std::move(stream));
  }
 
  for (size_t i = 0; i < unique.size(); ++i) {
    for (size_t j = i + 1; j < unique.size(); ++j) {
      if (unique[j].begin >= unique[i].end) {
        break;
      }
      const uint32_t intersection_end = std::min(unique[i].end, unique[j].end);
      if (unique[j].begin >= intersection_end) {
        continue;
      }
      const auto kind = unique[j].end == unique[i].end
                            ? DungeonStreamOverlapKind::kSuffix
                            : DungeonStreamOverlapKind::kInterior;
      inventory.overlaps.push_back({kind,
                                    unique[i].room_ids,
                                    unique[j].room_ids,
                                    {unique[j].begin, intersection_end}});
    }
  }
 
  inventory.occupied_intervals = UnionIntervals(std::move(occupied));
  inventory.free_intervals = ComplementIntervals(inventory.layout.data_ranges,
                                                 inventory.occupied_intervals);
  inventory.allocatable_free_intervals = ComplementIntervals(
      inventory.layout.allocation_ranges, inventory.occupied_intervals);
  return inventory;
}
 
absl::StatusOr<DungeonStreamWritePlan> PlanDungeonStreamWrites(
    const DungeonStreamInventory& inventory,
    const std::vector<DungeonStreamReplacement>& requested_replacements) {
  if (!inventory.ok()) {
    return absl::FailedPreconditionError(
        "Cannot plan writes from an inventory with stream issues");
  }
  if (requested_replacements.empty()) {
    return absl::InvalidArgumentError("No dungeon stream replacements given");
  }
 
  std::vector<DungeonStreamReplacement> replacements = requested_replacements;
  std::sort(replacements.begin(), replacements.end(),
            [](const auto& a, const auto& b) { return a.room_id < b.room_id; });
  for (size_t i = 0; i < replacements.size(); ++i) {
    if (replacements[i].room_id >= inventory.layout.pointer_count) {
      return absl::OutOfRangeError("Replacement room ID is out of range");
    }
    if (i > 0 && replacements[i - 1].room_id == replacements[i].room_id) {
      return absl::InvalidArgumentError("Replacement room IDs must be unique");
    }
    auto status = ValidateCompleteEncodedStream(inventory.layout.kind,
                                                replacements[i].encoded_stream);
    if (!status.ok()) {
      return absl::InvalidArgumentError(
          absl::StrFormat("Room %u replacement is invalid: %s",
                          replacements[i].room_id, status.message()));
    }
  }
 
  DungeonStreamWritePlan plan;
  plan.layout = inventory.layout;
  plan.source_size = inventory.source_size;
  plan.source_crc32 = inventory.source_crc32;
  plan.mode = DungeonStreamWriteMode::kCopyOnWrite;
  if (plan.layout.kind == DungeonStreamKind::kObject &&
      static_cast<uint64_t>(kDoorPointers) +
              static_cast<uint64_t>(plan.layout.pointer_count) * 3 >
          plan.source_size) {
    return absl::OutOfRangeError(
        "Object door-pointer table is outside the source ROM");
  }
  std::vector<DungeonStreamPcRange> free = inventory.allocatable_free_intervals;
  const uint32_t pointer_width = PointerWidth(plan.layout.pointer_encoding);
  for (const auto& replacement : replacements) {
    const uint32_t size =
        static_cast<uint32_t>(replacement.encoded_stream.size());
    auto address = FindFirstFit(free, plan.layout, size);
    if (!address.ok()) {
      return address.status();
    }
    auto pointer_bytes = EncodePointer(plan.layout, *address);
    if (!pointer_bytes.ok()) {
      return pointer_bytes.status();
    }
 
    plan.payload_writes.push_back(
        {replacement.room_id, *address, replacement.encoded_stream});
    plan.pointer_writes.push_back(
        {replacement.room_id,
         plan.layout.pointer_table_pc + replacement.room_id * pointer_width,
         std::move(*pointer_bytes)});
    if (plan.layout.kind == DungeonStreamKind::kObject) {
      auto door_offset = ObjectDoorListOffset(replacement.encoded_stream);
      if (!door_offset.ok()) {
        return door_offset.status();
      }
      auto door_pointer = EncodePointer(plan.layout, *address + *door_offset);
      if (!door_pointer.ok()) {
        return door_pointer.status();
      }
      plan.auxiliary_pointer_writes.push_back(
          {replacement.room_id, kDoorPointers + replacement.room_id * 3,
           std::move(*door_pointer)});
    }
    ConsumeInterval(&free, {*address, *address + size});
  }
  return plan;
}
 
absl::StatusOr<DungeonStreamWritePlan> PlanDungeonStreamRepack(
    const DungeonStreamInventory& inventory,
    const std::vector<DungeonStreamReplacement>& requested_replacements) {
  if (!inventory.ok()) {
    return absl::FailedPreconditionError(
        "Cannot repack streams from an inventory with stream issues");
  }
  if (inventory.layout.kind != DungeonStreamKind::kPotItem ||
      inventory.layout.pointer_encoding !=
          DungeonPointerEncoding::kFixedBank16) {
    return absl::InvalidArgumentError(
        "Repack-all currently supports only fixed-bank pot-item streams");
  }
  if (inventory.layout.pointer_count != kNumberOfRooms) {
    return absl::InvalidArgumentError(absl::StrFormat(
        "Pot-item repack requires exactly %d pointers", kNumberOfRooms));
  }
  if (inventory.layout.allocation_ranges.size() != 1) {
    return absl::InvalidArgumentError(
        "Pot-item repack requires exactly one normalized allocation range");
  }
  if (inventory.streams.size() != inventory.layout.pointer_count) {
    return absl::FailedPreconditionError(
        "Pot-item inventory does not cover every pointer-table entry");
  }
 
  std::vector<std::vector<uint8_t>> logical_streams(
      inventory.layout.pointer_count);
  std::vector<bool> seen_rooms(inventory.layout.pointer_count, false);
  for (const DungeonStreamRecord& record : inventory.streams) {
    if (!record.valid || record.room_id >= inventory.layout.pointer_count ||
        seen_rooms[record.room_id] || record.encoded_stream.empty() ||
        record.encoded_stream.size() != record.size()) {
      return absl::FailedPreconditionError(
          "Pot-item inventory contains an incomplete logical stream snapshot");
    }
    seen_rooms[record.room_id] = true;
    logical_streams[record.room_id] = record.encoded_stream;
  }
  if (std::find(seen_rooms.begin(), seen_rooms.end(), false) !=
      seen_rooms.end()) {
    return absl::FailedPreconditionError(
        "Pot-item inventory is missing a room stream snapshot");
  }
 
  std::vector<DungeonStreamReplacement> replacements = requested_replacements;
  std::sort(replacements.begin(), replacements.end(),
            [](const auto& a, const auto& b) { return a.room_id < b.room_id; });
  for (size_t i = 0; i < replacements.size(); ++i) {
    const DungeonStreamReplacement& replacement = replacements[i];
    if (replacement.room_id >= inventory.layout.pointer_count) {
      return absl::OutOfRangeError("Replacement room ID is out of range");
    }
    if (i > 0 && replacements[i - 1].room_id == replacement.room_id) {
      return absl::InvalidArgumentError("Replacement room IDs must be unique");
    }
    const absl::Status status = ValidateCompleteEncodedStream(
        inventory.layout.kind, replacement.encoded_stream);
    if (!status.ok()) {
      return absl::InvalidArgumentError(
          absl::StrFormat("Room %u replacement is invalid: %s",
                          replacement.room_id, status.message()));
    }
    logical_streams[replacement.room_id] = replacement.encoded_stream;
  }
 
  const uint32_t bank_begin = SnesToPc(
      (static_cast<uint32_t>(inventory.layout.pointer_bank) << 16) | 0x8000u);
  const uint32_t bank_end = bank_begin + kLoRomBankSize;
  uint64_t available_bytes = 0;
  for (const DungeonStreamPcRange& range : inventory.layout.allocation_ranges) {
    if (range.begin < bank_begin || range.end > bank_end) {
      return absl::InvalidArgumentError(absl::StrFormat(
          "Pot-item repack range [0x%06X,0x%06X) crosses or lies outside "
          "fixed pointer bank 0x%02X",
          range.begin, range.end, inventory.layout.pointer_bank));
    }
    available_bytes += static_cast<uint64_t>(range.end) - range.begin;
  }
 
  struct RepackGroup {
    uint32_t owner_room = 0;
    std::vector<uint8_t> bytes;
    std::vector<uint32_t> room_ids;
  };
  std::map<std::vector<uint8_t>, std::vector<uint32_t>> rooms_by_payload;
  for (uint32_t room_id = 0; room_id < inventory.layout.pointer_count;
       ++room_id) {
    rooms_by_payload[logical_streams[room_id]].push_back(room_id);
  }
  std::vector<RepackGroup> groups;
  groups.reserve(rooms_by_payload.size());
  uint64_t required_bytes = 0;
  for (auto& [bytes, room_ids] : rooms_by_payload) {
    required_bytes += bytes.size();
    groups.push_back({room_ids.front(), std::move(bytes), std::move(room_ids)});
  }
  if (required_bytes > available_bytes) {
    return absl::ResourceExhaustedError(
        absl::StrCat("Pot-item repack needs ", required_bytes,
                     " bytes but declared ranges provide ", available_bytes));
  }
  std::sort(groups.begin(), groups.end(), [](const auto& a, const auto& b) {
    return a.owner_room < b.owner_room;
  });
 
  DungeonStreamWritePlan plan;
  plan.layout = inventory.layout;
  plan.source_size = inventory.source_size;
  plan.source_crc32 = inventory.source_crc32;
  plan.mode = DungeonStreamWriteMode::kRepackAll;
  plan.payload_writes.reserve(groups.size());
  plan.pointer_writes.reserve(inventory.layout.pointer_count);
 
  std::vector<uint32_t> target_by_room(inventory.layout.pointer_count, 0);
  uint32_t next_address = inventory.layout.allocation_ranges.front().begin;
  for (const RepackGroup& group : groups) {
    const uint32_t address = next_address;
    plan.payload_writes.push_back({group.owner_room, address, group.bytes});
    for (const uint32_t room_id : group.room_ids) {
      target_by_room[room_id] = address;
    }
    next_address += static_cast<uint32_t>(group.bytes.size());
  }
 
  const uint32_t pointer_width =
      PointerWidth(inventory.layout.pointer_encoding);
  for (uint32_t room_id = 0; room_id < inventory.layout.pointer_count;
       ++room_id) {
    ASSIGN_OR_RETURN(std::vector<uint8_t> pointer,
                     EncodePointer(inventory.layout, target_by_room[room_id]));
    plan.pointer_writes.push_back(
        {room_id, inventory.layout.pointer_table_pc + room_id * pointer_width,
         std::move(pointer)});
  }
  return plan;
}
 
absl::Status ApplyDungeonStreamWritePlan(Rom* rom,
                                         const DungeonStreamWritePlan& plan) {
  if (rom == nullptr || !rom->is_loaded()) {
    return absl::InvalidArgumentError("ROM not loaded");
  }
  if (rom->size() != plan.source_size) {
    return absl::AbortedError("Dungeon stream plan source size is stale");
  }
  const uint32_t current_crc =
      util::CalculateCrc32(rom->data(), static_cast<size_t>(rom->size()));
  if (current_crc != plan.source_crc32) {
    return absl::AbortedError(absl::StrFormat(
        "Dungeon stream plan is stale (source CRC %08X, current CRC %08X)",
        plan.source_crc32, current_crc));
  }
 
  auto inventory = InventoryDungeonStreams(*rom, plan.layout);
  if (!inventory.ok()) {
    return inventory.status();
  }
  auto validation = ValidatePlanAgainstInventory(plan, *inventory);
  if (!validation.ok()) {
    return validation;
  }
 
  yaze::rom::WriteFence write_fence;
  auto allow_writes = [&](const std::vector<DungeonStreamWrite>& writes,
                          const char* label) -> absl::Status {
    for (const auto& write : writes) {
      const uint64_t end =
          static_cast<uint64_t>(write.address) + write.bytes.size();
      if (end > std::numeric_limits<uint32_t>::max()) {
        return absl::OutOfRangeError("Dungeon stream write range overflows");
      }
      RETURN_IF_ERROR(
          write_fence.Allow(write.address, static_cast<uint32_t>(end), label));
    }
    return absl::OkStatus();
  };
  RETURN_IF_ERROR(allow_writes(plan.payload_writes, "DungeonStreamPayload"));
  RETURN_IF_ERROR(allow_writes(plan.pointer_writes, "DungeonStreamPointer"));
  RETURN_IF_ERROR(allow_writes(plan.auxiliary_pointer_writes,
                               "DungeonStreamAuxiliaryPointer"));
  yaze::rom::ScopedWriteFence write_scope(rom, &write_fence);
 
  const std::vector<uint8_t> snapshot = rom->vector();
  const bool was_dirty = rom->dirty();
  auto rollback = [&]() {
    rom->mutable_vector() = snapshot;
    rom->set_dirty(was_dirty);
  };
 
  for (const auto& write : plan.payload_writes) {
    auto status =
        rom->WriteVector(static_cast<int>(write.address), write.bytes);
    if (!status.ok()) {
      rollback();
      return status;
    }
  }
  for (const auto& write : plan.pointer_writes) {
    auto status =
        rom->WriteVector(static_cast<int>(write.address), write.bytes);
    if (!status.ok()) {
      rollback();
      return status;
    }
  }
  for (const auto& write : plan.auxiliary_pointer_writes) {
    auto status =
        rom->WriteVector(static_cast<int>(write.address), write.bytes);
    if (!status.ok()) {
      rollback();
      return status;
    }
  }
  return absl::OkStatus();
}
 
}  // namespace yaze::zelda3