Tips for golfing in x86/x64 machine code

Question

I noticed that there's no such question, so here it is:

Do you have general tips for golfing in x86/x64 machine code? If the tip only applies to a certain environment or calling convention, please specify that in your answer.

Please only one tip per answer (see here).

Answer 1

Use shr for first occurrence lookup tables

Often times you need to do something like this to check whether a byte has been encountered:

bool found[256]={false};
for (uint8_t x : data) {
    // Check for first occurrence
    if (!found[x]) {
        // mark it as encountered
        found[x] = true;
        // do something
        func(x);
    }
}

There is a very easy way to do this in x86, and that is via shr.

Setup

Setting it up is easy thanks to push -1 which can create a block of 1 bits. I use x86_64 here, but it is the same on x86.

You can switch it to rep stos if you have that set up, but it isn't worth it to set up just for that loop.

        push    TABLE_SIZE/8
        pop     rcx
.Lpush_loop:
        push    -1
        loop    .Lpush_loop

Usage

shr will both mark the occurrence and indicate that it was unique by setting OF.

.Lloop:
        lodsb # example

        # 3 bytes (2 bytes if you use RDI/RBX/RBP/RSI or a register src)
        shr     byte ptr [rsp + rax]
        # OF == first occurrence
        jno     .Lfound

.Lfirst_occurrence:
        ...
.Lfound:
        loop    .Lloop # example

Magic.

See my answer for Type uniqchars! where I thoroughly explain it.

Answer 2

Align Registers to by Power of 2 Value with or/inc

Say you want to aligned a pointer for a load. I.e saying aligning for xmm load:

This is a pretty common idiom:

addq $16, %rdi   // 4b
andq $-16, %rdi  // 4b

A cheaper way:

orq $15, %rdi    // 4b
incq %rdi        // 3b

If your pointer is in RAX, the special 2-byte op al, imm8 no-modrm encoding is useful. Writing a byte or word register leaves the upper bytes untouched. On older Intel CPUs (before Sandybridge) this can cause a partial-register stall, but even for performance it's safe on modern CPUs.

or  $0xf, %al     // 2b   (leave upper bytes untouched)
inc %rax          // 3b   (carry into the upper bytes is possible)

or  $0xf, %dl     // 3b
inc %rdx          // 3b

or  $0xf, %dil    // 4b  REX + opcode + modrm + imm8
inc %rdi          // 3b  no savings

Also works with and $0xf0, %al to round down to the previous alignment boundary.

---

Also worth noting the or alone will round to value minus 1 so it can be used to keep address offsets in imm8 short encoding range i.e:

andq $-16, %rdi
// Stuff on (%rdi)[0, 79]
vmovdqa 80(%rdi), %xmm0

vs.

orq $15, %rdi
// Stuff on -15(%rdi)[0, 79]
vmovdqa 65(%rdi), %xmm0
# vmovdqa 80 - 15(%rdi), %xmm0   # same thing, but with the -15 in the asm source

Answer 3

pop ax and throw a value from stack

pop eax

push word 0; push word 8

push dword 8

push dword 9999

push word 0
push word 9999

Answer 4

AND to clear memory

0:  c7 01 00 00 00 00       mov    DWORD PTR [ecx],0x0
6:  31 c0 89 01             xor    eax,eax / mov DWORD PTR [ecx],eax
a:  83 21 00                and    DWORD PTR [ecx],0x0 

Answer 5

Use 32-bit x86 instead of 64-bit x86-64, if you can

This is a bit silly, but many code golf challenges only require 32-bit inputs, and 32-bit programs execute just fine on x86-64 processors (almost all instructions work, you can't use the lower 8 bits SIL, DIL, SPL, BPL). Assemble with nasm -f elf32 and link with ld -m elf_i386. You avoid extra bytes from REX prefixes without even thinking about it. MUL can multiply two 32-bit numbers and puts the full result in EDX:EAX, and DIV can divide a 64-bit dividend by r/m32.

...or 16-bit DOS, if you can

NASM can assemble raw COM files with -f bin. You'll need an emulator like emu2 or DOSBox to run these, so it won't run natively on a modern system, which is half the fun of x86.

Answer 6

LOOP according to ECX

This is the famously slow instruction that decrements CX/ECX/RCX as a counter, then short jumps if not zero, all in 2 bytes! LOOPcc variants also check ZF. Compare this to regular short branching, which takes 3 bytes:

E2 cb   loop    label   ; cb is rel8

4A      dec     ecx     ; sets ZF
75 cb   jnz     label   

JECXZ according to ECX

JCXZ/JECXZ/JRCXZ are weird instructions in the Jcc family that jump short based on if CX/ECX/RCX is 0, in 2 bytes. If you had an instruction before that sets ZF such as dec, you could use a standard JZ.

Answer 7

You can fetch sequential objects from the stack by setting esi to esp, and performing a sequence of lodsd/xchg reg, eax.

Answer 8

Useful one-byte instructions

WIP. Most are listed here. This answer will assume x86 (32-bit), with some notes for x86-64 (usually more bytes). I checked these with Compiler Explorer (godbolt.org) running NASM.

Stack Operations

• PUSH/POP: push/pop any of the eight +rd registers: EAX, ECX, EDX, EBX, ESI, EDI, EBP, ESP.
  • In 64-bit mode, you can't use registers R8-R15. Avoid registers that need prefixes
• PUSHAD/POPAD: push/pop all of the 8 general-purpose registers.
  • *Not available in 64-bit mode!

Register / Integer Operations

• CWDE: EAX := sign-extend of AX.
  • In 64-bit mode, CDQE : RAX := sign-extend of EAX takes an extra REX.W prefix byte.
• CDQ: EDX:EAX := sign-extend of EAX. If EAX doesn't have sign bit, this is useful to zero EDX.
  • In 64-bit mode, CQO: RDX:RAX := sign-extend of RAX takes an extra byte.
• INC/DEC: increment/decrement any of the +rd registers.
  • In 64-bit mode, takes 2 bytes for 32-bit register, 3 bytes for 64-bit register
• XCHG: Exchange any +rd register with EAX. Other sizes take 2 bytes.
  • In 64-bit mode, the default operation size is still 32 bits. 64-bit exchange with RAX takes an extra byte.

String Operations

• MOVSB/MOVSD: Move byte/dword from address ESI to EDI, then inc/dec both registers based on DF.
• LODSB/LODSD: Load byte/dword from address ESI into AL/EAX, and inc/dec ESI based on DF direction flag. This is very useful in iterating over strings/arrays.
• STOSB/STOSD: Store byte/dword from AL/EAX into address EDI, then inc/dec EDI based on DF.
• CMPSB/CMPSD: Compare byte/dword in address ESI with byte/dword in address EDI, set flags according to result, and inc/dec registers.
• SCASB/SCASD: Compare AL/EAX with byte/dword at EDI, set flags according to result, and inc/dec EDI.

Word (16-bit) versions of the instructions take 2 bytes. In 64-bit mode, defaults to 64-bit operands, and qword versions also take 2 bytes.

Opcode Prefixes (technically one byte)

• REP: Repeat the following string instruction, decrementing counter ECX until ECX = 0. REP can only prefix MOVS, LODS, and STOS.
• REPZ/REPNZ: Repeat the following string instruction, decrementing ECX, terminating when ECX = 0 OR termination condition (ZF = 0 / ZF = 1). Can only prefix CMPS (find (non-)matching bytes) and SCAS (find (non-)matching AL).