assembly - 如何将二进制整数转换为十六进制字符串？

Question

给定寄存器中的数字(二进制​​整数)，如何将其转换为十六进制ASCII数字字符串？ (即，将其序列化为文本格式。)

可以将数字存储在内存中或即时打印，但是通常一次存储在内存中并进行打印通常会更有效。 (您可以修改存储的循环以一次打印一次。)

我们能否与SIMD并行有效地处理所有半字节？ (SSE2或更高版本？)

Answer 1

相关:16-bit version，它将1字节转换为2个十六进制数字，您可以将其打印或存储到缓冲区中。 Converting bin to hex in assembly还有另一个16位版本，答案的一半包含大量文本解释，涵盖了问题的int-> hex-string部分。
如果针对代码大小而不是速度进行优化，则可以使用a hack using DAS that saves a few bytes。

16是2 的幂。与小数或其他不是2的幂的基数不同，我们不需要除法，我们可以首先提取最高有效的数字(即按打印顺序)。否则，我们只能先获取最低有效位(其值取决于数字的所有位)，然后我们必须倒退:有关非2幂的底数，请参见How do I print an integer in Assembly Level Programming without printf from the c library?。
每个4位位组映射到一个十六进制数字。我们可以使用移位或旋转以及AND掩码将输入的每个4位块提取为4位整数。
不幸的是，ASCII字符集(http://www.asciitable.com/)中0..9 a..f十六进制数字不连续。我们要么需要条件行为(分支或cmov)，要么可以使用查找表。
查找表通常对于指令计数和性能而言是最有效的，因为我们要反复进行此操作。现代CPU具有非常快的L1d高速缓存，这使得附近字节的重复加载非常便宜。流水线/无序执行隐藏了L1d缓存负载的〜5个周期延迟。

;; NASM syntax, i386 System V calling convention
global itohex      ; inputs: char* output,  unsigned number
itohex:
    push   edi           ; save a call-preserved register for scratch space
    mov    edi, [esp+8]  ; out pointer
    mov    eax, [esp+12] ; number

    mov    ecx, 8        ; 8 hex digits, fixed width zero-padded
.digit_loop:             ; do {
    rol    eax, 4          ; rotate the high 4 bits to the bottom

    mov    edx, eax
    and    edx, 0x0f       ; and isolate 4-bit integer in EDX

    movzx  edx, byte [hex_lut + edx]
    mov    [edi], dl       ; copy a character from the lookup table
    inc    edi             ; loop forward in the output buffer

    dec    ecx
    jnz    .digit_loop   ; }while(--ecx)

    pop    edi
    ret

section .rodata
    hex_lut:  db  "0123456789abcdef"

为了适应x86-64，调用约定将在寄存器而不是堆栈中传递args，例如x86-64 System V(非Windows)的RDI和ESI。只需从堆栈中卸下要加载的零件，然后更改循环以使用ESI而不是EAX。 (并使寻址模式为64位。您可能需要将 hex_lut地址LEA到循环外部的寄存器中；请参阅 this和 this)。
此版本转换为带有前导零的十六进制。如果要删除它们，则输入上的 bit_scan(input)/4(例如 lzcnt或 __builtin_clz)，或在输出ASCII字符串上的SIMD比较-> pmovmksb-> tzcnt会告诉您您有多少个0位数(因此您可以从第一个非零)。或从低位半字节开始转换并向后工作，直到右移将值设为零时停止转换，如使用cmov而不是查找表的第二个版本所示。
在BMI2( shrx/ rorx)之前，x86缺少复制和移位指令，因此就地旋转然后复制/AND很难。现代的x86(Intel和AMD)具有轮换的1个周期延迟( https://agner.org/optimize/和 https://uops.info/)，因此此循环承载的依赖链不会成为瓶颈。 (循环中有太多指令，即使在5宽Ryzen上，每个迭代甚至无法运行1个周期。)
我使用 mov ecx,8和 dec ecx/jnz来提高可读性；顶部的 lea ecx, [edi+8]和作为循环分支的 cmp edi, ecx / jb .digit_loop较小的总体计算机代码大小，并且在更多CPU上效率更高。 dec/jcc宏融合到单个uop中仅在Intel Sandybridge系列上发生； AMD仅将jcc与cmp或测试融合。与Intel一样，这种优化可使Ryzen前端的功耗降低到7ups，这还远远超出了1个周期内可以发布的范围。
脚注1:我们可以在移位之前使用SWAR(寄存器内的SIMD)执行AND:x & 0x0f0f0f0f低位半字节，而shr(x,4) & 0x0f0f0f0f高位半字节，然后通过交替处理每个寄存器中的字节来有效地展开。 (没有任何等效的 punpcklbw或将整数映射到不连续的ASCII代码的有效方法，我们仍然只需要分别处理每个字节。但是我们可以展开字节提取并读取AH然后读取AL(使用 movzx)为了保存移位指令，读取高8位寄存器会增加延迟，但我认为在当前CPU上并不会花费额外的成本。在英特尔CPU上写入高8位寄存器通常是不好的:读取CPU会增加额外的合并uop。完整的寄存器，并且有一个前端延迟来插入它。因此，通过改组寄存器来扩大存储范围可能不好。在不能使用XMM regs，但是可以使用BMI2的内核代码中， pdep可以将半字节扩展为字节但这可能比掩盖2种方法还差。)
测试程序:

// hex.c   converts argv[1] to integer and passes it to itohex
#include <stdio.h>
#include <stdlib.h>

void itohex(char buf[8], unsigned num);

int main(int argc, char**argv) {
    unsigned num = strtoul(argv[1], NULL, 0);  // allow any base
    char buf[9] = {0};
    itohex(buf, num);   // writes the first 8 bytes of the buffer, leaving a 0-terminated C string
    puts(buf);
}

编译:

nasm -felf32 -g -Fdwarf itohex.asm
gcc -g -fno-pie -no-pie -O3 -m32 hex.c itohex.o

测试运行:

$ ./a.out 12315
0000301b
$ ./a.out 12315123
00bbe9f3
$ ./a.out 999999999
3b9ac9ff
$ ./a.out 9999999999   # apparently glibc strtoul saturates on overflow
ffffffff
$ ./a.out 0x12345678   # strtoul with base=0 can parse hex input, too
12345678

替代实现:
有条件而不是查找表:需要更多说明，并且可能会更慢。但是它不需要任何静态数据。
可以用分支代替 cmov来完成，但这在大多数情况下甚至会更慢。 (假设0..9和a..f数字的随机混合，预测效果会不好。) https://codegolf.stackexchange.com/questions/193793/little-endian-number-to-string-conversion/193842#193842显示了针对代码大小进行了优化的版本。 (除了开头的 bswap以外，它是正常的uint32_t->十六进制，填充为零。)
这个版本很有趣，它从缓冲区的末尾开始，并递减指针。 (循环条件使用指针比较。)如果您不希望前导零，则可以使它在EDX变为零后停止，并使用EDI + 1作为数字的开头。
读者可以使用 cmp eax,9/ ja代替 cmov作为练习。它的16位版本可以使用不同的寄存器(例如BX作为临时寄存器)来仍然允许 lea cx, [bx + 'a'-10]复制和添加。或者，如果要避免使用 add与不支持P6扩展的古老CPU兼容，或者只是 cmp/ jcc和 cmov。

;; NASM syntax, i386 System V calling convention
itohex:   ; inputs: char* output,  unsigned number
itohex_conditional:
    push   edi             ; save a call-preserved register for scratch space
    push   ebx
    mov    edx, [esp+16]   ; number
    mov    ebx, [esp+12]   ; out pointer

    lea    edi, [ebx + 7]   ; First output digit will be written at buf+7, then we count backwards
.digit_loop:                ; do {
    mov    eax, edx
    and    eax, 0x0f            ; isolate the low 4 bits in EAX
    lea    ecx, [eax + 'a'-10]  ; possible a..f value
    add    eax, '0'             ; possible 0..9 value
    cmp    ecx, 'a'
    cmovae eax, ecx             ; use the a..f value if it's in range.
                                ; for better ILP, another scratch register would let us compare before 2x LEA,
                                ;  instead of having the compare depend on an LEA or ADD result.

    mov    [edi], al        ; *ptr-- = c;
    dec    edi

    shr    edx, 4

    cmp    edi, ebx         ; alternative:  jnz on flags from EDX to not write leading zeros.
    jae    .digit_loop      ; }while(ptr >= buf)

    pop    ebx
    pop    edi
    ret

我们可以使用2x lea + cmp/cmov在每次迭代中公开更多的ILP。 cmp和两个LEA仅取决于半字节值， cmov占用了所有这三个结果。但是在迭代过程中有很多ILP，只有 shr edx,4和指针递减作为循环承载的依赖项。我可以通过安排节省1个字节的代码大小，因此可以使用 cmp al, 'a'或其他东西。和/或 add al,'0'(如果我不关心与EAX分开重命名AL的CPU)。
测试用例，通过使用十六进制数字同时包含 9和 a的数字来检查byby错误。

$ nasm -felf32 -g -Fdwarf itohex.asm && gcc -g -fno-pie -no-pie -O3 -m32 hex.c itohex.o && ./a.out 0x19a2d0fb
19a2d0fb

带有SSE2，SSSE3，AVX2或AVX512F的SIMD，以及带有AVX512VBMI的〜2条指令
对于SSSE3和更高版本，最好将字节混洗用作半字节查找表。
这些SIMD版本中的大多数都可以使用两个压缩的32位整数作为输入，结果 vector 的低8位和高8位包含单独的结果，可以将这些结果与 movq和 movhps分开存储。
根据您的随机播放控件，这就像将其用于一个64位整数一样。
SSSE3 pshufb并行查找表。无需弄乱循环，我们可以在具有 pshufb的CPU上执行一些SIMD操作来完成此操作。 (SSSE3甚至不是x86-64的基准；它是Intel Core2和AMD Bulldozer的新功能)。
pshufb is a byte shuffle由 vector 控制，而不是由立即数控制(不同于所有早期的SSE1/SSE2/SSE3随机播放)。具有固定的目标和可变的shuffle控件，我们可以将其用作并行查找表，以并行方式执行16x查找(从 vector 中的16个字节的条目表开始)。
因此，我们将整个整数加载到 vector 寄存器中，并通过位移和 punpcklbw 将其半字节解包为字节。然后使用 pshufb将这些半字节映射到十六进制数字。
剩下的是ASCII数字，即XMM寄存器，其最低有效位是寄存器的最低字节。由于x86是低位字节序，因此没有免费的方法可以将它们以相反的顺序存储到内存中，首先是MSB。
我们可以使用额外的 pshufb将ASCII字节重新排序为打印顺序，或者在整数寄存器的输入上使用 bswap(并反转半字节->字节解包)。如果该整数来自内存，则通过 bswap的整数寄存器有点糟(尤其是对于AMD Bulldozer系列)，但是如果您首先在GP寄存器中拥有该整数，那就很好了。

;; NASM syntax, i386 System V calling convention

section .rodata
 align 16
    hex_lut:  db  "0123456789abcdef"
    low_nibble_mask: times 16 db 0x0f
    reverse_8B: db 7,6,5,4,3,2,1,0,   15,14,13,12,11,10,9,8
    ;reverse_16B: db 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

section .text

global itohex_ssse3    ; tested, works
itohex_ssse3:
    mov    eax,  [esp+4]    ; out pointer
    movd   xmm1, [esp+8]    ; number

    movdqa xmm0, xmm1
    psrld  xmm1, 4          ; right shift: high nibble -> low  (with garbage shifted in)
    punpcklbw xmm0, xmm1    ; interleave low/high nibbles of each byte into a pair of bytes
    pand   xmm0, [low_nibble_mask]   ; zero the high 4 bits of each byte (for pshufb)
    ; unpacked to 8 bytes, each holding a 4-bit integer

    movdqa xmm1, [hex_lut]
    pshufb xmm1, xmm0       ; select bytes from the LUT based on the low nibble of each byte in xmm0

    pshufb xmm1, [reverse_8B]  ; printing order is MSB-first

    movq   [eax], xmm1      ; store 8 bytes of ASCII characters
    ret
;; The same function for 64-bit integers would be identical with a movq load and a movdqu store.
;; but you'd need reverse_16B instead of reverse_8B to reverse the whole reg instead of each 8B half

可以将AND掩码和pshufb控件打包到一个16字节的 vector 中，类似于下面的 itohex_AVX512F。

AND_shuffle_mask: times 8 db 0x0f       ; low half: 8-byte AND mask
                   db 7,6,5,4,3,2,1,0   ; high half: shuffle constant that will grab the low 8 bytes in reverse order

将其加载到 vector 寄存器中，并将其用作AND掩码，然后将其用作 pshufb控件，以相反的顺序捕获低8个字节，将其保留为高8。最后的结果(8个ASCII十六进制数字)将在XMM寄存器的上半部分，因此请使用 movhps [eax], xmm1。在Intel CPU上，这仍然只是1个融合域uop，因此它与 movq一样便宜。但是在Ryzen上，它需要在商店顶部进行洗牌。另外，如果您要并行转换两个整数或一个64位整数，则此技巧没有用。
SSE2，保证在x86-64 中可用:
如果没有SSSE3 pshufb，我们需要依靠标量 bswap来使字节以正确的打印顺序排列，而 punpcklbw另一种方法是首先与每对的高半字节交织。
代替表查找，我们只需添加 '0'，并为大于9的数字添加另一个 'a' - ('0'+10)(将它们放入 'a'..'f'范围)。 SSE2的压缩字节比较大于 pcmpgtb 。加上按位AND，这就是我们有条件添加的全部内容。

itohex:             ; tested, works.
global itohex_sse2
itohex_sse2:
    mov    edx,  [esp+8]    ; number
    mov    ecx,  [esp+4]    ; out pointer
    ;; or enter here for fastcall arg passing.  Or rdi, esi for x86-64 System V.  SSE2 is baseline for x86-64
    bswap  edx
    movd   xmm0, edx

    movdqa xmm1, xmm0
    psrld  xmm1, 4          ; right shift: high nibble -> low  (with garbage shifted in)
    punpcklbw xmm1, xmm0    ; interleave high/low nibble of each byte into a pair of bytes
    pand   xmm1, [low_nibble_mask]   ; zero the high 4 bits of each byte
    ; unpacked to 8 bytes, each holding a 4-bit integer, in printing order

    movdqa  xmm0, xmm1
    pcmpgtb xmm1, [vec_9]
    pand    xmm1, [vec_af_add] ; digit>9 ?  'a'-('0'+10)  :  0
    
    paddb   xmm0, [vec_ASCII_zero]
    paddb   xmm0, xmm1      ; conditional add for digits that were outside the 0..9 range, bringing them to 'a'..'f'

    movq   [ecx], xmm0      ; store 8 bytes of ASCII characters
    ret
    ;; would work for 64-bit integers with 64-bit bswap, just using movq + movdqu instead of movd + movq


section .rodata
align 16
    vec_ASCII_zero: times 16 db '0'
    vec_9:          times 16 db 9
    vec_af_add:     times 16 db 'a'-('0'+10)
    ; 'a' - ('0'+10) = 39 = '0'-9, so we could generate this from the other two constants, if we were loading ahead of a loop
    ; 'A'-('0'+10) = 7 = 0xf >> 1.  So we could generate this on the fly from an AND.  But there's no byte-element right shift.

    low_nibble_mask: times 16 db 0x0f

这个版本比大多数其他版本需要更多的 vector 常量。 4x 16字节为64字节，可容纳在一个缓存行中。您可能想在第一个 vector 之前添加 align 64，而不仅仅是 align 16，因此它们都来自同一缓存行。
这甚至可以仅使用MMX来实现，仅使用8字节常数，但是您需要一个 emms，因此这可能仅在没有SSE2或拆分128位的非常老的CPU上是一个好主意。可以分成64位(例如Pentium-M或K8)。在具有消除运动的 vector 寄存器的现代CPU(如Bulldozer和IvyBrige)上，它仅适用于XMM寄存器，不适用于MMX。我确实安排了寄存器的使用，因此第二个 movdqa不在关键路径上，但是我第一次没有这样做。

AVX可以保存 movdqa，但更有趣的是 AVX2，我们可以从较大的输入一次生成32字节的十六进制数字。 2个64位整数或4个32位整数；使用128-> 256位广播负载将输入数据复制到每个通道中。从那里开始，带有从每个128位通道的低半或高半部分读取的控制 vector 的车道内 vpshufb ymm应该为您设置低字节中的低64位输入的半字节，而对于低位通道中的零字节则为零。高电平通道中的高64位输入解压缩。
或者，如果输入数字来自不同的来源，那么 vinserti128在某些CPU上可能值得，而仅执行单独的128位操作。

AVX512VBMI (Cannonlake/IceLake，在Skylake-X中不存在)具有2寄存器字节混洗 vpermt2b ，可以将 puncklbw交织与字节反转结合在一起。 甚至更好，我们有 VPMULTISHIFTQB ，它可以从源的每个qword提取8个未对齐的8位位域。
我们可以使用它来将所需的半字节直接提取到所需的顺序中，从而避免了单独的右移指令。 (它仍然带有垃圾位，但是 vpermb忽略高垃圾。)
要将其用于64位整数，请使用广播源和multishift控件，该控件将在 vector 底部的输入qword的高32位解压缩，在 vector 的顶部解压32位。 (假设小端输入)
要将其用于64位以上的输入，请使用vpmovzxdq将每个输入dword零​​扩展为qword ，并为 vpmultishiftqb设置每个qword中具有相同的28,24，...，4,0控制模式。 (例如，从输入的256位 vector 或四个dword-> ymm reg生成输出的zmm vector ，以避免时钟速度限制和实际运行512位AVX512指令的其他影响。)
注意，更宽的 vpermb使用每个控制字节的5或6位，这意味着您需要将hexLUT广播到ymm或zmm寄存器，或在内存中重复。

itohex_AVX512VBMI:                         ;  Tested with SDE
    vmovq          xmm1, [multishift_control]
    vpmultishiftqb xmm0, xmm1, qword [esp+8]{1to2}    ; number, plus 4 bytes of garbage.  Or a 64-bit number
    mov    ecx,  [esp+4]            ; out pointer
   
     ;; VPERMB ignores high bits of the selector byte, unlike pshufb which zeroes if the high bit is set
     ;; and it takes the bytes to be shuffled as the optionally-memory operand, not the control
    vpermb  xmm1, xmm0, [hex_lut]   ; use the low 4 bits of each byte as a selector

    vmovq   [ecx], xmm1     ; store 8 bytes of ASCII characters
    ret
    ;; For 64-bit integers: vmovdqa load [multishift_control], and use a vmovdqu store.

section .rodata
align 16
    hex_lut:  db  "0123456789abcdef"
    multishift_control: db 28, 24, 20, 16, 12, 8, 4, 0
    ; 2nd qword only needed for 64-bit integers
                        db 60, 56, 52, 48, 44, 40, 36, 32

# I don't have an AVX512 CPU, so I used Intel's Software Development Emulator
$ /opt/sde-external-8.4.0-2017-05-23-lin/sde -- ./a.out 0x1235fbac
1235fbac

vpermb xmm不能穿越车道，因为只涉及一个车道(与 vpermb ymm或zmm不同)。但是不幸的是，在CannonLake( according to instlatx64 results)上，它仍然具有3个周期的延迟，因此 pshufb对于延迟来说会更好。但是 pshufb根据高位有条件地为零，因此需要屏蔽控制 vector 。假设 vpermb xmm只有1 uop，这会使吞吐量变得更糟。在一个循环中，我们可以将 vector 常量保留在寄存器中(而不是内存操作数)，它只保存1条指令，而不是2条指令。
(更新:是的， https://uops.info/确认 vpermb为1 uop，延迟为3c，Cannon Lake和Ice Lake的吞吐量为1c。ICL的 vpshufb xmm/ymm的吞吐量为0.5c)

AVX2可变移位或AVX512F合并掩码可节省交错
使用AVX512F，在将数字广播到XMM寄存器中之后，我们可以使用合并掩码右移一个双字，而另一个双字保持不变。
或我们可以使用AVX2可变移位vpsrlvd来做与完全相同的事情，其移位计数 vector 为 [4, 0, 0, 0]。英特尔Skylake及更高版本具有单码 vpsrlvd; Haswell/Broadwell取多个uops(2p0 + p5)。 Ryzen的 vpsrlvd xmm是1 uop，3c延迟，每2个时钟吞吐量1个。 (比立即轮类更糟糕)。
然后，我们只需要一个单寄存器字节混洗 vpshufb来交织半字节和字节反转。但是，然后您需要一个掩码寄存器中的常数，该常数需要几个指令来创建。在将多个整数转换为十六进制的循环中，这将是更大的胜利。
对于该功能的非循环独立版本，我将两半的一个16字节常量用于不同的事物:上半部分为 set1_epi8(0x0f)，下半部分为8字节的 pshufb控制 vector 。这不会节省很多，因为EVEX广播内存操作数允许 vpandd xmm0, xmm0, dword [AND_mask]{1to4}，只需要4个字节的空间即可存储一个常量。

itohex_AVX512F:       ;; Saves a punpcklbw.  tested with SDE
    vpbroadcastd  xmm0, [esp+8]    ; number.  can't use a broadcast memory operand for vpsrld because we need merge-masking into the old value
    mov     edx, 1<<3             ; element #3
    kmovd   k1, edx
    vpsrld  xmm0{k1}, xmm0, 4      ; top half:  low dword: low nibbles unmodified (merge masking).  2nd dword: high nibbles >> 4
      ; alternatively, AVX2 vpsrlvd with a [4,0,0,0] count vector.  Still doesn't let the data come from a memory source operand.

    vmovdqa xmm2, [nibble_interleave_AND_mask]
    vpand   xmm0, xmm0, xmm2     ; zero the high 4 bits of each byte (for pshufb), in the top half
    vpshufb xmm0, xmm0, xmm2     ; interleave nibbles from the high two dwords into the low qword of the vector

    vmovdqa xmm1, [hex_lut]
    vpshufb xmm1, xmm1, xmm0       ; select bytes from the LUT based on the low nibble of each byte in xmm0

    mov      ecx,  [esp+4]    ; out pointer
    vmovq   [ecx], xmm1       ; store 8 bytes of ASCII characters
    ret

section .rodata
align 16
    hex_lut:  db  "0123456789abcdef"
    nibble_interleave_AND_mask: db 15,11, 14,10, 13,9, 12,8  ; shuffle constant that will interleave nibbles from the high half
                      times 8 db 0x0f              ; high half: 8-byte AND mask