2
\$\begingroup\$

As the title suggests, I'm writing an x64 Code Emitter. Right now I've only encoded 1 instruction (The add instruction). I want to know if this API can be improved at all.

This is how you I use it.

int main() {
    // The Operand type contains the type of the operand and a union with the contained value.
    // There are 4 types right now, NONE, REGISTER, MEMORY, and CONSTANT.
    Operand imm42 = (Operand) { OPERAND_CONSTANT, .Constant = 42 };
    Operand imm256 = (Operand) { OPERAND_CONSTANT, .Constant = 256 };
        
    // rax and r8 are constants defined in another file.
    // the emitAdd function for now simply prints the result to stdout.
    emitAdd(rax, imm42); // -> 48 83 C0 2A
    emitAdd(rax, imm256); // -> 48 05 00 01 00 00 
    emitAdd(r8, imm42); // -> 49 83 C0 2A
    emitAdd(r8, imm256); // -> 49 81 C0 00 01 00 00
}

I'm pretty happy with what I've done so far, and I've tested every variation of this instruction. i.e (add reg, imm add reg, reg) I haven't encoded memory variants yet though.

This is the main code.

// Instruction.c
// forward declaration for emitAdd
#include "Instruction.h"

#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>
#include "types.h"
#include "Encoding.h"

unsigned int registerToIndex(Register reg) {
    switch (reg) {
        case REGISTER_AL:
        case REGISTER_AX:
        case REGISTER_EAX:
        case REGISTER_RAX: return 0;
        case REGISTER_CL:
        case REGISTER_CX:
        case REGISTER_ECX:
        case REGISTER_RCX: return 1;
        case REGISTER_DL:
        case REGISTER_DX:
        case REGISTER_EDX:
        case REGISTER_RDX: return 2;
        case REGISTER_BL:
        case REGISTER_BX:
        case REGISTER_EBX:
        case REGISTER_RBX: return 3;
        case REGISTER_AH:
        case REGISTER_SPL:
        case REGISTER_SP:
        case REGISTER_ESP:
        case REGISTER_RSP: return 4;
        case REGISTER_CH:
        case REGISTER_BPL:
        case REGISTER_BP:
        case REGISTER_EBP:
        case REGISTER_RBP: return 5;
        case REGISTER_DH:
        case REGISTER_SIL:
        case REGISTER_SI:
        case REGISTER_ESI:
        case REGISTER_RSI: return 6;
        case REGISTER_BH:
        case REGISTER_DIL:
        case REGISTER_DI:
        case REGISTER_EDI:
        case REGISTER_RDI: return 7;
        case REGISTER_R8B:
        case REGISTER_R8W:
        case REGISTER_R8D:
        case REGISTER_R8: return 8;
        case REGISTER_R9B:
        case REGISTER_R9W:
        case REGISTER_R9D:
        case REGISTER_R9: return 9;
        case REGISTER_R10B:
        case REGISTER_R10W:
        case REGISTER_R10D:
        case REGISTER_R10: return 10;
        case REGISTER_R11B:
        case REGISTER_R11W:
        case REGISTER_R11D:
        case REGISTER_R11: return 11;
        case REGISTER_R12B:
        case REGISTER_R12W:
        case REGISTER_R12D:
        case REGISTER_R12: return 12;
        case REGISTER_R13B:
        case REGISTER_R13W:
        case REGISTER_R13D:
        case REGISTER_R13: return 13;
        case REGISTER_R14B:
        case REGISTER_R14W:
        case REGISTER_R14D:
        case REGISTER_R14: return 14;
        case REGISTER_R15B:
        case REGISTER_R15W:
        case REGISTER_R15D:
        case REGISTER_R15: return 15;
    }
}

static bool is8BitRegister(Register reg) {
    return reg >= REGISTER_AL && reg <= REGISTER_R15B;
}
static bool is16BitRegister(Register reg) {
    return reg >= REGISTER_AX && reg <= REGISTER_R15W;
}
static bool is32BitRegister(Register reg) {
    return reg >= REGISTER_EAX && reg <= REGISTER_R15D;
}
static bool is64BitRegister(Register reg) {
    return reg >= REGISTER_RAX && reg <= REGISTER_R15;
}

static bool needsREX(Register reg) {
    switch (reg) {
        case REGISTER_SPL:
        case REGISTER_BPL:
        case REGISTER_SIL:
        case REGISTER_DIL:
        case REGISTER_R8B:
        case REGISTER_R9B:
        case REGISTER_R10B:
        case REGISTER_R11B:
        case REGISTER_R12B:
        case REGISTER_R13B:
        case REGISTER_R14B:
        case REGISTER_R15B:
        case REGISTER_R8W:
        case REGISTER_R9W:
        case REGISTER_R10W:
        case REGISTER_R11W:
        case REGISTER_R12W:
        case REGISTER_R13W:
        case REGISTER_R14W:
        case REGISTER_R15W:
        case REGISTER_R8D:
        case REGISTER_R9D:
        case REGISTER_R10D:
        case REGISTER_R11D:
        case REGISTER_R12D:
        case REGISTER_R13D:
        case REGISTER_R14D:
        case REGISTER_R15D:
        case REGISTER_R8:
        case REGISTER_R9:
        case REGISTER_R10:
        case REGISTER_R11:
        case REGISTER_R12:
        case REGISTER_R13:
        case REGISTER_R14:
        case REGISTER_R15: return true;
    }

    return false;
}

static void printMemory(byte* memory, size_t length) {
    /*
        byte arr[] = {0x3, 0x4, 0x6, 0x5};

        printMemory(arr, 4); -> 03 04 06 05
    */
    for (size_t i = 0; i < length; i++) {
        byte b = memory[i];
        printf("%X%X ", (b & 0xF0) >> 4, b & 0x0F);
    }
    printf("\n");
}

/*
    This function optimizes for instruction size, so instructions are encoded using the
    least amount of bytes possible.
*/
void emitAdd(Operand destination, Operand source) {
    // for now just assume the largest an x64 instruction can be.
    // I think it can be bigger, I haven't checked.
    byte instruction[14] = {};
    unsigned int index = 0;

    if (destination.Type == OPERAND_REGISTER && source.Type == OPERAND_CONSTANT) {
        Register reg = destination.Register;
        unsigned int registerCode = registerToIndex(reg);
        qword constant = source.Constant;

        if (reg == REGISTER_AL || reg == REGISTER_AX || reg == REGISTER_EAX || reg == REGISTER_RAX) {
            switch (reg) {
                case REGISTER_AL: {
                    instruction[index++] = 0x4;
                    *(byte*)(instruction + index++) = constant;
                } break;
                case REGISTER_AX: {
                    instruction[index++] = 0x66;
                    instruction[index++] = 0x5;
                    *(word*)(instruction + index) = constant, index += 2;
                } break;
                case REGISTER_EAX:
                case REGISTER_RAX: {
                    if (reg == REGISTER_RAX)
                        instruction[index++] = REX_W;
                    
                    if (constant <= 0xFF) {
                        instruction[index++] = 0x83;
                        instruction[index++] = encodeModRM(REGISTER_ADDRESSING, 0, registerCode);
                        *(byte*)(instruction + index++) = constant;
                    } else {
                        instruction[index++] = 0x5;
                        *(dword*)(instruction + index) = constant, index += 4;
                    }
                } break;
            }
        } else if (is8BitRegister(reg)) {
            if (needsREX(reg))
                instruction[index++] = (reg < REGISTER_R8B ? REX : REX_B);

            instruction[index++] = 0x80;
            instruction[index++] = encodeModRM(REGISTER_ADDRESSING, 0, registerCode);
            *(byte*)(instruction + index++) = constant; 
        } else if (is16BitRegister(reg)) {
            instruction[index++] = 0x66;
            if (constant <= 0xFF) {
                if (needsREX(reg))
                    instruction[index++] = REX_B;
                instruction[index++] = 0x83;
                instruction[index++] = encodeModRM(REGISTER_ADDRESSING, 0, registerCode);
                *(byte*)(instruction + index++) = constant;
            } else {
                if (needsREX(reg))
                    instruction[index++] = REX_B;

                instruction[index++] = 0x81;
                instruction[index++] = encodeModRM(REGISTER_ADDRESSING, 0, registerCode);
                *(word*)(instruction + index) = constant, index += 2;
            }
        } else if (is32BitRegister(reg)) {
            if (constant <= 0xFF) {
                if (needsREX(reg))
                    instruction[index++] = REX_B;
                instruction[index++] = 0x83;
                instruction[index++] = encodeModRM(REGISTER_ADDRESSING, 0, registerCode);
                *(byte*)(instruction + index++) = constant;
            } else {
                if (needsREX(reg))
                    instruction[index++] = REX_B;

                instruction[index++] = 0x81;
                instruction[index++] = encodeModRM(REGISTER_ADDRESSING, 0, registerCode);
                *(dword*)(instruction + index) = constant, index += 4;
            }
        } else { // must be a 64 bit register
            instruction[index++] = (reg < REGISTER_R8 ? REX_W : REX_W | REX_B);
            if (constant <= 0xFF) {
                instruction[index++] = 0x83;
                instruction[index++] = encodeModRM(REGISTER_ADDRESSING, 0, registerCode);
                *(byte*)(instruction + index++) = constant;
            } else {
                instruction[index++] = 0x81;
                instruction[index++] = encodeModRM(REGISTER_ADDRESSING, 0, registerCode);
                *(dword*)(instruction + index) = constant, index += 4;
            }
        }
    } else if (destination.Type == OPERAND_REGISTER && source.Type == OPERAND_REGISTER) {
        Register dst = destination.Register;
        Register src = source.Register;
        unsigned int dstRegisterCode = registerToIndex(dst);
        unsigned int srcRegisterCode = registerToIndex(src);

        if (is8BitRegister(dst) && is8BitRegister(src)) {
            if (needsREX(dst) || needsREX(src)) {
                unsigned int rexPrefixIndex = index++;
                instruction[rexPrefixIndex] = REX;
                instruction[rexPrefixIndex] |= (dst >= REGISTER_R8B ? REX_B : 0);
                instruction[rexPrefixIndex] |= (src >= REGISTER_R8B ? REX_R : 0);
            }

            instruction[index++] = 0x00;
            instruction[index++] = encodeModRM(REGISTER_ADDRESSING, srcRegisterCode, dstRegisterCode);
        } else if (is16BitRegister(dst) && is16BitRegister(src)) {
            instruction[index++] = 0x66;
            if (needsREX(dst) || needsREX(src)) {
                unsigned int rexPrexfixIndex = index++;
                instruction[rexPrexfixIndex] = REX;
                instruction[rexPrexfixIndex] |= (dst >= REGISTER_R8W ? REX_B : 0);
                instruction[rexPrexfixIndex] |= (src >= REGISTER_R8W ? REX_R : 0);
            }
            instruction[index++] = 0x1;
            instruction[index++] = encodeModRM(REGISTER_ADDRESSING, srcRegisterCode, dstRegisterCode);
        } else if (is32BitRegister(dst) && is32BitRegister(src)) {
            if (needsREX(dst) || needsREX(src)) {
                unsigned int rexPrefixIndex = index++;
                instruction[rexPrefixIndex] = REX;
                instruction[rexPrefixIndex] |= (dst >= REGISTER_R8D ? REX_B : 0);
                instruction[rexPrefixIndex] |= (src >= REGISTER_R8D ? REX_R : 0);
            }

            instruction[index++] = 0x1;
            instruction[index++] = encodeModRM(REGISTER_ADDRESSING, srcRegisterCode, dstRegisterCode);
        } else if (is64BitRegister(dst) && is64BitRegister(src)) {
            unsigned int rexPrefixIndex = index++;
            instruction[rexPrefixIndex] = REX_W;
            instruction[rexPrefixIndex] |= (dst >= REGISTER_R8 ? REX_B : 0);
            instruction[rexPrefixIndex] |= (src >= REGISTER_R8 ? REX_R : 0);

            instruction[index++] = 0x1;
            instruction[index++] = encodeModRM(REGISTER_ADDRESSING, srcRegisterCode, dstRegisterCode);
        }
    }

    printMemory(instruction, index);
}

All the sources are here, it's mostly defining constants and forward declarations.

types.h: https://hastebin.com/pipuqezoxe.cpp
Encoding.h: https://hastebin.com/esiciniwex.cpp
Instruction.h: https://hastebin.com/refokaluka.cpp
Instruction.c (where all the code emitting happens): https://hastebin.com/fuboqijedi.cpp
Improve this question
\$\endgroup\$
4
  • 4
    \$\begingroup\$ IMO the API is still too small to give meaningful feedback about, especially because it doesn't include any interesting cases yet (eg memory operands and labels). Maybe someone else feels differently about that.. \$\endgroup\$
    – harold
    Sep 10, 2021 at 12:59
  • 2
    \$\begingroup\$ Too long to include? If those 4 files cause you to go over the 64K limit we have here, then I suggest they probably need some splitting to make them more manageable. \$\endgroup\$
    – Toby Speight
    Sep 10, 2021 at 13:13
  • \$\begingroup\$ @Toby Speight I've included the code in the main post if that helps, I originally excluded it for brevity, the emitAdd function is only ~150 lines. \$\endgroup\$
    – xKaihatsu
    Sep 10, 2021 at 13:55
  • 2
    \$\begingroup\$ If you look at other code reviews, you will see that the standard is to include all the code, so that people can run it. You should only work on brevity if the code is bigger than fits in a single question. You should always include enough code in the question so that people can run it, possibly in the form of unit tests. In any case, I would suggest that you try to include all four files. If it doesn't tell you that breaks the 64K limit, then you're good. If it does, then there might be more to consider. \$\endgroup\$
    – mdfst13
    Sep 10, 2021 at 16:40

1 Answer 1

Reset to default
3
\$\begingroup\$ 
// forward declaration for emitAdd
#include "Instruction.h"

There's no declaration here. Do you mean it's in Instruction.h? I think you don't need this comment. When you include a header with the same name as the source file, everyone reading your code will assume it contains declarations of exported functions. If it doesn't, that might be worthy of comment.

unsigned int registerToIndex(Register reg) {
    switch (reg) {
        case REGISTER_AL:
        case REGISTER_AX:
        case REGISTER_EAX:
        case REGISTER_RAX: return 0;
        case REGISTER_CL:
        case REGISTER_CX:
        case REGISTER_ECX:
        case REGISTER_RCX: return 1;
        [...]

This is a lot of boilerplate, and mistakes could easily creep in. Aside from that, having an unordered enum for the registers is inconvenient for users of the library, who will probably want to mention them by number, not name, in most cases (when writing a register allocator, for instance).

I would either separate the register type from the register index, storing the latter in some other field of the Operand struct, or else rearrange the enum so that this function can be something like

unsigned int registerToIndex(Register reg) {
    return (unsigned)reg % 16u;
}

and document that.

static bool needsREX(Register reg) { [...] }

This returns false for registers like rax that normally need REX.W. It seems as though it's really testing for every need for REX other than REX.W, which is hard to capture in a function name.

My advice is to handle prefixes in a different way. Instead of having custom logic to work out what prefixes you'll need up front, track it as you go, and emit the prefixes at the end. encodeModRM should set REX.RXB based on the arguments.

printf("%X%X ", (b & 0xF0) >> 4, b & 0x0F);

That can just be printf("%02X ", b);.

void emitAdd(Operand destination, Operand source) { [...] }

The length of this function and the amount of duplicated code worries me. You've got a long road ahead of you. You definitely don't want to be copy-and-pasting all of this code just so that you can change the opcode byte for other instructions.

The 16-bit, 32-bit and 64-bit cases are almost identical, and I'd unify them.

unsigned int registerCode = registerToIndex(reg);

I wouldn't use "code" and "index" for the same property. Just call it "index".

if (reg == REGISTER_AL || reg == REGISTER_AX || reg == REGISTER_EAX || reg == REGISTER_RAX) {

You may as well change this to if (registerCode == 0) {.

*(byte*)(instruction + index++) = constant;

instruction is an array of byte, so I'd just say instruction[index++] = constant;

*(word*)(instruction + index) = constant, index += 2;
*(dword*)(instruction + index) = constant, index += 4;

These aren't portable; they assume that the machine is little-endian and supports unaligned stores. Even if you don't make them portable right now, you should move them into separate functions so that they aren't duplicated everywhere, and can be made portable later without search-and-replace.

if (constant <= 0xFF) {

This test is wrong because byte immediates are sign extended. It should be something like ((dword)constant <= 0x7Fu || (dword)constant >= 0xFFFFFF80u) (with obvious changes in the 16-bit case). Of course, this test should also be in its own function.

if (is8BitRegister(dst) && is8BitRegister(src)) {
    if (needsREX(dst) || needsREX(src)) {

Some combinations of 8-bit registers aren't encodable, like ah,r8b. You emit incorrect code in this case.

If you take my advice to work out prefixes as you go, you should have a "invalid with REX" flag that you set whenever you see ah/ch/dh/bh, and test it at the end and error out if necessary.

} else if (is64BitRegister(dst) && is64BitRegister(src)) { [...] }

There's no default case in this if-else chain, so when the register types don't match you'll just silently emit no code. The same is true if the operand types are invalid or you just haven't implemented them yet.

In general, be suspicious of if-else chains without a final else, and switch statements without a default case. You may want to add an explicit // do nothing case if doing nothing is really the right action.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.