现在可以使用普通C（不仅C ++）的编译时间哈希！
#算法 #c #哈希 #arduino

大家好，我回来了！经过几个月的失踪，不安的夜晚，过山车，终于我有一些要分享的东西ð让我们再次挖掘到兔子洞中

一点背景（我猜...）

想象一下，您试图用像"Acceleration X"这样的标签识别多个数据段，然后将它们用于设备之间的数据传输。通常，程序员宁愿创建一个像下表这样的整数的约定。

id 标签
1 加速x
2 加速y
3 方向
4 温度
... ...

传输数据时，所有设备都因为硬件约束而使用ID而不是标签（我们现在谈论的是Arduino/ESP32/AVR）。这种方法将起作用，但是如果您正在与大型团队或在互联网上与社区合作该怎么办？ 好吧...这很难

我们不尝试为每个标签定义一个整数，而是为什么不尝试自动化它？当然我们可以，但这是捕获：

  • ID必须不同，如果标签不同，否则它们碰撞
  • 接受标签的多样性，但ID大小（位于位）必须一致
  • 尽可能快地

好的，但是解决方案是什么？

在计算机科学中，我们了解了 hash函数的做法，并解决了上述问题。它的工作如下。

CRC32 converts vary length of text to 32 bits integer

这种方法是计算世界中的常见实践。通常用于error checking。但是，您是否曾经想过它实际上是如何工作的现场？ It's... complicated对我说。如此复杂，以至于没有人打扰创建其实现，以至于在complation Time 用宏语言中运行！

为什么要在汇编时间上运行它？

以前，我做了一个涉及AVR微控制器（准确地说是Arduino uno）和一个Orange Pi板的项目，并偶然发现了这种情况。我愚蠢地要求微控制器在运行时计算CRC32的±40个字符串，然后他们变得混乱。这种方法atte sram的2/3，花了多秒钟才能完成setup()函数。我开始考虑如果可以在编译时而不是运行时做到这一点。那可以节省大量的微控制器，对吗？好吧...不是那么容易。

试验和失败

C ++常数表达式

通过C ++的功率，我们可以明确地告诉编译器，以使用constexpr关键字计算CRC32！ Stackoverflow的某人给了我们一个snippet of compile-time CRC32。当我在Linux笔记本电脑上模拟它时，它可以按预期工作。除了...我忘记了我的橙皮板使用C代替C ++。

Facepalm

无论如何，这没什么大不了的，该董事会具有Gigahertz速度的多个CPU。我想没有什么问题...

内存使用比以前更大

...直到我意识到Arduino Ide无法编译：

Sketch uses 4448 bytes (13%) of program storage space. Maximum is 32256 bytes.
Global variables use 2290 bytes (111%) of dynamic memory, leaving -242 bytes for local variables. Maximum is 2048 bytes.
Not enough memory; see https://support.arduino.cc/hc/en-us/articles/360013825179 for tips on reducing your footprint.
Error compiling for board Arduino Uno.

no, noo, please god, noo!!

进行了数小时的故障排除，我意识到：

  1. CRC32表是由编译器无用的Flash存储。我意识到看到this gist后有一张桌子，由于某种原因，编译器将其存储到闪存中。
  2. 为什么在地球上这些弦仍然由编译器存储在Flash中？！

事实证明，我不能简单地将constexpr用于此目的。即使我遵循this advice，恒定表达仍然没有表现为“恒定表达”。

Now what?

让我们使用替代方案：宏

CRC32对于宏来说太复杂了

现在这是最有趣的事情，我们如何用宏来编写CRC32？答案是“不能”。试想一下，将大象活到冰箱里。即使将大象切成碎片，也不会起作用！

有趣的事情？您说“它不能”很有趣？

好吧，这不是“有趣的事情”，我的意思是，对不起。我的意思是当我找出一种替代方案但仍在工作的哈希算法时。 介绍我的自制简单XOR哈希功能：

f(s,i,x) = (s[i] ^ x) * 17

Where:
    s = Input string
    i = Current character index
    x = Hash result of previous character, if i == 0 then x = 11

该功能正在为字符串的每个字符（从左到右）执行（首先到最后）。

我称此算法称为六个哈希，因为该函数的参数看起来很有趣。未来似乎很光明，不是吗？现在，让我们写下DARN MACRO！

尝试使用Boost预处理器

对于那些不知道什么是Boost的人来说，这是一个C ++库，有助于预防re-inventing the wheel，同时尝试编程非常复杂的内容，例如仅与Macro，Boost Preprocessor循环。幸运的是，Boost Preprocessor Repeat还可以使用普通C，不仅是C ++。因此，我的橙皮板可以在编译时计算哈希。不幸的是，我的六种哈希算法需要sizeof(input)和 bubost ...不会...工作... 使用它。小时的解决方法，没有运气。

Visible Confusion

现在呢？哭泣??

好吧，我想我必须重新发明轮子again：）

用php循环C宏（认真）

如果我告诉您，PHP可以是C宏的宏？ 困惑？让我解释一下。

a Diagram where PHP file being read and outputs C file

使用PHP的目的是自动复制#define的系列，因为这就是Boost预处理器的作用。如果您曾经听说过PHP应该是预处理HTML，请再考虑一下，在盒子外面思考。 php可以方便地从中转换... 

#include <limits.h>

#define __IDENTITY_HASH_FUNC(s, n, i, x) (s[i < n ? n - 1 - i : 0] ^ x) * 17ull

<?php
    $max_iter = getenv("MAX_ITERATION");
    $last_iter = $max_iter - 1;

    echo "#define __IDENTITY_ITER_$last_iter(s, x, n) x\n";

    for ($i = $last_iter - 1; $i >= 0; $i--)
    {
        $next_iter = $i + 1;
        echo "#define __IDENTITY_ITER_$i(s, x, n) ($i < n ? __IDENTITY_HASH_FUNC(s, n, $i, __IDENTITY_ITER_$next_iter(s, x, n)) : x)\n";
    }
?>

#define IDENTITY(text) ((identity_t) /* */ __IDENTITY_ITER_0(text, 11ull, (sizeof text - 1)))

...到这个

#include <limits.h>

#define __IDENTITY_HASH_FUNC(s, n, i, x) (s[i < n ? n - 1 - i : 0] ^ x) * 17ull

#define __IDENTITY_ITER_63(s, x, n) x
#define __IDENTITY_ITER_62(s, x, n) (62 < n ? __IDENTITY_HASH_FUNC(s, n, 62, __IDENTITY_ITER_63(s, x, n)) : x)
#define __IDENTITY_ITER_61(s, x, n) (61 < n ? __IDENTITY_HASH_FUNC(s, n, 61, __IDENTITY_ITER_62(s, x, n)) : x)
#define __IDENTITY_ITER_60(s, x, n) (60 < n ? __IDENTITY_HASH_FUNC(s, n, 60, __IDENTITY_ITER_61(s, x, n)) : x)
#define __IDENTITY_ITER_59(s, x, n) (59 < n ? __IDENTITY_HASH_FUNC(s, n, 59, __IDENTITY_ITER_60(s, x, n)) : x)
#define __IDENTITY_ITER_58(s, x, n) (58 < n ? __IDENTITY_HASH_FUNC(s, n, 58, __IDENTITY_ITER_59(s, x, n)) : x)
#define __IDENTITY_ITER_57(s, x, n) (57 < n ? __IDENTITY_HASH_FUNC(s, n, 57, __IDENTITY_ITER_58(s, x, n)) : x)
/* 55 Lines collapsed, imagine how long the code if this expanded! */
#define __IDENTITY_ITER_1(s, x, n) (1 < n ? __IDENTITY_HASH_FUNC(s, n, 1, __IDENTITY_ITER_2(s, x, n)) : x)
#define __IDENTITY_ITER_0(s, x, n) (0 < n ? __IDENTITY_HASH_FUNC(s, n, 0, __IDENTITY_ITER_1(s, x, n)) : x)

#define IDENTITY(text) ((identity_t) /* */ __IDENTITY_ITER_0(text, 11ull, (sizeof text - 1)))

它有效！最后！

Hooray!

也很高兴提及任何人都可以通过设置MAX_ITERATION environment variable设置最大输入长度。可自定义，没有过多的复制，易于修订。

结论

这是一个诚实的激动人心的旅程，只是为了进行编译时间的工作。无论如何，您不必像我创建一个库一样重新发明轮子：

identity.h

不幸的是，它仍然是not perfect。如果您可以使其完美，请提取请求或打开问题。那会有所帮助。感谢您加入我到兔子洞的旅程。请参阅yafaterð