unwindFrameMachO

pub fn unwindFrameMachO(
    allocator: Allocator,
    base_address: usize,
    context: *UnwindContext,
    ma: *std.debug.MemoryAccessor,
    unwind_info: []const u8,
    eh_frame: ?[]const u8,
) !usize {
    const header = std.mem.bytesAsValue(
        macho.unwind_info_section_header,
        unwind_info[0..@sizeOf(macho.unwind_info_section_header)],
    );
    const indices = std.mem.bytesAsSlice(
        macho.unwind_info_section_header_index_entry,
        unwind_info[header.indexSectionOffset..][0 .. header.indexCount * @sizeOf(macho.unwind_info_section_header_index_entry)],
    );
    if (indices.len == 0) return error.MissingUnwindInfo;

    const mapped_pc = context.pc - base_address;
    const second_level_index = blk: {
        var left: usize = 0;
        var len: usize = indices.len;

        while (len > 1) {
            const mid = left + len / 2;
            const offset = indices[mid].functionOffset;
            if (mapped_pc < offset) {
                len /= 2;
            } else {
                left = mid;
                if (mapped_pc == offset) break;
                len -= len / 2;
            }
        }

        // Last index is a sentinel containing the highest address as its functionOffset
        if (indices[left].secondLevelPagesSectionOffset == 0) return error.MissingUnwindInfo;
        break :blk &indices[left];
    };

    const common_encodings = std.mem.bytesAsSlice(
        macho.compact_unwind_encoding_t,
        unwind_info[header.commonEncodingsArraySectionOffset..][0 .. header.commonEncodingsArrayCount * @sizeOf(macho.compact_unwind_encoding_t)],
    );

    const start_offset = second_level_index.secondLevelPagesSectionOffset;
    const kind = std.mem.bytesAsValue(
        macho.UNWIND_SECOND_LEVEL,
        unwind_info[start_offset..][0..@sizeOf(macho.UNWIND_SECOND_LEVEL)],
    );

    const entry: struct {
        function_offset: usize,
        raw_encoding: u32,
    } = switch (kind.*) {
        .REGULAR => blk: {
            const page_header = std.mem.bytesAsValue(
                macho.unwind_info_regular_second_level_page_header,
                unwind_info[start_offset..][0..@sizeOf(macho.unwind_info_regular_second_level_page_header)],
            );

            const entries = std.mem.bytesAsSlice(
                macho.unwind_info_regular_second_level_entry,
                unwind_info[start_offset + page_header.entryPageOffset ..][0 .. page_header.entryCount * @sizeOf(macho.unwind_info_regular_second_level_entry)],
            );
            if (entries.len == 0) return error.InvalidUnwindInfo;

            var left: usize = 0;
            var len: usize = entries.len;
            while (len > 1) {
                const mid = left + len / 2;
                const offset = entries[mid].functionOffset;
                if (mapped_pc < offset) {
                    len /= 2;
                } else {
                    left = mid;
                    if (mapped_pc == offset) break;
                    len -= len / 2;
                }
            }

            break :blk .{
                .function_offset = entries[left].functionOffset,
                .raw_encoding = entries[left].encoding,
            };
        },
        .COMPRESSED => blk: {
            const page_header = std.mem.bytesAsValue(
                macho.unwind_info_compressed_second_level_page_header,
                unwind_info[start_offset..][0..@sizeOf(macho.unwind_info_compressed_second_level_page_header)],
            );

            const entries = std.mem.bytesAsSlice(
                macho.UnwindInfoCompressedEntry,
                unwind_info[start_offset + page_header.entryPageOffset ..][0 .. page_header.entryCount * @sizeOf(macho.UnwindInfoCompressedEntry)],
            );
            if (entries.len == 0) return error.InvalidUnwindInfo;

            var left: usize = 0;
            var len: usize = entries.len;
            while (len > 1) {
                const mid = left + len / 2;
                const offset = second_level_index.functionOffset + entries[mid].funcOffset;
                if (mapped_pc < offset) {
                    len /= 2;
                } else {
                    left = mid;
                    if (mapped_pc == offset) break;
                    len -= len / 2;
                }
            }

            const entry = entries[left];
            const function_offset = second_level_index.functionOffset + entry.funcOffset;
            if (entry.encodingIndex < header.commonEncodingsArrayCount) {
                if (entry.encodingIndex >= common_encodings.len) return error.InvalidUnwindInfo;
                break :blk .{
                    .function_offset = function_offset,
                    .raw_encoding = common_encodings[entry.encodingIndex],
                };
            } else {
                const local_index = try math.sub(
                    u8,
                    entry.encodingIndex,
                    math.cast(u8, header.commonEncodingsArrayCount) orelse return error.InvalidUnwindInfo,
                );
                const local_encodings = std.mem.bytesAsSlice(
                    macho.compact_unwind_encoding_t,
                    unwind_info[start_offset + page_header.encodingsPageOffset ..][0 .. page_header.encodingsCount * @sizeOf(macho.compact_unwind_encoding_t)],
                );
                if (local_index >= local_encodings.len) return error.InvalidUnwindInfo;
                break :blk .{
                    .function_offset = function_offset,
                    .raw_encoding = local_encodings[local_index],
                };
            }
        },
        else => return error.InvalidUnwindInfo,
    };

    if (entry.raw_encoding == 0) return error.NoUnwindInfo;
    const reg_context = Dwarf.abi.RegisterContext{
        .eh_frame = false,
        .is_macho = true,
    };

    const encoding: macho.CompactUnwindEncoding = @bitCast(entry.raw_encoding);
    const new_ip = switch (builtin.cpu.arch) {
        .x86_64 => switch (encoding.mode.x86_64) {
            .OLD => return error.UnimplementedUnwindEncoding,
            .RBP_FRAME => blk: {
                const regs: [5]u3 = .{
                    encoding.value.x86_64.frame.reg0,
                    encoding.value.x86_64.frame.reg1,
                    encoding.value.x86_64.frame.reg2,
                    encoding.value.x86_64.frame.reg3,
                    encoding.value.x86_64.frame.reg4,
                };

                const frame_offset = encoding.value.x86_64.frame.frame_offset * @sizeOf(usize);
                var max_reg: usize = 0;
                inline for (regs, 0..) |reg, i| {
                    if (reg > 0) max_reg = i;
                }

                const fp = (try regValueNative(context.thread_context, fpRegNum(reg_context), reg_context)).*;
                const new_sp = fp + 2 * @sizeOf(usize);

                // Verify the stack range we're about to read register values from
                if (ma.load(usize, new_sp) == null or ma.load(usize, fp - frame_offset + max_reg * @sizeOf(usize)) == null) return error.InvalidUnwindInfo;

                const ip_ptr = fp + @sizeOf(usize);
                const new_ip = @as(*const usize, @ptrFromInt(ip_ptr)).*;
                const new_fp = @as(*const usize, @ptrFromInt(fp)).*;

                (try regValueNative(context.thread_context, fpRegNum(reg_context), reg_context)).* = new_fp;
                (try regValueNative(context.thread_context, spRegNum(reg_context), reg_context)).* = new_sp;
                (try regValueNative(context.thread_context, ip_reg_num, reg_context)).* = new_ip;

                for (regs, 0..) |reg, i| {
                    if (reg == 0) continue;
                    const addr = fp - frame_offset + i * @sizeOf(usize);
                    const reg_number = try Dwarf.compactUnwindToDwarfRegNumber(reg);
                    (try regValueNative(context.thread_context, reg_number, reg_context)).* = @as(*const usize, @ptrFromInt(addr)).*;
                }

                break :blk new_ip;
            },
            .STACK_IMMD,
            .STACK_IND,
            => blk: {
                const sp = (try regValueNative(context.thread_context, spRegNum(reg_context), reg_context)).*;
                const stack_size = if (encoding.mode.x86_64 == .STACK_IMMD)
                    @as(usize, encoding.value.x86_64.frameless.stack.direct.stack_size) * @sizeOf(usize)
                else stack_size: {
                    // In .STACK_IND, the stack size is inferred from the subq instruction at the beginning of the function.
                    const sub_offset_addr =
                        base_address +
                        entry.function_offset +
                        encoding.value.x86_64.frameless.stack.indirect.sub_offset;
                    if (ma.load(usize, sub_offset_addr) == null) return error.InvalidUnwindInfo;

                    // `sub_offset_addr` points to the offset of the literal within the instruction
                    const sub_operand = @as(*align(1) const u32, @ptrFromInt(sub_offset_addr)).*;
                    break :stack_size sub_operand + @sizeOf(usize) * @as(usize, encoding.value.x86_64.frameless.stack.indirect.stack_adjust);
                };

                // Decode the Lehmer-coded sequence of registers.
                // For a description of the encoding see lib/libc/include/any-macos.13-any/mach-o/compact_unwind_encoding.h

                // Decode the variable-based permutation number into its digits. Each digit represents
                // an index into the list of register numbers that weren't yet used in the sequence at
                // the time the digit was added.
                const reg_count = encoding.value.x86_64.frameless.stack_reg_count;
                const ip_ptr = if (reg_count > 0) reg_blk: {
                    var digits: [6]u3 = undefined;
                    var accumulator: usize = encoding.value.x86_64.frameless.stack_reg_permutation;
                    var base: usize = 2;
                    for (0..reg_count) |i| {
                        const div = accumulator / base;
                        digits[digits.len - 1 - i] = @intCast(accumulator - base * div);
                        accumulator = div;
                        base += 1;
                    }

                    const reg_numbers = [_]u3{ 1, 2, 3, 4, 5, 6 };
                    var registers: [reg_numbers.len]u3 = undefined;
                    var used_indices = [_]bool{false} ** reg_numbers.len;
                    for (digits[digits.len - reg_count ..], 0..) |target_unused_index, i| {
                        var unused_count: u8 = 0;
                        const unused_index = for (used_indices, 0..) |used, index| {
                            if (!used) {
                                if (target_unused_index == unused_count) break index;
                                unused_count += 1;
                            }
                        } else unreachable;

                        registers[i] = reg_numbers[unused_index];
                        used_indices[unused_index] = true;
                    }

                    var reg_addr = sp + stack_size - @sizeOf(usize) * @as(usize, reg_count + 1);
                    if (ma.load(usize, reg_addr) == null) return error.InvalidUnwindInfo;
                    for (0..reg_count) |i| {
                        const reg_number = try Dwarf.compactUnwindToDwarfRegNumber(registers[i]);
                        (try regValueNative(context.thread_context, reg_number, reg_context)).* = @as(*const usize, @ptrFromInt(reg_addr)).*;
                        reg_addr += @sizeOf(usize);
                    }

                    break :reg_blk reg_addr;
                } else sp + stack_size - @sizeOf(usize);

                const new_ip = @as(*const usize, @ptrFromInt(ip_ptr)).*;
                const new_sp = ip_ptr + @sizeOf(usize);
                if (ma.load(usize, new_sp) == null) return error.InvalidUnwindInfo;

                (try regValueNative(context.thread_context, spRegNum(reg_context), reg_context)).* = new_sp;
                (try regValueNative(context.thread_context, ip_reg_num, reg_context)).* = new_ip;

                break :blk new_ip;
            },
            .DWARF => {
                return unwindFrameMachODwarf(allocator, base_address, context, ma, eh_frame orelse return error.MissingEhFrame, @intCast(encoding.value.x86_64.dwarf));
            },
        },
        .aarch64, .aarch64_be => switch (encoding.mode.arm64) {
            .OLD => return error.UnimplementedUnwindEncoding,
            .FRAMELESS => blk: {
                const sp = (try regValueNative(context.thread_context, spRegNum(reg_context), reg_context)).*;
                const new_sp = sp + encoding.value.arm64.frameless.stack_size * 16;
                const new_ip = (try regValueNative(context.thread_context, 30, reg_context)).*;
                if (ma.load(usize, new_sp) == null) return error.InvalidUnwindInfo;
                (try regValueNative(context.thread_context, spRegNum(reg_context), reg_context)).* = new_sp;
                break :blk new_ip;
            },
            .DWARF => {
                return unwindFrameMachODwarf(allocator, base_address, context, ma, eh_frame orelse return error.MissingEhFrame, @intCast(encoding.value.arm64.dwarf));
            },
            .FRAME => blk: {
                const fp = (try regValueNative(context.thread_context, fpRegNum(reg_context), reg_context)).*;
                const new_sp = fp + 16;
                const ip_ptr = fp + @sizeOf(usize);

                const num_restored_pairs: usize =
                    @popCount(@as(u5, @bitCast(encoding.value.arm64.frame.x_reg_pairs))) +
                    @popCount(@as(u4, @bitCast(encoding.value.arm64.frame.d_reg_pairs)));
                const min_reg_addr = fp - num_restored_pairs * 2 * @sizeOf(usize);

                if (ma.load(usize, new_sp) == null or ma.load(usize, min_reg_addr) == null) return error.InvalidUnwindInfo;

                var reg_addr = fp - @sizeOf(usize);
                inline for (@typeInfo(@TypeOf(encoding.value.arm64.frame.x_reg_pairs)).@"struct".fields, 0..) |field, i| {
                    if (@field(encoding.value.arm64.frame.x_reg_pairs, field.name) != 0) {
                        (try regValueNative(context.thread_context, 19 + i, reg_context)).* = @as(*const usize, @ptrFromInt(reg_addr)).*;
                        reg_addr += @sizeOf(usize);
                        (try regValueNative(context.thread_context, 20 + i, reg_context)).* = @as(*const usize, @ptrFromInt(reg_addr)).*;
                        reg_addr += @sizeOf(usize);
                    }
                }

                inline for (@typeInfo(@TypeOf(encoding.value.arm64.frame.d_reg_pairs)).@"struct".fields, 0..) |field, i| {
                    if (@field(encoding.value.arm64.frame.d_reg_pairs, field.name) != 0) {
                        // Only the lower half of the 128-bit V registers are restored during unwinding
                        @memcpy(
                            try regBytes(context.thread_context, 64 + 8 + i, context.reg_context),
                            std.mem.asBytes(@as(*const usize, @ptrFromInt(reg_addr))),
                        );
                        reg_addr += @sizeOf(usize);
                        @memcpy(
                            try regBytes(context.thread_context, 64 + 9 + i, context.reg_context),
                            std.mem.asBytes(@as(*const usize, @ptrFromInt(reg_addr))),
                        );
                        reg_addr += @sizeOf(usize);
                    }
                }

                const new_ip = @as(*const usize, @ptrFromInt(ip_ptr)).*;
                const new_fp = @as(*const usize, @ptrFromInt(fp)).*;

                (try regValueNative(context.thread_context, fpRegNum(reg_context), reg_context)).* = new_fp;
                (try regValueNative(context.thread_context, ip_reg_num, reg_context)).* = new_ip;

                break :blk new_ip;
            },
        },
        else => return error.UnimplementedArch,
    };

    context.pc = stripInstructionPtrAuthCode(new_ip);
    if (context.pc > 0) context.pc -= 1;
    return new_ip;
}