2

我尝试使用宏在编译时计算常量 C 字符串的哈希值。这是我的示例代码：

#include <stddef.h>
#include <stdint.h>

typedef uint32_t hash_t;

#define hash_cstr(s) ({           \
      typeof(sizeof(s)) i = 0;    \
      hash_t h = 5381;            \
      for (; i < sizeof(s) - 1; ) \
        h = h * 33 + s[i++];      \
      h;                          \
    })

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

int main() {
#define test(s) printf("The djb2 hash of " #s " is a %u\n", hash_cstr(#s))

  test(POST);
  test(/path/to/file);
  test(Content-Length);
}

现在我运行GCC来显示列表：

arm-none-eabi-gcc-4.8 -S -O2 -funroll-loops -o hash_test.S hash_test.c

结果正如预期的那样：所有字符串都被消除并被其哈希值替换。但通常我使用-Os来编译嵌入式应用程序的代码。当我尝试这样做时，我只对少于四个字符的字符串进行哈希处理。我还尝试设置参数max-unroll-times并使用GCC 4.9：

arm-none-eabi-gcc-4.9 -S -Os -funroll-loops \
  --param max-unroll-times=128 -o hash_test.S hash_test.c

我无法理解这种行为的原因以及如何扩展这个四个字符的限制。

4

3 回答 3

2

我建议将相关代码放在一个单独的文件中，并使用-O2（而不是-Os）编译该文件。或者放置一个特定于函数的编译指示，例如

 #pragma GCC optimize ("-O2")

在函数之前，或使用类似的函数属性__attribute__((optimize("02")))（并且该pure属性可能也相关）

您可能对__builtin_constant_p.

我会让你的散列代码成为一些static inline函数（可能带有always_inline函数属性），例如

 static inline hash_t hashfun(const char*s) {
    hash_t h = 5381;
    for (const char* p = s; *p; p++) 
      h = h * 33 + *p;
    return h;
 }

一个更可移植（且不那么脆弱）的替代方法是更改​​您的构建过程以生成一些 C 文件（例如，使用简单awk或python脚本，甚至是临时 C 程序），其中包含以下内容

  const char str1[]="POST";
  hash_t hash1=2089437419; // the hash code of str1

不要忘记，.c或者.h文件可以由其他东西生成（你只需要在你的内部添加一些规则Makefile来生成它们）；如果您的老板对此感到不安，请向他展示元编程维基页面。

于 2015-12-17T12:07:59.073 回答
1

似乎我找到了一种解决方法，它受长度限制。它看起来像一个肮脏的黑客，但可以与任何GCC工具链一起工作。

#define _hash_cstr_4(s, o)                \
  for (; i < ((o + 4) < sizeof(s) - 1 ?   \
              (o + 4) : sizeof(s) - 1); ) \
    h = h * 33 + s[i++]

#define _hash_cstr_16(s, o)           \
  _hash_cstr_4(s, o);                 \
  _hash_cstr_4(s, o + 4);             \
  _hash_cstr_4(s, o + 8);             \
  _hash_cstr_4(s, o + 12)

#define _hash_cstr_64(s, o)           \
  _hash_cstr_16(s, o);                \
  _hash_cstr_16(s, o + 16);           \
  _hash_cstr_16(s, o + 32);           \
  _hash_cstr_16(s, o + 48)

#define _hash_cstr_256(s, o)          \
  _hash_cstr_64(s, o);                \
  _hash_cstr_64(s, o + 64);           \
  _hash_cstr_64(s, o + 128);          \
  _hash_cstr_64(s, o + 192)

#define hash_cstr(s) ({                  \
      typeof(sizeof(s)) i = 0;           \
      hash_t h = 5381;                   \
      if (sizeof(s) - 1 < 256) {         \
        _hash_cstr_256(s, 0);            \
      } else                             \
        for (; i < sizeof(s) - 1; )      \
          h = h * 33 + s[i++];           \
      h;                                 \
    })

当哈希字符串的长度小于256个字符时，在编译时计算哈希，否则在运行时计算哈希。

此解决方案不需要额外调整编译器。它也适用于-Os和-O1。

于 2015-12-17T15:05:58.033 回答
0

如果允许 C++ 给模板函数一个机会，例如：

template<int I>
  hash_t hash_rec(const char* str, hash_t h) {
  if( I > 0 ) {
    return hash_rec<I-1>(str, h * 33 + str[I-1]);
  } else {
    return h;
  }
}

#define hash(str) hash_rec<sizeof(str)>(str, 5381)

h = hash(str);
于 2015-12-17T12:20:52.663 回答