使用预处理器计算奇偶校验位(通过 ref 调用的奇偶校验功能样式)

Question

假设我想在编译时生成奇偶校验。奇偶校验计算被赋予文字常量，并且对于任何体面的优化器，它都会归结为一个常量本身。现在使用 C 预处理器查看以下奇偶校验计算:

#define PARITY16(u16) (PARITY8((u16)&0xff) ^ PARITY8((u16)>>8))
#define PARITY8(u8) (PARITY4((u8)&0x0f) ^ PARITY4((u8)>>4))
#define PARITY4(u4) (PARITY2((u4)&0x03) ^ PARITY2((u4)>>2))
#define PARITY2(u2) (PARITY1((u2)&0x01) ^ PARITY1((u2)>>1))
#define PARITY1(u1) (u1)

int message[] = { 0x1234, 0x5678, PARITY16(0x1234^0x5678));

这将在编译时计算奇偶校验，但它会产生大量的中间代码，扩展到表达式 u16 的 16 个实例，它本身可以是例如任意复杂的表达式。问题是 C 预处理器无法评估中间表达式，并且在一般情况下只会扩展文本(您可以强制它在原位进行整数运算，但仅适用于微不足道的情况，或者千兆字节的#定义)。我发现 3 位的奇偶校验可以通过算术表达式一次生成:([0..7]*3+1)/4。这将 16 位奇偶校验减少为以下宏:

#define PARITY16(u16) ((4 & ((((u16)&7)*3+1) ^           \
                            ((((u16)>>3)&7)*3+1) ^               \
                            ((((u16)>>6)&7)*3+1) ^               \
                            ((((u16)>>9)&7)*3+1) ^               \
                            ((((u16)>>12)&7)*3+1) ^              \
                            ((((u16)>>15)&1)*3+1))) >> 2))

它仅将 u16 扩展了 6 次。有没有更便宜的(就扩展数量而言)方式，例如4,5等的直接公式。位奇偶校验？对于范围 > 3 位的可接受(非溢出)值 k、d、m，我找不到形式为 (x*k+d)/m 的线性表达式的解决方案。谁有更聪明的预处理器奇偶校验计算快捷方式？

Answer 1

您正在寻找这样的东西吗？下面的“PARITY16(u16)”预处理器宏可用作结构赋值中的文字常量，它只对参数求值一次。

/* parity.c
 * test code to test out bit-twiddling cleverness
 * 2013-05-12: David Cary started.
*/

// works for all 0...0xFFFF
// and only evalutes u16 one time.
#define PARITYodd33(u33) \
    ( \
        ((((((((((((((( \
            (u33) \
        &0x555555555)*5)>>2) \
        &0x111111111)*0x11)>>4) \
        &0x101010101)*0x101)>>8) \
        &0x100010001)*0x10001)>>16) \
        &0x100000001)*0x100000001)>>32) \
    &1)
#define PARITY16(u16) PARITYodd33(((unsigned long long)u16)*0x20001)

// works for all 0...0xFFFF
// but, alas, generates 16 instances of u16.
#define PARITY_16(u16) (PARITY8((u16)&0xff) ^ PARITY8((u16)>>8))
#define PARITY8(u8) (PARITY4((u8)&0x0f) ^ PARITY4((u8)>>4))
#define PARITY4(u4) (PARITY2((u4)&0x03) ^ PARITY2((u4)>>2))
#define PARITY2(u2) (PARITY1((u2)&0x01) ^ PARITY1((u2)>>1))
#define PARITY1(u1) (u1)

int message1[] = { 0x1234, 0x5678, PARITY16(0x1234^0x5678) };
int message2[] = { 0x1234, 0x5678, PARITY_16(0x1234^0x5678) };

#include <stdio.h>

int main(void){
        int errors = 0;
        int i=0;
        printf(" Testing parity ...\n");
        printf(" 0x%x = message with PARITY16\n", message1[2] );
        printf(" 0x%x = message with PARITY_16\n", message2[2] );
        for(i=0; i<0x10000; i++){
                int left = PARITY_16(i);
                int right =  PARITY16(i);
                if( left != right ){
                        printf(" 0x%x: (%d != %d)\n", i, left, right );
                        errors++;
                        return 0;
                };
        };
        printf(" 0x%x errors detected. \n", errors );
} /* vim: set shiftwidth=4 expandtab ignorecase : */

与您发布的原始代码非常相似，它对位进行配对并(实际上)计算每对之间的异或，然后根据结果再次对位进行配对，每次将位数减半，直到只有一个奇偶校验位仍然存在。

但这真的是您想要的吗？

许多人说他们正在计算消息的“奇偶性”。但根据我的经验，大多数时候它们确实在产生一个error-detection code大于单个奇偶校验位——一个LRC , 或 CRC , 或 Hamming code , 或等等。

更多详情

如果当前系统在合理的时间内编译，它给出了正确的答案，我不会管它。重构“预处理器如何生成一些常量”将逐位生成相同的运行时可执行文件。我宁愿有易于阅读的来源即使编译需要整整一秒的时间。

许多人使用比标准 C 预处理器更易于阅读的语言来生成 C 源代码。参见 pycrc , character set extractor , "using Python to generate C"等

如果当前系统编译时间太长，而不是调整 C 预处理器，我很想将该消息(包括奇偶校验)放在一个单独的“.h”文件中使用硬编码常量(而不是强制 C 预处理器每次都计算它们)，和“#include”嵌入式系统的“.c”文件中的“.h”文件。

然后我会制作一个完全独立的程序(可能用 C 或 Python)进行奇偶校验计算和打印出该“.h”文件的内容作为预先计算的 C 源代码，像

print("int message[] = { 0x%x, 0x%x, 0x%x };\n",
    M[0], M[1], parity( M[0]^M[1] ) );

并调整我的 MAKEFILE运行该 Python(或其他)程序以重新生成该“.h”文件当且仅当有必要时。