汇编语言(x86):如何创建计算斐波那契数列的循环
我正在使用Visual Studio 2013 Ultimate在MASM中编程汇编语言(x86)。我试图使用数组来计算n个元素的斐波那契序列。换句话说，我正在尝试到一个数组元素，获取它前面的两个元素，将它们相加，并将结果存储在另一个数组中。
我在建立索引寄存器时遇到了麻烦。
我的程序设置是这样的：
TITLE fibonacci.asm
INCLUDE Irvine32.inc
.data
fibInitial BYTE 0, 1, 2, 3, 4, 5, 6
fibComputed BYTE 5 DUP(0)
.code
main PROC
MOVZX si, fibInitial
MOVZX di, fibComputed
MOV cl, LENGTHOF fibInitial
L1:
MOV ax, [si - 1]
MOV dx, [si - 2]
MOV bp, ax + dx
MOV dl, TYPE fibInitial
MOVZX si, dl
MOV [edi], bp
MOV dh, TYPE fibComputed
MOVZX di, dl
loop L1
exit
main ENDP
END main
我无法编译该代码，因为有一条错误消息显示行mov ebp,ax+dx的“error a2031:must be index or base register”（错误A2031:must be index or base register）。但是，我肯定还有其他的逻辑错误我忽略了。
共有1个答案
相关：Code-golf打印Fib(10**9)的前1000位数字：我的x86 asm答案使用扩展精度adc循环，并将二进制转换为字符串。内环针对速度进行了优化，其他部分针对尺寸进行了优化。
计算Fibonacci序列只需要保持两个状态：当前元素和前一个元素。除了计算fibinitial的长度之外，我不知道您要对它做什么。这不是在perl中为$n(0..5)执行的地方。
我知道你根本就只是在学asm，但我还是要说说性能。没有太多的理由去学习asm而不知道什么是快什么不是。如果您不需要性能，请让编译器从C源代码为您制作asm。另请参阅https://stackoverflow.com/tags/x86/info上的其他链接
使用状态寄存器可以简化计算A[1]时需要查看A[-1]的问题。您可以从curr=1、prev=0开始，然后从A[0]=curr开始。要生成斐波那契数的“现代”零开头序列，请从curr=0和prev=1开始。
幸运的是，我最近正在考虑fibonacci代码的一个高效循环，所以我花时间写了一个完整的函数。请参阅下面的展开版本和矢量化版本（节省存储指令，但即使在为32bit CPU编译时也能使64bit int更快）：
; fib.asm
;void fib(int32_t *dest, uint32_t count);
; not-unrolled version. See below for a version which avoids all the mov instructions
global fib
fib:
; 64bit SysV register-call ABI:
; args: rdi: output buffer pointer. esi: count (and you can assume the upper32 are zeroed, so using rsi is safe)
;; locals: rsi: endp
;; eax: current edx: prev
;; ecx: tmp
;; all of these are caller-saved in the SysV ABI, like r8-r11
;; so we can use them without push/pop to save/restore them.
;; The Windows ABI is different.
test esi, esi ; test a reg against itself instead of cmp esi, 0
jz .early_out ; count == 0.
mov eax, 1 ; current = 1
xor edx, edx ; prev = 0
lea rsi, [rdi + rsi * 4] ; endp = &out[count]; // loop-end pointer
;; lea is very useful for combining add, shift, and non-destructive operation
;; this is equivalent to shl rsi, 4 / add rsi, rdi
align 16
.loop: ; do {
mov [rdi], eax ; *buf = current
add rdi, 4 ; buf++
lea ecx, [rax + rdx] ; tmp = curr+prev = next_cur
mov edx, eax ; prev = curr
mov eax, ecx ; curr=tmp
;; see below for an unrolled version that doesn't need any reg->reg mov instructions
; you might think this would be faster:
; add edx, eax ; but it isn't
; xchg eax, edx ; This is as slow as 3 mov instructions, but we only needed 2 thanks to using lea
cmp rdi, rsi ; } while(buf < endp);
jb .loop ; jump if (rdi BELOW rsi). unsigned compare
;; the LOOP instruction is very slow, avoid it
.early_out:
ret
另一个循环条件可以是
dec esi ; often you'd use ecx for counts, but we had it in esi
jnz .loop
AMD CPU可以融合CMP/BRANCH，但不能融合DEC/BRANCH.Intel CPU还可以宏熔断dec/jnz。（或带符号的小于零/大于零）。dec/inc不更新进位标志，因此您不能将它们与上面/下面的无符号ja/jb一起使用。我认为，您可以在循环中执行adc（带进位的添加），使用inc/dec作为循环计数器，以不干扰进位标志，但部分标志减慢在现代CPU上使其变得糟糕。
LEA ecx,[eax+edx]需要一个额外的字节（地址大小的前缀），这就是为什么我使用32位的dest和64位的地址。（这些是lea在64位模式下的默认操作数大小）。对速度没有直接影响，只是通过代码大小间接影响。
另一个循环体可以是：
mov ecx, eax ; tmp=curr. This stays true after every iteration
.loop:
mov [rdi], ecx
add ecx, edx ; tmp+=prev ;; shorter encoding than lea
mov edx, eax ; prev=curr
mov eax, ecx ; curr=tmp
展开循环进行更多的迭代将意味着更少的洗牌。而不是mov指令，您只需要跟踪哪个寄存器保存哪个变量。即使用某种寄存器重命名来处理赋值。
.loop: ;; on entry: ; curr:eax prev:edx
mov [rdi], eax ; store curr
add edx, eax ; curr:edx prev:eax
.oddentry:
mov [rdi + 4], edx ; store curr
add eax, edx ; curr:eax prev:edx
;; we're back to our starting state, so we can loop
add rdi, 8
cmp rdi, rsi
jb .loop
展开的问题是，您需要清理遗留下来的任何奇怪的迭代。二次方展开因子可以使清理循环稍微容易一些，但是添加12并不比添加16快。（关于一个愚蠢的3倍展开版本，使用lea在第三寄存器中生成curr+prev，请参阅本文的前一个修订版，因为我没有意识到您实际上并不需要临时。感谢rcgldr捕捉到了这一点。）
请参阅下面的一个完整的工作展开版本，它可以处理任何计数。
测试前端（此版本新增：一个canary元素，用于检测在缓冲区结束后写入的asm错误。）
// fib-main.c
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
void fib(uint32_t *buf, uint32_t count);
int main(int argc, const char *argv[]) {
uint32_t count = 15;
if (argc > 1) {
count = atoi(argv[1]);
}
uint32_t buf[count+1]; // allocated on the stack
// Fib overflows uint32 at count = 48, so it's not like a lot of space is useful
buf[count] = 0xdeadbeefUL;
// uint32_t count = sizeof(buf)/sizeof(buf[0]);
fib(buf, count);
for (uint32_t i ; i < count ; i++){
printf("%u ", buf[i]);
}
putchar('\n');
if (buf[count] != 0xdeadbeefUL) {
printf("fib wrote past the end of buf: sentinel = %x\n", buf[count]);
}
}
此代码已完全工作并经过测试（除非我没有将本地文件中的更改复制回答案>.<):
peter@tesla:~/src/SO$ yasm -f elf64 fib.asm && gcc -std=gnu11 -g -Og fib-main.c fib.o
peter@tesla:~/src/SO$ ./a.out 48
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 512559680
再次感谢rcgldr让我思考如何在循环设置中处理奇数和偶数，而不是在最后进行清理迭代。
我使用了无分支设置代码，它将4*count%2添加到起始指针。那可以是零，但是加零比分枝看我们是否应该。Fibonacci序列会很快溢出一个寄存器，因此保持序言代码的紧凑和高效是重要的，而不仅仅是循环内部的代码。（如果我们要优化的话，我们希望优化许多长度较短的调用）。
; 64bit SysV register-call ABI
; args: rdi: output buffer pointer. rsi: count
;; locals: rsi: endp
;; eax: current edx: prev
;; ecx: tmp
;; all of these are caller-saved in the SysV ABI, like r8-r11
;; so we can use them without push/pop to save/restore them.
;; The Windows ABI is different.
;void fib(int32_t *dest, uint32_t count); // unrolled version
global fib
fib:
cmp esi, 1
jb .early_out ; count below 1 (i.e. count==0, since it's unsigned)
mov eax, 1 ; current = 1
mov [rdi], eax
je .early_out ; count == 1, flags still set from cmp
;; need this 2nd early-out because the loop always does 2 iterations
;;; branchless handling of odd counts:
;;; always do buf[0]=1, then start the loop from 0 or 1
;;; Writing to an address you just wrote to is very cheap
;;; mov/lea is about as cheap as best-case for branching (correctly-predicted test/jcc for count%2==0)
;;; and saves probably one unconditional jump that would be needed either in the odd or even branch
mov edx, esi ;; we could save this mov by using esi for prev, and loading the end pointer into a different reg
and edx, eax ; prev = count & 1 = count%2
lea rsi, [rdi + rsi*4] ; end pointer: same regardless of starting at 0 or 1
lea rdi, [rdi + rdx*4] ; buf += count%2
;; even count: loop starts at buf[0], with curr=1, prev=0
;; odd count: loop starts at buf[1], with curr=1, prev=1
align 16 ;; the rest of this func is just *slightly* longer than 16B, so there's a lot of padding. Tempting to omit this alignment for CPUs with a loop buffer.
.loop: ;; do {
mov [rdi], eax ;; *buf = current
; on loop entry: curr:eax prev:edx
add edx, eax ; curr:edx prev:eax
;.oddentry: ; unused, we used a branchless sequence to handle odd counts
mov [rdi+4], edx
add eax, edx ; curr:eax prev:edx
;; back to our starting arrangement
add rdi, 8 ;; buf++
cmp rdi, rsi ;; } while(buf < endp);
jb .loop
; dec esi ; set up for this version with sub esi, edx; instead of lea
; jnz .loop
.early_out:
ret
若要生成从零开始的序列，请执行以下操作
curr=count&1; // and esi, 1
buf += curr; // lea [rdi], [rdi + rsi*4]
prev= 1 ^ curr; // xor eax, esi
而不是当前
curr = 1;
prev = count & 1;
buf += count & 1;
我们还可以在两个版本中保存mov指令，方法是使用esi保存prev，因为prev依赖于count。
;; loop prologue for sequence starting with 1 1 2 3
;; (using different regs and optimized for size by using fewer immediates)
mov eax, 1 ; current = 1
cmp esi, eax
jb .early_out ; count below 1
mov [rdi], eax
je .early_out ; count == 1, flags still set from cmp
lea rdx, [rdi + rsi*4] ; endp
and esi, eax ; prev = count & 1
lea rdi, [rdi + rsi*4] ; buf += count & 1
;; eax:curr esi:prev rdx:endp rdi:buf
;; end of old code
;; loop prologue for sequence starting with 0 1 1 2
cmp esi, 1
jb .early_out ; count below 1, no stores
mov [rdi], 0 ; store first element
je .early_out ; count == 1, flags still set from cmp
lea rdx, [rdi + rsi*4] ; endp
mov eax, 1 ; prev = 1
and esi, eax ; curr = count&1
lea rdi, [rdi + rsi*4] ; buf += count&1
xor eax, esi ; prev = 1^curr
;; ESI:curr EAX:prev (opposite of other setup)
;;
;; optimized for code size, NOT speed. Prob. could be smaller, esp. if we want to keep the loop start aligned, and jump between before and after it.
;; most of the savings are from avoiding mov reg, imm32,
;; and from counting down the loop counter, instead of checking an end-pointer.
;; loop prologue for sequence starting with 0 1 1 2
xor edx, edx
cmp esi, 1
jb .early_out ; count below 1, no stores
mov [rdi], edx ; store first element
je .early_out ; count == 1, flags still set from cmp
xor eax, eax ; movzx after setcc would be faster, but one more byte
shr esi, 1 ; two counts per iteration, divide by two
;; shift sets CF = the last bit shifted out
setc al ; curr = count&1
setnc dl ; prev = !(count&1)
lea rdi, [rdi + rax*4] ; buf+= count&1
;; extra uop or partial register stall internally when reading eax after writing al, on Intel (except P4 & silvermont)
;; EAX:curr EDX:prev (same as 1 1 2 setup)
;; even count: loop starts at buf[0], with curr=0, prev=1
;; odd count: loop starts at buf[1], with curr=1, prev=0
.loop:
...
dec esi ; 1B smaller than 64b cmp, needs count/2 in esi
jnz .loop
.early_out:
ret
Fibonacci序列不是特别可并行的。没有简单的方法从F(i)和F(i-4)得到F(i+4)或类似的东西。我们能用向量做的是减少内存的存储量。从：
a = [f3 f2 f1 f0 ] -> store this to buf
b = [f2 f1 f0 f-1]
则a+=b；B+=A；A+=B；b+=a；生成：
a = [f7 f6 f5 f4 ] -> store this to buf
b = [f6 f5 f4 f3 ]
当将两个64bit int打包到128b矢量中时，这就不那么愚蠢了。即使在32bit代码中，也可以使用SSE进行64bit整数数学运算。
此答案的以前版本具有未完成的打包-32位矢量版本，该版本无法正确处理计数%4！=0。为了加载序列的前4个值，我使用了pmovzxbd，这样我就不需要16B的数据，而我只能使用4B。得到第一个-1。1值的序列放入向量寄存器要容易得多，因为只有一个非零值可以加载和混洗。
;void fib64_sse(uint64_t *dest, uint32_t count);
; using SSE for fewer but larger stores, and for 64bit integers even in 32bit mode
global fib64_sse
fib64_sse:
mov eax, 1
movd xmm1, eax ; xmm1 = [0 1] = [f0 f-1]
pshufd xmm0, xmm1, 11001111b ; xmm0 = [1 0] = [f1 f0]
sub esi, 2
jae .entry ; make the common case faster with fewer branches
;; could put the handling for count==0 and count==1 right here, with its own ret
jmp .cleanup
align 16
.loop: ; do {
paddq xmm0, xmm1 ; xmm0 = [ f3 f2 ]
.entry:
;; xmm1: [ f0 f-1 ] ; on initial entry, count already decremented by 2
;; xmm0: [ f1 f0 ]
paddq xmm1, xmm0 ; xmm1 = [ f4 f3 ] (or [ f2 f1 ] on first iter)
movdqu [rdi], xmm0 ; store 2nd last compute result, ready for cleanup of odd count
add rdi, 16 ; buf += 2
sub esi, 2
jae .loop ; } while((count-=2) >= 0);
.cleanup:
;; esi <= 0 : -2 on the count=0 special case, otherwise -1 or 0
;; xmm1: [ f_rc f_rc-1 ] ; rc = count Rounded down to even: count & ~1
;; xmm0: [ f_rc+1 f_rc ] ; f(rc+1) is the value we need to store if count was odd
cmp esi, -1
jne .out ; this could be a test on the Parity flag, with no extra cmp, if we wanted to be really hard to read and need a big comment explaining the logic
;; xmm1 = [f1 f0]
movhps [rdi], xmm1 ; store the high 64b of xmm0. There is no integer version of this insn, but that doesn't matter
.out:
ret
没有必要进一步展开，dep链延迟限制了吞吐量，因此我们可以始终平均每个周期存储一个元素。减少UOP中的循环开销有助于超线程，但这是非常小的。
正如您所看到的，即使在两个展开时处理所有的拐角情况也是相当复杂的。它需要额外的启动开销，即使在您试图优化它以将其保持在最小的时候也是如此。很容易就会出现大量的条件分支。
更新的主：
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>
#ifdef USE32
void fib(uint32_t *buf, uint32_t count);
typedef uint32_t buftype_t;
#define FMTx PRIx32
#define FMTu PRIu32
#define FIB_FN fib
#define CANARY 0xdeadbeefUL
#else
void fib64_sse(uint64_t *buf, uint32_t count);
typedef uint64_t buftype_t;
#define FMTx PRIx64
#define FMTu PRIu64
#define FIB_FN fib64_sse
#define CANARY 0xdeadbeefdeadc0deULL
#endif
#define xstr(s) str(s)
#define str(s) #s
int main(int argc, const char *argv[]) {
uint32_t count = 15;
if (argc > 1) {
count = atoi(argv[1]);
}
int benchmark = argc > 2;
buftype_t buf[count+1]; // allocated on the stack
// Fib overflows uint32 at count = 48, so it's not like a lot of space is useful
buf[count] = CANARY;
// uint32_t count = sizeof(buf)/sizeof(buf[0]);
if (benchmark) {
int64_t reps = 1000000000 / count;
for (int i=0 ; i<=reps ; i++)
FIB_FN(buf, count);
} else {
FIB_FN(buf, count);
for (uint32_t i ; i < count ; i++){
printf("%" FMTu " ", buf[i]);
}
putchar('\n');
}
if (buf[count] != CANARY) {
printf(xstr(FIB_FN) " wrote past the end of buf: sentinel = %" FMTx "\n", buf[count]);
}
}
在我的SandyBridgei5上，对于刚刚低于8192的计数，按2展开的非向量版本的吞吐量接近于理论上的最大吞吐量，即每周期1个存储（每周期3.5条指令）。8192*4B/INT=32768=L1缓存大小。在实践中，我看到~3.3到~3.4个insn/周期。不过，我正在计算Linuxperf的整个程序，而不仅仅是严密的循环。
无论如何，没有任何意义再进一步展开。显然，这不再是count=47之后的Fibonacci序列，因为我们使用了uint32_t。然而，对于较大的count，吞吐量受到内存带宽的限制，低至~2.6insn/周期。在这一点上，我们主要研究如何优化Memset。
64位矢量版本以每周期3个insns（每两个时钟一个128B存储）运行，阵列大小约为L2高速缓存大小的1.5倍。（即./fib64 49152)。当阵列大小增加到L3高速缓存大小的较大部分时，性能下降到L3高速缓存大小的3/4时的每周期~2个insn（每3个时钟一个存储）。当大小大于L3缓存时，它的级别达到每6个周期1个存储区。
所以当我们放入L2缓存而不放入L1缓存时，用向量存储效果更好。
-
主要内容：递归生成斐波那契数列,总结公元 1202 年，意大利数学家莱昂纳多·斐波那契提出了具备以下特征的数列： 前两个数的值分别为 0 、1 或者 1、1； 从第 3 个数字开始，它的值是前两个数字的和； 为了纪念他，人们将满足以上两个特征的数列称为斐波那契数列。 如下就是一个斐波那契数列： 1 1 2 3 5 8 13 21 34...... 下面的动画展示了斐波那契数列的生成过程： 图 1 斐波那契数列 很多编程题目要求我们输
-
题目链接 NowCoder 题目描述 求斐波那契数列的第 n 项，n <= 39。 <!--1}\end{array}\right." class="mathjax-pic"/> --> 解题思路 如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。 递归是将一个问题划分
-
Python3 实例 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13,特别指出：第0项是0，第1项是第一个1。从第三项开始，每一项都等于前两项之和。 Python 实现斐波那契数列代码如下： 实例(Python 3.0+)# -*- coding: UTF-8 -*- # Filename : test.py # author by : www.runoob.com
-
问题内容： 我最初对程序进行了错误编码。我没有为程序返回范围内的斐波那契数（即startNumber 1，endNumber 20应该仅= 1和20之间的那些数字），而是为程序编写了显示范围内的所有斐波那契数（即startNumber 1，endNumber 20）显示=前20个斐波那契数字）。我以为我有一个确定的代码。我也看不出为什么会这样。 有人在我的第二部分中指出了这一点（由于重复而被关闭-
-
问题内容： 关门了 。这个问题需要更加集中。它当前不接受答案。 想要改善这个问题吗？ 更新问题，使其仅通过编辑此帖子来关注一个问题。 6年前关闭。 改善这个问题 如何在SQL中生成斐波那契数列！ 我需要生成斐波那契数列0 1 1 2 3 5 8 13 21 … N 我使用C代码轻松做到了这一点，我需要使用Sql做到这一点！ 问题答案： 试试这个 ！ 0 1 1 2 3 5 8 13 21 34 5
-
一、题目 写一个函数，输入n，求斐波那契数列的第n项值。 斐波那契数列的定义如下： 二、解题思路 按照上述递推式，可以使用循环或递归的方式获取第n项式。 三、解题代码 public class Test { /** * 写一个函数，输入n，求斐波那契（Fibonacci) 数列的第n项 * @param n Fibonacci数的项数 * @ret