如何仅使用C预处理器计算字符串字面值的哈希？

Question

如何仅使用C预处理器计算字符串字面值的哈希？

7

我需要使用C预处理器来获得字符串校验和或哈希值（或等效内容），如果可能的话。用例是在具有非常有限的内存和CPU的嵌入式设备上执行错误日志记录。我想定义一个LogError()宏，该宏在循环缓冲区中插入hash(__FILE__)和__LINE__（以16位数字形式）。但是，hash(__FILE__)需要编译为常量；如果实际的文件名作为字符串存储在将使用太多内存的程序中，因此无法使用。可以使用任何方法计算哈希值。可以在每个文件的顶部使用一些唯一编号来#define FILE_ID，并在记录日志时使用它，但这不是首选解决方案，它具有一定的维护成本。是否有更好的方法？

- Alex I

2

在C语言中，像"foo.c"[0]+9*"foo.c"[1]这样的表达式不是常量表达式，但在代码中使用时，仍然可能被编译为常量。 - greggo

如果两个文件具有相同的哈希值会怎样？ - user253751

3

不可能完成。您的编译器可能会或可能不会将哈希函数调用折叠为常量；我更倾向于它无法这样做。如果您在makefile中使用类似于“-DFILE_ID=$$(myhashpgm $<)”这样的东西，使用FILE_ID的解决方案实际上非常低维护。 - n. m.

是的，我考虑过这种方法，它是可行的，但文件名的长度受到限制。然而，也不能保证它会编译成一个常量。 - n. m.

1

这个问题很尴尬，因为在某些情况下使用预处理器来哈希字符串是有用的，但几乎肯定_不是_这种情况的好解决方案。我添加了自己的答案，但想知道你的详细用例是否应该成为另一个问题，用于计算原始架构的日志记录ID。 - ideasman42

显示剩余5条评论

3个回答

0

如何在CMake中实现这个？我无法弄清楚如何为每个源文件运行脚本，并将结果放置为-DFILE_CHEKSUM的值。

使用STRHASH的方法有一个很大的限制-它最多接受32个字符作为输入，当我的名称更长时，它就无法编译。我认为在构建之前计算它并将其作为-D传递是更好的方法，但我只是无法在cmake中实现它:(

- Robert Gałat

没关系，我使用了以下代码：

static inline unsigned int strhash()
{
    const char *p = __FILE__;
    // 忽略 clang-diagnostic-static-local-in-inline - 在这种情况下是预期的行为
    static unsigned int h = 5381;  // NOLINT
    if(h!=5381)
    {
        return h;
    }

    for (;*p != '\0'; p++) {
        h = (h << 5) + h + (unsigned int)*p;
    }

    return h;
}

因此，在文件中计算一次后，我将快速返回。 - Robert Gałat

0

你对预处理器要求过高了。

最好的方法是按照 @n.m 的建议，为每个文件构建一个定义为预处理宏的其名称的16位校验和。

这种解决方案的一个微小困难在于找到一个16位校验和实用程序。GNU cksum 工具只有32位。

但是FreeBSD有一个更好的工具，可以让您选择16位或32位。如果您的开发系统是Debian衍生品，则可以通过以下方式获得它：

sudo apt-get install freebsd-buildutils

然后运行：

dpkg-query -L freebsd-buildutils

查看FreeBSD中cksum的安装位置。在我的情况下，它是：

/usr/bin/freebsd-cksum

但你可能会发现不同的结果。

你可以通过传递选项-o 1来指示FreeBSD cksum生成一个16位校验和。你可以查看它的手册页面。

在生成定义文件名校验和的预处理器宏时，请注意将校验和定义为16位无符号整数，因为这正是你想要的。如果它变成了一个纯十进制数字，例如，默认情况下它将默认为有符号整数，这可能会给你带来意外的麻烦。

以下是使用GNU make的解决方案草图：

main.c

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

int main(int argc, char **argv)
{
    printf("%hu\n",FILE_CHKSUM);
    return 0;
}

Makefile

.phony: all clean

SRCS = main.c
OBJS = $(SRCS:.c=.o)
# Take the 1st word of the output of `echo <filename> | freebsd-cksum -o 1`
FILE_CHKSUM = $(word 1,$(shell echo $(1) | freebsd-cksum -o 1))

all: prog

%.o:%.c
    $(CC) $(CPPLAGS) $(CFLAGS) -DFILE_CHKSUM='((uint16_t)$(call FILE_CHKSUM,$<))' -c -o $@ $< 

prog: $(OBJS)
    $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $(OBJS) $(LDLIBS)

clean:
    rm -f $(OBJS) prog

运行 make：

cc   -DFILE_CHKSUM='((uint16_t)3168)' -c -o main.o main.c 
cc   -o prog main.o

运行 prog：

./prog
3168

- Mike Kinghan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ideasman42 · Accepted Answer

这个问题“如何仅使用C预处理器计算字符串文字的哈希值？”是合理的，但我认为您包含了有关__FILE__和日志ID的细节，这是一个转移话题。

这意味着任何回答都需要解决您描述的问题，或回答关于使用预处理器哈希字符串的问题（在您的特定情况下可能不是一个好的解决方案！）。

恰好，__FILE__扩展为变量而不是文字字符串（至少在GCC中），因此您需要将文件名定义为常量。例如，您可以使用构建系统传递每个define。

正如其他人指出的那样，您可以通过构建系统计算哈希并将其传递，尽管这避免了关于哈希字符串文本的问题。

无论如何，当我搜索使用预处理器进行哈希时，都会出现这个问题，而且没有一个答案涵盖了这一点，因此这里是一个涵盖了字符串哈希部分的答案。

这是可能的，尽管相当冗长。

/**
 * Implement compile-time string hashing on string literals.
 *
 * This macro implements the widely used "djb" hash apparently posted
 * by Daniel Bernstein to comp.lang.c some time ago.  The 32 bit
 * unsigned hash value starts at 5381 and for each byte 'c' in the
 * string, is updated: ``hash = hash * 33 + c``.  This
 * function uses the signed value of each byte.
 *
 * note: this is the same hash method that glib 2.34.0 uses.
 */

#define SEED 5381

#if 0
// correct but causes insane expansion
#  define _SH(e, c) (((e) << 5) + (e) + (unsigned char)(c))
#elif defined(__GNUC__)
// Use statement-expression extension
#  define _SH(e, c) ({ unsigned int _e = (unsigned int)(e); (_e << 5) + _e + (unsigned char)c; })
#else
// use an inline function, the compiler will be able to optimize this out.
static inline unsigned int _SH(unsigned int e, unsigned char c)
{
    unsigned int _e = (unsigned int)e;
    return (_e << 5) + _e + (unsigned char)c;
}
#endif

#define _SH_1(a) _SH(SEED, (a)[0])
#define _SH_2(a) _SH(_SH_1(a), (a)[1])
#define _SH_3(a) _SH(_SH_2(a), (a)[2])
#define _SH_4(a) _SH(_SH_3(a), (a)[3])
#define _SH_5(a) _SH(_SH_4(a), (a)[4])
#define _SH_6(a) _SH(_SH_5(a), (a)[5])
#define _SH_7(a) _SH(_SH_6(a), (a)[6])
#define _SH_8(a) _SH(_SH_7(a), (a)[7])
#define _SH_9(a) _SH(_SH_8(a), (a)[8])
#define _SH_10(a) _SH(_SH_9(a), (a)[9])
#define _SH_11(a) _SH(_SH_10(a), (a)[10])
#define _SH_12(a) _SH(_SH_11(a), (a)[11])
#define _SH_13(a) _SH(_SH_12(a), (a)[12])
#define _SH_14(a) _SH(_SH_13(a), (a)[13])
#define _SH_15(a) _SH(_SH_14(a), (a)[14])
#define _SH_16(a) _SH(_SH_15(a), (a)[15])
#define _SH_17(a) _SH(_SH_16(a), (a)[16])
#define _SH_18(a) _SH(_SH_17(a), (a)[17])
#define _SH_19(a) _SH(_SH_18(a), (a)[18])
#define _SH_20(a) _SH(_SH_19(a), (a)[19])
#define _SH_21(a) _SH(_SH_20(a), (a)[20])
#define _SH_22(a) _SH(_SH_21(a), (a)[21])
#define _SH_23(a) _SH(_SH_22(a), (a)[22])
#define _SH_24(a) _SH(_SH_23(a), (a)[23])
#define _SH_25(a) _SH(_SH_24(a), (a)[24])
#define _SH_26(a) _SH(_SH_25(a), (a)[25])
#define _SH_27(a) _SH(_SH_26(a), (a)[26])
#define _SH_28(a) _SH(_SH_27(a), (a)[27])
#define _SH_29(a) _SH(_SH_28(a), (a)[28])
#define _SH_30(a) _SH(_SH_29(a), (a)[29])
#define _SH_31(a) _SH(_SH_30(a), (a)[30])
#define _SH_32(a) _SH(_SH_31(a), (a)[31])

// initial check prevents too-large strings from compiling
#define STRHASH(a) ( \
    (void)(sizeof(int[(sizeof(a) > 33 ? -1 : 1)])), \
    (sizeof(a) == 1) ? SEED : \
    (sizeof(a) == 2) ? _SH_1(a) : \
    (sizeof(a) == 3) ? _SH_2(a) : \
    (sizeof(a) == 4) ? _SH_3(a) : \
    (sizeof(a) == 4) ? _SH_3(a) : \
    (sizeof(a) == 5) ? _SH_4(a) : \
    (sizeof(a) == 6) ? _SH_5(a) : \
    (sizeof(a) == 7) ? _SH_6(a) : \
    (sizeof(a) == 8) ? _SH_7(a) : \
    (sizeof(a) == 9) ? _SH_8(a) : \
    (sizeof(a) == 10) ? _SH_9(a) : \
    (sizeof(a) == 11) ? _SH_10(a) : \
    (sizeof(a) == 12) ? _SH_11(a) : \
    (sizeof(a) == 13) ? _SH_12(a) : \
    (sizeof(a) == 14) ? _SH_13(a) : \
    (sizeof(a) == 15) ? _SH_14(a) : \
    (sizeof(a) == 16) ? _SH_15(a) : \
    (sizeof(a) == 17) ? _SH_16(a) : \
    (sizeof(a) == 18) ? _SH_17(a) : \
    (sizeof(a) == 19) ? _SH_18(a) : \
    (sizeof(a) == 20) ? _SH_19(a) : \
    (sizeof(a) == 21) ? _SH_20(a) : \
    (sizeof(a) == 22) ? _SH_21(a) : \
    (sizeof(a) == 23) ? _SH_22(a) : \
    (sizeof(a) == 24) ? _SH_23(a) : \
    (sizeof(a) == 25) ? _SH_24(a) : \
    (sizeof(a) == 26) ? _SH_25(a) : \
    (sizeof(a) == 27) ? _SH_26(a) : \
    (sizeof(a) == 28) ? _SH_27(a) : \
    (sizeof(a) == 29) ? _SH_28(a) : \
    (sizeof(a) == 30) ? _SH_29(a) : \
    (sizeof(a) == 31) ? _SH_30(a) : \
    (sizeof(a) == 32) ? _SH_31(a) : \
    (sizeof(a) == 33) ? _SH_32(a) : \
    0)
// last zero is unreachable

// only for comparison
unsigned int strhash_func(const void *str)
{
    const signed char *p;
    unsigned int h = 5381;

    for (p = str; *p != '\0'; p++) {
        h = (h << 5) + h + (unsigned int)*p;
    }

    return h;
}

/* -------------------------------------------------------------------- */
#include <stdio.h>

#define TEST_STR1 "Hello World"
#define TEST_STR2 "Testing 123"
int main(void)
{
    unsigned int A = STRHASH(TEST_STR1);
    unsigned int B = STRHASH(TEST_STR2);

    printf("String hash: const %u <- '%s'\n", STRHASH(TEST_STR1), TEST_STR1);
    printf("String hash: const %u <- '%s'\n", STRHASH(TEST_STR2), TEST_STR2);
    printf("String hash: dyn %u <- '%s'\n", strhash_func(TEST_STR1), TEST_STR1);
    printf("String hash: dyn %u <- '%s'\n", strhash_func(TEST_STR2), TEST_STR2);

#if defined(__GNUC__)
    printf("Is this known at compile time?, answer is: %d\n", __builtin_constant_p(A));
#endif
}

请注意，由于某些原因，Clang 5.0输出了answer is: 0，但仔细检查后，它实际上在编译时知道该值，只是__builtin_constant_p似乎不像GCC那样工作。