Reverse-engineering the vintage Intel 8087’s tangent algorithm: more than CORDIC

逆向工程英特尔 8087 复古芯片的正切算法：不仅仅是 CORDIC

Reverse-engineering the vintage Intel 8087’s tangent algorithm: more than CORDIC. I hope you’re not tired of the 8087, because I have another article about Intel’s floating-point chip. In 1980, Intel introduced the 8087, making floating-point operations much faster in the IBM PC and other systems. In this article, I look at the algorithm behind the chip’s tangent instruction. One popular approach for trigonometric functions is an algorithm called CORDIC. Another approach is a polynomial approximation. The 8087 combined the two to obtain both high accuracy and high performance.

逆向工程英特尔 8087 复古芯片的正切算法：不仅仅是 CORDIC。希望你还没有对 8087 感到厌倦，因为我还有一篇关于英特尔浮点芯片的文章。1980 年，英特尔推出了 8087，使得 IBM PC 及其他系统中的浮点运算速度大幅提升。在本文中，我将探讨该芯片正切指令背后的算法。三角函数的一种流行方法是 CORDIC 算法，另一种则是多项式逼近。8087 将两者结合起来，从而同时获得了高精度和高性能。

The 8087 provided an enormous speedup over the 8086 microprocessor, computing a tangent in 90 microseconds rather than 13,000 microseconds. By examining the circuitry and microcode of the 8087, I can explain the algorithm behind the tangent instruction, called FPTAN. To explore the 8087’s circuitry, I popped the lid off a chip with a chisel and created a high-resolution image with a microscope. The microcode ROM is the large rectangular region in the center of the die, holding the 1648 micro-instructions that control the chip. The bottom half of the chip (red box) is the datapath, the circuitry that performs floating-point calculations on 80-bit values.

8087 相比 8086 微处理器提供了巨大的速度提升，计算正切仅需 90 微秒，而此前则需要 13,000 微秒。通过检查 8087 的电路和微代码，我可以解释正切指令（称为 FPTAN）背后的算法。为了探索 8087 的电路，我用凿子撬开了芯片盖，并用显微镜制作了一张高分辨率图像。微代码 ROM 是芯片中心的大型矩形区域，存储着控制芯片的 1648 条微指令。芯片的下半部分（红色框）是数据通路，即对 80 位数值执行浮点计算的电路。

A close-up of the 8087’s datapath, showing functional blocks that are used by FPTAN. Zooming in on the datapath shows the relevant functional units. The exponent ROM holds fixed exponent values that the algorithms need. The constant ROM holds constants, including the constants used by the CORDIC algorithm. The shifter is a large component; it shifts a 64-bit value left or right by arbitrary amounts. The adder is the heart of the 8087’s calculations; as well as providing addition and subtraction, it is used in a loop for multiplication, division, and square roots. The B register holds one input to the adder, while multiple sources can provide the other input. The sum register holds the adder’s output. The eight stack registers and the temporary registers hold floating-point numbers. Finally, the shift register holds 16 status bits for the CORDIC calculations.

8087 数据通路的特写，展示了 FPTAN 使用的功能模块。放大数据通路可以看到相关的功能单元。指数 ROM 存储了算法所需的固定指数值。常量 ROM 存储了常量，包括 CORDIC 算法使用的常量。移位器是一个大型组件，它可以将 64 位数值向左或向右移动任意位数。加法器是 8087 计算的核心；除了提供加法和减法外，它还被用于乘法、除法和平方根的循环运算中。B 寄存器保存加法器的一个输入，而其他多个源可以提供另一个输入。和寄存器保存加法器的输出。八个堆栈寄存器和临时寄存器用于保存浮点数。最后，移位寄存器保存了用于 CORDIC 计算的 16 位状态位。

The CORDIC algorithm: CORDIC is a clever algorithm for quickly computing transcendental functions with simple hardware: it uses shift and add instructions along with table lookups, but doesn’t need multiplication or division. This algorithm dates back to 1956, when it was developed for the B-58 Hustler, the first bomber capable of flying at Mach 2. The aircraft had an analog navigation computer, but analog components provided limited accuracy. Engineer Jack Volder was given the task of designing a digital computer to replace the analog computer. One key problem was that an analog computer can easily generate sines and cosines with an electromechanical device called a resolver. But trigonometric functions are difficult to produce digitally, especially with the slow transistors of that era.

CORDIC 算法：CORDIC 是一种巧妙的算法，可以通过简单的硬件快速计算超越函数：它使用移位和加法指令以及查表法，而不需要乘法或除法。该算法可以追溯到 1956 年，当时它是为 B-58“盗贼”轰炸机开发的，这是第一架能够以 2 马赫速度飞行的轰炸机。该飞机配备了模拟导航计算机，但模拟组件提供的精度有限。工程师 Jack Volder 被委以重任，设计一台数字计算机来取代模拟计算机。一个关键问题是，模拟计算机可以通过一种称为“分解器”的机电装置轻松生成正弦和余弦。但在数字环境下，尤其是考虑到那个时代缓慢的晶体管，生成三角函数非常困难。

Jack Volder came up with a fast way to calculate trigonometric functions with simple hardware. He called the algorithm—and the computer that implemented it—CORDIC: “COordinate Rotation DIgital Computer”. CORDIC converts an angle to a vector, where the vector’s coordinates provide the necessary trig functions. The trick is to break down the angle into a sequence of special angles, angles that make vector rotation easy. These special angles are precomputed and stored in a table, so the CORDIC calculation can be performed quickly, even on 1950s hardware. Each CORDIC iteration provides an additional bit of accuracy, so the algorithm converges rapidly. CORDIC became popular, including in scientific calculators, which used decimal CORDIC instead of binary.

Jack Volder 想出了一种用简单硬件快速计算三角函数的方法。他将该算法以及实现它的计算机称为 CORDIC：“坐标旋转数字计算机”。CORDIC 将角度转换为向量，向量的坐标提供了所需的三角函数。其诀窍是将角度分解为一系列特殊角度，这些角度使向量旋转变得容易。这些特殊角度是预先计算并存储在表中的，因此即使在 1950 年代的硬件上，CORDIC 计算也能快速执行。每次 CORDIC 迭代都会提供额外的精度位，因此算法收敛迅速。CORDIC 变得非常流行，包括在科学计算器中，这些计算器使用十进制 CORDIC 而不是二进制。

Some trigonometry: I’ll try to keep the math to a minimum, but in this section I’ll give a quick explanation of how CORDIC works. The diagram below reviews how trig functions are related to the coordinates of a point. Suppose you have an angle θ; it specifies a point (X, Y) on the unit circle. The basic formulas are X=cos θ, Y=sin θ, and Y/X = tan θ. Thus, if you can determine the coordinate (X, Y), then you can determine the value of the trig functions. If the point is not on the unit circle, e.g. (X’, Y’), then you can still easily determine tan θ. (Spoiler: this is what the 8087 does.) However, sin θ and cos θ become messy.

一些三角学知识：我将尽量减少数学公式，但在本节中，我将简要解释 CORDIC 的工作原理。下图回顾了三角函数如何与点的坐标相关联。假设你有一个角度 θ；它指定了单位圆上的一个点 (X, Y)。基本公式为 X=cos θ，Y=sin θ，以及 Y/X = tan θ。因此，如果你能确定坐标 (X, Y)，那么你就能确定三角函数的值。如果该点不在单位圆上，例如 (X’, Y’)，那么你仍然可以轻松确定 tan θ。（剧透：这就是 8087 所做的事情。）然而，sin θ 和 cos θ 会变得很复杂。

If you’ve done any computer graphics, you’ve probably seen how a rotation matrix can rotate a point by an angle. (If you’re not familiar with rotation matrices, you can read about them here or just trust that it works.) Multiplying a point (X, Y) by the rotation matrix yields the new point (X’, Y’) as shown below. Unfortunately, since the rotation matrix requires sin and cos, it doesn’t seem like it helps solve our problem. However, we can divide the matrix by cos θ; this seems even less helpful since now the matrix needs tan, which is what we want to evaluate. (Moreover, the vector’s length will grow.) But the key to CORDIC is to use special angles, αn = arctan(2-n). When we substitute one of these special angles into the matrix, we get a matrix which is easy to evaluate in hardware: multiplying by a power of 2 can be done by shifting the bits.

如果你做过计算机图形学，你可能见过旋转矩阵如何将一个点旋转一个角度。（如果你不熟悉旋转矩阵，可以在此处阅读相关内容，或者直接相信它有效。）将点 (X, Y) 乘以旋转矩阵会得到新点 (X’, Y’)，如下所示。不幸的是，由于旋转矩阵需要 sin 和 cos，它似乎对解决我们的问题没有帮助。然而，我们可以将矩阵除以 cos θ；这似乎更没用，因为现在矩阵需要 tan，而这正是我们想要计算的。（此外，向量的长度会增加。）但 CORDIC 的关键在于使用特殊角度 αn = arctan(2-n)。当我们把这些特殊角度之一代入矩阵时，我们得到一个易于在硬件中计算的矩阵：乘以 2 的幂可以通过位移来实现。