from filetypes.base import *
import malcat
from filetypes.ISO import VolumeDescriptor, ExtendedTimestamp
import struct

def align(val, what, down=False):
    if val % what:
        if down:
            val -= val % what
        else:
            val += what - (val % what)
    return val


class CharacterSetSpecification(Struct):

    def parse(self):
        yield UInt8(name="CharacterSet", values=[
            ("CS0", 0),
            ("CS1", 1),
            ("CS2", 2),
            ("CS3", 3),
            ("CS4", 4),
            ("CS5", 5),
            ("CS6", 6),
            ("CS7", 7),
            ("CS8", 8),
        ])
        yield Bytes(63, name="Data")


class RegId(Struct):

    def parse(self):
        yield BitsField(
            Bit(name="Dirty"),
            Bit(name="Protected"),
            NullBits(6),
            name="Flags")
        yield String(23, zero_terminated=False, name="Identifier")
        yield Bytes(8, name="Suffix")


class DString(Struct):

    def __init__(self, size, *args, **kwargs):
        Struct.__init__(self, *args, **kwargs)
        self._size = size

    def parse(self):
        encoding = yield UInt8(name="Encoding")
        if encoding == 0x10:
            yield CStringUtf16be(max_size=self._size - 1, name="Value")
        elif encoding == 0x8:
            yield CStringUtf8(max_size=self._size - 1, name="Value")
        else:
            yield CString(max_size=self._size - 1, name="Value")
        if len(self) < self._size:
            yield Unused(self._size - len(self))


class Tag(Struct):

    def parse(self):
        yield UInt16(name="Identifier", values=[
            ("PRIMARY_VOLUME_DESCRIPTOR", 1),
            ("ANCHOR_VOLUME_DESCRIPTOR", 2),
            ("VOLUME_DESCRIPTOR_POINTER", 3),
            ("IMPLEMENTATION_USE_VOLUME_DESCRIPTOR", 4),
            ("PARTITION_DESCRIPTOR", 5),
            ("LOGICAL_VOLUME_DESCRIPTOR", 6),
            ("UNALLOCATED_SPACE_DESCRIPTOR", 7),
            ("TERMINATING_DESCRIPTOR", 8),
            ("LOGICAL_VOLUME_INTEGRITY_DESCRIPTOR", 9),
        ])
        yield UInt16(name="Version", comment="descriptor version")
        yield UInt8(name="Checksum")
        yield Unused(1)
        yield UInt16(name="SerialNumber")
        yield UInt16(name="Crc")
        yield UInt16(name="CrcLength")
        yield UInt32(name="TagLocation", comment="sector number")



class IcbTag(Struct):

    def parse(self):
        yield UInt32(name="PreviousEntries", comment="number of Direct Entries recorded in this ICB hierarchy prior to this entry")
        typ = yield UInt16(name="StrategyType", values=[
            ("NOT_SPECIFIED", 0),
            ("TYPE_1", 1),
            ("TYPE_2", 2),
            ("TYPE_3", 3),
            ("TYPE_4", 4),
        ])
        yield Bytes(2, name="StrategyParameters")
        yield UInt16(name="MaximumEntries", comment="maximum number of entries, including both direct and indirect, that may be recorded in this ICB")
        yield Unused(1)
        yield UInt8(name="FileType", values=[
            ("NOT_SPECIFIED", 0),
            ("UNALLOCATED", 1),
            ("INTEGRITY", 2),
            ("INDIRECT", 3),
            ("DIRECTORY", 4),
            ("BYTES", 5),
            ("BLOCK", 6),
            ("CHARACTER", 7),
            ("EXTRA_ATTRIBUTES", 8),
            ("FIFO", 9),
            ("SOCKET", 10),
            ("TERMINAL", 11),
            ("SYMLINK", 12),
            ("STREAMDIR", 13),
            ("META_FILE", 0xFA),
            ("META_MIRROR", 0xFB),
            ("META_BITMAP", 0xFC),
        ])
        yield LogicalBlockAddress(name="ParentLocation")
        yield BitsField(
            Bit(name="DescriptorType0"),
            Bit(name="DescriptorType1"),
            Bit(name="SortedDirectory"),
            Bit(name="NoReloc"),
            Bit(name="Archive"),
            Bit(name="SetUid"),
            Bit(name="SetGid"),
            Bit(name="Sticky"),
            Bit(name="Contiguous"),
            Bit(name="System"),
            Bit(name="Transformed"),
            Bit(name="MultiVersion"),
            Bit(name="Stream"),
            name="Flags")


class ExtentDescriptor(Struct):

    def parse(self):
        yield UInt32(name="Size", comment="length of the extent, in bytes, identified by the Location field")
        yield UInt32(name="Location", comment="location of the extent, as a logical sector number")


class LogicalBlockAddress(Struct):

    def parse(self):
        yield UInt32(name="LogicalBlockNumber")
        yield UInt16(name="PartitionReferenceNumber")


class ShortAllocationDescriptor(Struct):

    def parse(self):
        yield UInt32(name="Size", comment="length of the extent, in bytes, identified by the Location field")
        yield UInt32(name="Location", comment="location of the extent, as a logical sector number")


class ExtendedAllocationDescriptor(Struct):

    def parse(self):
        yield UInt32(name="Size", comment="length of the extent, in bytes, identified by the Location field")
        yield UInt32(name="RecordSize", comment="")
        yield UInt32(name="InformationSize", comment="")
        yield LogicalBlockAddress(name="Location", comment="location of the extent, as a logical sector number")
        yield Bytes(2, name="ImplementationUse")


class LongAllocationDescriptor(Struct):

    def parse(self):
        yield UInt32(name="Size", comment="length of the extent, in bytes, identified by the Location field")
        yield LogicalBlockAddress(name="Location", comment="location of the extent, as a logical sector number")
        yield Bytes(6, name="ImplementationUse")


class Descriptor(Struct):

    def parse(self):
        tag = yield Tag()
        yield Bytes(2048 - len(self), name="Data")


class PartitionVolumeDescriptor(Struct):

    def parse(self):
        tag = yield Tag()
        yield UInt32(name="VolumeDescriptorSequenceNumber")
        yield UInt32(name="PrimaryVolumeDescriptorNumber")
        yield DString(32, name="VolumeIdentifier")
        yield UInt16(name="VolumeSequenceNumber")
        yield UInt16(name="MaximumVolumeSequenceNumber")
        yield UInt16(name="InterchangeLevel")
        yield UInt16(name="MaximumInterchangeLevel")
        yield UInt32(name="CharacterSetList")
        yield UInt32(name="MaximumCharacterSetList")
        yield DString(128, name="VolumeSetIdentifier")
        yield CharacterSetSpecification(name="DescriptorCharacterSet")
        yield CharacterSetSpecification(name="ExplanatoryCharacterSet")
        yield ExtentDescriptor(name="VolumeAbstract")
        yield ExtentDescriptor(name="VolumeCopyrightNotice")
        yield RegId(name="ApplicationIdentifier")
        yield ExtendedTimestamp(name="RecordingTime")
        yield RegId(name="ImplementationIdentifier")
        yield Bytes(64, name="ImplementationUse")
        yield UInt32(name="PreviousVolumeDescriptorSequenceLocation")
        yield BitsField(
            Bit(name="Common"),
            NullBits(15),
            name="Flags")
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class AnchorVolumeDescriptor(Struct):

    def parse(self):
        tag = yield Tag()
        yield ExtentDescriptor(name="MainVolumeDescriptor")
        yield ExtentDescriptor(name="ReservedVolumeDescriptor")
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class SequenceVolumeDescriptor(Struct):

    def parse(self):
        tag = yield Tag()
        yield UInt32(name="VolumeDescriptorSequenceNumber")
        yield ExtentDescriptor(name="NextVolumeDescriptorSequence")
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class ImplementationUseDescriptor(Struct):

    def parse(self):
        tag = yield Tag()
        yield UInt32(name="VolumeDescriptorSequenceNumber")
        yield RegId(name="ImplementationIdentifier")
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class PartitionDescriptor(Struct):

    def parse(self):
        tag = yield Tag()
        yield UInt32(name="VolumeDescriptorSequenceNumber")
        yield BitsField(
            Bit(name="Allocation"),
            NullBits(15),
            name="Flags")
        yield UInt16(name="PartitionNumber")
        yield RegId(name="PartitionContent")
        yield Bytes(128, name="PartitionContentUse")
        yield UInt32(name="AccessType", values=[
            ("NOT_SPECIFIED", 0),
            ("READ_ONLY", 1),
            ("WRITE_ONCE", 2),
            ("REWRITEABLE", 3),
            ("OVERWRITEABLE", 4),
        ])
        yield UInt32(name="PartitionLocation")
        yield UInt32(name="PartitionSize")
        yield RegId(name="ImplementationIdentifier")
        yield Bytes(128, name="ImplementationUse")
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class PartitionMap(Struct):

    def parse(self):
        typ = yield UInt8(name="Type", values=[
            ("NOT_SPECIFIED", 0),
            ("TYPE_1", 1),
            ("TYPE_2", 2),
        ])
        sz = yield UInt8(name="Size")
        if typ == 1:
            yield UInt16(name="VolumeSequenceNumber")
            yield UInt16(name="PartitionNumber")
        elif typ == 2:
            yield Unused(2)
            id = yield RegId(name="PartitionTypeIdentifier")
            if id["Identifier"] == "*UDF Virtual Partition":
                yield UInt16(name="VolumeSequenceNumber")
                yield UInt16(name="PartitionNumber")
            if id["Identifier"] == "*UDF Metadata Partition":
                yield UInt16(name="VolumeSequenceNumber")
                yield UInt16(name="PartitionNumber")
                yield UInt32(name="MetadataFileLocation")
                yield UInt32(name="MetadataMirrorLocation")
                yield UInt32(name="MetadataBitmapLocation")
                yield UInt32(name="AllocationUnitSize")
                yield UInt16(name="AlignUnitSize")
                yield UInt8(name="Flags")
        if len(self) < sz:
            yield Bytes(sz - len(self), name="Data")


class LogicalVolumeDescriptor(Struct):

    def parse(self):
        tag = yield Tag()
        yield UInt32(name="VolumeDescriptorSequenceNumber")
        yield CharacterSetSpecification(name="DescriptorCharacterSet")
        yield DString(128, name="LogicalVolumeIdentifier")
        yield UInt32(name="BlockSize")
        yield RegId(name="DomainIdentifer")
        yield Bytes(16, name="LogicalVolumeContentUse")
        sz = yield UInt32(name="MapTableSize")
        num = yield UInt32(name="NumberOfPartitionMaps")
        yield RegId(name="ImplementationIdentifer")
        yield Bytes(128, name="ImplementationUse")
        yield ExtentDescriptor(name="IntegritySequence")
        for i in range(num):
            yield PartitionMap(name="PartitionMap.{}".format(i))
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class UnallocatedSpaceDescriptor(Struct):

    def parse(self):
        tag = yield Tag()
        yield UInt32(name="VolumeDescriptorSequenceNumber")
        num = yield UInt32(name="NumberOfAllocationDescriptor")
        if num:
            yield Array(num, ExtentDescriptor(), name="AllocationDescriptors")
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class TerminatingDescriptor(Struct):

    def parse(self):
        tag = yield Tag()
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class FileSetDescriptor(Struct):

    def parse(self):
        yield Tag()
        yield ExtendedTimestamp(name="RecordingTime")
        yield UInt16(name="InterchangeLevel")
        yield UInt16(name="MaximumInterchangeLevel")
        yield UInt32(name="CharacterSetList")
        yield UInt32(name="MaximumCharacterSetList")
        yield UInt32(name="FileSetNumber")
        yield UInt32(name="FileSetDescriptorNumber")
        yield CharacterSetSpecification(name="LogicalVolumeCharacterSet")
        yield DString(128, name="LogicalVolumeIdentifier")
        yield CharacterSetSpecification(name="FileSetCharacterSet")
        yield DString(32, name="FileSetIdentifier")
        yield DString(32, name="CopyrightFileIdentifier")
        yield DString(32, name="AbstractIdentifier")
        yield LongAllocationDescriptor(name="RootDirectory")
        yield RegId(name="DomainIdentifer")
        yield LongAllocationDescriptor(name="Next")
        yield LongAllocationDescriptor(name="SystemStreamDirectory")
        if len(self) < 2048:
            yield Unused(2048 - len(self))


class AllocationDescriptorsArray(Struct):

    def __init__(self, size, ad_class, *args, **kwargs):
        Struct.__init__(self, *args, **kwargs)
        self.__ad_class = ad_class
        self.__size = size

    def parse(self):
        while len(self) < self.__size:
            if self.__ad_class is None:
                raise FatalError("Wrong AllocationDescriptor type")
            yield self.__ad_class()


class FileEntryDescriptor(Struct):

    def parse(self):
        yield Tag()
        icb = yield IcbTag()
        yield UInt32(name="Uid")
        yield UInt32(name="Gid")
        yield UInt32(name="Permissions")
        yield UInt16(name="LinkCount")
        yield UInt8(name="RecordFormat")
        yield UInt8(name="RecordDisplayAttributes")
        yield UInt32(name="RecordSize")
        yield UInt64(name="InformationSize")
        yield UInt64(name="LogicalBlocksRecorded")
        yield ExtendedTimestamp(name="AccessTime")
        yield ExtendedTimestamp(name="ModificationTime")
        yield ExtendedTimestamp(name="AttributeTime")
        yield UInt32(name="Checkpoint")
        yield LongAllocationDescriptor(name="ExtendedAttributes")
        yield RegId(name="ImplementationIdentifier")
        yield UInt64(name="UniqueId")
        ea_sz = yield UInt32(name="ExtendedAttributesSize")
        ad_size = yield UInt32(name="AllocationDescriptorsSize")
        if ea_sz:
            yield Bytes(ea_sz, name="ExtendedAttributesContent")
        start = len(self)
        ad_type =  icb["Flags"]["DescriptorType0"] + icb["Flags"]["DescriptorType1"] * 2
        ad_class = {
            0: ShortAllocationDescriptor,
            1: LongAllocationDescriptor,
            2: ExtendedAllocationDescriptor,
            3: None
        }[ad_type]
        if ad_size and ad_class:
            yield AllocationDescriptorsArray(ad_size, ad_class, name="AllocationDescriptors")


class ExtendedFileEntryDescriptor(Struct):

    def parse(self):
        yield Tag()
        icb = yield IcbTag()
        yield UInt32(name="Uid")
        yield UInt32(name="Gid")
        yield UInt32(name="Permissions")
        yield UInt16(name="LinkCount")
        yield UInt8(name="RecordFormat")
        yield UInt8(name="RecordDisplayAttributes")
        yield UInt32(name="RecordSize")
        yield UInt64(name="InformationSize")
        yield UInt64(name="ObjectSize")
        yield UInt64(name="LogicalBlocksRecorded")
        yield ExtendedTimestamp(name="AccessTime")
        yield ExtendedTimestamp(name="ModificationTime")
        yield ExtendedTimestamp(name="CreationTime")
        yield ExtendedTimestamp(name="AttributeTime")
        yield UInt32(name="Checkpoint")
        yield Unused(4)
        yield LongAllocationDescriptor(name="ExtendedAttributes")
        yield LongAllocationDescriptor(name="StreamDirectory")
        yield RegId(name="ImplementationIdentifier")
        yield UInt64(name="UniqueId")
        ea_sz = yield UInt32(name="ExtendedAttributesSize")
        ad_size = yield UInt32(name="AllocationDescriptorsSize")
        if ea_sz:
            yield Bytes(ea_sz, name="ExtendedAttributesContent")
        start = len(self)
        ad_type =  icb["Flags"]["DescriptorType0"] + icb["Flags"]["DescriptorType1"] * 2
        ad_class = {
            0: ShortAllocationDescriptor,
            1: LongAllocationDescriptor,
            2: ExtendedAllocationDescriptor,
            3: None
        }[ad_type]
        if ad_size and ad_class:
            yield AllocationDescriptorsArray(ad_size, ad_class, name="AllocationDescriptors")            


class FileIdentifierDescriptor(Struct):

    def parse(self):
        yield Tag()
        yield UInt16(name="FileVersion")
        yield BitsField(
            Bit(name="Existence"),
            Bit(name="Directory"),
            Bit(name="Deleted"),
            Bit(name="Parent"),
            Bit(name="Metadata"),
            name="Characteristics")
        fi = yield UInt8(name="FileIdentifierSize")
        yield LongAllocationDescriptor(name="ICB")
        iu = yield UInt16(name="ImplementationUseSize")
        if iu:
            yield Bytes(iu, name="ImplementationUse")
        if fi:
            yield DString(fi, name="FileIdentifier")
        if len(self) % 4:
            yield Unused(4 - len(self) % 4)




KNOWN_DESCRIPTORS = {
    1: PartitionVolumeDescriptor,
    2: AnchorVolumeDescriptor,
    3: SequenceVolumeDescriptor,
    4: ImplementationUseDescriptor,
    5: PartitionDescriptor,
    6: LogicalVolumeDescriptor,
    7: UnallocatedSpaceDescriptor,
    8: TerminatingDescriptor,
    256: FileSetDescriptor,
    257: FileIdentifierDescriptor,
    261: FileEntryDescriptor,
    266: ExtendedFileEntryDescriptor,
}


class Volume:

    def __init__(self, analyzer, volume_desc):
        self.__analyzer = analyzer
        self.descriptor = volume_desc
        self.physical_partitions = {}
        self.partitions = {}
        self.logical= None
        self.block_size = 2048

    def add_physical_partition(self, part):
        self.physical_partitions[part["PartitionNumber"]] = part

    def set_logical(self, desc):
        self.logical = desc
        self.block_size = desc["BlockSize"]

    @property
    def name(self):
        return self.descriptor["VolumeIdentifier"]["Value"].replace("\x00", "").strip()

    def lba2offset(self, lba):
        num = lba["PartitionReferenceNumber"]
        partition = self.partitions.get(num)
        if not partition:
            raise FatalError("Unknown partition {} for volume {}".format(num, self.name))
        return partition.start + self.block_size * lba["LogicalBlockNumber"]

    def lad2range(self, lcb):
        lba = lcb["Location"]
        size = lcb["Size"]
        num = lba["PartitionReferenceNumber"]
        partition = self.partitions.get(num)
        if not partition:
            raise FatalError("Unknown partition {} for volume {}".format(num, self.name))
        offset = self.block_size * lba["LogicalBlockNumber"]
        return partition, offset, size




class Partition:
    def __init__(self, volume):
        self.volume = volume

    @property
    def block_size(self):
        return self.volume.block_size

    def iterate_blocks(self, index, size):
        pass

    def sad2range(self, lcb):
        lba = lcb["Location"]
        size = lcb["Size"]
        index = self.block_size * lba
        return self, index, size

    def ad2range(self, ad):
        if ad.Location.size == 4:
            return self.sad2range(ad)
        else:
            return self.volume.lad2range(ad)
    
class PhysicalPartition(Partition):

    def __init__(self, volume, part_desc):
        Partition.__init__(self, volume)
        self.start = part_desc["PartitionLocation"] * volume.block_size
        self.end = self.start + part_desc["PartitionSize"] * volume.block_size
        self.descriptor = part_desc

    def iterate_blocks(self, index, size):
        if self.start + index + size > self.end:
            raise FatalError("range {:x}-{:x} outside partition {}".format(index, index+size, self))
        yield self.start + index, size
    
    @property
    def name(self):
        return "{}::{}".format(self.volume.descriptor["VolumeIdentifier"]["Value"], self.descriptor["PartitionNumber"])


class VirtualPartition(Partition): 

    def __init__(self, volume, file, block_size = None, name=""):
        Partition.__init__(self, volume)
        self.file = file
        self.__block_size = block_size
        self.__name = name

    @property
    def block_size(self):
        if self.__block_size is None:
            return self.volume.block_size
        else:
            return self.__block_size

    def iterate_blocks(self, index, size):
        for offset, bsize in self.file.iterate_blocks():
            if index < bsize:
                todo = min(size, bsize - index)
                yield offset + index, todo
                size -= todo
                index  = 0
            else:
                index -= size
            if size <= 0:
                break

    @property
    def name(self):
        return "{}::{}".format(self.volume.descriptor["VolumeIdentifier"]["Value"], self.__name)


class File:

    def __init__(self, partition, index, descriptor):
        self.__partition = partition
        self.index = index
        self.descriptor = descriptor

    def iterate_allocs(self):
        if "AllocationDescriptors" in self.descriptor:
            allocs = self.descriptor["AllocationDescriptors"]
            for i in range(allocs.count):
                ad = allocs.at(i)
                yield self.__partition.ad2range(ad)
        else:
            index = self.index + self.descriptor.size
            size = self.descriptor["AllocationDescriptorsSize"]
            yield self.__partition, index, size

    def iterate_blocks(self):
        for part, index, size in self.iterate_allocs():
            yield from part.iterate_blocks(index, size)

    @property
    def size(self):
        sz = 0
        for _, size in self.iterate_blocks():
            sz += size
        return size


class UDFAnalyzer(FileTypeAnalyzer):
    category = malcat.FileType.FILESYSTEM
    name = "UDF"
    regexp = r"(?<=\x00)BEA01\x01"
    priority = 1

    @classmethod
    def locate(cls, curfile, offset_magic, parent_parser):
        while offset_magic > 0x8001:
            data = curfile.read(offset_magic - 0x800, 5)
            if not data.endswith(b"01"):
                break
            offset_magic -= 0x800
        if offset_magic < 0x8001:
            return None
        return offset_magic - 0x8001, ""

    def __init__(self):
        FileTypeAnalyzer.__init__(self)
        self.filesystem = {}
        self.volumes = {}

    def open(self, vfile, password=None):
        res = bytearray()
        f = self.filesystem[vfile.path]
        for offset, size in f.iterate_blocks():
            res.extend(self.read(offset, size))
        return res


    def parse(self, hint):
        self.add_section("SystemArea", 0, 0x8000, discardable=True)

        # iso-compliant headers
        self.jump(0x8000)
        while True:
            typ, tag = struct.unpack("<B5s", self.read(self.tell(), 6))
            vd = yield VolumeDescriptor()
            if vd["Magic"] == "TEA01":
                break
        self.add_section("ISO", 0x8000, 0x8000, discardable=True)
        self.confirm()

        # achor descriptor
        self.jump(256 * 0x800)
        anchor = yield AnchorVolumeDescriptor()
        volume_start = anchor["MainVolumeDescriptor"]["Location"] * 0x800

        # udf headers
        self.jump(volume_start)
        last_volume = None
        self.descriptors = {}
        while True:
            typ, = struct.unpack("<H", self.read(self.tell(), 2))
            class_ = KNOWN_DESCRIPTORS.get(typ, Descriptor)
            parent = None
            if type != 1 and last_volume:
                parent = last_volume.descriptor
            td = yield class_(parent=parent)
            if typ == 8:
                break
            if "VolumeDescriptorSequenceNumber" in td:
                self.descriptors[td["VolumeDescriptorSequenceNumber"]] = td
            if typ == 1:
                last_volume = Volume(self, td)
                self.volumes[td["VolumeSequenceNumber"]] = last_volume
            elif typ == 6:
                if not last_volume:
                    raise FatalError("No volume defined")
                last_volume.set_logical(td)
            elif typ == 5:
                if not last_volume:
                    raise FatalError("No volume defined")
                last_volume.add_physical_partition(td)
        self.confirm()
        if last_volume is None:
            raise FatalError("No volume")
        elif last_volume.logical is None:
            raise FatalError("No logical volume")
        self.add_section(last_volume.name, volume_start, 0x8000, volume_start, 0x8000)

        done = set()
        todo = []
        eof = 0
        # parse partitions
        for volume in self.volumes.values():
            # build partition map
            for i in range(256):
                n = f"PartitionMap.{i}"
                if not n in volume.logical:
                    break
                m = volume.logical[n]
                if m["Type"] == 1:
                    volume.partitions[i] = PhysicalPartition(volume, volume.physical_partitions[m["PartitionNumber"]])
                elif m["Type"] == 2:
                    partition = PhysicalPartition(volume, volume.physical_partitions[m["PartitionNumber"]])
                    volume.partitions[i] = VirtualPartition(volume, None, name=m["PartitionTypeIdentifier"]["Identifier"])
                    subtype = m["PartitionTypeIdentifier"]["Identifier"]
                    if subtype == "*UDF Metadata Partition":
                        if m["MetadataFileLocation"] != 0xffffffff:
                            todo.append(("#METADATA", partition, m["MetadataFileLocation"], partition.descriptor, volume.partitions[i]))
                        if m["MetadataMirrorLocation"] != 0xffffffff:
                            todo.append(("#METADATA_MIRROR", partition, m["MetadataMirrorLocation"], partition.descriptor, volume.partitions[i]))
                        if m["MetadataBitmapLocation"] != 0xffffffff:
                            todo.append(("#METADATA_BITMAP", partition, m["MetadataBitmapLocat"], partition.descriptor, volume.partitions[i]))
                else:
                    raise FatalError("Invalid partition type")

            for k, partition in volume.partitions.items():
                name = "{}::{}".format(volume.name, k)
                if isinstance(partition, PhysicalPartition):
                    self.add_section(name, partition.start, partition.end - partition.start)
                    todo.append(("", partition, 0, partition.descriptor, None))
                    eof = max(eof, partition.end)
        self.set_eof(eof)

        # parse files
        while todo:
            dname, partition, index, parent, vpart = todo.pop(0)
            offset, _ = next(partition.iterate_blocks(index, 1))
            if offset in done:
                continue
            done.add(offset)
            self.jump(offset)
            dont_stop_after_terminator = False
            while True:
                typ, = struct.unpack("<H", self.read(self.tell(), 2))
                class_ = KNOWN_DESCRIPTORS.get(typ, Descriptor)
                td = yield class_(parent = parent)
                if td["Tag"]["Identifier"] == 8:
                    if not dont_stop_after_terminator:
                        break
                elif td["Tag"]["Identifier"] == 256:
                    part, root_offset, root_size = volume.lad2range(td["RootDirectory"])
                    if root_size:
                        if root_offset == index:
                            # sometimes root directory directly follows file set
                            dont_stop_after_terminator = True
                        else:
                            todo.append(("", part, root_offset, td, None))
                elif td["Tag"]["Identifier"] in (261, 266):
                    f = File(partition, index, td)
                    if vpart is not None:
                        vpart.file = f
                    filetype = td["IcbTag"]["FileType"]
                    if filetype in (5, 0xfa, 0xfb, 0xfc):
                        self.filesystem[dname] = f
                        self.add_file(dname, td["InformationSize"], "open")
                        if filetype in (0xfa, 0xfb):
                            part, index, _ = next(f.iterate_allocs())
                            todo.append(("", part, index, td, None))
                    elif filetype == 4:
                        # directory
                        for offset, size in f.iterate_blocks():
                            self.jump(offset)
                            while self.tell() < offset + size:
                                fid = yield FileIdentifierDescriptor(parent=td)
                                if fid["Characteristics"]["Parent"] or fid["FileIdentifierSize"] == 0:
                                    continue
                                name = fid["FileIdentifier"]["Value"]
                                part, off, _ = volume.lad2range(fid["ICB"])
                                todo.append(("/".join([dname, name]), part, off, td, None))
                    break
                else:
                    break
