Определение хеш-макроса в C

Вы, вероятно, получили это определение из jhash.h: поддержка хеширования Jenkins

Как говорится в комментарии к предыдущей ссылке, обратимо смешивает 3 32-битных значения значения a, b и c получены из ключа, рассматриваемого как последовательность 32-битных значений, конечная цель - вычислить хеш-значение ключа.

Rotate и xor очень распространены при вычислении хэша, они также имеют преимущество, которое является обратимым.

Если я использую части кода, то для моего случая будет больше личных определений:

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

/* some personal definition for my case to make it working */
#define u32 unsigned int
#define u8 unsigned char
#define __get_unaligned_cpu32(k) (*k)

unsigned rol32(unsigned v, int n)
{
  return (v << n) | (v >> ((-n) & 0x1F));
}

/* codes from hash.h: Jenkins hash support.
 *
 * Copyright (C) 2006. Bob Jenkins (bob_jenkins@burtleburtle.net)
 * Copyright (C) 2009-2010 Jozsef Kadlecsik (kadlec@blackhole.kfki.hu)
 */

/* __jhash_mix -- mix 3 32-bit values reversibly. */
#define __jhash_mix(a, b, c)                        \
{                                                \
        a -= c;  a ^= rol32(c, 4);  c += b;        \
        b -= a;  b ^= rol32(a, 6);  a += c;        \
        c -= b;  c ^= rol32(b, 8);  b += a;        \
        a -= c;  a ^= rol32(c, 16); c += b;        \
        b -= a;  b ^= rol32(a, 19); a += c;        \
        c -= b;  c ^= rol32(b, 4);  b += a;        \
}

/* __jhash_final - final mixing of 3 32-bit values (a,b,c) into c */
#define __jhash_final(a, b, c)                        \
{                                                \
        c ^= b; c -= rol32(b, 14);                \
        a ^= c; a -= rol32(c, 11);                \
        b ^= a; b -= rol32(a, 25);                \
        c ^= b; c -= rol32(b, 16);                \
        a ^= c; a -= rol32(c, 4);                \
        b ^= a; b -= rol32(a, 14);                \
        c ^= b; c -= rol32(b, 24);                \
}

/* An arbitrary initial parameter */
#define JHASH_INITVAL                0xdeadbeef

/* jhash - hash an arbitrary key
 * @k: sequence of bytes as key
 * @length: the length of the key
 * @initval: the previous hash, or an arbitray value
 *
 * The generic version, hashes an arbitrary sequence of bytes.
 * No alignment or length assumptions are made about the input key.
 *
 * Returns the hash value of the key. The result depends on endianness.
 */
static inline u32 jhash(const void *key, u32 length, u32 initval)
{
        u32 a, b, c;
        const u8 *k = key;

        /* Set up the internal state */
        a = b = c = JHASH_INITVAL + length + initval;

        /* All but the last block: affect some 32 bits of (a,b,c) */
        while (length > 12) {
                a += __get_unaligned_cpu32(k);
                b += __get_unaligned_cpu32(k + 4);
                c += __get_unaligned_cpu32(k + 8);
                __jhash_mix(a, b, c);
                length -= 12;
                k += 12;
        }
        /* Last block: affect all 32 bits of (c) */
        switch (length) {
        case 12: c += (u32)k[11]<<24;        /* fall through */
        case 11: c += (u32)k[10]<<16;        /* fall through */
        case 10: c += (u32)k[9]<<8;        /* fall through */
        case 9:  c += k[8];                /* fall through */
        case 8:  b += (u32)k[7]<<24;        /* fall through */
        case 7:  b += (u32)k[6]<<16;        /* fall through */
        case 6:  b += (u32)k[5]<<8;        /* fall through */
        case 5:  b += k[4];                /* fall through */
        case 4:  a += (u32)k[3]<<24;        /* fall through */
        case 3:  a += (u32)k[2]<<16;        /* fall through */
        case 2:  a += (u32)k[1]<<8;        /* fall through */
        case 1:  a += k[0];
                 __jhash_final(a, b, c);
        case 0: /* Nothing left to add */
                break;
        }

        return c;
}

#define N 32

int main()
{
  int k[32];
  size_t i;

  srand(time(0));

  printf("jhash({");

  for (i = 0; i != N; ++i) {
    k[i] = rand();
    printf("%d ", k[i]);
  }

  printf("}, %u, 0) = %u\n", N, jhash(k, N, 0));
}

Компиляция и выполнение:

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra k.c
pi@raspberrypi:/tmp $ ./a.out
jhash({725625346 2051442142 1165233932 1356547768 2099014845 266019399 528918070 18604707 1945148507 987748948 1335740895 332797747 1690673992 2098399251 1687576619 286743973 2002511209 1997615319 887418158 1218108826 1451009818 973285977 2028050363 1116200465 863906896 1573231493 1035506113 1283577784 928643781 74360164 191441086 1654269127 }, 32, 0) = 1693699835
pi@raspberrypi:/tmp $ ./a.out
jhash({1500372397 800038188 1822383935 2049924247 1967907533 1822952097 1311149758 1738252197 464832103 1177755638 296710542 694221671 414698890 78801632 1686474026 1285412744 264383868 1512129910 242686348 514308142 557986701 1643746510 341957038 1943957666 304144553 484844558 449494178 1729050684 1161649732 1866984013 472090176 514538481 }, 32, 0) = 1130358
pi@raspberrypi:/tmp $ ./a.out
jhash({122835781 612581003 328765017 1664431043 1825042737 154150284 1014172891 1296418362 1125874777 1361929618 1388631300 1047417778 1279955676 1261053435 600697914 129834773 1724943228 1012276842 1738014852 1931963584 1793760158 1232153606 1847243743 600168910 808588272 1509948749 1980278411 1089542038 1356188813 1473345525 739126939 1479024594 }, 32, 0) = 843972389

Макросы выполняют подстановку текста. Это означает, что он просто заменяет все, что вы даете ему как a, b и c внутри определения. Вы можете сделать то же самое вручную, и он должен дать вам код, который он генерирует.

Примечания:

• Макросы работают без какой-либо проверки синтаксиса, проверки типов или других проверок работоспособности, поэтому их обычно осуждают.
• Фактическая работа этого кода зависит также от того, что вы ему кормите. Мой ответ не объясняет, как это должно работать именно по этой причине. Это зависит от того, что находится вне контроля этого макроса.
• Этот код, вероятно, будет лучше закодирован как встроенная функция, которая обеспечивает проверку типов и, как правило, несколько ограничений, которые, в свою очередь, предоставляют гарантии.
• Вероятно, в основном это не имеет значения, но этот макрос даже содержит ошибки, потому что он использует символ, который зарезервирован (двойное, последовательное подчеркивание) для компилятора и реализации. Я не уверен насчет точного термина, но он либо приводит к тому, что программа плохо сформирована, либо к неопределенному поведению, но «глючит» суммирует его довольно хорошо. Это еще одна вещь, которая делает этот код плохим.