SIMD algorithm

Instruction PSHUFB does parallel lookup from 16-byte array stored in an XMM register — this is exactly what bin to hex conversion needs.

Code snippet showing the idea:

movdqa    (%eax), %xmm0 ; xmm0 = {0xba, 0xdc, 0xaf, 0xe8, ...}
movdqa     %xmm0, %xmm1 ; xmm1 -- bits 4..7 shifted 4 positions right
psrlw         $4, %xmm1 ; xmm1 = {0xad, 0xca, 0xfe, 0x80, ...}
punpcklbw  %xmm0, %xmm1 ; xmm0 = {0xba, 0xad, 0xdc, 0xca, 0xaf, 0xfe, 0xe8, 0x80, ...}
                        ; MASK = packed_byte(0x0f)
pand        MASK, %xmm1 ; xmm0 = {0xb0, 0xa0, 0xd0, 0xc0, 0xa0, 0xf0, 0xe0, 0x80, ...}
                        ;      -- bits 0..3
movdqa HEXDIGITS, %xmm0 ; HEXDIGITS = {'0', '1', '2', '3', ..., 'a', 'b', 'c', 'd', 'e', 'f'}
pshufb     %xmm1, %xmm0 ; xmm0 = {'b', 'a', 'd', 'c', 'a', 'f', 'e', '8', ...}

Tests

hexprint.c is a test program that compares speed of presented method with three other lookup-based methods:

• std — standard 16-byte lookup (2 lookups per byte)
• std2 — 256-byte lookup (1 lookup per byte)
• std3 — 2 x 256-byte lookups (2 lookups per 2 bytes)

In a single iteration 100 x 16 bytes are decoded, and the number of iterations is 100000.