crc32c.c

/* crc32c.c -- compute CRC-32C using the Intel crc32 instruction
 * Copyright (C) 2013, 2021 Mark Adler
 * Version 1.2  5 Jun 2021  Mark Adler
 */

/*
  This software is provided 'as-is', without any express or implied
  warranty.  In no event will the author be held liable for any damages
  arising from the use of this software.

  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.
  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.

  Mark Adler
  madler@alumni.caltech.edu
 */

/* Modified version of Mark Adler's original CRC-32c implementation.
 * For the original, see: https://stackoverflow.com/a/17646775
 *
 * - SSE 4.2 hardware implementation simplified to not require large tables
 *   (at a performance cost).
 * - Added an ARMv8-a hardware implementation.
 * - Algorithm is revised to use a 32-bit variant fallback to be kinder to
 *   older hardware. The fallback also supports big endian now.
 * - Style and type changes to better match libxmp.
 */

#include "common.h"

#if defined(__i386) || defined(__i386__) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_AMD64)
#define IS_X86
#endif

#if defined(__aarch64__) || (defined(_M_ARM) && _M_ARM >= 8)
#define IS_ARM64_CRC32C
#include <arm_acle.h>
#endif


#ifndef CRC32_GENERATE

// Table for a 32-bits-at-a-time software CRC-32C calculation. This table
// has built into it the pre and post bit inversion of the CRC.
static const uint32 crc32c_table[][256] =
{
	{0x527d5351, 0xa016d052, 0xb34623a6, 0x412da0a5, 0x95e7c44e, 0x678c474d,
	 0x74dcb4b9, 0x86b737ba, 0xd8a40b9e, 0x2acf889d, 0x399f7b69, 0xcbf4f86a,
	 0x1f3e9c81, 0xed551f82, 0xfe05ec76, 0x0c6e6f75, 0x4223943e, 0xb048173d,
	 0xa318e4c9, 0x517367ca, 0x85b90321, 0x77d28022, 0x648273d6, 0x96e9f0d5,
	 0xc8faccf1, 0x3a914ff2, 0x29c1bc06, 0xdbaa3f05, 0x0f605bee, 0xfd0bd8ed,
	 0xee5b2b19, 0x1c30a81a, 0x72c0dd8f, 0x80ab5e8c, 0x93fbad78, 0x61902e7b,
	 0xb55a4a90, 0x4731c993, 0x54613a67, 0xa60ab964, 0xf8198540, 0x0a720643,
	 0x1922f5b7, 0xeb4976b4, 0x3f83125f, 0xcde8915c, 0xdeb862a8, 0x2cd3e1ab,
	 0x629e1ae0, 0x90f599e3, 0x83a56a17, 0x71cee914, 0xa5048dff, 0x576f0efc,
	 0x443ffd08, 0xb6547e0b, 0xe847422f, 0x1a2cc12c, 0x097c32d8, 0xfb17b1db,
	 0x2fddd530, 0xddb65633, 0xcee6a5c7, 0x3c8d26c4, 0x13064eed, 0xe16dcdee,
	 0xf23d3e1a, 0x0056bd19, 0xd49cd9f2, 0x26f75af1, 0x35a7a905, 0xc7cc2a06,
	 0x99df1622, 0x6bb49521, 0x78e466d5, 0x8a8fe5d6, 0x5e45813d, 0xac2e023e,
	 0xbf7ef1ca, 0x4d1572c9, 0x03588982, 0xf1330a81, 0xe263f975, 0x10087a76,
	 0xc4c21e9d, 0x36a99d9e, 0x25f96e6a, 0xd792ed69, 0x8981d14d, 0x7bea524e,
	 0x68baa1ba, 0x9ad122b9, 0x4e1b4652, 0xbc70c551, 0xaf2036a5, 0x5d4bb5a6,
	 0x33bbc033, 0xc1d04330, 0xd280b0c4, 0x20eb33c7, 0xf421572c, 0x064ad42f,
	 0x151a27db, 0xe771a4d8, 0xb96298fc, 0x4b091bff, 0x5859e80b, 0xaa326b08,
	 0x7ef80fe3, 0x8c938ce0, 0x9fc37f14, 0x6da8fc17, 0x23e5075c, 0xd18e845f,
	 0xc2de77ab, 0x30b5f4a8, 0xe47f9043, 0x16141340, 0x0544e0b4, 0xf72f63b7,
	 0xa93c5f93, 0x5b57dc90, 0x48072f64, 0xba6cac67, 0x6ea6c88c, 0x9ccd4b8f,
	 0x8f9db87b, 0x7df63b78, 0xd08b6829, 0x22e0eb2a, 0x31b018de, 0xc3db9bdd,
	 0x1711ff36, 0xe57a7c35, 0xf62a8fc1, 0x04410cc2, 0x5a5230e6, 0xa839b3e5,
	 0xbb694011, 0x4902c312, 0x9dc8a7f9, 0x6fa324fa, 0x7cf3d70e, 0x8e98540d,
	 0xc0d5af46, 0x32be2c45, 0x21eedfb1, 0xd3855cb2, 0x074f3859, 0xf524bb5a,
	 0xe67448ae, 0x141fcbad, 0x4a0cf789, 0xb867748a, 0xab37877e, 0x595c047d,
	 0x8d966096, 0x7ffde395, 0x6cad1061, 0x9ec69362, 0xf036e6f7, 0x025d65f4,
	 0x110d9600, 0xe3661503, 0x37ac71e8, 0xc5c7f2eb, 0xd697011f, 0x24fc821c,
	 0x7aefbe38, 0x88843d3b, 0x9bd4cecf, 0x69bf4dcc, 0xbd752927, 0x4f1eaa24,
	 0x5c4e59d0, 0xae25dad3, 0xe0682198, 0x1203a29b, 0x0153516f, 0xf338d26c,
	 0x27f2b687, 0xd5993584, 0xc6c9c670, 0x34a24573, 0x6ab17957, 0x98dafa54,
	 0x8b8a09a0, 0x79e18aa3, 0xad2bee48, 0x5f406d4b, 0x4c109ebf, 0xbe7b1dbc,
	 0x91f07595, 0x639bf696, 0x70cb0562, 0x82a08661, 0x566ae28a, 0xa4016189,
	 0xb751927d, 0x453a117e, 0x1b292d5a, 0xe942ae59, 0xfa125dad, 0x0879deae,
	 0xdcb3ba45, 0x2ed83946, 0x3d88cab2, 0xcfe349b1, 0x81aeb2fa, 0x73c531f9,
	 0x6095c20d, 0x92fe410e, 0x463425e5, 0xb45fa6e6, 0xa70f5512, 0x5564d611,
	 0x0b77ea35, 0xf91c6936, 0xea4c9ac2, 0x182719c1, 0xcced7d2a, 0x3e86fe29,
	 0x2dd60ddd, 0xdfbd8ede, 0xb14dfb4b, 0x43267848, 0x50768bbc, 0xa21d08bf,
	 0x76d76c54, 0x84bcef57, 0x97ec1ca3, 0x65879fa0, 0x3b94a384, 0xc9ff2087,
	 0xdaafd373, 0x28c45070, 0xfc0e349b, 0x0e65b798, 0x1d35446c, 0xef5ec76f,
	 0xa1133c24, 0x5378bf27, 0x40284cd3, 0xb243cfd0, 0x6689ab3b, 0x94e22838,
	 0x87b2dbcc, 0x75d958cf, 0x2bca64eb, 0xd9a1e7e8, 0xcaf1141c, 0x389a971f,
	 0xec50f3f4, 0x1e3b70f7, 0x0d6b8303, 0xff000000},
	{0xa31c2483, 0xb0bebcf4, 0x8459146d, 0x97fb8c1a, 0xed96455f, 0xfe34dd28,
	 0xcad375b1, 0xd971edc6, 0x3e08e73b, 0x2daa7f4c, 0x194dd7d5, 0x0aef4fa2,
	 0x708286e7, 0x63201e90, 0x57c7b609, 0x44652e7e, 0x9cd9d502, 0x8f7b4d75,
	 0xbb9ce5ec, 0xa83e7d9b, 0xd253b4de, 0xc1f12ca9, 0xf5168430, 0xe6b41c47,
	 0x01cd16ba, 0x126f8ecd, 0x26882654, 0x352abe23, 0x4f477766, 0x5ce5ef11,
	 0x68024788, 0x7ba0dfff, 0xdc97c781, 0xcf355ff6, 0xfbd2f76f, 0xe8706f18,
	 0x921da65d, 0x81bf3e2a, 0xb55896b3, 0xa6fa0ec4, 0x41830439, 0x52219c4e,
	 0x66c634d7, 0x7564aca0, 0x0f0965e5, 0x1cabfd92, 0x284c550b, 0x3beecd7c,
	 0xe3523600, 0xf0f0ae77, 0xc41706ee, 0xd7b59e99, 0xadd857dc, 0xbe7acfab,
	 0x8a9d6732, 0x993fff45, 0x7e46f5b8, 0x6de46dcf, 0x5903c556, 0x4aa15d21,
	 0x30cc9464, 0x236e0c13, 0x1789a48a, 0x042b3cfd, 0x5c0be287, 0x4fa97af0,
	 0x7b4ed269, 0x68ec4a1e, 0x1281835b, 0x01231b2c, 0x35c4b3b5, 0x26662bc2,
	 0xc11f213f, 0xd2bdb948, 0xe65a11d1, 0xf5f889a6, 0x8f9540e3, 0x9c37d894,
	 0xa8d0700d, 0xbb72e87a, 0x63ce1306, 0x706c8b71, 0x448b23e8, 0x5729bb9f,
	 0x2d4472da, 0x3ee6eaad, 0x0a014234, 0x19a3da43, 0xfedad0be, 0xed7848c9,
	 0xd99fe050, 0xca3d7827, 0xb050b162, 0xa3f22915, 0x9715818c, 0x84b719fb,
	 0x23800185, 0x302299f2, 0x04c5316b, 0x1767a91c, 0x6d0a6059, 0x7ea8f82e,
	 0x4a4f50b7, 0x59edc8c0, 0xbe94c23d, 0xad365a4a, 0x99d1f2d3, 0x8a736aa4,
	 0xf01ea3e1, 0xe3bc3b96, 0xd75b930f, 0xc4f90b78, 0x1c45f004, 0x0fe76873,
	 0x3b00c0ea, 0x28a2589d, 0x52cf91d8, 0x416d09af, 0x758aa136, 0x66283941,
	 0x815133bc, 0x92f3abcb, 0xa6140352, 0xb5b69b25, 0xcfdb5260, 0xdc79ca17,
	 0xe89e628e, 0xfb3cfaf9, 0x58dfde7a, 0x4b7d460d, 0x7f9aee94, 0x6c3876e3,
	 0x1655bfa6, 0x05f727d1, 0x31108f48, 0x22b2173f, 0xc5cb1dc2, 0xd66985b5,
	 0xe28e2d2c, 0xf12cb55b, 0x8b417c1e, 0x98e3e469, 0xac044cf0, 0xbfa6d487,
	 0x671a2ffb, 0x74b8b78c, 0x405f1f15, 0x53fd8762, 0x29904e27, 0x3a32d650,
	 0x0ed57ec9, 0x1d77e6be, 0xfa0eec43, 0xe9ac7434, 0xdd4bdcad, 0xcee944da,
	 0xb4848d9f, 0xa72615e8, 0x93c1bd71, 0x80632506, 0x27543d78, 0x34f6a50f,
	 0x00110d96, 0x13b395e1, 0x69de5ca4, 0x7a7cc4d3, 0x4e9b6c4a, 0x5d39f43d,
	 0xba40fec0, 0xa9e266b7, 0x9d05ce2e, 0x8ea75659, 0xf4ca9f1c, 0xe768076b,
	 0xd38faff2, 0xc02d3785, 0x1891ccf9, 0x0b33548e, 0x3fd4fc17, 0x2c766460,
	 0x561bad25, 0x45b93552, 0x715e9dcb, 0x62fc05bc, 0x85850f41, 0x96279736,
	 0xa2c03faf, 0xb162a7d8, 0xcb0f6e9d, 0xd8adf6ea, 0xec4a5e73, 0xffe8c604,
	 0xa7c8187e, 0xb46a8009, 0x808d2890, 0x932fb0e7, 0xe94279a2, 0xfae0e1d5,
	 0xce07494c, 0xdda5d13b, 0x3adcdbc6, 0x297e43b1, 0x1d99eb28, 0x0e3b735f,
	 0x7456ba1a, 0x67f4226d, 0x53138af4, 0x40b11283, 0x980de9ff, 0x8baf7188,
	 0xbf48d911, 0xacea4166, 0xd6878823, 0xc5251054, 0xf1c2b8cd, 0xe26020ba,
	 0x05192a47, 0x16bbb230, 0x225c1aa9, 0x31fe82de, 0x4b934b9b, 0x5831d3ec,
	 0x6cd67b75, 0x7f74e302, 0xd843fb7c, 0xcbe1630b, 0xff06cb92, 0xeca453e5,
	 0x96c99aa0, 0x856b02d7, 0xb18caa4e, 0xa22e3239, 0x455738c4, 0x56f5a0b3,
	 0x6212082a, 0x71b0905d, 0x0bdd5918, 0x187fc16f, 0x2c9869f6, 0x3f3af181,
	 0xe7860afd, 0xf424928a, 0xc0c33a13, 0xd361a264, 0xa90c6b21, 0xbaaef356,
	 0x8e495bcf, 0x9debc3b8, 0x7a92c945, 0x69305132, 0x5dd7f9ab, 0x4e7561dc,
	 0x3418a899, 0x27ba30ee, 0x135d9877, 0x00ff0000},
	{0x9105d4a8, 0x344446d6, 0xde6a86a5, 0x7b2b14db, 0x0fdb70b2, 0xaa9ae2cc,
	 0x40b422bf, 0xe5f5b0c1, 0xa954ea6d, 0x0c157813, 0xe63bb860, 0x437a2a1e,
	 0x378a4e77, 0x92cbdc09, 0x78e51c7a, 0xdda48e04, 0xe1a7a922, 0x44e63b5c,
	 0xaec8fb2f, 0x0b896951, 0x7f790d38, 0xda389f46, 0x30165f35, 0x9557cd4b,
	 0xd9f697e7, 0x7cb70599, 0x9699c5ea, 0x33d85794, 0x472833fd, 0xe269a183,
	 0x084761f0, 0xad06f38e, 0x70412fbc, 0xd500bdc2, 0x3f2e7db1, 0x9a6fefcf,
	 0xee9f8ba6, 0x4bde19d8, 0xa1f0d9ab, 0x04b14bd5, 0x48101179, 0xed518307,
	 0x077f4374, 0xa23ed10a, 0xd6ceb563, 0x738f271d, 0x99a1e76e, 0x3ce07510,
	 0x00e35236, 0xa5a2c048, 0x4f8c003b, 0xeacd9245, 0x9e3df62c, 0x3b7c6452,
	 0xd152a421, 0x7413365f, 0x38b26cf3, 0x9df3fe8d, 0x77dd3efe, 0xd29cac80,
	 0xa66cc8e9, 0x032d5a97, 0xe9039ae4, 0x4c42089a, 0x56605471, 0xf321c60f,
	 0x190f067c, 0xbc4e9402, 0xc8bef06b, 0x6dff6215, 0x87d1a266, 0x22903018,
	 0x6e316ab4, 0xcb70f8ca, 0x215e38b9, 0x841faac7, 0xf0efceae, 0x55ae5cd0,
	 0xbf809ca3, 0x1ac10edd, 0x26c229fb, 0x8383bb85, 0x69ad7bf6, 0xccece988,
	 0xb81c8de1, 0x1d5d1f9f, 0xf773dfec, 0x52324d92, 0x1e93173e, 0xbbd28540,
	 0x51fc4533, 0xf4bdd74d, 0x804db324, 0x250c215a, 0xcf22e129, 0x6a637357,
	 0xb724af65, 0x12653d1b, 0xf84bfd68, 0x5d0a6f16, 0x29fa0b7f, 0x8cbb9901,
	 0x66955972, 0xc3d4cb0c, 0x8f7591a0, 0x2a3403de, 0xc01ac3ad, 0x655b51d3,
	 0x11ab35ba, 0xb4eaa7c4, 0x5ec467b7, 0xfb85f5c9, 0xc786d2ef, 0x62c74091,
	 0x88e980e2, 0x2da8129c, 0x595876f5, 0xfc19e48b, 0x163724f8, 0xb376b686,
	 0xffd7ec2a, 0x5a967e54, 0xb0b8be27, 0x15f92c59, 0x61094830, 0xc448da4e,
	 0x2e661a3d, 0x8b278843, 0x1a22a3eb, 0xbf633195, 0x554df1e6, 0xf00c6398,
	 0x84fc07f1, 0x21bd958f, 0xcb9355fc, 0x6ed2c782, 0x22739d2e, 0x87320f50,
	 0x6d1ccf23, 0xc85d5d5d, 0xbcad3934, 0x19ecab4a, 0xf3c26b39, 0x5683f947,
	 0x6a80de61, 0xcfc14c1f, 0x25ef8c6c, 0x80ae1e12, 0xf45e7a7b, 0x511fe805,
	 0xbb312876, 0x1e70ba08, 0x52d1e0a4, 0xf79072da, 0x1dbeb2a9, 0xb8ff20d7,
	 0xcc0f44be, 0x694ed6c0, 0x836016b3, 0x262184cd, 0xfb6658ff, 0x5e27ca81,
	 0xb4090af2, 0x1148988c, 0x65b8fce5, 0xc0f96e9b, 0x2ad7aee8, 0x8f963c96,
	 0xc337663a, 0x6676f444, 0x8c583437, 0x2919a649, 0x5de9c220, 0xf8a8505e,
	 0x1286902d, 0xb7c70253, 0x8bc42575, 0x2e85b70b, 0xc4ab7778, 0x61eae506,
	 0x151a816f, 0xb05b1311, 0x5a75d362, 0xff34411c, 0xb3951bb0, 0x16d489ce,
	 0xfcfa49bd, 0x59bbdbc3, 0x2d4bbfaa, 0x880a2dd4, 0x6224eda7, 0xc7657fd9,
	 0xdd472332, 0x7806b14c, 0x9228713f, 0x3769e341, 0x43998728, 0xe6d81556,
	 0x0cf6d525, 0xa9b7475b, 0xe5161df7, 0x40578f89, 0xaa794ffa, 0x0f38dd84,
	 0x7bc8b9ed, 0xde892b93, 0x34a7ebe0, 0x91e6799e, 0xade55eb8, 0x08a4ccc6,
	 0xe28a0cb5, 0x47cb9ecb, 0x333bfaa2, 0x967a68dc, 0x7c54a8af, 0xd9153ad1,
	 0x95b4607d, 0x30f5f203, 0xdadb3270, 0x7f9aa00e, 0x0b6ac467, 0xae2b5619,
	 0x4405966a, 0xe1440414, 0x3c03d826, 0x99424a58, 0x736c8a2b, 0xd62d1855,
	 0xa2dd7c3c, 0x079cee42, 0xedb22e31, 0x48f3bc4f, 0x0452e6e3, 0xa113749d,
	 0x4b3db4ee, 0xee7c2690, 0x9a8c42f9, 0x3fcdd087, 0xd5e310f4, 0x70a2828a,
	 0x4ca1a5ac, 0xe9e037d2, 0x03cef7a1, 0xa68f65df, 0xd27f01b6, 0x773e93c8,
	 0x9d1053bb, 0x3851c1c5, 0x74f09b69, 0xd1b10917, 0x3b9fc964, 0x9ede5b1a,
	 0xea2e3f73, 0x4f6fad0d, 0xa5416d7e, 0x0000ff00},
	{0x2803e8bd, 0xf5464205, 0x9764cb3c, 0x4a216184, 0x5321d94e, 0x8e6473f6,
	 0xec46facf, 0x31035077, 0xde478b5b, 0x030221e3, 0x6120a8da, 0xbc650262,
	 0xa565baa8, 0x78201010, 0x1a029929, 0xc7473391, 0xc1675980, 0x1c22f338,
	 0x7e007a01, 0xa345d0b9, 0xba456873, 0x6700c2cb, 0x05224bf2, 0xd867e14a,
	 0x37233a66, 0xea6690de, 0x884419e7, 0x5501b35f, 0x4c010b95, 0x9144a12d,
	 0xf3662814, 0x2e2382ac, 0xff26fc36, 0x2263568e, 0x4041dfb7, 0x9d04750f,
	 0x8404cdc5, 0x5941677d, 0x3b63ee44, 0xe62644fc, 0x09629fd0, 0xd4273568,
	 0xb605bc51, 0x6b4016e9, 0x7240ae23, 0xaf05049b, 0xcd278da2, 0x1062271a,
	 0x16424d0b, 0xcb07e7b3, 0xa9256e8a, 0x7460c432, 0x6d607cf8, 0xb025d640,
	 0xd2075f79, 0x0f42f5c1, 0xe0062eed, 0x3d438455, 0x5f610d6c, 0x8224a7d4,
	 0x9b241f1e, 0x4661b5a6, 0x24433c9f, 0xf9069627, 0x83a5b75a, 0x5ee01de2,
	 0x3cc294db, 0xe1873e63, 0xf88786a9, 0x25c22c11, 0x47e0a528, 0x9aa50f90,
	 0x75e1d4bc, 0xa8a47e04, 0xca86f73d, 0x17c35d85, 0x0ec3e54f, 0xd3864ff7,
	 0xb1a4c6ce, 0x6ce16c76, 0x6ac10667, 0xb784acdf, 0xd5a625e6, 0x08e38f5e,
	 0x11e33794, 0xcca69d2c, 0xae841415, 0x73c1bead, 0x9c856581, 0x41c0cf39,
	 0x23e24600, 0xfea7ecb8, 0xe7a75472, 0x3ae2feca, 0x58c077f3, 0x8585dd4b,
	 0x5480a3d1, 0x89c50969, 0xebe78050, 0x36a22ae8, 0x2fa29222, 0xf2e7389a,
	 0x90c5b1a3, 0x4d801b1b, 0xa2c4c037, 0x7f816a8f, 0x1da3e3b6, 0xc0e6490e,
	 0xd9e6f1c4, 0x04a35b7c, 0x6681d245, 0xbbc478fd, 0xbde412ec, 0x60a1b854,
	 0x0283316d, 0xdfc69bd5, 0xc6c6231f, 0x1b8389a7, 0x79a1009e, 0xa4e4aa26,
	 0x4ba0710a, 0x96e5dbb2, 0xf4c7528b, 0x2982f833, 0x308240f9, 0xedc7ea41,
	 0x8fe56378, 0x52a0c9c0, 0x7aa32182, 0xa7e68b3a, 0xc5c40203, 0x1881a8bb,
	 0x01811071, 0xdcc4bac9, 0xbee633f0, 0x63a39948, 0x8ce74264, 0x51a2e8dc,
	 0x338061e5, 0xeec5cb5d, 0xf7c57397, 0x2a80d92f, 0x48a25016, 0x95e7faae,
	 0x93c790bf, 0x4e823a07, 0x2ca0b33e, 0xf1e51986, 0xe8e5a14c, 0x35a00bf4,
	 0x578282cd, 0x8ac72875, 0x6583f359, 0xb8c659e1, 0xdae4d0d8, 0x07a17a60,
	 0x1ea1c2aa, 0xc3e46812, 0xa1c6e12b, 0x7c834b93, 0xad863509, 0x70c39fb1,
	 0x12e11688, 0xcfa4bc30, 0xd6a404fa, 0x0be1ae42, 0x69c3277b, 0xb4868dc3,
	 0x5bc256ef, 0x8687fc57, 0xe4a5756e, 0x39e0dfd6, 0x20e0671c, 0xfda5cda4,
	 0x9f87449d, 0x42c2ee25, 0x44e28434, 0x99a72e8c, 0xfb85a7b5, 0x26c00d0d,
	 0x3fc0b5c7, 0xe2851f7f, 0x80a79646, 0x5de23cfe, 0xb2a6e7d2, 0x6fe34d6a,
	 0x0dc1c453, 0xd0846eeb, 0xc984d621, 0x14c17c99, 0x76e3f5a0, 0xaba65f18,
	 0xd1057e65, 0x0c40d4dd, 0x6e625de4, 0xb327f75c, 0xaa274f96, 0x7762e52e,
	 0x15406c17, 0xc805c6af, 0x27411d83, 0xfa04b73b, 0x98263e02, 0x456394ba,
	 0x5c632c70, 0x812686c8, 0xe3040ff1, 0x3e41a549, 0x3861cf58, 0xe52465e0,
	 0x8706ecd9, 0x5a434661, 0x4343feab, 0x9e065413, 0xfc24dd2a, 0x21617792,
	 0xce25acbe, 0x13600606, 0x71428f3f, 0xac072587, 0xb5079d4d, 0x684237f5,
	 0x0a60becc, 0xd7251474, 0x06206aee, 0xdb65c056, 0xb947496f, 0x6402e3d7,
	 0x7d025b1d, 0xa047f1a5, 0xc265789c, 0x1f20d224, 0xf0640908, 0x2d21a3b0,
	 0x4f032a89, 0x92468031, 0x8b4638fb, 0x56039243, 0x34211b7a, 0xe964b1c2,
	 0xef44dbd3, 0x3201716b, 0x5023f852, 0x8d6652ea, 0x9466ea20, 0x49234098,
	 0x2b01c9a1, 0xf6446319, 0x1900b835, 0xc445128d, 0xa6679bb4, 0x7b22310c,
	 0x622289c6, 0xbf67237e, 0xdd45aa47, 0x000000ff}
};

/* Table-driven software version as a fall-back. */
static uint32 crc32c_sw(uint32 crc, const void *buf, size_t len)
{
	const uint8 *data = (const uint8 *)buf;
	size_t i, n;

	if (buf == NULL)
		return 0;

	while (len && ((size_t)data & 3) != 0) {
		crc = (crc >> 8) ^ crc32c_table[0][(crc ^ *data++) & 0xff];
		len--;
	}

	n = len >> 2;
	for (i = 0; i < n; i++) {
		uint32 word = crc ^ ((const uint32 *)data)[i];
#ifdef WORDS_BIGENDIAN
		crc   = crc32c_table[3][(word >> 24) & 0xff] ^
			crc32c_table[2][(word >> 16) & 0xff] ^
			crc32c_table[1][(word >>  8) & 0xff] ^
			crc32c_table[0][(word >>  0) & 0xff];
#else
		crc   = crc32c_table[3][(word >>  0) & 0xff] ^
			crc32c_table[2][(word >>  8) & 0xff] ^
			crc32c_table[1][(word >> 16) & 0xff] ^
			crc32c_table[0][(word >> 24) & 0xff];
#endif
	}
	data += n << 2;
	len &= 3;
	while (len) {
		len--;
		crc = (crc >> 8) ^ crc32c_table[0][(crc ^ *data++) & 0xff];
	}
	return crc;
}

#ifdef IS_X86

static uint32 crc32c_sse42(uint32 crc, const void *buf, size_t len)
{
	const uint8 *next = (const uint8 *)buf;
	const uint8 *end;
	uint64 crc0 = crc ^ 0xffffffff;

	if (buf == NULL)
		return 0;

	// Compute the crc for up to seven leading bytes, bringing the data pointer
	// to an eight-byte boundary.
	while (len && ((size_t)next & 7) != 0) {
		__asm__("crc32b\t" "(%1), %0"
			: "+r"(crc0)
			: "r"(next), "m"(*next));
		next++;
		len--;
	}

	// Compute the crc on eight-byte units.
	end = next + (len - (len & 7));
	while (next < end) {
		__asm__("crc32q\t" "(%1), %0"
			: "+r"(crc0)
			: "r"(next), "m"(*next));
		next += 8;
	}
	len &= 7;

	// Compute the crc for up to seven trailing bytes.
	while (len) {
		__asm__("crc32b\t" "(%1), %0"
			: "+r"(crc0)
			: "r"(next), "m"(*next));
		next++;
		len--;
	}

	// Return the crc, post-processed.
	return ~(uint32)crc0;
}

static int has_crc32c_sse42(void)
{
	uint32 eax, ecx;
	eax = 1;
	__asm__("cpuid"
		: "=c"(ecx)
		: "a"(eax)
		: "%ebx", "%edx");

	return (ecx >> 20) & 1;
}

#endif /* IS_X86 */

#ifdef IS_ARM64_CRC32C

static uint32 crc32c_arm64(uint32 crc, const void *buf, size_t len)
{
	const uint8 *next = (const uint8 *)buf;
	const uint8 *end;

	if (buf == NULL)
		return 0;

	crc = ~crc;

	while (len && ((size_t)next & 7) != 0) {
		crc = __crc32cb(crc, *next);
		next++;
		len--;
	}

	end = next + (len - (len & 7));
	while (next < end) {
		crc = __crc32cd(crc, *((uint64 *)next));
		next += 8;
	}
	len &= 7;

	while (len) {
		crc = __crc32cb(crc, *next);
		next++;
		len--;
	}

	return ~crc;
}

static int has_crc32c_arm64(void)
{
	/* // "haha you thought this would work in user mode?" --ARM probably
	uint32 id_isar5;
	__asm__("mrc p15, 0, %0, c0, c2, 5"
		: "+r"(id_isar5)
	);

	return (id_isar5 >> 16) & 0xff;
	*/
	return 1;
}

#endif /* IS_ARM64_CRC32C */

/* Compute a CRC-32C.  If the crc32 instruction is available, use the hardware
 * version.  Otherwise, use the software version. */
uint32 libxmp_crc32c(uint32 crc, const void *buf, size_t len)
{
#ifdef IS_X86
	if (has_crc32c_sse42())
		return crc32c_sse42(crc, buf, len);
#endif

#ifdef IS_ARM64_CRC32C
	if (has_crc32c_arm64())
		return crc32c_arm64(crc, buf, len);
#endif
	return crc32c_sw(crc, buf, len);
}

int main(void)
{
	static const char TEST_STRING[] = "abcdefjlkjfgklflg";
	printf("CRC-32c software: %08x\n", crc32c_sw(0, TEST_STRING, strlen(TEST_STRING)));
	printf("CRC-32c hardware: %08x\n", libxmp_crc32c(0, TEST_STRING, strlen(TEST_STRING)));
	return 0;
}
#endif /* !CRC32_GENERATE */


#ifdef CRC32_GENERATE
// Generate crc32c.h for crc32c.c.

#include <stdio.h>
#include <stdint.h>

#define LONG 8192
#define SHORT 256

// Print a 2-D table of four-byte constants in hex.
static void print_table(uint32_t *tab, size_t rows, size_t cols, char *name)
{
    printf("static const uint32 %s[][%zu] =\n{\n", name, cols);
    size_t end = rows * cols;
    size_t k = 0;
    for (;;) {
	fputs("\t{", stdout);
	size_t n = 0, j = 0;
	for (;;) {
	    printf("0x%08x", tab[k + n]);
	    if (++n == cols)
		break;
	    putchar(',');
	    if (++j == 6) {
		fputs("\n\t", stdout);
		j = 0;
	    }
	    putchar(' ');
	}
	k += cols;
	if (k == end)
	    break;
	puts("},");
    }
    puts("}\n};");
}

/* CRC-32C (iSCSI) polynomial in reversed bit order. */
#define POLY 0x82f63b78
/*
static void crc32c_word_table(void) {
    uint32_t table[8][256];

    // Generate byte-wise table.
    for (unsigned n = 0; n < 256; n++) {
	uint32_t crc = ~n;
	for (unsigned k = 0; k < 8; k++)
	    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
	table[0][n] = ~crc;
    }

    // Use byte-wise table to generate word-wise table.
    for (unsigned n = 0; n < 256; n++) {
	uint32_t crc = ~table[0][n];
	for (unsigned k = 1; k < 8; k++) {
	    crc = table[0][crc & 0xff] ^ (crc >> 8);
	    table[k][n] = ~crc;
	}
    }

    // Print table.
    print_table(table[0], 8, 256, "crc32c_table");
}*/

static void crc32c_word_table(void)
{
	uint32_t table[4][256];

	// Generate byte-wise table.
	for (unsigned n = 0; n < 256; n++) {
		uint32_t crc = ~n;
		for (unsigned k = 0; k < 8; k++)
			crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
		table[0][n] = ~crc;
	}

	// Use byte-wise table to generate word-wise table.
	for (unsigned n = 0; n < 256; n++) {
		uint32_t crc = ~table[0][n];
		for (unsigned k = 1; k < 4; k++) {
			crc = table[0][crc & 0xff] ^ (crc >> 8);
			table[k][n] = ~crc;
		}
	}

	// Print table.
	print_table(table[0], 4, 256, "crc32c_table");
}

int main(void)
{
	puts(
"// crc32c.h\n"
"// Tables and constants for crc32c.c software and hardware calculations.\n"
"\n"
"// Table for a 32-bits-at-a-time software CRC-32C calculation. This table\n"
"// has built into it the pre and post bit inversion of the CRC."
	);
	crc32c_word_table();
	return 0;
}

#endif /* CRC32_GENERATE */