时间戳

首页 > 解决方案 > 可以“交换 nybble”和“字节掩码”技巧将多字节逻辑移位 4 比使用移位链的天真方法快得多

microcontroller - 可以“交换 nybble”和“字节掩码”技巧将多字节逻辑移位 4 比使用移位链的天真方法快得多

问题描述

我正在编写一个定点 (16Q16) 算法，该算法使用Wikipedia 上概述的 Newton-Raphson 方法进行除法。（相关的 SE 问题在这里。）

第一步需要逻辑右移 1-16 位。我的 CPU 是 8 位微控制器，所以没有桶形移位器；硬件只能支持移位 1 位。（相关的 SE 问题在这里。）按位移n位，可以使用单次移位指令n时间，但是，这具有显着的最坏情况时序。当与移位的多字节性质相结合时，这种糟糕的最坏情况变得非常糟糕。如果将 1 个字节移位 1 次需要 1 个周期，我们可以很快想象出需要将 16 个字节移位 16 次时的问题。请记住，这只是第一步。

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

我遇到的问题是讨厌的 4 班。

我的直觉，以及这里和那里的一些片段和帖子，告诉我它们存在一种有效的方法，可以将 nybble 交换指令与位掩码和逻辑操作结合起来，以创建一种可以优化转换的“nybble 交换拉链效应”一个任意长度的 4 位数组。（相关的 SE 问题在这里。链接到答案 3）

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

使用任何类型的 nybble 交换字节掩码技巧，这是否可以通过更接近每字节一个周期而不是每比特一个周期的时间复杂度来完成？

注意：这是 PIC18 ASM，但很明显发生了什么。任何关于如何进行重大改进的建议都是对这个问题的回答。是的！我意识到它很可能已经非常接近最优，但意识到移位 4 是几段代码中反复出现的热点。我希望从每个块中至少删除一条指令。砍掉两个会很棒。

; 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
;------------------------------------------

标签： microcontrollerbit-shiftpicpic188-bit

解决方案

您的解决方案涉及 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

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

推荐阅读