我必须做一个查找表中的，我有一个字符串和一个字符串的CRC32。如果有一个小姐，我一定要减小尺寸和查找的标识符的preFIX。 因此，我需要计算的preFIX校验并重复此过程为每个preFIX。

I have to do a lookup in a table, and I have a string identifier and the CRC32 of the string. If there is a miss, I have to decrement the size and lookup for a prefix of the identifier. Therefore, I would need to calculate the checksum of the prefix and repeat the process for each prefix.

该算法的我的C code是这样的：

My C code of this algorithm is something like this:

find_prefix(char* string, uint16_t size, uint32_t crc, hash_table_t *hash_table){
  do{
    if(perform_lookup(string, size, crc, hash_table)==HIT){
      return size;
    }
    size--;
    crc=calculate_crc(string, size, 0xFFFFFFFF);  //Is there a better way?
  } while(size);
}

我的问题是：我能避免CRC计算和推导的preFIX的CRC，给整个字符串的CRC和字符串本身

My question is: can I avoid the crc calculation and derive the crc of the prefix, given the crc of the whole string and the string itself?

我找到了一些相关的问题here和这里，但我有一个约束：当表为previosly填充，的CRC该标识符计算硬件，所以我不能修改算法，两者的联系提供尽可能的回答（用所有的部件基本上XOR）计算校验和的方式不同。

I found some related questions here and here, but I have a constraint: when the table is previosly populated, the crc of the identifier is calculated in hardware, so I can't modify the algorithm, and both the links provide as answer a different way of calculating the checksum (basically using XOR of all the components).

非常感谢你。

推荐答案

是的，这是可能的。 （除了微不足道的观察，如果你有字符串中的问题说明，那么你可以简单地计算出的preFIX的CRC）。

Yes, it is possible. (Aside from the trivial observation that if you have the string as stated in the question, then you can simply compute the CRC of the prefix.)

要重新表述您的问题，我有两个字符串A和B，他们的串联是AB。如果我有AB只有CRC和我有字符串B，我能计算出的CRC？

To rephrase your question, I have two strings A and B, where their concatenation is AB. If I have only the CRC of AB and I have the string B, can I compute the CRC of A?

您只需反向计算CRC，使用CRC的高位，以确定使用了哪个表项的过​​程。这几乎一样快，计算B.例子code中的CRC为标准的CRC-32的ZIP，GZIP等使用的：

You can just reverse the process of computing the CRC, using the high byte of the CRC to determine which table entry was used. It's almost as fast as computing the CRC of B. Example code for the standard CRC-32 used in zip, gzip, etc.:

/* Given the CRC of the concatenated string AB and the string B, calculate the
   CRC of A.  Placed in the public domain by Mark Adler. */

#include <stdio.h>

#define local static

/* Byte-wise CRC table for CRC-32 */
local unsigned long crc_table[] = {
    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
    0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
    0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
    0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
    0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
    0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
    0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
    0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
    0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
    0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
    0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
    0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
    0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
    0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
    0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
    0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
    0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
    0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
    0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
    0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
    0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
    0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
    0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
    0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
    0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
    0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
    0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
    0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
    0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
    0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
    0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
    0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
    0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
    0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
    0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
    0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
    0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
    0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
    0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
    0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
    0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
    0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
    0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
    0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
    0x2d02ef8d
};

local unsigned char rev[256];

local void revgen(void)
{
    unsigned k;

    for (k = 0; k < 256; k++)
        rev[crc_table[k] >> 24] = k;
}

#define ONES 0xffffffff

local unsigned long revcrc(unsigned long crc,
                           const unsigned char *buf, size_t len)
{
    unsigned k;

    crc = crc ^ ONES;
    while (len--) {
        k = rev[crc >> 24];
        crc = ((crc ^ crc_table[k]) << 8) | (k ^ buf[len]);
    }
    return crc ^ ONES;
}

int main(void)
{
    unsigned long crc = 0x9ef61f95;     /* CRC-32 of "foobar" */
                                        /* CRC-32 of "foo" is 0x8c736521 */

    revgen();
    printf("0x%08lx (should be 0x8c736521)\n",
           revcrc(crc, (unsigned char *)"bar", 3));
    return 0;
}