1

我是汇编初学者，这是我设计用于从二进制转换为灰色的代码，并以十六进制打印生成的位模式。

      mov      al, a               
      mov      bl, al
      shr      bl, 1
      xor      al, bl

虽然程序可以运行，但我想学习其他更简单的方法来提高效率，我尝试了很多其他方法，但它影响了输出。

4

1 回答 1

2

（这个答案是根据问题的第一个版本编写的，其中有一些尚未优化的十六进制打印代码，它是 .exe 程序的完整源代码。问题的更新删除了唯一的部分除了与 8086 无关的 ILP 外，还有优化的空间，所以我不打算删除答案的这些部分。）

代码大小优化（与 8086 尤其是 8088 的速度相关，请参阅此逆向计算答案）：

  • bin2Gray 部分：没有变化，除非您计算从内存重新加载或a保持不变。只需重新订购 Pentium 及更高版本上 ILP 的说明。或者也许是一张桌子xlat。
  • byte->hex 数字：21 个字节，低于 32 个（以及更少的代码获取字节数）
  • 退出：从 4 (mov ah / int) 下降 1 个字节 ( ret)。至少适用于.com较小的可执行文件。

我可能应该计算需要获取的总字节数（即执行指令的字节数）的代码大小，而不是静态代码大小，尽管这对于优化也很有用。

从 21 字节 bin2hex 部分中删除循环将花费几个字节的静态代码大小，但将动态字节数减少约 5，IIRC。并避免在采用的分支上丢弃任何预取缓冲区，当然除外int 10h。

int 20h也可以退出（不需要任何 AH 设置），但只能从.com可执行文件中退出。对我来说有趣的部分是用紧凑的代码计算所需寄存器中的 ASCII 数字，但如果你想要一个小的整体程序，a.com是要走的路。这也避免了 DS 的设置。a（尽管如果您制作和 EQU 或=常量，则不需要设置 DS 。）

未尝试：利用初始寄存器值，这在某些 DOS 版本中显然是可靠的。如果您假装自己正在编写一个可能对较大程序有用的块，那是不可行的。

您的程序基本上有两个独立的部分；计算格雷码，并为寄存器中的 1 字节值计算 bin->hex。单独提取半字节并不能有效地向后优化格雷码计算，所以我认为我们可以将它们完全分开。

有多种不同的方法可以制作格雷码（在连续值之间只有一位翻转）。AFAIK，x ^ (x>>1)是从二进制计算中最便宜的，但在给定寄存器中的输入的情况下，仅用 2 条指令就可以完成某些事情并非不可能。

也相关： gray->binary 的格雷码算法（32 位或更少）指出标准x ^ (x>>1)是 GF(2 k ) 中的乘法。gf2p8affineqb所以在最近的带有 Galois-Field 指令的 CPU 上，我认为你可以一次执行 16 个字节。（gf2p8mulb使用一个固定的多项式，我认为这不是我们想要的。）

8088 性能主要与内存访问有关（包括代码获取）

https://www2.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/opcode_i.html显示指令时序，但这些时序只是执行，而不是代码获取。8088 有一个 4 字节的预取缓冲区（并且只有一个 8 位数据总线），8086 上有 6 字节的 16 位总线。Supercat 在那里的回答中建议：

在最初的 8088 处理器上，估计执行速度的最简单方法通常是忽略周期计数，而是计算内存访问次数，包括取指令，然后乘以 4。

我认为 8086 的情况大致相同，只是每次访问都可以是一个完整的 2 字节字。所以直线代码（没有分支）一次可以获取 2 个字节。

为简单起见，我只是用表中的指令大小和循环计数对 asm 源进行了注释，而没有尝试对预取缓冲区的行为进行建模。

xlat(like al = ds:[bx+al]) 只有 1 个字节，如果您不介意拥有一个 256 字节的表，则值得使用。执行需要 11 个字节，但这包括它进行的数据访问。不计取代码，//mov bl,al是2+2+3个周期，但是3个字的代码大小会花费12个周期来取。xlat 几乎需要那么长的时间，但是当它完成时，预取缓冲区将有一些时间来获取以后的指令，所以我认为这更像是一个胜利。shr al,1xor al,bl

尽管如此，它确实要求该表来自某个地方，或者在加载可执行文件时来自磁盘，或者您必须预先计算它。而且您需要获得指向 BX 的指针，因此只有在循环中执行此操作才可能是胜利。

但是，如果您使用的是表格，您可以将问题的两个部分结合起来，并查找给定二进制的格雷码的两个 ASCII 十六进制数字字符，例如mov dx, [bx + si]在 SI 中使用表指针，在 BL 中使用二进制字节和 BH =0。（DX 设置您使用 DOS 调用输出 DL。）这当然需要您的表为 256个字（512 个字节）。拥有一个很小的可执行文件可能比在这里节省几个周期更有价值；屏幕或文件的实际 I/O 可能足够慢，因此无关紧要。但是，如果您对多个字节执行此操作，则将 ASCII 字节对复制到缓冲区中可能会很好。

有一种优化将有助于更现代的 CPU（从 Pentium 开始）可以并行运行多于 1 条指令：复制寄存器，然后移动原始寄存器，以便可以在与复制相同的周期内发生。

; optimized for Instruction-level Parallelism
;; input: AL    output: AL = bin_to_gray(AL)
;; clobbers: DL
   mov  dl, al         ; 2B  2 cycles (not counting code-fetch bottlenecks)
   shr  al, 1          ; 2B  2c
   xor  al, dl         ; 2B  3c

（有关现代 CPU 的更多信息，请参阅https://agner.org/optimize/。而且x86 的 MOV 真的可以“免费”吗？为什么我根本不能重现这个？ - mov-elimination 不适用于字节或字寄存器，因为它合并到 EDX 的低部分。所以即使在一般具有 mov-elimination 的 CPU 上，它也不能在这里应用，因此这种优化可以节省延迟。）

我很确定 bin -> gray 没有进一步的改进空间。即使是现代 x86 也没有复制和右移（除了另一个寄存器 BMI2 中的计数shrx，或带有 AVX 的 SIMD 寄存器，但仅适用于 word/dword/qword 元素大小）。也没有右移和异或，所以没有避免 a mov，并且 shr 和 xor 显然也是必要的。XOR 是无进位加法，但我认为这没有帮助。除非您有无进位乘法 ( pclmulqdq) 和乘法器常数，以将输入的两个副本以正确的偏移量相互复制到乘法结果的高半部分，否则您将需要分别执行这些操作。或者使用 Galois-field 新指令 (GFNI)：AVX-512 Galois-field 相关指令有什么用途？

尽管如此，如果您想彻底检查，https ://en.wikipedia.org/wiki/Superoptimization - 要求超级优化器寻找产生与 mov/shr/xor 序列相同的 AL 结果的序列。

在实际用例中，您通常需要在寄存器中获取数据的代码，因为这就是您应该将数据传递给函数的方式。之后mov al, a，这就是您的代码正在做的事情。

但是，如果它是内存中的全局变量，则可以通过两次加载而不是复制寄存器来节省一个字节的代码大小，但mov会牺牲速度。 或者更好的是，使它成为一个汇编时间常数。 （虽然如果你这样做了，下一步就是mov al, a ^ (a>>1)在组装时进行计算。）

; a equ 0ACh         ; makes the following instructions 2 bytes each
;;; otherwise, with a being static storage, loading from memory twice sucks
    mov  al, a
    shr  al, 1    ; 2B, 2 cycles
    xor  al, a    ; reg,imm: 2B, 4 cycles on 8088.    reg,mem: 3B, 13+6 cycles

字节 -> 2 个 ASCII 十六进制数字

这是更有趣的部分。

只循环 2 次迭代有时是不值得的，尤其是当你将事情分开做每一半时，你可以节省一些工作。（例如低半字节是x & 0xf，高是x >> 4。使用 rol/mov/and 不是最佳的。）

技巧：

  • Prefer insn al, imm - x86对带有 AL 的立即操作数有简短的特殊情况。（也是 AX,imm16）。

  • 想要在 AL 中做事意味着使用BIOS int 10h/ AH=0Eh电传输出打印更有效，该输出在 AL 中输入，并且不会破坏任何其他寄存器。我认为 BIOS 输出将忽略 DOS I/O 重定向，foo > outfile.txt并始终打印到屏幕上。

  • 有一个邪恶的黑客滥用DAS将 0..15 整数转换为 ASCII 十六进制数字'0'..'9'或'A'..'F'没有分支。在 8086（与现代 x86 不同）上，DAS 与典型的整数指令一样快。请参阅此 codegolf.SE 答案，详细了解其工作原理；这是非常不明显的，但它避免了分支，所以它实际上是 8086 的一个很大的加速。

  • BIOS/DOS 调用一般不会修改 AH，所以可以在循环外进行设置。

  • 然后对于代码大小，而不是仅仅展开，使用cl=4作为循环计数器来循环并重新运行一些较早的代码一次（不包括移位）。 sub cl, 2/jnz会起作用，但使用奇偶校验标志是一种使用dec cx(1B) /jpe向后跳一次，然后在下一次下降的方法。

  • DOS程序（或至少.com程序）有SP指向一些干净退出的代码的地址。所以你可以通过 退出ret。

（我没有考虑在保持整体策略的同时改进你的循环。使用AL尽可能多的指令可能是值得的，但是rol在 8086 上运行两次而不是移动一次会花费很多周期：8 + 4*n for按 CL 移动。）

;; input: byte in AL.   output: print 2 ASCII hex digits with BIOS int 10h
;; clobbers: CX, DX
hexprint_byte:
     mov   ah, 0Eh                       ; BIOS teletype call #
;     push  ax            ; 1B 15c
     mov   dx, ax        ; 2B 2c         ; save number, and AH=call number
     mov   cl, 4         ; 2B 4c
     shr   al, cl        ; 2B 8+4*4 cycles   isolate the high nibble
.loop:
     cmp   al, 10        ; 2B 4c  set CF according to digit <= 9
     sbb   al, 69h       ; 2B 4c  read CF, set CF and conditionally set AF
     das                 ; 1B 4c   magic, which happens to work
     int   10h           ; 2B        BIOS teletype output (AL), no return value
;     pop   ax            ; 1B 12c    ; would do one extra pop if you used this instead of mov/xchg, so you'd need jmp ax instead of ret.  But AND destroys AX
     xchg  ax, dx        ; 1B 3c     ; retrieve the original again (with AH=0Eh call number)
     and   al, 0Fh       ; 2B 4c     ; isolate the low nibble this time

     dec   cx            ; 1B 3c     ; PF is set from the low byte only, CH garbage isn't a problem.  
     jpe   .loop         ; 2B 4c-not-taken, 16c-taken
               ;  4-1 = 3, (0b11) which has even parity
               ; so JPE is taken the first time, falls through the 2nd 

;; size = 21 bytes

ret然后您可以使用或退出程序int 20h。

这是 NASM 语法；如果您的汇编程序不喜欢.loop，请将其更改为其他内容。（NASM 不允许2:作为本地标签，所以无论如何我都必须选择不同的名称。）我在 Linux 上测试了这个单步执行，以确保循环分支被执行一次，并且当我在 AH/AL 中获得正确的值时int 10h达到了。（我用 NOP 替换它，因为我实际上将它构建到一个 32 位静态可执行文件中，因此我可以轻松地在 GDB 中单步执行它，而不会弄乱过时的 16 位开发设置。字节数来自组装为 16-一点，当然。）

为了速度，只需复制 cmp/sbb/das/int 10h 只需几个字节，节省dec/ jpe。（就像 7 个字节而不是 dec/jpe 的 3 个字节）。无论哪种方式，第一次打印后的 xchg / AND 都是必需的。

采取的分支花费 16 个周期，这将避免xchg/ and（3 个字节 / 7 个周期）的第二次冗余/无用执行，以及循环开销。

你要求小（在 8086 上速度快），所以这就是我所做的。这牺牲了其他一切，包括可读性，以节省字节。但这就是在汇编中打代码的乐趣！

不幸的是，它也绝对不像你在标题中要求的那样简单。 更简单的可能会使用查找表，也许使用 xlatb。这在 8086 上也可能更快，特别是如果你想避免DAS黑客攻击。

另一个可能有助于代码大小（但对性能非常不利）的技巧是aam 16设置 AH= 商 = 前导数字，AL = 余数 = 尾随数字（低）。（注意，与 相反div bl） Displaying Time in Assembly显示了将其与 BIOS int 10h 输出一起使用的示例，用于 2 位十进制数。（通常 AAM 与立即数一起使用10，显然 NEC V20 CPU 忽略立即数并总是除以 10。英特尔 CPU 只对 AL 进行立即除法）。在 8088/8086 上，AAM 需要 83 个周期，类似于div，这基本上就是它的作用。使用 2 次方的硬件除法通常很糟糕。

使用 AAM 16 的版本有 23 个字节，没有使用任何循环（我在寄存器中没有任何常量可以利用，所以mov cx, 1/loop将是 5 个字节，而 cmp/sbb/das/int 10h 总共是 7 个）

比循环版本更慢更大，但“更简单”

     aam   16       ; 83 cycles, 2 bytes   AH= quotient = leading digit   AL = remainder = trailing digit (low)
  ; normally never use div or aam by a power of 2, only for code-size over speed.
     cmp   al, 10        ; 2B 4c  set CF according to digit <= 9
     sbb   al, 69h       ; 2B 4c  read CF, set CF and conditionally set AF
     das                 ; 1B 4c   magic, which happens to work
     xchg  dx, ax        ; 1B 3c    stash low digit in DL

     mov   al, dh        ; 2B 2c    get leading digit
     cmp   al, 10        ; 2B 4c
     sbb   al, 69h       ; 2B 4c    most significant (high) nibble as ASCII hex
     das                 ; 1B 4c
     
     mov   ah, 0Eh       ; 2B 3c BIOS teletype output (of AL), advancing cursor
     int   10h           ; 2B ?
     mov   al, dl        ; 2B 2c  ; get low digit back from DL   xchg  ax, dx breaks AH callnum
     int   10h           ; 2B
; size=23B

我想知道我是否可以将int 21h / AH=2来自 DL 的输入用于其中一个输出？这将需要更改 AH，但也许可以为第二个输出完成。不幸的是，DOS 调用在 AL 上进行，将其设置为打印的字符。（例如，使用这个 int 10h 调用）。

有关的：

于 2021-05-05T15:07:48.360 回答