x86 machine code, 7 bytes
EDX = x = fib[1]
, EAX = y = fib[2]
, RCX = n
(1-indexed)
returns in EAX. Works in all 3 modes (16, 32, and 64).
Try it online!
(64-bit NASM source with a _start that parses 3 integers from argv strings)
0000000000401070 <cfib>:
401070: eb .byte 0xeb # jmp rel8 consuming the 01 add opcode as a rel8
0000000000401071 <cfib.loop>:
401071: 01 d0 add eax,edx
# loop entry point on first iteration, jumping over the ModRM byte of the ADD
401073: 92 xchg edx,eax
401074: e2 fb loop 401071 <cfib.loop>
401076: c3 ret
This "jumps" into the loop with machine code that decodes 2 different ways: with a jmp +1
when falling into the loop from the top of the function, or with that 01
byte being an ADD opcode when the loop
instruction jumps backwards. Equivalent to jmp .entry
but with only 1 byte outside the loop instead of 2.
(Credit to @Ira Baxter for pointing out the general idea of falling into a loop with 1 byte outside that consumes some loop bytes to do something different on the first iteration, e.g. the opcode for cmp al, imm8
as a 1-byte encoding for a jump forward by 1. I got lucky that 01 add
could be consumed by jmp rel8 to skip a total of 2 bytes without needing a 66
prefix for cmp ax, imm16
or being in 16-bit mode. 01 or 03 add didn't work well as a modrm for anything like add r/m32, imm8
; we need to avoid a memory operand. Note that this trick is not good for performance on some modern CPUs, e.g. AMD that caches instruction boundaries in L1i tags, and probably not newer Intel/AMD with uop caches.)
Stripping labels lets objdump decode as the CPU would on the first pass:
cfib:
401070: eb 01 jmp 0x401073 # jmp rel8 = +1
401072: d0 .byte 0xd0 # jumped over
401073: 92 xchg edx,eax
401074: e2 fb loop 0x401071
401076: c3 ret
It's easy to see that the EDX input will be the EAX return value for ECX=1 (exit right away, loop
is never taken so add
never runs).
Use strace ./custom-fib 14 2308 4261
to see the full integer value passed to the exit()
system call before truncation to an 8-bit exit status.
In 32-bit mode, the same machine code is callable with GCC regparm(3) calling convention as __attribute__((regparm(3))) unsigned custom_fib(unsigned y /*eax*/, unsigned x /*edx*/, unsigned n /*ecx*/);
, returning in EAX as usual.
Without the 2-way decode hack: x86 machine code, 8 bytes
0-indexed n
in RCX, x
(fib[0]
) in EAX, y (fib[1]
) in EDX - note opposite arg order
0000000000401070 <cfib>:
401070: e3 05 jrcxz 401077 <cfib.done>
0000000000401072 <cfib.loop>:
401072: 0f c1 c2 xadd edx,eax
401075: e2 fb loop 401072 <cfib.loop>
0000000000401077 <cfib.done>:
401077: c3 ret
This way shows off x86's xadd
instruction, normally only used with a memory destination and a lock
prefix to implement fetch_add
.
The reg,reg form of xadd
decodes to only 3 uops on Intel Skylake, same as xchg reg,reg
(https://uops.info/). (The loop
instruction is slow on Intel so this is hardly optimized for speed. If you want a speed-efficient asm implementation, unroll by 2 to remove the xchg as shown in my SO answer using clever loop setup to avoid excess branching for odd vs. even n
for standard 0,1 Fibonacci.)
[1, 2, 3]
? Yes. Whatever you need to accept 3 integers. \$\endgroup\$n,[x,y]
wheren
is a number andx
andy
are numbers in a list? That's probably being a little too flexible though ;) \$\endgroup\$