Skip to content

Add back CRC-64 #3

Description

@nitro2k01

I'm currently making an assembly language version of this test to see the full potential of the hashing algorithms with hand optimized code. As part of this, I'm also investigating the performance of this benchmark. The readme says that CRC-64 (among other algos) was omitted because the execution time would take tens of seconds.

Image

Firstly, this might be true for some of the other algorithms using uint64_t, but I tried adding CRC-64 to the test with the source code from the NDS test, and it didn't seem too bad. It clocked in at 5726 ms. If the iteration count is reduced to 2 or even 1, it would use an acceptable amount of time as not to ruin the UX.

Secondly, it seems GBDK's uint64_t implementation is just so slow that it's more or less broken. I made a variant of the CRC-64 function, splitting the state up into two uint32_t, and that instantly made the algorithm twice as fast, attached below. I might have to look into the generated code and why uint64_t is so slow.

#define CRC64_POLY_HI  0x42F0E1EBUL
#define CRC64_POLY_LO  0xA9EA3693UL

void hash_crc64_split(const uint8_t *data, uint16_t len, uint8_t out[8]) HBENCH_BANKED {
    uint32_t crc_hi = 0u;
    uint32_t crc_lo = 0u;
    uint16_t i;
    uint8_t  j;

    for (i = 0; i < len; i++) {
        crc_hi ^= ((uint32_t)data[i]) << 24u;
        for (j = 0; j < 8u; j++) {
            if(crc_hi & (1UL << 31)){
                crc_hi = (
                        (crc_lo & (1UL << 31)) ? 
                        ((crc_hi << 1)|1) :
                        (crc_hi << 1) 
                    ) ^ CRC64_POLY_HI;

                crc_lo = (crc_lo << 1) ^ CRC64_POLY_LO;
            }else{
                crc_hi = (
                        (crc_lo & (1UL << 31)) ? 
                        ((crc_hi << 1)|1) :
                        (crc_hi << 1) 
                    );

                crc_lo = (crc_lo << 1);
            }
        }
    }
    out[0] = (uint8_t)(crc_hi >> 24); out[1] = (uint8_t)(crc_hi >> 16);
    out[2] = (uint8_t)(crc_hi >> 8);  out[3] = (uint8_t)(crc_hi);
    out[4] = (uint8_t)(crc_lo >> 24); out[5] = (uint8_t)(crc_lo >> 16);
    out[6] = (uint8_t)(crc_lo >>  8); out[7] = (uint8_t)(crc_lo);
}

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions