Наиболее эффективная формула для распаковки 16-битного BCD? (например, от 0x1234 до 0x01020304)

Question

Есть ли хитрость для эффективной распаковки 16-битного упакованного номера BCD?

Для этого по пешеходному пути требуется 10 операций (3 смены, 4 AND и 3 OR или ADD):

x = (bcd & 0xF000) << 12
  | (bcd & 0x0F00) <<  8
  | (bcd & 0x00F0) <<  4
  | (bcd & 0x000F)

При многоканальном ADD / OR критическая длина пути составит 3 но эти операции, как правило, являются двоичными, и поэтому большинство процессоров будут искать критический путь длиной 4.

Может ли это быть сделано более эффективно?

Примечание: для некоторых целей это может быть одинаково полезно, если некоторую перестановку кусочков можно распаковать особенно эффективно, например, если слово, которое нужно распаковать, происходит из справочной таблицы, над созданием которой у меня есть полный контроль (так что я могу прикрепить каждый ди git куда угодно Я хочу). Целью использования упакованного вместо распакованного BCD в этом случае было бы вдвое уменьшить нагрузку на память и избежать превышения размера кэша L1, снимая некоторую нагрузку с перенасыщенной подсистемы памяти, увеличивая нагрузку на ALU ЦП.

Например, если я переставлю цифры как 0x1324, то простое обратное чередование даст 0x01020304:

x = ((bcd << 12) | bcd) & 0x0F0F0F0F

Это всего три операции с критической длиной пути 3, что значительно лучше, чем в исходной версии ...

Answer 1

Вот альтернативный способ, с меньшим количеством операций, но более длинным критическим путем, основанный на двоичном разложении расстояния перемещения полуба (перемещение полуба, которые перемещаются на 8 или 12 шагов вместе на 8, перемещение полубайта, которые перемещают расстояние 4 или 12 вместе на 4).

x = bcd
x = ((x & 0xFF00) << 8) | (x & 0xFF)
x = ((x & 0x00F000F0) << 4) | (x & 0x000F000F)

Например:

// start
0000ABCD
// move A and B by 8
00AB00CD
// move A and C by 4
0A0B0C0D

Answer 2

Наиболее эффективным решением будет машинная спецификация c, поскольку разные ISA имеют разные возможности, когда дело доходит до работы с непосредственными константами или комбинирования сдвигов с операциями ALU. Вот альтернативная реализация с хорошим параллелизмом на уровне команд, который может превосходить на платформах с очень быстрым умножением целых чисел. Целочисленное умножение часто полезно для алгоритмов перестановки битов, выполняя несколько операций сложения-добавления параллельно.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/* reference implementation */
uint32_t bcd_spread_1 (uint32_t a)
{
    return (((a & 0xF000) << 12) |
            ((a & 0x0F00) <<  8) |
            ((a & 0x00F0) <<  4) |
            ((a & 0x000F) <<  0));
}

/* alternative implementation */
uint32_t bcd_spread_2 (uint32_t a)
{
    return ((((a & 0xf0f0) * 0x1010) & 0x0f000f00) |
            (((a & 0x0f0f) * 0x0101) & 0x000f000f));
}

/* BCD addition. Knuth TAOCP 4 */
uint32_t median (uint32_t x, uint32_t y, uint32_t z)
{
    return (x & (y | z)) | (y & z);
}

uint32_t bcd_add (uint32_t x, uint32_t y)
{
    uint32_t z, u, t;
    z = y + 0x66666666;
    u = x + z;
    t = median (~x, ~z, u) & 0x88888888;
    return u - t + (t >> 2);
}

int main (void)
{
    uint32_t x, y, bcd = 0;
    do {
        x = bcd_spread_1 (bcd);
        y = bcd_spread_2 (bcd);
        if (x != y) {
            printf ("!!!! bcd=%04x x=%08x y=%08x\n", bcd, x, y);
            return EXIT_FAILURE;
        }
        bcd = bcd_add (bcd, 1);
    } while (bcd < 0x10000);
    return EXIT_SUCCESS;
}

Answer 3

Используйте алгоритм DoubleDabble .