On 09/12/2014 10:54 PM, Abhijit Menon-Sen wrote:
At 2014-09-12 22:38:01 +0300, hlinnakan...@vmware.com wrote:
We probably should consider switching to a faster CRC algorithm again,
regardless of what we do with compression.
As it happens, I'm already working on resurrecting a patch that Andres
posted in 2010 to switch to zlib's faster CRC implementation.
As it happens, I also wrote an implementation of Slice-by-4 the other
day :-). Haven't gotten around to post it, but here it is.
What algorithm does zlib use for CRC calculation?
- Heikki
diff --git a/src/include/utils/pg_crc.h b/src/include/utils/pg_crc.h
index 375c405..da1af98 100644
--- a/src/include/utils/pg_crc.h
+++ b/src/include/utils/pg_crc.h
@@ -37,25 +37,60 @@ typedef uint32 pg_crc32;
/* Finish a CRC calculation */
#define FIN_CRC32(crc) ((crc) ^= 0xFFFFFFFF)
+static inline uint32
+swap(uint32 x)
+{
+ /* XXX: use configure check for this? */
+#if defined(__GNUC__) || defined(__clang__)
+ return __builtin_bswap32(x);
+#else
+ return (x >> 24) | ((x >> 8) & 0x0000FF00) | ((x << 8) & 0x00FF0000) | (x << 24);
+#endif
+}
+
/* Accumulate some (more) bytes into a CRC */
#define COMP_CRC32(crc, data, len) \
do { \
const unsigned char *__data = (const unsigned char *) (data); \
uint32 __len = (len); \
+ pg_crc32 __crc = (crc); \
+ \
+ /* Process byte at a time until the data address is aligned */ \
+ while ((((uintptr_t) __data) & 3) != 0 && __len > 0) \
+ { \
+ int __tab_index = ((int) ((__crc) >> 24) ^ *__data++) & 0xFF; \
+ (__crc) = pg_crc32_table[0][__tab_index] ^ ((__crc) << 8); \
+ __len--; \
+ } \
+ /* Process 4 bytes a time */ \
+ while (__len >= 4) \
+ { \
+ uint32 *current = (uint32 *) __data; \
\
- while (__len-- > 0) \
+ (__crc) = swap(__crc); \
+ (__crc) ^= *current; \
+ (__crc) = pg_crc32_table[3][ (__crc) & 0xFF] \
+ ^ pg_crc32_table[2][((__crc)>>8 ) & 0xFF] \
+ ^ pg_crc32_table[1][((__crc)>>16) & 0xFF] \
+ ^ pg_crc32_table[0][ (__crc)>>24 ]; \
+ __len -= 4; \
+ __data += 4; \
+ } \
+ /* Process the last 0-3 bytes one byte at a time */ \
+ while (__len > 0) \
{ \
- int __tab_index = ((int) ((crc) >> 24) ^ *__data++) & 0xFF; \
- (crc) = pg_crc32_table[__tab_index] ^ ((crc) << 8); \
+ int __tab_index = ((int) ((__crc) >> 24) ^ *__data++) & 0xFF; \
+ (__crc) = pg_crc32_table[0][__tab_index] ^ ((__crc) << 8); \
+ __len--; \
} \
+ (crc) = __crc; \
} while (0)
/* Check for equality of two CRCs */
#define EQ_CRC32(c1,c2) ((c1) == (c2))
/* Constant table for CRC calculation */
-extern CRCDLLIMPORT const uint32 pg_crc32_table[];
-
+extern CRCDLLIMPORT const uint32 pg_crc32_table[4][256];
#ifdef PROVIDE_64BIT_CRC
diff --git a/src/include/utils/pg_crc_tables.h b/src/include/utils/pg_crc_tables.h
index a487ee4..fcc9a58 100644
--- a/src/include/utils/pg_crc_tables.h
+++ b/src/include/utils/pg_crc_tables.h
@@ -33,7 +33,9 @@
* x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.
* (This is the same polynomial used in Ethernet checksums, for instance.)
*/
-const uint32 pg_crc32_table[256] = {
+const uint32 pg_crc32_table[4][256] =
+{
+{
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
@@ -98,6 +100,205 @@ const uint32 pg_crc32_table[256] = {
0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
+},
+{
+ 0x00000000, 0xC951729F, 0x49D3E37F, 0x808291E0,
+ 0xF3A08CA3, 0x3AF1FE3C, 0xBA736FDC, 0x73221D43,
+ 0x3C301F07, 0xF5616D98, 0x75E3FC78, 0xBCB28EE7,
+ 0xCF9093A4, 0x06C1E13B, 0x864370DB, 0x4F120244,
+ 0xD41608D9, 0x1D477A46, 0x9DC5EBA6, 0x54949939,
+ 0x27B6847A, 0xEEE7F6E5, 0x6E656705, 0xA734159A,
+ 0xE82617DE, 0x21776541, 0xA1F5F4A1, 0x68A4863E,
+ 0x1B869B7D, 0xD2D7E9E2, 0x52557802, 0x9B040A9D,
+ 0xDF2B2124, 0x167A53BB, 0x96F8C25B, 0x5FA9B0C4,
+ 0x2C8BAD87, 0xE5DADF18, 0x65584EF8, 0xAC093C67,
+ 0xE31B3E23, 0x2A4A4CBC, 0xAAC8DD5C, 0x6399AFC3,
+ 0x10BBB280, 0xD9EAC01F, 0x596851FF, 0x90392360,
+ 0x0B3D29FD, 0xC26C5B62, 0x42EECA82, 0x8BBFB81D,
+ 0xF89DA55E, 0x31CCD7C1, 0xB14E4621, 0x781F34BE,
+ 0x370D36FA, 0xFE5C4465, 0x7EDED585, 0xB78FA71A,
+ 0xC4ADBA59, 0x0DFCC8C6, 0x8D7E5926, 0x442F2BB9,
+ 0x65274409, 0xAC763696, 0x2CF4A776, 0xE5A5D5E9,
+ 0x9687C8AA, 0x5FD6BA35, 0xDF542BD5, 0x1605594A,
+ 0x59175B0E, 0x90462991, 0x10C4B871, 0xD995CAEE,
+ 0xAAB7D7AD, 0x63E6A532, 0xE36434D2, 0x2A35464D,
+ 0xB1314CD0, 0x78603E4F, 0xF8E2AFAF, 0x31B3DD30,
+ 0x4291C073, 0x8BC0B2EC, 0x0B42230C, 0xC2135193,
+ 0x8D0153D7, 0x44502148, 0xC4D2B0A8, 0x0D83C237,
+ 0x7EA1DF74, 0xB7F0ADEB, 0x37723C0B, 0xFE234E94,
+ 0xBA0C652D, 0x735D17B2, 0xF3DF8652, 0x3A8EF4CD,
+ 0x49ACE98E, 0x80FD9B11, 0x007F0AF1, 0xC92E786E,
+ 0x863C7A2A, 0x4F6D08B5, 0xCFEF9955, 0x06BEEBCA,
+ 0x759CF689, 0xBCCD8416, 0x3C4F15F6, 0xF51E6769,
+ 0x6E1A6DF4, 0xA74B1F6B, 0x27C98E8B, 0xEE98FC14,
+ 0x9DBAE157, 0x54EB93C8, 0xD4690228, 0x1D3870B7,
+ 0x522A72F3, 0x9B7B006C, 0x1BF9918C, 0xD2A8E313,
+ 0xA18AFE50, 0x68DB8CCF, 0xE8591D2F, 0x21086FB0,
+ 0x6638BEC5, 0xAF69CC5A, 0x2FEB5DBA, 0xE6BA2F25,
+ 0x95983266, 0x5CC940F9, 0xDC4BD119, 0x151AA386,
+ 0x5A08A1C2, 0x9359D35D, 0x13DB42BD, 0xDA8A3022,
+ 0xA9A82D61, 0x60F95FFE, 0xE07BCE1E, 0x292ABC81,
+ 0xB22EB61C, 0x7B7FC483, 0xFBFD5563, 0x32AC27FC,
+ 0x418E3ABF, 0x88DF4820, 0x085DD9C0, 0xC10CAB5F,
+ 0x8E1EA91B, 0x474FDB84, 0xC7CD4A64, 0x0E9C38FB,
+ 0x7DBE25B8, 0xB4EF5727, 0x346DC6C7, 0xFD3CB458,
+ 0xB9139FE1, 0x7042ED7E, 0xF0C07C9E, 0x39910E01,
+ 0x4AB31342, 0x83E261DD, 0x0360F03D, 0xCA3182A2,
+ 0x852380E6, 0x4C72F279, 0xCCF06399, 0x05A11106,
+ 0x76830C45, 0xBFD27EDA, 0x3F50EF3A, 0xF6019DA5,
+ 0x6D059738, 0xA454E5A7, 0x24D67447, 0xED8706D8,
+ 0x9EA51B9B, 0x57F46904, 0xD776F8E4, 0x1E278A7B,
+ 0x5135883F, 0x9864FAA0, 0x18E66B40, 0xD1B719DF,
+ 0xA295049C, 0x6BC47603, 0xEB46E7E3, 0x2217957C,
+ 0x031FFACC, 0xCA4E8853, 0x4ACC19B3, 0x839D6B2C,
+ 0xF0BF766F, 0x39EE04F0, 0xB96C9510, 0x703DE78F,
+ 0x3F2FE5CB, 0xF67E9754, 0x76FC06B4, 0xBFAD742B,
+ 0xCC8F6968, 0x05DE1BF7, 0x855C8A17, 0x4C0DF888,
+ 0xD709F215, 0x1E58808A, 0x9EDA116A, 0x578B63F5,
+ 0x24A97EB6, 0xEDF80C29, 0x6D7A9DC9, 0xA42BEF56,
+ 0xEB39ED12, 0x22689F8D, 0xA2EA0E6D, 0x6BBB7CF2,
+ 0x189961B1, 0xD1C8132E, 0x514A82CE, 0x981BF051,
+ 0xDC34DBE8, 0x1565A977, 0x95E73897, 0x5CB64A08,
+ 0x2F94574B, 0xE6C525D4, 0x6647B434, 0xAF16C6AB,
+ 0xE004C4EF, 0x2955B670, 0xA9D72790, 0x6086550F,
+ 0x13A4484C, 0xDAF53AD3, 0x5A77AB33, 0x9326D9AC,
+ 0x0822D331, 0xC173A1AE, 0x41F1304E, 0x88A042D1,
+ 0xFB825F92, 0x32D32D0D, 0xB251BCED, 0x7B00CE72,
+ 0x3412CC36, 0xFD43BEA9, 0x7DC12F49, 0xB4905DD6,
+ 0xC7B24095, 0x0EE3320A, 0x8E61A3EA, 0x4730D175
+},
+{
+ 0x00000000, 0xB3CAE514, 0xDCE38634, 0x6F296320,
+ 0x843800A6, 0x37F2E5B2, 0x58DB8692, 0xEB116386,
+ 0x1F707B87, 0xACBA9E93, 0xC393FDB3, 0x705918A7,
+ 0x9B487B21, 0x28829E35, 0x47ABFD15, 0xF4611801,
+ 0x97B6CFCD, 0x247C2AD9, 0x4B5549F9, 0xF89FACED,
+ 0x138ECF6B, 0xA0442A7F, 0xCF6D495F, 0x7CA7AC4B,
+ 0x88C6B44A, 0x3B0C515E, 0x5425327E, 0xE7EFD76A,
+ 0x0CFEB4EC, 0xBF3451F8, 0xD01D32D8, 0x63D7D7CC,
+ 0x3D4DEB45, 0x8E870E51, 0xE1AE6D71, 0x52648865,
+ 0xB975EBE3, 0x0ABF0EF7, 0x65966DD7, 0xD65C88C3,
+ 0x223D90C2, 0x91F775D6, 0xFEDE16F6, 0x4D14F3E2,
+ 0xA6059064, 0x15CF7570, 0x7AE61650, 0xC92CF344,
+ 0xAAFB2488, 0x1931C19C, 0x7618A2BC, 0xC5D247A8,
+ 0x2EC3242E, 0x9D09C13A, 0xF220A21A, 0x41EA470E,
+ 0xB58B5F0F, 0x0641BA1B, 0x6968D93B, 0xDAA23C2F,
+ 0x31B35FA9, 0x8279BABD, 0xED50D99D, 0x5E9A3C89,
+ 0x1A9C9CD7, 0xA95679C3, 0xC67F1AE3, 0x75B5FFF7,
+ 0x9EA49C71, 0x2D6E7965, 0x42471A45, 0xF18DFF51,
+ 0x05ECE750, 0xB6260244, 0xD90F6164, 0x6AC58470,
+ 0x81D4E7F6, 0x321E02E2, 0x5D3761C2, 0xEEFD84D6,
+ 0x8D2A531A, 0x3EE0B60E, 0x51C9D52E, 0xE203303A,
+ 0x091253BC, 0xBAD8B6A8, 0xD5F1D588, 0x663B309C,
+ 0x925A289D, 0x2190CD89, 0x4EB9AEA9, 0xFD734BBD,
+ 0x1662283B, 0xA5A8CD2F, 0xCA81AE0F, 0x794B4B1B,
+ 0x27D17792, 0x941B9286, 0xFB32F1A6, 0x48F814B2,
+ 0xA3E97734, 0x10239220, 0x7F0AF100, 0xCCC01414,
+ 0x38A10C15, 0x8B6BE901, 0xE4428A21, 0x57886F35,
+ 0xBC990CB3, 0x0F53E9A7, 0x607A8A87, 0xD3B06F93,
+ 0xB067B85F, 0x03AD5D4B, 0x6C843E6B, 0xDF4EDB7F,
+ 0x345FB8F9, 0x87955DED, 0xE8BC3ECD, 0x5B76DBD9,
+ 0xAF17C3D8, 0x1CDD26CC, 0x73F445EC, 0xC03EA0F8,
+ 0x2B2FC37E, 0x98E5266A, 0xF7CC454A, 0x4406A05E,
+ 0x9C6F016D, 0x2FA5E479, 0x408C8759, 0xF346624D,
+ 0x185701CB, 0xAB9DE4DF, 0xC4B487FF, 0x777E62EB,
+ 0x831F7AEA, 0x30D59FFE, 0x5FFCFCDE, 0xEC3619CA,
+ 0x07277A4C, 0xB4ED9F58, 0xDBC4FC78, 0x680E196C,
+ 0x0BD9CEA0, 0xB8132BB4, 0xD73A4894, 0x64F0AD80,
+ 0x8FE1CE06, 0x3C2B2B12, 0x53024832, 0xE0C8AD26,
+ 0x14A9B527, 0xA7635033, 0xC84A3313, 0x7B80D607,
+ 0x9091B581, 0x235B5095, 0x4C7233B5, 0xFFB8D6A1,
+ 0xA122EA28, 0x12E80F3C, 0x7DC16C1C, 0xCE0B8908,
+ 0x251AEA8E, 0x96D00F9A, 0xF9F96CBA, 0x4A3389AE,
+ 0xBE5291AF, 0x0D9874BB, 0x62B1179B, 0xD17BF28F,
+ 0x3A6A9109, 0x89A0741D, 0xE689173D, 0x5543F229,
+ 0x369425E5, 0x855EC0F1, 0xEA77A3D1, 0x59BD46C5,
+ 0xB2AC2543, 0x0166C057, 0x6E4FA377, 0xDD854663,
+ 0x29E45E62, 0x9A2EBB76, 0xF507D856, 0x46CD3D42,
+ 0xADDC5EC4, 0x1E16BBD0, 0x713FD8F0, 0xC2F53DE4,
+ 0x86F39DBA, 0x353978AE, 0x5A101B8E, 0xE9DAFE9A,
+ 0x02CB9D1C, 0xB1017808, 0xDE281B28, 0x6DE2FE3C,
+ 0x9983E63D, 0x2A490329, 0x45606009, 0xF6AA851D,
+ 0x1DBBE69B, 0xAE71038F, 0xC15860AF, 0x729285BB,
+ 0x11455277, 0xA28FB763, 0xCDA6D443, 0x7E6C3157,
+ 0x957D52D1, 0x26B7B7C5, 0x499ED4E5, 0xFA5431F1,
+ 0x0E3529F0, 0xBDFFCCE4, 0xD2D6AFC4, 0x611C4AD0,
+ 0x8A0D2956, 0x39C7CC42, 0x56EEAF62, 0xE5244A76,
+ 0xBBBE76FF, 0x087493EB, 0x675DF0CB, 0xD49715DF,
+ 0x3F867659, 0x8C4C934D, 0xE365F06D, 0x50AF1579,
+ 0xA4CE0D78, 0x1704E86C, 0x782D8B4C, 0xCBE76E58,
+ 0x20F60DDE, 0x933CE8CA, 0xFC158BEA, 0x4FDF6EFE,
+ 0x2C08B932, 0x9FC25C26, 0xF0EB3F06, 0x4321DA12,
+ 0xA830B994, 0x1BFA5C80, 0x74D33FA0, 0xC719DAB4,
+ 0x3378C2B5, 0x80B227A1, 0xEF9B4481, 0x5C51A195,
+ 0xB740C213, 0x048A2707, 0x6BA34427, 0xD869A133
+},
+{
+ 0x00000000, 0x988DF636, 0x6CE3AAFF, 0xF46E5CC9,
+ 0xD2D5E139, 0x4A58170F, 0xBE364BC6, 0x26BBBDF0,
+ 0xFD738AF5, 0x65FE7CC3, 0x9190200A, 0x091DD63C,
+ 0x2FA66BCC, 0xB72B9DFA, 0x4345C133, 0xDBC83705,
+ 0xD8A4CBE7, 0x40293DD1, 0xB4476118, 0x2CCA972E,
+ 0x0A712ADE, 0x92FCDCE8, 0x66928021, 0xFE1F7617,
+ 0x25D74112, 0xBD5AB724, 0x4934EBED, 0xD1B91DDB,
+ 0xF702A02B, 0x6F8F561D, 0x9BE10AD4, 0x036CFCE2,
+ 0x15830911, 0x8D0EFF27, 0x7960A3EE, 0xE1ED55D8,
+ 0xC756E828, 0x5FDB1E1E, 0xABB542D7, 0x3338B4E1,
+ 0xE8F083E4, 0x707D75D2, 0x8413291B, 0x1C9EDF2D,
+ 0x3A2562DD, 0xA2A894EB, 0x56C6C822, 0xCE4B3E14,
+ 0xCD27C2F6, 0x55AA34C0, 0xA1C46809, 0x39499E3F,
+ 0x1FF223CF, 0x877FD5F9, 0x73118930, 0xEB9C7F06,
+ 0x30544803, 0xA8D9BE35, 0x5CB7E2FC, 0xC43A14CA,
+ 0xE281A93A, 0x7A0C5F0C, 0x8E6203C5, 0x16EFF5F3,
+ 0x61FE2E7A, 0xF973D84C, 0x0D1D8485, 0x959072B3,
+ 0xB32BCF43, 0x2BA63975, 0xDFC865BC, 0x4745938A,
+ 0x9C8DA48F, 0x040052B9, 0xF06E0E70, 0x68E3F846,
+ 0x4E5845B6, 0xD6D5B380, 0x22BBEF49, 0xBA36197F,
+ 0xB95AE59D, 0x21D713AB, 0xD5B94F62, 0x4D34B954,
+ 0x6B8F04A4, 0xF302F292, 0x076CAE5B, 0x9FE1586D,
+ 0x44296F68, 0xDCA4995E, 0x28CAC597, 0xB04733A1,
+ 0x96FC8E51, 0x0E717867, 0xFA1F24AE, 0x6292D298,
+ 0x747D276B, 0xECF0D15D, 0x189E8D94, 0x80137BA2,
+ 0xA6A8C652, 0x3E253064, 0xCA4B6CAD, 0x52C69A9B,
+ 0x890EAD9E, 0x11835BA8, 0xE5ED0761, 0x7D60F157,
+ 0x5BDB4CA7, 0xC356BA91, 0x3738E658, 0xAFB5106E,
+ 0xACD9EC8C, 0x34541ABA, 0xC03A4673, 0x58B7B045,
+ 0x7E0C0DB5, 0xE681FB83, 0x12EFA74A, 0x8A62517C,
+ 0x51AA6679, 0xC927904F, 0x3D49CC86, 0xA5C43AB0,
+ 0x837F8740, 0x1BF27176, 0xEF9C2DBF, 0x7711DB89,
+ 0x96B8B26F, 0x0E354459, 0xFA5B1890, 0x62D6EEA6,
+ 0x446D5356, 0xDCE0A560, 0x288EF9A9, 0xB0030F9F,
+ 0x6BCB389A, 0xF346CEAC, 0x07289265, 0x9FA56453,
+ 0xB91ED9A3, 0x21932F95, 0xD5FD735C, 0x4D70856A,
+ 0x4E1C7988, 0xD6918FBE, 0x22FFD377, 0xBA722541,
+ 0x9CC998B1, 0x04446E87, 0xF02A324E, 0x68A7C478,
+ 0xB36FF37D, 0x2BE2054B, 0xDF8C5982, 0x4701AFB4,
+ 0x61BA1244, 0xF937E472, 0x0D59B8BB, 0x95D44E8D,
+ 0x833BBB7E, 0x1BB64D48, 0xEFD81181, 0x7755E7B7,
+ 0x51EE5A47, 0xC963AC71, 0x3D0DF0B8, 0xA580068E,
+ 0x7E48318B, 0xE6C5C7BD, 0x12AB9B74, 0x8A266D42,
+ 0xAC9DD0B2, 0x34102684, 0xC07E7A4D, 0x58F38C7B,
+ 0x5B9F7099, 0xC31286AF, 0x377CDA66, 0xAFF12C50,
+ 0x894A91A0, 0x11C76796, 0xE5A93B5F, 0x7D24CD69,
+ 0xA6ECFA6C, 0x3E610C5A, 0xCA0F5093, 0x5282A6A5,
+ 0x74391B55, 0xECB4ED63, 0x18DAB1AA, 0x8057479C,
+ 0xF7469C15, 0x6FCB6A23, 0x9BA536EA, 0x0328C0DC,
+ 0x25937D2C, 0xBD1E8B1A, 0x4970D7D3, 0xD1FD21E5,
+ 0x0A3516E0, 0x92B8E0D6, 0x66D6BC1F, 0xFE5B4A29,
+ 0xD8E0F7D9, 0x406D01EF, 0xB4035D26, 0x2C8EAB10,
+ 0x2FE257F2, 0xB76FA1C4, 0x4301FD0D, 0xDB8C0B3B,
+ 0xFD37B6CB, 0x65BA40FD, 0x91D41C34, 0x0959EA02,
+ 0xD291DD07, 0x4A1C2B31, 0xBE7277F8, 0x26FF81CE,
+ 0x00443C3E, 0x98C9CA08, 0x6CA796C1, 0xF42A60F7,
+ 0xE2C59504, 0x7A486332, 0x8E263FFB, 0x16ABC9CD,
+ 0x3010743D, 0xA89D820B, 0x5CF3DEC2, 0xC47E28F4,
+ 0x1FB61FF1, 0x873BE9C7, 0x7355B50E, 0xEBD84338,
+ 0xCD63FEC8, 0x55EE08FE, 0xA1805437, 0x390DA201,
+ 0x3A615EE3, 0xA2ECA8D5, 0x5682F41C, 0xCE0F022A,
+ 0xE8B4BFDA, 0x703949EC, 0x84571525, 0x1CDAE313,
+ 0xC712D416, 0x5F9F2220, 0xABF17EE9, 0x337C88DF,
+ 0x15C7352F, 0x8D4AC319, 0x79249FD0, 0xE1A969E6
+}
};
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
