microcontroller - "swap nybble"和 "byte mask"技巧是否可以比使用移位链的简单方法更快地进行多字节逻辑移位 4

Question

我正在编写一个定点 (16Q16) 算法，它使用 Newton–Raphson 方法进行除法 outlined on Wikipedia. (相关 SE 问题 HERE .)

第一步需要逻辑右移 1-16 位。我的 CPU 是一个 8 位微 Controller ，所以没有桶形移位器；硬件只能支持移动 1 位。 (相关的 SE 问题 HERE。)要移动 n 位，可以使用单个移位指令 n 次，但是，这具有明显的最坏情况时序。当移位的多字节性质复杂化时，这种糟糕的最坏情况变得糟糕透顶。如果将1个字节移位1次需要1个周期，我们可以很快想象需要将16个字节移位16次时的问题。请记住，这只是第一步。

明显的优化就是分而治之；手动计算 2 的所有幂。第一个简单的情况是移动 16 和 8，因为这只是将内存索引更改为定点数。这样做只需大约 4 个周期/指令即可将 16 字节移位 16 位，与“单移位链接”相比速度提高了 64 倍。

我遇到的问题是讨厌的 4 类次。

我的直觉以及一些片段和帖子告诉我，它们存在一种有效的方法，可以将 nybble 交换指令与位掩码和逻辑操作结合起来，以创建一种“nybble 交换 zipper 效果”可以最佳地将任意长度的数组移动 4 位。 (相关 SE 问题 HERE。答案 3 的链接)

我知道它至少可以从根本上完成，因为我有一个仅使用 SWAP、XOR 和 AND 指令的概念教授。我也知道它可以更快地完成，因为我所拥有的比简单的移位链方法快一个周期(哈哈，是的，一个)。 (见下面的代码框)我不知道的是......

是否可以使用任何类型的 nybble 交换字节掩码技巧以更接近每个字节一个周期而不是每个位一个周期的时间复杂度来完成此操作？

注意:这是 PIC18 ASM，但很明显发生了什么。关于如何对此进行重大改进的任何建议都将是对这个问题的回答。是的!我意识到它很可能已经接近最佳状态，但意识到移动 4 是几段代码中反复出现的热点。我期望从每个 block 中至少删除一条指令。剪掉两个会很棒。

; Shift the denominator -> 4 (19 cyc)
;------------------------------------------
        SWAPF   Denom+3, W, BANKED
        MOVWF   Denom+3, BANKED
        ANDLW   0xF0
        XORWF   Denom+3, F, BANKED

        SWAPF   Denom+2, F, BANKED
        XORWF   Denom+2, F, BANKED
        XORWF   Denom+2, W, BANKED
        ANDLW   0xF0
        XORWF   Denom+2, F, BANKED

        SWAPF   Denom+1, F, BANKED
        XORWF   Denom+1, F, BANKED
        XORWF   Denom+1, W, BANKED
        ANDLW   0xF0
        XORWF   Denom+1, F, BANKED

        SWAPF   Denom+0, F, BANKED
        XORWF   Denom+0, F, BANKED
        XORWF   Denom+0, W, BANKED
        ANDLW   0xF0
        XORWF   Denom+0, F, BANKED
;------------------------------------------

Answer 1

您的解决方案涉及 19 条指令(每条指令需要一个周期)，但简单的解决方案只需要 18 条指令:

RRCF   Denom+3, F, BANKED
RRCF   Denom+2, F, BANKED
RRCF   Denom+1, F, BANKED
RRCF   Denom+0, F, BANKED

RRCF   Denom+3, F, BANKED
RRCF   Denom+2, F, BANKED
RRCF   Denom+1, F, BANKED
RRCF   Denom+0, F, BANKED

RRCF   Denom+3, F, BANKED
RRCF   Denom+2, F, BANKED
RRCF   Denom+1, F, BANKED
RRCF   Denom+0, F, BANKED

RRCF   Denom+3, F, BANKED
RRCF   Denom+2, F, BANKED
RRCF   Denom+1, F, BANKED
RRCF   Denom+0, F, BANKED

MOVLW  0x0F
ANDWF  Denom+3, F, BANKED

我想不出比实际执行这种转变更快的方法了。