Упаковать / распаковать массив из 64 bools в uint64 - PullRequest
Новая
       44

Упаковать / распаковать массив из 64 bools в uint64

3 голосов
/ 03 апреля 2020

Я сталкивался с этим ответом .

Но я столкнулся с двумя проблемами, я не уверен, как адаптировать его для упаковки 64 бит (см. Ниже), и я могу я не могу распаковать их.

Вот что у меня есть для упаковки: 

const int i = 1;
#define is_bigendian() ((*(char *) &i) == 0)

#define MAGIC (is_bigendian() ? 0x0102040810204080 : 0x8040201008040201)

inline uint8_t pack8b(bool *a) {
    uint64_t t = *((uint64_t *) a);
    return (MAGIC * t >> 56) & 0xFF;
}

uint32_t pack32b(bool *a) {
    return (pack8b(a + 0) << 24) | (pack8b(a + 8) << 16) |
           (pack8b(a + 16) << 8) | (pack8b(a + 24) << 0);
}

uint64_t pack64b(bool *a) {
    return ((uint64_t) pack32b(a) << 32) | pack32b(a + 32);
}

РЕДАКТИРОВАТЬ: Вот то, что у меня так далеко, что работает как шарм, я открыт для предложений по улучшению производительности: 

uint64_t MAGIC() {
    static const int i = 1;
    // Takes of little / big endian
    bool bigEndian = ((*(char *) &i) == 0);
    return bigEndian ? 0x0102040810204080 : 0x8040201008040201;
}

uint8_t pack8b(bool *a) {
    uint64_t t = *((uint64_t *) a);
    return (MAGIC() * t >> 56) & 0xFF;
}

uint16_t pack16b(bool *a) {
    return ((uint16_t) pack8b(a + 0) << 8) | (pack8b(a + 8) << 0);
}

uint32_t pack32b(bool *a) {
    return ((uint32_t) pack16b(a + 0) << 16) | (pack16b(a + 16) << 0);
}

uint64_t pack64b(bool *a) {
    return ((uint64_t) pack32b(a + 0) << 32) | (pack32b(a + 32) << 0);
}

void unpack8b(bool *a, uint8_t v) {
    uint64_t mask = 0x8080808080808080ULL;
    *((uint64_t *) a) = ((MAGIC() * v) & mask) >> 7;
}

void unpack16b(bool *a, uint16_t v) {
    unpack8b(a + 0, v >> 8);
    unpack8b(a + 8, v >> 0);
}

void unpack32b(bool *a, uint32_t v) {
    unpack16b(a + 0, v >> 16);
    unpack16b(a + 16, v >> 0);
}

void unpack64b(bool *a, uint64_t v) {
    unpack32b(a + 0, v >> 32);
    unpack32b(a + 32, v >> 0);
}

Ответы [ 2 ]

3 голосов
/ 03 апреля 2020

Ваше решение работает для меня. Я проверил его с помощью g cc на tio: Попробуйте онлайн!

Простейшей функцией для распаковки uint64_t будет: 

void unpack64b(uint64_t num, bool* bit_field) {
    for (int i = 63; 0 <= i; i--) {
        bit_field[i] = num & 1;
        num = num >> 1;
    }
}

Если bit_field инициализирован для всех нулей, то возможен досрочный выход: 

void unpack64b(uint64_t num, bool* bit_field) {
    for (int i = 63; num > 0; i--) {
        bit_field[i] = num & 1;
        num = num >> 1;
    }
}

Для упаковки для 32 и 64 бит, не следует ли это также знать о порядке байтов кодирование

2 голосов
/ 03 апреля 2020

Я не могу разобраться, распаковывая их.

Для начала сконцентрируйся на простой итерации битов, сделай самый простой способ, который работает. Для меня это были просто простые назначения массива с битами и маской: 

#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

static const int i = 1;
uint64_t MAGIC(void) {
    return ((*(const char *)&i) == 0) ? 0x0102040810204080ull : 0x8040201008040201ull;
}

void unpack8b(bool a[8], uint8_t v) {
    if (((*(const char *)&i) == 0)) {
        a[0] = v & 0x01;
        a[1] = v & 0x02;
        a[2] = v & 0x04;
        a[3] = v & 0x08;
        a[4] = v & 0x10;
        a[5] = v & 0x20;
        a[6] = v & 0x40;
        a[7] = v & 0x80;
    } else {
        a[7] = v & 0x01;
        a[6] = v & 0x02;
        a[5] = v & 0x04;
        a[4] = v & 0x08;
        a[3] = v & 0x10;
        a[2] = v & 0x20;
        a[1] = v & 0x40;
        a[0] = v & 0x80;
    }
}

void unpack16b(bool a[16], uint16_t v) {
    unpack8b(&a[0], v >> 8);
    unpack8b(&a[8], v);
}

void unpack32b(bool a[32], uint32_t v) {
    unpack16b(&a[0], v >> 16);
    unpack16b(&a[16], v);
}

void unpack64b(bool a[64], uint64_t v) {
    unpack32b(&a[0], v >> 32);
    unpack32b(&a[32], v);
}

uint8_t pack8b(bool a[8]) {
    static_assert(sizeof(bool) == 1, "");
    static_assert(sizeof(uint64_t) == 8, "");
    static_assert(CHAR_BIT == 8, "");
    uint64_t t;
    memcpy(&t, a, sizeof(t));
    return (MAGIC() * t >> 56) & 0xFF;
}

uint16_t pack16b(bool a[16]) {
    return pack8b(&a[0]) << 8 | pack8b(&a[8]);
}

uint32_t pack32b(bool a[32]) {
    return (uint32_t)pack16b(&a[0]) << 16 | pack16b(&a[16]);
}

uint64_t pack64b(bool a[64]) {
    return ((uint64_t)pack32b(&a[0]) << 32) | pack32b(&a[32]);
}

int main() {
    _Alignas(uint64_t) bool a[64];
    for (int i = 0; i < 64; ++i) {
        a[i] = rand() % 2;
    }

    for (int i = 0; i < 64; ++i) printf("%d%s", a[i], !((i+1)%8)?" ":"");
    printf("\n");

    uint64_t v = pack64b(a);
    printf("%llx\n", v);

    memset(a, -1, sizeof(a));
    unpack64b(a, v);

    for (int i = 0; i < 64; ++i) printf("%d%s", a[i], !((i+1)%8)?" ":"");
    printf("\n");
}

Выходы: 

10111100 11010110 00001011 00011110 00111010 11110100 10101001 00011101 
bcd60b1e3af4a91d
10111100 11010110 00001011 00011110 00111010 11110100 10101001 00011101

Обратите внимание, что когда int на платформе имеет 16 бит, (pack8b(a + 0) << 24) в вашем коде неопределённое поведение. Приведите его к типу с большим количеством битов, чем 24 (uint32_t)pack8b(a + 0) << 24, прежде чем переходить в режим повышенной безопасности.

...