循环移位扩展是用于什么的？

Question

我记得在一个汇编课上，我们学习了m68k处理器，它有三种不同的移位方式：线性移位、循环移位和带扩展的循环移位。

最后一种带扩展的循环移位，基本上是将所有位向左或向右旋转，但是在将最外层的位移动到开头之前，它会将其放入一个扩展位中（如果您再次移位1）。

我画了一个小图：

基本上，在循环移位中使用了第33位，但当然不会出现在32位的单词中。第33位是处理器的X标志，代表扩展。你可以同样使用任何状态标志，例如进位标志，但我猜摩托罗拉的人想要保留该标志，以免被覆盖，在某些需要带有扩展旋转的算法中需要进位标志来执行其正常职责。

无论如何，旋转带扩展的目的是什么？它用于什么？为什么需要它？它看起来很奇怪。为什么你需要第33位呢？

我阅读了this和this，这两个相关问题，但它们没有讨论带扩展的循环移位。

我知道一些普通移位的用途。基本上是除以二，或测试可除性，并对位进行排列以获得随机性。像那样的东西。但我想不出为什么你需要将一些扩展位插入到旋转中，但在结果中不会出现。

编辑：我对它的任何使用都感兴趣，无论是现代还是古老的，而且是否在m68k上并不重要。 m68k只是我第一次遇到它的地方（我甚至从未在那里使用过它）。

- DrZ214

---

相关：x86中旋转指令（ROL，RCL）的目的是什么？ / 左/右旋转进位的实际用途，但这些问题并没有专注于“带扩展”/“通过进位”的部分；那些其他问题的许多答案只是关于普通旋转的。 - Peter Cordes

Answer 1

假设您想将一个32位的字向右移位，但您只有16位寄存器。为了做到这一点，您需要将32位字的两个16位部分向右移位，并将移出高位的位传送到低位。

如果您只有逻辑移位，那么这样做就很麻烦，因为您必须手动修复那个位。旋转进位指令允许您将需要传输的位保留在进位标志中，并在一次操作中将其插入。旋转进位指令会将移出的位放置在进位标志中，因此您可以轻松地将它们链接在一起以对任意大小的数据进行右移位。

- fuz

---

Fuz所说的，实际上你也可以通过这些旋转将位图图像（B&W 1b位图类型）向左/右移动一个像素。在ZX Spectrum上，要将整个屏幕向右移动1个像素，您可以使用未卷积的rr(hl) inc hl指令循环（或者更确切地说是inc l，其中您知道地址的低8位l <255）...仍然不够快（即使展开并带有部分inc），无法在单个帧中移动整个屏幕，最多只能通过这种方式移动约55％的屏幕（更聪明的游戏会在内存中使用预旋转的精灵来避免较慢的旋转指令）。 - Ped7g

这是一个正确的答案，尽管没有专注于m68k，它只有32位寄存器。如果你在所有地方加倍比特数，它就可以适配。 - tofro

@tofro 显然，当你试图用只有32位寄存器来移动64位数字时，你会遇到同样的问题。 - fuz

Answer 2

在x86（和大多数拥有此指令的体系结构）上，额外的位是进位标志，并且很多东西可以设置该标志。通过带进位左移或右移允许你将进位位移回到其他某个寄存器中。有趣的是m68k使用了不同的标志来实现扩展旋转。

我对m68k不太熟悉，所以我主要会谈论其他架构。（但是显然这是你想要的：apparently that's what you want）

像这样的指令通常可以在比x86或m68k弱得多的微控制器上使用。或者在指令码空间（和解码复杂度）受限的情况下，一些CPU仅具有旋转进位1次而没有常规的移位指令。如果你想要移入0，请确保标志首先被清除。

8051只能进行左/右移1位的旋转和带进位的左/右移1位的旋转，而不能进行移位操作。在ISA参考手册中查看rlc。如果可能的话，在想要移入零的情况下避免使用clr指令，可以在其他一些将Carry清除的操作之后放置rlc指令。

我认为，扩展循环移位通常使用Carry标志，而不是像m68k那样使用自己的X位。

总之，对于CPU来说，扩展精度的旋转是一种传统/预期的操作，但在更有限的CPU上具有更多的用途。

---

对于一个寄存器，rcl reg, 1和adc reg,reg是相同的操作：将旧内容左移1位，并将低位设置为CF。通过旋转或adc移出的位成为CF的新值。因此，如果RCL可用于内存操作数或(对于奇怪的情况)计数大于1，则RCL只是指令集中的非冗余部分。(右旋版本不是冗余的。)

我不知道为什么你会使用计数>1。在现代x86上，通过carry进行旋转的count=1相当快，但是变量计数或固定计数>1则明显较慢。我不知道鸡/蛋问题是如何解决的：CPU设计师没有使其快速，因为没有人使用它，还是人们停止使用它，因为它很慢。但可能是前者，因为我记不起来有人提到过通过carry进行旋转超过1位的用途。

对于扩展精度移位，x86有一个双移位指令（shld / shrd dst, src, count），它将dst向左或向右移动，并从src中移入比零或符号位的位。由于它不适用于2个内存操作数，因此需要使用单独的指令来加载和存储寄存器以实现扩展精度移位循环。与使用rcr dword [edi], 1 / sub edi, 4的循环相比，代码大小更大，但在现代x86上，代码大小很少是问题，使用单独的指令进行加载/存储也不会更慢。更重要的是，shrd一次可以移动多个位，因此可以通过循环数组一次实现2个或多个位的多精度移位。

扩展旋转只能在寄存器之间每次移动一个位，因为它使用一个1位存储空间（在标志位中）。我认为，在m68k上，如果您确实想在寄存器之间移动多个位，则可能会复制寄存器并使用常规移位+ OR进行组合。（或者使用旋转和AND/OR拆分位。）

在 AMD 的 CPU 上，shld/shrd 比 rcl/rcr-by-1 更慢，但在 Intel 的 CPU 上则相反。 (http://agner.org/optimize/)。

---

我真的想不出除了在寄存器之间移位比特以外的任何用例。也许如果你将一个比特移出，然后分支到可能设置或清除X比特的某个位置，然后将比特移回来，你可以使用扩展旋转对低位或高位进行某些操作？但是通常情况下，您可以更轻松地使用AND、OR或XOR与常量执行相同的操作。

- Peter Cordes

---

另一个用例是填充位缓冲区。您可以使用1初始化缓冲区，并使用rcl将cf中的值移入缓冲区中进行填充。当在rcl之后设置了cf，则知道缓冲区已满，并且可以在不必跟踪计数器或类似内容的情况下将其刷新出去。 - fuz

“（我写完大部分答案后才注意到你特别提到m68k）。实际上，我对使用带扩展的旋转感兴趣。 m68k只是我最先遇到它的地方。我已经编辑了原始帖子。” - DrZ214

我不知道为什么你会使用计数> 1。我也不知道。我当然可以想到线性移位和循环移位（不带扩展）的用途，但是你知道我甚至记不起m68k指令集是否允许将立即值传递给移位操作，或者是否必须通过指令n次循环。 - DrZ214

@DrZ214：好的，很高兴我还是发布了这个答案。在x86上，使用CF，你可能可以通过将CF中的一位（以另一种方式设置）移位到寄存器中来做更多奇怪的技巧。正如Fuz指出的那样，你可以通过这种方式设置位图。 - Peter Cordes

@DrZ214：增加了关于8051的部分，该部分只有旋转操作，没有常规的移位操作。 - Peter Cordes

Answer 3

ROXL非常有用，可以进行非破坏性位测试，并且与BTST.x指令相比可以节省相当多的指令（BTST.x指令仅适用于8位和32位大小）。一旦你这样做了，通过旋转超过一个位置，还可以实现跳过某些位的功能。

  ROXL.W #4,D0      ; shift bit 12 into carry and X
  BCC.S isNotSet    ; branch if bit is not set
  BSR isSet         ; do whatever you want
isNotSet:
  ROXL.W #11,D0     ; rotate around to reset to previous value

- tofro

Answer 4

它还用于扩展精度的乘法和除法，因为这些操作基本上是加（或减）和移位。这也意味着我们可以做一些很酷的事情，比如下面这个:

ADD eax, ebx
RCR eax, 1

计算2个整数的平均值。

有一个汇编演示程序，用256字节的代码，使用RCL注册表和CL工具来在仅使用2字节的情况下计算随机数字。

- Olorin