@test use std::testing;

export mod fdt;

export mod platform;

export mod boot;

//! Machine entry boundary and published platform state.

use super::platform;

use super::fdt;

use super::range;

use super::limits;

use super::sync;

/// Platform data published by hart zero before secondary initialization.

export unsafe static PLATFORM: platform::Platform = undefined;

/// Release/acquire publication flag for PLATFORM.

static READY: u64 = 0;

/// Number of harts that validated their machine stack.

static ARRIVED: u64 = 0;

/// Read a byte from a device register with I/O ordering.

fn read8(address: u64) -> u8;

/// Write a byte to a device register with I/O ordering.

fn write8(address: u64, value: u8);

/// Send a bounded diagnostic through the discovered byte-wide UART.

unsafe fn print(message: *[u8]) {

    for i in 0..PLATFORM.deviceCount {

        let device = PLATFORM.devices[i];

        if device.kind <> platform::Kind::Uart {

            continue;

        }

        if device.memory.end - device.memory.start < 6 {

            return;

        }

        for byte in message {

            let mut polls: u32 = 0;

            while (read8(device.memory.start + 5) & 32) == 0 {

                set polls += 1;

                if polls == 1000000 {

                    return;

                }

            }

            write8(device.memory.start, byte);

        }

        return;

    }

}

/// Initialize one hart from firmware arguments. Return true for the last hart.

/// Firmware supplies a mapped FDT and a disjoint, reserved stack for each hart.

export unsafe fn enter(hart: u64, tree: *u8, stackTop: u64) -> bool {

    let treeAddress = tree as u64;

    assert hart < limits::HARTS as u64;

    if hart == 0 {

        assert (treeAddress & 7) == 0 and treeAddress <= 0xffffffffffffffff - 65536;

        let prefix = @sliceOf(tree, 40);

        let size = try! fdt::integer(&prefix[..], 4, 4) as u32;

        assert size >= 40 and size <= 65536;

        let blob = @sliceOf(tree, size);

        try! platform::decode(&blob[..], &mut PLATFORM);

        let treeRange = range::new(treeAddress, size as u64) else panic "FDT range";

        assert platform::inRam(&PLATFORM, treeRange);

        try! platform::protect(&mut PLATFORM, treeRange);

        print("kernel: platform ready\n");

        sync::storeRelease(&mut READY, 1);

    } else {

        while sync::loadAcquire(&READY) == 0 {

        }

    }

    assert (PLATFORM.harts & (1 << hart as u32)) <> 0;

    assert stackTop == PLATFORM.stacks[hart as u32].end and (stackTop & 15) == 0;

    let mut count: u64 = 0;

    for id in 0..limits::HARTS {

        if (PLATFORM.harts & (1 << id)) <> 0 {

            set count += 1;

        }

    }

    return sync::fetchAdd(&mut ARRIVED, 1) + 1 == count;

}

//! RV64 machine startup. Firmware supplies a0=hart, a1=FDT, and aligned sp.

.text;

.export @kernel::boot::start;

.export @kernel::boot::initialize;

.export @kernel::boot::read8;

.export @kernel::boot::write8;

@kernel::boot::start

    call @kernel::boot::initialize;

@idle

    wfi;

    j @idle;

// Initialize machine CSRs and preserve the firmware stack across Radiance entry.

@kernel::boot::initialize

    csrw mie %zero;

    csrw mstatus %zero;

    csrw mscratch %sp;

    mv %a2 %sp;

    addi %sp %sp -16;

    sd %ra 0(%sp);

    call @kernel::boot::enter;

    ld %ra 0(%sp);

    addi %sp %sp 16;

    ret;

@kernel::boot::read8

    fence iorw iorw;

    lbu %a0 0(%a0);

    fence iorw iorw;

    ret;

@kernel::boot::write8

    fence iorw iorw;

    sb %a1 0(%a0);

    fence iorw iorw;

    ret;

//! Bounded flattened device-tree decoding. All offsets refer to the input blob.

use super::range;

/// Invalid or unsupported platform description.

export union Error: Copy {

    /// A field or byte sequence is outside the blob.

    Truncated,

    /// Header, structure, or reservation data is invalid.

    Invalid,

    /// The tree exceeds the supported nesting depth.

    Depth,

}

/// Byte interval within the validated blob.

export record Span: Copy {

    /// First byte offset.

    start: u32,

    /// Exclusive end offset.

    end: u32,

}

/// Validated header and block extents.

export record Header: Copy {

    /// Declared blob length.

    size: u32,

    /// Structure block.

    structure: Span,

    /// Property-name strings.

    strings: Span,

    /// Reservation entries, excluding the zero terminator.

    reservations: Span,

}

/// Structure traversal state. Use only with the blob passed to `header`.

export record Cursor: Copy {

    /// Next structure byte.

    offset: u32,

    /// Number of open nodes.

    depth: u32,

    /// A root node has started.

    started: bool,

    /// The end token has been consumed.

    finished: bool,

    /// Depth bits for nodes whose children have started.

    children: u32,

}

/// One tree structure item. Names exclude their zero terminator.

export union Event: Copy {

    /// Node name.

    Begin(Span),

    /// Property name and value.

    Property { name: Span, value: Span },

    /// End of the current node.

    EndNode,

    /// End of the complete tree.

    End,

}

/// Read a bounded big-endian integer of four or eight bytes.

export fn integer(bytes: &[u8], offset: u32, width: u32) -> u64 throws (Error) {

    if width <> 4 and width <> 8 {

        throw Error::Invalid;

    }

    if offset > bytes.len or width > bytes.len - offset {

        throw Error::Truncated;

    }

    let mut value: u64 = 0;

    for i in 0..width {

        set value = (value << 8) | bytes[offset + i] as u64;

    }

    return value;

}

/// Check a block's extent without addition overflow.

fn block(total: u32, start: u32, size: u32) -> Span throws (Error) {

    if start < 40 or start > total or size > total - start {

        throw Error::Truncated;

    }

    return Span { start, end: start + size };

}

/// Check whether two nonempty spans overlap.

fn overlaps(a: Span, b: Span) -> bool {

    return a.start < a.end and b.start < b.end and a.start < b.end and b.start < a.end;

}

/// Validate a version-17 header, disjoint blocks, and all memory reservations.

export fn header(bytes: &[u8]) -> Header throws (Error) {

    if bytes.len < 40 {

        throw Error::Truncated;

    }

    if try integer(bytes, 0, 4) <> 0xd00dfeed {

        throw Error::Invalid;

    }

    let size = try integer(bytes, 4, 4) as u32;

    if size > bytes.len or size < 40 {

        throw Error::Truncated;

    }

    if try integer(bytes, 20, 4) <> 17 or try integer(bytes, 24, 4) > 17 {

        throw Error::Invalid;

    }

    let structure = try block(size, try integer(bytes, 8, 4) as u32, try integer(bytes, 36, 4) as u32);

    let strings = try block(size, try integer(bytes, 12, 4) as u32, try integer(bytes, 32, 4) as u32);

    let reserved = try integer(bytes, 16, 4) as u32;

    if (structure.start & 3) <> 0 or (structure.end & 3) <> 0 or (reserved & 7) <> 0 or reserved < 40 {

        throw Error::Invalid;

    }

    let mut end = reserved;

    loop {

        if end > size or size - end < 16 {

            throw Error::Truncated;

        }

        let address = try integer(bytes, end, 8);

        let length = try integer(bytes, end + 8, 8);

        if address == 0 and length == 0 {

            break;

        }

        if range::new(address, length) == nil {

            throw Error::Invalid;

        }

        set end += 16;

    }

    let reservations = Span { start: reserved, end: end + 16 };

    if overlaps(structure, strings) or overlaps(structure, reservations) or overlaps(strings, reservations) {

        throw Error::Invalid;

    }

    return Header { size, structure, strings, reservations: Span { start: reserved, end } };

}

/// Start traversal at the first structure token.

export fn cursor(tree: Header) -> Cursor {

    return Cursor { offset: tree.structure.start, depth: 0, started: false, finished: false, children: 0 };

}

/// Find a terminated string inside one validated block.

fn name(bytes: &[u8], start: u32, end: u32) -> Span throws (Error) {

    if end > bytes.len or start >= end {

        throw Error::Truncated;

    }

    let mut at = start;

    while at < end {

        if bytes[at] == 0 {

            return Span { start, end: at };

        }

        set at += 1;

    }

    throw Error::Truncated;

}

/// Round an offset to the next token boundary within the structure block.

fn padded(bytes: &[u8], end: u32, limit: u32) -> u32 throws (Error) {

    let padding = (4 - (end & 3)) & 3;

    if end > limit or padding > limit - end {

        throw Error::Truncated;

    }

    for i in end..end + padding {

        if bytes[i] <> 0 {

            throw Error::Invalid;

        }

    }

    return end + padding;

}

/// Read one structure event, skipping NOP tokens. Nesting is bounded to 32 nodes.

export fn next(bytes: &[u8], tree: Header, state: &mut Cursor) -> Event throws (Error) {

    if state.finished {

        return Event::End;

    }

    loop {

        if state.offset > tree.structure.end or tree.structure.end - state.offset < 4 {

            throw Error::Truncated;

        }

        let token = try integer(bytes, state.offset, 4);

        set state.offset += 4;

        match token {

            case 1 => {

                if state.depth == 32 {

                    throw Error::Depth;

                }

                if state.depth == 0 and state.started {

                    throw Error::Invalid;

                }

                let value = try name(bytes, state.offset, tree.structure.end);

                if state.depth == 0 and value.start <> value.end {

                    throw Error::Invalid;

                }

                if state.depth > 0 and value.start == value.end {

                    throw Error::Invalid;

                }

                if state.depth > 0 {

                    set state.children |= 1 << (state.depth - 1);

                }

                set state.children &= ~(1 << state.depth);

                set state.depth += 1;

                set state.started = true;

                set state.offset = try padded(bytes, value.end + 1, tree.structure.end);

                return Event::Begin(value);

            },

            case 2 => {

                if state.depth == 0 {

                    throw Error::Invalid;

                }

                set state.depth -= 1;

                return Event::EndNode;

            },

            case 3 => {

                if state.depth == 0 or (state.children & (1 << (state.depth - 1))) <> 0 {

                    throw Error::Invalid;

                }

                if tree.structure.end - state.offset < 8 {

                    throw Error::Truncated;

                }

                let size = try integer(bytes, state.offset, 4) as u32;

                let offset = try integer(bytes, state.offset + 4, 4) as u32;

                set state.offset += 8;

                if size > tree.structure.end - state.offset {

                    throw Error::Truncated;

                }

                if offset >= tree.strings.end - tree.strings.start {

                    throw Error::Invalid;

                }

                let key = try name(bytes, tree.strings.start + offset, tree.strings.end);

                if key.start == key.end {

                    throw Error::Invalid;

                }

                let value = Span { start: state.offset, end: state.offset + size };

                set state.offset = try padded(bytes, value.end, tree.structure.end);

                return Event::Property { name: key, value };

            },

            case 4 => {

            },

            case 9 => {

                if state.depth <> 0 or not state.started or state.offset <> tree.structure.end {

                    throw Error::Invalid;

                }

                set state.finished = true;

                return Event::End;

            },

            else => throw Error::Invalid,

        }

    }

}

//! Fixed platform resources and reserved-memory exclusion.

use super::fdt;

use super::range;

use super::limits;

/// Maximum RAM banks in the platform description.

export constant RAM_BANKS: u32 = 16;

/// Maximum firmware, image, stack, and device reservations.

export constant RESERVATIONS: u32 = 64;

/// Platform extraction failure.

export union Error: Copy {

    /// Malformed flattened tree.

    Tree(fdt::Error),

    /// Unsupported or inconsistent platform resource.

    Invalid,

    /// The platform exceeds fixed storage.

    Capacity,

}

/// Device mechanism selected from its compatible property.

export union Kind: Copy {

    /// Byte-wide 16550 UART.

    Uart,

    /// Per-hart machine timers and software interrupts.

    Clint,

    /// Platform interrupt controller.

    Plic,

    /// Emulator termination register.

    Finish,

}

/// A supported memory-mapped device.

export record Device: Copy {

    /// Hardware mechanism.

    kind: Kind,

    /// Physical register extent.

    memory: range::Range,

}

/// Validated boot resources. Only array elements below their counts are live.

export record Platform: Copy {

    /// RAM bank ranges.

    ram: [range::Range; RAM_BANKS],

    /// Number of RAM banks.

    ramCount: u32,

    /// Memory excluded from general allocation.

    reserved: [range::Range; RESERVATIONS],

    /// Number of reserved ranges.

    reservedCount: u32,

    /// Supported MMIO devices in tree order.

    devices: [Device; limits::DEVICES],

    /// Number of MMIO devices.

    deviceCount: u32,

    /// Bit mask of online physical hart IDs.

    harts: u32,

    /// Timer ticks per second.

    timebase: u32,

    /// Kernel stack ranges, indexed by physical hart ID.

    stacks: [range::Range; limits::HARTS],

    /// Number of stack ranges in the boot contract.

    stackCount: u32,

}

/// Properties retained until a node closes.

record Node: Copy {

    /// Node name in the input blob.

    name: fdt::Span,

    /// Parent bus address-cell count.

    addressCells: u32,

    /// Parent bus size-cell count.

    sizeCells: u32,

    /// Address-cell count for child nodes.

    childAddress: u32,

    /// Size-cell count for child nodes.

    childSize: u32,

    /// Register tuples, if present.

    registers: ?fdt::Span,

    /// Device compatibility strings, if present.

    compatible: ?fdt::Span,

    /// Device type string, if present.

    deviceType: ?fdt::Span,

    /// Node status permits use.

    enabled: bool,

    /// This node or its parent is the reserved-memory container.

    reserved: bool,

}

/// Compare a complete byte span with a name.

fn equal(bytes: &[u8], span: fdt::Span, value: &[u8]) -> bool {

    if span.end - span.start <> value.len {

        return false;

    }

    for i in 0..value.len {

        if bytes[span.start + i] <> value[i] {

            return false;

        }

    }

    return true;

}

/// Find an exact string in a zero-terminated property string list.

fn string(bytes: &[u8], span: fdt::Span, value: &[u8]) -> bool {

    let mut start = span.start;

    for i in span.start..span.end {

        if bytes[i] == 0 {

            if equal(bytes, fdt::Span { start, end: i }, value) {

                return true;

            }

            set start = i + 1;

        }

    }

    return false;

}

/// Read a cell count supported by the native 64-bit platform.

fn scalar(bytes: &[u8], value: fdt::Span) -> u32 throws (Error) {

    if value.end - value.start <> 4 {

        throw Error::Invalid;

    }

    let result = try fdt::integer(bytes, value.start, 4) catch err {

        throw Error::Tree(err);

    };

    return result as u32;

}

/// Read a nonempty physical range from one register tuple.

fn extent(bytes: &[u8], at: u32, addressCells: u32, sizeCells: u32) -> range::Range throws (Error) {

    if addressCells < 1 or addressCells > 2 or sizeCells < 1 or sizeCells > 2 {

        throw Error::Invalid;

    }

    let address = try fdt::integer(bytes, at, addressCells * 4) catch err {

        throw Error::Tree(err);

    };

    let size = try fdt::integer(bytes, at + addressCells * 4, sizeCells * 4) catch err {

        throw Error::Tree(err);

    };

    let result = range::new(address, size) else {

        throw Error::Invalid;

    };

    return result;

}

/// Append a reservation. Identical entries from both FDT representations share one slot.

export fn protect(platform: &mut Platform, value: range::Range) throws (Error) {

    for i in 0..platform.reservedCount {

        if platform.reserved[i] == value {

            return;

        }

    }

    if platform.reservedCount == RESERVATIONS {

        throw Error::Capacity;

    }

    set platform.reserved[platform.reservedCount] = value;

    set platform.reservedCount += 1;

}

/// Test a physical extent for overlap.

fn overlaps(left: range::Range, right: range::Range) -> bool {

    return left.start < right.end and right.start < left.end;

}

/// Test whether one complete extent belongs to a RAM bank.

export fn inRam(platform: &Platform, value: range::Range) -> bool {

    for i in 0..platform.ramCount {

        if range::contains(platform.ram[i], value) {

            return true;

        }

    }

    return false;

}

/// Check whether a nonempty physical extent is RAM with no reserved byte.

export fn available(platform: &Platform, value: range::Range) -> bool {

    if not inRam(platform, value) {

        return false;

    }

    for i in 0..platform.reservedCount {

        if overlaps(platform.reserved[i], value) {

            return false;

        }

    }

    return true;

}

/// Record resources only after all properties of their node are known.

fn finish(bytes: &[u8], node: Node, platform: &mut Platform) throws (Error) {

    if not node.enabled {

        return;

    }

    let registers = node.registers else {

        return;

    };

    if let typeName = node.deviceType {

        if string(bytes, typeName, &"cpu"[..]) {

            if node.sizeCells <> 0 or node.addressCells < 1 or node.addressCells > 2

                or registers.end - registers.start <> node.addressCells * 4 {

                    throw Error::Invalid;

                }

            let hart = try fdt::integer(bytes, registers.start, node.addressCells * 4) catch err {

                throw Error::Tree(err);

            };

            if hart >= limits::HARTS as u64 or (platform.harts & (1 << hart as u32)) <> 0 {

                throw Error::Invalid;

            }

            set platform.harts |= 1 << hart as u32;

            return;

        }

    }

    let width = (node.addressCells + node.sizeCells) * 4;

    if width == 0 or (registers.end - registers.start) % width <> 0 {

        throw Error::Invalid;

    }

    let mut at = registers.start;

    while at < registers.end {

        let value = try extent(bytes, at, node.addressCells, node.sizeCells);

        if node.reserved {

            try protect(platform, value);

        }

        else {

            let mut memory = false;

            if let typeName = node.deviceType {

                set memory = string(bytes, typeName, &"memory"[..]);

            }

            if memory {

                if platform.ramCount == RAM_BANKS {

                    throw Error::Capacity;

                }

                for i in 0..platform.ramCount {

                    if overlaps(platform.ram[i], value) {

                        throw Error::Invalid;

                    }

                }

                set platform.ram[platform.ramCount] = value;

                set platform.ramCount += 1;

            } else {

                let mut kind: ?Kind = nil;

                if let names = node.compatible {

                    if string(bytes, names, &"ns16550a"[..]) {

                        set kind = Kind::Uart;

                    }

                    else if string(bytes, names, &"riscv,clint0"[..]) {

                        set kind = Kind::Clint;

                    }

                    else if string(bytes, names, &"riscv,plic0"[..]) {

                        set kind = Kind::Plic;

                    }

                    else if string(bytes, names, &"radiant,finish"[..]) {

                        set kind = Kind::Finish;

                    }

                }

                if let deviceKind = kind {

                    if platform.deviceCount == limits::DEVICES {

                        throw Error::Capacity;

                    }

                    set platform.devices[platform.deviceCount] = Device { kind: deviceKind, memory: value };

                    set platform.deviceCount += 1;

                }

                try protect(platform, value);

            }

        }

        set at += width;

    }

}

/// Extract native platform resources. Discard the output if decoding fails.

export unsafe fn decode(bytes: &[u8], platform: &mut Platform) throws (Error) {

    set platform.ramCount = 0; set platform.reservedCount = 0; set platform.deviceCount = 0;

    set platform.harts = 0; set platform.timebase = 0; set platform.stackCount = 0;

    let tree = try fdt::header(bytes) catch err {

        throw Error::Tree(err);

    };

    let mut at = tree.reservations.start;

    while at < tree.reservations.end {

        try protect(platform, try extent(bytes, at, 2, 2)); set at += 16;

    }

    let mut nodes: [Node; 32] = undefined;

    let mut state = fdt::cursor(tree);

    loop {

        let event = try fdt::next(bytes, tree, &mut state) catch err {

            throw Error::Tree(err);

        };

        match event {

            case fdt::Event::Begin(name) => {

                let mut addressCells: u32 = 2;

                let mut sizeCells: u32 = 1;

                let mut reserved = false;

                let mut enabled = true;

                if state.depth > 1 {

                    let parent = nodes[state.depth - 2];

                    set addressCells = parent.childAddress; set sizeCells = parent.childSize;

                    set reserved = parent.reserved;

                    set enabled = parent.enabled;

                }

                if state.depth == 2 and equal(bytes, name, &"reserved-memory"[..]) {

                    set reserved = true;

                }

                set nodes[state.depth - 1] = Node { name, addressCells, sizeCells, childAddress: 2, childSize: 1,

                    registers: nil, compatible: nil, deviceType: nil, enabled, reserved };

            },

            case fdt::Event::Property { name, value } => {

                if equal(bytes, name, &"#address-cells"[..]) {

                    let count = try scalar(bytes, value);

                    if count > 2 {

                        throw Error::Invalid;

                    }

                    set nodes[state.depth - 1].childAddress = count;

                } else if equal(bytes, name, &"#size-cells"[..]) {

                    let count = try scalar(bytes, value);

                    if count > 2 {

                        throw Error::Invalid;

                    }

                    set nodes[state.depth - 1].childSize = count;

                } else if equal(bytes, name, &"reg"[..]) {

                    set nodes[state.depth - 1].registers = value;

                }

                else if equal(bytes, name, &"compatible"[..]) {

                    set nodes[state.depth - 1].compatible = value;

                }

                else if equal(bytes, name, &"device_type"[..]) {

                    set nodes[state.depth - 1].deviceType = value;

                }

                else if equal(bytes, name, &"status"[..]) {

                    set nodes[state.depth - 1].enabled = nodes[state.depth - 1].enabled and (string(bytes, value, &"okay"[..]) or string(bytes, value, &"ok"[..]));

                } else if equal(bytes, name, &"ranges"[..]) and value.start <> value.end {

                    throw Error::Invalid;

                }

                else if state.depth == 2 and equal(bytes, nodes[state.depth - 1].name, &"cpus"[..]) and equal(bytes, name, &"timebase-frequency"[..]) {

                    set platform.timebase = try scalar(bytes, value);

                } else if state.depth == 2 and equal(bytes, nodes[state.depth - 1].name, &"chosen"[..]) and equal(bytes, name, &"radiance,kernel-stacks"[..]) {

                    let size = value.end - value.start;

                    if size % 16 <> 0 or size / 16 > limits::HARTS {

                        throw Error::Invalid;

                    }

                    set platform.stackCount = size / 16;

                    for i in 0..platform.stackCount {

                        let stack = try extent(bytes, value.start + i * 16, 2, 2);

                        if (stack.start & 15) <> 0 or (stack.end & 15) <> 0 {

                            throw Error::Invalid;

                        }

                        set platform.stacks[i] = stack; try protect(platform, stack);

                    }

                }

            },

            case fdt::Event::EndNode => try finish(bytes, nodes[state.depth], platform),

            case fdt::Event::End => break,

        }

    }

    if platform.ramCount == 0 or platform.harts == 0 or platform.timebase == 0 {

        throw Error::Invalid;

    }

    for hart in 0..limits::HARTS {

        if (platform.harts & (1 << hart)) == 0 {

            continue;

        }

        if hart >= platform.stackCount or not inRam(platform, platform.stacks[hart]) {

            throw Error::Invalid;

        }

        for other in 0..hart {

            if (platform.harts & (1 << other)) <> 0 and overlaps(platform.stacks[hart], platform.stacks[other]) {

                throw Error::Invalid;

            }

        }

    }

}

export mod fdt;

export mod platform;

//! Device-tree byte fixtures and structural rejection checks.

use std::testing;

use kernel::fdt;

/// Store a big-endian field in a test fixture.

fn put(bytes: &mut [u8], offset: u32, width: u32, value: u64) {

    for i in 0..width {

        set bytes[offset + i] = (value >> ((width - i - 1) * 8) as u64) as u8;

    }

}

/// Build one root property and one high-address memory reservation.

fn fixture(bytes: &mut [u8]) {

    for i in 0..bytes.len {

        set bytes[i] = 0;

    }

    put(bytes, 0, 4, 0xd00dfeed); put(bytes, 4, 4, 108);

    put(bytes, 8, 4, 72); put(bytes, 12, 4, 104); put(bytes, 16, 4, 40);

    put(bytes, 20, 4, 17); put(bytes, 24, 4, 16);

    put(bytes, 32, 4, 4); put(bytes, 36, 4, 32);

    put(bytes, 40, 8, 0x80000000); put(bytes, 48, 8, 4096);

    put(bytes, 72, 4, 1);

    put(bytes, 80, 4, 3); put(bytes, 84, 4, 4); put(bytes, 88, 4, 0);

    put(bytes, 92, 4, 42); put(bytes, 96, 4, 2); put(bytes, 100, 4, 9);

    set bytes[104] = 'r'; set bytes[105] = 'e'; set bytes[106] = 'g';

}

/// Validate the complete tree, including the final structure token.

fn validate(bytes: &[u8]) throws (fdt::Error) {

    let tree = try fdt::header(bytes);

    let mut state = fdt::cursor(tree);

    loop {

        match try fdt::next(bytes, tree, &mut state) {

            case fdt::Event::End => return,

            else => {

            },

        }

    }

}

/// Require malformed input to fail through a bounded decoder error.

fn rejects(bytes: &[u8]) throws (testing::TestError) {

    let mut failed = false;

    try validate(bytes) catch {

        set failed = true;

    };

    try testing::expect(failed);

}

/// Decode big-endian ranges and the ordered structure events.

@test unsafe fn traversal() throws (testing::TestError) {

    let mut bytes: [u8; 108] = undefined;

    fixture(&mut bytes[..]);

    let tree = try! fdt::header(&bytes[..]);

    try testing::expect(tree.reservations.start == 40 and tree.reservations.end == 56);

    try testing::expect(try! fdt::integer(&bytes[..], 40, 8) == 0x80000000);

    let mut state = fdt::cursor(tree);

    match try! fdt::next(&bytes[..], tree, &mut state) {

        case fdt::Event::Begin(name) => try testing::expect(name.start == name.end),

        else => try testing::expect(false),

    }

    match try! fdt::next(&bytes[..], tree, &mut state) {