S实现:如何处理单个比特？

Question

我有一个任务，要求我们实现S-DES (简化DES)，算法包括很多位排列、移位以及异或。

显然，最快的实现方法是使用位操作，例如：

char CLS(char key, int shift){
    char skey;
    skey = (key << shift) | (key >> (8 - shift)) 
    return skey;
}

/* Get 8-bit subkey from 10-bit key */
char permute(short int key){
    short int i;
    short int k1[] = { BIT_6, BIT_3, BIT_7, BIT_4, BIT_8, BIT_5, BIT_10, BIT_9 }; // SDES spec
    char sk1 = '\0';

    for(i = 0; i < 8; i++){
        sk1 = (sk1 << 1) | (key & k1[i]);
    }
}

...

这就足够简单了。然而，如何有效地获取这些位呢？使用像fread()这样的东西，我可以一次读取至少一个字节，并将这些字节提供给SDES算法，但这完全没有充分利用CPU，因为我不仅一次只读取和加密一个字节，而且还会一次将1字节加密数据写入磁盘！当然，一定有更好的办法。

我能想到的唯一替代方法是将每个字节作为char数组来处理，并以这种方式操作比特，但这不仅会增加内存开销:我一次只能处理一个字节，而且我无法使用shift操作，而是需要使用临时数组和数组索引。

我希望稍微改善一下这种行为，但我所能想到的只是把更大的块带入记忆中。例如，我可以使用fread()将4K个数据块读取到一个字符array4096中，然后处理它，而不是从磁盘逐个读取4096字节。

但是，考虑到这是一个简单的算法，我不确定这是否是我所能做的。还能做进一步的改进吗?或者说这是否已经达到了最好的效果？

如果有人想看一看，这里就是S算法的规范.

Answer 1

如果您想加快算法的速度，可以将字节数组上的加密并行化，例如使用OpenMP。正如DarkSquirrel42在评论中指出的那样，为了获得速度，您还应该使用一个查找表将您的permute函数替换为一个函数：

#define LUT_SIZE 1024
static char lookup_table[LUT_SIZE];

/* Get 8-bit subkey from 10-bit key */
char permute(short int key)
{
    // SDES spec
    short int k1[] = { BIT_6, BIT_3, BIT_7, BIT_4, BIT_8, BIT_5, BIT_10, BIT_9 }; 
    char sk1 = '\0';

    for (short int i = 0; i < 8; i++) {
        sk1 = (sk1 << 1) | (key & k1[i]);
    }
    return sk1;
}

void init_lut()
{
    for (short int i = 0; i < LUT_SIZE; i++) {
        lookup_table[i] = permute(i);
    }
}

char permute_fast(short int key)
{
    if (key < 0 || key >= LUT_SIZE) {
        //error handling
        return 0;
    }
    return lookup_table[key];
}