#if 0 /* #/ ================================================================ #/ #/ bxgen.c #/ #/ Binary executable code generation and linking. #/ Compiler backend. #/ #/ ---------------------------------------------------------------- #/ #/ Qualities #/ #/ - Single source file (for now) #/ - Simple and flexible API #/ - No external dependencies #/ - No configuration required #/ - No dynamic memory management #/ - Easy cross-compilation #/ - Platform-independent host #/ #/ Inspirations #/ #/ - Cuik https://github.com/RealNeGate/Cuik #/ - tinycc https://repo.or.cz/w/tinycc.git #/ - QBE https://c9x.me/compile/ #/ #/ To-Do list #/ #/ - ELF + x86_64 executable #/ - x86_64 object file #/ - Linking libraries #/ - String table for names and arrays #/ - Proper error handling #/ - Proper prefixes for identifiers #/ - Correct serialization for endianness #/ - Effective entity allocation #/ - Implicit procedure prototypes #/ - Implicit exit after ret from entry point #/ - Static single-assignment #/ - Sea of Nodes #/ - Optimization layers #/ - Multithreading #/ - Memory reallocation when necessary #/ - JIT #/ - COFF, PE, OMF, Mach-O #/ - i386, RISC-V, ARM, WebAssembly #/ - Soft floating-point arithmeric #/ - Built-in standard library #/ - Built-in battaries: #/ - File I/O #/ - Input devices #/ - Networking #/ - Graphics #/ - Audio #/ #/ Bugs #/ #/ - ... #/ #/ Done features #/ #/ - ELF header #/ - IO static dispatch #/ #/ ---------------------------------------------------------------- #/ #/ (C) 2024 Mitya Selivanov , MIT License #/ #/ ================================================================ #/ #/ Self-compilation shell script #/ #/ ================================================================ SRC=${0##*./} BIN=${SRC%.*} gcc \ -Wno-old-style-declaration -Wno-missing-braces \ -Wall -Wextra -Werror -pedantic \ -O0 -fsanitize=undefined,address,leak -mshstk \ -o $BIN $SRC && \ ./$BIN $@ exit $? # */ #endif // ================================================================ // // Compilation options // // ================================================================ #ifndef IMPLEMENTATION #define IMPLEMENTATION 1 #endif #ifndef HELPERS #define HELPERS 1 #endif #ifndef TESTING #define TESTING 1 #endif // ================================================================ // // Basic declarations // // ================================================================ typedef signed char i8; typedef signed short i16; typedef signed int i32; typedef signed long long i64; typedef unsigned char u8; typedef unsigned short u16; typedef unsigned int u32; typedef unsigned long long u64; typedef float f32; typedef double f64; typedef signed char b8; // 8-bit boolean typedef char c8; // 8-bit character // ================================================================ // // IR data declarations // // ================================================================ enum { HOST_Unknown = 0, HOST_Unix, HOST_Linux, HOST_Windows, HOST_macOS, HOST_Cygwin, #if defined(__CYGWIN__) HOST = HOST_Cygwin, #elif defined(_WIN32) HOST = HOST_Windows, #elif defined(__linux__) HOST = HOST_Linux, #elif defined(__APPLE__) HOST = HOST_macOS, #elif defined(__unix__) HOST = HOST_Unix, #else HOST = HOST_Unknown, #endif // For indices UNDEFINED = -1, // Formats // FORMAT_ELF = 1, FORMAT_COFF, FORMAT_PE, FORMAT_OMF, FORMAT_MATCH_O, // Architecture // ARCH_RISC_V = 64, ARCH_I386, ARCH_X86_64, ARCH_ARM32, ARCH_ARM64, // Endianness // LE = 1, BE = 2, // Sea of Nodes flow type // FLOW_DATA = 0, FLOW_CONTROL, // Semantic node operations // DATA_I64 = 0, CTRL_CALL, CTRL_RET, // Calling conventions CONV_CDECL = 0, CONV_STDCALL, CONV_FASTCALL, CONV_THISCALL, // Primitive data types // TYPE_I32 = 0, // Unit types // UNIT_CODE = 0, UNIT_LIBRARY_OBJECT, UNIT_LIBRARY_STATIC, UNIT_LIBRARY_DYNAMIC, // String tables // STRING_TABLE_ALIGNMENT = 16, // TODO // Entity types // ENTITY_NODE = 0, ENTITY_PROC, ENTITY_UNIT, // Limits // MAX_LITERAL_SIZE = 400, MAX_NAME_SIZE = 80, MAX_PROC_COUNT = 40, MAX_NODE_COUNT = 60, MAX_LINK_COUNT = 20, MAX_ARG_COUNT = 20, MAX_ENTITY_COUNT = 16384, // IO dispatch operations // IO_OPEN_READ = 0, IO_OPEN_WRITE, IO_CLOSE, IO_SEEK, IO_TELL, IO_READ, IO_WRITE, IO_CHMOD_EXE, IO_SEEK_CURSOR = 0, IO_SEEK_BEGIN, IO_SEEK_END, }; // TODO typedef struct { i64 size; i64 index; } String_Handle; // TODO typedef struct { i64 size; i64 capacity; u8 *data; u8 *occupied; } Strint_Table; typedef struct { i16 size; i16 type; i64 node; } Var; typedef struct { i16 val_count; Var vals[MAX_ARG_COUNT]; } Ret; typedef struct { // NOTE // We may call a local procedure by it's id, // or a global procedure by name. i16 convention; // can be implicitly retrieved from the procedure i64 target_proc; i64 target_name_size; c8 target_name[MAX_NAME_SIZE]; // TODO use string table i64 arg_count; Var args[MAX_ARG_COUNT]; } Call; // A semantic node is an operation with optional data // and possible references to other nodes. typedef struct { i16 op; i64 index_in_proc; union { u8 lit_bytes[MAX_LITERAL_SIZE]; // byte array literal i64 lit_int; // integer literal Ret ret; Call call; }; } Node; // A procedure is a collection of semantic nodes // and has a string name. typedef struct { i16 convention; i64 name_size; c8 name[MAX_NAME_SIZE]; // TODO use string table i64 node_count; i64 nodes[MAX_NODE_COUNT]; i64 ret_index; i64 unit; i64 index_in_unit; } Proc; // A compilation unit is a collection of procedures. // typedef struct { i16 type; i64 entry_point_index; i64 name_size; c8 name[MAX_NAME_SIZE]; // TODO use string table i64 proc_count; i64 procs[MAX_PROC_COUNT]; i64 link_count; i64 links[MAX_LINK_COUNT]; } Unit; // An entity can be any of: // - Node // - Proc // - Unit // // Every entity can be referenced by it's unique index // in the entity pool. typedef struct { b8 is_enabled; i16 type; union { Node node; Proc proc; Unit unit; }; } Entity; // Pool, a collection of all entities. // // NOTE // We use one single large memory block for *everything*. typedef struct { i64 entity_count; i64 capacity; Entity *entities; } Pool; // ================================================================ // // API declarations // // ================================================================ #ifdef __cplusplus extern "C" { #endif i64 pool_add(Pool *pool, Entity data); void pool_remove(Pool *pool, i64 entity, i16 type); i64 node_init(Pool *pool, Node data); void node_destroy(Pool *pool, i64 node); i64 node_data_i64(Pool *pool, i64 value); i64 node_ctrl_call(Pool *pool, i16 convention, i64 target_proc, i64 arg_count, Var *args); i64 node_ctrl_call_by_name(Pool *pool, i16 convention, i64 name_size, c8 *name, i64 arg_count, Var *args); i64 node_ctrl_ret(Pool *pool, i64 value_count, Var *values); i64 proc_init(Pool *pool); void proc_destroy(Pool *pool, i64 proc); void proc_set_convention(Pool *pool, i64 proc, i16 convention); void proc_set_name(Pool *pool, i64 proc, i64 name_size, c8 *name); void proc_node_add(Pool *pool, i64 proc, i64 node); void proc_node_remove(Pool *pool, i64 proc, i64 node); i64 unit_init(Pool *pool, i16 type); void unit_destroy(Pool *pool, i64 unit); void unit_proc_add(Pool *pool, i64 unit, i64 proc); void unit_proc_remove(Pool *pool, i64 unit, i64 proc); void unit_link_add(Pool *pool, i64 unit, i64 link_unit); void unit_link_remove(Pool *pool, i64 unit, i64 link_unit); void unit_set_name(Pool *pool, i64 unit, i64 name_size, c8 *name); void unit_set_entry_point(Pool *pool, i64 unit, i64 entry_point_proc); void unit_write(Pool *pool, i64 unit, u16 target, i64 io_id, void *io_user_data); i64 io_open_read(i64 name_size, c8 *name, void *user_data); i64 io_open_write(i64 name_size, c8 *name, void *user_data); void io_close(i64 f, void *user_data); b8 io_seek(i64 f, i64 offset, u16 origin, void *user_data); i64 io_tell(i64 f, void *user_data); i64 io_read(i64 f, i64 size, void *data, void *user_data); i64 io_write(i64 f, i64 size, void *data, void *user_data); void io_chmod_exe(i64 f, void *user_data); void bx_assert(b8 condition, c8 *message, u32 line, c8 *file); void io_dispatch(i16 op, i64 *id, i64 *size, void *data, void *user_data); #ifndef DISABLE_HELPERS i64 n_i64(i64 value); i64 n_call(i16 convention, i64 target_proc, i64 arg_count, Var *args); i64 n_call_by_name(i16 convention, c8 *name, i64 arg_count, Var *args); i64 n_ret(i64 val_count, Var *vals); i64 p_new(c8 *name); void p_add(i64 proc, i64 node); i64 u_new(); void u_add(i64 unit, i64 proc); void u_entry_point(i64 unit, i64 proc); void u_elf_x86_64(i64 unit, c8 *output_file_name); void l_code(i64 unit, i64 link_unit); void l_object(i64 unit, c8 *object_library); void l_static(i64 unit, c8 *static_library); #endif #ifdef __cplusplus } #endif // ================================================================ // // IMPLEMENTATION // // ================================================================ // // * Basic utilities // // ================================================================ #if IMPLEMENTATION #ifdef __cplusplus #error Implementation code should be compiled with a C compiler! #endif #ifndef NULL #define NULL ((void *) 0) #endif #define BX_ASSERT(condition) \ bx_assert((condition), #condition, __LINE__, __FILE__) i64 bx_align(i64 x, i64 a) { BX_ASSERT(a > 0); return x + ((a - (x % a)) % a); } void bx_mem_cpy(void *dst, void *src, i64 size) { BX_ASSERT(dst != NULL); BX_ASSERT(src != NULL); BX_ASSERT(size > 0); for (i64 i = 0; i < size; ++i) ((u8 *)dst)[i] = ((u8 *)src)[i]; } b8 bx_mem_eq(void *a, void *b, i64 size) { BX_ASSERT(a != NULL); BX_ASSERT(b != NULL); BX_ASSERT(size > 0); u8 *x = (u8 *) a; u8 *y = (u8 *) b; for (i64 i = 0; i < size; ++i) if (x[i] != y[i]) return 0; return 1; } i64 bx_str_len(c8 *s, c8 *s_max) { for (i64 len = 0; s + len < s_max; ++len) if (s[len] == '\0') return len; BX_ASSERT(0); return 0; } b8 bx_str_eq( c8 *a, c8 *a_end, c8 *b, c8 *b_end ) { BX_ASSERT(a != NULL && a_end != NULL); BX_ASSERT(b != NULL && b_end != NULL); while (*a == *b && a != a_end && b != b_end) { ++a; ++b; } return a == a_end && b == b_end; } c8 *bx_find_char(c8 *s, c8 *s_end, c8 c) { BX_ASSERT(s != NULL); BX_ASSERT(s_end != NULL); while (s != s_end && *s != c) ++s; return *s == c ? s : NULL; } // ================================================================ // // * Semantic graph // // ================================================================ // IR building procs // i64 pool_add(Pool *pool, Entity data) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entity_count < pool->capacity); i64 id = pool->entity_count++; data.is_enabled = 1, pool->entities[id] = data; return id; } void pool_remove(Pool *pool, i64 entity, i16 type) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[entity].is_enabled); BX_ASSERT(pool->entities[entity].type == type); pool->entities[entity].is_enabled = 1; } i64 node_init(Pool *pool, Node data) { data.index_in_proc = UNDEFINED; return pool_add(pool, (Entity) { .type = ENTITY_NODE, .node = data, }); } void node_destroy(Pool *pool, i64 node) { pool_remove(pool, node, ENTITY_NODE); } i64 node_data_i64(Pool *pool, i64 value) { return node_init(pool, (Node) { .op = DATA_I64, .lit_int = value, }); } i64 node_ctrl_call(Pool *pool, i16 convention, i64 target_proc, i64 arg_count, Var *args) { BX_ASSERT(arg_count <= MAX_ARG_COUNT); Call call = { .convention = convention, .target_proc = target_proc, .arg_count = arg_count, }; if (arg_count > 0) bx_mem_cpy(call.args, args, arg_count * sizeof *args); return node_init(pool, (Node) { .op = CTRL_CALL, .call = call, }); } i64 node_ctrl_call_by_name(Pool *pool, i16 convention, i64 name_size, c8 *name, i64 arg_count, Var *args) { BX_ASSERT(arg_count <= MAX_ARG_COUNT); Call call = { .convention = convention, .target_name_size = name_size, .arg_count = arg_count, }; if (name_size > 0) bx_mem_cpy(call.target_name, name, name_size); if (arg_count > 0) bx_mem_cpy(call.args, args, arg_count * sizeof *args); return node_init(pool, (Node) { .op = CTRL_CALL, .call = call, }); } i64 node_ctrl_ret(Pool *pool, i64 value_count, Var *values) { BX_ASSERT(value_count <= MAX_ARG_COUNT); Ret ret = { .val_count = value_count, }; if (value_count > 0) bx_mem_cpy(ret.vals, values, value_count * sizeof *values); return node_init(pool, (Node) { .op = CTRL_RET, .ret = ret, }); } i64 proc_init(Pool *pool) { return pool_add(pool, (Entity) { .type = ENTITY_PROC, .proc = (Proc) { .ret_index = UNDEFINED, .index_in_unit = UNDEFINED, }, }); } void proc_destroy(Pool *pool, i64 proc) { pool_remove(pool, proc, ENTITY_PROC); } void proc_set_convention(Pool *pool, i64 proc, i16 convention) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[proc].is_enabled); BX_ASSERT(pool->entities[proc].type == ENTITY_PROC); pool->entities[proc].proc.convention = convention; } void proc_set_name(Pool *pool, i64 proc, i64 name_size, c8 *name) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[proc].is_enabled); BX_ASSERT(pool->entities[proc].type == ENTITY_PROC); BX_ASSERT(name_size <= MAX_NAME_SIZE); BX_ASSERT(name_size >= 0); Proc *p = &pool->entities[proc].proc; p->name_size = name_size; if (name_size > 0) bx_mem_cpy(p->name, name, name_size); } void proc_node_add(Pool *pool, i64 proc, i64 node) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[proc].is_enabled); BX_ASSERT(pool->entities[proc].type == ENTITY_PROC); BX_ASSERT(pool->entities[node].is_enabled); BX_ASSERT(pool->entities[node].type == ENTITY_NODE); Proc *p = &pool->entities[proc].proc; Node *n = &pool->entities[node].node; BX_ASSERT(n->index_in_proc == UNDEFINED); i64 index = p->node_count; if (n->op == CTRL_RET) { // Only one return node is allowed. // BX_ASSERT(p->ret_index == UNDEFINED); p->ret_index = index; } BX_ASSERT(index < MAX_NODE_COUNT); n->index_in_proc = index; p->nodes[index] = node; ++p->node_count; } void proc_node_remove(Pool *pool, i64 proc, i64 node) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[proc].is_enabled); BX_ASSERT(pool->entities[proc].type == ENTITY_PROC); BX_ASSERT(pool->entities[node].type == ENTITY_NODE); Proc *p = &pool->entities[proc].proc; Node *n = &pool->entities[node].node; BX_ASSERT(n->index_in_proc != UNDEFINED); BX_ASSERT(p->nodes[n->index_in_proc] == node); if (n->op == CTRL_RET) { BX_ASSERT(p->ret_index != UNDEFINED); p->ret_index = UNDEFINED; } p->nodes[n->index_in_proc] = UNDEFINED; n->index_in_proc = UNDEFINED; } i64 unit_init(Pool *pool, i16 type) { return pool_add(pool, (Entity) { .type = ENTITY_UNIT, .unit = (Unit) { .type = type, .entry_point_index = UNDEFINED, } }); } void unit_destroy(Pool *pool, i64 unit) { pool_remove(pool, unit, ENTITY_UNIT); } void unit_proc_add(Pool *pool, i64 unit, i64 proc) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[unit].is_enabled); BX_ASSERT(pool->entities[unit].type == ENTITY_UNIT); BX_ASSERT(pool->entities[proc].is_enabled); BX_ASSERT(pool->entities[proc].type == ENTITY_PROC); Unit *u = &pool->entities[unit].unit; Proc *p = &pool->entities[proc].proc; BX_ASSERT(p->index_in_unit == UNDEFINED); i64 index = u->proc_count; BX_ASSERT(index < MAX_PROC_COUNT); p->index_in_unit = index; u->procs[index] = proc; ++u->proc_count; } void unit_proc_remove(Pool *pool, i64 unit, i64 proc) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[unit].is_enabled); BX_ASSERT(pool->entities[unit].type == ENTITY_UNIT); BX_ASSERT(pool->entities[proc].type == ENTITY_PROC); Unit *u = &pool->entities[unit].unit; Proc *p = &pool->entities[proc].proc; BX_ASSERT(p->index_in_unit != UNDEFINED); BX_ASSERT(u->procs[p->index_in_unit] == proc); if (u->entry_point_index == p->index_in_unit) u->entry_point_index = UNDEFINED; u->procs[p->index_in_unit] = UNDEFINED; p->index_in_unit = UNDEFINED; } void unit_link_add(Pool *pool, i64 unit, i64 link_unit) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[unit].is_enabled); BX_ASSERT(pool->entities[unit].type == ENTITY_UNIT); BX_ASSERT(pool->entities[link_unit].is_enabled); BX_ASSERT(pool->entities[link_unit].type == ENTITY_UNIT); Unit *u = &pool->entities[unit].unit; for (i64 i = 0; i < u->link_count; ++i) if (u->links[i] == link_unit) return; BX_ASSERT(u->link_count < MAX_LINK_COUNT); u->links[u->link_count++] = link_unit; } void unit_link_remove(Pool *pool, i64 unit, i64 link_unit) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[unit].is_enabled); BX_ASSERT(pool->entities[unit].type == ENTITY_UNIT); BX_ASSERT(pool->entities[link_unit].type == ENTITY_UNIT); Unit *u = &pool->entities[unit].unit; for (i64 i = 0; i < u->link_count; ++i) if (u->links[i] == link_unit) { u->links[i] = UNDEFINED; return; } BX_ASSERT(0); } void unit_set_name(Pool *pool, i64 unit, i64 name_size, c8 *name) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[unit].is_enabled); BX_ASSERT(pool->entities[unit].type == ENTITY_UNIT); BX_ASSERT(name_size <= MAX_NAME_SIZE); BX_ASSERT(name_size >= 0); Unit *u = &pool->entities[unit].unit; u->name_size = name_size; if (name_size > 0) bx_mem_cpy(u->name, name, name_size); } void unit_set_entry_point(Pool *pool, i64 unit, i64 entry_point_proc) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[unit].is_enabled); BX_ASSERT(pool->entities[unit].type == ENTITY_UNIT); Unit *u = &pool->entities[unit].unit; if (entry_point_proc == UNDEFINED) { u->entry_point_index = UNDEFINED; return; } BX_ASSERT(pool->entities[entry_point_proc].is_enabled); BX_ASSERT(pool->entities[entry_point_proc].type == ENTITY_PROC); Proc *p = &pool->entities[entry_point_proc].proc; BX_ASSERT(p->index_in_unit != UNDEFINED); BX_ASSERT(u->procs[p->index_in_unit] == entry_point_proc); pool->entities[unit].unit.entry_point_index = p->index_in_unit; } // ================================================================ // // * Serialization // // ================================================================ typedef struct { unsigned little:1; } Bits; i32 host_bit_order() { if ((*(Bits *) &(u8) { 1 }).little == 1) return LE; return BE; } i32 host_byte_order() { if (((u8 *) &(u32) { 1 })[0] == 1) return LE; return BE; } i32 host_f64_dword_order() { if ((*(u64 *) &(f64) { -1.4575323640233e-306 } & 0xffffffffull) == 0x40301fcbull) return host_byte_order(); if ((*(u64 *) &(f64) { -1.4575323640233e-306 } & 0xffffffff00000000ull) == 0x40301fcb00000000ull) return host_byte_order() == LE ? BE : LE; BX_ASSERT(0 && "Unknown native floating-point number format"); return 0; } u8 read_u8(i32 bit_order, u8 *v) { if (bit_order == host_bit_order()) return *v; return ((*v >> 7) & 1) | (((*v >> 6) & 1) << 1) | (((*v >> 5) & 1) << 2) | (((*v >> 4) & 1) << 3) | (((*v >> 3) & 1) << 4) | (((*v >> 2) & 1) << 5) | (((*v >> 1) & 1) << 6) | (((*v) & 1) << 7); } u16 read_u16(i32 bit_order, i32 byte_order, u8 *v, u8 *v_end) { BX_ASSERT(v != NULL); BX_ASSERT(v + 2 <= v_end); if (byte_order == host_byte_order()) return ((u16) read_u8(bit_order, v)) | (((u16) read_u8(bit_order, v + 1)) << 8); return ((u16) read_u8(bit_order, v + 1)) | (((u16) read_u8(bit_order, v)) << 8); } u32 read_u32(i32 bit_order, i32 byte_order, u8 *v, u8 *v_end) { BX_ASSERT(v != NULL); BX_ASSERT(v + 4 <= v_end); if (byte_order == host_byte_order()) return ((u32) read_u8(bit_order, v)) | (((u32) read_u8(bit_order, v + 1)) << 8) | (((u32) read_u8(bit_order, v + 2)) << 16) | (((u32) read_u8(bit_order, v + 3)) << 24); return ((u32) read_u8(bit_order, v + 3)) | (((u32) read_u8(bit_order, v + 2)) << 8) | (((u32) read_u8(bit_order, v + 1)) << 16) | (((u32) read_u8(bit_order, v)) << 24); } u64 read_u64(i32 bit_order, i32 byte_order, u8 *v, u8 *v_end) { BX_ASSERT(v != NULL); BX_ASSERT(v + 8 <= v_end); if (byte_order == host_byte_order()) return ((u64) read_u8(bit_order, v)) | (((u64) read_u8(bit_order, v + 1)) << 8) | (((u64) read_u8(bit_order, v + 2)) << 16) | (((u64) read_u8(bit_order, v + 3)) << 24) | (((u64) read_u8(bit_order, v + 4)) << 32) | (((u64) read_u8(bit_order, v + 5)) << 40) | (((u64) read_u8(bit_order, v + 6)) << 48) | (((u64) read_u8(bit_order, v + 7)) << 56); return ((u64) read_u8(bit_order, v + 7)) | (((u64) read_u8(bit_order, v + 6)) << 8) | (((u64) read_u8(bit_order, v + 5)) << 16) | (((u64) read_u8(bit_order, v + 4)) << 24) | (((u64) read_u8(bit_order, v + 3)) << 32) | (((u64) read_u8(bit_order, v + 2)) << 40) | (((u64) read_u8(bit_order, v + 1)) << 48) | (((u64) read_u8(bit_order, v)) << 56); } void write_u8(i32 bit_order, u8 x, u8 *v) { BX_ASSERT(v != NULL); if (bit_order == host_bit_order()) *v = x; else *v = ((x >> 7) & 1) | (((x >> 6) & 1) << 1) | (((x >> 5) & 1) << 2) | (((x >> 4) & 1) << 3) | (((x >> 3) & 1) << 4) | (((x >> 2) & 1) << 5) | (((x >> 1) & 1) << 6) | (((x) & 1) << 7); } void write_u16(i32 bit_order, i32 byte_order, u16 x, u8 *v, u8 *v_end) { BX_ASSERT(v != NULL); BX_ASSERT(v + 2 <= v_end); if (byte_order == host_byte_order()) { write_u8(bit_order, (u8) ( x & 0xff), v); write_u8(bit_order, (u8) ((x >> 8) & 0xff), v + 1); } else { write_u8(bit_order, (u8) ( x & 0xff), v + 1); write_u8(bit_order, (u8) ((x >> 8) & 0xff), v); } } void write_u32(i32 bit_order, i32 byte_order, u32 x, u8 *v, u8 *v_end) { BX_ASSERT(v != NULL); BX_ASSERT(v + 4 <= v_end); if (byte_order == host_byte_order()) { write_u8(bit_order, (u8) ( x & 0xff), v); write_u8(bit_order, (u8) ((x >> 8) & 0xff), v + 1); write_u8(bit_order, (u8) ((x >> 16) & 0xff), v + 2); write_u8(bit_order, (u8) ((x >> 24) & 0xff), v + 3); } else { write_u8(bit_order, (u8) ( x & 0xff), v + 3); write_u8(bit_order, (u8) ((x >> 8) & 0xff), v + 2); write_u8(bit_order, (u8) ((x >> 16) & 0xff), v + 1); write_u8(bit_order, (u8) ((x >> 24) & 0xff), v); } } void write_u64(i32 bit_order, i32 byte_order, u64 x, u8 *v, u8 *v_end) { BX_ASSERT(v != NULL); BX_ASSERT(v + 8 <= v_end); if (byte_order == host_byte_order()) { write_u8(bit_order, (u8) ( x & 0xff), v); write_u8(bit_order, (u8) ((x >> 8) & 0xff), v + 1); write_u8(bit_order, (u8) ((x >> 16) & 0xff), v + 2); write_u8(bit_order, (u8) ((x >> 24) & 0xff), v + 3); write_u8(bit_order, (u8) ((x >> 32) & 0xff), v + 4); write_u8(bit_order, (u8) ((x >> 40) & 0xff), v + 5); write_u8(bit_order, (u8) ((x >> 48) & 0xff), v + 6); write_u8(bit_order, (u8) ((x >> 56) & 0xff), v + 7); } else { write_u8(bit_order, (u8) ( x & 0xff), v + 7); write_u8(bit_order, (u8) ((x >> 8) & 0xff), v + 6); write_u8(bit_order, (u8) ((x >> 16) & 0xff), v + 5); write_u8(bit_order, (u8) ((x >> 24) & 0xff), v + 4); write_u8(bit_order, (u8) ((x >> 32) & 0xff), v + 3); write_u8(bit_order, (u8) ((x >> 40) & 0xff), v + 2); write_u8(bit_order, (u8) ((x >> 48) & 0xff), v + 1); write_u8(bit_order, (u8) ((x >> 56) & 0xff), v); } } i16 read_i16(i32 bit_order, i32 byte_order, void *v, void *v_end) { return (i16) read_u16(bit_order, byte_order, v, v_end); } i32 read_i32(i32 bit_order, i32 byte_order, void *v, void *v_end) { return (i32) read_u32(bit_order, byte_order, v, v_end); } i64 read_i64(i32 bit_order, i32 byte_order, void *v, void *v_end) { return (i64) read_u64(bit_order, byte_order, v, v_end); } f32 read_f32(i32 bit_order, i32 byte_order, void *v, void *v_end) { host_f64_dword_order(); // FIXME return *(f32 *) &(u32) { read_u32(bit_order, byte_order, v, v_end) }; } f32 read_f64(i32 bit_order, i32 byte_order, i32 f64_dword_order, void *v, void *v_end) { u64 x = read_u64(bit_order, byte_order, v, v_end); if (f64_dword_order != host_f64_dword_order()) x = ((x & 0xffffffffull) << 32) | ((x >> 32) & 0xffffffffull); return *(f64 *) &x; } void write_i16(i32 bit_order, i32 byte_order, i16 x, void *v, void *v_end) { write_u16(bit_order, byte_order, (u16) x, v, v_end); } void write_i32(i32 bit_order, i32 byte_order, i32 x, void *v, void *v_end) { write_u32(bit_order, byte_order, (u32) x, v, v_end); } void write_i64(i32 bit_order, i32 byte_order, i64 x, void *v, void *v_end) { write_u64(bit_order, byte_order, (u64) x, v, v_end); } void write_f32(i32 bit_order, i32 byte_order, f32 x, void *v, void *v_end) { host_f64_dword_order(); // FIXME write_u32(bit_order, byte_order, *(u32 *) &x, v, v_end); } void write_f64(i32 bit_order, i32 byte_order, i32 f64_dword_order, f64 x, void *v, void *v_end) { if (f64_dword_order == host_f64_dword_order()) write_u64(bit_order, byte_order, *(u64 *) &x, v, v_end); else { write_u32(bit_order, byte_order, *(((u32 *) &x) + 1), (u8 *) v, v_end); write_u32(bit_order, byte_order, * (u32 *) &x, ((u8 *) v) + 4, v_end); } } #define HBIO host_bit_order() #define HBYO host_byte_order() #define HO_u8 host_bit_order() #define HO_u16 host_bit_order(), host_byte_order() #define HO_u32 host_bit_order(), host_byte_order() #define HO_u64 host_bit_order(), host_byte_order() #define HO_f32 host_bit_order(), host_byte_order() #define HO_f64 host_bit_order(), host_byte_order(), host_f64_dword_order() // ================================================================ // // * Code generation and linking // // ---------------------------------------------------------------- // // Docs and helpful materials // // AR https://man.freebsd.org/cgi/man.cgi?query=ar&sektion=5 // ELF https://man7.org/linux/man-pages/man5/elf.5.html // // Relocation types // https://intezer.com/blog/malware-analysis/executable-and-linkable-format-101-part-3-relocations/ // https://docs.oracle.com/cd/E19120-01/open.solaris/819-0690/chapter7-2/index.html // // https://web.archive.org/web/20150324024617/http://mylinuxbook.com/readelf-command/ // // LLVM impl https://github.com/llvm/llvm-project/blob/main/lld/ELF/Driver.cpp#L2822 // https://github.com/llvm/llvm-project/blob/main/lld/ELF/Writer.cpp#L304 // https://github.com/llvm/llvm-project/blob/main/lld/ELF/OutputSections.cpp#L469 // // Online assembler // https://defuse.ca/online-x86-assembler.htm // https://shell-storm.org/online/Online-Assembler-and-Disassembler/ // // Linux syscall // https://man7.org/linux/man-pages/man2/intro.2.html // https://man7.org/linux/man-pages/man2/syscalls.2.html // https://man7.org/linux/man-pages/man2/syscall.2.html // // ---------------------------------------------------------------- // // TODO Experiment with mapping several p_vaddr into one p_paddr. // // ================================================================ #include // TEMP #include // TEMP // TODO enum { MAX_SECTION_SIZE = 1024 * 1024 * 10, MAX_SYMBOL_NAME_SIZE = 1024, MAX_INPUT_SIZE = 1024 * 1024 * 100, MAX_SYMBOLS = 1024 * 100, MAX_RELOCATIONS = 1024 * 100, MAX_INPUT_SECTIONS = 1024 * 10, }; typedef struct { i64 address_in_memory; i64 offset_in_file; i64 size; u8 bytes[MAX_SECTION_SIZE]; } Section; typedef struct { i64 src_section; i64 src_offset_in_file; i64 src_size; i64 name_size; c8 name[MAX_SYMBOL_NAME_SIZE]; } Symbol; typedef struct { i64 src_section; i64 src_offset_in_file; i64 src_size; i64 dst_section; i64 dst_address_in_memory; } Relocation; typedef struct { i64 object; i64 section; i64 offset_in_file; i64 size; } Input_Section_Info; typedef struct { Section exec; Section read_only; Section read_write; Section zero_init; i64 symbols_size; Symbol symbols[MAX_SYMBOLS]; i64 relocs_size; Relocation relocs[MAX_RELOCATIONS]; i64 input_raw_size; u8 input_raw[MAX_INPUT_SIZE]; i64 input_sections_size; Input_Section_Info input_sections[MAX_INPUT_SECTIONS]; } Binary_Output; // ================================================================ typedef struct { u64 offset; u64 size; } Offset_Size; typedef struct { u64 offset; u16 count; } Offset_Count; typedef struct { Offset_Size name; u32 type; u64 flags; Offset_Size data; } Section_Header; typedef struct { Offset_Size name; u8 info; Offset_Size section; Offset_Size value; } Symbol_Entry; typedef struct { Offset_Size dst; Offset_Size symbol; u32 type; } Rel_Entry; typedef struct { Offset_Size dst; Offset_Size symbol; u32 type; i64 addent; } Rela_Entry; c8 ELF_MAGIC[4] = "\x7f" "ELF"; u8 ELF_64 = 2; u8 ELF_2_LE = 1; u8 ELF_VERSION = 1; u8 ELF_SYS_V = 0; u8 ELF_LINUX = 3; u8 ELF_ABI_VERSION = 0; u16 ELF_RELOCATABLE = 1; u16 ELF_EXECUTABLE = 2; u16 ELF_X86_64 = 62; u16 ELF_HEADER_SIZE = 64; u16 ELF_PROGRAM_HEADER_SIZE = 56; u16 ELF_SECTION_HEADER_SIZE = 64; u64 X86_64_BASE_ADDRESS = 0x400000; u64 X86_64_ALIGNMENT = 8; c8 AR_MAGIC[8] = "!\n"; c8 AR_SYMBOL_TABLE[] = "/ "; c8 AR_STRING_TABLE[] = "// "; c8 STRTAB[] = ".strtab"; // ================================================================ u32 ar_find_symbol_offset_by_name(u8 *ar_symbol_table, u8 *ar_end, c8 *name, c8 *name_end) { BX_ASSERT(ar_symbol_table != NULL); BX_ASSERT(name != NULL); BX_ASSERT(name_end > name); u32 count = read_u32(HBIO, BE, ar_symbol_table, ar_end); i64 len = name_end - name; c8 *s = (c8 *) (ar_symbol_table + 4 * (count + 1)); u32 index = 0; for (; index < count; ++index) { BX_ASSERT(s + len <= (c8 *) ar_end); if (s[len] == '\0' && bx_mem_eq(s, name, len)) return read_u32(HBIO, BE, ar_symbol_table + 4 * (index + 1), ar_end); while (*s != '\0' && s < (c8 *) ar_end) ++s; BX_ASSERT(s < (c8 *) ar_end); BX_ASSERT(*s == '\0'); ++s; } BX_ASSERT(0); return 0; } u16 elf_section_names_table_index( u8 *elf_begin, u8 *elf_end ) { return read_u16(HBIO, HBYO, elf_begin + 62, elf_end); } Offset_Count elf_section_headers( u8 *elf_begin, u8 *elf_end ) { return (Offset_Count) { .offset = read_u64(HBIO, HBYO, elf_begin + 40, elf_end), .count = read_u16(HBIO, HBYO, elf_begin + 60, elf_end), }; } u64 elf_section_header_offset( u8 *elf_begin, u8 *elf_end, u16 index ) { return elf_section_headers(elf_begin, elf_end).offset + ELF_SECTION_HEADER_SIZE * index; } Offset_Size elf_section_names_data( u8 *elf_begin, u8 *elf_end ) { u16 string_table_index = elf_section_names_table_index(elf_begin, elf_end); u8 *begin = elf_begin + elf_section_header_offset(elf_begin, elf_end, string_table_index); return (Offset_Size) { .offset = read_u64(HBIO, HBYO, begin + 24, elf_end), .size = read_u64(HBIO, HBYO, begin + 32, elf_end), }; } Offset_Size elf_name_in_string_table( u8 * elf_begin, u8 * elf_end, Offset_Size string_table, u32 name_offset ) { u64 offset = string_table.offset + name_offset; c8 *begin = (c8 *) (elf_begin + offset); c8 *end = begin + string_table.size; BX_ASSERT(end <= (c8 *) elf_end); return (Offset_Size) { .offset = offset, .size = bx_str_len(begin, end), }; } u64 elf_find_section_header_by_name( u8 * elf_begin, u8 * elf_end, c8 * name, u32 name_size ) { Offset_Count headers = elf_section_headers(elf_begin, elf_end); Offset_Size names = elf_section_names_data(elf_begin, elf_end); for (u16 i = 0; i < headers.count; ++i) { u8 *begin = elf_begin + headers.offset + i * ELF_SECTION_HEADER_SIZE; u32 name_offset = read_u32(HBIO, HBYO, begin, elf_end); if (name_offset + name_size <= names.size && bx_mem_eq(elf_begin + names.offset + name_offset, name, name_size)) return headers.offset + i * ELF_SECTION_HEADER_SIZE; } BX_ASSERT(0); return 0; } Section_Header elf_section_data_by_offset( u8 *elf_begin, u8 *elf_end, u64 offset ) { Offset_Size names = elf_section_names_data(elf_begin, elf_end); u8 * begin = elf_begin + offset; u32 name_index = read_u32(HBIO, HBYO, begin, elf_end); return (Section_Header) { .name = elf_name_in_string_table( elf_begin, elf_end, names, name_index ), .type = read_u32(HBIO, HBYO, begin + 4, elf_end), .flags = read_u64(HBIO, HBYO, begin + 8, elf_end), .data = { .offset = read_u64(HBIO, HBYO, begin + 24, elf_end), .size = read_u64(HBIO, HBYO, begin + 32, elf_end), }, }; } void unit_write(Pool *pool, i64 unit, u16 target, i64 io_out, void *io_user_data) { BX_ASSERT(pool != NULL && pool->entities != NULL); BX_ASSERT(pool->entities[unit].is_enabled); BX_ASSERT(pool->entities[unit].unit.entry_point_index != UNDEFINED); BX_ASSERT(target == (FORMAT_ELF | ARCH_X86_64)); // ============================================================== #define WRITE(x, n) io_write( io_out, n, x, io_user_data ) #define WRITE_V(...) io_write( io_out, sizeof((u8[]) {__VA_ARGS__}), (u8[]) {__VA_ARGS__}, io_user_data ) #define WRITE_DUP(x, n) io_write( io_out, n, (u8[n]) { 0 }, io_user_data ) #define WRITE_2(x) io_write( io_out, 2, &(u16) { x }, io_user_data ) #define WRITE_4(x) io_write( io_out, 4, &(u32) { x }, io_user_data ) #define WRITE_8(x) io_write( io_out, 8, &(u64) { x }, io_user_data ) u8 code[32] = { 0xb8, 0x3c, 0x00, 0x00, 0x00, // mov eax, 60 0xbf, 0x2a, 0x00, 0x00, 0x00, // mov edi, 42 0x0f, 0x05, // syscall }; u64 code_offset = bx_align(ELF_HEADER_SIZE + ELF_PROGRAM_HEADER_SIZE, X86_64_ALIGNMENT); u64 code_size = bx_align(sizeof code, X86_64_ALIGNMENT); u64 entry_offset = 0; u64 base_address = X86_64_BASE_ADDRESS; u64 code_address = base_address + code_offset; u64 entry = code_address + entry_offset; BX_ASSERT((code_offset % X86_64_ALIGNMENT) == 0); BX_ASSERT((code_size % X86_64_ALIGNMENT) == 0); // ELF header // WRITE ( ELF_MAGIC, 4 ); WRITE_V( ELF_64 ); WRITE_V( ELF_2_LE ); WRITE_V( ELF_VERSION ); WRITE_V( ELF_SYS_V ); WRITE_V( ELF_ABI_VERSION ); WRITE_DUP(0, 7); // padding WRITE_2( ELF_EXECUTABLE ); WRITE_2( ELF_X86_64 ); WRITE_4( ELF_VERSION ); WRITE_8( entry ); WRITE_8( ELF_HEADER_SIZE ); WRITE_8( 0 ); // section header offset WRITE_4( 0 ); // flags WRITE_2( ELF_HEADER_SIZE ); WRITE_2( ELF_PROGRAM_HEADER_SIZE ); WRITE_2( 1 ); // program header count WRITE_2( 0 ); // section header size WRITE_2( 0 ); // section header count WRITE_2( 0 ); // string table section header index // Program header // WRITE_4( 1 ); // type (PT_LOAD) WRITE_4( 5 ); // flags (PF_X | PF_R) WRITE_8( code_offset ); WRITE_8( code_address ); // virtual address WRITE_8( code_address ); // phisical address WRITE_8( code_size ); // size in file WRITE_8( code_size ); // size in memory WRITE_8( X86_64_ALIGNMENT ); // Code // for (i64 i = code_offset - ELF_HEADER_SIZE - ELF_PROGRAM_HEADER_SIZE; i > 0; --i) WRITE_V( 0 ); WRITE( code, code_size ); #undef WRITE_V #undef WRITE_DUP #undef WRITE_32 #undef WRITE_64 #undef WRITE // ============================================================== // Intermediate buffer // if (0) { u8 static in_buffer[1024 * 1024 * 300]; // 300 MB i64 static ar_offsets[128]; i64 ar_count = 0; // Read all dependency files into the memory // { Unit *u = &pool->entities[unit].unit; for (i64 link_index = 0; link_index < u->link_count; ++link_index) { i64 id = u->links[link_index]; if (id == UNDEFINED) continue; BX_ASSERT(ar_count + 1 < (i64) (sizeof ar_offsets / sizeof *ar_offsets)); Unit *l = &pool->entities[id].unit; BX_ASSERT(pool->entities[id].is_enabled); BX_ASSERT(l->type == UNIT_LIBRARY_STATIC); BX_ASSERT(l->name_size > 0 && l->name_size <= MAX_NAME_SIZE); i64 f = io_open_read(l->name_size, l->name, io_user_data); io_seek(f, 0, IO_SEEK_END, io_user_data); i64 size = io_tell(f, io_user_data); io_seek(f, 0, IO_SEEK_BEGIN, io_user_data); if (ar_count == 0) ar_offsets[ar_count] = 0; ar_offsets[ar_count + 1] = ar_offsets[ar_count] + bx_align(size, 8); i64 n = io_read(f, size, in_buffer + ar_offsets[ar_count], io_user_data); BX_ASSERT(n == size); ++ar_count; io_close(f, io_user_data); } } for (i64 ar_index = 0; ar_index < ar_count; ++ar_index) { // ================================================================ // // Read AR library u8 *ar_begin = in_buffer + ar_offsets[ar_index]; u8 *ar_end = in_buffer + ar_offsets[ar_index + 1]; u8 *ar_symbol_table = NULL; u8 *ar_string_table = NULL; BX_ASSERT(bx_mem_eq(ar_begin, AR_MAGIC, 8)); u8 *f_begin = ar_begin + 8; while (f_begin + 60 < ar_end) { u8 *f_id = f_begin; u8 *f_size = f_begin + 48; u8 *f_end = f_begin + 58; u8 *f_data = f_begin + 60; i64 fn_size; { c8 buf[7] = {0}; bx_mem_cpy(buf, f_size, 6); fn_size = atoi(buf); } fn_size = bx_align(fn_size, 2); BX_ASSERT(bx_mem_eq(f_end, "\x60\x0a", 2)); BX_ASSERT(f_begin + fn_size <= ar_end); if (bx_mem_eq(f_id, AR_SYMBOL_TABLE, 16)) { // AR symbol table // ar_symbol_table = f_data; f_begin = f_data + fn_size; } else if (bx_mem_eq(f_id, AR_STRING_TABLE, 16)) { // String table // ar_string_table = f_data; f_begin = f_data + fn_size; } else { // ======================================================== // // Decode ELF object file u8 *elf_begin = f_data; u8 *elf_end = f_begin + fn_size; f_begin = elf_end; u64 section_header_offset; u16 section_count; u16 string_table_index; u16 string_table_offset; BX_ASSERT(read_u8(HBIO, elf_begin) == ELF_MAGIC[0]); BX_ASSERT(read_u8(HBIO, elf_begin + 1) == ELF_MAGIC[1]); BX_ASSERT(read_u8(HBIO, elf_begin + 2) == ELF_MAGIC[2]); BX_ASSERT(read_u8(HBIO, elf_begin + 3) == ELF_MAGIC[3]); BX_ASSERT(read_u8(HBIO, elf_begin + 4) == ELF_64); BX_ASSERT(read_u8(HBIO, elf_begin + 5) == ELF_2_LE); BX_ASSERT(read_u8(HBIO, elf_begin + 6) == ELF_VERSION); u8 osabi = read_u8(HBIO, elf_begin + 7); BX_ASSERT(osabi == ELF_SYS_V || osabi == ELF_LINUX); BX_ASSERT(read_u8(HBIO, elf_begin + 8) == ELF_ABI_VERSION); BX_ASSERT(read_u16(HBIO, HBYO, elf_begin + 16, elf_end) == ELF_RELOCATABLE); BX_ASSERT(read_u16(HBIO, HBYO, elf_begin + 18, elf_end) == ELF_X86_64); BX_ASSERT(read_u32(HBIO, HBYO, elf_begin + 20, elf_end) == ELF_VERSION); BX_ASSERT(read_u64(HBIO, HBYO, elf_begin + 24, elf_end) == 0); // entry BX_ASSERT(read_u64(HBIO, HBYO, elf_begin + 32, elf_end) == 0); // program header offset section_header_offset = read_u64(HBIO, HBYO, elf_begin + 40, elf_end); BX_ASSERT(read_u32(HBIO, HBYO, elf_begin + 48, elf_end) == 0); // flags BX_ASSERT(read_u16(HBIO, HBYO, elf_begin + 52, elf_end) == ELF_HEADER_SIZE); BX_ASSERT(read_u16(HBIO, HBYO, elf_begin + 54, elf_end) == 0); // program header size BX_ASSERT(read_u16(HBIO, HBYO, elf_begin + 56, elf_end) == 0); // program header count BX_ASSERT(read_u16(HBIO, HBYO, elf_begin + 58, elf_end) == ELF_SECTION_HEADER_SIZE); section_count = read_u16(HBIO, HBYO, elf_begin + 60, elf_end); string_table_index = read_u16(HBIO, HBYO, elf_begin + 62, elf_end); string_table_offset = read_u64(HBIO, HBYO, elf_begin + section_header_offset + string_table_index * ELF_SECTION_HEADER_SIZE + 24, elf_end); (void) ar_symbol_table; (void) ar_string_table; (void) section_header_offset; (void) section_count; (void) string_table_index; (void) string_table_offset; f_begin = f_data + fn_size; // ======================================================== } } } return; } // ============================================================== // Read dependencies // { Unit *u = &pool->entities[unit].unit; for (i64 i = 0; i < u->link_count; ++i) { if (u->links[i] == UNDEFINED) continue; i64 index = u->links[i]; Unit *l = &pool->entities[index].unit; BX_ASSERT(pool->entities[index].is_enabled); BX_ASSERT(l->type == UNIT_LIBRARY_STATIC); BX_ASSERT(l->name_size > 0 && l->name_size <= MAX_NAME_SIZE); i64 f = io_open_read(l->name_size, l->name, io_user_data); c8 buf0_[MAX_NAME_SIZE + 1] = { 0 }; bx_mem_cpy(buf0_, l->name, l->name_size); printf("\nReading `%s` library...\n\n", buf0_); i64 n = 0, current_offset = 0; // ========================================================== // // Read AR library u8 magic[8]; n = io_read(f, sizeof magic, magic, io_user_data); if (n == 0) continue; current_offset += n; BX_ASSERT(magic[0] == '!'); BX_ASSERT(magic[1] == '<'); BX_ASSERT(magic[2] == 'a'); BX_ASSERT(magic[3] == 'r'); BX_ASSERT(magic[4] == 'c'); BX_ASSERT(magic[5] == 'h'); BX_ASSERT(magic[6] == '>'); BX_ASSERT(magic[7] == '\n'); u32 static offsets[10000] = { 0 }; c8 static symbols[10000][256] = { 0 }; b8 static found[10000] = { 0 }; i64 num_symbols = 0; for (;;) { c8 id[17] = { 0 }; c8 timestamp[13] = { 0 }; c8 owner[7] = { 0 }; c8 group[7] = { 0 }; c8 mode[9] = { 0 }; c8 size[11] = { 0 }; c8 end[2] = { 0 }; i64 file_offset = current_offset; n = io_read(f, (sizeof id) - 1, id, io_user_data); if (n == 0) break; current_offset += n; n = io_read(f, (sizeof timestamp) - 1, timestamp, io_user_data); if (n == 0) break; current_offset += n; n = io_read(f, (sizeof owner) - 1, owner, io_user_data); if (n == 0) break; current_offset += n; n = io_read(f, (sizeof group) - 1, group, io_user_data); if (n == 0) break; current_offset += n; n = io_read(f, (sizeof mode) - 1, mode, io_user_data); if (n == 0) break; current_offset += n; n = io_read(f, (sizeof size) - 1, size, io_user_data); if (n == 0) break; current_offset += n; n = io_read(f, sizeof end, end, io_user_data); if (n == 0) break; current_offset += n; BX_ASSERT(end[0] == '\x60'); BX_ASSERT(end[1] == '\x0a'); if (bx_str_eq(id, id + 16, AR_SYMBOL_TABLE, AR_SYMBOL_TABLE + 16)) { // AR symbol table // u32 count_be; n = io_read(f, 4, &count_be, io_user_data); if (n == 0) break; current_offset += n; num_symbols = (( count_be & 0xffu) << 24) | (((count_be >> 8) & 0xffu) << 16) | (((count_be >> 16) & 0xffu) << 8) | ((count_be >> 24) & 0xffu); printf("Symbol table - %lld symbols.\n\n", num_symbols); BX_ASSERT(num_symbols <= (i64) (sizeof offsets / sizeof *offsets)); for (u32 j = 0; j < num_symbols; ++j) { u32 offset_be; n = io_read(f, 4, &offset_be, io_user_data); if (n == 0) break; current_offset += n; offsets[j] = (( offset_be & 0xffu) << 24) | (((offset_be >> 8) & 0xffu) << 16) | (((offset_be >> 16) & 0xffu) << 8) | ((offset_be >> 24) & 0xffu); } if (n == 0) break; i64 byte_count = 0; for (u32 j = 0; j < num_symbols; ++j) { i64 symbol_size = 0; for (;; ++symbol_size) { c8 c; n = io_read(f, 1, &c, io_user_data); if (n == 0) break; current_offset += n; ++byte_count; if (c == '\0') break; BX_ASSERT(symbol_size < 256); if (symbol_size < 256) symbols[j][symbol_size] = c; } if (n == 0) break; } if (n == 0) break; if ((byte_count & 1) == 1) { // align io_seek(f, 1, IO_SEEK_CURSOR, io_user_data); current_offset += 1; } } else if (bx_str_eq(id, id + 16, AR_STRING_TABLE, AR_STRING_TABLE + 16)) { // String table // i64 byte_count = atoi(size); if ((byte_count & 1) == 1) ++byte_count; // align b8 has_line = 0; while (byte_count > 0) { c8 c; n = io_read(f, 1, &c, io_user_data); if (n == 0) break; current_offset += n; byte_count -= n; if (c == '\0') { if (has_line) { printf("\n"); has_line = 0; } } else { if (c == '/') { if (!has_line) printf(""); } else printf("%c", c); has_line = 1; } } } else { if (bx_find_char(id, id + 16, '/') != NULL) *bx_find_char(id, id + 16, '/') = '\0'; if (bx_find_char(size, size + 6, ' ') != NULL) *bx_find_char(size, size + 6, ' ') = '\0'; printf("%08llx %-16s - %5s bytes\n\n", file_offset, id, size); // Search for symbols pointing to the current file // { b8 symbol_found = 0; for (i64 symbol_index = 0; symbol_index < num_symbols; ++symbol_index) if (offsets[symbol_index] == file_offset) { printf(" %-50s\n", symbols[symbol_index]); found[symbol_index] = 1; symbol_found = 1; } if (!symbol_found) printf(" \n"); } // ====================================================== // // Decode ELF object file i64 byte_count = atoi(size); if ((byte_count & 1) == 1) ++byte_count; // align i64 begin_offset = current_offset; u8 buf[16]; n = io_read(f, sizeof buf, buf, io_user_data); if (n == 0) break; current_offset += n; byte_count -= n; BX_ASSERT(buf[0] == 0x7f); BX_ASSERT(buf[1] == 'E'); BX_ASSERT(buf[2] == 'L'); BX_ASSERT(buf[3] == 'F'); BX_ASSERT(buf[4] == ELF_64); BX_ASSERT(buf[5] == ELF_2_LE); BX_ASSERT(buf[6] == ELF_VERSION); BX_ASSERT(buf[7] == ELF_SYS_V || buf[7] == ELF_LINUX); // SysV or Linux BX_ASSERT(buf[8] == ELF_ABI_VERSION); #define READ(x) do { \ n = io_read(f, sizeof (x), \ &(x), \ io_user_data); \ current_offset += n; \ byte_count -= n; \ } while (0) u64 section_header_offset; u16 section_count; u16 strings_index; u64 strings_offset; u64 symbol_names_offset; u64 symbol_names_size; b8 symbol_names_found = 0; // ELF header // { u16 type; u16 machine; u32 ver; u64 entry; u64 program_header_offset; u32 flags; u16 elf_header_size; u16 program_header_size; u16 program_header_count; u16 section_header_size; READ(type); READ(machine); READ(ver); READ(entry); READ(program_header_offset); READ(section_header_offset); READ(flags); READ(elf_header_size); READ(program_header_size); READ(program_header_count); READ(section_header_size); READ(section_count); READ(strings_index); BX_ASSERT(type == ELF_RELOCATABLE); BX_ASSERT(machine == ELF_X86_64); BX_ASSERT(ver == ELF_VERSION); BX_ASSERT(entry == 0); BX_ASSERT(program_header_offset == 0); BX_ASSERT(flags == 0); BX_ASSERT(elf_header_size == 64); BX_ASSERT(program_header_size == 0); BX_ASSERT(program_header_count == 0); BX_ASSERT(section_header_size == 64); u64 section_offset = section_header_offset - (current_offset - begin_offset); io_seek(f, section_offset, IO_SEEK_CURSOR, io_user_data); byte_count -= section_offset; current_offset += section_offset; // Find offset to the section name string table data // { i64 prev_offset = current_offset; io_seek(f, begin_offset + section_header_offset + strings_index * 64 + 24, IO_SEEK_BEGIN, io_user_data); n = io_read(f, 8, &strings_offset, io_user_data); if (n == 0) break; io_seek(f, prev_offset, IO_SEEK_BEGIN, io_user_data); current_offset = prev_offset; } // Find offset to the symbol string table data // { i64 prev_offset = current_offset; i64 prev_byte_count = byte_count; for (u16 i = 0; i < section_count; ++i) { io_seek(f, begin_offset + section_header_offset + i * 64, IO_SEEK_BEGIN, io_user_data); u32 name; u64 offset; u64 size; READ(name); io_seek(f, 20, IO_SEEK_CURSOR, io_user_data); READ(offset); READ(size); // Search for the name in the string table // io_seek(f, begin_offset + strings_offset + name, IO_SEEK_BEGIN, io_user_data); c8 buf[8]; n = io_read(f, sizeof buf, buf, io_user_data); if (n == 0) break; if (!bx_str_eq(buf, buf + 7, STRTAB, STRTAB + 7)) continue; symbol_names_offset = offset; symbol_names_size = size; symbol_names_found = 1; break; } io_seek(f, prev_offset, IO_SEEK_BEGIN, io_user_data); current_offset = prev_offset; byte_count = prev_byte_count; } } for (u16 i = 0; i < section_count; ++i) { u32 name; u32 type; u64 flags; u64 addr; u64 offset; u64 size; u32 link; u32 info; u64 addralign; u64 entsize; READ(name); READ(type); READ(flags); READ(addr); READ(offset); READ(size); READ(link); READ(info); READ(addralign); READ(entsize); if (type == 0) { printf("\n"); continue; } if (type == 2 || type == 4 || type == 9) // sym/rela/rel printf("%s", "\x1b[32m"); else if ((flags & 2) != 0) // alloc printf("%s", "\x1b[34m"); else if (type == 3) // string table printf("%s", "\x1b[33m"); else printf("%s", "\x1b[31m"); // NOTE // Only alloc (flags & 2) sections should be written to the output binary. // Search for the name in the string table // { i64 prev_offset = current_offset; io_seek(f, begin_offset + strings_offset + name, IO_SEEK_BEGIN, io_user_data); i32 padding = 50; printf(" "); for (;; --padding) { c8 c; n = io_read(f, 1, &c, io_user_data); if (n == 0) break; if (c == '\0') break; printf("%c", c); } if (padding > 0) printf("%*s", padding, ""); io_seek(f, prev_offset, IO_SEEK_BEGIN, io_user_data); current_offset = prev_offset; } printf("%s", "\x1b[37m"); printf( "%-10s", type >= 1 && type <= 9 ? (c8 *[]) { "Program", "Symbols", "Strings", "Rel add", "Hash", "Dynamic", "Note", "Zeros", "Rel", }[type - 1] : type == 17 ? "Group" : "" ); if ((flags & 2) == 2) printf("R"); else printf("_"); if ((flags & 1) == 1) printf("W"); else printf("_"); if ((flags & 4) == 4) printf("X"); else printf("_"); if (size > 0) printf(" - %lld bytes", size); printf("\n"); switch (type) { // ================================================== // // Symbols case 2: { // Find symbol addresses // BX_ASSERT(entsize == 24); i64 prev_offset = current_offset; i64 prev_byte_count = byte_count; io_seek(f, begin_offset + offset, IO_SEEK_BEGIN, io_user_data); current_offset = begin_offset + offset; printf("\n"); for (byte_count = size; byte_count > 0;) { BX_ASSERT(symbol_names_found); u32 sym_name; u8 sym_info; u8 sym_other; u16 sym_shndx; u64 sym_value; u64 sym_size; READ(sym_name); BX_ASSERT(n != 0); READ(sym_info); BX_ASSERT(n != 0); READ(sym_other); BX_ASSERT(n != 0); READ(sym_shndx); BX_ASSERT(n != 0); READ(sym_value); BX_ASSERT(n != 0); READ(sym_size); BX_ASSERT(n != 0); printf(" "); if (sym_name != 0) { if (sym_name < symbol_names_size) { // Search for the symbol name in the string table // i64 prev_offset = current_offset; io_seek(f, begin_offset + symbol_names_offset + sym_name, IO_SEEK_BEGIN, io_user_data); i32 padding = 48; if ((sym_info & 0xf) == 1 || (sym_info & 0xf) == 2) printf("%s", "\x1b[32m"); printf("\""); for (;; --padding) { c8 c; n = io_read(f, 1, &c, io_user_data); if (n == 0) break; if (c == '\0') break; printf("%c", c); } printf("\""); if ((sym_info & 0xf) == 1 || (sym_info & 0xf) == 2) printf("%s", "\x1b[37m"); if (padding > 0) printf("%*s", padding, ""); io_seek(f, prev_offset, IO_SEEK_BEGIN, io_user_data); current_offset = prev_offset; } else printf("%-50d", sym_name); } else printf("%*s", 50, ""); printf("%08llx ", sym_value); // symbol address printf("%-8s ", (sym_info & 0xf) <= 4 ? (c8 *[]) { "No type", "Data", "Func", "Section", "File", }[sym_info & 0xf] : "" ); printf("%-3d", sym_shndx); if (sym_size != 0) printf("- %lld bytes", sym_size); printf("\n"); } printf("\n"); io_seek(f, prev_offset, IO_SEEK_BEGIN, io_user_data); current_offset = prev_offset; byte_count = prev_byte_count; } break; // ================================================== // // Relocarions without addends case 9: { BX_ASSERT(entsize == 16); i64 prev_offset = current_offset; i64 prev_byte_count = byte_count; io_seek(f, begin_offset + offset, IO_SEEK_BEGIN, io_user_data); current_offset = begin_offset + offset; printf("\n"); for (byte_count = size; byte_count > 0;) { u64 rel_offset; u64 rel_info; READ(rel_offset); BX_ASSERT(n != 0); READ(rel_info); BX_ASSERT(n != 0); u32 rel_sym = (u32) (rel_info >> 32); u32 rel_type = (u32) (rel_info & 0xffffffff); printf(" "); printf("%08llx sym %-2d type %-2d", rel_offset, rel_sym, rel_type); printf("\n"); } printf("\n"); io_seek(f, prev_offset, IO_SEEK_BEGIN, io_user_data); current_offset = prev_offset; byte_count = prev_byte_count; } break; // ================================================== // // Relocarions with addends // // for .rela.NAME: // // .NAME[rela_offset] <- calc_reloc( // B = base_memory_address // P = rela_offset // A = rela_addent // S = .symtab[rela_sym].sym_value // Z = .symtab[rela_sym].sym_size // ) case 4: { BX_ASSERT(entsize == 24); i64 prev_offset = current_offset; i64 prev_byte_count = byte_count; io_seek(f, begin_offset + offset, IO_SEEK_BEGIN, io_user_data); current_offset = begin_offset + offset; printf("\n"); for (byte_count = size; byte_count > 0;) { u64 rela_offset; u64 rela_info; i64 rela_addent; READ(rela_offset); BX_ASSERT(n != 0); READ(rela_info); BX_ASSERT(n != 0); READ(rela_addent); BX_ASSERT(n != 0); u32 rela_sym = (u32) (rela_info >> 32); u32 rela_type = (u32) (rela_info & 0xffffffff); printf(" "); printf("%08llx sym %-2d type %-2d add %-2lld", rela_offset, rela_sym, rela_type, rela_addent); // Check value from destination address // { i64 prev_offset = current_offset; i64 prev_byte_count = byte_count; u64 sym_size = 0; // Go to the symbol table for (u64 j = 0; j < section_count; ++j) { io_seek(f, begin_offset + section_header_offset + j * 64 + 4, IO_SEEK_BEGIN, io_user_data); u32 type; READ(type); if (type != 2) continue; io_seek(f, 16, IO_SEEK_CURSOR, io_user_data); u64 offset; READ(offset); io_seek(f, begin_offset + offset + rela_sym * 24 + 16, IO_SEEK_BEGIN, io_user_data); READ(sym_size); break; } if (sym_size > 0) { // NOTE Ad hok // Go to the previous section io_seek(f, begin_offset + section_header_offset + (i - 1) * 64 + 24, IO_SEEK_BEGIN, io_user_data); u64 offset; u64 size; READ(offset); READ(size); if (size > 0) { io_seek(f, begin_offset + offset + rela_offset, IO_SEEK_BEGIN, io_user_data); u8 static buf[4]; if (sym_size > 4) sym_size = 4; io_read(f, sym_size, buf, io_user_data); for (u32 k = 0; k < sym_size; ++k) BX_ASSERT(buf[k] == 0); } } io_seek(f, prev_offset, IO_SEEK_BEGIN, io_user_data); current_offset = prev_offset; byte_count = prev_byte_count; } printf("\n"); } printf("\n"); io_seek(f, prev_offset, IO_SEEK_BEGIN, io_user_data); current_offset = prev_offset; byte_count = prev_byte_count; } break; // ================================================== default:; } } printf("\n"); io_seek(f, byte_count, IO_SEEK_CURSOR, io_user_data); current_offset += byte_count; #undef READ // ====================================================== } } for (i64 symbol_index = 0; symbol_index < num_symbols; ++symbol_index) if (!found[symbol_index]) printf(" ? : %-16s - %-50s\n", "", symbols[symbol_index]); // ========================================================== io_close(f, io_user_data); } } } i64 io_open_read(i64 name_size, c8 *name, void *user_data) { i64 f; io_dispatch(IO_OPEN_READ, &f, &name_size, name, user_data); return f; } i64 io_open_write(i64 name_size, c8 *name, void *user_data) { i64 f; io_dispatch(IO_OPEN_WRITE, &f, &name_size, name, user_data); return f; } void io_close(i64 f, void *user_data) { io_dispatch(IO_CLOSE, &f, NULL, NULL, user_data); } b8 io_seek(i64 f, i64 offset, u16 origin, void *user_data) { io_dispatch(IO_SEEK, &f, &offset, &origin, user_data); return 1; } i64 io_tell(i64 f, void *user_data) { i64 offset; io_dispatch(IO_TELL, &f, &offset, NULL, user_data); return offset; } i64 io_read(i64 f, i64 size, void *data, void *user_data) { io_dispatch(IO_READ, &f, &size, data, user_data); return size; } i64 io_write(i64 f, i64 size, void *data, void *user_data) { io_dispatch(IO_WRITE, &f, &size, data, user_data); return size; } void io_chmod_exe(i64 f, void *user_data) { io_dispatch(IO_CHMOD_EXE, &f, NULL, NULL, user_data); } // ================================================================ // // * Helper procedures // // ================================================================ #if HELPERS #include #include #include #ifdef __unix__ #include #include #endif // Assert // void bx_assert(b8 condition, c8 *message, u32 line, c8 *file) { if (condition) return; fflush(stdout); fprintf(stderr, "\r\x1b[31mASSERTION:\x1b[37m `\x1b[33m%s\x1b[37m`" " is false in \x1b[36m%s:%d\x1b[37m\n", message, file, line); exit(-1); } // IO dispatch procedure // void io_dispatch(i16 op, i64 *id, i64 *size, void *data, void *user_data) { BX_ASSERT(id != NULL); (void) user_data; FILE **f = (FILE **) id; c8 buf[MAX_NAME_SIZE] = { 0 }; switch (op) { case IO_OPEN_READ: case IO_OPEN_WRITE: BX_ASSERT(size != NULL); BX_ASSERT(*size > 0 && *size < MAX_NAME_SIZE); BX_ASSERT(data != NULL); bx_mem_cpy(buf, data, *size); *f = fopen(buf, op == IO_OPEN_READ ? "rb" : "wb"); BX_ASSERT(*f != NULL); break; case IO_CLOSE: BX_ASSERT(*f != NULL); BX_ASSERT(size == NULL); BX_ASSERT(data == NULL); fclose(*f); break; case IO_SEEK: { BX_ASSERT(*f != NULL); BX_ASSERT(size != NULL); BX_ASSERT(data != NULL); u16 *origin = (u16 *) data; if (!(*origin == IO_SEEK_CURSOR && *size == 0)) { BX_ASSERT(*origin == IO_SEEK_CURSOR || *origin == IO_SEEK_BEGIN || *origin == IO_SEEK_END); i32 s = fseek(*f, *size, *origin == IO_SEEK_CURSOR ? SEEK_CUR : *origin == IO_SEEK_BEGIN ? SEEK_SET : SEEK_END); BX_ASSERT(s == 0); } } break; case IO_TELL: { BX_ASSERT(*f != NULL); BX_ASSERT(size != NULL); BX_ASSERT(data == NULL); i64 n = (i64) ftell(*f); BX_ASSERT(n >= 0); *size = n; } break; case IO_READ: BX_ASSERT(*f != NULL); BX_ASSERT(size != NULL); BX_ASSERT(data != NULL); BX_ASSERT(*size > 0); *size = fread(data, 1, *size, *f); break; case IO_WRITE: BX_ASSERT(*f != NULL); BX_ASSERT(size != NULL); BX_ASSERT(data != NULL); BX_ASSERT(*size > 0); *size = fwrite(data, 1, *size, *f); break; case IO_CHMOD_EXE: BX_ASSERT(*f != NULL); BX_ASSERT(size == NULL); #ifdef __unix__ fchmod(fileno(*f), 0775); #endif break; default: BX_ASSERT(0); } } // Global state // Pool g_pool = { // Statically allocate a large memory block. // // TODO // Reallocate the memory block when necessary. .capacity = MAX_ENTITY_COUNT, .entities = (Entity[MAX_ENTITY_COUNT]) { 0 }, }; // Handy procedures // i64 n_i64(i64 value) { return node_data_i64(&g_pool, value); } i64 n_call(i16 convention, i64 target_proc, i64 arg_count, Var *args) { return node_ctrl_call(&g_pool, convention, target_proc, arg_count, args); } i64 n_call_by_name(i16 convention, c8 *name, i64 arg_count, Var *args) { return node_ctrl_call_by_name(&g_pool, convention, strlen(name), name, arg_count, args); } i64 n_ret(i64 val_count, Var *vals) { return node_ctrl_ret(&g_pool, val_count, vals); } i64 p_new(c8 *name) { i64 p = proc_init(&g_pool); proc_set_name(&g_pool, p, strlen(name), name); return p; } void p_add(i64 proc, i64 node) { proc_node_add(&g_pool, proc, node); } i64 u_new() { return unit_init(&g_pool, UNIT_CODE); } void u_add(i64 unit, i64 proc) { unit_proc_add(&g_pool, unit, proc); } void u_entry_point(i64 unit, i64 proc) { unit_set_entry_point(&g_pool, unit, proc); } void u_elf_x86_64(i64 unit, c8 *output_file_name) { i64 out = io_open_write(strlen(output_file_name), output_file_name, NULL); unit_write(&g_pool, unit, FORMAT_ELF | ARCH_X86_64, out, NULL); io_chmod_exe(out, NULL); io_close(out, NULL); } void l_code(i64 unit, i64 link_unit) { unit_link_add(&g_pool, unit, link_unit); } void l_object(i64 unit, c8 *object_library) { i64 l = unit_init(&g_pool, UNIT_LIBRARY_OBJECT); unit_set_name(&g_pool, l, strlen(object_library), object_library); unit_link_add(&g_pool, unit, l); } void l_static(i64 unit, c8 *static_library) { i64 l = unit_init(&g_pool, UNIT_LIBRARY_STATIC); unit_set_name(&g_pool, l, strlen(static_library), static_library); unit_link_add(&g_pool, unit, l); } #endif // ================================================================ // // EXAMPLE // // ================================================================ #if HELPERS && TESTING int main(int argc, char **argv) { (void) argc; (void) argv; printf("host bit order: %s\n", host_bit_order() == LE ? "LE" : "BE"); printf("host byte order: %s\n", host_byte_order() == LE ? "LE" : "BE"); printf("host f64 dword order: %s\n\n", host_f64_dword_order() == LE ? "LE" : "BE"); printf("entity - %d bytes\n", (i32) sizeof(Entity)); printf("binary output buffer - %d MB\n\n", (i32) sizeof(Binary_Output) / (1024 * 1024)); i64 main = p_new("main"); i64 n0 = n_i64(42); p_add(main, n0); p_add(main, n_ret(1, (Var[]) { {.size = 4, .type = TYPE_I32, .node = n0, } })); i64 u = u_new(); u_add(u, main); u_entry_point(u, main); // l_static(u, "/lib/x86_64-linux-gnu/libc.a"); l_static(u, "libtest.a"); printf("Writing ELF x86_64 executable...\n"); u_elf_x86_64(u, "test_foo"); i32 ret = system("./test_foo"); BX_ASSERT(WEXITSTATUS(ret) == 42); printf("\nBye!\n"); return 0; } #endif #endif