crc_tables_generate.c

#if 0
    cc --std=c23 "$0" -O3 -o "$0.out"
    ./"$0.out"
    rm "$0.out"
    exit
#endif
 
#include <string.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <ctype.h>
 
struct crc_details {
    const char *name;
    uint8_t bits;
    uint64_t polynomial;
    bool reflect;
};
 
const char *capitalise(const char *str) {
    static char ret[64];
    int i = 0;
    while (i < 64 && i < strlen(str)) {
        ret[i] = toupper(str[i]);
        i++;
    }
    ret[i] = '\0';
    return ret;
}
 
#define TABLE_LEN(details) ((details).bits >= 8 ? 256u : 1u << (details).bits)
#define MASK(details) ((details).bits == 64 ? ~UINT64_C(0) : (UINT64_C(1) << (details).bits) - UINT64_C(1))
#define HIGH_BIT(details) (UINT64_C(1) << ((details).bits - 1))
#define HIGH_BYTE_OFFSET(details) ((details).bits - 8)
#define TYPE_NAME(details) (\
    (details).bits > 32 ? "uint64_t" :\
    (details).bits > 16 ? "uint32_t" :\
    (details).bits > 8  ? "uint16_t" :\
    "uint8_t"\
)
#define LITERAL_WRAPPER(details) (\
    (details).bits > 32 ? "UINT64_C" :\
    (details).bits > 16 ? "UINT32_C" :\
    (details).bits > 8  ? "UINT16_C" :\
    "UINT8_C"\
)
 
uint64_t reflect(const uint64_t n, const uint8_t bits) {
    uint64_t r = 0;
    for (uint8_t i = 0; i < bits; i++) {
        r |= (n >> i & 1) << (bits - i - 1);
    }
    if (bits == 64)
        return r;
    return r & ((UINT64_C(1) << bits) - 1);
}
void table_gen(uint64_t *table, const struct crc_details details) {
    const uint64_t polynomial = details.polynomial & MASK(details);
 
    uint64_t crc;
    for (uint64_t i = 0; i < TABLE_LEN(details); i++) {
        if (details.reflect)
            crc = reflect(i, details.bits);
        else
            crc = i << HIGH_BYTE_OFFSET(details);
 
        for (int bit = 0; bit < 8; bit++) {
            if (crc & HIGH_BIT(details))
                crc = crc << 1 ^ polynomial;
            else
                crc <<= 1;
        }
 
        if (details.reflect)
            table[i] = reflect(crc, details.bits);
        else
            table[i] = crc & MASK(details);
    }
}
void power_table_gen(uint64_t *table, uint8_t bits, const struct crc_details details) {
    uint64_t power = (details.bits <= 8) ? details.polynomial : 0x100;
    for (uint8_t i = 0; i < bits; i++) {
        table[i] = power;
        uint64_t n = power, res = 0;
        for (uint64_t j = 0; j < details.bits; j++) {
            if (power & (UINT64_C(1) << j))
                res ^= n;
            if (n & HIGH_BIT(details))
                n = (n << 1) ^ details.polynomial;
            else
                n <<= 1;
            n &= MASK(details);
        }
        power = res;
    }
}
void inverse_table_gen(uint64_t *table, const struct crc_details details) {
    // I gave up here.
    // There are some optimisations to be had for other crc manipulation methods,
    // but they are not implemented in libclod yet (probably never).
}
void write_details(const struct crc_details details) {
    const char *caps = capitalise(details.name);
    printf("#define %s_BITS %d\n", caps,  details.bits);
    printf("#define %s_POLYNOMIAL %s(0x%"PRIX64")\n", caps, LITERAL_WRAPPER(details), details.polynomial);
    printf("#define %s_NORMALISED_POLYNOMIAL %s(0x%"PRIX64")\n",
        caps, LITERAL_WRAPPER(details), details.reflect ? reflect(details.polynomial, details.bits) : details.polynomial);
    printf("#define %s_REFLECTED %s\n", caps, details.reflect ? "true" : "false");
}
void write_table(const uint64_t *table, size_t table_len, const char *suffix, const struct crc_details details) {
    printf("static constexpr %s %s_%s[%"PRIu64"] = {\n\t", TYPE_NAME(details), details.name, suffix, (uint64_t)table_len);
    for (size_t i = 0; i < table_len; i++) {
        printf("%s(0x%" PRIX64 "),", LITERAL_WRAPPER(details), table[i]);
        if (i != table_len - 1) {
            if (i%4 == 3) {
                printf("\n\t");
            } else {
                printf(" ");
            }
        }
    }
    printf("\n};\n");
}
int main() {
    const struct crc_details details[] = {
        {
            .name = "crc64",
            .bits = 64,
            .polynomial = UINT64_C(0x42F0E1EBA9EA3693),
            .reflect = false
        },
        {
            .name = "crc32",
            .bits = 32,
            .polynomial = UINT64_C(0x1EDC6F41),
            .reflect = true
        },
        {
            .name = "crc24",
            .bits = 24,
            .polynomial = UINT64_C(0x864CFB),
            .reflect = false
        },
        {
            .name = "crc16",
            .bits = 16,
            .polynomial = UINT64_C(0x1021),
            .reflect = true
        },
        {
            .name = "crc8",
            .bits = 8,
            .polynomial = UINT64_C(0x07),
            .reflect = false
        }
    };
    constexpr size_t details_len = sizeof(details)/sizeof(details[0]);
    uint64_t table[256];
 
    printf("// generated by "__FILE__"\n");
    printf("#ifndef LIBCLOD_CRC_TABLES_H\n");
    printf("#define LIBCLOD_CRC_TABLES_H\n");
    printf("#include <stdint.h>\n\n");
    for (unsigned i = 0; i < details_len; i++) {
        write_details(details[i]);
 
        table_gen(table, details[i]);
        write_table(table, 256, "table", details[i]);
 
        power_table_gen(table, 64, details[i]);
        write_table(table, 64, "power_table", details[i]);
 
        if (i != details_len - 1) printf("\n");
    }
    printf("#endif\n");
}