[OPENPPP2] ssea 算法详解（中文）

ssea 算法详解中文语言切换:English Version | README (EN) | README (CN)本文档覆盖ppp/cryptography/ssea中的每一个算法在本库中对齐镜像标量实现、SIMD 实现或为何不适用 SIMD的形式化论证、所选择方法的可行性证明、实测基准、以及边界与错误语义。所有非标量路径均已验证与标量参考在每个输入长度 1…100000上逐字节一致见tests/测试套件。1. shuffle_data / unshuffle_data算法for i in [0, size): j (i ^ key) % size; swap(data[i], data[j])unshuffle_data以逆序运行同一循环swap 序列是自身的逆每个 swap 是对合逆序运行即还原组合。标量实现shuffle_data_scalar/unshuffle_data_scalar— 1:1 移植。SIMD 可行性论证不适用目标索引j (i ^ key) % size依赖 i 的32 位模除运行时模数—不存在闭式向量公式。每次 swap 访问两个数据依赖的随机内存位置。SIMD 面向连续流随机置换受内存延迟约束任何 SIMD gather/scatter 原语仍按元素逐一加载/存储 — 相对标量 swap 无吞吐收益。复杂度 O(n) 随机访存无可开发的数据级并行。结论标量是正确选择SIMD 无法帮助。优化标量2 的幂sizej (i ^ key) (size - 1)以 AND 取代 32 位div20-30 周期。2^k 尺寸实测 1.8-2.9x。尺寸标量优化加速256839 MB/s1505 MB/s1.79x4096853 MB/s2468 MB/s2.89x65535非 2 幂789 MB/s834 MB/s1.06x2. delta_encodeSSE2 约 8xAVX2 约 10x算法out[0] in[0] - kf; out[i] in[i] - in[i-1] (mod 256)每个输出字节只依赖当前与前一个输入字节 —数据并行模式。SSE2 实现16 字节/轮约 6 条指令a loadu(in i) // [in[i]..in[i15]] prev pslldq(a, 1) | prev_last // [in[i-1], in[i]..in[i14]] out psubb(a, prev) // 模 256 减法 prev_last srli_si128(a, 15) // 下一块需要的 in[i15]prev_last首块仅保留kf的低字节pand 0xFF—cvtsi32_si128写入 4 字节负值/大 kf 时掩码是必须的。证明pslldq(a,1)[j] a[j-1]故prev[j] in[ij-1]psubb为模 256 减法与标量Byte运算一致。首块以in[-1] ≡ kf (mod 256)匹配out[0] in[0] - kf。边界语义空/空指针 → 返回 0。尾 16 字节标量处理prev_byte in[i-1]由主循环延续。3. delta_decodeSSE2 约 8xAVX2 约 8.7x算法out[0] in[0] kf; out[i] out[i-1] in[i] (mod 256)这是前缀和— 串行依赖链但可并行化。SSE2 实现Hillis-Steele 扫描16 lanep a p p pslldq(p, 1) // 跨度 1 p p pslldq(p, 2) // 跨度 3 p p pslldq(p, 4) // 跨度 7 p p pslldq(p, 8) // 跨度 15 - p[j] sum(in[0..j]) out p carry // carry 上一块末字节 carry out[15] // srli_si128(15) cvtsi128_si32 提取方向扫描需要前一个字节低地址方向必须用pslldqslli。用psrldq会读到下一个字节产生右向和 — 错误的前缀。证明模加法满足结合律块内前缀p[j] Σ in[0..j]以对数深度4 轮跨度 124815精确计算模 256跨块进位out[15]精确链接各块与标量递推一致。边界语义同 encode空/空指针 → 0尾标量acc延续。4. base94_encodeSSSE3 pshufb1.4-4.4x算法b (byte - kf) 0xFF b 93 : 输出 1 字符 0x20 b b 93 : 输出 2 字符 0x20 (b/93 92), 0x20 (b%93)说明免除法 SIMD 形式因b ∈ [93,255]b/93 ∈ {1,2}— 逃逸首字符恒为}(0x7D) 或~(0x7E)hi 0x7D (b 186) lo b - 93*(b93) - 93*(b186) 0x20 // b%93 0x20每字节输出顺序为[hi, lo]首字符在前余数在后。每字节输出长度L[i] 1 (b93)使输出位置数据依赖→变长展开。为何需要 SSSE3 pshufb可行性证明展开是字节 gatherout[pos[i]] lo[i]pos[i]为 L 的前缀和。纯 SSE2没有字节级任意重排指令pshufb是 SSSE3 引入替代方案可证明更差逐孔移位链O(孔数) 次psrldq mask or≈ 24 ops/16B 且掩码数据依赖 — 比标量还差SWAR 乘法压缩~20 ops/16B 掩码相关的魔术常数 — 复杂且更慢。选择以 8 位展开掩码索引预计算 256-entry 表 一条pshufb为本库采用的方法计算核保持 SSE2。实现8 输入字节/轮b8 loadl(ini); b8 psubb(b8, kf) // b byte - kf biased pxor(b8, 0x80) // 无符号比较偏置 L1 pcmpgtb(biased, 92^0x80) // b 93 L2 pcmpgtb(biased, 185^0x80) // b 186 lo b8 - (L193) - (L293) 0x20 // b%93 0x20 hi 0x7D (L21) // } 或 ~ ex punpcklbw(hi, lo) // [hi0,lo0,hi1,lo1,...] mask movemask(L1) 0xFF // 位 i 第 i 对为 2 字符 out16 pshufb(ex, ENCODE_TABLE[mask]) // gather store 16 字节; op 8 popcount(mask)ENCODE_TABLE[m] 每对的源索引2 字符对取[hi, lo]1 字符对取[lo]其余为垃圾按长度计数截断。边界语义两遍先长度后写入保持缓存友好尾 8 字节标量。空/空指针 → 错误语义0/nullptr。5. base94_decodeSSSE3 pshufb1.3-3.8x算法ch 0x20, offset ch - 0x20 94 (否则报错) offset 93 - 逃逸对: v (offset-92)*93 next_offset (校验) 输出字节 v kf说明逃逸起始 iffch 0x7D配对值v 93 93*(ch0x7E) next - 0x20。每个逃逸对只删除其续字符输出位置 i - (之前的逃逸数)—与 encode 镜像的变长压缩同一 256-entry 表索引用2*i匹配punpcklbw(v,v)重复布局。校验字符 0x20、 0x7E、续字符偏移 93、~ 续偏移 69 →v 255以偏置字节pcmpgtb向量化任一违规回退标量参考错误语义精确保留。跨块处理位置 7 的逃逸消费字节 8下一块首字节。删除掩码进位del (esc 1) | carry标量尾从i carry开始跳过被消费字节。边界语义输入 16 字节 → 直接标量参考SIMD 开销大于收益。截断逃逸、字母表外字符、值溢出均与标量一致地返回失败。6. base94_decimal整数 - Base94 字符串算法uint64 - 字符串反复/94与%94≤ 11 位反转。字符串/字节 - uint64n n*94 数字链。SIMD 可行性论证不适用串行依赖每一位依赖上一位的余数/累加值 — 无并行形式。SSE2 无 64 位整数除法%94所需。数据极小全部输入/输出仅 8…11 字节SIMD 初始化加载/广播/查表超过总工作量。无批量场景每包头部一次转换无法摊薄。结论标量是唯一合理选择。已用边界值0、1、93、94、94²±1、UINT64_MAX、20 万次随机往返、错误路径验证。7. random_next / lcgmodPRNG算法三步 LCGL(x) 1103515245*x 12345 (mod 2^32)的 16 位折叠组合result ((t116)0x7FF)20 ^ ((t216)0x3FF)10 ^ ((t316)0x3FF)SIMD 可行性论证不适用单次调用是单 seed 的 3 步串行折叠— 调用内无可并行内容。批量场景原则上存在并行 LCG 跳步但见 §8生产调用模式kf random_next(kf)以返回值覆盖 seed序列成为非线性 fold 链跳步不适用。结论标量批量层面的分析属于 §8。8. masked_xor / masked_xor_random_nextmasked_xor定键对每个 32 位字异或常量kf尾16/8 位。SSE216 字节一次pxor指令数约降 16 倍。实测 0.65-0.96x — MSVC /O2 已将标量循环自动向量化到同宽度达到内存带宽约 70 GB/s。手动 SSE2 版本保留作可移植性参考但 MSVC 下推荐标量。结论编译器已覆盖保持标量。masked_xor_random_next每字 LCG 密钥流对每个 32 位字: kf random_next(kf); word ^ kf 尾 (16/8 位): word ^ kf (不再更新)密钥流语义random_next将推进后的 seed 写入*seed并返回折叠值随后该值被赋回kf—覆盖了 seed。因此密钥流是k_{n1} fold(k_n)—非线性 fold 链fold 含移位/XOR。LCG 跳步L3幂可证明无法重现此序列。故密钥流严格串行无法并行。实现标量密钥流生成 SSE2 批量 XOR每轮 4 字。实测约 1.0x —密钥流占主导XOR 批处理增益有限。结论可接受对该精确语义并行密钥流数学上不可能。边界语义零长度 → true负长度 → false。尾键使用末字后不更新与标量完全一致已用 1…100000 全长度 多 kf 验证。汇总表#算法标量SIMD实测选择的方法1shuffle/unshuffleref不适用已论证2 幂 1.8-2.9xAND标量 2 幂 AND2delta_encoderefSSE2 及以上AVX2 最优约 8xAVX2 10xSSE23delta_decoderefSSE2 及以上AVX2 最优约 8xSSE24base94_encoderef/LUTSSSE3 及以上AVX2 最优1.4-4.4xSSSE35base94_decoderefSSSE3 及以上SSE4.1 最优1.3-3.8xSSSE36base94_decimalref不适用已论证—标量7random_next/lcgmodref不适用已论证—标量8masked_xorrefAVX2/标量AVX2 2x标量优于 128 位AVX2 否则标量9masked_xor_random_nextref密钥流标量 XOR SSE2约 1.0x混合正确性保证每条 SIMD 路径与标量参考在全部长度 1…100000、边界组合、错误路径、canary越界检测、未对齐偏移、多 kf/key 下逐字节一致 —见tests/测试套件。