PostgreSQL Source Code  git master
pg_crc.h
Go to the documentation of this file.
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://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  * The CRC-32C variant is in port/pg_crc32c.h.
28  *
29  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
30  * Portions Copyright (c) 1994, Regents of the University of California
31  *
32  * src/include/utils/pg_crc.h
33  */
34 #ifndef PG_CRC_H
35 #define PG_CRC_H
36 
37 typedef uint32 pg_crc32;
38 
39 /*
40  * CRC-32, the same used e.g. in Ethernet.
41  *
42  * This is currently only used in ltree and hstore contrib modules. It uses
43  * the same lookup table as the legacy algorithm below. New code should
44  * use the Castagnoli version instead.
45  */
46 #define INIT_TRADITIONAL_CRC32(crc) ((crc) = 0xFFFFFFFF)
47 #define FIN_TRADITIONAL_CRC32(crc) ((crc) ^= 0xFFFFFFFF)
48 #define COMP_TRADITIONAL_CRC32(crc, data, len) \
49  COMP_CRC32_NORMAL_TABLE(crc, data, len, pg_crc32_table)
50 #define EQ_TRADITIONAL_CRC32(c1, c2) ((c1) == (c2))
51 
52 /* Sarwate's algorithm, for use with a "normal" lookup table */
53 #define COMP_CRC32_NORMAL_TABLE(crc, data, len, table) \
54 do { \
55  const unsigned char *__data = (const unsigned char *) (data); \
56  uint32 __len = (len); \
57 \
58  while (__len-- > 0) \
59  { \
60  int __tab_index = ((int) (crc) ^ *__data++) & 0xFF; \
61  (crc) = table[__tab_index] ^ ((crc) >> 8); \
62  } \
63 } while (0)
64 
65 /*
66  * The CRC algorithm used for WAL et al in pre-9.5 versions.
67  *
68  * This closely resembles the normal CRC-32 algorithm, but is subtly
69  * different. Using Williams' terms, we use the "normal" table, but with
70  * "reflected" code. That's bogus, but it was like that for years before
71  * anyone noticed. It does not correspond to any polynomial in a normal CRC
72  * algorithm, so it's not clear what the error-detection properties of this
73  * algorithm actually are.
74  *
75  * We still need to carry this around because it is used in a few on-disk
76  * structures that need to be pg_upgradeable. It should not be used in new
77  * code.
78  */
79 #define INIT_LEGACY_CRC32(crc) ((crc) = 0xFFFFFFFF)
80 #define FIN_LEGACY_CRC32(crc) ((crc) ^= 0xFFFFFFFF)
81 #define COMP_LEGACY_CRC32(crc, data, len) \
82  COMP_CRC32_REFLECTED_TABLE(crc, data, len, pg_crc32_table)
83 #define EQ_LEGACY_CRC32(c1, c2) ((c1) == (c2))
84 
85 /*
86  * Sarwate's algorithm, for use with a "reflected" lookup table (but in the
87  * legacy algorithm, we actually use it on a "normal" table, see above)
88  */
89 #define COMP_CRC32_REFLECTED_TABLE(crc, data, len, table) \
90 do { \
91  const unsigned char *__data = (const unsigned char *) (data); \
92  uint32 __len = (len); \
93 \
94  while (__len-- > 0) \
95  { \
96  int __tab_index = ((int) ((crc) >> 24) ^ *__data++) & 0xFF; \
97  (crc) = table[__tab_index] ^ ((crc) << 8); \
98  } \
99 } while (0)
100 
101 /*
102  * Constant table for the CRC-32 polynomials. The same table is used by both
103  * the normal and traditional variants.
104  */
105 extern PGDLLIMPORT const uint32 pg_crc32_table[256];
106 
107 #endif /* PG_CRC_H */
unsigned int uint32
Definition: c.h:493
#define PGDLLIMPORT
Definition: c.h:1303
PGDLLIMPORT const uint32 pg_crc32_table[256]
Definition: pg_crc.c:32
uint32 pg_crc32
Definition: pg_crc.h:37