How to quickly compute CRC-32 of an all-zeroed buffer

[fcorbelli]

During the debugging phase of my personal version of ZPAQ I ran into a problem.
The existence of "holes", that is, sequences of zero bytes that ZPAQ does not store and does not restore.
So I have to calculate the CRC-32 of "virtual" blocks to calculate the correct CRC

Example

    unsigned char allzeros[1000000];

    memset(allzeros,0,sizeof(allzeros));



(...)



if ((g_crc32[i].crc32start+g_crc32[i].crc32size) != (g_crc32[i+1].crc32start))

            {

                printf("############################## HOUSTON WE HAVE AN HOLE %d %d\n",i,g_crc32.size());

                printf("Start %08ld\n",g_crc32[i].crc32start);

                printf("Size  %08ld\n",g_crc32[i].crc32size);

                printf("End   %08ld\n",g_crc32[i].crc32start+g_crc32[i].crc32size);

                printf("Next  %08ld\n",g_crc32[i+1].crc32start);

                

                uint64_t holestart=g_crc32[i].crc32start+g_crc32[i].crc32size;

                printf("Start  %08ld\n",holestart);

                

                uint64_t holesize=g_crc32[i+1].crc32start-(g_crc32[i].crc32start+g_crc32[i].crc32size);

                printf("Size  %08ld\n",holesize);

                

                uint32_t zerocrc;

                zerocrc=crc32_16bytes (allzeros,(uint32_t)holesize); <<<======= very quick, very dirty

                printf("zero  %08X\n",zerocrc);

                currentcrc32=crc32_combine(currentcrc32, zerocrc,(uint32_t)holesize);

            

In this first development approach I brutally allocate a vector of a million characters, zeroed, on which I take the CRC32 for the length I need (obviously it's just a skeleton).

For example, given a
3.536.704 bytes file (mysql.exe)
ZPAQ create some fragments

24/12/2020  18:34         2.050.374 globals_00000000000000_00000002050374_791FBF21

24/12/2020  18:34           497.149 globals_00000002091717_00000002588866_4514DF59

24/12/2020  18:34           306.965 globals_00000002630209_00000002937174_56B179E2

24/12/2020  18:34           558.187 globals_00000002978517_00000003536704_19F30641



... but some "padding" (virtual 0s chunk) may be needed,

in this case 3x41.343 bytes



24/12/2020  18:34         2.050.374 globals_00000000000000_00000002050374_791FBF21

24/12/2020  18:34            41.343 globals_00000002050374_00000002091717_448030DD_zero

24/12/2020  18:34           497.149 globals_00000002091717_00000002588866_4514DF59

24/12/2020  18:34            41.343 globals_00000002588866_00000002630209_448030DD_zero

24/12/2020  18:34           306.965 globals_00000002630209_00000002937174_56B179E2

24/12/2020  18:34            41.343 globals_00000002937174_00000002978517_448030DD_zero

24/12/2020  18:34           558.187 globals_00000002978517_00000003536704_19F30641

Is there a (quick) function calc_crc32_of_a_zero_block_of_length_n?

uint32_t crczero(uint32_t N)

{

    unsigned char allzeros[1000000];

    memset(allzeros,0,sizeof(allzeros)); ==>> I know, I know...

    uint32_t=crc32(allzeros,N); 

}

Thank you

[fcorbelli]

Something better than...

uint32_t crc32zeros(int32_t i_size)

{

    uint32_t crc=0;

    if (i_size==0)

        return crc;



    static unsigned char allzeros[1024]={0};

    

    unsigned int block=i_size/sizeof(allzeros);

    unsigned int resto=i_size-(block*sizeof(allzeros));

    uint32_t zerocrc=0xEFB5AF2E; //crc32_16bytes (allzeros,(uint32_t)sizeof(allzeros));

    uint32_t crcresto=crc32_16bytes (allzeros,(uint32_t)resto);

    

    for (unsigned int i=0; i<block;i++)

        crc=crc32_combine(crc, zerocrc,(uint32_t)sizeof(allzeros));

    crc=crc32_combine(crc, crcresto,(uint32_t)resto);

    return crc;

    

}

[Shelwien]

You can also precompute the CRC of power-of-2 zero-block sizes, then combine these.
But precomputing a million of CRCs would be simpler.

[fcorbelli]

const uint32_t zero_block_crc32[54] =

{

0xD202EF8D,0x41D912FF,0x2144DF1C,0x6522DF69,0xECBB4B55,0x190A55AD,0x758D6336,0xC2A8FA9D,

0x0D968558,0xB2AA7578,0xEFB5AF2E,0xF1E8BA9E,0xC71C0011,0xD8F49994,0xAB54D286,0x011FFCA6,

0xD7978EEB,0x7EE8CDCD,0xE20EEA22,0x75660AAC,0xA738EA1C,0x8D89877E,0x1147406A,0x1AD2BC45,

0xA47CA14A,0x59450445,0xB2EB30ED,0x80654151,0x2A0E7DBB,0x6DB88320,0x5B64C2B0,0x4DBDF21C,

0xD202EF8D,0x41D912FF,0x2144DF1C,0x6522DF69,0xECBB4B55,0x190A55AD,0x758D6336,0xC2A8FA9D,

0x0D968558,0xB2AA7578,0xEFB5AF2E,0xF1E8BA9E,0xC71C0011,0xD8F49994,0xAB54D286,0x011FFCA6,

0xD7978EEB,0x7EE8CDCD,0xE20EEA22,0x75660AAC,0xA738EA1C,0x8D89877E

};

uint32_t crc32ofzeroblock(uint64_t i_size) 

{

    assert(i_size<9.007.199.254.740.992); //8D89877E 2^53 9.007.199.254.740.992

    if (i_size==0)

        return 0;

    uint32_t mycrc=0;

    unsigned int i=0;

    while (i_size > 0)

    {

        if ((i_size%2)==1)

            mycrc=crc32_combine(mycrc,zero_block_crc32[i],1<<i);

        i_size=i_size/2;

        i++;

    }

       return mycrc;

}

I made this.
Not really smart, but straigthfoward