根据CRC32值，是否能够快速获得其原始值？

标题：答复
作者：readyu
时间：2008-06-19 21:49

下面是crc32/ crc16求逆的代码。
其实就是DonQuixote的： CRC32碰撞的实现。做了以下改进。
以前看过一个软件注册算法用到了crc16的逆，crc16的逆就更简单了。

全部采用的查表法，速度较快。
首先构造tab/ rf_tab。rf_tab是求逆的表。

typedef unsigned char      BYTE;
typedef unsigned short     WORD;
typedef unsigned int       DWORD;

#define LOWORD(l)           ((WORD)(l))
#define HIWORD(l)           ((WORD)(((DWORD)(l) >> 16) & 0xFFFF))
#define LOBYTE(w)           ((BYTE)(w))
#define HIBYTE(w)           ((BYTE)(((WORD)(w) >> 8) & 0xFF))
#define MAKEWORD(a, b)      ((WORD)(((BYTE)(a)) | ((WORD)((BYTE)(b))) << 8))
#define MAKEDWORD(a, b)     ((DWORD)(((WORD)(a)) | ((DWORD)((WORD)(b))) << 16))

#define MakeWord(a,b)    MAKEWORD(b,a)
#define MakeDWord(a,b)   MAKEDWORD(b,a)

// crc32/ crc16 funs
#define CRC32_NEW   (0xFFFFFFFFUL)
#define CRC32_POLY  (0xEDB88320UL)
#define CRC16_NEW   (unsigned short)(0xFFFF)
#define CRC16_POLY  (unsigned short)(0x8408)
#define CRC16_STD_POLY  (unsigned short)(0xA001)

unsigned int crc32_tab[256];
unsigned short crc16_tab[256];

unsigned char crc32_rf[256];
unsigned char crc16_rf[256];

void init_crc32_table(unsigned int poly)
{
    unsigned int i,j;
    unsigned int crc;
    for( i = 0; i < 256; i ++ ) {
        crc = i;
        for( j = 0; j < 8; j ++ ){
            if(crc & 1) crc = (crc >> 1) ^ poly;
            else crc >>= 1;
        }
        crc32_tab[i] = crc;
    }
    return;
}

void init_crc32_rf_table(void)
{
    unsigned int i,j;

    for(i=0; i<256; i++) {
        j = HIBYTE(HIWORD(crc32_tab[i]));
        crc32_rf[j] = i;
    }
    return;
}

/* must init_crc32_rf_table() first */
#define RF(x)   crc32_rf[(BYTE) x]
#define F(x)    HIBYTE(HIWORD(crc32_tab[(BYTE) x]))
#define G(x)    LOBYTE(HIWORD(crc32_tab[(BYTE) x]))
#define H(x)    HIBYTE(LOWORD(crc32_tab[(BYTE) x]))
#define I(x)    LOBYTE(LOWORD(crc32_tab[(BYTE) x]))

/*
given crc_head = ABCD
find abcd;
that crc(abcd) = WXYZ
*/
unsigned int rCRC32(unsigned int WXYZ,unsigned int ABCD)
{
    BYTE p,o,n,m,a,b,c,d,W,X,Y,Z,A,B,C,D;

    W=HIBYTE(HIWORD(WXYZ));
    X=LOBYTE(HIWORD(WXYZ));
    Y=HIBYTE(LOWORD(WXYZ));
    Z=LOBYTE(LOWORD(WXYZ));

    A=HIBYTE(HIWORD(ABCD));
    B=LOBYTE(HIWORD(ABCD));
    C=HIBYTE(LOWORD(ABCD));
    D=LOBYTE(LOWORD(ABCD));

    p=crc32_rf[W];
    o=crc32_rf[(BYTE) (X^G(p))];
    n=crc32_rf[(BYTE) (Y^G(o)^H(p))];
    m=crc32_rf[(BYTE) (Z^G(n)^H(o)^I(p))];

    d=m^D;
    c=n^C^I(m);
    b=o^B^H(m)^I(n);
    a=p^A^G(m)^H(n)^I(o);
    return MakeDWord(MakeWord(a,b),MakeWord(c,d));
}

#define FF(x)  HIBYTE(crc16_tab[(unsigned char)x])
#define GG(x)  LOBYTE(crc16_tab[(unsigned char)x])

void init_crc16_table(unsigned short poly)
{
    unsigned int i,j;
    unsigned short crc;
    for( i = 0; i < 256; i ++ ) {
        crc = i;
        for( j = 0; j < 8; j ++ ){
            if(crc & 1) crc = (crc >> 1) ^ poly;
            else crc >>= 1;
        }
        crc16_tab[i] = crc;
    }
    return;
}

void init_crc16_rf_table(void)
{
    unsigned int i,j;

    for(i=0; i<256; i++) {
        j = HIBYTE(crc16_tab[i]);
        crc16_rf[j] = i;
    }
    return;
}

unsigned short rCRC16(unsigned short XY, unsigned short AB)
{
    BYTE X,Y,A,B,a,b,m,n;

    X=HIBYTE(XY);
    Y=LOBYTE(XY);
    A=HIBYTE(AB);
    B=LOBYTE(AB);

    n=crc16_rf[X];
    m=crc16_rf[(BYTE) (Y^GG(n))];

    b=m^B;
    a=n^A^GG(m);
    return MakeWord(a,b);
}