“是不是时候了，我的朋友们，让我们摇摆到威廉，莎士比亚吗？ ”。
我最近读了一篇有关自定义键盘的文章，并再次认为写一个键盘实现参考（即，以其名称签名并公开显示并不感到羞耻）会很好。 这个想法不是第一次出现，而是在第一阶段就停止了-阅读初始信息，因为我想使此阶段易于定制，易于使用，通用且有效，并且我不喜欢“选择两者”的提议。
必要的注意-我看到4个键盘实现层：0-事件检测，1-数据读取，2-数据清理和存储，3-消息生成，4-转码等。 在我看来，第1层和与之相关的第0层最有前途的似乎是使用Anton Chizhov模板来处理MK引脚（基于Loki类），也许有一天，其结果不会为人共享，但今天肯定不会。 现在我正在考虑第二层。
让我们来表述这个问题-必须存储一组固定的开关信息，这些开关具有两个预定义值之一（“闭合”和“未闭合”）。 最自然的候选对象是布尔变量和位集库，以存储集。 由于效率的要求是绝对必要的，因此希望从这一角度评估模块的实施。
我的第一个想法是查看源代码，所有内容立即变得清晰起来，但是在与他们进行了短暂的了解之后，我意识到学习其他人的模板并不是一件很有趣的事情（而且效率也不高）。 另外，由于直接对编译器不开放，因此来源没有对实现的有效性给出准确的评估。 实际上，仍然需要研究源文本，否则对源文本进行更改将是一个非常漫长的过程（当然，除非我们对达到一定的结果感兴趣），但这是另一篇文章的主题。
因此，采用了研究“黑匣子”的技术-我们将各种代码片段输入到输入中，并考虑生成的汇编器。 不幸的是，不可能将最喜欢的Godbolt站点用于熟悉的AVR架构，因为此实现中没有正在研究的库。 当然，您可以用笔拖动它，但是不能保证它将是正确的源代码。
因此，我们将看一个不同的体系结构。 x51并未提供给gcc编译器使用，我从不喜欢x86，ARM没有一个非常方便（一个人）且易于理解的汇编器，MIPS非常具体且不太常见，各种SPARC甚至更糟（嗯，我不会冒犯他们喜欢的架构的人，并非更好），但是有一个很好的候选MSP430，它基于PDP的水晶般清晰，优雅的体系结构，TI对此却丝毫没有破坏（尽管他们尝试过）。 给出了用于此体系结构的许多位的库，因此您可以开始学习。
让我们开始吧，因为听起来并不琐碎，但是从一开始就宣布了众多。 马上我们将看到，尽管该体系结构中的自然单位是两个字节的字，但存储的内存却以四个字节的字分配，并且提供了非常方便和高效的字节处理方式，这导致了奇怪的事件。 您可以理解作者，应该无处不在地实现32位数字，并且自然地依赖它，但是在这种情况下，最好使用8位，对于AVR，8位将是唯一合理的解决方案。
一个有趣的问题，但是如何在编译过程中确定体系结构的位深度，则需要尝试uint8_t_fast。 我们注意到可能的优化，然后继续。
除了分配内存外，初始化还很有趣-对于全局集，它以标准方式完成-在调用main之前清零，对于局部集，它也以标准方式完成，也就是说，如果未明确指定初始值，则绝不可以。 好吧，而且，像往常一样，如果可以用函数外部的初始值描述静态集，则应使用它，以免打开不必要的标志并且不花费执行时间。 但是在这里我们没想到会有任何启示，我们只是检查了一般规则。
让我们开始修改集合，为此我们留下了方括号以及set和reset方法。 我们可以期望看到这样的情况来设置元素M在集合M中：
M[n / w] |= (1<<(n % w))
其中w是基本元素中的位数，对于给定的体系结构，静态定义n（例如4），并且所包含的优化会导致以下形式的代码：
bis.w #0x0010, m
确实，我们在窗口的右半部分看到了这样的代码，而且不太可能有人会冒着冒风险断言更有效的解决方案的可能性。 但这仅适用于指示的条件，对于任意n幅图完全改变，对于方法，我们观察参数对可接纳性的验证并生成相应的异常，对于方括号，我们看到对参数的限制是带有允许范围的位掩码并具有完全可预测的未定义行为，这两种情况都与文档一致。 由于索引被视为无符号数，因此负数的处理非常正确。
我们提请注意以下事实：集合的元素的赋值不仅可以是0和1（正如人们可能期望的那样），而且可以是规则“什么是单位？ 不是零”，这是很合逻辑的，但是在文档中却很少反映出来。 做了一些奇怪的事情，但布尔值会更自然，将其剔除并继续前进。
比较为一组集合中的元素数量不确定的情况生成的代码，这表明在两种情况（[]和方法）下，代码的效率都非常接近且很小，因为调用了标准库中的一个子程序来计算（1 << n），并且该子程序移位32位数字0x00000001，放置在两个寄存器中。 我们看不到它的原始文本，但是通话的事实导致令人悲伤的想法。 事实是，在所考虑的体系结构中，没有像在所有（许多）心爱的ARM中那样向左移动（也没有向右移动）任意数量的位置。 有1个位置的移位（如果根本不存在，这很奇怪），有2,3,4个位置的移位（但严格按命令中固定的数字，而不是参数），有REPT前缀（但执行速度会降低）祝愿最好）。 您可以实现最小单位的移位（这一点很重要，只有一个单位），即通过交换四位位等技巧在相对较短的时间内通过位数获得位掩码，但是这将是一个非常依赖的部分，通常情况下最好不要这样做。
因此，一种通用且快速的方法是将位掩码存储在数组和索引中，并且在这种体系结构上它也非常有效，代码如下所示：
M[n/w] |= BitArray[n %w]
像这样的汇编器：
bis.b BitArray(r0),M(r1)
由于我们在谈论模式，并且w是字节大小的倍数，因此在这里除法运算非常有效。 我们注意到最小化实现的存储元素的明显优势：对于一个字节，一个字节需要8字节的数组，对于字组织，-2 * 16 = 32字节，对于32位长字，则需要4 * 32 = 128字节以存储所有必需的口罩，如果结果保持不变，为什么还要支付更多。 让我们记住更多可能的优化并继续前进。
我们还要注意一个事实-如果目标体系结构具有位标记的内存区域（在这里再次调用先前拒绝的ARM），则使用set元素进行操作的效率更高的实现是可能的，在该区域中，元素安装操作通常变为BitSetAddr [n] =南瓜1，它转换为常数n的单个汇编器命令，但是那里已经有足够的有效移位，因此，这种优化将更加冗余，尤其是考虑到其局限性。 原则上，x51和AVR中都有类似的位寻址区域，但是仅对于恒定的元素编号才有有效的命令，在一般情况下，一切都不尽人意（坦率地说是不好的）。
好了，现在仔细看一下生成的代码，并注意我们观察到与以双字存储集合有关的工件。 用于修改集合元素的操作的编译器生成一系列命令，这些命令从内存中读取相应的双字到2个寄存器中（我记得我们有16位寄存器），对其进行修改并将结果发送回内存。 如果仅更改一个元素，则操作掩码将只包含32个可能的单位（其余为零）。 当我们应用静态定义的元素编号时，应在优化阶段排除不更改结果的操作。 通常会发生这种情况，但是对于各种操作数而言，都会出错，并且形式的工件会泄漏到最终代码中：
bic #0,r0
如果您注意到该寄存器虽然被读取，却没有写回到内存，这看起来尤其有趣。 严格来说，优化的结果不受任何地方的监管，因此它们可以是任何东西，没有什么可冒犯的，但是，“结果并不整洁。” 如果我们不认真考虑编译器的源代码，我们将无法直接影响此过程，因此让我们绕开它-我们将通过简化优化器的工作来帮助优化器。
顺便说一句，我仍然找不到问题的答案-在C ++中的宏或模板级别是否可能针对静态未定义的参数在编译阶段为静态定义的定义不同的实现。 如果有人知道武士的方式，请在评论中告诉我，我尝试了constexpr，但没有用。
我们继续研究，发现编译器无法控制地优化对集合的调用（当然，如果打开了优化功能），也就是说，完全不能保证安装/清理各种元素的顺序，并且不以任何方式与源代码运算符的顺序进行连接。 但是我无法创建一个易失性集，也许我做错了什么？ 与任何局部优化一样，对外部函数的调用会强制编译器对全局数组强制执行所有准备好的操作，但这对解决方案来说太强了，对局部操作没有帮助。 嗯，可能什么也没做，您只需要考虑类似的功能，而不要使用集合在使用串行接口（即，它们的软件副本）的流之间传输信息。
可以得出一个一般性的结论：由于内存和运行时的成本过高，因此不建议将当前形式的位集用于资源有限的体系结构。 Github上有一个可能的修改，其中考虑了注释文本上的所有数据，每个人都可以使用它。 这个mod的创建历史将很快发布在哈布雷，有趣的时刻。
总而言之，有一点要说-数据仓库“正面”的实现，即使是在集合的优化版本上，也将需要N / 8字节的数据存储器（128个开关将需要16字节），并且尽管运算将需要O（1）时间，但乘数将是许多单位（甚至最多10个或更多）的MK周期。 因此，考虑到问题的要求并引入某些限制，我们可以提供数据存储的替代实现。
如果我们认为在任何时候都不能关闭一个以上的开关（我们将忽略所有其他开关，直到此时按下的按钮打开），那么我们可以绕过一个字节（前提是不超过256个开关）并且写入/读取将需要O（1）个处理器周期，并且乘法器将非常适中。
这种方法很容易扩展和存储有关同时关闭的n个开关的信息，但是您不应该使n太大，因为所需的内存量会增加，并且执行反转操作的时间会随着集合中元素数量的增加而线性增加，尽管它仍为O（1）与开关数量有关。 使用二叉树的三角实现为O（loq2（n）），可以显着减少指示的时间增加，但是对于小n来说，它并不是那么重要。 是的，令人怀疑的是，在搜索过程中计算下一个索引的复杂性是否会弥补简单迭代次数的减少。 此实现的缺点包括可能无法记录集合中的元素，应在调用程序中对其进行处理（我们拒绝立即更改缓冲区大小的选项，并且感到愤慨，这不适用于嵌入式解决方案）。
该方法的实现将在此处给出。