在位数组中有效查找“1”的位置
我正在连接一个程序来测试一组电线的开路或短路情况。该程序在 AVR 上运行，将测试向量（步行“1”）驱动到电线上并接收返回结果。它将所得向量与已存储在 SD 卡或外部 EEPROM 上的预期数据进行比较。
这里有一个例子，假设我们有一组 8 根电线，所有电线都是直通的，即它们没有连接点。因此，如果我们驱动 0b00000010，我们应该收到 0b00000010。
假设我们收到 0b11000010。这意味着导线 7,8 和导线 2 之间存在短路。我可以通过 0b00000010 ^ 0b11000010 = 0b11000000 检测到我感兴趣的位。这清楚地告诉我第 7 号线和第 8 号线有故障，但是我如何在大型位数组中有效地找到这些“1”的位置。使用位掩码只需 8 条线即可轻松完成此操作，但我正在开发的系统必须处理多达 300 条线（位）。在我开始使用如下宏并测试 300*300 位数组中的每一位之前，我想在这里询问是否有更优雅的解决方案。
#define BITMASK(b) (1 << ((b) % 8))
#define BITSLOT(b) ((b / 8))
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a,b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a,b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + 8 - 1) / 8)
只是为了进一步展示如何检测开路。预期数据：0b00000010，接收数据：0b00000000（电线未拉高）。 0b00000010 ^ 0b00000000 = 0b0b00000010 - 电线 2 开路。
注意：我知道测试 300 条线不是 AVR Mega 1281 内的微小 RAM 可以处理的，这就是为什么我将其分成几组，即测试 50 条线，比较，显示结果，然后继续。
I'm wiring a program that tests a set of wires for open or short circuits. The program, which runs on an AVR, drives a test vector (a walking '1') onto the wires and receives the result back. It compares this resultant vector with the expected data which is already stored on an SD Card or external EEPROM.
Here's an example, assume we have a set of 8 wires all of which are straight through i.e. they have no junctions. So if we drive 0b00000010 we should receive 0b00000010.
Suppose we receive 0b11000010. This implies there is a short circuit between wire 7,8 and wire 2. I can detect which bits I'm interested in by 0b00000010 ^ 0b11000010 = 0b11000000. This tells me clearly wire 7 and 8 are at fault but how do I find the position of these '1's efficiently in an large bit-array. It's easy to do this for just 8 wires using bit masks but the system I'm developing must handle up to 300 wires (bits). Before I started using macros like the following and testing each bit in an array of 300*300-bits I wanted to ask here if there was a more elegant solution.
#define BITMASK(b) (1 << ((b) % 8))
#define BITSLOT(b) ((b / 8))
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a,b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a,b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + 8 - 1) / 8)
Just to further show how to detect an open circuit. Expected data: 0b00000010, received data: 0b00000000 (the wire isn't pulled high). 0b00000010 ^ 0b00000000 = 0b0b00000010 - wire 2 is open.
NOTE: I know testing 300 wires is not something the tiny RAM inside an AVR Mega 1281 can handle, that is why I'll split this into groups i.e. test 50 wires, compare, display result and then move forward.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
许多架构提供了用于定位字中的第一个设置位或用于计算设置位的数量的特定指令。编译器通常为这些操作提供内在函数，这样您就不必编写内联汇编。例如，GCC 提供了 __builtin_ffs、
__builtin_ctz、__builtin_popcount等，其中每一个都应该映射到目标架构上的相应指令，利用位级并行性。如果目标体系结构不支持这些，编译器将发出有效的软件实现。在软件中逐位测试向量的简单方法效率不高。
如果您的编译器没有实现这些，您仍然可以使用 de Bruijn 编写自己的实现序列。
Many architectures provide specific instructions for locating the first set bit in a word, or for counting the number of set bits. Compilers usually provide intrinsics for these operations, so that you don't have to write inline assembly. GCC, for example, provides
__builtin_ffs,__builtin_ctz,__builtin_popcount, etc., each of which should map to the appropriate instruction on the target architecture, exploiting bit-level parallelism.If the target architecture doesn't support these, an efficient software implementation is emitted by the compiler. The naive approach of testing the vector bit by bit in software is not very efficient.
If your compiler doesn't implement these, you can still code your own implementation using a de Bruijn sequence.
您预计会出现多少次故障？如果您不经常期望它们，那么优化“存在故障”情况似乎毫无意义——对速度真正重要的唯一部分是“无故障”情况。
要优化无故障情况，只需将实际结果与预期结果进行异或，并进行
input ^ Expected == 0测试以查看是否设置了任何位。如果您进一步期望故障数量在确实存在时通常很小，您可以使用类似的策略来优化“很少故障”的情况 - 屏蔽
input ^ Expect值以获取前 8 位，仅后 8 位，依此类推，并将每个结果与零进行比较。然后，您只需要在不等于零的位中搜索设置的位，这应该将搜索空间缩小到可以很快完成的事情。How often do you expect faults? If you don't expect them that often, then it seems pointless to optimize the "fault exists" case -- the only part that will really matter for speed is the "no fault" case.
To optimize the no-fault case, simply XOR the actual result with the expected result and a
input ^ expected == 0test to see if any bits are set.You can use a similar strategy to optimize the "few faults" case, if you further expect the number of faults to typically be small when they do exist -- mask the
input ^ expectedvalue to get just the first 8 bits, just the second 8 bits, and so on, and compare each of those results to zero. Then, you just need to search for the set bits within the ones that are not equal to zero, which should narrow the search space to something that can be done pretty quickly.您可以使用查找表。例如，255 字节的 log-base-2 查找表可用于查找字节中最高有效的 1 位：
其中 log2 定义如下：
在大多数处理器上，这样的查找表将进入 ROM。但AVR是哈佛机器，将数据放入代码空间（ROM）需要特殊的非标准扩展，这取决于编译器。例如，IAR AVR 编译器需要使用扩展关键字 __flash。在 WinAVR (GNU AVR) 中，您需要使用 PROGMEM 属性，但它比这更复杂，因为您还需要使用特殊的宏来从程序空间读取。
You can use a lookup table. For example log-base-2 lookup table of 255 bytes can be used to find the most-significant 1-bit in a byte:
where log2 is defined as follows:
On most processors a lookup table like this will go to ROM. But AVR is a Harvard machine and to place data in code space (ROM) requires special non-standard extension, which depends on the compiler. For example the IAR AVR compiler would need use the extended keyword __flash. In WinAVR (GNU AVR) you would need to use the PROGMEM attribute, but it's more complex than that, because you would also need to use special macros to to read from the program space.
我认为只有一种方法可以做到这一点：
我强烈推荐内联函数而不是那些宏。
为什么你的 MCU 不能处理 300 条线？
300/8 = 37.5 字节。四舍五入为38。需要存储两次，outdata和indata，38*2 = 76字节。
您不能腾出 76 字节 RAM 吗？
I think there is only one way to do this:
I would strongly recommend inline functions instead of those macros.
Why can't your MCU handle 300 wires?
300/8 = 37.5 bytes. Rounded to 38. It needs to be stored twice, outdata and indata, 38*2 = 76 bytes.
You can't spare 76 bytes of RAM?
我认为你只见树木不见森林。看起来像是钉床测试。首先测试一些假设：
1) 您知道每个测试/通电的引脚应带电。
2) 您已将步骤 1 的网表转换为 SD 上的文件。
如果您在字节级别和位级别上操作，则可以简化问题。如果您为引脚通电，则会在您的文件中存储预期的模式输出。首先找到不匹配的字节；识别字节中不匹配的引脚；最后将通电的引脚与故障引脚编号一起存储。
您不需要用于搜索或结果的数组。总体思路：
I think you're missing the forest through the trees. Seems like a bed of nails test. First test some assumptions:
1) You know which pins should be live for each pin tested/energized.
2) you have a netlist translated for step 1 into a file on sd
If you operate on a byte level as well as bit, it simplifies the issue. If you energize a pin, there is an expected pattern out stored in your file. First find the mismatched bytes; identify mismatched pins in the byte; finally store the energized pin with the faulty pin numbers.
You don't need an array for searching, or results. general idea: