EIP-7939: 计算前导零（CLZ）操作码

用于计算 256 位字中前导零位数的操作码

摘要

引入一个新的操作码 CLZ(x)，它从堆栈中弹出 x，并将 x 中的前导零位数推送到堆栈。如果 x 为零，则推送 256。

动机

计算前导零（CLZ）是许多处理器架构（甚至是像 ARM 这样的 RISC 架构）中的原生操作码。

它是数学运算、字节运算、压缩算法、数据结构中的一个基本构建块：

• lnWad
• powWad
• lambertW0Wad
• sqrt
• cbrt
• 字节字符串比较
• 广义的calldata压缩/解压缩
• 位图（用于查找下一个/上一个设置/未设置位）
• 后量子签名方案

添加 CLZ 操作码将：

• 降低计算成本。
• 降低 ZK 证明成本。最快的已知 Solidity 实现使用多个动态按位右移 shr，这在证明时非常昂贵。在 SP1 rv32im 中，32 位右移的成本是 32 位乘法的 1.6 倍。
• 减小字节码大小。最快的已知 Solidity 实现包含几个大的常量，并且通常为了性能而内联。

规范

引入一个新的操作码：CLZ (0x1e)。

• 从堆栈中弹出 1 个值。
• 根据以下代码将一个值推送到堆栈：

/// @dev 计算前导零。
/// 返回最高有效位之前的零的数量。
/// 如果 `x` 为零，则返回 256。
/// 这是 Solidity 中已知的最快的 `CLZ` 实现，大约使用 184 gas。
function clz(uint256 x) internal pure returns (uint256 r) {
    /// @solidity memory-safe-assembly
    assembly {
        r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
        r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
        r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
        r := or(r, shl(4, lt(0xffff, shr(r, x))))
        r := or(r, shl(3, lt(0xff, shr(r, x))))
        // forgefmt: disable-next-item
        r := add(xor(r, byte(and(0x1f, shr(shr(r, x), 0x8421084210842108cc6318c6db6d54be)),
            0xf8f9f9faf9fdfafbf9fdfcfdfafbfcfef9fafdfafcfcfbfefafafcfbffffffff)), iszero(x))
    }
}

或者用 Python 表示，

def clz(x):
    """返回最高有效位之前的零的数量。"""
    if x < 0:
        raise ValueError("clz 对于负数未定义")
    if x > 2**256 - 1:
        raise ValueError("clz 对于大于 2**256 - 1 的数字未定义")
    if x == 0:
        return 256
    # 转换为二进制字符串并删除任何 '0b' 前缀。
    bin_str = bin(x).replace('0b', '')
    return 256 - len(bin_str)

或者用 C++ 表示，

inline uint32_t clz(uint32_t x) {
    uint32_t r = 0;
    if (!(x & 0xFFFF0000)) { r += 16; x <<= 16; }
    if (!(x & 0xFF000000)) { r += 8;  x <<= 8;  }
    if (!(x & 0xF0000000)) { r += 4;  x <<= 4;  }
    if (!(x & 0xC0000000)) { r += 2;  x <<= 2;  }
    if (!(x & 0x80000000)) { r += 1; }
    return r;
}

// `x` 是一个用 8 个 uint32 limbs 表示的 uint256 位数字。
// 此实现针对通过 rv32im 进行 SP1 证明进行了优化。
// 对于常规计算，它的性能与 `ADD` 类似。
inline uint32_t clz(uint32_t x[8]) {
    if (x[7] != 0) return clz(x[7]);
    if (x[6] != 0) return 32 + clz(x[6]);
    if (x[5] != 0) return 64 + clz(x[5]);
    if (x[4] != 0) return 96 + clz(x[4]);
    if (x[3] != 0) return 128 + clz(x[3]);
    if (x[2] != 0) return 160 + clz(x[2]);
    if (x[1] != 0) return 192 + clz(x[1]);
    if (x[0] != 0) return 224 + clz(x[0]);
    return 256;
}

操作码的成本为 3，与 ADD 相同。

理由

特殊的 0 情况

256 是 255 之后的最小数字。返回一个小数字允许以最小的额外字节码比较结果。

对于字节扫描操作，可以通过简单地计算 256 >> 3 来获得零字要跳过的字节数，结果为 32。

优先于 CTZ（计算尾随零）

通过使用 x & -x 分离最小位，可以使用 CLZ 轻松实现计算最低有效位。

但是，不可能用 CTZ 实现 CLZ。

Gas 成本

我们已经针对 intx 库中的 ADD 实现对 CLZ 实现进行了基准测试。CLZ 使用的计算周期数与 ADD 大致相同。

在平均和最坏的情况下，SP1 rv32im 优化变体使用的计算周期少于 ADD。

在 SP1 rv32im 中，256 位 CLZ 的证明成本低于 ADD。

向后兼容性

这是一个以前不存在的新操作码。

测试用例

PUSH32 0x000000000000000000000000000000000000000000000000000000000000000
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000100

PUSH32 0x8000000000000000000000000000000000000000000000000000000000000000
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000000

PUSH32 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000000

PUSH32 0x4000000000000000000000000000000000000000000000000000000000000000
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000001

PUSH32 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000001

PUSH32 0x0000000000000000000000000000000000000000000000000000000000000001
CLZ
---
0x00000000000000000000000000000000000000000000000000000000000000ff

安全注意事项

CLZ 是一个无状态操作码，在内存使用、计算和证明成本方面具有较低的最坏情况恒定成本。因此，它可以安全地免受拒绝服务攻击的利用。

版权

在 CC0 下放弃版权及相关权利。

Citation

Please cite this document as:

Vectorized (@Vectorized), Georgios Konstantopoulos (@gakonst), Jochem Brouwer (@jochem-brouwer), Ben Adams (@benaadams), Giulio Rebuffo (@Giulio2002), "EIP-7939: 计算前导零（CLZ）操作码 [DRAFT]," Ethereum Improvement Proposals, no. 7939, April 2025. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7939.