logo标签列表

在嵌入式应用中选择C语言的唯一标识符

calgorithmembedded
4
我目前正在尝试实现一种算法来选择唯一的（16位）标识符。挑战在于以一种快速且不使用太多内存的方式完成此操作。当前已使用标识符的列表是通过扫描外部Flash设备通过一系列SPI事务确定的，因此这是一个相对较慢的过程。此外，算法将在一个相对较小的微控制器上运行，因此我不能真的将所有条目读入RAM并在那里处理。
到目前为止，我想到的思路有：
1.选择一个数字，然后扫描列表并查看它是否被使用。反复执行此操作。这种方法速度较慢（特别是如果有很多文件）。
2.与上述方法类似，但使用具有适当种子的伪随机数生成器选择数字。这样做的优点是迭代次数较少。
3.扫描列表并用所有找到的条目填充数组。排序后就变得简单了。这可能会使用大量内存。
4.使用一个巨大的（好吧，非常巨大的）位掩码。不是很实用。
5.接受该工具的寿命是在写入65534个文件到Flash之前就会被丢弃或“格式化”，因此只需将迄今为止使用的最高值存储在Flash或备份内存中并继续递增。老实说，对于这个特定的应用程序，这可能非常有效。
目前，我倾向于使用第二种方法或第五种方法，但如果有人有其他想法，我会很感兴趣。我希望能够找到一种类似于CRC的算法，可以用来处理每个数字，并给出一个没有被使用过的数字的合理估计，但我不知道这应该如何实现。
ID是否必须是非连续的？ - Robert Deml
完全没有关系，它们只需要在任何给定的时间是唯一的（因此删除的ID可以立即重新使用）。 - DrAl
12个回答
5

我认为你有几个选择，但还有一个选择可以考虑，那就是布隆过滤器。这种方法可能会出现误判（即您可能会将某个ID排除在已使用之列，尽管它实际上没有被使用），但它可以让您选择要为此数据分配的确切空间。

4
如果没有足够的RAM来实现一个包含64K条目的位图，那么为了找到未使用的ID，可以通过在每次扫描中使用较小的临时位图来减少对FLASH的扫描次数。16字节的位图可以在第一次扫描中记录0-255范围内找到的ID，在第二次扫描中记录256-511范围内找到的ID，以此类推。在每次扫描结束时，如果位图中至少有一个未标记的位，则表示查找完成。我相信这与使用随机起始范围结合使用效果会很好。
另一方面，如果我对选项5非常有信心，我可能会选择它。
1
使用最大线性反馈移位寄存器并存储您分配的最后一个值。LFSR将在特定起始点（不包括零）给出序列1..2^n中所有数字，以伪随机顺序。如果从第k个元素开始，则始终会得到相同的第k + 1个元素。实现非常简单：
if (IsEven(sequence)) {
    sequence /= 2;
}
else {
    sequence = (sequence / 2) ^ feedback;
}

其中反馈是从最大反馈表中的位模式，用于生成所需位数的数字。这意味着要生成下一个数字，您需要读取上一个分配的数字，通过上述代码运行它，然后使用它。

或者，为什么不只是计数并存储上一个分配的数字？

1

我猜测FLASH设备由于提到了SPI而不可移动，但是如果记忆卡具有SPI访问模式，则可能不是真的。

如果FLASH是永久性的，并且您有一个稳健的非易失性地方来记住最后发出的ID，则可能是应该做的事情。它在运行时肯定是快速和低内存的。它应该很容易解释、实现和测试。

如果FLASH是可拆卸的，则使用伪随机数生成器并测试冲突可能是正确的方法。假设您的数字分布良好，那么根据总数就可以轻松预测冲突的几率。只需选择一个重复间隔较长的生成器即可。为所选算法模拟这一点作为验收测试可能是个好主意。

1

我想知道为什么你不直接存储最后一个ID并递增它。你犹豫的原因是什么？在你的问题中没有给出原因，只有一种普遍的不安。

如果你需要ID具有一定的随机性以确保安全性，那么使用随机数生成器并将生成器的当前注册值保存在闪存中。这样，你可以加载它们用于下一个ID，这可以确保你选择合适的算法后获得完整的循环长度而不会重复。

[编辑]由于你担心碰撞，肯定有一些数据可能会发生碰撞，例如文件名或其他一些数据。如果常规方法（创建文件名并检查其是否存在）太慢，并且在“分配映射”中有巨大的间隙，则生成一个随机ID并进行检查。这应该可以让你在几次迭代中找到未使用的ID。

没有必要保证 ID 的安全性；我对存储最后一个 ID 感到不安的唯一原因是当我达到 ID 号码 65535 时。假设 ID 将被删除，会有空缺（Flash 存储器中不会有 65535 条条目的空间），所以我必须找出哪些是未使用的，这又将我带回到同样的问题。 - DrAl
这个解决方案快速、简单且可预测。如果你担心有一天会溢出，可以考虑将寻找可用ID的任务作为后台任务实现（当然，只有在溢出后才需要这样做）。 - Peter Gibson
0

我会选择2。但是要小心选择生成器和种子的方式。所有伪随机数序列在一定迭代次数后会重复。因此，您需要测试您的序列，以确保它不会太快地重复。

0

我会尝试第三种变体。不是存储排序后的值数组，而是存储排序后的范围数组。

0
你有多少RAM？这有点难以确定，"嵌入式"可以意味着很多东西。:) 一个位图需要8192字节，在生成期间保证每次都有完美的结果。
我也考虑过某种“稀疏”位图，但我手头没有合适的数据结构，不过可能值得研究一下。
微控制器的总RAM为10k，但是有很多事情要处理（包括相当多的循环缓冲区），所以即使是暂时的8k也有点太多了。 - DrAl
0

保持一个连续的ID计数器。
将ID通过MD5运行。
使用最低的16位。

理论上，MD5为每个输入创建不同的哈希值。最低的16位应该与整个哈希值一样“随机”。

0

如果您可以使用更大的ID，那么5将是一个不言而喻的选择。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接