Как использовать gperf для создания хэша для диапазона значений?

Question

У меня есть ряд шестнадцатеричных чисел, как эти

0xabcd****
0xabdc**89
0x****abcd
0xde****ab
# 50 or so more entries like these
# where * is any hex number

Мне нужна хеш-функция, которая будет принимать значение 4 байта и генерировать ответ Y/N для членства.

Я попытался использовать gperf, но, к сожалению, он не интерпретируется * как подстановочный знак. Кто-нибудь сталкивался с этой проблемой раньше? Мой код в C.

Answer 1

Если я могу доверять своей арифметике, каждый **** имеет 16^4 возможных значений, поэтому перечисляются четыре спецификации подстановочных знаков 3 * 16^4 + 16^2 значения - что-то порядка 200 000 - немного вне сферы действия gperf (его документы говорят, что "большой" набор ключей составляет 15 000).

Подстановочные знаки означают для меня регулярные выражения, так почему бы не попробовать это? Вот попытка, которая определяет "4-байтовое значение" как uint32_t и представляет текстовую кодировку такого значения regex(3) техника. Вполне возможно, что это не то, что вы искали, но, как весело было поковыряться, вот и все.

#include <sys/types.h>
#include <regex.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

static regex_t the_re;

int
matcher_init(void)
{
    static const char the_re_string[] = "(abcd....|abdc..89|....abcd|de....ab|"
                                         /* OP's 4, plus 46 more... */
                                         "..d80a..|..7bc5..|c6..514a|..b7585a|"
                                         "4732ecc4|7c22e4da|5a5e..63|....e866|"
                                         "..fdc367|ac....b4|70249edc|..e97e32|"
                                         "....94d8|....fa6c|4591..ff|..e4..67|"
                                         "aab285..|....f81b|15bb22ba|3cf4....|"
                                         "57d3ad86|..bd..1e|..ec67b7|..693aaf|"
                                         "323c..18|cab237cb|d4b2c6b4|2a15..2f|"
                                         "....d196|..5e..10|....b1f1|b54e9838|"
                                         "..0cf1..|5c1a..fb|....f34d|19..d34c|"
                                         "..cacb48|..4c2d09|48..bc..|f98cc7..|"
                                         "ac..2b1a|..beb5..|98..03..|..61c35e|"
                                         "....1245|61..5ca8)";
    int res;

    if ((res = regcomp(&the_re, the_re_string, REG_EXTENDED|REG_NOSUB)) != 0) {
        char ebuf[256];

        (void) regerror(res, &the_re, ebuf, sizeof ebuf);
        (void) fprintf(stderr, "regcomp failed: %s\n", ebuf);

        return -1;
    }

    return 0;
}

int
matcher_matches(uint32_t u)
{
    char ubuf[9];

    (void) sprintf(ubuf, "%08x", u);

    return regexec(&the_re, ubuf, 0, 0, 0) == 0;
}

int
main(void)
{
    int i;
    unsigned tf, iterations, matches;
    time_t start;

    uint32_t tvals[] = {
                0xabcd0000, 0xabdc0089, 0x0000abcd, 0xde0000ab,
                0x00d80a00, 0x007bc500, 0xc600514a, 0x00b7585a,
                0x4732ecc4, 0x7c22e4da, 0x5a5e0063, 0x0000e866,
                0x00fdc367, 0xac0000b4, 0x70249edc, 0x00e97e32,
                0x000094d8, 0x0000fa6c, 0x459100ff, 0x00e40067,
                0xaab28500, 0x0000f81b, 0x15bb22ba, 0x3cf40000,
                0x57d3ad86, 0x00bd001e, 0x00ec67b7, 0x00693aaf,
                0x323c0018, 0xcab237cb, 0xd4b2c6b4, 0x2a15002f,
                0x0000d196, 0x005e0010, 0x0000b1f1, 0xb54e9838,
                0x000cf100, 0x5c1a00fb, 0x0000f34d, 0x1900d34c,
                0x00cacb48, 0x004c2d09, 0x4800bc00, 0xf98cc700,
                0xac002b1a, 0x00beb500, 0x98000300, 0x0061c35e,
                0x00001245, 0x61005ca8 };

    if (matcher_init() == -1) {
        return 1;
    }

    /* test known values */

    tf = 0;

    for (i = 0; i < sizeof(tvals) / sizeof(tvals[0]); i++) {
        if (!matcher_matches(tvals[i])) {
            (void) printf("0x%08x should match; didn't...\n", tvals[i]);
            tf = 1;
        }
    }

    if (tf) {
        return 1;
    }

    /* some random probes */

    srand((time(0) << 16) | (getpid() & 0xFFFF));

    iterations = matches = 0;

    (void) time(&start);

    for (i = 0; i < 1000000; i++) {
        uint32_t u = (uint32_t) ((rand() << 16) | (rand() & 0xFFFF));

        /* printf("Test: 0x%08x\n", u); */

        if (matcher_matches(u)) {
            (void) printf("Match: %08x\n", u);
            (void) fflush(stdout);
            matches++;
        }

        iterations++;
    }

    printf("iterations: %d; matches: %d (%u seconds)\n",
                        iterations, matches,
                        (unsigned) (time(0) - start));

    return 0;
}

Ответы на это напомнили мне о самом вопросе, и после размышления мне пришло в голову более прямой путь. Почему лучшие ответы не появляются в первую очередь, я никогда не узнаю.

В любом случае, не используйте регулярные выражения, просто значение и маску. Код выше теряет matcher_init вызов (вместе со всем, что связано с регулярным выражением), и matcher_matches Поддержка по телефону может выглядеть следующим образом. Искомые значения соответствуют дополнительным 46, которые я произвел для первого ответа, поэтому тот же тестовый код в первом ответе main будет продолжать работать.

Я полагаю, вы могли бы отсортировать массив struct vm так, чтобы вначале появлялись записи с меньшим количеством битов, установленных в маске, и вы покупаете скромный выигрыш в производительности, но даже если эта вторая попытка примерно в пять раз быстрее, чем для меня на основе регулярных выражений.

static struct {
    uint32_t val, mask;
} vm [] = {
    { 0xabcd0000, 0xffff0000 },
    { 0xabdc0089, 0xffff00ff },
    { 0x0000abcd, 0x0000ffff },
    { 0xde0000ab, 0xff0000ff },
    { 0x00d80a00, 0x00ffff00 },
    { 0x007bc500, 0x00ffff00 },
    { 0xc600514a, 0xff00ffff },
    { 0x00b7585a, 0x00ffffff },
    { 0x4732ecc4, 0xffffffff },
    { 0x7c22e4da, 0xffffffff },
    { 0x5a5e0063, 0xffff00ff },
    { 0x0000e866, 0x0000ffff },
    { 0x00fdc367, 0x00ffffff },
    { 0xac0000b4, 0xff0000ff },
    { 0x70249edc, 0xffffffff },
    { 0x00e97e32, 0x00ffffff },
    { 0x000094d8, 0x0000ffff },
    { 0x0000fa6c, 0x0000ffff },
    { 0x459100ff, 0xffff00ff },
    { 0x00e40067, 0x00ff00ff },
    { 0xaab28500, 0xffffff00 },
    { 0x0000f81b, 0x0000ffff },
    { 0x15bb22ba, 0xffffffff },
    { 0x3cf40000, 0xffff0000 },
    { 0x57d3ad86, 0xffffffff },
    { 0x00bd001e, 0x00ff00ff },
    { 0x00ec67b7, 0x00ffffff },
    { 0x00693aaf, 0x00ffffff },
    { 0x323c0018, 0xffff00ff },
    { 0xcab237cb, 0xffffffff },
    { 0xd4b2c6b4, 0xffffffff },
    { 0x2a15002f, 0xffff00ff },
    { 0x0000d196, 0x0000ffff },
    { 0x005e0010, 0x00ff00ff },
    { 0x0000b1f1, 0x0000ffff },
    { 0xb54e9838, 0xffffffff },
    { 0x000cf100, 0x00ffff00 },
    { 0x5c1a00fb, 0xffff00ff },
    { 0x0000f34d, 0x0000ffff },
    { 0x1900d34c, 0xff00ffff },
    { 0x00cacb48, 0x00ffffff },
    { 0x004c2d09, 0x00ffffff },
    { 0x4800bc00, 0xff00ff00 },
    { 0xf98cc700, 0xffffff00 },
    { 0xac002b1a, 0xff00ffff },
    { 0x00beb500, 0x00ffff00 },
    { 0x98000300, 0xff00ff00 },
    { 0x0061c35e, 0x00ffffff },
    { 0x00001245, 0x0000ffff },
    { 0x61005ca8, 0xff00ffff }
};

int
matcher_matches(uint32_t u)
{
    size_t i;

    for (i = 0; i < sizeof(vm) / sizeof(vm[0]); i++) {
        if ((u & vm[i].mask) == vm[i].val) {
            return 1;
        }
    }
    return 0;
}

Подстановочные знаки теперь нули в mask поле структуры, с соответствующими битами "все равно" значения (установлены в ноль) в val поле.

Answer 2

Поскольку вы не хотите перечислять значения для gperf (и похоже gperf в любом случае не может обрабатывать столько входов), то вы не можете использовать gperf для вашей задачи, поэтому ответ на свой вопрос вы не можете использовать gperf создать свой хэш.

Я рекомендую забыть об идеальном хешировании (вы не описываете никаких требований к идеальному хешированию, кроме вашего желания использовать) gperf). Сами значения хорошо распределены для использования в качестве хеш-значения как есть.