我决定认输。这是我的代码。它应该为单个块 512 位输入构建 SHA-2 算法的执行树，无需预处理。但是，我将其从 64 次迭代降低到 4 次迭代，因为遍历树从未完成 64 次迭代。即使在 4 次迭代中，它也会遍历 10,000 个节点——即使只分配了 1000 个节点，包括一堆常量，它们是叶子，甚至不计入遍历计数。此外，断言保证是非周期性的，如果它是周期性的，它就永远不会返回，不会永远等待然后返回。
我到底对这段代码做了什么，导致它需要永远遍历这么小的无周期树？
问问题
78 次
1 回答
2
嗯，这是可以预料的。树可能以非常紧凑的方式存储，但它有很多很多重复的部分。它非常大。
例如，考虑以下序列：
auto s0 = la.rotate(2) ^ la.rotate(13) ^ la.rotate(22);
现在，s0树下面有三个原始la表达式。
auto t2 = s0 + maj;
……那棵树进去了t2……
la = t1 + t2;
...la最终在循环结束时再次出现。所以，la现在（至少）有三个对la上一次迭代树的引用。下一次迭代将再次将其重复三次。而且一遍又一遍。由此我们可以得出最终树中原始实例的 3^64 个实例的下限la（即使存储中仅存在一个实例）。3^64 是 3.43368382 × 10^30，即大约 3 亿。
树的生成采用简单的路线，只是重用子树。另一方面，遍历函数最终会多次遍历同一个子树。
于 2012-05-17T10:17:14.630 回答