Results 1 to 4 of 4

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

  1. #1
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts

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

    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

  2. #2
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts
    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;

    }


  3. #3
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,133
    Thanks
    320
    Thanked 1,396 Times in 801 Posts
    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.

  4. #4
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts

    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

Similar Threads

  1. Quickly find duplicate files
    By fcorbelli in forum Data Compression
    Replies: 8
    Last Post: 19th December 2020, 21:07
  2. Code snippet to compute CPU frequency
    By Bulat Ziganshin in forum Data Compression
    Replies: 6
    Last Post: 8th May 2020, 05:05
  3. Replies: 8
    Last Post: 30th July 2019, 18:20
  4. Fast CRC table construction and rolling CRC hash calculation
    By Bulat Ziganshin in forum Data Compression
    Replies: 10
    Last Post: 27th May 2018, 04:32
  5. Reading to a buffer
    By Piotr Tarsa in forum The Off-Topic Lounge
    Replies: 17
    Last Post: 27th January 2012, 05:32

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •