// Package erofs reads and creates EROFS filesystem images.
//
// # Reading
//
// Use [Open] to read an existing EROFS image through Go's standard [fs.FS]
// interface:
//
//	img, err := erofs.Open(f)
//	data, err := fs.ReadFile(img, "etc/hostname")
//
// # Writing
//
// Use [Create] to build a new EROFS image. Entries can be added one at a
// time, or bulk-copied from any [fs.FS] via [Writer.CopyFrom]:
//
//	w := erofs.Create(outFile)
//	w.CopyFrom(srcFS)
//	w.Close()
//
// For metadata-only images that reference data in an external source
// (e.g. for container layer indexing), pass [MetadataOnly] to CopyFrom:
//
//	w := erofs.Create(outFile)
//	w.CopyFrom(srcFS, erofs.MetadataOnly())
//	w.Close()
package erofs

import (
	"bufio"
	"bytes"
	"cmp"
	"encoding/binary"
	"errors"
	"fmt"
	"io"
	"io/fs"
	"path"
	"slices"
	"sync"
	"time"

	"github.com/erofs/go-erofs/internal/disk"
)

// Errors
var (
	// ErrInvalid occurs when an invalid value is detected in the erofs data.
	// Whether this invalid data is the result of corruption or bad input
	// is up to the caller to decide.
	// This error may be wrapped with more details.
	ErrInvalid = fs.ErrInvalid

	// ErrInvalidSuperblock occurs when the super block could not be validated
	// when initially loading the erofs input. Unlike other corruption cases,
	// invalid super block should be returned immediately
	ErrInvalidSuperblock = fmt.Errorf("invalid super block: %w", ErrInvalid)

	// ErrNotImplemented is returned when a feature is known but not implemented
	// yet by this library
	ErrNotImplemented = errors.New("not implemented")

	// ErrNotDirectory is returned when a path component is not a directory.
	ErrNotDirectory = errors.New("not a directory")

	// ErrIsDirectory is returned when an operation expected a file but found
	// a directory.
	ErrIsDirectory = errors.New("is a directory")

	// ErrLoop is returned when too many symlinks are encountered during
	// path resolution.
	ErrLoop = fmt.Errorf("too many symlinks: %w", ErrInvalid)
)

// Stat is the raw erofs stat data returned by Sys() on [fs.FileInfo] values.
// It is a plain data struct analogous to [syscall.Stat_t].
//
// For cross-platform fs.FS compatibility, callers should prefer
// type-asserting the [fs.FileInfo] to accessor interfaces rather
// than inspecting Stat fields directly. The returned [fs.FileInfo]
// implements the following single-method interfaces:
//
//	Ownership:  UID() uint32, GID() uint32
//	InodeInfo:  Ino() uint64, Nlink() uint64
//	DeviceInfo: Rdev() uint64
//	Xattrs:     GetAllXattr() map[string]string, GetXattr(string) (string, bool)
type Stat struct {
	Mode        fs.FileMode
	Size        int64
	InodeLayout uint8
	Rdev        uint32
	Ino         int64
	UID         uint32
	GID         uint32
	Mtime       uint64
	MtimeNs     uint32
	Nlink       int
	Xattrs      map[string]string
}

// holeOffset is the sentinel value for DataRange.Offset that marks a hole
// (a sparse region of zeros) rather than backed device data.
const holeOffset int64 = -1

// DataRange describes one entry in the complete logical layout of a file's
// content. A slice of DataRange values returned by [fileInfo.DataRange]
// covers the file from logical byte 0 to logical byte [fs.FileInfo.Size]-1
// in order, with no gaps or overlaps.
//
// The sum of all Size values in the slice must equal the file size exactly.
// A slice whose sizes do not sum to the file size is invalid.
//
// Each entry is either a data entry or a hole entry:
//
//   - A data entry has Offset >= 0. The bytes at [Offset, Offset+Size) in
//     Device are the file's content verbatim — uncompressed, unreferenced
//     by transformation.
//   - A hole entry has Offset == -1. It represents Size bytes of zeros at the
//     current logical position. Device is ignored for hole entries.
//
// Compressed data should not be represented as a DataRange. When a source
// FS contains compressed files, it should not provide DataRange() []DataRange
// for those files (or should return nil). In full-image mode CopyFrom will
// fall back to reading through Open(), which decompresses transparently, and
// write the decompressed data into the output image. In MetadataOnly mode
// there is no such fallback: files without DataRange() (or pre-built chunks)
// are stored as chunk-based inodes with no physical mappings (all holes).
type DataRange struct {
	Device uint16 // device index (0 for the device assigned by CopyFrom); ignored for holes
	Offset int64  // byte offset in the device, or -1 for a hole entry
	Size   int64  // byte length of this entry
}

type options struct {
	extraDevices []io.ReaderAt
}

// OpenOpt is an option for configuring the EROFS reader
type OpenOpt func(*options)

// Deprecated: Use [OpenOpt] instead, will be removed in 0.3
type Opt = OpenOpt

// WithExtraDevices specifies additional devices to read
// chunk data from
func WithExtraDevices(devices ...io.ReaderAt) OpenOpt {
	return func(o *options) {
		o.extraDevices = append(o.extraDevices, devices...)
	}
}

// Open returns a FileSystem reading from the given ReaderAt.
// The ReaderAt must be a valid EROFS block file.
// No additional memory mapping is done and must be handled by
// the caller.
func Open(r io.ReaderAt, opts ...OpenOpt) (fs.FS, error) {
	o := options{}
	for _, opt := range opts {
		opt(&o)
	}
	var superBlock [disk.SizeSuperBlock]byte
	n, err := r.ReadAt(superBlock[:], disk.SuperBlockOffset)
	if err != nil {
		return nil, err
	}

	if n != disk.SizeSuperBlock {
		return nil, fmt.Errorf("invalid super block: read %d bytes", n)
	}

	i := image{
		meta: r,
	}
	if err = decodeSuperBlock(superBlock, &i.sb); err != nil {
		return nil, err
	}
	// The maximum reasonable filesystem block size is 64k, which is
	// the largest supported page size of aarch64 platforms.
	if i.sb.BlkSizeBits < 9 || i.sb.BlkSizeBits > 16 {
		return nil, fmt.Errorf("unsupported block size bits %d: %w", i.sb.BlkSizeBits, ErrInvalidSuperblock)
	}
	unknownFeat := i.sb.FeatureIncompat &^ disk.FeatureIncompatAll
	if unknownFeat != 0 {
		return nil, fmt.Errorf("unsupported incompatible feature 0x%x: %w", unknownFeat, ErrNotImplemented)
	}
	ondiskExtraDevices := uint32(0)
	if i.sb.FeatureIncompat&disk.FeatureIncompatDeviceTable != 0 {
		ondiskExtraDevices = uint32(i.sb.ExtraDevices)
		// Calculate device_id_mask
		// sbi->device_id_mask = roundup_pow_of_two(ondisk_extradevs + 1) - 1;
		i.deviceIDMask = uint16(roundupPowerOfTwo(uint32(i.sb.ExtraDevices)+1) - 1)
	}

	if int(ondiskExtraDevices) != len(o.extraDevices) {
		// TODO: Provide options for skipping extra devices and error out later?
		return nil, fmt.Errorf("invalid super block: extra devices count %d does not match provided %d", ondiskExtraDevices, len(o.extraDevices))
	}

	// Parse the device table if extra devices exist
	if ondiskExtraDevices > 0 {
		devTableOffset := int64(i.sb.DevtSlotOff) * disk.SizeDeviceSlot
		i.devices = make([]deviceInfo, int(ondiskExtraDevices))
		for idx := range i.devices {
			var slotBuf [disk.SizeDeviceSlot]byte
			offset := devTableOffset + int64(idx)*disk.SizeDeviceSlot
			if _, err := r.ReadAt(slotBuf[:], offset); err != nil {
				return nil, fmt.Errorf("failed to read device slot %d at offset %d: %w", idx, offset, err)
			}
			var slot disk.DeviceSlot
			if _, err := binary.Decode(slotBuf[:], binary.LittleEndian, &slot); err != nil {
				return nil, fmt.Errorf("failed to decode device slot %d: %w", idx, err)
			}
			i.devices[idx] = deviceInfo{
				device:        o.extraDevices[idx],
				mappedBlkAddr: slot.MappedBlkAddr,
				blocks:        slot.Blocks,
			}
		}
	}

	// Error out filesystems with unsupported compressed inodes
	if i.sb.FeatureIncompat&disk.FeatureIncompatLZ4_0Padding != 0 ||
		i.sb.ComprAlgs != 0 {
		return nil, fmt.Errorf("unsupported compressed filesystem (FeatureIncompat=0x%x, ComprAlgs=0x%x): %w",
			i.sb.FeatureIncompat, i.sb.ComprAlgs, ErrNotImplemented)
	}

	i.blkPool.New = func() any {
		return &block{
			buf: make([]byte, 1<<i.sb.BlkSizeBits),
		}
	}

	return &i, nil
}

// Deprecated: Use [Open] instead, will be removed in 0.3
func EroFS(r io.ReaderAt, opts ...Opt) (fs.FS, error) {
	return Open(r, opts...)
}

// roundupPowerOfTwo rounds v up to the next power of two.
func roundupPowerOfTwo(v uint32) uint32 {
	v--
	v |= v >> 1
	v |= v >> 2
	v |= v >> 4
	v |= v >> 8
	v |= v >> 16
	v++
	return v
}

// deviceInfo holds the parsed mapped address range for a device table entry.
type deviceInfo struct {
	device        io.ReaderAt
	mappedBlkAddr uint32 // starting mapped block address
	blocks        uint32 // total block count for this device
}

type image struct {
	sb disk.SuperBlock

	meta         io.ReaderAt
	devices      []deviceInfo // parsed device table entries
	deviceIDMask uint16
	blkPool      sync.Pool
	longPrefixes []string // cached long xattr prefixes
	prefixesOnce sync.Once
	prefixesErr  error
}

// start physical offset of the separate metadata zone
func (img *image) metaStartPos() int64 {
	return int64(img.sb.MetaBlkAddr) << int64(img.sb.BlkSizeBits)
}

// maxReadFileSize is the maximum file size that ReadFile will allocate.
// ReadFile is intended for small files; for larger files, callers should
// use Open and io.Copy. 128 MiB is generous for typical use (configs,
// manifests, symlink targets, etc.) while guarding against
// unexpectedly large files.
const maxReadFileSize = 128 << 20 // 128 MiB

// mapDev resolves map->m_bdev and map->m_pa mapping for go-erofs.
// It works similarly to erofs_map_dev in the linux kernel.
func (img *image) mapDev(deviceID uint16, pa int64) (io.ReaderAt, int64, error) {
	if deviceID > 0 {
		if int(deviceID) > len(img.devices) {
			return nil, 0, fmt.Errorf("invalid device id %d", deviceID)
		}
		return img.devices[deviceID-1].device, pa, nil
	}

	if len(img.devices) > 0 {
		for _, dev := range img.devices {
			if dev.mappedBlkAddr == 0 {
				continue
			}

			startOff := int64(dev.mappedBlkAddr) << img.sb.BlkSizeBits
			length := int64(dev.blocks) << img.sb.BlkSizeBits

			if pa >= startOff && pa < startOff+length {
				return dev.device, pa - startOff, nil
			}
		}
	}

	return img.meta, pa, nil
}

// blockSize returns the filesystem block size.
func (img *image) blockSize() uint32 { return 1 << img.sb.BlkSizeBits }

// buildTime returns the build timestamp from the superblock.
func (img *image) buildTime() uint64 { return img.sb.BuildTime }

// deviceBlocks returns the total block count across all extra devices.
// Each device's block count is reported at the device's native block size
// (matching the superblock block size).
func (img *image) deviceBlocks() []uint64 {
	if len(img.devices) == 0 {
		return nil
	}
	blocks := make([]uint64, len(img.devices))
	for i, d := range img.devices {
		blocks[i] = uint64(d.blocks)
	}
	return blocks
}

// openDirect returns an io.Reader for a file's data that reads directly
// from the underlying metadata reader, bypassing the block-at-a-time
// Read path. Returns nil if direct reading is not possible (e.g.
// chunk-based or compressed files).
func (img *image) openDirect(ino *inode) io.Reader {
	if ino.size <= 0 {
		return nil
	}
	blockSize := int64(1 << img.sb.BlkSizeBits)
	switch ino.inodeLayout {
	case disk.LayoutFlatPlain:
		// Data is contiguous starting at dataBlkAddr.
		dataOffset := int64(ino.inodeData) << img.sb.BlkSizeBits
		return io.NewSectionReader(img.meta, dataOffset, ino.size)
	case disk.LayoutFlatInline:
		// Last block is inline after the inode; earlier blocks at dataBlkAddr.
		// Only use direct read for single-block files (all data inline).
		if ino.size > blockSize {
			return nil
		}
		inodeAddr := img.metaStartPos() + int64(ino.nid)*disk.SizeInodeCompact
		trailingAddr := inodeAddr + ino.flatDataOffset()
		return io.NewSectionReader(img.meta, trailingAddr, ino.size)
	case disk.LayoutChunkBased:
		// Chunk-based files store data at the physical block addresses
		// listed in the chunk index. For contiguous single-device files,
		// the data is laid out consecutively and can be read directly.
		chunkFmt := uint16(ino.inodeData)
		if chunkFmt&disk.LayoutChunkFormatIndexes == 0 {
			return nil
		}
		chunkBits := img.sb.BlkSizeBits + uint8(chunkFmt&disk.LayoutChunkFormatBits)
		nchunks := int((ino.size-1)>>chunkBits) + 1

		// Read chunk index entries to check contiguity.
		inodeStart := img.metaStartPos() + int64(ino.nid)*disk.SizeInodeCompact
		baseOffset := inodeStart + ino.flatDataOffset()
		if baseOffset%8 != 0 {
			baseOffset = (baseOffset + 7) & ^int64(7)
		}
		needed := int64(nchunks) * int64(disk.SizeChunkIndex)
		if needed > maxChunkIndexBytes {
			return nil
		}
		idxBuf := make([]byte, needed)
		if _, err := img.meta.ReadAt(idxBuf, baseOffset); err != nil {
			return nil
		}

		// Check that all chunks are contiguous on the same device.
		var startBlock uint64
		var deviceID uint16
		for i := range nchunks {
			off := i * disk.SizeChunkIndex
			blkLo := binary.LittleEndian.Uint32(idxBuf[off+4 : off+8])
			if ^blkLo == 0 {
				return nil // hole
			}
			blkHi := binary.LittleEndian.Uint16(idxBuf[off : off+2])
			did := binary.LittleEndian.Uint16(idxBuf[off+2:off+4]) & img.deviceIDMask
			phys := (uint64(blkHi) << 32) | uint64(blkLo)

			blocksPerChunk := uint64(1 << (chunkBits - img.sb.BlkSizeBits))
			if i == 0 {
				startBlock = phys
				deviceID = did
			} else {
				expected := startBlock + uint64(i)*blocksPerChunk
				if phys != expected || did != deviceID {
					return nil // not contiguous or different device
				}
			}
		}

		// All chunks contiguous — resolve through the device.
		dataOffset := int64(startBlock) << img.sb.BlkSizeBits
		if deviceID > 0 && int(deviceID) <= len(img.devices) {
			return io.NewSectionReader(img.devices[deviceID-1].device, dataOffset, ino.size)
		}
		return io.NewSectionReader(img.meta, dataOffset, ino.size)
	default:
		return nil
	}
}

func (img *image) readMetadata(r io.Reader) ([]byte, error) {
	// - A 2-byte little-endian length field, which is aligned to a 4-byte boundary
	// - The length bytes of payload data
	var lenBuf [2]byte
	if _, err := io.ReadFull(r, lenBuf[:]); err != nil {
		return nil, fmt.Errorf("failed to read metadata length %v: %w", lenBuf, err)
	}

	dataLen := int(binary.LittleEndian.Uint16(lenBuf[:]))
	if dataLen < 1 {
		dataLen = 65536
	}

	data := make([]byte, dataLen)
	if _, err := io.ReadFull(r, data); err != nil {
		return nil, fmt.Errorf("failed to read metadata payload: %w", err)
	}

	// Align to 4-byte boundary except for hitting EOF
	totalLen := 2 + dataLen
	if rem := totalLen % 4; rem != 0 {
		padding := int64(4 - rem)
		if _, err := io.CopyN(io.Discard, r, padding); err != nil &&
			!errors.Is(err, io.EOF) &&
			!errors.Is(err, io.ErrUnexpectedEOF) {
			return nil, fmt.Errorf("failed to discard padding of %d bytes: %w", padding, err)
		}
	}
	return data, nil
}

// loadLongPrefixes loads and caches the long xattr prefixes from the packed inode
// using the regular inode read logic to handle compressed/non-inline data.
//
// Long xattr name prefixes are used to optimize storage of xattrs with common
// prefixes. They are stored sequentially in a special "packed inode" or
// "meta inode".
// See: https://docs.kernel.org/filesystems/erofs.html#extended-attributes
func (img *image) loadLongPrefixes() error {
	img.prefixesOnce.Do(func() {
		if img.sb.XattrPrefixCount == 0 {
			return
		}

		var r io.Reader

		// Calculate the starting offset. XattrPrefixStart is defined in the
		// superblock as being in units of 4 bytes from the start of the corresponding inode
		startOffset := int64(img.sb.XattrPrefixStart) * 4

		if (img.sb.FeatureIncompat&disk.FeatureIncompatFragments != 0) && img.sb.PackedNid > 0 {
			// The packed inode (identified by PackedNid in the superblock) is a special
			// inode used for shared data and metadata.
			// We use ".packed" as a descriptive name for this internal inode.
			f := &file{
				img:   img,
				name:  ".packed",
				nid:   img.sb.PackedNid,
				ftype: 0, // regular file
			}

			// Read inode info to determine size and layout
			fi, err := f.readInfo()
			if err != nil {
				img.prefixesErr = fmt.Errorf("failed to read packed inode: %w", err)
				return
			}

			if startOffset > fi.size {
				img.prefixesErr = fmt.Errorf("xattr prefix start offset %d exceeds packed inode size %d", startOffset, fi.size)
				return
			}

			// Set the read offset
			f.offset = startOffset
			r = bufio.NewReader(f)
		} else {
			// FIXME(hsiangkao): should avoid hacky 1<<32 here since we don't care about the end
			r = io.NewSectionReader(img.meta, startOffset, 1<<32)
		}

		img.longPrefixes = make([]string, img.sb.XattrPrefixCount)
		for i := 0; i < int(img.sb.XattrPrefixCount); i++ {
			data, err := img.readMetadata(r)
			if err != nil {
				img.prefixesErr =
					fmt.Errorf("failed to read long xattr prefix %d: %w", i, err)
				return
			}

			// First byte is the base_index referencing a standard xattr prefix
			baseIndex := xattrIndex(data[0])

			// Remaining bytes are the infix to be appended to the base prefix
			infix := string(data[1:])

			// Construct full prefix: base prefix + infix
			img.longPrefixes[i] = baseIndex.String() + infix
		}
	})
	return img.prefixesErr
}

// getLongPrefix returns the long xattr prefix at the given index
func (img *image) getLongPrefix(index uint8) (string, error) {
	if err := img.loadLongPrefixes(); err != nil {
		return "", err
	}

	if int(index) >= len(img.longPrefixes) {
		return "", fmt.Errorf("long xattr prefix index %d out of range (max %d)", index, len(img.longPrefixes)-1)
	}

	return img.longPrefixes[index], nil
}

func (img *image) loadAt(addr, size int64) (*block, error) {
	blkSize := int64(1 << img.sb.BlkSizeBits)
	if size > blkSize {
		size = blkSize
	}

	b := img.getBlock()
	if n, err := img.meta.ReadAt(b.buf[:size], addr); err != nil {
		img.putBlock(b)
		return nil, fmt.Errorf("failed to read %d bytes at %d: %w", size, addr, err)
	} else {
		b.offset = 0
		b.end = int32(n)
	}

	return b, nil
}

// loadBlock loads the block with the given data
func (img *image) loadBlock(fi *inode, pos int64) (*block, error) {
	nblocks := calculateBlocks(img.sb.BlkSizeBits, fi.size)
	bn := int(pos >> int(img.sb.BlkSizeBits))
	if bn >= nblocks {
		return nil, fmt.Errorf("block position larger than number of blocks for inode: %w", io.EOF)
	}
	var addr int64
	blockSize := int(1 << img.sb.BlkSizeBits)
	blockOffset := 0
	blockEnd := blockSize
	switch fi.inodeLayout {
	case disk.LayoutFlatPlain:
		// flat plain has no holes
		addr = int64(int(fi.inodeData)+bn) << img.sb.BlkSizeBits
		blockOffset = int(pos % int64(blockSize))
		if bn == nblocks-1 {
			blockEnd = int(fi.size - int64(bn)*int64(1<<img.sb.BlkSizeBits))
		}
	case disk.LayoutFlatInline:
		// If on the last block, validate
		if bn == nblocks-1 {
			addr = img.metaStartPos() + int64(fi.nid*disk.SizeInodeCompact)
			// Move to the data offset from the start of the inode
			addr += fi.flatDataOffset()

			// Get the offset from the start of the block
			blockOffset = int(addr & int64(blockSize-1))

			// Move addr to start of block
			addr = (addr & ^int64(blockSize-1))

			// Compute end of inline data within the block (before adjusting
			// blockOffset for the read position).
			blockEnd = int(fi.size-int64(bn*blockSize)) + blockOffset

			// Move the offset within the block based on position within file
			blockOffset += int(pos - int64(bn<<int(img.sb.BlkSizeBits)))

			// Ensure the last block is not exceeded
			if blockEnd > blockSize {
				return nil, fmt.Errorf("inline data cross block boundary for nid %d: %w", fi.nid, ErrInvalid)
			}
		} else {
			addr = int64(int(fi.inodeData)+bn) << img.sb.BlkSizeBits
			blockOffset = int(pos % int64(blockSize))
		}
	case disk.LayoutChunkBased:
		// first 2 le bytes for format, second 2 bytes are reserved
		format := uint16(fi.inodeData)
		if format&disk.LayoutChunkFormat48Bit != 0 {
			return nil, fmt.Errorf("48-bit chunk format for nid %d: %w", fi.nid, ErrNotImplemented)
		}
		if format&^(disk.LayoutChunkFormatBits|disk.LayoutChunkFormatIndexes) != 0 {
			return nil, fmt.Errorf("unsupported chunk format %x for nid %d: %w", format, fi.nid, ErrInvalid)
		}

		chunkbits := img.sb.BlkSizeBits + uint8(format&disk.LayoutChunkFormatBits)
		chunkn := int((fi.size-1)>>chunkbits) + 1
		cn := int(pos >> chunkbits)

		if cn >= chunkn {
			return nil, fmt.Errorf("chunk format does not fit into allocated bytes for nid %d: %w", fi.nid, ErrInvalid)
		}

		inodeStart := img.metaStartPos() + int64(fi.nid*disk.SizeInodeCompact)
		baseOffset := inodeStart + fi.flatDataOffset()

		unit := 4
		if format&disk.LayoutChunkFormatIndexes == disk.LayoutChunkFormatIndexes {
			unit = 8
			// Align to 8 bytes
			if baseOffset%8 != 0 {
				baseOffset = (baseOffset + 7) & ^int64(7)
			}
		}

		entryPos := baseOffset + int64(cn*unit)
		var entryBuf [8]byte
		if n, err := img.meta.ReadAt(entryBuf[:unit], entryPos); err != nil {
			return nil, fmt.Errorf("failed to read chunk entry at %d: %w", entryPos, err)
		} else if n != unit {
			return nil, fmt.Errorf("short read of chunk entry at %d: read %d bytes, expected %d", entryPos, n, unit)
		}

		var addr int64
		var deviceID uint16

		if unit == 8 {
			startBlkLo := binary.LittleEndian.Uint32(entryBuf[4:8])
			if ^startBlkLo == 0 {
				addr = -1
			} else {
				addr = int64(startBlkLo) << img.sb.BlkSizeBits
				deviceID = binary.LittleEndian.Uint16(entryBuf[2:4]) & img.deviceIDMask
			}
		} else {
			rawAddr := binary.LittleEndian.Uint32(entryBuf[:4])
			if ^rawAddr == 0 {
				addr = -1
			} else {
				addr = int64(rawAddr) << img.sb.BlkSizeBits
			}
		}

		if bn == nblocks-1 {
			blockEnd = int(fi.size - int64(bn)*int64(1<<img.sb.BlkSizeBits))
		}
		blockOffset = int(pos % int64(blockSize))

		if addr == -1 {
			// Null address, return new zero filled block
			return &block{
				buf:    make([]byte, 1<<img.sb.BlkSizeBits),
				offset: int32(blockOffset),
				end:    int32(blockEnd),
			}, nil
		}

		// Add block offset within chunk
		blockPos := int64(bn) << img.sb.BlkSizeBits
		if blockPos > 0 {
			addr += (blockPos - int64(cn<<chunkbits))
		}

		reader, mappedAddr, err := img.mapDev(deviceID, addr)
		if err != nil {
			return nil, fmt.Errorf("failed to map device for nid %d: %w", fi.nid, err)
		}
		addr = mappedAddr

		if blockOffset < 0 || blockEnd > blockSize || blockOffset >= blockEnd {
			return nil, fmt.Errorf("invalid chunk block bounds [%d:%d] for nid %d: %w", blockOffset, blockEnd, fi.nid, ErrInvalid)
		}
		b := img.getBlock()
		if n, err := reader.ReadAt(b.buf[blockOffset:blockEnd], addr+int64(blockOffset)); err != nil {
			img.putBlock(b)
			return nil, fmt.Errorf("failed to read block for nid %d: %w", fi.nid, err)
		} else if n != (blockEnd - blockOffset) {
			img.putBlock(b)
			return nil, fmt.Errorf("failed to read full block for nid %d: %w", fi.nid, ErrInvalid)
		}
		b.offset = int32(blockOffset)
		b.end = int32(blockEnd)
		return b, nil
	case disk.LayoutCompressedFull, disk.LayoutCompressedCompact:
		return nil, fmt.Errorf("inode layout (%d) for %d: %w", fi.inodeLayout, fi.nid, ErrNotImplemented)
	default:
		return nil, fmt.Errorf("inode layout (%d) for %d: %w", fi.inodeLayout, fi.nid, ErrInvalid)
	}
	if blockOffset < 0 || blockEnd > blockSize || blockOffset >= blockEnd {
		return nil, fmt.Errorf("invalid block bounds [%d:%d] for nid %d: %w", blockOffset, blockEnd, fi.nid, ErrInvalid)
	}

	b := img.getBlock()
	b.offset = int32(blockOffset)
	b.end = int32(blockEnd)
	if n, err := img.meta.ReadAt(b.bytes(), addr+int64(blockOffset)); err != nil {
		img.putBlock(b)
		return nil, fmt.Errorf("failed to read block for nid %d: %w", fi.nid, err)
	} else if n != blockEnd-blockOffset {
		img.putBlock(b)
		return nil, fmt.Errorf("failed to read full block for nid %d: %w, expected %d, actual %d", fi.nid, ErrInvalid, blockEnd-blockOffset, n)
	}
	return b, nil
}

func (img *image) getBlock() *block {
	return img.blkPool.Get().(*block)
}

// putBlock returns a block after complete so its
// buffer can be put back into the buffer pool
func (img *image) putBlock(b *block) {
	img.blkPool.Put(b)
}

const maxSymlinks = 255

// maxSymlinkSize is the maximum size of a symlink target.
// Linux PATH_MAX is 4096; we use the same limit.
const maxSymlinkSize = 4096

// readLink reads the symlink target for the given nid.
func (i *image) readLink(nid uint64, name string) (string, error) {
	f := &file{img: i, name: name, nid: nid, ftype: fs.ModeSymlink}
	fi, err := f.readInfo()
	if err != nil {
		return "", err
	}
	if fi.size < 0 || fi.size > maxSymlinkSize {
		return "", fmt.Errorf("symlink target size %d out of range: %w", fi.size, ErrInvalid)
	}
	buf := make([]byte, fi.size)
	if fi.size > 0 {
		if _, err = f.Read(buf); err != nil && err != io.EOF {
			return "", err
		}
	}
	return string(buf), nil
}

// resolve cleans the path and walks directory entries to find the target inode.
// When follow is true, symlinks are followed (including the final component).
// When follow is false, the final component is not followed (for Lstat/ReadLink).
// Intermediate symlinks are always followed.
func (i *image) resolve(op, name string, follow bool) (nid uint64, ftype fs.FileMode, basename string, err error) {
	original := name
	if path.IsAbs(name) {
		name = name[1:]
	}
	name = path.Clean(name)
	if name == "." {
		name = ""
	}

	nid = uint64(i.sb.RootNid)
	ftype = fs.ModeDir

	// curPath tracks the full resolved path of the current directory
	// so that relative symlink targets can be resolved correctly.
	linksFollowed := 0
	curPath := ""
	basename = name
	for name != "" {
		var sep int
		for sep < len(name) && name[sep] != '/' {
			sep++
		}
		var rest string
		if sep < len(name) {
			basename = name[:sep]
			rest = name[sep+1:]
		} else {
			basename = name
			rest = ""
		}

		if ftype != fs.ModeDir {
			return 0, 0, "", &fs.PathError{Op: op, Path: original, Err: ErrNotDirectory}
		}
		d := &dir{
			file: file{
				img:   i,
				name:  basename,
				nid:   nid,
				ftype: ftype,
			},
		}
		entNid, entFtype, err := d.lookup(basename)
		if err != nil {
			return 0, 0, "", &fs.PathError{Op: op, Path: original, Err: err}
		}
		nid = entNid
		ftype = entFtype & fs.ModeType

		// Follow symlinks for intermediate components always,
		// and for the final component only when follow is true.
		isFinal := rest == ""
		if ftype&fs.ModeSymlink != 0 && (follow || !isFinal) {
			linksFollowed++
			if linksFollowed > maxSymlinks {
				return 0, 0, "", &fs.PathError{Op: op, Path: original, Err: ErrLoop}
			}
			target, err := i.readLink(nid, basename)
			if err != nil {
				return 0, 0, "", err
			}
			// Prepend the symlink target to the remaining path
			if rest != "" {
				target = target + "/" + rest
			}
			// Resolve relative to the parent directory's full path
			if !path.IsAbs(target) {
				target = curPath + "/" + target
			}
			// Clean and re-resolve from root
			target = path.Clean(target)
			if len(target) > 0 && target[0] == '/' {
				target = target[1:]
			}
			nid = uint64(i.sb.RootNid)
			ftype = fs.ModeDir
			curPath = ""
			name = target
			if name == "." {
				name = ""
			}
			basename = name
			continue
		}

		if curPath == "" {
			curPath = basename
		} else {
			curPath = curPath + "/" + basename
		}
		name = rest
	}

	if basename == "" {
		basename = original
	}
	return nid, ftype, basename, nil
}

func (i *image) Open(name string) (fs.File, error) {
	nid, ftype, basename, err := i.resolve("open", name, true)
	if err != nil {
		return nil, err
	}
	b := file{img: i, name: basename, nid: nid, ftype: ftype}
	if ftype.IsDir() {
		return &dir{file: b}, nil
	}
	return &b, nil
}

func (i *image) Stat(name string) (fs.FileInfo, error) {
	nid, ftype, basename, err := i.resolve("stat", name, true)
	if err != nil {
		return nil, err
	}
	f := &file{img: i, name: basename, nid: nid, ftype: ftype}
	return f.statInfo()
}

// ReadFile reads the named file and returns its contents.
// Files larger than maxReadFileSize (128 MiB) are rejected;
// use Open and io.Copy for larger files.
func (i *image) ReadFile(name string) ([]byte, error) {
	nid, ftype, basename, err := i.resolve("readfile", name, true)
	if err != nil {
		return nil, err
	}
	if ftype.IsDir() {
		return nil, &fs.PathError{Op: "read", Path: name, Err: ErrIsDirectory}
	}
	f := &file{img: i, name: basename, nid: nid, ftype: ftype}
	fi, err := f.readInfo()
	if err != nil {
		return nil, err
	}
	if fi.size < 0 || fi.size > maxReadFileSize {
		return nil, fmt.Errorf("file size %d exceeds ReadFile limit %d; use Open and io.Copy for large files: %w", fi.size, int64(maxReadFileSize), ErrInvalid)
	}
	buf := make([]byte, fi.size)
	if fi.size > 0 {
		if _, err = f.Read(buf); err != nil && err != io.EOF {
			return nil, err
		}
	}
	return buf, nil
}

func (i *image) ReadDir(name string) ([]fs.DirEntry, error) {
	nid, ftype, basename, err := i.resolve("readdir", name, true)
	if err != nil {
		return nil, err
	}
	if !ftype.IsDir() {
		return nil, &fs.PathError{Op: "readdir", Path: name, Err: ErrNotDirectory}
	}
	d := &dir{file: file{img: i, name: basename, nid: nid, ftype: ftype}}
	entries, err := d.ReadDir(-1)
	if err != nil {
		return nil, err
	}
	slices.SortFunc(entries, func(a, b fs.DirEntry) int {
		return cmp.Compare(a.Name(), b.Name())
	})
	return entries, nil
}

func (i *image) ReadLink(name string) (string, error) {
	nid, ftype, basename, err := i.resolve("readlink", name, false)
	if err != nil {
		return "", err
	}
	if ftype&fs.ModeSymlink == 0 {
		return "", &fs.PathError{Op: "readlink", Path: name, Err: fs.ErrInvalid}
	}
	return i.readLink(nid, basename)
}

func (i *image) Lstat(name string) (fs.FileInfo, error) {
	nid, ftype, basename, err := i.resolve("lstat", name, false)
	if err != nil {
		return nil, err
	}
	f := &file{img: i, name: basename, nid: nid, ftype: ftype}
	return f.statInfo()
}

type file struct {
	img   *image
	name  string
	nid   uint64
	ftype fs.FileMode

	// Mutable fields, open file should not be accessed concurrently
	offset int64  // current offset for read operations
	info   *inode // cached inode
}

func (b *file) readInfo() (ino *inode, err error) {
	if b.info != nil {
		return b.info, nil
	}

	addr := b.img.metaStartPos() + int64(b.nid*disk.SizeInodeCompact)
	blkSize := int32(1 << b.img.sb.BlkSizeBits)
	blk := b.img.getBlock()
	blk.offset = int32(addr & int64(blkSize-1))
	blk.end = blkSize
	if blk.end-blk.offset < disk.SizeInodeExtended {
		// Use buffer starting from beginning of inode, do not use the position
		// in the block since an extended inode may span multiple blocks
		blk.offset = 0
		blk.end = disk.SizeInodeExtended
	}

	defer func() {
		v := recover()
		if v != nil {
			err = fmt.Errorf("file format error: %v", v)
		}
		if err != nil {
			b.img.putBlock(blk)
		}

	}()

	buf := blk.bytes()
	_, err = b.img.meta.ReadAt(buf, addr)
	if err != nil {
		return nil, err
	}

	var format, xcnt uint16
	if _, err = binary.Decode(buf[:2], binary.LittleEndian, &format); err != nil {
		return nil, err
	}

	layout := uint8((format & 0x0E) >> 1)
	if format&0x01 == 0 {
		var di disk.InodeCompact
		if _, err := binary.Decode(buf[:disk.SizeInodeCompact], binary.LittleEndian, &di); err != nil {
			return nil, err
		}
		b.info = &inode{
			name:        b.name,
			nid:         b.nid,
			icsize:      disk.SizeInodeCompact,
			inodeLayout: layout,
			inodeData:   di.InodeData,
			size:        int64(di.Size),
			mode:        (fs.FileMode(di.Mode) & ^fs.ModeType) | b.ftype,
			rawMode:     di.Mode,
			uid:         uint32(di.UID),
			gid:         uint32(di.GID),
			nlink:       int(di.Nlink),
			mtime:       b.img.sb.BuildTime,
			mtimeNs:     b.img.sb.BuildTimeNs,
		}
		xcnt = di.XattrCount
	} else {
		var di disk.InodeExtended
		if _, err = binary.Decode(buf[:disk.SizeInodeExtended], binary.LittleEndian, &di); err != nil {
			return nil, err
		}
		b.info = &inode{
			name:        b.name,
			nid:         b.nid,
			icsize:      disk.SizeInodeExtended,
			inodeLayout: layout,
			inodeData:   di.InodeData,
			size:        int64(di.Size),
			mode:        (fs.FileMode(di.Mode) & ^fs.ModeType) | b.ftype,
			rawMode:     di.Mode,
			uid:         di.UID,
			gid:         di.GID,
			nlink:       int(di.Nlink),
			mtime:       di.Mtime,
			mtimeNs:     di.MtimeNs,
		}
		xcnt = di.XattrCount
	}

	if xcnt > 0 {
		b.info.xsize = int(xcnt-1)*disk.SizeXattrEntry + disk.SizeXattrBodyHeader
	}

	switch {
	case b.info.inodeLayout == disk.LayoutFlatPlain || b.info.size == 0 || blk.end != blkSize:
		b.img.putBlock(blk)
	default:
		// If the inode has trailing data used later, cache it
		b.info.cached = blk
	}
	return b.info, nil
}

// statInfo reads the inode and builds a fileInfo with full stat data
// including extended attributes. The cached block is released since
// stat callers do not need inline data.
func (b *file) statInfo() (*fileInfo, error) {
	ino, err := b.readInfo()
	if err != nil {
		return nil, err
	}
	fi := &fileInfo{
		name:    ino.name,
		size:    ino.size,
		mode:    ino.mode,
		mtime:   ino.mtime,
		mtimeNs: ino.mtimeNs,
		stat: &Stat{
			Mode:        disk.EroFSModeToGoFileMode(ino.rawMode),
			Size:        ino.size,
			InodeLayout: ino.inodeLayout,
			Ino:         int64(ino.nid),
			Rdev:        disk.RdevFromMode(ino.rawMode, ino.inodeData),
			UID:         ino.uid,
			GID:         ino.gid,
			Nlink:       ino.nlink,
			Mtime:       ino.mtime,
			MtimeNs:     ino.mtimeNs,
		},
	}
	if ino.xsize > 0 {
		if err := loadXattrs(b, fi.stat); err != nil {
			return nil, err
		}
	}
	// Build data ranges for regular files.
	// Flat layouts are cheap (no I/O) — compute eagerly.
	// Chunk-based layout requires a ReadAt on the image; defer until needed.
	if ino.mode.IsRegular() && ino.size > 0 {
		if ino.inodeLayout == disk.LayoutChunkBased {
			// Capture a snapshot of the fields buildChunkDataRanges needs.
			// We must not capture ino by pointer: the caller may reuse it,
			// and cached block is released below.
			inoCopy := *ino
			inoCopy.cached = nil
			img := b.img
			fi.rangesLoader = func() []DataRange {
				f := &file{img: img}
				return f.buildChunkDataRanges(&inoCopy)
			}
		} else {
			fi.dataRanges = b.buildDataRanges(ino)
		}
	}
	// Release cached block - stat callers don't need inline data
	if ino.cached != nil {
		b.img.putBlock(ino.cached)
		ino.cached = nil
	}
	return fi, nil
}

// buildDataRanges computes the physical data ranges for a regular file.
func (b *file) buildDataRanges(ino *inode) []DataRange {
	blockSize := int64(1 << b.img.sb.BlkSizeBits)
	switch ino.inodeLayout {
	case disk.LayoutFlatPlain:
		dataOffset := int64(ino.inodeData) << b.img.sb.BlkSizeBits
		return []DataRange{{Device: 0, Offset: dataOffset, Size: ino.size}}
	case disk.LayoutFlatInline:
		inodeAddr := b.img.metaStartPos() + int64(ino.nid)*disk.SizeInodeCompact
		trailingAddr := inodeAddr + ino.flatDataOffset()
		if ino.size <= blockSize {
			return []DataRange{{Device: 0, Offset: trailingAddr, Size: ino.size}}
		}
		// Multi-block inline: earlier full blocks at dataBlkAddr, last block inline.
		// headSize is the number of complete blocks before the inline tail, in bytes.
		// ino.inodeData is the starting block address, not a block count.
		headSize := ((ino.size - 1) / blockSize) * blockSize
		tailSize := ino.size - headSize
		var ranges []DataRange
		if headSize > 0 {
			dataOffset := int64(ino.inodeData) << b.img.sb.BlkSizeBits
			ranges = append(ranges, DataRange{Device: 0, Offset: dataOffset, Size: headSize})
		}
		ranges = append(ranges, DataRange{Device: 0, Offset: trailingAddr, Size: tailSize})
		return ranges
	case disk.LayoutChunkBased:
		return b.buildChunkDataRanges(ino)
	}
	return nil
}

// maxChunkIndexBytes is an upper bound on the chunk-index table we will
// allocate for a single file. 64 MiB covers ~8 M chunks; no real EROFS image
// should approach this, and it prevents allocation bombs from corrupt images.
const maxChunkIndexBytes = 64 << 20 // 64 MiB

// buildChunkDataRanges parses chunk indexes into DataRange entries covering
// the complete logical layout of the file. The returned slice satisfies the
// DataRange contract: entries are in logical-file order and their sizes sum
// to ino.size exactly.
//
// Null/hole chunks are emitted as DataRange{Offset: -1, Size: ...} entries.
// Consecutive null chunks coalesce into a single hole entry.
// Adjacent data chunks that are physically contiguous on the same device
// merge into one entry. Data chunks never merge across a hole boundary.
//
// The final entry (data or hole) has its Size trimmed to the file-tail length
// so the invariant sum(Size) == ino.size holds precisely.
func (b *file) buildChunkDataRanges(ino *inode) []DataRange {
	chunkFmt := uint16(ino.inodeData)
	if chunkFmt&disk.LayoutChunkFormatIndexes == 0 {
		return nil
	}
	// 48-bit chunk addressing is not yet implemented; the null-chunk sentinel
	// (blkLo == 0xFFFFFFFF) is only unambiguous in 32-bit address mode.
	if chunkFmt&disk.LayoutChunkFormat48Bit != 0 {
		return nil
	}
	chunkBits := b.img.sb.BlkSizeBits + uint8(chunkFmt&disk.LayoutChunkFormatBits)
	nchunks := int((ino.size-1)>>chunkBits) + 1
	chunkSize := int64(1) << chunkBits

	inodeStart := b.img.metaStartPos() + int64(ino.nid)*disk.SizeInodeCompact
	baseOffset := inodeStart + ino.flatDataOffset()
	if baseOffset%8 != 0 {
		baseOffset = (baseOffset + 7) & ^int64(7)
	}
	needed := int64(nchunks) * int64(disk.SizeChunkIndex)
	if needed > maxChunkIndexBytes {
		return nil
	}
	idxBuf := make([]byte, needed)
	if _, err := b.img.meta.ReadAt(idxBuf, baseOffset); err != nil {
		return nil
	}

	var ranges []DataRange
	for i := range nchunks {
		// Size of this logical chunk: full chunkSize for all but the last.
		size := chunkSize
		if i == nchunks-1 {
			size = ino.size - int64(i)*chunkSize
		}

		off := i * disk.SizeChunkIndex
		blkLo := binary.LittleEndian.Uint32(idxBuf[off+4 : off+8])
		if ^blkLo == 0 {
			// Null/hole chunk: coalesce with a preceding hole if possible.
			if len(ranges) > 0 && ranges[len(ranges)-1].Offset == holeOffset {
				ranges[len(ranges)-1].Size += size
			} else {
				ranges = append(ranges, DataRange{Offset: holeOffset, Size: size})
			}
			continue
		}

		blkHi := binary.LittleEndian.Uint16(idxBuf[off : off+2])
		deviceID := binary.LittleEndian.Uint16(idxBuf[off+2:off+4]) & b.img.deviceIDMask
		phys := (uint64(blkHi) << 32) | uint64(blkLo)
		byteOffset := int64(phys) << b.img.sb.BlkSizeBits

		// Merge with the previous entry if it is a data range that is
		// physically contiguous on the same device.
		if len(ranges) > 0 {
			prev := &ranges[len(ranges)-1]
			if prev.Offset != holeOffset && prev.Device == deviceID && prev.Offset+prev.Size == byteOffset {
				prev.Size += size
				continue
			}
		}
		ranges = append(ranges, DataRange{Device: deviceID, Offset: byteOffset, Size: size})
	}
	return ranges
}

func (b *file) Stat() (fs.FileInfo, error) {
	return b.statInfo()
}

func (b *file) Read(p []byte) (int, error) {
	fi, err := b.readInfo()
	if err != nil {
		return 0, err
	}

	var n int
	for len(p) > 0 {
		if b.offset >= fi.size {
			return n, io.EOF
		}
		blk, err := b.img.loadBlock(fi, b.offset)
		if err != nil {
			if errors.Is(err, io.EOF) {
				err = io.EOF
				b.offset += int64(n)
			}
			return n, err
		}
		buf := blk.bytes()
		copied := copy(p, buf)
		n += copied
		p = p[copied:]
		b.offset += int64(copied)

		b.img.putBlock(blk)
	}
	return n, nil
}

func (b *file) Close() error {
	if b.info != nil && b.info.cached != nil {
		b.img.putBlock(b.info.cached)
		b.info.cached = nil
	}
	return nil
}

type direntry struct {
	file
}

func (d *direntry) Name() string {
	return d.name
}

func (d *direntry) IsDir() bool {
	return d.ftype.IsDir()
}

func (d *direntry) Type() fs.FileMode {
	return d.ftype
}

func (d *direntry) Info() (fs.FileInfo, error) {
	return d.statInfo()
}

type dir struct {
	file

	// bn is the current block to read from (relative to file start)
	bn int

	// consumed is how many have been returned in the current block
	consumed uint16
}

func (d *dir) ReadDir(n int) ([]fs.DirEntry, error) {
	fi, err := d.readInfo()
	if err != nil {
		return nil, fmt.Errorf("readInfo failed: %w", err)
	}

	var ents []fs.DirEntry
	pos := int64(d.bn << d.img.sb.BlkSizeBits)
	for pos < fi.size {
		b, err := d.img.loadBlock(fi, pos)
		if err != nil {
			if errors.Is(err, io.EOF) {
				break
			}
			return nil, err
		}
		buf := b.bytes()
		if len(buf) < 12 {
			d.img.putBlock(b)
			break
		}

		var dirents [2]disk.Dirent

		readN, err := binary.Decode(buf[:12], binary.LittleEndian, &dirents[0])
		if err != nil {
			d.img.putBlock(b)
			return nil, fmt.Errorf("decode failed: %w", err)
		}
		if readN != 12 {
			d.img.putBlock(b)
			return nil, errors.New("invalid dirent: not fully decoded")
		}

		entryN := dirents[0].NameOff / disk.SizeDirent
		bufLen := len(buf)

		// Validate that NameOff is within bounds and dirent entries fit.
		if int(dirents[0].NameOff) > bufLen || entryN == 0 {
			d.img.putBlock(b)
			return ents, fmt.Errorf("invalid dirent name offset %d (buf size %d): %w", dirents[0].NameOff, bufLen, ErrInvalid)
		}

		for i := uint16(0); i < entryN; i++ {
			var name string
			if i < entryN-1 {
				start := int(disk.SizeDirent) * (int(i) + 1)
				if start+int(disk.SizeDirent) > bufLen {
					d.img.putBlock(b)
					return ents, fmt.Errorf("dirent entry %d exceeds block: %w", i+1, ErrInvalid)
				}
				readN, err := binary.Decode(buf[start:start+int(disk.SizeDirent)], binary.LittleEndian, &dirents[1])
				if err != nil {
					d.img.putBlock(b)
					return nil, fmt.Errorf("decode failed: %w", err)
				}
				if readN != 12 {
					d.img.putBlock(b)
					return nil, errors.New("invalid dirent: not fully decoded")
				}
				if int(dirents[0].NameOff) > bufLen || int(dirents[1].NameOff) > bufLen || dirents[1].NameOff < dirents[0].NameOff {
					d.img.putBlock(b)
					return ents, fmt.Errorf("invalid dirent name offset range [%d:%d] (buf size %d): %w",
						dirents[0].NameOff, dirents[1].NameOff, bufLen, ErrInvalid)
				}
				name = string(buf[dirents[0].NameOff:dirents[1].NameOff])
			} else {
				if int(dirents[0].NameOff) > bufLen {
					d.img.putBlock(b)
					return ents, fmt.Errorf("invalid dirent name offset %d (buf size %d): %w", dirents[0].NameOff, bufLen, ErrInvalid)
				}
				// The last entry name extends to end of block;
				// trim any NUL padding.
				raw := buf[dirents[0].NameOff:]
				if j := bytes.IndexByte(raw, 0); j >= 0 {
					raw = raw[:j]
				}
				name = string(raw)
			}

			if i >= d.consumed && name != "." && name != ".." {
				f := file{
					img:   d.img,
					name:  name,
					nid:   dirents[0].Nid,
					ftype: disk.EroFSFtypeToFileMode(dirents[0].FileType),
				}
				ents = append(ents, &direntry{f})
				d.consumed = i + 1

				if n > 0 && len(ents) == n {
					if i == entryN-1 {
						d.consumed = 0
						d.bn++
					}
					d.img.putBlock(b)
					return ents, nil
				}
			}

			// Rotate next to current
			dirents[0] = dirents[1]
		}

		d.img.putBlock(b)
		d.consumed = 0
		d.bn++
		pos = int64(d.bn << d.img.sb.BlkSizeBits)
	}

	// Per fs.ReadDirFile contract: when n > 0 and we've reached the end
	// of the directory, return io.EOF. When n <= 0, return all entries
	// without io.EOF.
	if n > 0 {
		return ents, io.EOF
	}
	return ents, nil
}

// lookup searches for a directory entry by name using binary search.
// EROFS directories are sorted by name both within and across blocks.
// A cross-block binary search locates the correct block, then an
// intra-block binary search finds the entry.
// Returns the nid and file type if found, or fs.ErrNotExist if not.
func (d *dir) lookup(target string) (uint64, fs.FileMode, error) {
	fi, err := d.readInfo()
	if err != nil {
		return 0, 0, fmt.Errorf("readInfo failed: %w", err)
	}

	targetBytes := []byte(target)
	blkSize := int64(1 << d.img.sb.BlkSizeBits)
	nblocks := int((fi.size + blkSize - 1) / blkSize)

	// Binary search across blocks: compare target against the first
	// entry of each block to find which block may contain the target.
	// The last loaded block is retained to avoid reloading it for the
	// intra-block search.
	var lastBlk *block
	lastIdx := -1
	lo, hi := 0, nblocks
	for lo < hi {
		mid := lo + (hi-lo)/2
		pos := int64(mid) * blkSize
		b, err := d.img.loadBlock(fi, pos)
		if err != nil {
			if errors.Is(err, io.EOF) {
				hi = mid
				continue
			}
			if lastBlk != nil {
				d.img.putBlock(lastBlk)
			}
			return 0, 0, err
		}
		buf := b.bytes()
		firstName, err := blockFirstName(buf)
		if err != nil {
			d.img.putBlock(b)
			if lastBlk != nil {
				d.img.putBlock(lastBlk)
			}
			return 0, 0, err
		}

		if bytes.Compare(firstName, targetBytes) <= 0 {
			// This block's first entry <= target; keep it as candidate.
			if lastBlk != nil {
				d.img.putBlock(lastBlk)
			}
			lastBlk = b
			lastIdx = mid
			lo = mid + 1
		} else {
			d.img.putBlock(b)
			hi = mid
		}
	}

	// lastIdx is the last block whose first entry <= target.
	// The target must be in that block if it exists.
	if lastIdx < 0 {
		return 0, 0, fs.ErrNotExist
	}

	buf := lastBlk.bytes()
	nid, ftype, err := lookupBlock(buf, targetBytes)
	d.img.putBlock(lastBlk)
	return nid, ftype, err
}

// blockFirstName returns the name of the first entry in a directory block.
func blockFirstName(buf []byte) ([]byte, error) {
	if len(buf) < disk.SizeDirent {
		return nil, fmt.Errorf("directory block too small: %w", ErrInvalid)
	}
	var first disk.Dirent
	if _, err := binary.Decode(buf[:disk.SizeDirent], binary.LittleEndian, &first); err != nil {
		return nil, fmt.Errorf("decode failed: %w", err)
	}
	entryN := first.NameOff / disk.SizeDirent
	if entryN == 0 || int(first.NameOff) > len(buf) {
		return nil, fmt.Errorf("invalid name offset %d: %w", first.NameOff, ErrInvalid)
	}
	var nameEnd uint16
	if entryN > 1 {
		nextOff := int(disk.SizeDirent) + 8
		if nextOff+2 > len(buf) {
			return nil, fmt.Errorf("next dirent name offset out of range: %w", ErrInvalid)
		}
		nameEnd = binary.LittleEndian.Uint16(buf[nextOff:])
	} else {
		nameEnd = uint16(len(buf))
	}
	if first.NameOff > nameEnd || int(nameEnd) > len(buf) {
		return nil, fmt.Errorf("name range [%d:%d] out of bounds: %w", first.NameOff, nameEnd, ErrInvalid)
	}
	name := buf[first.NameOff:nameEnd]
	// Trim NUL terminator if present
	if i := bytes.IndexByte(name, 0); i >= 0 {
		name = name[:i]
	}
	return name, nil
}

// blockDirent decodes the dirent at index i from buf and returns the
// name bytes for that entry. entryN is the total number of entries.
func blockDirent(buf []byte, i, entryN uint16) (disk.Dirent, []byte, error) {
	var de disk.Dirent
	off := int(disk.SizeDirent * i)
	if off+disk.SizeDirent > len(buf) {
		return de, nil, fmt.Errorf("dirent %d offset %d out of range: %w", i, off, ErrInvalid)
	}
	if _, err := binary.Decode(buf[off:off+disk.SizeDirent], binary.LittleEndian, &de); err != nil {
		return de, nil, fmt.Errorf("decode dirent %d failed: %w", i, err)
	}
	var nameEnd uint16
	if i < entryN-1 {
		nextOff := int(disk.SizeDirent*(i+1)) + 8
		if nextOff+2 > len(buf) {
			return de, nil, fmt.Errorf("dirent %d next name offset out of range: %w", i, ErrInvalid)
		}
		nameEnd = binary.LittleEndian.Uint16(buf[nextOff:])
	} else {
		nameEnd = uint16(len(buf))
	}
	if de.NameOff > nameEnd || int(nameEnd) > len(buf) {
		return de, nil, fmt.Errorf("dirent %d name range [%d:%d] out of bounds: %w", i, de.NameOff, nameEnd, ErrInvalid)
	}
	name := buf[de.NameOff:nameEnd]
	// The last entry name may be NUL-terminated before the end of the block.
	if i == entryN-1 {
		if j := bytes.IndexByte(name, 0); j >= 0 {
			name = name[:j]
		}
	}
	return de, name, nil
}

// lookupBlock searches a single directory block for the target name
// using binary search.
func lookupBlock(buf, target []byte) (uint64, fs.FileMode, error) {
	if len(buf) < disk.SizeDirent {
		return 0, 0, fmt.Errorf("directory block too small: %w", ErrInvalid)
	}
	var first disk.Dirent
	if _, err := binary.Decode(buf[:disk.SizeDirent], binary.LittleEndian, &first); err != nil {
		return 0, 0, fmt.Errorf("decode failed: %w", err)
	}
	if first.NameOff%disk.SizeDirent != 0 {
		return 0, 0, fmt.Errorf("invalid name offset %d not aligned to dirent size: %w", first.NameOff, ErrInvalid)
	}
	entryN := first.NameOff / disk.SizeDirent
	if int(first.NameOff) > len(buf) {
		return 0, 0, fmt.Errorf("name offset %d exceeds block size %d: %w", first.NameOff, len(buf), ErrInvalid)
	}

	lo, hi := uint16(0), entryN
	for lo < hi {
		mid := lo + (hi-lo)/2
		de, name, err := blockDirent(buf, mid, entryN)
		if err != nil {
			return 0, 0, err
		}
		switch bytes.Compare(name, target) {
		case 0:
			return de.Nid, disk.EroFSFtypeToFileMode(de.FileType), nil
		case -1:
			lo = mid + 1
		default:
			hi = mid
		}
	}
	return 0, 0, fs.ErrNotExist
}

// inode holds the parsed on-disk inode data needed for I/O operations.
// It is an internal type and is not returned to callers directly.
type inode struct {
	name        string
	nid         uint64
	icsize      int8
	xsize       int
	inodeLayout uint8
	inodeData   uint32
	size        int64
	mode        fs.FileMode
	rawMode     uint16
	uid         uint32
	gid         uint32
	nlink       int
	mtime       uint64
	mtimeNs     uint32
	cached      *block
}

func (ino *inode) flatDataOffset() int64 {
	// inode core size + xattr size
	return int64(ino.icsize) + int64(ino.xsize)
}

// fileInfo implements [fs.FileInfo] and provides extended metadata
// via type-assertable accessor methods. Callers can extract
// Unix-style metadata without importing this package:
//
//	if u, ok := fi.(interface{ UID() uint32 }); ok { uid = u.UID() }
type fileInfo struct {
	name       string
	size       int64
	mode       fs.FileMode
	mtime      uint64
	mtimeNs    uint32
	stat       *Stat
	dataRanges []DataRange

	// rangesOnce and rangesLoader support lazy computation of data ranges
	// for chunk-based files (LayoutChunkBased). The loader performs a ReadAt
	// to parse the chunk index, so it is deferred until the caller actually
	// calls DataRange(). For flat layouts (FlatPlain, FlatInline), ranges
	// are computed eagerly at stat time since they require no I/O.
	rangesOnce   sync.Once
	rangesLoader func() []DataRange
}

func (fi *fileInfo) Name() string       { return fi.name }
func (fi *fileInfo) Size() int64        { return fi.size }
func (fi *fileInfo) Mode() fs.FileMode  { return fi.mode }
func (fi *fileInfo) IsDir() bool        { return fi.mode.IsDir() }
func (fi *fileInfo) Sys() any           { return fi.stat }
func (fi *fileInfo) ModTime() time.Time { return time.Unix(int64(fi.mtime), int64(fi.mtimeNs)) }
func (fi *fileInfo) UID() uint32        { return fi.stat.UID }
func (fi *fileInfo) GID() uint32        { return fi.stat.GID }
func (fi *fileInfo) Ino() uint64        { return uint64(fi.stat.Ino) }
func (fi *fileInfo) Nlink() uint64      { return uint64(fi.stat.Nlink) }
func (fi *fileInfo) Rdev() uint64       { return uint64(fi.stat.Rdev) }

// DataRange returns the physical data ranges for this file's uncompressed
// content. Returns nil for compressed files, directories, symlinks, and
// other non-regular entries.
func (fi *fileInfo) DataRange() []DataRange {
	if fi.rangesLoader != nil {
		fi.rangesOnce.Do(func() {
			fi.dataRanges = fi.rangesLoader()
		})
	}
	return fi.dataRanges
}

// GetAllXattr returns all extended attributes.
func (fi *fileInfo) GetAllXattr() map[string]string { return fi.stat.Xattrs }

// GetXattr returns the value of a single extended attribute.
func (fi *fileInfo) GetXattr(name string) (string, bool) {
	v, ok := fi.stat.Xattrs[name]
	return v, ok
}
func decodeSuperBlock(b [disk.SizeSuperBlock]byte, sb *disk.SuperBlock) error {
	n, err := binary.Decode(b[:], binary.LittleEndian, sb)
	if err != nil {
		return err
	}
	if n != disk.SizeSuperBlock {
		return fmt.Errorf("invalid super block: decoded %d bytes", n)
	}
	if sb.MagicNumber != disk.MagicNumber {
		return fmt.Errorf("invalid super block: invalid magic number %x", sb.MagicNumber)
	}
	return nil
}