6502 算术逻辑单元（ALU）

算术逻辑单元（ALU）是 CPU 的核心部件，负责 CPU 内的各种算术运算。现代 CPU 的 ALU 无疑相当复杂，想要从晶体管或逻辑门级别对它的工作原理进行说明几乎不现实。但是 6502 CPU 是一款颇具知名度但又相对简单的 8 位 CPU，使用它来介绍 ALU 的原理非常合适。接下来让我们来看看 6502 的 ALU 是如何构成以及它的工作原理。
功能

6502 CPU 可以对 8 位有符号和无符号数进行加（ADC）、减（SBC）、按位与（AND）、按位或（ORA）、按位异或（EOR）、左移（ASL，ROL）、右移（LSR，ROR）总共 9 种运算。但是并不是每一种运算都有一个对应的运算模式，6502 ALU 只支持求和（SUMS）、按位与（ANDS）、按位或（ORS）、按位异或（EORS）和右移（SRS）共 5 种运算模式。因此，有些指令是通过一些“巧思”实现的。
减法（SBC）

减法（SBC）是由求和实现的。SBC 指令的功能可以表述为 \(A - M - \overline{C} \to A\)，其中 A 表示 A 寄存器；M 表示内存中的操作数；C 表示标志寄存器中进位标志（CF）的值。SBC 可以转换为加法：

\[\begin{split}SBC =&\ A - M - \overline{C} \\    =&\ A + -M - \overline{C} \\    =&\ A + \overline{M} + 1 - \overline{C} \\    =&\ A + \overline{M} + C\end{split}\]
所以只需要把 M 取反后送入 ALU，然后照常进行加法即可。
左移（ASL，ROL）

左移（ASL，ROL）相当于把操作数乘以 2，所以是通过把操作数加上自身实现的。即 \(X + X + C \to X\)，其中 X 表示操作数（来自 A 寄存器或者内存），C 表示标志寄存器中进位标志（CF）的值。
右移（LSR，ROR）

右移（LSR，ROR）是把每个 NAND 输出位接入到上一个位的总输出中，其中最高位固定为 1。在存储时，最高位有单独的信号（ADD/SB7）用来控制是否放到总线上。运算时，ALU 的两个输入都被配置为操作数，这样：

\[\begin{split}Y_{n} =& \overline{A_{n+1} \cdot B_{n+1}} \\=& \overline{X_{n+1} \cdot X_{n+1}} \\=& \overline{X_{n+1}}\end{split}\]
可见，输出正好是操作数右移一位后取反的结果，要得到正确结果只需对输出取反即可。
核心结构

由于没有乘除法运算，因此 ALU 的核心其实基本就是一个 8 比特全加器，比较有趣的是这个全加器的奇偶位电路略有不同。
其中偶数位全加器的晶体管电路图如下：

对应的逻辑门电路图如下：

奇数位全加器的晶体管电路如下：

对应的逻辑门电路图如下：

想知道晶体管电路是怎么转换到逻辑门电路的？可以看看这篇文章
上面晶体管电路中，x1、x2 用来控制是否对 DATA1 进行取反。x1 用于将相反数送入 ALU，x2 用于将原数送入 ALU。

将这两个运算单元交替串联起来，就组成了 ALU：

注意，这只是演示。由于 6502 支持 BCD，实际电路比上述电路复杂，后文有介绍

外围结构

ALU 的外围结构包括两个输入寄存器（AI 和 BI）、一个输出寄存器（ADD，注意这个不是累加寄存器 AC）、标志寄存器、BCD 修正电路，这些外围结构与 ALU 计算核心一起组成了功能完整的 ALU。运算方式选择实际上是运算结果的选择。从上面的逻辑门电路图不难看出，ALU 是一次性把求和、与、或和异或运算都进行了的，选择不同的计算结果就达到了进行不同计算的目的。
这些外围组件与 ALU 计算核心的连接关系如下：

ALU 状态标志

ALU 除了输出运算结果，还附带输出一些状态信息，这些状态包括：溢出标志（AVR）、符号标志（NF）、进位标志（ACR）、零标志（ZF）以及 BCD 修正要用到的半进位标志（HC）。有了这些状态标志，CPU 就能实现“比较”指令。
溢出标志（AVR）

溢出标志表示计算结果溢出，有符号数运算结果如果小于 -128 或者大于 127 则溢出。溢出标志对于无符号数没有意义，无符号数的溢出看进位标志（ACR）即可。溢出检测电路如下：

图中 Carry6 是 ALU 的第 7 个位（次高位）的进位输出，NAND7 是 ALU NAND 输出的最高位，NOR7 则是 NOR 输出的最高位
上面晶体管电路对应的逻辑门电路图如下：

即：

\[\begin{split}\overline{AVR} =&\overline{\overline{NAND_7+ Carry_6} + NOR_7 \cdot Carry_6} \\AVR =& \overline{NAND_7+ Carry_6} + NOR_7 \cdot Carry_6 \\    =& \overline{\overline{A_7 \cdot B_7} + Carry_6} + \overline{A_7 + B_7} \cdot Carry_6 \\    =& A_7 \cdot B_7 \cdot \overline{Carry_6} + \overline{A_7 + B_7} \cdot Carry_6\end{split}\]
当 Carry6 为 0 时，AVR 等于 \(A_7 \cdot B_7\)；当 Carry6 为 1 时，AVR 等于 \(\overline{A_7 + B_7}\)。让我们一起分析看看这种检测方式是否有效。
若 Carry6 为 0：

• A、B 都为正数时，和小于等于 127。这时不会溢出
  
• A、B 只有一个负数时，它们的和仍然为负数。这时，负数的那个绝对值较大，不会溢出
  
• A、B 都为负数时，它们的和变为正数。显然溢出
  

若 Carry6 为 1：

• A、B 都为正数时，和变为负数。显然溢出
  
• A、B 只有一个负数时，和为正数。这时，正数的那个绝对值较大，不会溢出
  
• A、B 都为负数时，要产生 Carry6 的进位，其中一个（假设是 A）必然大于等于 -64（即次高位为 1），B 则需要满足 B >= (~A + 1) | -128 。B >= (~A + 1) | -128 等价于 B >= -A + -128，也就是 B + A >= -128，即 “A + B” 不会溢出
  

综上，Carry6 为 0 且 A、B 都为负数时（即 \(A_7 \cdot B_7 = 1\)）会溢出；Carry6 为 1 且 A、B 都为正数时（即 \(\overline{A_7} \cdot \overline{B_7} = 1\)）会溢出。
根据上面的分析，我们可以确认 6502 的溢出检测算法是正确的。但是上面的算法有点复杂和难以理解，如果我们进行模拟器开发，通常采用以下算法判断溢出：

1. OV = 0x80 & (AI ^ ADD) & (BI ^ ADD) ? 1 : 0;

复制代码

即，最终结果与 A、B 都异号时，计算会溢出。这其实跟上面 AVR 的逻辑表达式是等价的。
符号标志（NF）

符号标志表示计算结果是否为负数，也就是计算结果的最高位（第 8 位）是否为 1。此标志只在对有符号数进行运算时才有意义。
零标志（ZF）

零标志表示计算结果是否为零，电路非常简单，就是把计算结果送入一个 NOR 门。
进位标志（ACR）

进位标志就是全加器的进位输出取反，不再多做介绍。
半进位标志（HC）

这个标志是 ALU 第 4 个位上产生的进位（Carry3），用于 BCD 修正，没有对应的寄存器。
BCD 模式

6502 CPU 支持硬件 BCD 模式，这种模式需要额外的电路对结果进行修正。BCD 修正电路如在 MOS 科技的专利 patent US 3991307 中有详细介绍。BCD 修正电路包含 BCD 进位部件和 BCD 修正部件两个部分，这些部件与 ALU 加法器的关系如下：

接下来，我们来拆解一下每个部分的工作原理。
BCD 进位

BCD 进位部件分成低四位进位 DC3 和 高四位进位 DC7，其中 DC3 的进位电路如下：

上述电路对应的逻辑表达式如下：

\[\begin{split}DC3 =& DAA \cdot \{(A2 \cdot B2 + A3 \oplus B3) \cdot [A2 \oplus B2 + A1 \oplus B1 + A1 \cdot B1 + (A0 \cdot B0 + AC_{in}) \cdot (A0 + B0)] + (A0 \cdot B0 + AC_{in}) \cdot (A0 + B0) \cdot A1 \cdot B1 \cdot (A2 + B2)\} \\=& DAA \cdot \{(A2 \cdot B2 + A3 \oplus B3) \cdot [Carry0 + A1 + B1 + A2 \oplus B2] + Carry0 \cdot A1 \cdot B1 \cdot (A2 + B2)\}\end{split}\]
其中 \(Carry0 = (A0 \cdot B0 + AC_{in}) \cdot (A0 + B0)\)。
这个逻辑表达式相当复杂，很难想象是怎么设计出来的。对这个表达式进行验算可以发现，A + B + AC 小于 10 时，DC3 为 0；和大于等于 10 时，DC3 大多数情况下值为 1。和大于等于 10 但 DC3 为 0 的情形中，二进制加法进位 Carry3 这时是 1，所以最终并不不影响后续 BCD 修正。
DC3 与 ALU 加法器的第 3 位输出 Carry3 进行 “或” 运算后被送往第 4 位的进位输入。由于实际 ALU 加法器的第 3 位输出是取反了的，且第 4 位的进位输入也要求取反，所以实际电路是这样的：

最后形成的新 Carry3 也被叫做 HC（半进位）。
ALU 加法器加上上述 DC3 进位电路后完成的功能如下：

1. s = a + b + c;
2. if (s > 9) {
3.   s |= 0x10;
4. }

复制代码

DC7 与 DC3 基本上是相同的，不再过多介绍。

对应的逻辑表达式：

\[\begin{split}DC7 &= (A6 \cdot B6 + A7 \oplus B7) \cdot (Carry4 + A5 \cdot B5 + A5 \oplus B5 + A6 \oplus B6) + Carry4 \cdot A5 \cdot B5 \cdot A6 \oplus B6 \\&= (A6 \cdot B6 + A7 \oplus B7) \cdot (Carry4 + A5 + B5 + A6 \oplus B6) + Carry4 \cdot A5 \cdot B5 \cdot A6 \oplus B6\end{split}\]
BCD 修正

BCD 的高、低四位用的是相同的修正电路，这里只细讲低四位的修正电路。低四位修正电路如下：

电路中 SB0~SB3 表示的 CPU 内的特殊总线（SB 总线）的低四位。CPU 在进行 BCD 修正时，SB 总线上的数据实际上就是 ADD 寄存器中的内容（可以参考 Hanson 的框图辅助理解 CPU 内的数据通路）。所以，上述修正电路对应的逻辑表达式如下：

\[\begin{split}DS0 =& ADD0 \\DS1 =& (DSAL + DAAL) \oplus ADD1 \\DS2 =& (DSAL \cdot ADD1 + DAAL \cdot \overline{ADD1}) \oplus ADD2 \\DS3 =& [DSAL \cdot (\overline{ADD1} + \overline{ADD2}) + DAAL \cdot (ADD1 + ADD2)] \oplus ADD3\end{split}\]
当 DAA 为 1 时，DS 等于 ADD + 6; 当 DSA 为 1 时，DS 等于 ADD + 10。这正是 BCD 修正算法。
BCD 命令信号

BCD 修正命令分为加法修正（DAA）和减法修正（DSA）两个信号，信号的生成电路如下：

上面电路中的 51、52 表示解码器的 51、52 号输出。其中 51 解码 SBC 的 T0 周期，52 解码 SBC、ADC 的 T0 周期。D_out 表示 D 标志位（BCD 模式位）的值。

51 的指令匹配模板：111XXXX1
52 的指令匹配模板：X11XXXX1

上面电路对应的逻辑表达式如下：

\[\begin{split}DAA =& \overline{SBC0} \cdot ADC0 \cdot D \\DSA =& SBC0 \cdot D\end{split}\]
上面电路的 DAA、DSA 信号延迟一个时钟周期后（即 T1 周期）将被送到下面的电路中，进一步生成针对高、低四位的命令信号：

注意，这里的 Carry3 并不是加法器第 3 位的输出，而是前面提到的 HC。所以：

\[\begin{split}DAAL =& DAA \cdot HC \\DAAH =& DAA \cdot ACR \\DSAL =& DSA \cdot \overline{HC} \\DSAH =& DSA \cdot \overline{ACR}\end{split}\]
附

完整电路

最后给出完整的重建电路，如下：

代码模拟

带 BCD 修正逻辑的 ADC、SBC 指令模拟代码如下：

1. #define BIT_N    0x80
2. #define BIT_V    0x40
3. #define BIT_B    0x10
4. #define BIT_D    0x08
5. #define BIT_I    0x04
6. #define BIT_Z    0x02
7. #define BIT_C    0x01
8. #define BITS_NVZC    0xc3
10. uint8_t ADC(uint8_t a, uint8_t b, uint8_t *flags) {
11.   int s = 0;
13.   if (*flags & BIT_D) {
14.     s = (a & 0xf) + (b & 0xf) + (*flags & BIT_C);
15.     if (s > 9) {
16.       s = 0x10 | (s + 0x6) & 0xf;
17.     }
18.     s = (a & 0xf0) + (b & 0xf0) + s;
19.     if (s > 0x9f) {
20.       s = 0x100 | (s + 0x60) & 0xff;
21.     }
22.   } else {
23.     s = a + b + (*flags & BIT_C);
24.   }
26.   *flags &= ~BITS_NVZC;
27.   *flags |= ((a ^ s) & (b ^ s) & BIT_N ? BIT_V : 0)
28.     | (s > 255 ? BIT_C : 0)
29.     | ((uint8_t)s ? s & BIT_N : BIT_Z);
31.   return (uint8_t)s;
32. }
34. uint8_t SBC(uint8_t a, uint8_t b, uint8_t *flags) {
35.   int s = 0;
36.   b ^= 0xff;
38.   if (*flags & BIT_D) {
39.     s = (a & 0xf) + (b & 0xf) + (*flags & BIT_C);
40.     if (s < 0x10) {
41.       s = 0x10 | (s + 0xa) & 0xf;
42.     }
43.     s = (a & 0xf0) + (b & 0xf0) + s;
44.     if (s < 0x100) {
45.       s = 0x100 | (s + 0xa0) & 0xff;
46.     }
47.   } else {
48.     s = a + b + (*flags & BIT_C);
49.   }
51.   *flags &= ~BITS_NVZC;
52.   *flags |= ((a ^ s) & (b ^ s) & BIT_N ? BIT_V : 0)
53.     | (s > 255 ? BIT_C : 0)
54.     | ((uint8_t)s ? s & BIT_N : BIT_Z);
56.   return (uint8_t)s;
57. }

复制代码

参考

• patent US 3991307
  
• breaks-alu.md
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！