assembly - 6502 的快速有符号 16 位除以 7

Question

我正在为 6502 cpu 编写一个汇编语言程序，并且发现我需要一个尽可能快的除七例程，特别是可以接受 16 位除数的例程。

我熟悉找到的例程here ，但是推广除七例程发现相当复杂，粗略地考察一下通用算法(使用整数除法)

x/7 ~= (x + x/8 + x/64 ... )/8

表示要处理 16 位范围，可能需要超过 100 个周期才能完成，因为 6502 的单个累加器寄存器以及 6502 上各个内存位移位的相对速度较慢。

我认为查找表可能会有所帮助，但在 6502 上，我当然仅限于 256 字节或更少的查找表。为此，可以假设存在两个 256 字节的查找表 xdiv7 和 xmod7，当使用无符号的单字节值作为表的索引时，可以快速获得字节除以 7 或模的结果分别为 7 个。不过，我不确定如何利用这些来查找完整 16 位范围的值。

同时，我还需要一个模 7 算法，尽管理想情况下，任何可以通过除法得出的解决方案也都会产生模 7 结果。如果需要额外的预计算表，我可以添加这些表，只要所有表的总内存需求不超过大约 3k。

虽然我最终需要一个有符号除法算法，但无符号算法就足够了，因为我可以根据需要将其概括为有符号例程。

任何帮助将不胜感激。

Answer 1

注意:如@Damien_The_Unbeliever评论中指出，upperHigh 和 lowerLow 表是相同的。因此它们可以组合成一个表。然而，这种优化会使代码更难阅读，解释也更难写，因此组合表格留给读者作为练习。

<小时/>

下面的代码展示了如何在将 16 位无符号值除以 7 时生成商和余数。解释代码的最简单方法 (IMO) 是通过一个示例，所以让我们考虑除 0xa732 by 7. 预期结果是:

quotient = 0x17e2
remainder = 4  

我们首先将输入视为两个 8 位值，即高字节和低字节。 高字节是0xa7，低字节是0x32。

我们从上字节计算商和余数:

0xa700 / 7 = 0x17db
0xa700 % 7 = 3 

所以我们需要三个表:

• upperHigh 存储商的高字节:upperHigh[0xa7] = 0x17
• upperLow 存储商的低字节:upperLow[0xa7] = 0xdb
• upperRem 存储余数:upperRem[0xa7] = 3

我们从低字节计算商和余数:

0x32 / 7 = 0x07
0x32 % 7 = 1

所以我们需要两个表:

• lowerLow 存储商的低字节:lowerLow[0x32] = 0x07
• lowerRem 存储余数:lowerRem[0x32] = 1

现在我们需要汇总最终答案。余数是两个余数之和。由于每个余数都在 [0,6] 范围内，因此总和在 [0,12] 范围内。因此我们可以使用两个 13 字节查找将和转换为最终余数和进位。

商的低字节是该进位与 lowerLow 和 upperLow 表中的值之和。请注意，总和可能会在高字节中生成进位。

商的高字节是该进位与 upperHigh 表中的值之和。

因此，要完成该示例:

remainder = 1 + 3 = 4              // simple add (no carry in)
lowResult = 0x07 + 0xdb = 0xe2     // add with carry from remainder
highResult = 0x17                  // add with carry from lowResult

实现此功能的汇编代码由 7 个表查找、一个不带进位的加法指令和两个带进位的加法指令组成。

<小时/>

#include <stdio.h>
#include <stdint.h>

uint8_t upperHigh[256];  // index:(upper 8 bits of the number)  value:(high 8 bits of the quotient)
uint8_t upperLow[256];   // index:(upper 8 bits of the number)  value:(low  8 bits of the quotient)
uint8_t upperRem[256];   // index:(upper 8 bits of the number)  value:(remainder when dividing the upper bits by 7)
uint8_t lowerLow[256];   // index:(lower 8 bits of the number)  value:(low  8 bits of the quotient)
uint8_t lowerRem[256];   // index:(lower 8 bits of the number)  value:(remainder when dividing the lower bits by 7)
uint8_t carryRem[13]    = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1 };
uint8_t combinedRem[13] = { 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5 };

void populateLookupTables(void)
{
    for (uint16_t i = 0; i < 256; i++)
    {
        uint16_t upper = i << 8;
        upperHigh[i] = (upper / 7) >> 8;
        upperLow[i] = (upper / 7) & 0xff;
        upperRem[i] = upper % 7;

        uint16_t lower = i;
        lowerLow[i] = lower / 7;
        lowerRem[i] = lower % 7;
    }
}

void divideBy7(uint8_t upperValue, uint8_t lowerValue, uint8_t *highResult, uint8_t *lowResult, uint8_t *remainder)
{
    uint8_t temp = upperRem[upperValue] + lowerRem[lowerValue];
    *remainder = combinedRem[temp];
    *lowResult = upperLow[upperValue] + lowerLow[lowerValue] + carryRem[temp];
    uint8_t carry = (upperLow[upperValue] + lowerLow[lowerValue] + carryRem[temp]) >> 8;  // Note this is just the carry flag from the 'lowResult' calcaluation
    *highResult = upperHigh[upperValue] + carry;
}

int main(void)
{
    populateLookupTables();

    uint16_t n = 0;
    while (1)
    {
        uint8_t upper = n >> 8;
        uint8_t lower = n & 0xff;

        uint16_t quotient1  = n / 7;
        uint16_t remainder1 = n % 7;

        uint8_t high, low, rem;
        divideBy7(upper, lower, &high, &low, &rem);
        uint16_t quotient2 = (high << 8) | low;
        uint16_t remainder2 = rem;

        printf("n=%u q1=%u r1=%u q2=%u r2=%u", n, quotient1, remainder1, quotient2, remainder2);
        if (quotient1 != quotient2 || remainder1 != remainder2)
            printf(" **** failed ****");
        printf("\n");

        n++;
        if (n == 0)
            break;
    }
}