summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2006-09-05 23:06:54 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2006-09-05 23:06:54 (GMT)
commit46467e91b0c96f368b2ac75569dfab2d3a097ef8 (patch)
tree9028c68c57d3f0a06152823f768484d1d460562b
parent5afc64f31b1cb2f3907ad5fa5f1a1629d27fb5c4 (diff)
downloadhdf5-46467e91b0c96f368b2ac75569dfab2d3a097ef8.zip
hdf5-46467e91b0c96f368b2ac75569dfab2d3a097ef8.tar.gz
hdf5-46467e91b0c96f368b2ac75569dfab2d3a097ef8.tar.bz2
[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)
-rw-r--r--src/H5Zfletcher32.c4
-rw-r--r--src/H5checksum.c133
-rw-r--r--src/H5private.h3
-rw-r--r--test/tchecksum.c72
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 */