[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)

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 */