仅使用整数常量表达式计算sqrt(SIZE_MAX + 1),以满足奇怪的ABI

Question

OpenBSD的C库有一个名为reallocarray(3)的扩展realloc(array, size*nmemb),如果乘法溢出,它就不会爆炸. 该实现包含此片段:

/*
 * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
 */
#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))

在Programmers.SE上,该计算的修改版本因技术错误而受到谴责. 4显然应该是CHAR_BIT/2,但这不是唯一的问题.假设一个不常见的ABI,其中size_t有填充位.(这并非荒谬地令人难以置信:考虑一个具有32位寄存器但具有24位地址空间的微控制器.)然后SIZE_MAX小于1 << (sizeof(size_t)*CHAR_BIT)[在无限精度算术中]并且计算错误.

所以,问题:你能否floor(sqrt(SIZE_MAX+1))仅使用C99整数常数表达式算法进行计算,除了C99要求以及你可以从中学到什么之外,不做任何关于ABI的假设<limits.h>？注意,SIZE_MAX可能相等UINTMAX_MAX,即可能没有任何类型可以表示SIZE_MAX+1没有溢出.

编辑:我认为 SIZE_MAX需要为2 ^ñ  - 1为正整数Ñ,但不必然是形式2的^2n个  - 1 -考虑S/390中,一个其的的ABI有一个31位的地址空间.因此:如果sqrt(SIZE_MAX+1)不是整数,则所需的结果(给定如何使用此常量)具有floor()真值.

Answer 1

该常量SIZE_MAX是非负的并且类型为size_t。为了简短起见，我将定义：

  #define S SIZE_MAX  

正如您所指出的，数学值S+1超出或可能超出任何整数类型的范围。
我将写出S1的数学值S+1。
如果我们考虑 的对数（如果需要的话，以 2 为底）S1，那么我们有：

 logarithm(sqrt(S1)) == (1.0/2.0) logarithm(S1)

另一方面，在几乎可以肯定的每种现实情况下，我们都会将其S表示为仅具有位的二进制数1。b一般来说，这个位数是乘以CHAR_BIT2 的幂再乘以 CHAR_BIT：16、32、64、128...我将用 表示该幂的指数p。因此，对于 CHAR_BIT == 8，我们有：

16 == CHAR_BIT * 2 ----> p == 1
32 == CHAR_BIT * 4 ----> p == 2
64 == CHAR_BIT * 8 ----> p == 3

现在我们有：

logarithm(S1) == b == CHAR_BIT * (2 ** p)   (I am denoting with ** to the "power math. operator").

logarithm(sqrt(S1)) == logaritm(S1) / 2.0 == CHAR_BIT * (2 ** p) / 2.0 == CHAR_BIT * (2 ** (p - 1))

通过假设或知道 中的每一位size_t仅用于表示整数的位，我们可以得到以下等式： 的某些（未知）值p：

sizeof(size_t) == b == CHAR_BIT * (2 ** p)

我们可以假设，对于 2014 年的最新技术， 的值p <= 5（您可以在接下来的内容中将这个神奇的数字 5 增加到更大的值）。

现在，考虑以下表达式，旨在“搜索并找到” 的值b，假设p <= 5：

#define S_1 ((size_t)1ULL)
#define b (sizeof(size_t))
#define bitexpr(p) ((size_t)(CHAR_BIT * (S_1 << (p))))
#define expr(p) ((size_t) (S_1 << (p)))
#define exp2_expr_1(p) ((size_t)(S_1 << bitexpr(p-1)))
// SRSM() stands for: Square Root SizeMax
#define SRSM  ( \
    (expr(1)==b)? exp2_expr_1(1) :             \
        (expr(2)==b)? exp2_expr_1(2) :         \
            (expr(3)==b)? exp2_expr_1(3) :     \
              (expr(4)==b)? exp2_expr_1(4) :   \
                (expr(5)==b)? exp2_expr_1(5) : \
                   (size_t)0  /* Error! */     \
    ) /* end-of-macro*/

实际上，宏SRSM带来了 的平方根S+1，但我想您可以弄清楚如何处理这个数字。

这里重要的是， 的平方根可以通过使用纯整数常量表达式SIZE_MAX来获得。

如果你愿意，“神奇”的数字 5 可以换成另一个数字。

一个更通用的方法，旨在解决任意情况，在任何可能符合标准的机器上，它会更复杂。
本文中使用的方法与 has 的值无关CHAR_BIT，但它使用字节数是 2 的幂。

编辑：我稍微改变了“搜索”的方法，从 1 开始，然后逐渐增大，以避免与<<运算符和大数字可能的“错误”匹配（人们永远不知道......）。现在，第一场比赛肯定是正确的。