# Routine for convert decimal digits to Densely Packed Decimal

I've written an amd64 assembly routine (in gas syntax using the System V calling convention) to convert three decimal digits to Densely packed decimal because I wasn't satisfied by the performance of the assembly generated by gcc and clang for all implementations of the conversion I could think of. Here is the code:

    .section .text
.type decimal2dpd,@function
.globl decimal2dpd

# convert three digits abc to DPD
# SysV calling convention: a in edi, b in esi, c in edx
# assumes 0 <= a, b, c < 10
.align 8
decimal2dpd:
mov %esi,%eax
shl $4,%eax or %edx,%eax and$0021,%eax
shl $7,%edi or %edi,%eax and$016,%edx
btr $10,%eax # at this point, eax = (a & 7) << 4 | (b & 1) << 4 | (c & 1) and CF is set if a > 7 # and edi is free for use jc .Lagt7 # here a < 8 shl$4,%esi
btr 7,%esi jc .Lbgt7 # here a < 8 and b < 8 or %esi,%eax or %edx,%eax ret .align 8 .Lbgt7: # here a < 8 and b > 7 or0012,%eax
shl $4,%edx mov$0104,%edi
btr 7,%edx cmovc %edi,%edx or %edx,%eax ret .align 8 .Lagt7: # here a > 7 shl7,%edx # eax = (a & 1 | c & 6) << 7 | (b & 1) << 5 | (c & 1)
or %edx,%eax    # now eax[10] is set if c > 7
btr $10,%eax jc .Lcgt7 # here a > 7 and c < 8 or$0014,%eax
shl $4,%esi mov$0002,%edi
btr 7,%esi cmovc %edi,%esi or %esi,%eax ret .align 8 .Lcgt7: # here a > 7 and c > 7 and016,%esi
or $0056,%eax shl$7,%esi
mov $0100,%edi btr$10,%esi
cmovc %edi,%esi
or %esi,%eax
ret
.size decimal2dpd,.-decimal2dpd


This routine is roughly 10% faster than the C code implementing roughly the same algorithm shown below. I would like to know if there is any obvious or less obvious way to improve this routine for better performance.

extern unsigned
decimal2dpd(unsigned a, unsigned b, unsigned c)
{
unsigned result = c & 1 | (a & 7) << 7;

if (a < 8) {
if (b < 8)
return result | b << 4 | c;
else
return result | (c > 7 ? 0104 : (c & 6) << 4) | (b & 1) << 4 | 0012;
} else {
result |= (b & 1) << 4;

if (c < 8)
return result | (c & 6) << 7 | (b > 7 ? 0002 : b << 4) | 0014;
else
return result | (b > 7 ? 0100 : (b & 6) << 7) | 0056;
}
}


I especially believe that the fact that all arguments are in the range 0–9 can be exploited further, I didn't found a way to do so though (except for a).

Using a tiny (24 byte) lookup table and some multiplication trickery, I was able to make the following implementation (roughly 1.5 times as fast as the original):

        .section .text
.type bcd2dpd_mul,@function
.globl bcd2dpd_mul

# convert BCD to DPD with multiplication tricks
# input abcd efgh iklm in edi
.align 8
bcd2dpd_mul:
mov %edi,%eax           #   = 0000 abcd efgh iklm
shl %al                 #   = 0000 abcd fghi klm0
shr %eax                #   = 0000 0abc dfgh iklm
test $0x880,%edi # fast path for a = e = 0 jz 1f and$0x888,%edi         #   = 0000 a000 e000 i000
imul $0x0490,%di # = aei0 0000 0000 0000 mov %eax,%esi and$0x66,%esi          # q = 0000 0000 0fg0 0kl0
shr $13,%edi # u = 0000 0000 0000 0aei imul tab-8(,%rdi,4),%si # v = q * tab[u-2][0] and$0x397,%eax         # r = 0000 00bc d00h 0klm
xor %esi,%eax           # w = r ^ v
or tab-6(,%rdi,4),%ax   # x = w | tab[u-2][1]
and \$0x3ff,%eax         #   = 0000 00xx xxxx xxxx
1:      ret

.size bcd2dpd_mul,.-bcd2dpd_mul

.section .rodata
.align 4
tab:
.short 0x0011 ; .short 0x000a
.short 0x0000 ; .short 0x004e
.short 0x0081 ; .short 0x000c
.short 0x0008 ; .short 0x002e
.short 0x0081 ; .short 0x000e
.short 0x0000 ; .short 0x006e
.size tab,.-tab


which was optimized further with help from the folks on Stackoverflow.