49
\$\begingroup\$

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).

\$\endgroup\$

35 Answers 35

1
2
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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 
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ Why is this better than pop eax / pop edx / ...? If you need to leave them on the stack, you can push them all back after to restore ESP, still 2 bytes per object with no need to mov esi,esp. Or did you mean for 4-byte objects in 64-bit code where pop would get 8 bytes? BTW, you can even use pop to loop over a buffer with better performance than lodsd, e.g. for extended-precision addition in Extreme Fibonacci \$\endgroup\$ Mar 29, 2018 at 15:06
  • \$\begingroup\$ it's more correctly useful after an "lea esi,[esp+size of ret address]", which would preclude using pop unless you have a spare register. \$\endgroup\$ Apr 3, 2018 at 12:46
  • \$\begingroup\$ Oh, for function args? Pretty rare you want more args than there are registers, or that you'd want the caller to leave one in memory instead of passing them all in registers. (I have a half-finished answer about using custom calling conventions, in case one of the standard register-call conventions doesn't fit perfectly.) \$\endgroup\$ Apr 3, 2018 at 19:18
  • \$\begingroup\$ cdecl instead of fastcall will leave the parameters on the stack, and it's easy to have lots of parameters. See github.com/peterferrie/tinycrypt, for example. \$\endgroup\$ Apr 8, 2018 at 21:53
1
2

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.