2
\$\begingroup\$

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
    or $0012,%eax
    shl $4,%edx
    mov $0104,%edi
    btr $7,%edx
    cmovc %edi,%edx
    or %edx,%eax
    ret

    .align 8
.Lagt7: # here a > 7
    shl $7,%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
    and $016,%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).

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.