crc32.c 34 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198
  1. /* crc32.c -- compute the CRC-32 of a data stream
  2. * Copyright (C) 1995-2022 Mark Adler
  3. * For conditions of distribution and use, see copyright notice in zlib.h
  4. *
  5. * This interleaved implementation of a CRC makes use of pipelined multiple
  6. * arithmetic-logic units, commonly found in modern CPU cores. It is due to
  7. * Kadatch and Jenkins (2010). See doc/crc-doc.1.0.pdf in this distribution.
  8. */
  9. /* @(#) $Id$ */
  10. /*
  11. Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
  12. protection on the static variables used to control the first-use generation
  13. of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
  14. first call get_crc_table() to initialize the tables before allowing more than
  15. one thread to use crc32().
  16. MAKECRCH can be #defined to write out crc32.h. A main() routine is also
  17. produced, so that this one source file can be compiled to an executable.
  18. */
  19. #ifdef MAKECRCH
  20. # include <stdio.h>
  21. # ifndef DYNAMIC_CRC_TABLE
  22. # define DYNAMIC_CRC_TABLE
  23. # endif /* !DYNAMIC_CRC_TABLE */
  24. #endif /* MAKECRCH */
  25. #include "deflate.h"
  26. #include "cpu_features.h"
  27. #include "zutil.h" /* for Z_U4, Z_U8, z_crc_t, and FAR definitions */
  28. #if defined(CRC32_SIMD_SSE42_PCLMUL) || defined(CRC32_ARMV8_CRC32)
  29. #include "crc32_simd.h"
  30. #endif
  31. /*
  32. A CRC of a message is computed on N braids of words in the message, where
  33. each word consists of W bytes (4 or 8). If N is 3, for example, then three
  34. running sparse CRCs are calculated respectively on each braid, at these
  35. indices in the array of words: 0, 3, 6, ..., 1, 4, 7, ..., and 2, 5, 8, ...
  36. This is done starting at a word boundary, and continues until as many blocks
  37. of N * W bytes as are available have been processed. The results are combined
  38. into a single CRC at the end. For this code, N must be in the range 1..6 and
  39. W must be 4 or 8. The upper limit on N can be increased if desired by adding
  40. more #if blocks, extending the patterns apparent in the code. In addition,
  41. crc32.h would need to be regenerated, if the maximum N value is increased.
  42. N and W are chosen empirically by benchmarking the execution time on a given
  43. processor. The choices for N and W below were based on testing on Intel Kaby
  44. Lake i7, AMD Ryzen 7, ARM Cortex-A57, Sparc64-VII, PowerPC POWER9, and MIPS64
  45. Octeon II processors. The Intel, AMD, and ARM processors were all fastest
  46. with N=5, W=8. The Sparc, PowerPC, and MIPS64 were all fastest at N=5, W=4.
  47. They were all tested with either gcc or clang, all using the -O3 optimization
  48. level. Your mileage may vary.
  49. */
  50. /* Define N */
  51. #ifdef Z_TESTN
  52. # define N Z_TESTN
  53. #else
  54. # define N 5
  55. #endif
  56. #if N < 1 || N > 6
  57. # error N must be in 1..6
  58. #endif
  59. /*
  60. z_crc_t must be at least 32 bits. z_word_t must be at least as long as
  61. z_crc_t. It is assumed here that z_word_t is either 32 bits or 64 bits, and
  62. that bytes are eight bits.
  63. */
  64. /*
  65. Define W and the associated z_word_t type. If W is not defined, then a
  66. braided calculation is not used, and the associated tables and code are not
  67. compiled.
  68. */
  69. #ifdef Z_TESTW
  70. # if Z_TESTW-1 != -1
  71. # define W Z_TESTW
  72. # endif
  73. #else
  74. # ifdef MAKECRCH
  75. # define W 8 /* required for MAKECRCH */
  76. # else
  77. # if defined(__x86_64__) || defined(__aarch64__)
  78. # define W 8
  79. # else
  80. # define W 4
  81. # endif
  82. # endif
  83. #endif
  84. #ifdef W
  85. # if W == 8 && defined(Z_U8)
  86. typedef Z_U8 z_word_t;
  87. # elif defined(Z_U4)
  88. # undef W
  89. # define W 4
  90. typedef Z_U4 z_word_t;
  91. # else
  92. # undef W
  93. # endif
  94. #endif
  95. /* Local functions. */
  96. local z_crc_t multmodp OF((z_crc_t a, z_crc_t b));
  97. local z_crc_t x2nmodp OF((z_off64_t n, unsigned k));
  98. /* If available, use the ARM processor CRC32 instruction. */
  99. #if defined(__aarch64__) && defined(__ARM_FEATURE_CRC32) && W == 8 \
  100. && defined(USE_CANONICAL_ARMV8_CRC32)
  101. # define ARMCRC32_CANONICAL_ZLIB
  102. #endif
  103. #if defined(W) && (!defined(ARMCRC32_CANONICAL_ZLIB) || defined(DYNAMIC_CRC_TABLE))
  104. /*
  105. Swap the bytes in a z_word_t to convert between little and big endian. Any
  106. self-respecting compiler will optimize this to a single machine byte-swap
  107. instruction, if one is available. This assumes that word_t is either 32 bits
  108. or 64 bits.
  109. */
  110. local z_word_t byte_swap(word)
  111. z_word_t word;
  112. {
  113. # if W == 8
  114. return
  115. (word & 0xff00000000000000) >> 56 |
  116. (word & 0xff000000000000) >> 40 |
  117. (word & 0xff0000000000) >> 24 |
  118. (word & 0xff00000000) >> 8 |
  119. (word & 0xff000000) << 8 |
  120. (word & 0xff0000) << 24 |
  121. (word & 0xff00) << 40 |
  122. (word & 0xff) << 56;
  123. # else /* W == 4 */
  124. return
  125. (word & 0xff000000) >> 24 |
  126. (word & 0xff0000) >> 8 |
  127. (word & 0xff00) << 8 |
  128. (word & 0xff) << 24;
  129. # endif
  130. }
  131. #endif
  132. /* CRC polynomial. */
  133. #define POLY 0xedb88320 /* p(x) reflected, with x^32 implied */
  134. #ifdef DYNAMIC_CRC_TABLE
  135. local z_crc_t FAR crc_table[256];
  136. local z_crc_t FAR x2n_table[32];
  137. local void make_crc_table OF((void));
  138. #ifdef W
  139. local z_word_t FAR crc_big_table[256];
  140. local z_crc_t FAR crc_braid_table[W][256];
  141. local z_word_t FAR crc_braid_big_table[W][256];
  142. local void braid OF((z_crc_t [][256], z_word_t [][256], int, int));
  143. #endif
  144. #ifdef MAKECRCH
  145. local void write_table OF((FILE *, const z_crc_t FAR *, int));
  146. local void write_table32hi OF((FILE *, const z_word_t FAR *, int));
  147. local void write_table64 OF((FILE *, const z_word_t FAR *, int));
  148. #endif /* MAKECRCH */
  149. /*
  150. Define a once() function depending on the availability of atomics. If this is
  151. compiled with DYNAMIC_CRC_TABLE defined, and if CRCs will be computed in
  152. multiple threads, and if atomics are not available, then get_crc_table() must
  153. be called to initialize the tables and must return before any threads are
  154. allowed to compute or combine CRCs.
  155. */
  156. /* Definition of once functionality. */
  157. typedef struct once_s once_t;
  158. local void once OF((once_t *, void (*)(void)));
  159. /* Check for the availability of atomics. */
  160. #if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \
  161. !defined(__STDC_NO_ATOMICS__)
  162. #include <stdatomic.h>
  163. /* Structure for once(), which must be initialized with ONCE_INIT. */
  164. struct once_s {
  165. atomic_flag begun;
  166. atomic_int done;
  167. };
  168. #define ONCE_INIT {ATOMIC_FLAG_INIT, 0}
  169. /*
  170. Run the provided init() function exactly once, even if multiple threads
  171. invoke once() at the same time. The state must be a once_t initialized with
  172. ONCE_INIT.
  173. */
  174. local void once(state, init)
  175. once_t *state;
  176. void (*init)(void);
  177. {
  178. if (!atomic_load(&state->done)) {
  179. if (atomic_flag_test_and_set(&state->begun))
  180. while (!atomic_load(&state->done))
  181. ;
  182. else {
  183. init();
  184. atomic_store(&state->done, 1);
  185. }
  186. }
  187. }
  188. #else /* no atomics */
  189. /* Structure for once(), which must be initialized with ONCE_INIT. */
  190. struct once_s {
  191. volatile int begun;
  192. volatile int done;
  193. };
  194. #define ONCE_INIT {0, 0}
  195. /* Test and set. Alas, not atomic, but tries to minimize the period of
  196. vulnerability. */
  197. local int test_and_set OF((int volatile *));
  198. local int test_and_set(flag)
  199. int volatile *flag;
  200. {
  201. int was;
  202. was = *flag;
  203. *flag = 1;
  204. return was;
  205. }
  206. /* Run the provided init() function once. This is not thread-safe. */
  207. local void once(state, init)
  208. once_t *state;
  209. void (*init)(void);
  210. {
  211. if (!state->done) {
  212. if (test_and_set(&state->begun))
  213. while (!state->done)
  214. ;
  215. else {
  216. init();
  217. state->done = 1;
  218. }
  219. }
  220. }
  221. #endif
  222. /* State for once(). */
  223. local once_t made = ONCE_INIT;
  224. /*
  225. Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
  226. 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.
  227. Polynomials over GF(2) are represented in binary, one bit per coefficient,
  228. with the lowest powers in the most significant bit. Then adding polynomials
  229. is just exclusive-or, and multiplying a polynomial by x is a right shift by
  230. one. If we call the above polynomial p, and represent a byte as the
  231. polynomial q, also with the lowest power in the most significant bit (so the
  232. byte 0xb1 is the polynomial x^7+x^3+x^2+1), then the CRC is (q*x^32) mod p,
  233. where a mod b means the remainder after dividing a by b.
  234. This calculation is done using the shift-register method of multiplying and
  235. taking the remainder. The register is initialized to zero, and for each
  236. incoming bit, x^32 is added mod p to the register if the bit is a one (where
  237. x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by x
  238. (which is shifting right by one and adding x^32 mod p if the bit shifted out
  239. is a one). We start with the highest power (least significant bit) of q and
  240. repeat for all eight bits of q.
  241. The table is simply the CRC of all possible eight bit values. This is all the
  242. information needed to generate CRCs on data a byte at a time for all
  243. combinations of CRC register values and incoming bytes.
  244. */
  245. local void make_crc_table()
  246. {
  247. unsigned i, j, n;
  248. z_crc_t p;
  249. /* initialize the CRC of bytes tables */
  250. for (i = 0; i < 256; i++) {
  251. p = i;
  252. for (j = 0; j < 8; j++)
  253. p = p & 1 ? (p >> 1) ^ POLY : p >> 1;
  254. crc_table[i] = p;
  255. #ifdef W
  256. crc_big_table[i] = byte_swap(p);
  257. #endif
  258. }
  259. /* initialize the x^2^n mod p(x) table */
  260. p = (z_crc_t)1 << 30; /* x^1 */
  261. x2n_table[0] = p;
  262. for (n = 1; n < 32; n++)
  263. x2n_table[n] = p = multmodp(p, p);
  264. #ifdef W
  265. /* initialize the braiding tables -- needs x2n_table[] */
  266. braid(crc_braid_table, crc_braid_big_table, N, W);
  267. #endif
  268. #ifdef MAKECRCH
  269. {
  270. /*
  271. The crc32.h header file contains tables for both 32-bit and 64-bit
  272. z_word_t's, and so requires a 64-bit type be available. In that case,
  273. z_word_t must be defined to be 64-bits. This code then also generates
  274. and writes out the tables for the case that z_word_t is 32 bits.
  275. */
  276. #if !defined(W) || W != 8
  277. # error Need a 64-bit integer type in order to generate crc32.h.
  278. #endif
  279. FILE *out;
  280. int k, n;
  281. z_crc_t ltl[8][256];
  282. z_word_t big[8][256];
  283. out = fopen("crc32.h", "w");
  284. if (out == NULL) return;
  285. /* write out little-endian CRC table to crc32.h */
  286. fprintf(out,
  287. "/* crc32.h -- tables for rapid CRC calculation\n"
  288. " * Generated automatically by crc32.c\n */\n"
  289. "\n"
  290. "local const z_crc_t FAR crc_table[] = {\n"
  291. " ");
  292. write_table(out, crc_table, 256);
  293. fprintf(out,
  294. "};\n");
  295. /* write out big-endian CRC table for 64-bit z_word_t to crc32.h */
  296. fprintf(out,
  297. "\n"
  298. "#ifdef W\n"
  299. "\n"
  300. "#if W == 8\n"
  301. "\n"
  302. "local const z_word_t FAR crc_big_table[] = {\n"
  303. " ");
  304. write_table64(out, crc_big_table, 256);
  305. fprintf(out,
  306. "};\n");
  307. /* write out big-endian CRC table for 32-bit z_word_t to crc32.h */
  308. fprintf(out,
  309. "\n"
  310. "#else /* W == 4 */\n"
  311. "\n"
  312. "local const z_word_t FAR crc_big_table[] = {\n"
  313. " ");
  314. write_table32hi(out, crc_big_table, 256);
  315. fprintf(out,
  316. "};\n"
  317. "\n"
  318. "#endif\n");
  319. /* write out braid tables for each value of N */
  320. for (n = 1; n <= 6; n++) {
  321. fprintf(out,
  322. "\n"
  323. "#if N == %d\n", n);
  324. /* compute braid tables for this N and 64-bit word_t */
  325. braid(ltl, big, n, 8);
  326. /* write out braid tables for 64-bit z_word_t to crc32.h */
  327. fprintf(out,
  328. "\n"
  329. "#if W == 8\n"
  330. "\n"
  331. "local const z_crc_t FAR crc_braid_table[][256] = {\n");
  332. for (k = 0; k < 8; k++) {
  333. fprintf(out, " {");
  334. write_table(out, ltl[k], 256);
  335. fprintf(out, "}%s", k < 7 ? ",\n" : "");
  336. }
  337. fprintf(out,
  338. "};\n"
  339. "\n"
  340. "local const z_word_t FAR crc_braid_big_table[][256] = {\n");
  341. for (k = 0; k < 8; k++) {
  342. fprintf(out, " {");
  343. write_table64(out, big[k], 256);
  344. fprintf(out, "}%s", k < 7 ? ",\n" : "");
  345. }
  346. fprintf(out,
  347. "};\n");
  348. /* compute braid tables for this N and 32-bit word_t */
  349. braid(ltl, big, n, 4);
  350. /* write out braid tables for 32-bit z_word_t to crc32.h */
  351. fprintf(out,
  352. "\n"
  353. "#else /* W == 4 */\n"
  354. "\n"
  355. "local const z_crc_t FAR crc_braid_table[][256] = {\n");
  356. for (k = 0; k < 4; k++) {
  357. fprintf(out, " {");
  358. write_table(out, ltl[k], 256);
  359. fprintf(out, "}%s", k < 3 ? ",\n" : "");
  360. }
  361. fprintf(out,
  362. "};\n"
  363. "\n"
  364. "local const z_word_t FAR crc_braid_big_table[][256] = {\n");
  365. for (k = 0; k < 4; k++) {
  366. fprintf(out, " {");
  367. write_table32hi(out, big[k], 256);
  368. fprintf(out, "}%s", k < 3 ? ",\n" : "");
  369. }
  370. fprintf(out,
  371. "};\n"
  372. "\n"
  373. "#endif\n"
  374. "\n"
  375. "#endif\n");
  376. }
  377. fprintf(out,
  378. "\n"
  379. "#endif\n");
  380. /* write out zeros operator table to crc32.h */
  381. fprintf(out,
  382. "\n"
  383. "local const z_crc_t FAR x2n_table[] = {\n"
  384. " ");
  385. write_table(out, x2n_table, 32);
  386. fprintf(out,
  387. "};\n");
  388. fclose(out);
  389. }
  390. #endif /* MAKECRCH */
  391. }
  392. #ifdef MAKECRCH
  393. /*
  394. Write the 32-bit values in table[0..k-1] to out, five per line in
  395. hexadecimal separated by commas.
  396. */
  397. local void write_table(out, table, k)
  398. FILE *out;
  399. const z_crc_t FAR *table;
  400. int k;
  401. {
  402. int n;
  403. for (n = 0; n < k; n++)
  404. fprintf(out, "%s0x%08lx%s", n == 0 || n % 5 ? "" : " ",
  405. (unsigned long)(table[n]),
  406. n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", "));
  407. }
  408. /*
  409. Write the high 32-bits of each value in table[0..k-1] to out, five per line
  410. in hexadecimal separated by commas.
  411. */
  412. local void write_table32hi(out, table, k)
  413. FILE *out;
  414. const z_word_t FAR *table;
  415. int k;
  416. {
  417. int n;
  418. for (n = 0; n < k; n++)
  419. fprintf(out, "%s0x%08lx%s", n == 0 || n % 5 ? "" : " ",
  420. (unsigned long)(table[n] >> 32),
  421. n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", "));
  422. }
  423. /*
  424. Write the 64-bit values in table[0..k-1] to out, three per line in
  425. hexadecimal separated by commas. This assumes that if there is a 64-bit
  426. type, then there is also a long long integer type, and it is at least 64
  427. bits. If not, then the type cast and format string can be adjusted
  428. accordingly.
  429. */
  430. local void write_table64(out, table, k)
  431. FILE *out;
  432. const z_word_t FAR *table;
  433. int k;
  434. {
  435. int n;
  436. for (n = 0; n < k; n++)
  437. fprintf(out, "%s0x%016llx%s", n == 0 || n % 3 ? "" : " ",
  438. (unsigned long long)(table[n]),
  439. n == k - 1 ? "" : (n % 3 == 2 ? ",\n" : ", "));
  440. }
  441. /* Actually do the deed. */
  442. int main()
  443. {
  444. make_crc_table();
  445. return 0;
  446. }
  447. #endif /* MAKECRCH */
  448. #ifdef W
  449. /*
  450. Generate the little and big-endian braid tables for the given n and z_word_t
  451. size w. Each array must have room for w blocks of 256 elements.
  452. */
  453. local void braid(ltl, big, n, w)
  454. z_crc_t ltl[][256];
  455. z_word_t big[][256];
  456. int n;
  457. int w;
  458. {
  459. int k;
  460. z_crc_t i, p, q;
  461. for (k = 0; k < w; k++) {
  462. p = x2nmodp((n * w + 3 - k) << 3, 0);
  463. ltl[k][0] = 0;
  464. big[w - 1 - k][0] = 0;
  465. for (i = 1; i < 256; i++) {
  466. ltl[k][i] = q = multmodp(i << 24, p);
  467. big[w - 1 - k][i] = byte_swap(q);
  468. }
  469. }
  470. }
  471. #endif
  472. #else /* !DYNAMIC_CRC_TABLE */
  473. /* ========================================================================
  474. * Tables for byte-wise and braided CRC-32 calculations, and a table of powers
  475. * of x for combining CRC-32s, all made by make_crc_table().
  476. */
  477. #include "crc32.h"
  478. #endif /* DYNAMIC_CRC_TABLE */
  479. /* ========================================================================
  480. * Routines used for CRC calculation. Some are also required for the table
  481. * generation above.
  482. */
  483. /*
  484. Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC polynomial,
  485. reflected. For speed, this requires that a not be zero.
  486. */
  487. local z_crc_t multmodp(a, b)
  488. z_crc_t a;
  489. z_crc_t b;
  490. {
  491. z_crc_t m, p;
  492. m = (z_crc_t)1 << 31;
  493. p = 0;
  494. for (;;) {
  495. if (a & m) {
  496. p ^= b;
  497. if ((a & (m - 1)) == 0)
  498. break;
  499. }
  500. m >>= 1;
  501. b = b & 1 ? (b >> 1) ^ POLY : b >> 1;
  502. }
  503. return p;
  504. }
  505. /*
  506. Return x^(n * 2^k) modulo p(x). Requires that x2n_table[] has been
  507. initialized.
  508. */
  509. local z_crc_t x2nmodp(n, k)
  510. z_off64_t n;
  511. unsigned k;
  512. {
  513. z_crc_t p;
  514. p = (z_crc_t)1 << 31; /* x^0 == 1 */
  515. while (n) {
  516. if (n & 1)
  517. p = multmodp(x2n_table[k & 31], p);
  518. n >>= 1;
  519. k++;
  520. }
  521. return p;
  522. }
  523. /* =========================================================================
  524. * This function can be used by asm versions of crc32(), and to force the
  525. * generation of the CRC tables in a threaded application.
  526. */
  527. const z_crc_t FAR * ZEXPORT get_crc_table()
  528. {
  529. #ifdef DYNAMIC_CRC_TABLE
  530. once(&made, make_crc_table);
  531. #endif /* DYNAMIC_CRC_TABLE */
  532. return (const z_crc_t FAR *)crc_table;
  533. }
  534. /* =========================================================================
  535. * Use ARM machine instructions if available. This will compute the CRC about
  536. * ten times faster than the braided calculation. This code does not check for
  537. * the presence of the CRC instruction at run time. __ARM_FEATURE_CRC32 will
  538. * only be defined if the compilation specifies an ARM processor architecture
  539. * that has the instructions. For example, compiling with -march=armv8.1-a or
  540. * -march=armv8-a+crc, or -march=native if the compile machine has the crc32
  541. * instructions.
  542. */
  543. #if ARMCRC32_CANONICAL_ZLIB
  544. /*
  545. Constants empirically determined to maximize speed. These values are from
  546. measurements on a Cortex-A57. Your mileage may vary.
  547. */
  548. #define Z_BATCH 3990 /* number of words in a batch */
  549. #define Z_BATCH_ZEROS 0xa10d3d0c /* computed from Z_BATCH = 3990 */
  550. #define Z_BATCH_MIN 800 /* fewest words in a final batch */
  551. unsigned long ZEXPORT crc32_z(crc, buf, len)
  552. unsigned long crc;
  553. const unsigned char FAR *buf;
  554. z_size_t len;
  555. {
  556. z_crc_t val;
  557. z_word_t crc1, crc2;
  558. const z_word_t *word;
  559. z_word_t val0, val1, val2;
  560. z_size_t last, last2, i;
  561. z_size_t num;
  562. /* Return initial CRC, if requested. */
  563. if (buf == Z_NULL) return 0;
  564. #ifdef DYNAMIC_CRC_TABLE
  565. once(&made, make_crc_table);
  566. #endif /* DYNAMIC_CRC_TABLE */
  567. /* Pre-condition the CRC */
  568. crc = (~crc) & 0xffffffff;
  569. /* Compute the CRC up to a word boundary. */
  570. while (len && ((z_size_t)buf & 7) != 0) {
  571. len--;
  572. val = *buf++;
  573. __asm__ volatile("crc32b %w0, %w0, %w1" : "+r"(crc) : "r"(val));
  574. }
  575. /* Prepare to compute the CRC on full 64-bit words word[0..num-1]. */
  576. word = (z_word_t const *)buf;
  577. num = len >> 3;
  578. len &= 7;
  579. /* Do three interleaved CRCs to realize the throughput of one crc32x
  580. instruction per cycle. Each CRC is calcuated on Z_BATCH words. The three
  581. CRCs are combined into a single CRC after each set of batches. */
  582. while (num >= 3 * Z_BATCH) {
  583. crc1 = 0;
  584. crc2 = 0;
  585. for (i = 0; i < Z_BATCH; i++) {
  586. val0 = word[i];
  587. val1 = word[i + Z_BATCH];
  588. val2 = word[i + 2 * Z_BATCH];
  589. __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0));
  590. __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc1) : "r"(val1));
  591. __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc2) : "r"(val2));
  592. }
  593. word += 3 * Z_BATCH;
  594. num -= 3 * Z_BATCH;
  595. crc = multmodp(Z_BATCH_ZEROS, crc) ^ crc1;
  596. crc = multmodp(Z_BATCH_ZEROS, crc) ^ crc2;
  597. }
  598. /* Do one last smaller batch with the remaining words, if there are enough
  599. to pay for the combination of CRCs. */
  600. last = num / 3;
  601. if (last >= Z_BATCH_MIN) {
  602. last2 = last << 1;
  603. crc1 = 0;
  604. crc2 = 0;
  605. for (i = 0; i < last; i++) {
  606. val0 = word[i];
  607. val1 = word[i + last];
  608. val2 = word[i + last2];
  609. __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0));
  610. __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc1) : "r"(val1));
  611. __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc2) : "r"(val2));
  612. }
  613. word += 3 * last;
  614. num -= 3 * last;
  615. val = x2nmodp(last, 6);
  616. crc = multmodp(val, crc) ^ crc1;
  617. crc = multmodp(val, crc) ^ crc2;
  618. }
  619. /* Compute the CRC on any remaining words. */
  620. for (i = 0; i < num; i++) {
  621. val0 = word[i];
  622. __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0));
  623. }
  624. word += num;
  625. /* Complete the CRC on any remaining bytes. */
  626. buf = (const unsigned char FAR *)word;
  627. while (len) {
  628. len--;
  629. val = *buf++;
  630. __asm__ volatile("crc32b %w0, %w0, %w1" : "+r"(crc) : "r"(val));
  631. }
  632. /* Return the CRC, post-conditioned. */
  633. return crc ^ 0xffffffff;
  634. }
  635. #else
  636. #ifdef W
  637. /*
  638. Return the CRC of the W bytes in the word_t data, taking the
  639. least-significant byte of the word as the first byte of data, without any pre
  640. or post conditioning. This is used to combine the CRCs of each braid.
  641. */
  642. local z_crc_t crc_word(data)
  643. z_word_t data;
  644. {
  645. int k;
  646. for (k = 0; k < W; k++)
  647. data = (data >> 8) ^ crc_table[data & 0xff];
  648. return (z_crc_t)data;
  649. }
  650. local z_word_t crc_word_big(data)
  651. z_word_t data;
  652. {
  653. int k;
  654. for (k = 0; k < W; k++)
  655. data = (data << 8) ^
  656. crc_big_table[(data >> ((W - 1) << 3)) & 0xff];
  657. return data;
  658. }
  659. #endif
  660. /* ========================================================================= */
  661. unsigned long ZEXPORT crc32_z(crc, buf, len)
  662. unsigned long crc;
  663. const unsigned char FAR *buf;
  664. z_size_t len;
  665. {
  666. /*
  667. * zlib convention is to call crc32(0, NULL, 0); before making
  668. * calls to crc32(). So this is a good, early (and infrequent)
  669. * place to cache CPU features if needed for those later, more
  670. * interesting crc32() calls.
  671. */
  672. #if defined(CRC32_SIMD_SSE42_PCLMUL)
  673. /*
  674. * Use x86 sse4.2+pclmul SIMD to compute the crc32. Since this
  675. * routine can be freely used, check CPU features here.
  676. */
  677. if (buf == Z_NULL) {
  678. if (!len) /* Assume user is calling crc32(0, NULL, 0); */
  679. cpu_check_features();
  680. return 0UL;
  681. }
  682. if (x86_cpu_enable_simd && len >= Z_CRC32_SSE42_MINIMUM_LENGTH) {
  683. /* crc32 16-byte chunks */
  684. z_size_t chunk_size = len & ~Z_CRC32_SSE42_CHUNKSIZE_MASK;
  685. crc = ~crc32_sse42_simd_(buf, chunk_size, ~(uint32_t)crc);
  686. /* check remaining data */
  687. len -= chunk_size;
  688. if (!len)
  689. return crc;
  690. /* Fall into the default crc32 for the remaining data. */
  691. buf += chunk_size;
  692. }
  693. #else
  694. if (buf == Z_NULL) {
  695. return 0UL;
  696. }
  697. #endif /* CRC32_SIMD_SSE42_PCLMUL */
  698. #ifdef DYNAMIC_CRC_TABLE
  699. once(&made, make_crc_table);
  700. #endif /* DYNAMIC_CRC_TABLE */
  701. /* Pre-condition the CRC */
  702. crc = (~crc) & 0xffffffff;
  703. #ifdef W
  704. /* If provided enough bytes, do a braided CRC calculation. */
  705. if (len >= N * W + W - 1) {
  706. z_size_t blks;
  707. z_word_t const *words;
  708. unsigned endian;
  709. int k;
  710. /* Compute the CRC up to a z_word_t boundary. */
  711. while (len && ((z_size_t)buf & (W - 1)) != 0) {
  712. len--;
  713. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  714. }
  715. /* Compute the CRC on as many N z_word_t blocks as are available. */
  716. blks = len / (N * W);
  717. len -= blks * N * W;
  718. words = (z_word_t const *)buf;
  719. /* Do endian check at execution time instead of compile time, since ARM
  720. processors can change the endianess at execution time. If the
  721. compiler knows what the endianess will be, it can optimize out the
  722. check and the unused branch. */
  723. endian = 1;
  724. if (*(unsigned char *)&endian) {
  725. /* Little endian. */
  726. z_crc_t crc0;
  727. z_word_t word0;
  728. #if N > 1
  729. z_crc_t crc1;
  730. z_word_t word1;
  731. #if N > 2
  732. z_crc_t crc2;
  733. z_word_t word2;
  734. #if N > 3
  735. z_crc_t crc3;
  736. z_word_t word3;
  737. #if N > 4
  738. z_crc_t crc4;
  739. z_word_t word4;
  740. #if N > 5
  741. z_crc_t crc5;
  742. z_word_t word5;
  743. #endif
  744. #endif
  745. #endif
  746. #endif
  747. #endif
  748. /* Initialize the CRC for each braid. */
  749. crc0 = crc;
  750. #if N > 1
  751. crc1 = 0;
  752. #if N > 2
  753. crc2 = 0;
  754. #if N > 3
  755. crc3 = 0;
  756. #if N > 4
  757. crc4 = 0;
  758. #if N > 5
  759. crc5 = 0;
  760. #endif
  761. #endif
  762. #endif
  763. #endif
  764. #endif
  765. /*
  766. Process the first blks-1 blocks, computing the CRCs on each braid
  767. independently.
  768. */
  769. while (--blks) {
  770. /* Load the word for each braid into registers. */
  771. word0 = crc0 ^ words[0];
  772. #if N > 1
  773. word1 = crc1 ^ words[1];
  774. #if N > 2
  775. word2 = crc2 ^ words[2];
  776. #if N > 3
  777. word3 = crc3 ^ words[3];
  778. #if N > 4
  779. word4 = crc4 ^ words[4];
  780. #if N > 5
  781. word5 = crc5 ^ words[5];
  782. #endif
  783. #endif
  784. #endif
  785. #endif
  786. #endif
  787. words += N;
  788. /* Compute and update the CRC for each word. The loop should
  789. get unrolled. */
  790. crc0 = crc_braid_table[0][word0 & 0xff];
  791. #if N > 1
  792. crc1 = crc_braid_table[0][word1 & 0xff];
  793. #if N > 2
  794. crc2 = crc_braid_table[0][word2 & 0xff];
  795. #if N > 3
  796. crc3 = crc_braid_table[0][word3 & 0xff];
  797. #if N > 4
  798. crc4 = crc_braid_table[0][word4 & 0xff];
  799. #if N > 5
  800. crc5 = crc_braid_table[0][word5 & 0xff];
  801. #endif
  802. #endif
  803. #endif
  804. #endif
  805. #endif
  806. for (k = 1; k < W; k++) {
  807. crc0 ^= crc_braid_table[k][(word0 >> (k << 3)) & 0xff];
  808. #if N > 1
  809. crc1 ^= crc_braid_table[k][(word1 >> (k << 3)) & 0xff];
  810. #if N > 2
  811. crc2 ^= crc_braid_table[k][(word2 >> (k << 3)) & 0xff];
  812. #if N > 3
  813. crc3 ^= crc_braid_table[k][(word3 >> (k << 3)) & 0xff];
  814. #if N > 4
  815. crc4 ^= crc_braid_table[k][(word4 >> (k << 3)) & 0xff];
  816. #if N > 5
  817. crc5 ^= crc_braid_table[k][(word5 >> (k << 3)) & 0xff];
  818. #endif
  819. #endif
  820. #endif
  821. #endif
  822. #endif
  823. }
  824. }
  825. /*
  826. Process the last block, combining the CRCs of the N braids at the
  827. same time.
  828. */
  829. crc = crc_word(crc0 ^ words[0]);
  830. #if N > 1
  831. crc = crc_word(crc1 ^ words[1] ^ crc);
  832. #if N > 2
  833. crc = crc_word(crc2 ^ words[2] ^ crc);
  834. #if N > 3
  835. crc = crc_word(crc3 ^ words[3] ^ crc);
  836. #if N > 4
  837. crc = crc_word(crc4 ^ words[4] ^ crc);
  838. #if N > 5
  839. crc = crc_word(crc5 ^ words[5] ^ crc);
  840. #endif
  841. #endif
  842. #endif
  843. #endif
  844. #endif
  845. words += N;
  846. }
  847. else {
  848. /* Big endian. */
  849. z_word_t crc0, word0, comb;
  850. #if N > 1
  851. z_word_t crc1, word1;
  852. #if N > 2
  853. z_word_t crc2, word2;
  854. #if N > 3
  855. z_word_t crc3, word3;
  856. #if N > 4
  857. z_word_t crc4, word4;
  858. #if N > 5
  859. z_word_t crc5, word5;
  860. #endif
  861. #endif
  862. #endif
  863. #endif
  864. #endif
  865. /* Initialize the CRC for each braid. */
  866. crc0 = byte_swap(crc);
  867. #if N > 1
  868. crc1 = 0;
  869. #if N > 2
  870. crc2 = 0;
  871. #if N > 3
  872. crc3 = 0;
  873. #if N > 4
  874. crc4 = 0;
  875. #if N > 5
  876. crc5 = 0;
  877. #endif
  878. #endif
  879. #endif
  880. #endif
  881. #endif
  882. /*
  883. Process the first blks-1 blocks, computing the CRCs on each braid
  884. independently.
  885. */
  886. while (--blks) {
  887. /* Load the word for each braid into registers. */
  888. word0 = crc0 ^ words[0];
  889. #if N > 1
  890. word1 = crc1 ^ words[1];
  891. #if N > 2
  892. word2 = crc2 ^ words[2];
  893. #if N > 3
  894. word3 = crc3 ^ words[3];
  895. #if N > 4
  896. word4 = crc4 ^ words[4];
  897. #if N > 5
  898. word5 = crc5 ^ words[5];
  899. #endif
  900. #endif
  901. #endif
  902. #endif
  903. #endif
  904. words += N;
  905. /* Compute and update the CRC for each word. The loop should
  906. get unrolled. */
  907. crc0 = crc_braid_big_table[0][word0 & 0xff];
  908. #if N > 1
  909. crc1 = crc_braid_big_table[0][word1 & 0xff];
  910. #if N > 2
  911. crc2 = crc_braid_big_table[0][word2 & 0xff];
  912. #if N > 3
  913. crc3 = crc_braid_big_table[0][word3 & 0xff];
  914. #if N > 4
  915. crc4 = crc_braid_big_table[0][word4 & 0xff];
  916. #if N > 5
  917. crc5 = crc_braid_big_table[0][word5 & 0xff];
  918. #endif
  919. #endif
  920. #endif
  921. #endif
  922. #endif
  923. for (k = 1; k < W; k++) {
  924. crc0 ^= crc_braid_big_table[k][(word0 >> (k << 3)) & 0xff];
  925. #if N > 1
  926. crc1 ^= crc_braid_big_table[k][(word1 >> (k << 3)) & 0xff];
  927. #if N > 2
  928. crc2 ^= crc_braid_big_table[k][(word2 >> (k << 3)) & 0xff];
  929. #if N > 3
  930. crc3 ^= crc_braid_big_table[k][(word3 >> (k << 3)) & 0xff];
  931. #if N > 4
  932. crc4 ^= crc_braid_big_table[k][(word4 >> (k << 3)) & 0xff];
  933. #if N > 5
  934. crc5 ^= crc_braid_big_table[k][(word5 >> (k << 3)) & 0xff];
  935. #endif
  936. #endif
  937. #endif
  938. #endif
  939. #endif
  940. }
  941. }
  942. /*
  943. Process the last block, combining the CRCs of the N braids at the
  944. same time.
  945. */
  946. comb = crc_word_big(crc0 ^ words[0]);
  947. #if N > 1
  948. comb = crc_word_big(crc1 ^ words[1] ^ comb);
  949. #if N > 2
  950. comb = crc_word_big(crc2 ^ words[2] ^ comb);
  951. #if N > 3
  952. comb = crc_word_big(crc3 ^ words[3] ^ comb);
  953. #if N > 4
  954. comb = crc_word_big(crc4 ^ words[4] ^ comb);
  955. #if N > 5
  956. comb = crc_word_big(crc5 ^ words[5] ^ comb);
  957. #endif
  958. #endif
  959. #endif
  960. #endif
  961. #endif
  962. words += N;
  963. crc = byte_swap(comb);
  964. }
  965. /*
  966. Update the pointer to the remaining bytes to process.
  967. */
  968. buf = (unsigned char const *)words;
  969. }
  970. #endif /* W */
  971. /* Complete the computation of the CRC on any remaining bytes. */
  972. while (len >= 8) {
  973. len -= 8;
  974. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  975. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  976. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  977. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  978. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  979. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  980. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  981. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  982. }
  983. while (len) {
  984. len--;
  985. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  986. }
  987. /* Return the CRC, post-conditioned. */
  988. return crc ^ 0xffffffff;
  989. }
  990. #endif
  991. /* ========================================================================= */
  992. unsigned long ZEXPORT crc32(crc, buf, len)
  993. unsigned long crc;
  994. const unsigned char FAR *buf;
  995. uInt len;
  996. {
  997. #if defined(CRC32_ARMV8_CRC32)
  998. /* We got to verify ARM CPU features, so exploit the common usage pattern
  999. * of calling this function with Z_NULL for an initial valid crc value.
  1000. * This allows to cache the result of the feature check and avoid extraneous
  1001. * function calls.
  1002. * TODO: try to move this to crc32_z if we don't loose performance on ARM.
  1003. */
  1004. if (buf == Z_NULL) {
  1005. if (!len) /* Assume user is calling crc32(0, NULL, 0); */
  1006. cpu_check_features();
  1007. return 0UL;
  1008. }
  1009. if (arm_cpu_enable_crc32)
  1010. return armv8_crc32_little(crc, buf, len);
  1011. #endif
  1012. return crc32_z(crc, buf, len);
  1013. }
  1014. /* ========================================================================= */
  1015. uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
  1016. uLong crc1;
  1017. uLong crc2;
  1018. z_off64_t len2;
  1019. {
  1020. #ifdef DYNAMIC_CRC_TABLE
  1021. once(&made, make_crc_table);
  1022. #endif /* DYNAMIC_CRC_TABLE */
  1023. return multmodp(x2nmodp(len2, 3), crc1) ^ (crc2 & 0xffffffff);
  1024. }
  1025. /* ========================================================================= */
  1026. uLong ZEXPORT crc32_combine(crc1, crc2, len2)
  1027. uLong crc1;
  1028. uLong crc2;
  1029. z_off_t len2;
  1030. {
  1031. return crc32_combine64(crc1, crc2, len2);
  1032. }
  1033. /* ========================================================================= */
  1034. uLong ZEXPORT crc32_combine_gen64(len2)
  1035. z_off64_t len2;
  1036. {
  1037. #ifdef DYNAMIC_CRC_TABLE
  1038. once(&made, make_crc_table);
  1039. #endif /* DYNAMIC_CRC_TABLE */
  1040. return x2nmodp(len2, 3);
  1041. }
  1042. /* ========================================================================= */
  1043. uLong ZEXPORT crc32_combine_gen(len2)
  1044. z_off_t len2;
  1045. {
  1046. return crc32_combine_gen64(len2);
  1047. }
  1048. /* ========================================================================= */
  1049. uLong ZEXPORT crc32_combine_op(crc1, crc2, op)
  1050. uLong crc1;
  1051. uLong crc2;
  1052. uLong op;
  1053. {
  1054. return multmodp(op, crc1) ^ (crc2 & 0xffffffff);
  1055. }
  1056. ZLIB_INTERNAL void crc_reset(deflate_state *const s)
  1057. {
  1058. #ifdef CRC32_SIMD_SSE42_PCLMUL
  1059. if (x86_cpu_enable_simd) {
  1060. crc_fold_init(s);
  1061. return;
  1062. }
  1063. #endif
  1064. s->strm->adler = crc32(0L, Z_NULL, 0);
  1065. }
  1066. ZLIB_INTERNAL void crc_finalize(deflate_state *const s)
  1067. {
  1068. #ifdef CRC32_SIMD_SSE42_PCLMUL
  1069. if (x86_cpu_enable_simd)
  1070. s->strm->adler = crc_fold_512to32(s);
  1071. #endif
  1072. }
  1073. ZLIB_INTERNAL void copy_with_crc(z_streamp strm, Bytef *dst, long size)
  1074. {
  1075. #ifdef CRC32_SIMD_SSE42_PCLMUL
  1076. if (x86_cpu_enable_simd) {
  1077. crc_fold_copy(strm->state, dst, strm->next_in, size);
  1078. return;
  1079. }
  1080. #endif
  1081. zmemcpy(dst, strm->next_in, size);
  1082. strm->adler = crc32(strm->adler, dst, size);
  1083. }