1 /*-------------------------------------------------------------------------
4 * PostgreSQL 64-bit CRC support
6 * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $Header: /cvsroot/pgsql/src/backend/utils/hash/pg_crc.c,v 1.1 2001/03/13 01:17:06 tgl Exp $
13 *-------------------------------------------------------------------------
17 #include "utils/pg_crc.h"
20 #ifdef INT64_IS_BUSTED
22 const uint32 crc_table0[256] = {
23 0x00000000, 0xA9EA3693,
24 0x53D46D26, 0xFA3E5BB5,
25 0x0E42ECDF, 0xA7A8DA4C,
26 0x5D9681F9, 0xF47CB76A,
27 0x1C85D9BE, 0xB56FEF2D,
28 0x4F51B498, 0xE6BB820B,
29 0x12C73561, 0xBB2D03F2,
30 0x41135847, 0xE8F96ED4,
31 0x90E185EF, 0x390BB37C,
32 0xC335E8C9, 0x6ADFDE5A,
33 0x9EA36930, 0x37495FA3,
34 0xCD770416, 0x649D3285,
35 0x8C645C51, 0x258E6AC2,
36 0xDFB03177, 0x765A07E4,
37 0x8226B08E, 0x2BCC861D,
38 0xD1F2DDA8, 0x7818EB3B,
39 0x21C30BDE, 0x88293D4D,
40 0x721766F8, 0xDBFD506B,
41 0x2F81E701, 0x866BD192,
42 0x7C558A27, 0xD5BFBCB4,
43 0x3D46D260, 0x94ACE4F3,
44 0x6E92BF46, 0xC77889D5,
45 0x33043EBF, 0x9AEE082C,
46 0x60D05399, 0xC93A650A,
47 0xB1228E31, 0x18C8B8A2,
48 0xE2F6E317, 0x4B1CD584,
49 0xBF6062EE, 0x168A547D,
50 0xECB40FC8, 0x455E395B,
51 0xADA7578F, 0x044D611C,
52 0xFE733AA9, 0x57990C3A,
53 0xA3E5BB50, 0x0A0F8DC3,
54 0xF031D676, 0x59DBE0E5,
55 0xEA6C212F, 0x438617BC,
56 0xB9B84C09, 0x10527A9A,
57 0xE42ECDF0, 0x4DC4FB63,
58 0xB7FAA0D6, 0x1E109645,
59 0xF6E9F891, 0x5F03CE02,
60 0xA53D95B7, 0x0CD7A324,
61 0xF8AB144E, 0x514122DD,
62 0xAB7F7968, 0x02954FFB,
63 0x7A8DA4C0, 0xD3679253,
64 0x2959C9E6, 0x80B3FF75,
65 0x74CF481F, 0xDD257E8C,
66 0x271B2539, 0x8EF113AA,
67 0x66087D7E, 0xCFE24BED,
68 0x35DC1058, 0x9C3626CB,
69 0x684A91A1, 0xC1A0A732,
70 0x3B9EFC87, 0x9274CA14,
71 0xCBAF2AF1, 0x62451C62,
72 0x987B47D7, 0x31917144,
73 0xC5EDC62E, 0x6C07F0BD,
74 0x9639AB08, 0x3FD39D9B,
75 0xD72AF34F, 0x7EC0C5DC,
76 0x84FE9E69, 0x2D14A8FA,
77 0xD9681F90, 0x70822903,
78 0x8ABC72B6, 0x23564425,
79 0x5B4EAF1E, 0xF2A4998D,
80 0x089AC238, 0xA170F4AB,
81 0x550C43C1, 0xFCE67552,
82 0x06D82EE7, 0xAF321874,
83 0x47CB76A0, 0xEE214033,
84 0x141F1B86, 0xBDF52D15,
85 0x49899A7F, 0xE063ACEC,
86 0x1A5DF759, 0xB3B7C1CA,
87 0x7D3274CD, 0xD4D8425E,
88 0x2EE619EB, 0x870C2F78,
89 0x73709812, 0xDA9AAE81,
90 0x20A4F534, 0x894EC3A7,
91 0x61B7AD73, 0xC85D9BE0,
92 0x3263C055, 0x9B89F6C6,
93 0x6FF541AC, 0xC61F773F,
94 0x3C212C8A, 0x95CB1A19,
95 0xEDD3F122, 0x4439C7B1,
96 0xBE079C04, 0x17EDAA97,
97 0xE3911DFD, 0x4A7B2B6E,
98 0xB04570DB, 0x19AF4648,
99 0xF156289C, 0x58BC1E0F,
100 0xA28245BA, 0x0B687329,
101 0xFF14C443, 0x56FEF2D0,
102 0xACC0A965, 0x052A9FF6,
103 0x5CF17F13, 0xF51B4980,
104 0x0F251235, 0xA6CF24A6,
105 0x52B393CC, 0xFB59A55F,
106 0x0167FEEA, 0xA88DC879,
107 0x4074A6AD, 0xE99E903E,
108 0x13A0CB8B, 0xBA4AFD18,
109 0x4E364A72, 0xE7DC7CE1,
110 0x1DE22754, 0xB40811C7,
111 0xCC10FAFC, 0x65FACC6F,
112 0x9FC497DA, 0x362EA149,
113 0xC2521623, 0x6BB820B0,
114 0x91867B05, 0x386C4D96,
115 0xD0952342, 0x797F15D1,
116 0x83414E64, 0x2AAB78F7,
117 0xDED7CF9D, 0x773DF90E,
118 0x8D03A2BB, 0x24E99428,
119 0x975E55E2, 0x3EB46371,
120 0xC48A38C4, 0x6D600E57,
121 0x991CB93D, 0x30F68FAE,
122 0xCAC8D41B, 0x6322E288,
123 0x8BDB8C5C, 0x2231BACF,
124 0xD80FE17A, 0x71E5D7E9,
125 0x85996083, 0x2C735610,
126 0xD64D0DA5, 0x7FA73B36,
127 0x07BFD00D, 0xAE55E69E,
128 0x546BBD2B, 0xFD818BB8,
129 0x09FD3CD2, 0xA0170A41,
130 0x5A2951F4, 0xF3C36767,
131 0x1B3A09B3, 0xB2D03F20,
132 0x48EE6495, 0xE1045206,
133 0x1578E56C, 0xBC92D3FF,
134 0x46AC884A, 0xEF46BED9,
135 0xB69D5E3C, 0x1F7768AF,
136 0xE549331A, 0x4CA30589,
137 0xB8DFB2E3, 0x11358470,
138 0xEB0BDFC5, 0x42E1E956,
139 0xAA188782, 0x03F2B111,
140 0xF9CCEAA4, 0x5026DC37,
141 0xA45A6B5D, 0x0DB05DCE,
142 0xF78E067B, 0x5E6430E8,
143 0x267CDBD3, 0x8F96ED40,
144 0x75A8B6F5, 0xDC428066,
145 0x283E370C, 0x81D4019F,
146 0x7BEA5A2A, 0xD2006CB9,
147 0x3AF9026D, 0x931334FE,
148 0x692D6F4B, 0xC0C759D8,
149 0x34BBEEB2, 0x9D51D821,
150 0x676F8394, 0xCE85B507
153 const uint32 crc_table1[256] = {
154 0x00000000, 0x42F0E1EB,
155 0x85E1C3D7, 0xC711223C,
156 0x49336645, 0x0BC387AE,
157 0xCCD2A592, 0x8E224479,
158 0x9266CC8A, 0xD0962D61,
159 0x17870F5D, 0x5577EEB6,
160 0xDB55AACF, 0x99A54B24,
161 0x5EB46918, 0x1C4488F3,
162 0x663D78FF, 0x24CD9914,
163 0xE3DCBB28, 0xA12C5AC3,
164 0x2F0E1EBA, 0x6DFEFF51,
165 0xAAEFDD6D, 0xE81F3C86,
166 0xF45BB475, 0xB6AB559E,
167 0x71BA77A2, 0x334A9649,
168 0xBD68D230, 0xFF9833DB,
169 0x388911E7, 0x7A79F00C,
170 0xCC7AF1FF, 0x8E8A1014,
171 0x499B3228, 0x0B6BD3C3,
172 0x854997BA, 0xC7B97651,
173 0x00A8546D, 0x4258B586,
174 0x5E1C3D75, 0x1CECDC9E,
175 0xDBFDFEA2, 0x990D1F49,
176 0x172F5B30, 0x55DFBADB,
177 0x92CE98E7, 0xD03E790C,
178 0xAA478900, 0xE8B768EB,
179 0x2FA64AD7, 0x6D56AB3C,
180 0xE374EF45, 0xA1840EAE,
181 0x66952C92, 0x2465CD79,
182 0x3821458A, 0x7AD1A461,
183 0xBDC0865D, 0xFF3067B6,
184 0x711223CF, 0x33E2C224,
185 0xF4F3E018, 0xB60301F3,
186 0xDA050215, 0x98F5E3FE,
187 0x5FE4C1C2, 0x1D142029,
188 0x93366450, 0xD1C685BB,
189 0x16D7A787, 0x5427466C,
190 0x4863CE9F, 0x0A932F74,
191 0xCD820D48, 0x8F72ECA3,
192 0x0150A8DA, 0x43A04931,
193 0x84B16B0D, 0xC6418AE6,
194 0xBC387AEA, 0xFEC89B01,
195 0x39D9B93D, 0x7B2958D6,
196 0xF50B1CAF, 0xB7FBFD44,
197 0x70EADF78, 0x321A3E93,
198 0x2E5EB660, 0x6CAE578B,
199 0xABBF75B7, 0xE94F945C,
200 0x676DD025, 0x259D31CE,
201 0xE28C13F2, 0xA07CF219,
202 0x167FF3EA, 0x548F1201,
203 0x939E303D, 0xD16ED1D6,
204 0x5F4C95AF, 0x1DBC7444,
205 0xDAAD5678, 0x985DB793,
206 0x84193F60, 0xC6E9DE8B,
207 0x01F8FCB7, 0x43081D5C,
208 0xCD2A5925, 0x8FDAB8CE,
209 0x48CB9AF2, 0x0A3B7B19,
210 0x70428B15, 0x32B26AFE,
211 0xF5A348C2, 0xB753A929,
212 0x3971ED50, 0x7B810CBB,
213 0xBC902E87, 0xFE60CF6C,
214 0xE224479F, 0xA0D4A674,
215 0x67C58448, 0x253565A3,
216 0xAB1721DA, 0xE9E7C031,
217 0x2EF6E20D, 0x6C0603E6,
218 0xF6FAE5C0, 0xB40A042B,
219 0x731B2617, 0x31EBC7FC,
220 0xBFC98385, 0xFD39626E,
221 0x3A284052, 0x78D8A1B9,
222 0x649C294A, 0x266CC8A1,
223 0xE17DEA9D, 0xA38D0B76,
224 0x2DAF4F0F, 0x6F5FAEE4,
225 0xA84E8CD8, 0xEABE6D33,
226 0x90C79D3F, 0xD2377CD4,
227 0x15265EE8, 0x57D6BF03,
228 0xD9F4FB7A, 0x9B041A91,
229 0x5C1538AD, 0x1EE5D946,
230 0x02A151B5, 0x4051B05E,
231 0x87409262, 0xC5B07389,
232 0x4B9237F0, 0x0962D61B,
233 0xCE73F427, 0x8C8315CC,
234 0x3A80143F, 0x7870F5D4,
235 0xBF61D7E8, 0xFD913603,
236 0x73B3727A, 0x31439391,
237 0xF652B1AD, 0xB4A25046,
238 0xA8E6D8B5, 0xEA16395E,
239 0x2D071B62, 0x6FF7FA89,
240 0xE1D5BEF0, 0xA3255F1B,
241 0x64347D27, 0x26C49CCC,
242 0x5CBD6CC0, 0x1E4D8D2B,
243 0xD95CAF17, 0x9BAC4EFC,
244 0x158E0A85, 0x577EEB6E,
245 0x906FC952, 0xD29F28B9,
246 0xCEDBA04A, 0x8C2B41A1,
247 0x4B3A639D, 0x09CA8276,
248 0x87E8C60F, 0xC51827E4,
249 0x020905D8, 0x40F9E433,
250 0x2CFFE7D5, 0x6E0F063E,
251 0xA91E2402, 0xEBEEC5E9,
252 0x65CC8190, 0x273C607B,
253 0xE02D4247, 0xA2DDA3AC,
254 0xBE992B5F, 0xFC69CAB4,
255 0x3B78E888, 0x79880963,
256 0xF7AA4D1A, 0xB55AACF1,
257 0x724B8ECD, 0x30BB6F26,
258 0x4AC29F2A, 0x08327EC1,
259 0xCF235CFD, 0x8DD3BD16,
260 0x03F1F96F, 0x41011884,
261 0x86103AB8, 0xC4E0DB53,
262 0xD8A453A0, 0x9A54B24B,
263 0x5D459077, 0x1FB5719C,
264 0x919735E5, 0xD367D40E,
265 0x1476F632, 0x568617D9,
266 0xE085162A, 0xA275F7C1,
267 0x6564D5FD, 0x27943416,
268 0xA9B6706F, 0xEB469184,
269 0x2C57B3B8, 0x6EA75253,
270 0x72E3DAA0, 0x30133B4B,
271 0xF7021977, 0xB5F2F89C,
272 0x3BD0BCE5, 0x79205D0E,
273 0xBE317F32, 0xFCC19ED9,
274 0x86B86ED5, 0xC4488F3E,
275 0x0359AD02, 0x41A94CE9,
276 0xCF8B0890, 0x8D7BE97B,
277 0x4A6ACB47, 0x089A2AAC,
278 0x14DEA25F, 0x562E43B4,
279 0x913F6188, 0xD3CF8063,
280 0x5DEDC41A, 0x1F1D25F1,
281 0xD80C07CD, 0x9AFCE626
284 #else /* int64 works */
286 const uint64 crc_table[256] = {
287 0x0000000000000000, 0x42F0E1EBA9EA3693,
288 0x85E1C3D753D46D26, 0xC711223CFA3E5BB5,
289 0x493366450E42ECDF, 0x0BC387AEA7A8DA4C,
290 0xCCD2A5925D9681F9, 0x8E224479F47CB76A,
291 0x9266CC8A1C85D9BE, 0xD0962D61B56FEF2D,
292 0x17870F5D4F51B498, 0x5577EEB6E6BB820B,
293 0xDB55AACF12C73561, 0x99A54B24BB2D03F2,
294 0x5EB4691841135847, 0x1C4488F3E8F96ED4,
295 0x663D78FF90E185EF, 0x24CD9914390BB37C,
296 0xE3DCBB28C335E8C9, 0xA12C5AC36ADFDE5A,
297 0x2F0E1EBA9EA36930, 0x6DFEFF5137495FA3,
298 0xAAEFDD6DCD770416, 0xE81F3C86649D3285,
299 0xF45BB4758C645C51, 0xB6AB559E258E6AC2,
300 0x71BA77A2DFB03177, 0x334A9649765A07E4,
301 0xBD68D2308226B08E, 0xFF9833DB2BCC861D,
302 0x388911E7D1F2DDA8, 0x7A79F00C7818EB3B,
303 0xCC7AF1FF21C30BDE, 0x8E8A101488293D4D,
304 0x499B3228721766F8, 0x0B6BD3C3DBFD506B,
305 0x854997BA2F81E701, 0xC7B97651866BD192,
306 0x00A8546D7C558A27, 0x4258B586D5BFBCB4,
307 0x5E1C3D753D46D260, 0x1CECDC9E94ACE4F3,
308 0xDBFDFEA26E92BF46, 0x990D1F49C77889D5,
309 0x172F5B3033043EBF, 0x55DFBADB9AEE082C,
310 0x92CE98E760D05399, 0xD03E790CC93A650A,
311 0xAA478900B1228E31, 0xE8B768EB18C8B8A2,
312 0x2FA64AD7E2F6E317, 0x6D56AB3C4B1CD584,
313 0xE374EF45BF6062EE, 0xA1840EAE168A547D,
314 0x66952C92ECB40FC8, 0x2465CD79455E395B,
315 0x3821458AADA7578F, 0x7AD1A461044D611C,
316 0xBDC0865DFE733AA9, 0xFF3067B657990C3A,
317 0x711223CFA3E5BB50, 0x33E2C2240A0F8DC3,
318 0xF4F3E018F031D676, 0xB60301F359DBE0E5,
319 0xDA050215EA6C212F, 0x98F5E3FE438617BC,
320 0x5FE4C1C2B9B84C09, 0x1D14202910527A9A,
321 0x93366450E42ECDF0, 0xD1C685BB4DC4FB63,
322 0x16D7A787B7FAA0D6, 0x5427466C1E109645,
323 0x4863CE9FF6E9F891, 0x0A932F745F03CE02,
324 0xCD820D48A53D95B7, 0x8F72ECA30CD7A324,
325 0x0150A8DAF8AB144E, 0x43A04931514122DD,
326 0x84B16B0DAB7F7968, 0xC6418AE602954FFB,
327 0xBC387AEA7A8DA4C0, 0xFEC89B01D3679253,
328 0x39D9B93D2959C9E6, 0x7B2958D680B3FF75,
329 0xF50B1CAF74CF481F, 0xB7FBFD44DD257E8C,
330 0x70EADF78271B2539, 0x321A3E938EF113AA,
331 0x2E5EB66066087D7E, 0x6CAE578BCFE24BED,
332 0xABBF75B735DC1058, 0xE94F945C9C3626CB,
333 0x676DD025684A91A1, 0x259D31CEC1A0A732,
334 0xE28C13F23B9EFC87, 0xA07CF2199274CA14,
335 0x167FF3EACBAF2AF1, 0x548F120162451C62,
336 0x939E303D987B47D7, 0xD16ED1D631917144,
337 0x5F4C95AFC5EDC62E, 0x1DBC74446C07F0BD,
338 0xDAAD56789639AB08, 0x985DB7933FD39D9B,
339 0x84193F60D72AF34F, 0xC6E9DE8B7EC0C5DC,
340 0x01F8FCB784FE9E69, 0x43081D5C2D14A8FA,
341 0xCD2A5925D9681F90, 0x8FDAB8CE70822903,
342 0x48CB9AF28ABC72B6, 0x0A3B7B1923564425,
343 0x70428B155B4EAF1E, 0x32B26AFEF2A4998D,
344 0xF5A348C2089AC238, 0xB753A929A170F4AB,
345 0x3971ED50550C43C1, 0x7B810CBBFCE67552,
346 0xBC902E8706D82EE7, 0xFE60CF6CAF321874,
347 0xE224479F47CB76A0, 0xA0D4A674EE214033,
348 0x67C58448141F1B86, 0x253565A3BDF52D15,
349 0xAB1721DA49899A7F, 0xE9E7C031E063ACEC,
350 0x2EF6E20D1A5DF759, 0x6C0603E6B3B7C1CA,
351 0xF6FAE5C07D3274CD, 0xB40A042BD4D8425E,
352 0x731B26172EE619EB, 0x31EBC7FC870C2F78,
353 0xBFC9838573709812, 0xFD39626EDA9AAE81,
354 0x3A28405220A4F534, 0x78D8A1B9894EC3A7,
355 0x649C294A61B7AD73, 0x266CC8A1C85D9BE0,
356 0xE17DEA9D3263C055, 0xA38D0B769B89F6C6,
357 0x2DAF4F0F6FF541AC, 0x6F5FAEE4C61F773F,
358 0xA84E8CD83C212C8A, 0xEABE6D3395CB1A19,
359 0x90C79D3FEDD3F122, 0xD2377CD44439C7B1,
360 0x15265EE8BE079C04, 0x57D6BF0317EDAA97,
361 0xD9F4FB7AE3911DFD, 0x9B041A914A7B2B6E,
362 0x5C1538ADB04570DB, 0x1EE5D94619AF4648,
363 0x02A151B5F156289C, 0x4051B05E58BC1E0F,
364 0x87409262A28245BA, 0xC5B073890B687329,
365 0x4B9237F0FF14C443, 0x0962D61B56FEF2D0,
366 0xCE73F427ACC0A965, 0x8C8315CC052A9FF6,
367 0x3A80143F5CF17F13, 0x7870F5D4F51B4980,
368 0xBF61D7E80F251235, 0xFD913603A6CF24A6,
369 0x73B3727A52B393CC, 0x31439391FB59A55F,
370 0xF652B1AD0167FEEA, 0xB4A25046A88DC879,
371 0xA8E6D8B54074A6AD, 0xEA16395EE99E903E,
372 0x2D071B6213A0CB8B, 0x6FF7FA89BA4AFD18,
373 0xE1D5BEF04E364A72, 0xA3255F1BE7DC7CE1,
374 0x64347D271DE22754, 0x26C49CCCB40811C7,
375 0x5CBD6CC0CC10FAFC, 0x1E4D8D2B65FACC6F,
376 0xD95CAF179FC497DA, 0x9BAC4EFC362EA149,
377 0x158E0A85C2521623, 0x577EEB6E6BB820B0,
378 0x906FC95291867B05, 0xD29F28B9386C4D96,
379 0xCEDBA04AD0952342, 0x8C2B41A1797F15D1,
380 0x4B3A639D83414E64, 0x09CA82762AAB78F7,
381 0x87E8C60FDED7CF9D, 0xC51827E4773DF90E,
382 0x020905D88D03A2BB, 0x40F9E43324E99428,
383 0x2CFFE7D5975E55E2, 0x6E0F063E3EB46371,
384 0xA91E2402C48A38C4, 0xEBEEC5E96D600E57,
385 0x65CC8190991CB93D, 0x273C607B30F68FAE,
386 0xE02D4247CAC8D41B, 0xA2DDA3AC6322E288,
387 0xBE992B5F8BDB8C5C, 0xFC69CAB42231BACF,
388 0x3B78E888D80FE17A, 0x7988096371E5D7E9,
389 0xF7AA4D1A85996083, 0xB55AACF12C735610,
390 0x724B8ECDD64D0DA5, 0x30BB6F267FA73B36,
391 0x4AC29F2A07BFD00D, 0x08327EC1AE55E69E,
392 0xCF235CFD546BBD2B, 0x8DD3BD16FD818BB8,
393 0x03F1F96F09FD3CD2, 0x41011884A0170A41,
394 0x86103AB85A2951F4, 0xC4E0DB53F3C36767,
395 0xD8A453A01B3A09B3, 0x9A54B24BB2D03F20,
396 0x5D45907748EE6495, 0x1FB5719CE1045206,
397 0x919735E51578E56C, 0xD367D40EBC92D3FF,
398 0x1476F63246AC884A, 0x568617D9EF46BED9,
399 0xE085162AB69D5E3C, 0xA275F7C11F7768AF,
400 0x6564D5FDE549331A, 0x279434164CA30589,
401 0xA9B6706FB8DFB2E3, 0xEB46918411358470,
402 0x2C57B3B8EB0BDFC5, 0x6EA7525342E1E956,
403 0x72E3DAA0AA188782, 0x30133B4B03F2B111,
404 0xF7021977F9CCEAA4, 0xB5F2F89C5026DC37,
405 0x3BD0BCE5A45A6B5D, 0x79205D0E0DB05DCE,
406 0xBE317F32F78E067B, 0xFCC19ED95E6430E8,
407 0x86B86ED5267CDBD3, 0xC4488F3E8F96ED40,
408 0x0359AD0275A8B6F5, 0x41A94CE9DC428066,
409 0xCF8B0890283E370C, 0x8D7BE97B81D4019F,
410 0x4A6ACB477BEA5A2A, 0x089A2AACD2006CB9,
411 0x14DEA25F3AF9026D, 0x562E43B4931334FE,
412 0x913F6188692D6F4B, 0xD3CF8063C0C759D8,
413 0x5DEDC41A34BBEEB2, 0x1F1D25F19D51D821,
414 0xD80C07CD676F8394, 0x9AFCE626CE85B507
417 #endif /* INT64_IS_BUSTED */