granicus.if.org Git - postgresql/blob - src/include/common/pg_crc.h

   1 /*
   2  * pg_crc.h
   3  *
   4  * PostgreSQL CRC support
   5  *
   6  * See Ross Williams' excellent introduction
   7  * A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, available from
   8  * http://www.ross.net/crc/ or several other net sites.
   9  *
  10  * We have three slightly different variants of a 32-bit CRC calculation:
  11  * CRC-32C (Castagnoli polynomial), CRC-32 (Ethernet polynomial), and a legacy
  12  * CRC-32 version that uses the lookup table in a funny way. They all consist
  13  * of four macros:
  14  *
  15  * INIT_<variant>(crc)
  16  *              Initialize a CRC accumulator
  17  *
  18  * COMP_<variant>(crc, data, len)
  19  *              Accumulate some (more) bytes into a CRC
  20  *
  21  * FIN_<variant>(crc)
  22  *              Finish a CRC calculation
  23  *
  24  * EQ_<variant>(c1, c2)
  25  *              Check for equality of two CRCs.
  26  *
  27  * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
  28  * Portions Copyright (c) 1994, Regents of the University of California
  29  *
  30  * src/include/common/pg_crc.h
  31  */
  32 #ifndef PG_CRC_H
  33 #define PG_CRC_H
  34
  35 /* ugly hack to let this be used in frontend and backend code on Cygwin */
  36 #ifdef FRONTEND
  37 #define CRCDLLIMPORT
  38 #else
  39 #define CRCDLLIMPORT PGDLLIMPORT
  40 #endif
  41
  42 typedef uint32 pg_crc32;
  43
  44 /*
  45  * CRC calculation using the CRC-32C (Castagnoli) polynomial.
  46  *
  47  * We use all-ones as the initial register contents and final bit inversion.
  48  * This is the same algorithm used e.g. in iSCSI. See RFC 3385 for more
  49  * details on the choice of polynomial.
  50  */
  51 #define INIT_CRC32C(crc) ((crc) = 0xFFFFFFFF)
  52 #define FIN_CRC32C(crc) ((crc) ^= 0xFFFFFFFF)
  53 #define COMP_CRC32C(crc, data, len)     \
  54         COMP_CRC32_NORMAL_TABLE(crc, data, len, pg_crc32c_table)
  55 #define EQ_CRC32C(c1, c2) ((c1) == (c2))
  56
  57 /*
  58  * CRC-32, the same used e.g. in Ethernet.
  59  *
  60  * This is currently only used in ltree and hstore contrib modules. It uses
  61  * the same lookup table as the legacy algorithm below. New code should
  62  * use the Castagnoli version instead.
  63  */
  64 #define INIT_TRADITIONAL_CRC32(crc) ((crc) = 0xFFFFFFFF)
  65 #define FIN_TRADITIONAL_CRC32(crc)      ((crc) ^= 0xFFFFFFFF)
  66 #define COMP_TRADITIONAL_CRC32(crc, data, len)  \
  67         COMP_CRC32_NORMAL_TABLE(crc, data, len, pg_crc32_table)
  68 #define EQ_TRADITIONAL_CRC32(c1, c2) ((c1) == (c2))
  69
  70 /*
  71  * The CRC algorithm used for WAL et al in pre-9.5 versions.
  72  *
  73  * This closely resembles the normal CRC-32 algorithm, but is subtly
  74  * different. Using Williams' terms, we use the "normal" table, but with
  75  * "reflected" code. That's bogus, but it was like that for years before
  76  * anyone noticed. It does not correspond to any polynomial in a normal CRC
  77  * algorithm, so it's not clear what the error-detection properties of this
  78  * algorithm actually are.
  79  *
  80  * We still need to carry this around because it is used in a few on-disk
  81  * structures that need to be pg_upgradeable. It should not be used in new
  82  * code.
  83  */
  84 #define INIT_LEGACY_CRC32(crc) ((crc) = 0xFFFFFFFF)
  85 #define FIN_LEGACY_CRC32(crc)   ((crc) ^= 0xFFFFFFFF)
  86 #define COMP_LEGACY_CRC32(crc, data, len)       \
  87         COMP_CRC32_REFLECTED_TABLE(crc, data, len, pg_crc32_table)
  88 #define EQ_LEGACY_CRC32(c1, c2) ((c1) == (c2))
  89
  90 /*
  91  * Common code for CRC computation using a lookup table.
  92  */
  93 #define COMP_CRC32_NORMAL_TABLE(crc, data, len, table)                    \
  94 do {                                                                                                                      \
  95         const unsigned char *__data = (const unsigned char *) (data); \
  96         uint32          __len = (len); \
  97 \
  98         while (__len-- > 0) \
  99         { \
 100                 int             __tab_index = ((int) (crc) ^ *__data++) & 0xFF; \
 101                 (crc) = table[__tab_index] ^ ((crc) >> 8); \
 102         } \
 103 } while (0)
 104
 105 #define COMP_CRC32_REFLECTED_TABLE(crc, data, len, table) \
 106 do {                                                                                                                      \
 107         const unsigned char *__data = (const unsigned char *) (data); \
 108         uint32          __len = (len); \
 109 \
 110         while (__len-- > 0) \
 111         { \
 112                 int             __tab_index = ((int) ((crc) >> 24) ^ *__data++) & 0xFF; \
 113                 (crc) = table[__tab_index] ^ ((crc) << 8); \
 114         } \
 115 } while (0)
 116
 117 /* Constant tables for CRC-32C and CRC-32 polynomials */
 118 extern CRCDLLIMPORT const uint32 pg_crc32c_table[];
 119 extern CRCDLLIMPORT const uint32 pg_crc32_table[];
 120
 121 #endif   /* PG_CRC_H */