小编hak*_*oja的帖子

我正在研究一个SHA3候选者JH的实现.我正处于算法通过NIST提供的所有KAT(已知答案测试)的地步,并且还使其成为Crypto-API的实例.因此,我开始研究它的表现.但我对Haskell很新,并且在分析时并不知道该寻找什么.

目前我的代码总是慢于用C语言编写的参考实现,所有输入长度都是10倍(C代码在这里找到:http://www3.ntu.edu.sg/home/wuhj/research/jh /jh_bitslice_ref64.h).

我的Haskell代码可以在这里找到:https://github.com/hakoja/SHA3/blob/master/Data/Digest/JHInternal.hs.

现在我不希望你浏览我的所有代码,而只是想要一些关于几个函数的技巧.我已经运行了一些性能测试,这是GHC生成的性能文件(的一部分):

Tue Oct 25 19:01 2011 Time and Allocation Profiling Report  (Final)

   main +RTS -sstderr -p -hc -RTS jh e False

total time  =        6.56 secs   (328 ticks @ 20 ms)
total alloc = 4,086,951,472 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

roundFunction                  Data.Digest.JHInternal  28.4   37.4
word128Shift                   Data.BigWord.Word128  14.9   19.7
blockMap                       Data.Digest.JHInternal  11.9   12.9
getBytes                       Data.Serialize.Get     6.7    2.4
unGet                          Data.Serialize.Get     5.5    1.3
sbox                           Data.Digest.JHInternal   4.0    7.4 …

我现在已经实现了另一个 SHA3​​候选者,即Grøstl.这仍然在进行中(非常如此),但目前224位版本通过了所有KAT.所以现在我想知道性能(再次: - >).这次的不同之处在于,我选择更接近地镜像(优化的)C实现,即我创建了一个从C到Haskell的端口.优化的C版本使用表查找来实现该算法.此外,代码主要基于更新包含64位字的数组.因此,我选择在Haskell中使用可变的无盒载体.

我的Grøstl代码可以在这里找到:https://github.com/hakoja/SHA3/blob/master/Data/Digest/GroestlMutable.hs

该算法的简短描述:它是一个Merkle-Damgård构造,只要有512位的消息块,就迭代一个压缩函数(在我的代码中为f512M).压缩函数非常简单:它只运行两个不同的独立512位排列P和Q(我的代码中的permP和permQ)并组合它们的输出.它的这些排列是由查找表实现的.

Q1)困扰我的第一件事是使用可变向量使我的代码看起来非常难看.这是我第一次在Haskell中编写任何主要的可变代码,所以我真的不知道如何改进它.关于如何更好地构建monadic代码的任何提示都将受到欢迎.

Q2)第二是表现.实际上它并不太糟糕,因为目前Haskell代码只慢了3倍.使用GHC-7.2.1并编译如下:

ghc -O2 -Odph -fllvm -optlo-O3 -optlo-loop-reduce -optlo-loop-deletion

Haskell代码使用60秒.输入约为1GB,而C版本使用21-22s.但有一些我觉得奇怪的事情:

(1)如果我尝试内联rnd512QM,代码需要4倍的时间,但如果我内联rnd512PM没有任何反应!为什么会这样？这两个功能几乎相同!

(2)这可能更难.我一直在尝试并行执行两个排列.但目前无济于事.这是我尝试过的一个例子:

f512 h m = V.force outP `par` (V.force outQ `pseq` (V.zipWith3 xor3 h outP outQ))
   where xor3 x1 x2 x3 = x1 `xor` x2 `xor` x3
         inP = V.zipWith xor h m
         outP = permP inP
         outQ = permQ m …

我想找到一种尽可能快的方法来乘以两个小布尔矩阵,其中小的意思是8x8,9x9 ... 16x16.这个例程将被大量使用,因此它需要非常高效,所以请不要建议直截了当的解决方案应该足够快.

对于特殊情况8x8和16x16,我已经有了相当高效的实现,基于此处的解决方案,我们将整个矩阵视为uint64_t或uint64_t[4]分别处理.在我的机器上,这比直接实现快大约70-80倍.

但是,在8 <k <16的情况下,我真的不知道如何利用任何合理的表示来实现上述巧妙的技巧.

基本上,我对使用任何类型的表示(矩阵)和函数签名的任何建议持开放态度.您可以假设这是针对32位或64位架构(选择最适合您的建议)

我想通过重复每个位8次来膨胀unsigned char到a uint64_t.例如

char -> uint64_t
0x00 -> 0x00
0x01 -> 0xFF
0x02 -> 0xFF00
0x03 -> 0xFFFF
0xAA -> 0xFF00FF00FF00FF00

我目前有以下实现,使用位移来测试是否设置了一个位,以实现此目的:

#include <stdint.h>
#include <inttypes.h>   

#define BIT_SET(var, pos) ((var) & (1 << (pos)))

static uint64_t inflate(unsigned char a)
{
    uint64_t MASK = 0xFF;
    uint64_t result = 0;
    for (int i = 0; i < 8; i++) {
        if (BIT_SET(a, i))
            result |= (MASK << (8 * i));    
    }

    return result;
} 

但是,我对C来说还是个新手,所以这个摆弄个别位的东西让我有点不同,可能会有更好的(即更有效的)方法.

编辑添加
好了,所以在尝试了表查找解决方案后,结果如下.但是,请记住,我没有直接测试例程,而是作为更大函数的一部分(确切地说是二进制矩阵的乘法),因此这可能会影响结果的结果.因此,在我的计算机上,当乘以一百万个8x8矩阵时,编译为:

  gcc -O2 …

作为学校项目的一部分,我正在Haskell中实现一些密码算法.你可能知道这涉及很多低级别的小提琴.现在我被困在一个特殊的子程序上,这让我很头疼.该例程是256位的置换,其工作原理如下:

输入:256位块.
然后,输入块中的所有偶数位(0,2,...)被视为输出块中的前128位.而奇数位被认为是输出块中的128个最后位.更具体地说,输出中第i位的公式为(a _i是输入块中的第i位,b是输出):

b _i = a _2i

b _{i + 2 ^d-1} = a _{2i + 1}

对于i,从0到2 ^d-1 -1,d = 8.

作为玩具示例,假设我们使用了例程的简化版本,该例程使用16位块而不是256位.然后,以下位串将被置换如下:

1010 1010 1010 1010 - > 1111 1111 0000 0000

我无法为此功能提供干净的实现.特别是我一直尝试使用ByteString - > ByteString签名,但这种强迫我使用Word8的粒度.但是输出字节串中的每个字节都是所有其他字节中的位的函数,这需要一些非常混乱的操作.

对于如何解决这个问题,我会非常感激.