From 46467e91b0c96f368b2ac75569dfab2d3a097ef8 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Tue, 5 Sep 2006 18:06:54 -0500 Subject: [svn-r12649] Description: Add a CRC algorithm to the library, initially for "small" (<256 byte) metadata blocks. Update checksum tests to verify it's working correctly. Tested: Linux/32 2.6 (chicago) Linux/64 2.6 (chicago2) (Will be testing on more platforms after checkin) --- src/H5Zfletcher32.c | 4 +- src/H5checksum.c | 133 ++++++++++++++++++++++++++++++++++++++++++++++++---- src/H5private.h | 3 +- test/tchecksum.c | 72 +++++++++++++++++++--------- 4 files changed, 179 insertions(+), 33 deletions(-) diff --git a/src/H5Zfletcher32.c b/src/H5Zfletcher32.c index 9092452..139a7ad 100644 --- a/src/H5Zfletcher32.c +++ b/src/H5Zfletcher32.c @@ -102,7 +102,7 @@ H5Z_filter_fletcher32 (unsigned flags, size_t UNUSED cd_nelmts, const unsigned U UINT32DECODE(tmp_src, stored_fletcher); /* Compute checksum (can't fail) */ - fletcher = H5_fletcher32(src, src_nbytes); + fletcher = H5_checksum_fletcher32(src, src_nbytes); /* The reversed checksum. There was a bug in the calculating code of * the Fletcher32 checksum in the library before v1.6.3. The checksum @@ -136,7 +136,7 @@ H5Z_filter_fletcher32 (unsigned flags, size_t UNUSED cd_nelmts, const unsigned U unsigned char *dst; /* Temporary pointer to destination buffer */ /* Compute checksum (can't fail) */ - fletcher = H5_fletcher32(src, nbytes); + fletcher = H5_checksum_fletcher32(src, nbytes); if (NULL==(dst=outbuf=H5MM_malloc(nbytes+FLETCHER_LEN))) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, 0, "unable to allocate Fletcher32 checksum destination buffer") diff --git a/src/H5checksum.c b/src/H5checksum.c index 4a1e5de..fd2a075 100644 --- a/src/H5checksum.c +++ b/src/H5checksum.c @@ -38,6 +38,10 @@ /* Local Macros */ /****************/ +/* Polynomial quotient */ +/* (same as the IEEE 802.3 (Ethernet) quotient) */ +#define H5_CRC_QUOTIENT 0x04C11DB7 + /******************/ /* Local Typedefs */ @@ -68,10 +72,16 @@ /* Local Variables */ /*******************/ +/* Table of CRCs of all 8-bit messages. */ +static uint32_t H5_crc_table[256]; + +/* Flag: has the table been computed? */ +static hbool_t H5_crc_table_computed = FALSE; + /*------------------------------------------------------------------------- - * Function: H5_fletcher32 + * Function: H5_checksum_fletcher32 * * Purpose: This routine provides a generic, fast checksum algorithm for * use in the library. @@ -80,7 +90,11 @@ * http://en.wikipedia.org/wiki/Fletcher%27s_checksum * for more details, etc. * - * Note #2: The algorithm below differs from that given in the Wikipedia + * Note #2: Per the information in RFC 3309: + * (http://tools.ietf.org/html/rfc3309) + * Fletcher's checksum is not reliable for small buffers. + * + * Note #3: The algorithm below differs from that given in the Wikipedia * page by copying the data into 'sum1' in a more portable way * and also by initializing 'sum1' and 'sum2' to 0 instead of * 0xffff (for backward compatibility reasons, mostly). @@ -93,13 +107,13 @@ *------------------------------------------------------------------------- */ uint32_t -H5_fletcher32(const void *_data, size_t _len) +H5_checksum_fletcher32(const void *_data, size_t _len) { const uint8_t *data = (const uint8_t *)_data; /* Pointer to the data to be summed */ size_t len = _len / 2; /* Length in 16-bit words */ uint32_t sum1 = 0, sum2 = 0; - FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5_fletcher32) + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5_checksum_fletcher32) /* Sanity check */ HDassert(_data); @@ -134,7 +148,107 @@ H5_fletcher32(const void *_data, size_t _len) sum2 = (sum2 & 0xffff) + (sum2 >> 16); FUNC_LEAVE_NOAPI((sum2 << 16) | sum1) -} /* end H5_fletcher32() */ +} /* end H5_checksum_fletcher32() */ + + +/*------------------------------------------------------------------------- + * Function: H5_checksum_crc_make_table + * + * Purpose: Compute the CRC table for the CRC checksum algorithm + * + * Return: none + * + * Programmer: Quincey Koziol + * Tuesday, September 5, 2006 + * + *------------------------------------------------------------------------- + */ +static void +H5_checksum_crc_make_table(void) +{ + uint32_t c; /* Checksum for each byte value */ + unsigned n, k; /* Local index variables */ + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5_checksum_crc_make_table) + + /* Compute the checksum for each possible byte value */ + for(n = 0; n < 256; n++) { + c = (uint32_t) n; + for(k = 0; k < 8; k++) + if(c & 1) + c = H5_CRC_QUOTIENT ^ (c >> 1); + else + c = c >> 1; + H5_crc_table[n] = c; + } + H5_crc_table_computed = TRUE; + + FUNC_LEAVE_NOAPI_VOID +} /* end H5_checksum_crc_make_table() */ + + +/*------------------------------------------------------------------------- + * Function: H5_checksum_crc_make_table + * + * Purpose: Update a running CRC with the bytes buf[0..len-1]--the CRC + * should be initialized to all 1's, and the transmitted value + * is the 1's complement of the final running CRC (see the + * H5_checksum_crc() routine below)). + * + * Return: 32-bit CRC checksum of input buffer (can't fail) + * + * Programmer: Quincey Koziol + * Tuesday, September 5, 2006 + * + *------------------------------------------------------------------------- + */ +static uint32_t +H5_checksum_crc_update(uint32_t crc, const uint8_t *buf, size_t len) +{ + size_t n; /* Local index variable */ + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5_checksum_crc_update) + + /* Initialize the CRC table if necessary */ + if(!H5_crc_table_computed) + H5_checksum_crc_make_table(); + + /* Update the CRC with the results from this buffer */ + for(n = 0; n < len; n++) + crc = H5_crc_table[(crc ^ buf[n]) & 0xff] ^ (crc >> 8); + + FUNC_LEAVE_NOAPI(crc) +} /* end H5_checksum_crc_update() */ + + +/*------------------------------------------------------------------------- + * Function: H5_checksum_crc + * + * Purpose: This routine provides a generic checksum algorithm for + * use in the library. + * + * Note: This algorithm was based on the implementation described + * in the document describing the PNG image format: + * http://www.w3.org/TR/PNG/#D-CRCAppendix + * + * Return: 32-bit CRC checksum of input buffer (can't fail) + * + * Programmer: Quincey Koziol + * Tuesday, September 5, 2006 + * + *------------------------------------------------------------------------- + */ +uint32_t +H5_checksum_crc(const void *_data, size_t len) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5_checksum_crc) + + /* Sanity check */ + HDassert(_data); + HDassert(len > 0); + + FUNC_LEAVE_NOAPI(H5_checksum_crc_update((uint32_t)0xffffffffL, (const uint8_t *)_data, len) ^ 0xffffffffL) +} /* end H5_checksum_crc() */ /*------------------------------------------------------------------------- @@ -163,10 +277,11 @@ H5_checksum_metadata(const void *data, size_t len) HDassert(len > 0); /* Choose the appropriate checksum routine */ - /* (use fletcher32 for everything right now, but will probably go - * with a CRC algorithm for "shorter" pieces of metadata eventually) - */ - chksum = H5_fletcher32(data, len); + /* (use Fletcher's checksum for "larger" buffers and CRC for "shorter" ones) */ + if(len < 256) + chksum = H5_checksum_crc(data, len); + else + chksum = H5_checksum_fletcher32(data, len); FUNC_LEAVE_NOAPI(chksum) } /* end H5_checksum_metadata() */ diff --git a/src/H5private.h b/src/H5private.h index 28c72c8..e9beabd 100644 --- a/src/H5private.h +++ b/src/H5private.h @@ -1447,7 +1447,8 @@ H5_DLL int H5T_term_interface(void); H5_DLL int H5Z_term_interface(void); /* Checksum functions */ -H5_DLL uint32_t H5_fletcher32(const void *data, size_t len); +H5_DLL uint32_t H5_checksum_fletcher32(const void *data, size_t len); +H5_DLL uint32_t H5_checksum_crc(const void *data, size_t len); H5_DLL uint32_t H5_checksum_metadata(const void *data, size_t len); /* Functions for debugging */ diff --git a/test/tchecksum.c b/test/tchecksum.c index 62c0505..ee492f8 100644 --- a/test/tchecksum.c +++ b/test/tchecksum.c @@ -51,13 +51,19 @@ test_chksum_size_one(void) uint32_t chksum; /* Checksum value */ /* Buffer w/real data */ - chksum = H5_fletcher32(buf, sizeof(buf)); - VERIFY(chksum, 0x17001700, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(buf, sizeof(buf)); + VERIFY(chksum, 0x17001700, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(buf, sizeof(buf)); + VERIFY(chksum, 0xfa2568b7, "H5_checksum_crc"); /* Buffer w/zero(s) for data */ HDmemset(buf, 0, sizeof(buf)); - chksum = H5_fletcher32(buf, sizeof(buf)); - VERIFY(chksum, 0, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(buf, sizeof(buf)); + VERIFY(chksum, 0, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(buf, sizeof(buf)); + VERIFY(chksum, 0xfa60fb57, "H5_checksum_crc"); } /* test_chksum_size_one() */ @@ -73,13 +79,19 @@ test_chksum_size_two(void) uint32_t chksum; /* Checksum value */ /* Buffer w/real data */ - chksum = H5_fletcher32(buf, sizeof(buf)); - VERIFY(chksum, 0x17bb17bb, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(buf, sizeof(buf)); + VERIFY(chksum, 0x17bb17bb, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(buf, sizeof(buf)); + VERIFY(chksum, 0xfc856608, "H5_checksum_crc"); /* Buffer w/zero(s) for data */ HDmemset(buf, 0, sizeof(buf)); - chksum = H5_fletcher32(buf, sizeof(buf)); - VERIFY(chksum, 0, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(buf, sizeof(buf)); + VERIFY(chksum, 0, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(buf, sizeof(buf)); + VERIFY(chksum, 0xfc7e9b20, "H5_checksum_crc"); } /* test_chksum_size_two() */ @@ -95,13 +107,19 @@ test_chksum_size_three(void) uint32_t chksum; /* Checksum value */ /* Buffer w/real data */ - chksum = H5_fletcher32(buf, sizeof(buf)); - VERIFY(chksum, 0x917679bb, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(buf, sizeof(buf)); + VERIFY(chksum, 0x917679bb, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(buf, sizeof(buf)); + VERIFY(chksum, 0xfebc5d70, "H5_checksum_crc"); /* Buffer w/zero(s) for data */ HDmemset(buf, 0, sizeof(buf)); - chksum = H5_fletcher32(buf, sizeof(buf)); - VERIFY(chksum, 0, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(buf, sizeof(buf)); + VERIFY(chksum, 0, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(buf, sizeof(buf)); + VERIFY(chksum, 0xf9cc4c7a, "H5_checksum_crc"); } /* test_chksum_size_three() */ @@ -117,13 +135,19 @@ test_chksum_size_four(void) uint32_t chksum; /* Checksum value */ /* Buffer w/real data */ - chksum = H5_fletcher32(buf, sizeof(buf)); - VERIFY(chksum, 0x924f7a94, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(buf, sizeof(buf)); + VERIFY(chksum, 0x924f7a94, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(buf, sizeof(buf)); + VERIFY(chksum, 0xff398a46, "H5_checksum_crc"); /* Buffer w/zero(s) for data */ HDmemset(buf, 0, sizeof(buf)); - chksum = H5_fletcher32(buf, sizeof(buf)); - VERIFY(chksum, 0, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(buf, sizeof(buf)); + VERIFY(chksum, 0, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(buf, sizeof(buf)); + VERIFY(chksum, 0xff117081, "H5_checksum_crc"); } /* test_chksum_size_four() */ @@ -143,13 +167,19 @@ test_chksum_large(void) large_buf[u] = u * 3; /* Buffer w/real data */ - chksum = H5_fletcher32(large_buf, sizeof(large_buf)); - VERIFY(chksum, 0x85b4e2a, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(large_buf, sizeof(large_buf)); + VERIFY(chksum, 0x85b4e2a, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(large_buf, sizeof(large_buf)); + VERIFY(chksum, 0xfbd0f7c0, "H5_checksum_crc"); /* Buffer w/zero(s) for data */ HDmemset(large_buf, 0, sizeof(large_buf)); - chksum = H5_fletcher32(large_buf, sizeof(large_buf)); - VERIFY(chksum, 0, "H5_fletcher32"); + chksum = H5_checksum_fletcher32(large_buf, sizeof(large_buf)); + VERIFY(chksum, 0, "H5_checksum_fletcher32"); + + chksum = H5_checksum_crc(large_buf, sizeof(large_buf)); + VERIFY(chksum, 0xfac8b4c4, "H5_checksum_crc"); } /* test_chksum_large() */ @@ -162,7 +192,7 @@ void test_checksum(void) { /* Output message about test being performed */ - MESSAGE(5, ("Testing checksum algorithm\n")); + MESSAGE(5, ("Testing checksum algorithms\n")); /* Various checks for fletcher32 checksum algorithm */ test_chksum_size_one(); /* Test buffer w/only 1 byte */ -- cgit v0.12