2

考虑我想在编译时生成奇偶校验。奇偶校验计算给出了文字常量，并且使用任何体面的优化器，它本身都会归结为一个常量。现在看一下使用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));

这将在编译时计算奇偶校验，但会产生大量的中间代码，扩展为表达式的 16 个实例，u16其本身可以是例如任意复杂的表达式。问题是C预处理器无法评估中间表达式，并且在一般情况下只能扩展文本（您可以强制它在原位进行整数运算，但仅适用于琐碎的情况，或者使用千兆字节的#defines）。我发现 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))

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

4

2 回答 2

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 : */

就像您发布的原始代码一样，它将位配对并（实际上）计算每对之间的 XOR，然后根据结果再次配对位，每次将位数减半，直到只剩下一个奇偶校验位。

但这真的是你想要的吗？

许多人说他们正在计算消息的“奇偶性”。但根据我的经验，大多数情况下，它们实际上是在生成比单个奇偶校验位更大的错误检测码—— LRC或CRC或Hamming 码等。

更多详细信息

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

许多人使用比标准 C 预处理器更易于阅读的语言来生成 C 源代码。请参阅pycrc、字符集提取器、“使用 Python 生成 C”等。

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

然后我会制作一个完全独立的程序（可能在 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”文件。

于 2013-05-13T05:43:59.013 回答
-1

正如 mfontanini 所说，内联函数要好得多。

如果你坚持宏，你可以定义一个临时变量。
使用gcc，您可以做到这一点，并且仍然拥有充当表达式的宏：
#define PARITY(x) ({int tmp=x; PARITY16(tmp);})
如果要坚持标准，则必须使宏成为语句：
#define PARITY(x, target) do { int tmp=x; target=PARITY16(tmp); } while(0)。

在这两种情况下，如果tmp最终使用函数中的名称（更糟糕的是 - 在传递给宏的参数中使用），您可能会遇到丑陋的错误。

于 2012-07-02T13:27:14.820 回答