“熵，遍历源，多维消息空间，位，多义性，马尔可夫过程-所有这些单词听起来都很令人印象深刻，无论它们放置的顺序如何。 如果按正确的顺序排列它们，它们将获得一定的理论内容。 真正的专家有时可以在他们的帮助下找到解决日常实际问题的解决方案。”
约翰·皮尔斯（John PIRS）：“我看不到邪恶”
这篇文章充满了关于在资源有限的情况下对MK进行数学运算的微妙优化的讨论，以及对嵌入式软件开发各个方面的主观评估。
我警告那些没有被这个警告吓到的人。
在继续描述从整数中提取平方根的过程之前，先对平方进行求逆，然后乘以运算，再谈一下后者。
假设我们有机会将一个8位数字乘以一个8位数字，得到一个16位结果（8 * 8 = 16），那么如何基于该操作来实现16 * 16 = 32的实现。 显而易见的方法是将16表示为两个8的和。
(16)*(16)=(1(8)*256+2(8))*1(8)*256+2(8)) =1*1*256*256+1*2*256+2*1*256+2*2如果在结果表达式中我们将乘以256乘以左移8位，则得到一个完全有效的算法。 让我们估计一下实现所花费的时间-我们需要4个8 * 8 = 16的乘法和4个字节数32 + 32 = 32的4个加法。 对于MK型AVR，我们得到4 * 2 + 4 * 4 = 24个周期，但这是一个“前额”解决方案。 让我们尝试改善结果。 我们不需要4个而是3个加法和一个赋值的事实在某种程度上简化了这种情况，因为不需要对结果进行初始归零，但我们仍然没有考虑它，尽管这是必要的，总时间应为24 + 4 = 28个周期。 但是，如果考虑到前三项中存在移位（分别，我们的低（两个低字节）为零，并且没有必要将其添加到结果中），那么我们将不必添加4个字节，而是添加三个和两个字节，这将减少执行时间为1 * 2 + 2 = 4个小节，并获得20个小节。 此外，我们要注意一个事实，即第一项和最后一项完全不相交，这使我们可以用第一项的赋值代替结果的最高一半的清零，并将执行时间再减少2个时钟周期至18个。此外，还使用了体系结构功能，即存在寄存器传输命令配对，再保存两个小节，最终结果-16个小节，而不是原来的28个小节-很好。
类似的优化方法适用于操作32 * 32 = 32，可以将执行时间从预期的4 * 4 *（2 + 4）+ 4 = 100个时钟周期减少为（3 + 5 + 4 + 3）+（5 + 3） +3）+（4 + 3）+ 3 = 36小节，这还不错。 好了，在考虑了各种乘法选项后，我们注意到可以在3 + 3 + 3 = 9个周期中获得16 * 16 = 16。 请注意，所有这些考虑仅在假设有2个小节的操作8 * 8 = 16的情况下才有效，并且如果它不在目标MK上，则该操作的所有其他版本的执行时间肯定不会变快。
让我们总结一下执行乘法所需的时间（8 * 8 = 8 2，8 * 8 = 16 9，16 * 16 = 16 16，16 * 16 = 32 36），现在考虑原始问题。
我们需要从32位数字H中提取平方整数根，即找到最大的16位数字n，以使n * n <=H。 我们所有中学课程的人都知道逐次逼近平方根的方法（n =（N / n'+ n）/ 2），但是使用它时，我们将不得不对整数进行除法，这是一个非常耗时的操作。
因此，开发了其他计算方案，其中一种是按位逼近方法，在伪代码中如下所示：
- 初始值-> n = 0; b = 0x8000；
- 执行16次-> if（（n + b）*（n + b）> = H）n = n + b; b = b >> 1；
您可以立即估计在此选项上花费的时间16（结果的位数）*（2（循环的组织）+2（加法）+ X（乘法）+5（比较和解）+2（结果的修改）/ 2（平均值）半场）+2（位移）= 16 *（12 + X）。 您问为什么在公式X中而不是数字16中，结果是伏击在等待着我们，因为我们是用C而不是汇编器编写的。 事实是，在标准库中没有位深度变化的乘法运算，我们不能应用16 * 16 = 32，而是被迫使用32 * 32 = 32，这将导致X = 36而不是X = 16，最终数字为16 * 48 = 768个时钟周期，用于提取32位数字的平方根的整数值。
当然，这比牛顿法要好得多，但是要让我们看看可以做什么。
因此，很明显，大部分时间都花在了计算下一个乘法结果上。 当然，您可以在汇编器中重写它，并使用较便宜的乘法版本，得到16 *（12 + 16）= 448个滴答，但我们将保留此方法作为最后的选择。 更仔细地考虑该过程，可以看到我们不是自己计算随机数的乘法，而是计算前一个值的乘积并增加一点，从而知道前一个值的平方。 因此，我们可以诉诸基于公式（n + b）*（n + b）= n * n + 2 * n * b + b * b的差分方案。 乍一看，它看起来像是在嘲笑-我们需要做四件甚至是长数字（32位）的两个加法运算，而不是一个乘法。 但是让我们开始理解：考虑到b = b'/ 2很容易获得，我们已经有了n * n，b * b，就像b'* b'/ 4一样，类似地2 * n * b = 2 * n * b'/ 2。
出现以下计算方案：
- 初始值-> nn = 0; n = 0; b = 0x8000； bb = b * b;
- 重复16次-> if（nn + n + bb> = H）{n = n + b; nn = nn + bb + n}; bb >> 2; b> 1；
我们估计实施成本16 *（2（周期的组织）+12（分配和两次增加）+5（比较和解决方案）+（2（增加）+8（两次增加））/ 2（平均半场时间）+8 （向右移动2个）+2（向右移动）= 16 * 34 = 544个时钟周期，比不正确乘以32 * 32更好，但我们仍有储备。
它们是什么-我们要注意最昂贵的操作-添加和比较总共17个时钟周期，然后重做算法的主循环：
2.重复16次-> T = H-bb-n； 如果（T> = 0）{H = T; n = n + b）;}; bb >> 2; b> 1；
那么循环的执行时间将为16 *（2（循环的组织）+12（计算新差）+ +1（比较和解）+（（4（赋值）+2（加法））/ 2（平均半时间）+8 +2）= 16 * 28 = 448个周期，如果考虑到体系结构的特殊性，则可以再保存2 + 2 = 4 * 16 = 64个周期，并保持在不到400个周期内。
当使用正确的乘法16 * 16 = 32时，即使没有汇编程序，“纯C”，我们得到的结果甚至会更好。 但是，有一个很大的缺点-如果带乘法的版本中的所有内容都是直观的，则带差异方案且没有注释的变体会给人以黑魔法的印象，您应该选择。 还要注意，我们将度量的数量交换为中间变量的额外内存，这种情况通常会发生。
必要的注意-与乘法相比，我们没有获得可观的（有时）收益，因为我们可以快速实现8 * 8 = 16。 如果MK中不存在（发生这种情况）或速度不那么快（也发生这种情况），那么差异方案将变得快很多倍，因为它仅使用标准的加法和移位操作，这保证在任何MK中都可以进行。
似乎它不会更好地工作，但是事实证明，仍然存在提高算法性能的储备。 让我们尝试使用另一种经典的加速方法-分而治之。 如果首先从参数的前半部分提取平方根，然后对其进行优化，该怎么办？ 首先，我们证明这从根本上是可能的。 实际上，我们以H = H'<< 16 + H''的形式表示自变量，并以n = n'<< 8 + n''的形式表示结果。 由于n''<256，因此其平方显然小于数字n = n'<< 8 + 256 =（n'+ 1）<< 8的平方。 因此，结果的最高部分不超过自变量最高部分的平方根。
这种方法的实现留给好奇的读者。
这种方法将为我们带来什么，因为迭代的总数将保持不变-我们可以使用较短长度的数字进行迭代的前半部分，这将减少时间成本。 这种方法可以应用于具有乘法和差分变量的变量，总增益将达到总执行时间的四分之一。
必要的注意-这种方法的适用性一点都不明显，当为MK（例如AVR）实施时，确实会发生执行加速，但是对于某些体系结构（例如，对于x86），运行速度出乎意料地出现了。 显然，在这种体系结构中使用非本地数据（16位）在时间上比使用本地（32位）要贵得多。 我没有进行深入研究，但是事实确实发生了，我应该报告它，以避免造成误解。
但这还不是全部。 既然我们已经走上了分离和统治的道路，那为什么不走得更远-从最老的树开始逐步从树的根中提取根（在我们的例子中，从年轻的树开始适得其反）。 算法方案是相同的-我们在当前结果中添加下一部分比特，然后尝试将下一位添加到结果中，检查是否超出了根值。 特殊之处在于，我们只能检查参数的高位，直到获得低位。
在实现时，我们使用了另一个技巧-而不是将减去的数字向右移动，而是将减量的参数向左移动，含义没有改变，并且速度提高了。 它的增加是由于两个因素-1）仅减去16位数字就足够了（有一个特殊性，必须加以考虑，但我们正在考虑案例研究vout）； 2）我们不需要移动下一位的平方，因为它总是等于一。 但是，您必须为这个世界上的所有事情付出代价，我们将向左扩展扩展差（6个字节），每个时钟偏移2位。 我们看一下伪代码
- 初始值-> n = 0; H1 = 0;
- 重复16次->（H1，H）<< 2; T = H1-n-1; 如果（T> 0）{H1 = T; n = n + 2}; n << 1;
并评估执行时间，得到16 *（12（扩展的移位）+4（计算差）+1（解决方案）+2（分配）+1（增加）+2（移位））= 16 * 22 = 352个小节，结果接近完美。 实施此选项时，存在一些陷阱，我还是把这个问题留给好奇的读者（好吧，他得到了这份工作）。
好吧，在促使我写这篇文章的部分的结尾。 有一个绝对绝妙的McuCpp库，由Anton Chizhov编写，其中基于loki类的作者身份，Andriescu非常优雅（就优雅而言，可以将其应用于C ++模板），并且可以使用<a«
pins Mcucpp »我非常尊重提到的作者（他们俩），最近，在与情况有关的情况下，我将在稍后对此进行讨论，我查看了该库的资源并再次表示赞赏。
但是，在其他文件中，我看到了template_utils.h，其中实现了一些辅助例程，其中包括32位数字的整数根。 它使用最简单的带乘积的顺序逼近算法的事实并不令人恐惧，因为该算法的速度并没有损失那么多，但是在可理解性方面，它给出了很多要点，但仍然可以取胜。 但是我真的不喜欢它在性能方面有些不准确的事实，因为“孩子们可以看到它”。 不准确性在于用32位表示所选的数字，因为我们深知32位数字的根不会超过16位，因此为什么我们需要移位零字节。 当编译器本身永远不会猜测要执行优化并应该提供帮助时，就是这种情况。
明显的功能转换
static inline uint32_t sqrt(uint32_t value) { uint16_t result = 0; uint16_t add = 0x8000; for (uint8_t i = 16; i !=0; ++i) { uint32_t rootGuess = result | add; uint32_t guess = rootGuess * rootGuess; if (value >= guess) { result = rootGuess; } add >>= 1; } return result; }
允许我们在移位后节省2个周期，并在每个周期上创建一个下一个因子时节省2个周期，以指示的形式组织该周期又需要另外4个周期（我知道编译器可以为我们做这样的优化，但是为什么不明确地帮助它），这对于纯修饰性代码更改（至少不影响其可理解性）非常有用。
后来的注释-有一条评论使我认为它会更正确
for (uint_fast8_t i= ...)
谢谢Oleg的帮助。
蛋糕上的樱桃是从正下方的符号号中提取整个平方根的功能，它声称√-1= 65635 = -1。另一方面，为什么不比其他任何结果都糟糕，我们没有例外原因在MK中，并且不存在负数的整个平方根。
好吧，关于我为何转向安东·奇佐夫图书馆的结论。 我最近收到一则关于MAX的国内RTOS帖子的提示，该帖子的名称为MAX（MultiAgent相干系统）-参见其创作者所宣传的帖子的标题，并移植到Milander制造的MK上。 注意-此帖子绝不是促销材料，读者很快就会明白。 前面提到的操作系统的mcucpp作者使用了环形缓冲区的实现（完全没有削弱Anton库的优势，我必须说，这部分不是参考，这仍然是一种软的表述，我在另一篇文章中写过，我将不再发表。） 由于我与Milander的生产设施紧密合作，因此使我感兴趣的材料也随之而来，我链接到开发人员网站。
从这里开始，雅罗斯拉夫纳的下一声呐喊。
去年，当首次宣布创建国内RTOS时，我从该站点下载了该软件产品的说明，但不知何故，我的手没有伸手去拿。 根据活动的性质，我必须处理家用组件（我了解得足够多...），因此拥有合适的软件将是一件很不错的事情。 记得去年的发行版中，该公司的负责人谈到开发上花费了数百万卢布，以及开发此软件产品的大型团队时，我决定看一下可免费下载的试用版，在这里我分享结果。
首先，半年的描述量几乎减少了一半（从115页减少到55页），如果欢迎使用带有屏幕截图描述从“程序描述”中启动第三种产品的过程的应用程序消失，则不希望出现这些材料（对于我花了（虽然不是很重要，但仍然花时间和金钱）在诸如《操作指南》之类的文件中，我为此感到困惑。 此外，在文档的第一句话中，我们看到了与事实的坦率偏离，因为RTOS本身无意以任何方式``创建程序''，由于某些原因，作者在文档的先前版本中不允许自己发表此类声明，因此可以感受到营销服务的影响。 它还提供了一个描述，如果描述曾经位于根目录的/ docs文件夹中，并且这是合乎逻辑的，那么现在它已隐藏在/ toolchain / macs / docs中，就像他们在我年轻时所说的那样，“每个人都以自己的方式生气”，我们继续。
我开始看一下描述，看一下源代码（试用版中已包含该代码），而我困惑地发现没有适用于此OS的外围设备驱动程序。 首先，我建议这是该试用版的功能，然后在论坛上来自开发人员的信息中，我发现确实没有驱动程序，但他们正在努力。 自为MK发行操作系统以来，已经有六个多月的时间（六个月，卡尔，实际上接近一年），并且他们致力于驱动程序。 当然，或者正如他们所说，毫无疑问，任何第三种产品（文件系统，网络堆栈，USB堆栈）都无法言喻。 作者关于MK的软件开发需求的一个有趣主意再次引起了人们的注意。
也就是说，已声明的OS（其突出特点是在多控制器系统内组织交互）并不具有组织这种交互的本地方法。 最重要的是-我们拥有任务管理，实际上是一个sheduler，最少的时间服务和同步任务的方式，而且，至少可以这么说。 好的，我们将进一步研究，即使使用这样的组件，也可能会找到有趣的解决方案，尤其是考虑到在一个站点（而非制造商的公司）上，我看到了对该操作系统源代码的“审查”。 该文档说，该软件产品不使用第三方（导入）组件，并且是原始的，因此有必要确保。
第一个观察结果是，如果您使用源代码包中包含的原始ARM文件将其移植到特定的Cortex-M0架构（1986 BE1T），那么这与使用第三方（导入的）文本片段非常相似-我个人认为这是用途，但是我可能一无所知。 其次，sheduler和相关任务管理组件的源代码确实是原始的并且没有类似物（至少我不知道），但是当我回想起电影《 Yambuya的邪恶之魂》中关于老巫师的短语时，这就是一种独创性。伟大的猎人：“割下耳朵，煮熟并吃掉-你猜到了吗？”
我将尝试解释-在一般的OS设计中，尤其在RTOS的设计中，最复杂的问题之一是确保系统中的所有进程都能访问共享资源的问题-处理器运行时。
事实是，设计不正确的系统（以及编写较差的任务）会阻止所有优先级较低的任务的执行，这肯定会使程序员感到困惑。这并不是要执行诸如中断控制之类的被禁止的操作（这是一个单独的讨论主题，并且在简单的MK框架中根本没有解决方案，尽管该操作系统的作者声称已使用MPU解决了此问题），而是关于连续执行而无需等待。这个问题是众所周知的，可以通过不同的方式解决，有关此主题的文献很多，通常，使用一组具有不同优先级的任务队列和经过修改的sheduler。这需要一定的成本来组织访问时间为O（1）的队列，例如，在FREE-RTOS中，当试图设置20个以上的优先级时，程序员会从编译器中得到一个困惑的问题，以及他是否真的需要那么多（即使这个问题也是如此）。有一个肯定的答案，如果不修改源代码，您将无法获得那么多的优先级）。因此，我惊讶地发现所讨论的操作系统最多允许您拥有60个优先级（甚至更多）。当我查看源代码时，惊喜零星散落。作者无需使用具有相同优先级的单独任务队列，而是使用一个队列（也有第二个阻塞任务队列）准备执行任务，这有助于节省内存（可能是这种解决方案的目的），因为- 将任务添加到队列的操作变为O（n）并且
- 这使得不可能使用修改过的sheduler-在我看来，20 *（3 * 4）= 240字节的RAM有点贵。该解决方案异常原始，但是，从我的角度来看，这是其唯一的优势。
总体而言，我仍然不知道作者将要花什么钱（但根据论坛的判断，他们仍未决定是否要这样做），以及哪些特定的解决方案和功能可以使该软件具有如此响亮的名字。尤其要考虑许多MK供应商（当然是进口的）免费提供多少软件。在浏览公司论坛以寻找答案时，我看到了对先前提到的mcucpp软件产品的引用（据称MAKS的作者受到Chizhov的想法的启发-3倍公顷），其中我发现了上述的一个小缺陷。本部分的结论是，如果以类似的方式实施软件领域中的其他替代进口决定，并且结果具有相似的质量，那么在我看来，构建家用嵌入式系统的前景就很难确定。总之，我想参考所提及的MK-Milander的公司开发人员和制造商的手册（不，不是OS开发人员，我什至不想在优秀开发人员旁边提及它）。您可以制作出优秀的微控制器（我不会说谎，它们的参数不如外国类似物，但也不致命），例如，一次（2013年）BE1T几乎是所有同学中的佼佼者，但在2019年的院子里，那时很多人都赶上了它。并超过了。但是，如果公司生产的优质MK没有：- ( , ) ( , , , , ),
- ( ),
- () 2,
- HAL, CMSIS (- ),
- ,
- ,
- (3rd part), ,
- ,
- ,
- , (, , ..) « »,
- , , ( , , MIT , « »), , (?).
当然，所有这些都不是单独出现的，而是要花钱的，但是在我看来，您这样水平的公司可以负担5个人六个月的工作来创建所有上述内容（第10条，也许第10条除外，尽管现在所有这些意义重大）许多MK小型制造商都有自己的IDE）。如果实现了这一点，那么土的外观就会消失，因为诸如这篇文章中描述的操作系统之类的工艺品的出现。尽管很可能我不了解某些东西，并且实际上并不是那么简单，但如果真的如此，那真是可惜。如果我的笔记看起来过于刺耳，我谨向您致歉，我不想冒犯您（Milander）。