第4期 杨先伟，等：随机序列的扑克检测优化研究 .517, dtsc()函数，该指令或函数返回CPU时钟周期值， //扑克测试优化后代码 按现代CPU的时钟频率计算，此计数器可精确到纳 int poker_test(BYTE p_u8,int n 秒级。两次RDTSC指令返回的时钟周期之差再除 以CPU频率，即可得到以s为单位的耗时值。 double v; 原算法和优化算法（算法1）对1000个样本进 BYTE p_bound p_u8 n/8,d; 行检测的性能统计结果见表3。 u32c4[16]={0},c8[256]={0}; 表3算法性能对比 while(p_u8 p_bound Table 3 The performance comparison of two algorithms 性能对比 原算法 算法1 d=*P_u8++; 耗时/s 2.244 0.236 c8[d]+: 速度比 1:1 9.508:1 c4[d4]++; 理论评估时只估算了最重要也最耗时的步骤 c4[d&0xf]++: 1),略去了后面的步骤的耗时。虽然步骤2)的计算 过程和原算法一样，但优化算法对步骤3)也做了相 /m=8时计算统计量 应的优化。实验的结果表明，优化算法通过充分利 v=poker_get_statistics(8,n,c8); 用CPU字长一次处理多个比特，优化整合算法流程 if(v>=POKER_BOUND_M_8) 减少不必要的计算，精简统计量的计算和判断过程 的技术方式和方法，的确可以显著地提升扑克检测 return -8; 的检测性能，且检测速度可提升9.5倍左右。 / 此外，算法性能提升显著的另外一个重要原因 /m=4时计算统计量 是扑克检测中的参数m取值较为特殊，m=8恰好 v=poker_get_statistics(4,n,c4); 是一个字节，m=4恰好是将一个字节拆分为两个 if(v >POKER_BOUND_M_4) “半字节”。这使得优化算法基于字节的处理方式 得到了淋漓尽致的发挥。 return -4; 6 结论 return 1; 本文对我国随机性检测规范采用的扑克检测算 } 法进行优化实现。通过充分利用CPU字长一次处 //扑克检测计算统计量，n为序列比特长度 理多个比特，优化整合算法流程减少不必要的计算， /m为参数，P_ct为子序列频数 精简统计量的计算和判断过程的技术方式和方法， double poker_get_statistics(int m,int n,u32 可以显著地提升扑克检测的检测性能，实验结果表 p_ctr) 明检测速度可提升9.5倍左右。因此，建议在实际 检测中采用软件实现时使用本文提出的扑克检测快 int i,blk_sz,pow_m; 速实现方式以提高扑克检测的检测效率。NIST和 double blk_sz_inv,sum; 我国的随机性检测规范还有很多别的检测项，其中 sum=0.0: 还有很多检测项可以做必要的性能优化，这将是今 pow_m 1 <<m; 后工作的一个研究方向。另外，怎样利用并行化技 blk sz n m; 术（如多线程技术，SMD指令、GPU运算）快速实现 blk_sz_inv 1.0 blk_sz; 这些检测项，也是今后研究的另一个方向。 for(i 0;i<pow_m;i++) 附录优化算法的代码 sum +p_ctr[i]p_ctr[i]blk_sz_inv; 本节列出优化算法（算法1）的标准C代码。其 中poker_.test函数为扑克测试优化后的功能实现函 return sum pow_m )-blk_sz; 数，poker_.get_statistics函数为扑克检测中计算统计 量的函数。ｒｄｔｓｃ（）函数，该指令或函数返回 ＣＰＵ 时钟周期值， 按现代 ＣＰＵ 的时钟频率计算，此计数器可精确到纳 秒级。 两次 ＲＤＴＳＣ 指令返回的时钟周期之差再除 以 ＣＰＵ 频率，即可得到以 ｓ 为单位的耗时值。 原算法和优化算法（算法 １）对 １ ０００ 个样本进 行检测的性能统计结果见表 ３。 表 ３ 算法性能对比 Ｔａｂｌｅ ３ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ 性能对比 原算法 算法 １ 耗时／ ｓ ２．２４４ ０．２３６ 速度比 １：１ ９．５０８：１ 理论评估时只估算了最重要也最耗时的步骤 １），略去了后面的步骤的耗时。 虽然步骤 ２）的计算 过程和原算法一样，但优化算法对步骤 ３）也做了相 应的优化。 实验的结果表明，优化算法通过充分利 用 ＣＰＵ 字长一次处理多个比特，优化整合算法流程 减少不必要的计算，精简统计量的计算和判断过程 的技术方式和方法，的确可以显著地提升扑克检测 的检测性能，且检测速度可提升 ９．５ 倍左右。 此外，算法性能提升显著的另外一个重要原因 是扑克检测中的参数 ｍ 取值较为特殊，ｍ ＝ ８ 恰好 是一个字节，ｍ ＝ ４ 恰好是将一个字节拆分为两个 “半字节”。 这使得优化算法基于字节的处理方式 得到了淋漓尽致的发挥。 ６ 结论 本文对我国随机性检测规范采用的扑克检测算 法进行优化实现。 通过充分利用 ＣＰＵ 字长一次处 理多个比特，优化整合算法流程减少不必要的计算， 精简统计量的计算和判断过程的技术方式和方法， 可以显著地提升扑克检测的检测性能，实验结果表 明检测速度可提升 ９．５ 倍左右。 因此，建议在实际 检测中采用软件实现时使用本文提出的扑克检测快 速实现方式以提高扑克检测的检测效率。 ＮＩＳＴ 和 我国的随机性检测规范还有很多别的检测项，其中 还有很多检测项可以做必要的性能优化，这将是今 后工作的一个研究方向。 另外，怎样利用并行化技 术（如多线程技术、ＳＩＭＤ 指令、ＧＰＵ 运算）快速实现 这些检测项，也是今后研究的另一个方向。 附录 优化算法的代码 本节列出优化算法（算法 １）的标准 Ｃ 代码。 其 中 ｐｏｋｅｒ＿ｔｅｓｔ 函数为扑克测试优化后的功能实现函 数，ｐｏｋｅｒ＿ｇｅｔ＿ｓｔａｔｉｓｔｉｃｓ 函数为扑克检测中计算统计 量的函数。 ／ ／ 扑克测试优化后代码 ｉｎｔ ｐｏｋｅｒ＿ｔｅｓｔ（ＢＹＴＥ ∗ｐ＿ｕ８， ｉｎｔ ｎ ） ｛ ｄｏｕｂｌｅ ｖ； ＢＹＴＥ ∗ｐ＿ｂｏｕｎｄ ＝ ｐ＿ｕ８ ＋ ｎ ／ ８， ｄ； ｕ３２ ｃ４［１６］ ＝ ｛０｝， ｃ８［２５６］ ＝ ｛０｝； ｗｈｉｌｅ（ ｐ＿ｕ８ ＜ ｐ＿ｂｏｕｎｄ ） ｛ ｄ ＝ ∗ｐ＿ｕ８＋＋； ｃ８［ ｄ ］＋＋； ｃ４［ ｄ ≫ ４ ］＋＋； ｃ４［ ｄ ＆ ０ｘｆ ］＋＋； ｝ ／ ／ ｍ ＝ ８ 时计算统计量 ｖ ＝ ｐｏｋｅｒ＿ｇｅｔ＿ｓｔａｔｉｓｔｉｃｓ（８， ｎ， ｃ８）； ｉｆ（ｖ ＞ ＝ ＰＯＫＥＲ＿ＢＯＵＮＤ＿Ｍ＿８） ｛ ｒｅｔｕｒｎ －８； ｝ ／ ／ ｍ ＝ ４ 时计算统计量 ｖ ＝ ｐｏｋｅｒ＿ｇｅｔ＿ｓｔａｔｉｓｔｉｃｓ（４， ｎ， ｃ４）； ｉｆ（ｖ ＞ ＝ ＰＯＫＥＲ＿ＢＯＵＮＤ＿Ｍ＿４） ｛ ｒｅｔｕｒｎ －４； ｝ ｒｅｔｕｒｎ １； ｝ ／ ／ 扑克检测计算统计量，ｎ 为序列比特长度 ／ ／ ｍ 为参数，ｐ＿ｃｔｒ 为子序列频数 ｄｏｕｂｌｅ ｐｏｋｅｒ＿ｇｅｔ＿ｓｔａｔｉｓｔｉｃｓ（ｉｎｔ ｍ， ｉｎｔ ｎ， ｕ３２ ∗ ｐ＿ｃｔｒ） ｛ ｉｎｔ ｉ， ｂｌｋ＿ｓｚ， ｐｏｗ＿ｍ； ｄｏｕｂｌｅ ｂｌｋ＿ｓｚ＿ｉｎｖ， ｓｕｍ； ｓｕｍ ＝ ０．０； ｐｏｗ＿ｍ ＝ １ ＜＜ ｍ； ｂｌｋ＿ｓｚ ＝ ｎ ／ ｍ； ｂｌｋ＿ｓｚ＿ｉｎｖ ＝ １．０ ／ ｂｌｋ＿ｓｚ； ｆｏｒ（ ｉ ＝ ０； ｉ ＜ ｐｏｗ＿ｍ； ｉ＋＋ ） ｛ ｓｕｍ ＋ ＝ ｐ＿ｃｔｒ［ｉ］ ∗ ｐ＿ｃｔｒ［ｉ］ ∗ ｂｌｋ＿ｓｚ＿ｉｎｖ； ｝ ｒｅｔｕｒｎ （ ｓｕｍ ∗ ｐｏｗ＿ｍ ） － ｂｌｋ＿ｓｚ； ｝ 第 ４ 期 杨先伟，等：随机序列的扑克检测优化研究 ·５１７·