diff options
| author | robot-contrib <[email protected]> | 2025-05-18 12:54:09 +0300 |
|---|---|---|
| committer | robot-contrib <[email protected]> | 2025-05-18 13:06:58 +0300 |
| commit | d1811f1cf5a0337457ccd3288ea035b98766d0ab (patch) | |
| tree | 47b0b2c8e27b4827c4f86d3f2b90a0787a7621a8 | |
| parent | 510bcc570720f5f3f1c90491ccdce126155c1017 (diff) | |
Update contrib/restricted/aws/aws-checksums to 0.2.7
commit_hash:c5bf5558f1399900ede13429f75a7f75ebd82151
29 files changed, 2443 insertions, 187 deletions
diff --git a/contrib/restricted/aws/aws-c-common/.yandex_meta/__init__.py b/contrib/restricted/aws/aws-c-common/.yandex_meta/__init__.py index 2cd57a9d597..56f81bb9af1 100644 --- a/contrib/restricted/aws/aws-c-common/.yandex_meta/__init__.py +++ b/contrib/restricted/aws/aws-c-common/.yandex_meta/__init__.py @@ -99,6 +99,9 @@ aws_c_common = CMakeNinjaNixProject( disable_includes=[ "legacy/ittnotify.h", ], + platform_dispatchers=[ + "generated/include/aws/common/config.h", + ], install_targets=["aws-c-common"], post_install=post_install, ) diff --git a/contrib/restricted/aws/aws-c-common/.yandex_meta/devtools.copyrights.report b/contrib/restricted/aws/aws-c-common/.yandex_meta/devtools.copyrights.report index 12b66fe1ae9..eb5b0f2cc33 100644 --- a/contrib/restricted/aws/aws-c-common/.yandex_meta/devtools.copyrights.report +++ b/contrib/restricted/aws/aws-c-common/.yandex_meta/devtools.copyrights.report @@ -38,7 +38,7 @@ BELONGS ya.make Score : 100.00 Match type : COPYRIGHT Files with this license: - generated/include/aws/common/config.h [5:5] + generated/include/aws/common/config-linux.h [5:5] include/aws/common/allocator.h [4:4] include/aws/common/array_list.h [5:5] include/aws/common/array_list.inl [5:5] diff --git a/contrib/restricted/aws/aws-c-common/.yandex_meta/devtools.licenses.report b/contrib/restricted/aws/aws-c-common/.yandex_meta/devtools.licenses.report index a8ede1532c6..164fe22492c 100644 --- a/contrib/restricted/aws/aws-c-common/.yandex_meta/devtools.licenses.report +++ b/contrib/restricted/aws/aws-c-common/.yandex_meta/devtools.licenses.report @@ -279,7 +279,7 @@ BELONGS ya.make Match type : TAG Links : http://www.apache.org/licenses/, http://www.apache.org/licenses/LICENSE-2.0, https://spdx.org/licenses/Apache-2.0 Files with this license: - generated/include/aws/common/config.h [6:6] + generated/include/aws/common/config-linux.h [6:6] include/aws/common/allocator.h [5:5] include/aws/common/array_list.h [6:6] include/aws/common/array_list.inl [6:6] diff --git a/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config-armv8a.h b/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config-armv8a.h new file mode 100644 index 00000000000..e76c18c7d81 --- /dev/null +++ b/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config-armv8a.h @@ -0,0 +1,8 @@ +#pragma once + +#include "config-linux.h" + +#undef AWS_ARCH_INTEL +#undef AWS_ARCH_INTEL_X64 + +#define AWS_ARCH_ARM64 diff --git a/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config-linux.h b/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config-linux.h new file mode 100644 index 00000000000..1bab20d34b3 --- /dev/null +++ b/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config-linux.h @@ -0,0 +1,33 @@ +#ifndef AWS_COMMON_CONFIG_H +#define AWS_COMMON_CONFIG_H + +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +/* + * This header exposes compiler feature test results determined during cmake + * configure time to inline function implementations. The macros defined here + * should be considered to be an implementation detail, and can change at any + * time. + */ +#define AWS_HAVE_GCC_OVERFLOW_MATH_EXTENSIONS +#define AWS_HAVE_GCC_INLINE_ASM +/* #undef AWS_HAVE_MSVC_INTRINSICS_X64 */ +#define AWS_HAVE_POSIX_LARGE_FILE_SUPPORT +/* #undef AWS_HAVE_EXECINFO */ +/* #undef AWS_HAVE_WINAPI_DESKTOP */ +#define AWS_HAVE_LINUX_IF_LINK_H +#define AWS_HAVE_AVX2_INTRINSICS +#define AWS_HAVE_AVX512_INTRINSICS +#define AWS_HAVE_MM256_EXTRACT_EPI64 +#define AWS_HAVE_CLMUL +/* #undef AWS_HAVE_ARM32_CRC */ +/* #undef AWS_HAVE_ARMv8_1 */ +/* #undef AWS_ARCH_ARM64 */ +#define AWS_ARCH_INTEL +#define AWS_ARCH_INTEL_X64 +#define AWS_USE_CPU_EXTENSIONS + +#endif diff --git a/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config.h b/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config.h index 1bab20d34b3..31c5d95152a 100644 --- a/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config.h +++ b/contrib/restricted/aws/aws-c-common/generated/include/aws/common/config.h @@ -1,33 +1,7 @@ -#ifndef AWS_COMMON_CONFIG_H -#define AWS_COMMON_CONFIG_H - -/** - * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. - * SPDX-License-Identifier: Apache-2.0. - */ - -/* - * This header exposes compiler feature test results determined during cmake - * configure time to inline function implementations. The macros defined here - * should be considered to be an implementation detail, and can change at any - * time. - */ -#define AWS_HAVE_GCC_OVERFLOW_MATH_EXTENSIONS -#define AWS_HAVE_GCC_INLINE_ASM -/* #undef AWS_HAVE_MSVC_INTRINSICS_X64 */ -#define AWS_HAVE_POSIX_LARGE_FILE_SUPPORT -/* #undef AWS_HAVE_EXECINFO */ -/* #undef AWS_HAVE_WINAPI_DESKTOP */ -#define AWS_HAVE_LINUX_IF_LINK_H -#define AWS_HAVE_AVX2_INTRINSICS -#define AWS_HAVE_AVX512_INTRINSICS -#define AWS_HAVE_MM256_EXTRACT_EPI64 -#define AWS_HAVE_CLMUL -/* #undef AWS_HAVE_ARM32_CRC */ -/* #undef AWS_HAVE_ARMv8_1 */ -/* #undef AWS_ARCH_ARM64 */ -#define AWS_ARCH_INTEL -#define AWS_ARCH_INTEL_X64 -#define AWS_USE_CPU_EXTENSIONS +#pragma once +#if defined(__aarch64__) || defined(_M_ARM64) +# include "config-armv8a.h" +#else +# include "config-linux.h" #endif diff --git a/contrib/restricted/aws/aws-checksums/.yandex_meta/__init__.py b/contrib/restricted/aws/aws-checksums/.yandex_meta/__init__.py index b04ae95e3b2..82e99879c4a 100644 --- a/contrib/restricted/aws/aws-checksums/.yandex_meta/__init__.py +++ b/contrib/restricted/aws/aws-checksums/.yandex_meta/__init__.py @@ -1,16 +1,33 @@ -from devtools.yamaker.modules import Linkable, Switch from devtools.yamaker.project import CMakeNinjaNixProject def post_install(self): # Otherwise debug build fails with gcc, as expected by the authors. - self.yamakes["."].after("CFLAGS", Switch({'BUILD_TYPE == "DEBUG"': Linkable(CFLAGS=["-DDEBUG_BUILD"])})) + with self.yamakes["."] as m: + m.SRCS.remove("source/intel/intrin/crc64nvme_clmul.c") + m.SRCS.remove("source/intel/intrin/crc32c_sse42_avx512.c") + m.SRCS.remove("source/intel/intrin/crc64nvme_avx512.c") + m.after( + "SRCS", + """ + IF (ARCH_X86_64) + SRC_C_AVX(source/intel/intrin/crc64nvme_clmul.c) + SRC_C_AVX512(source/intel/intrin/crc32c_sse42_avx512.c -mvpclmulqdq) + SRC_C_AVX512(source/intel/intrin/crc64nvme_avx512.c -mvpclmulqdq) + ELSEIF (ARCH_ARM64) + SRC(source/arm/crc32c_arm.c -mcrc) + ENDIF() + """, + ) aws_checksums = CMakeNinjaNixProject( arcdir="contrib/restricted/aws/aws-checksums", nixattr="aws-checksums", owners=["g:cpp-contrib"], + copy_sources=[ + "source/arm/crc32c_arm.c", + ], flags=["-DBUILD_JNI_BINDINGS=OFF"], disable_includes=["aws/checksums/crc_jni.h"], post_install=post_install, diff --git a/contrib/restricted/aws/aws-checksums/.yandex_meta/devtools.copyrights.report b/contrib/restricted/aws/aws-checksums/.yandex_meta/devtools.copyrights.report index e25417daec0..bed8808ec17 100644 --- a/contrib/restricted/aws/aws-checksums/.yandex_meta/devtools.copyrights.report +++ b/contrib/restricted/aws/aws-checksums/.yandex_meta/devtools.copyrights.report @@ -40,9 +40,19 @@ BELONGS ya.make Score : 100.00 Match type : COPYRIGHT Files with this license: + include/aws/checksums/checksums.h [4:4] include/aws/checksums/crc.h [4:4] include/aws/checksums/exports.h [4:4] - include/aws/checksums/private/crc_priv.h [4:4] - source/crc.c [2:2] + include/aws/checksums/private/crc32_priv.h [4:4] + include/aws/checksums/private/crc64_priv.h [5:5] + include/aws/checksums/private/crc_util.h [4:4] + source/arm/crc32c_arm.c [2:2] + source/checksums.c [2:2] + source/crc32.c [2:2] + source/crc64.c [2:2] + source/crc64_sw.c [2:2] source/crc_sw.c [2:2] source/intel/asm/crc32c_sse42_asm.c [2:2] + source/intel/intrin/crc32c_sse42_avx512.c [2:2] + source/intel/intrin/crc64nvme_avx512.c [2:2] + source/intel/intrin/crc64nvme_clmul.c [2:2] diff --git a/contrib/restricted/aws/aws-checksums/.yandex_meta/devtools.licenses.report b/contrib/restricted/aws/aws-checksums/.yandex_meta/devtools.licenses.report index 50bd3a93152..98b52cb56e8 100644 --- a/contrib/restricted/aws/aws-checksums/.yandex_meta/devtools.licenses.report +++ b/contrib/restricted/aws/aws-checksums/.yandex_meta/devtools.licenses.report @@ -41,12 +41,22 @@ BELONGS ya.make Match type : TAG Links : http://www.apache.org/licenses/, http://www.apache.org/licenses/LICENSE-2.0, https://spdx.org/licenses/Apache-2.0 Files with this license: + include/aws/checksums/checksums.h [5:5] include/aws/checksums/crc.h [5:5] include/aws/checksums/exports.h [5:5] - include/aws/checksums/private/crc_priv.h [5:5] - source/crc.c [3:3] + include/aws/checksums/private/crc32_priv.h [5:5] + include/aws/checksums/private/crc64_priv.h [6:6] + include/aws/checksums/private/crc_util.h [5:5] + source/arm/crc32c_arm.c [3:3] + source/checksums.c [3:3] + source/crc32.c [3:3] + source/crc64.c [3:3] + source/crc64_sw.c [3:3] source/crc_sw.c [3:3] source/intel/asm/crc32c_sse42_asm.c [3:3] + source/intel/intrin/crc32c_sse42_avx512.c [3:3] + source/intel/intrin/crc64nvme_avx512.c [3:3] + source/intel/intrin/crc64nvme_clmul.c [3:3] KEEP Apache-2.0 dc7f21ccff0f672f2a7cd6f412ae627d BELONGS ya.make diff --git a/contrib/restricted/aws/aws-checksums/.yandex_meta/override.nix b/contrib/restricted/aws/aws-checksums/.yandex_meta/override.nix index 9684509a4f4..f3665f72f50 100644 --- a/contrib/restricted/aws/aws-checksums/.yandex_meta/override.nix +++ b/contrib/restricted/aws/aws-checksums/.yandex_meta/override.nix @@ -1,10 +1,10 @@ pkgs: attrs: with pkgs; with attrs; rec { - version = "0.1.14"; + version = "0.2.7"; src = fetchFromGitHub { owner = "awslabs"; repo = "aws-checksums"; rev = "v${version}"; - hash = "sha256-yoViXJuM9UQMcn8W0CcWkCXroBLXjAestr+oqWHi5hQ="; + hash = "sha256-dYDTDWZJJ0JlvkMfLS376uUt5QzSmbV0UNRC4aq35TY="; }; } diff --git a/contrib/restricted/aws/aws-checksums/include/aws/checksums/checksums.h b/contrib/restricted/aws/aws-checksums/include/aws/checksums/checksums.h new file mode 100644 index 00000000000..623d6fe2a0e --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/include/aws/checksums/checksums.h @@ -0,0 +1,30 @@ +#ifndef AWS_CHECKSUMS_CHECKSUMS_H +#define AWS_CHECKSUMS_CHECKSUMS_H +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/checksums/exports.h> +#include <aws/common/common.h> + +AWS_PUSH_SANE_WARNING_LEVEL +AWS_EXTERN_C_BEGIN + +/** + * Initializes internal data structures used by aws-checksums. + * MUST be called before using any functionality in aws-checksums. + * Note: historically aws-checksums lazily initialized stuff and things worked without init. + * However, DO NOT rely on that behavior and explicitly call init instead. + */ +AWS_CHECKSUMS_API void aws_checksums_library_init(struct aws_allocator *allocator); + +/** + * Shuts down the internal data structures used by aws-checksums. + */ +AWS_CHECKSUMS_API void aws_checksums_library_clean_up(void); + +AWS_EXTERN_C_END +AWS_POP_SANE_WARNING_LEVEL + +#endif /* AWS_CHECKSUMS_CHECKSUMS_H */ diff --git a/contrib/restricted/aws/aws-checksums/include/aws/checksums/crc.h b/contrib/restricted/aws/aws-checksums/include/aws/checksums/crc.h index 0bb3022e784..2952450f686 100644 --- a/contrib/restricted/aws/aws-checksums/include/aws/checksums/crc.h +++ b/contrib/restricted/aws/aws-checksums/include/aws/checksums/crc.h @@ -6,11 +6,11 @@ */ #include <aws/checksums/exports.h> -#include <stdint.h> +#include <aws/common/macros.h> +#include <aws/common/stdint.h> -#ifdef __cplusplus -extern "C" { -#endif +AWS_PUSH_SANE_WARNING_LEVEL +AWS_EXTERN_C_BEGIN /** * The entry point function to perform a CRC32 (Ethernet, gzip) computation. @@ -18,18 +18,56 @@ extern "C" { * Pass 0 in the previousCrc32 parameter as an initial value unless continuing * to update a running crc in a subsequent call. */ -AWS_CHECKSUMS_API uint32_t aws_checksums_crc32(const uint8_t *input, int length, uint32_t previousCrc32); +AWS_CHECKSUMS_API uint32_t aws_checksums_crc32(const uint8_t *input, int length, uint32_t previous_crc32); + +/** + * The entry point function to perform a CRC32 (Ethernet, gzip) computation. + * Supports buffer lengths up to size_t max. + * Selects a suitable implementation based on hardware capabilities. + * Pass 0 in the previousCrc32 parameter as an initial value unless continuing + * to update a running crc in a subsequent call. + */ +AWS_CHECKSUMS_API uint32_t aws_checksums_crc32_ex(const uint8_t *input, size_t length, uint32_t previous_crc32); + +/** + * The entry point function to perform a Castagnoli CRC32c (iSCSI) computation. + * Selects a suitable implementation based on hardware capabilities. + * Pass 0 in the previousCrc32 parameter as an initial value unless continuing + * to update a running crc in a subsequent call. + */ +AWS_CHECKSUMS_API uint32_t aws_checksums_crc32c(const uint8_t *input, int length, uint32_t previous_crc32c); /** * The entry point function to perform a Castagnoli CRC32c (iSCSI) computation. + * Supports buffer lengths up to size_t max. * Selects a suitable implementation based on hardware capabilities. * Pass 0 in the previousCrc32 parameter as an initial value unless continuing * to update a running crc in a subsequent call. */ -AWS_CHECKSUMS_API uint32_t aws_checksums_crc32c(const uint8_t *input, int length, uint32_t previousCrc32); +AWS_CHECKSUMS_API uint32_t aws_checksums_crc32c_ex(const uint8_t *input, size_t length, uint32_t previous_crc32c); + +/** + * The entry point function to perform a CRC64-NVME (a.k.a. CRC64-Rocksoft) computation. + * Selects a suitable implementation based on hardware capabilities. + * Pass 0 in the previousCrc64 parameter as an initial value unless continuing + * to update a running crc in a subsequent call. + * There are many variants of CRC64 algorithms. This CRC64 variant is bit-reflected (based on + * the non bit-reflected polynomial 0xad93d23594c93659) and inverts the CRC input and output bits. + */ +AWS_CHECKSUMS_API uint64_t aws_checksums_crc64nvme(const uint8_t *input, int length, uint64_t previous_crc64); + +/** + * The entry point function to perform a CRC64-NVME (a.k.a. CRC64-Rocksoft) computation. + * Supports buffer lengths up to size_t max. + * Selects a suitable implementation based on hardware capabilities. + * Pass 0 in the previousCrc64 parameter as an initial value unless continuing + * to update a running crc in a subsequent call. + * There are many variants of CRC64 algorithms. This CRC64 variant is bit-reflected (based on + * the non bit-reflected polynomial 0xad93d23594c93659) and inverts the CRC input and output bits. + */ +AWS_CHECKSUMS_API uint64_t aws_checksums_crc64nvme_ex(const uint8_t *input, size_t length, uint64_t previous_crc64); -#ifdef __cplusplus -} -#endif +AWS_EXTERN_C_END +AWS_POP_SANE_WARNING_LEVEL #endif /* AWS_CHECKSUMS_CRC_H */ diff --git a/contrib/restricted/aws/aws-checksums/include/aws/checksums/exports.h b/contrib/restricted/aws/aws-checksums/include/aws/checksums/exports.h index a14e84e4403..fd9f2d885e5 100644 --- a/contrib/restricted/aws/aws-checksums/include/aws/checksums/exports.h +++ b/contrib/restricted/aws/aws-checksums/include/aws/checksums/exports.h @@ -4,7 +4,7 @@ * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. * SPDX-License-Identifier: Apache-2.0. */ -#if defined(AWS_C_RT_USE_WINDOWS_DLL_SEMANTICS) || defined(_WIN32) +#if defined(AWS_CRT_USE_WINDOWS_DLL_SEMANTICS) || defined(_WIN32) # ifdef AWS_CHECKSUMS_USE_IMPORT_EXPORT # ifdef AWS_CHECKSUMS_EXPORTS # define AWS_CHECKSUMS_API __declspec(dllexport) @@ -14,13 +14,12 @@ # else # define AWS_CHECKSUMS_API # endif /* AWS_CHECKSUMS_USE_IMPORT_EXPORT */ -#else /* defined (AWS_C_RT_USE_WINDOWS_DLL_SEMANTICS) || defined (_WIN32) */ -# if ((__GNUC__ >= 4) || defined(__clang__)) && defined(AWS_CHECKSUMS_USE_IMPORT_EXPORT) && \ - defined(AWS_CHECKSUMS_EXPORTS) +#else /* defined (AWS_CRT_USE_WINDOWS_DLL_SEMANTICS) || defined (_WIN32) */ +# if defined(AWS_CHECKSUMS_USE_IMPORT_EXPORT) && defined(AWS_CHECKSUMS_EXPORTS) # define AWS_CHECKSUMS_API __attribute__((visibility("default"))) # else # define AWS_CHECKSUMS_API -# endif /* __GNUC__ >= 4 || defined(__clang__) */ -#endif /* defined (AWS_C_RT_USE_WINDOWS_DLL_SEMANTICS) || defined (_WIN32) */ +# endif +#endif /* defined (AWS_CRT_USE_WINDOWS_DLL_SEMANTICS) || defined (_WIN32) */ #endif /* AWS_CHECKSUMS_EXPORTS_H */ diff --git a/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc32_priv.h b/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc32_priv.h new file mode 100644 index 00000000000..678677d7944 --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc32_priv.h @@ -0,0 +1,50 @@ +#ifndef AWS_CHECKSUMS_PRIVATE_CRC_PRIV_H +#define AWS_CHECKSUMS_PRIVATE_CRC_PRIV_H +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#define AWS_CRC32_SIZE_BYTES 4 +#include <aws/checksums/exports.h> +#include <aws/common/common.h> + +#include <aws/common/config.h> +#include <stdint.h> + +AWS_EXTERN_C_BEGIN + +/* Computes CRC32 (Ethernet, gzip, et. al.) using a (slow) reference implementation. */ +AWS_CHECKSUMS_API uint32_t aws_checksums_crc32_sw(const uint8_t *input, int length, uint32_t previousCrc32); + +/* Computes the Castagnoli CRC32c (iSCSI) using a (slow) reference implementation. */ +AWS_CHECKSUMS_API uint32_t aws_checksums_crc32c_sw(const uint8_t *input, int length, uint32_t previousCrc32c); + +#if defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_ARM64) +uint32_t aws_checksums_crc32_armv8(const uint8_t *input, int length, uint32_t previous_crc32); +uint32_t aws_checksums_crc32c_armv8(const uint8_t *input, int length, uint32_t previous_crc32c); +#elif defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_INTEL) +# if defined(AWS_ARCH_INTEL_X64) +typedef uint64_t *slice_ptr_type; +typedef uint64_t slice_ptr_int_type; +# define crc_intrin_fn _mm_crc32_u64 + +# if !defined(_MSC_VER) +uint32_t aws_checksums_crc32c_clmul_sse42(const uint8_t *data, int length, uint32_t previous_crc32c); +# endif + +# else +typedef uint32_t *slice_ptr_type; +typedef uint32_t slice_ptr_int_type; +# define crc_intrin_fn _mm_crc32_u32 +# endif +uint32_t aws_checksums_crc32c_intel_avx512_with_sse_fallback( + const uint8_t *input, + int length, + uint32_t previous_crc32c); + +#endif + +AWS_EXTERN_C_END + +#endif /* AWS_CHECKSUMS_PRIVATE_CRC_PRIV_H */ diff --git a/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc64_priv.h b/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc64_priv.h new file mode 100644 index 00000000000..f070dd7f1f3 --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc64_priv.h @@ -0,0 +1,51 @@ +#ifndef AWS_CHECKSUMS_PRIVATE_CRC64_PRIV_H +#define AWS_CHECKSUMS_PRIVATE_CRC64_PRIV_H + +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/checksums/exports.h> +#include <aws/common/config.h> +#include <aws/common/macros.h> +#include <stdint.h> + +AWS_EXTERN_C_BEGIN + +AWS_CHECKSUMS_API uint64_t aws_checksums_crc64nvme_sw(const uint8_t *input, int length, uint64_t prev_crc64); + +#if defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_INTEL_X64) && defined(AWS_HAVE_CLMUL) && \ + !(defined(_MSC_VER) && _MSC_VER < 1920) +uint64_t aws_checksums_crc64nvme_intel_clmul(const uint8_t *input, int length, uint64_t previous_crc_64); +#endif /* defined(AWS_ARCH_INTEL_X64) && defined(AWS_HAVE_CLMUL) && !(defined(_MSC_VER) && _MSC_VER < 1920) */ + +#if defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_INTEL_X64) && defined(AWS_HAVE_AVX2_INTRINSICS) && \ + !(defined(_MSC_VER) && _MSC_VER < 1920) +uint64_t aws_checksums_crc64nvme_intel_avx512(const uint8_t *input, int length, uint64_t previous_crc_64); +#endif /* defined(AWS_ARCH_INTEL_X64) && defined(AWS_HAVE_AVX2_INTRINSICS) && !(defined(_MSC_VER) && _MSC_VER < 1920) \ + */ + +#if defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_ARM64) +uint64_t aws_checksums_crc64nvme_arm_pmull(const uint8_t *input, int length, uint64_t previous_crc_64); +#endif /* INTPTR_MAX == INT64_MAX && defined(AWS_HAVE_ARMv8_1) */ + +/* Pre-computed constants for CRC64 */ +typedef struct { + uint64_t x2048[8]; /* x^2112 mod P(x) / x^2048 mod P(x) */ + uint64_t x1536[8]; /* x^1600 mod P(x) / x^1536 mod P(x) */ + uint64_t x1024[8]; /* x^1088 mod P(x) / x^1024 mod P(x) */ + uint64_t x512[8]; /* x^576 mod P(x) / x^512 mod P(x) */ + uint64_t x384[2]; /* x^448 mod P(x) / x^384 mod P(x) */ + uint64_t x256[2]; /* x^320 mod P(x) / x^256 mod P(x) */ + uint64_t x128[2]; /* x^192 mod P(x) / x^128 mod P(x) */ + uint64_t mu_poly[2]; /* Barrett mu / polynomial P(x) */ + uint64_t trailing[15][2]; /* Folding constants for 15 possible trailing input data lengths */ +} aws_checksums_crc64_constants_t; + +extern uint8_t aws_checksums_masks_shifts[6][16]; +extern aws_checksums_crc64_constants_t aws_checksums_crc64nvme_constants; + +AWS_EXTERN_C_END + +#endif /* AWS_CHECKSUMS_PRIVATE_CRC64_PRIV_H */ diff --git a/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc_priv.h b/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc_priv.h deleted file mode 100644 index 221c86f9a20..00000000000 --- a/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc_priv.h +++ /dev/null @@ -1,33 +0,0 @@ -#ifndef AWS_CHECKSUMS_PRIVATE_CRC_PRIV_H -#define AWS_CHECKSUMS_PRIVATE_CRC_PRIV_H -/** - * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. - * SPDX-License-Identifier: Apache-2.0. - */ - -#define AWS_CRC32_SIZE_BYTES 4 - -#include <aws/checksums/exports.h> -#include <stdint.h> - -#ifdef __cplusplus -extern "C" { -#endif - -/* Computes CRC32 (Ethernet, gzip, et. al.) using a (slow) reference implementation. */ -AWS_CHECKSUMS_API uint32_t aws_checksums_crc32_sw(const uint8_t *input, int length, uint32_t previousCrc32); - -/* Computes the Castagnoli CRC32c (iSCSI) using a (slow) reference implementation. */ -AWS_CHECKSUMS_API uint32_t aws_checksums_crc32c_sw(const uint8_t *input, int length, uint32_t previousCrc32c); - -/* Computes the Castagnoli CRC32c (iSCSI). */ -AWS_CHECKSUMS_API uint32_t aws_checksums_crc32c_hw(const uint8_t *data, int length, uint32_t previousCrc32); - -/* Computes CRC32 (Ethernet, gzip, et. al.) using crc instructions. */ -AWS_CHECKSUMS_API uint32_t aws_checksums_crc32_hw(const uint8_t *data, int length, uint32_t previousCrc32); - -#ifdef __cplusplus -} -#endif - -#endif /* AWS_CHECKSUMS_PRIVATE_CRC_PRIV_H */ diff --git a/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc_util.h b/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc_util.h new file mode 100644 index 00000000000..3f6fefe9094 --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/include/aws/checksums/private/crc_util.h @@ -0,0 +1,128 @@ +#ifndef AWS_CHECKSUMS_PRIVATE_CRC_UTIL_H +#define AWS_CHECKSUMS_PRIVATE_CRC_UTIL_H +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/common/byte_order.h> +#include <aws/common/cpuid.h> +#include <aws/common/stdint.h> +#include <limits.h> +#include <stdlib.h> + +#define large_buffer_apply_impl(Name, T) \ + static T aws_large_buffer_apply_##Name( \ + T (*checksum_fn)(const uint8_t *, int, T), const uint8_t *buffer, size_t length, T previous) { \ + T val = previous; \ + while (length > INT_MAX) { \ + val = checksum_fn(buffer, INT_MAX, val); \ + buffer += (size_t)INT_MAX; \ + length -= (size_t)INT_MAX; \ + } \ + val = checksum_fn(buffer, (int)length, val); \ + return val; \ + } + +/* helper function to reverse byte order on big-endian platforms*/ +static inline uint32_t aws_bswap32_if_be(uint32_t x) { + if (!aws_is_big_endian()) { + return x; + } + +#if _MSC_VER + return _byteswap_ulong(x); +#elif defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)) + return __builtin_bswap32(x); +#elif defined(__clang__) && __clang_major__ >= 3 + return __builtin_bswap32(x); +#else + return ( + ((x & 0xff000000u) >> 24) | ((x & 0x00ff0000u) >> 8) | ((x & 0x0000ff00u) << 8) | ((x & 0x000000ffu) << 24)); +#endif +} + +/* Reverse the bytes in a 64-bit word. */ +static inline uint64_t aws_bswap64_if_be(uint64_t x) { + if (!aws_is_big_endian()) { + return x; + } + +#if _MSC_VER + return _byteswap_uint64(x); +#elif defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)) + /* Note: gcc supports it starting with 4.2. here its just picking the lowest version we run test on. */ + return __builtin_bswap64(x); +#elif defined(__clang__) && __clang_major__ >= 3 + return __builtin_bswap64(x); +#else + return ((x << 56) & 0xff00000000000000ULL) | ((x << 40) & 0x00ff000000000000ULL) | + ((x << 24) & 0x0000ff0000000000ULL) | ((x << 8) & 0x000000ff00000000ULL) | + ((x >> 8) & 0x00000000ff000000ULL) | ((x >> 24) & 0x0000000000ff0000ULL) | + ((x >> 40) & 0x000000000000ff00ULL) | ((x >> 56) & 0x00000000000000ffULL); +#endif +} + +/** + * Force resolution of any global variables for CRC32. + * Note: in usual flow those are resolved on the first call to crc32 functions, which + * which might be deemed non-thread safe by some tools. + */ +void aws_checksums_crc32_init(void); + +/** + * Force resolution of any global variables for CRC64. + * Note: in usual flow those are resolved on the first call to crc64 functions, which + * which might be deemed non-thread safe by some tools. + */ +void aws_checksums_crc64_init(void); + +/** + * Note: this is slightly different from our typical pattern. + * This check is currently performed in a tight loop, so jumping through + * some hoops with inlining to avoid perf regressions, which forces + * below functions to be declared in a header. + */ +extern bool s_detection_performed; +extern bool s_detected_sse42; +extern bool s_detected_avx512; +extern bool s_detected_clmul; +extern bool s_detected_vpclmulqdq; + +static inline void aws_checksums_init_detection_cache(void) { + s_detected_clmul = aws_cpu_has_feature(AWS_CPU_FEATURE_CLMUL); + s_detected_sse42 = aws_cpu_has_feature(AWS_CPU_FEATURE_SSE_4_2); + s_detected_avx512 = aws_cpu_has_feature(AWS_CPU_FEATURE_AVX512); + s_detected_clmul = aws_cpu_has_feature(AWS_CPU_FEATURE_CLMUL); + s_detected_vpclmulqdq = aws_cpu_has_feature(AWS_CPU_FEATURE_VPCLMULQDQ); +} + +static inline bool aws_cpu_has_clmul_cached(void) { + if (AWS_UNLIKELY(!s_detection_performed)) { + aws_checksums_init_detection_cache(); + } + return s_detected_clmul; +} + +static inline bool aws_cpu_has_sse42_cached(void) { + if (AWS_UNLIKELY(!s_detection_performed)) { + aws_checksums_init_detection_cache(); + } + return s_detected_sse42; +} + +static inline bool aws_cpu_has_avx512_cached(void) { + if (AWS_UNLIKELY(!s_detection_performed)) { + aws_checksums_init_detection_cache(); + } + return s_detected_avx512; +} + +static inline bool aws_cpu_has_vpclmulqdq_cached(void) { + if (AWS_UNLIKELY(!s_detection_performed)) { + aws_checksums_init_detection_cache(); + } + return s_detected_vpclmulqdq; +} + +#endif /* AWS_CHECKSUMS_PRIVATE_CRC_UTIL_H */ diff --git a/contrib/restricted/aws/aws-checksums/source/arm/crc32c_arm.c b/contrib/restricted/aws/aws-checksums/source/arm/crc32c_arm.c new file mode 100644 index 00000000000..024d9cdf3d2 --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/source/arm/crc32c_arm.c @@ -0,0 +1,97 @@ +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +/* No instrics defined for 32-bit MSVC */ +#if (defined(_M_ARM64) || defined(__aarch64__) || defined(__arm__)) +# include <aws/checksums/private/crc32_priv.h> +# ifdef _M_ARM64 +# include <arm64_neon.h> +# define PREFETCH(p) __prefetch(p) +# else +# include <arm_acle.h> +# define PREFETCH(p) __builtin_prefetch(p) +# endif + +uint32_t aws_checksums_crc32c_armv8(const uint8_t *data, int length, uint32_t previous_crc32c) { + uint32_t crc = ~previous_crc32c; + + // Align data if it's not aligned + while (((uintptr_t)data & 7) && length > 0) { + crc = __crc32cb(crc, *(uint8_t *)data); + data++; + length--; + } + + while (length >= 64) { + PREFETCH(data + 384); + uint64_t *d = (uint64_t *)data; + crc = __crc32cd(crc, d[0]); + crc = __crc32cd(crc, d[1]); + crc = __crc32cd(crc, d[2]); + crc = __crc32cd(crc, d[3]); + crc = __crc32cd(crc, d[4]); + crc = __crc32cd(crc, d[5]); + crc = __crc32cd(crc, d[6]); + crc = __crc32cd(crc, d[7]); + data += 64; + length -= 64; + } + + while (length >= 8) { + crc = __crc32cd(crc, *(uint64_t *)data); + data += 8; + length -= 8; + } + + while (length > 0) { + crc = __crc32cb(crc, *(uint8_t *)data); + data++; + length--; + } + + return ~crc; +} + +uint32_t aws_checksums_crc32_armv8(const uint8_t *data, int length, uint32_t previous_crc32) { + uint32_t crc = ~previous_crc32; + + // Align data if it's not aligned + while (((uintptr_t)data & 7) && length > 0) { + crc = __crc32b(crc, *(uint8_t *)data); + data++; + length--; + } + + while (length >= 64) { + PREFETCH(data + 384); + uint64_t *d = (uint64_t *)data; + crc = __crc32d(crc, d[0]); + crc = __crc32d(crc, d[1]); + crc = __crc32d(crc, d[2]); + crc = __crc32d(crc, d[3]); + crc = __crc32d(crc, d[4]); + crc = __crc32d(crc, d[5]); + crc = __crc32d(crc, d[6]); + crc = __crc32d(crc, d[7]); + data += 64; + length -= 64; + } + + while (length >= 8) { + crc = __crc32d(crc, *(uint64_t *)data); + data += 8; + length -= 8; + } + + while (length > 0) { + crc = __crc32b(crc, *(uint8_t *)data); + data++; + length--; + } + + return ~crc; +} + +#endif diff --git a/contrib/restricted/aws/aws-checksums/source/checksums.c b/contrib/restricted/aws/aws-checksums/source/checksums.c new file mode 100644 index 00000000000..ed59853d197 --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/source/checksums.c @@ -0,0 +1,34 @@ +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/checksums/checksums.h> +#include <aws/checksums/private/crc_util.h> + +bool s_detection_performed = false; +bool s_detected_sse42 = false; +bool s_detected_avx512 = false; +bool s_detected_clmul = false; +bool s_detected_vpclmulqdq = false; + +static bool s_checksums_library_initialized = false; + +void aws_checksums_library_init(struct aws_allocator *allocator) { + if (!s_checksums_library_initialized) { + s_checksums_library_initialized = true; + + aws_common_library_init(allocator); + + aws_checksums_init_detection_cache(); + aws_checksums_crc32_init(); + aws_checksums_crc64_init(); + } +} + +void aws_checksums_library_clean_up(void) { + if (s_checksums_library_initialized) { + s_checksums_library_initialized = false; + aws_common_library_clean_up(); + } +} diff --git a/contrib/restricted/aws/aws-checksums/source/crc.c b/contrib/restricted/aws/aws-checksums/source/crc.c deleted file mode 100644 index f5d3e802fd8..00000000000 --- a/contrib/restricted/aws/aws-checksums/source/crc.c +++ /dev/null @@ -1,33 +0,0 @@ -/** - * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. - * SPDX-License-Identifier: Apache-2.0. - */ -#include <aws/checksums/crc.h> -#include <aws/checksums/private/crc_priv.h> - -#include <aws/common/cpuid.h> - -static uint32_t (*s_crc32c_fn_ptr)(const uint8_t *input, int length, uint32_t previousCrc32) = 0; -static uint32_t (*s_crc32_fn_ptr)(const uint8_t *input, int length, uint32_t previousCrc32) = 0; - -uint32_t aws_checksums_crc32(const uint8_t *input, int length, uint32_t previousCrc32) { - if (AWS_UNLIKELY(!s_crc32_fn_ptr)) { - if (aws_cpu_has_feature(AWS_CPU_FEATURE_ARM_CRC)) { - s_crc32_fn_ptr = aws_checksums_crc32_hw; - } else { - s_crc32_fn_ptr = aws_checksums_crc32_sw; - } - } - return s_crc32_fn_ptr(input, length, previousCrc32); -} - -uint32_t aws_checksums_crc32c(const uint8_t *input, int length, uint32_t previousCrc32) { - if (AWS_UNLIKELY(!s_crc32c_fn_ptr)) { - if (aws_cpu_has_feature(AWS_CPU_FEATURE_SSE_4_2) || aws_cpu_has_feature(AWS_CPU_FEATURE_ARM_CRC)) { - s_crc32c_fn_ptr = aws_checksums_crc32c_hw; - } else { - s_crc32c_fn_ptr = aws_checksums_crc32c_sw; - } - } - return s_crc32c_fn_ptr(input, length, previousCrc32); -} diff --git a/contrib/restricted/aws/aws-checksums/source/crc32.c b/contrib/restricted/aws/aws-checksums/source/crc32.c new file mode 100644 index 00000000000..387834267cb --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/source/crc32.c @@ -0,0 +1,69 @@ +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ +#include <aws/checksums/crc.h> +#include <aws/checksums/private/crc32_priv.h> +#include <aws/checksums/private/crc_util.h> + +#include <aws/common/cpuid.h> + +large_buffer_apply_impl(crc32, uint32_t) + + static uint32_t (*s_crc32c_fn_ptr)(const uint8_t *input, int length, uint32_t previous_crc32c) = NULL; +static uint32_t (*s_crc32_fn_ptr)(const uint8_t *input, int length, uint32_t previous_crc32) = NULL; + +void aws_checksums_crc32_init(void) { + if (s_crc32_fn_ptr == NULL) { +#if defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_ARM64) + if (aws_cpu_has_feature(AWS_CPU_FEATURE_ARM_CRC)) { + s_crc32_fn_ptr = aws_checksums_crc32_armv8; + } else { + s_crc32_fn_ptr = aws_checksums_crc32_sw; + } +#else + s_crc32_fn_ptr = aws_checksums_crc32_sw; +#endif + } + + if (s_crc32c_fn_ptr == NULL) { +#if defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_INTEL_X64) + if (aws_cpu_has_feature(AWS_CPU_FEATURE_SSE_4_2)) { + s_crc32c_fn_ptr = aws_checksums_crc32c_intel_avx512_with_sse_fallback; + } else { + s_crc32c_fn_ptr = aws_checksums_crc32c_sw; + } +#elif defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_ARM64) + if (aws_cpu_has_feature(AWS_CPU_FEATURE_ARM_CRC)) { + s_crc32c_fn_ptr = aws_checksums_crc32c_armv8; + } else { + s_crc32c_fn_ptr = aws_checksums_crc32c_sw; + } +#else + s_crc32c_fn_ptr = aws_checksums_crc32c_sw; +#endif + } +} + +uint32_t aws_checksums_crc32(const uint8_t *input, int length, uint32_t previous_crc32) { + if (AWS_UNLIKELY(s_crc32_fn_ptr == NULL)) { + aws_checksums_crc32_init(); + } + return s_crc32_fn_ptr(input, length, previous_crc32); +} + +uint32_t aws_checksums_crc32_ex(const uint8_t *input, size_t length, uint32_t previous_crc32) { + return aws_large_buffer_apply_crc32(aws_checksums_crc32, input, length, previous_crc32); +} + +uint32_t aws_checksums_crc32c(const uint8_t *input, int length, uint32_t previous_crc32c) { + if (AWS_UNLIKELY(s_crc32c_fn_ptr == NULL)) { + aws_checksums_crc32_init(); + } + + return s_crc32c_fn_ptr(input, length, previous_crc32c); +} + +uint32_t aws_checksums_crc32c_ex(const uint8_t *input, size_t length, uint32_t previous_crc32) { + return aws_large_buffer_apply_crc32(aws_checksums_crc32c, input, length, previous_crc32); +} diff --git a/contrib/restricted/aws/aws-checksums/source/crc64.c b/contrib/restricted/aws/aws-checksums/source/crc64.c new file mode 100644 index 00000000000..7befd9a53d9 --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/source/crc64.c @@ -0,0 +1,138 @@ +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/checksums/crc.h> +#include <aws/checksums/private/crc64_priv.h> +#include <aws/checksums/private/crc_util.h> +#include <aws/common/cpuid.h> + +large_buffer_apply_impl(crc64, uint64_t) + + AWS_ALIGNED_TYPEDEF(uint8_t, checksums_maxks_shifts_type[6][16], 16); + +// Intel PSHUFB / ARM VTBL patterns for left/right shifts and masks +checksums_maxks_shifts_type aws_checksums_masks_shifts = { + {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80}, // + {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f}, // left/right + // shifts + {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80}, // + {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}, // + {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}, // byte masks + {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}, // +}; + +AWS_ALIGNED_TYPEDEF(aws_checksums_crc64_constants_t, checksums_constants, 16); + +/* clang-format off */ + +// Pre-computed bit-reflected constants for CRC64NVME +// The actual exponents are reduced by 1 to compensate for bit-reflection (e.g. x^1024 is actually x^1023) +checksums_constants aws_checksums_crc64nvme_constants = { + .x2048 = + {0x37ccd3e14069cabc, + 0xa043808c0f782663, // x^2112 mod P(x) / x^2048 mod P(x) + 0x37ccd3e14069cabc, + 0xa043808c0f782663, // duplicated 3 times to support 64 byte avx512 loads + 0x37ccd3e14069cabc, + 0xa043808c0f782663, + 0x37ccd3e14069cabc, + 0xa043808c0f782663}, + .x1536 = + {0x758ee09da263e275, + 0x6d2d13de8038b4ca, // x^1600 mod P(x) / x^1536 mod P(x) + 0x758ee09da263e275, + 0x6d2d13de8038b4ca, // duplicated 3 times to support 64 byte avx512 loads + 0x758ee09da263e275, + 0x6d2d13de8038b4ca, + 0x758ee09da263e275, + 0x6d2d13de8038b4ca}, + .x1024 = + {0xa1ca681e733f9c40, + 0x5f852fb61e8d92dc, // x^1088 mod P(x) / x^1024 mod P(x) + 0xa1ca681e733f9c40, + 0x5f852fb61e8d92dc, // duplicated 3 times to support 64 byte avx512 loads + 0xa1ca681e733f9c40, + 0x5f852fb61e8d92dc, + 0xa1ca681e733f9c40, + 0x5f852fb61e8d92dc}, + .x512 = + {0x0c32cdb31e18a84a, + 0x62242240ace5045a, // x^576 mod P(x) / x^512 mod P(x) + 0x0c32cdb31e18a84a, + 0x62242240ace5045a, // duplicated 3 times to support 64 byte avx512 loads + 0x0c32cdb31e18a84a, + 0x62242240ace5045a, + 0x0c32cdb31e18a84a, + 0x62242240ace5045a}, + .x384 = {0xbdd7ac0ee1a4a0f0, 0xa3ffdc1fe8e82a8b}, // x^448 mod P(x) / x^384 mod P(x) + .x256 = {0xb0bc2e589204f500, 0xe1e0bb9d45d7a44c}, // x^320 mod P(x) / x^256 mod P(x) + .x128 = {0xeadc41fd2ba3d420, 0x21e9761e252621ac}, // x^192 mod P(x) / x^128 mod P(x) + .mu_poly = {0x27ecfa329aef9f77, 0x34d926535897936b}, // Barrett mu / polynomial P(x) (bit-reflected) + .trailing = + { + // trailing input constants for data lengths of 1-15 bytes + {0x04f28def5347786c, 0x7f6ef0c830358979}, // 1 trailing bytes: x^72 mod P(x) / x^8 mod P(x) + {0x49e1df807414fdef, 0x8776a97d73bddf69}, // 2 trailing bytes: x^80 mod P(x) / x^15 mod P(x) + {0x52734ea3e726fc54, 0xff6e4e1f4e4038be}, // 3 trailing bytes: x^88 mod P(x) / x^24 mod P(x) + {0x668ab3bbc976d29d, 0x8211147cbaf96306}, // 4 trailing bytes: x^96 mod P(x) / x^32 mod P(x) + {0xf2fa1fae5f5c1165, 0x373d15f784905d1e}, // 5 trailing bytes: x^104 mod P(x) / x^40 mod P(x) + {0x9065cb6e6d39918a, 0xe9742a79ef04a5d4}, // 6 trailing bytes: x^110 mod P(x) / x^48 mod P(x) + {0xc23dfbc6ca591ca3, 0xfc5d27f6bf353971}, // 7 trailing bytes: x^110 mod P(x) / x^56 mod P(x) + {0xeadc41fd2ba3d420, 0x21e9761e252621ac}, // 8 trailing bytes: x^120 mod P(x) / x^64 mod P(x) + {0xf12b2236ec577cd6, 0x04f28def5347786c}, // 9 trailing bytes: x^128 mod P(x) / x^72 mod P(x) + {0x0298996e905d785a, 0x49e1df807414fdef}, // 10 trailing bytes: x^144 mod P(x) / x^80 mod P(x) + {0xf779b03b943ff311, 0x52734ea3e726fc54}, // 11 trailing bytes: x^152 mod P(x) / x^88 mod P(x) + {0x07797643831fd90b, 0x668ab3bbc976d29d}, // 12 trailing bytes: x^160 mod P(x) / x^96 mod P(x) + {0x27a8849a7bc97a27, 0xf2fa1fae5f5c1165}, // 13 trailing bytes: x^168 mod P(x) / x^104 mod P(x) + {0xb937a2d843183b7c, 0x9065cb6e6d39918a}, // 14 trailing bytes: x^176 mod P(x) / x^112 mod P(x) + {0x31bce594cbbacd2d, 0xc23dfbc6ca591ca3}, // 15 trailing bytes: x^184 mod P(x) / x^120 mod P(x) + }, +}; +/* clang-format on */ + +static uint64_t (*s_crc64nvme_fn_ptr)(const uint8_t *input, int length, uint64_t prev_crc64) = NULL; + +void aws_checksums_crc64_init(void) { + if (s_crc64nvme_fn_ptr == NULL) { +#if defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_INTEL_X64) && !(defined(_MSC_VER) && _MSC_VER < 1920) +# if defined(AWS_HAVE_AVX512_INTRINSICS) + if (aws_cpu_has_feature(AWS_CPU_FEATURE_AVX512) && aws_cpu_has_feature(AWS_CPU_FEATURE_VPCLMULQDQ)) { + s_crc64nvme_fn_ptr = aws_checksums_crc64nvme_intel_avx512; + } else +# endif +# if defined(AWS_HAVE_CLMUL) && defined(AWS_HAVE_AVX2_INTRINSICS) + if (aws_cpu_has_feature(AWS_CPU_FEATURE_CLMUL) && aws_cpu_has_feature(AWS_CPU_FEATURE_AVX2)) { + s_crc64nvme_fn_ptr = aws_checksums_crc64nvme_intel_clmul; + } else { + s_crc64nvme_fn_ptr = aws_checksums_crc64nvme_sw; + } +# endif +# if !(defined(AWS_HAVE_AVX512_INTRINSICS) || (defined(AWS_HAVE_CLMUL) && defined(AWS_HAVE_AVX2_INTRINSICS))) + s_crc64nvme_fn_ptr = aws_checksums_crc64nvme_sw; +# endif + +#elif defined(AWS_USE_CPU_EXTENSIONS) && defined(AWS_ARCH_ARM64) && defined(AWS_HAVE_ARMv8_1) + if (aws_cpu_has_feature(AWS_CPU_FEATURE_ARM_CRYPTO) && aws_cpu_has_feature(AWS_CPU_FEATURE_ARM_PMULL)) { + s_crc64nvme_fn_ptr = aws_checksums_crc64nvme_arm_pmull; + } else { + s_crc64nvme_fn_ptr = aws_checksums_crc64nvme_sw; + } +#else // this branch being taken means it's not arm64 and not intel with avx extensions + s_crc64nvme_fn_ptr = aws_checksums_crc64nvme_sw; +#endif + } +} + +uint64_t aws_checksums_crc64nvme(const uint8_t *input, int length, uint64_t prev_crc64) { + if (AWS_UNLIKELY(s_crc64nvme_fn_ptr == NULL)) { + aws_checksums_crc64_init(); + } + + return s_crc64nvme_fn_ptr(input, length, prev_crc64); +} + +uint64_t aws_checksums_crc64nvme_ex(const uint8_t *input, size_t length, uint64_t previous_crc64) { + return aws_large_buffer_apply_crc64(aws_checksums_crc64nvme, input, length, previous_crc64); +} diff --git a/contrib/restricted/aws/aws-checksums/source/crc64_sw.c b/contrib/restricted/aws/aws-checksums/source/crc64_sw.c new file mode 100644 index 00000000000..56c65ceba1c --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/source/crc64_sw.c @@ -0,0 +1,1143 @@ +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/checksums/crc.h> +#include <aws/checksums/private/crc64_priv.h> +#include <aws/checksums/private/crc_util.h> + +/* CRC64NVME slice-by-8 lookup table (bit-reflected poly 0x9a6c9329ac4bc9b5) */ +/* little endian variant */ +static uint64_t crc64nvme_table_le[8][256] = { + // + { + 0x0000000000000000, 0x7f6ef0c830358979, 0xfedde190606b12f2, 0x81b31158505e9b8b, // [0][0x00] + 0xc962e5739841b68f, 0xb60c15bba8743ff6, 0x37bf04e3f82aa47d, 0x48d1f42bc81f2d04, // [0][0x04] + 0xa61cecb46814fe75, 0xd9721c7c5821770c, 0x58c10d24087fec87, 0x27affdec384a65fe, // [0][0x08] + 0x6f7e09c7f05548fa, 0x1010f90fc060c183, 0x91a3e857903e5a08, 0xeecd189fa00bd371, // [0][0x0c] + 0x78e0ff3b88be6f81, 0x078e0ff3b88be6f8, 0x863d1eabe8d57d73, 0xf953ee63d8e0f40a, // [0][0x10] + 0xb1821a4810ffd90e, 0xceecea8020ca5077, 0x4f5ffbd87094cbfc, 0x30310b1040a14285, // [0][0x14] + 0xdefc138fe0aa91f4, 0xa192e347d09f188d, 0x2021f21f80c18306, 0x5f4f02d7b0f40a7f, // [0][0x18] + 0x179ef6fc78eb277b, 0x68f0063448deae02, 0xe943176c18803589, 0x962de7a428b5bcf0, // [0][0x1c] + 0xf1c1fe77117cdf02, 0x8eaf0ebf2149567b, 0x0f1c1fe77117cdf0, 0x7072ef2f41224489, // [0][0x20] + 0x38a31b04893d698d, 0x47cdebccb908e0f4, 0xc67efa94e9567b7f, 0xb9100a5cd963f206, // [0][0x24] + 0x57dd12c379682177, 0x28b3e20b495da80e, 0xa900f35319033385, 0xd66e039b2936bafc, // [0][0x28] + 0x9ebff7b0e12997f8, 0xe1d10778d11c1e81, 0x606216208142850a, 0x1f0ce6e8b1770c73, // [0][0x2c] + 0x8921014c99c2b083, 0xf64ff184a9f739fa, 0x77fce0dcf9a9a271, 0x08921014c99c2b08, // [0][0x30] + 0x4043e43f0183060c, 0x3f2d14f731b68f75, 0xbe9e05af61e814fe, 0xc1f0f56751dd9d87, // [0][0x34] + 0x2f3dedf8f1d64ef6, 0x50531d30c1e3c78f, 0xd1e00c6891bd5c04, 0xae8efca0a188d57d, // [0][0x38] + 0xe65f088b6997f879, 0x9931f84359a27100, 0x1882e91b09fcea8b, 0x67ec19d339c963f2, // [0][0x3c] + 0xd75adabd7a6e2d6f, 0xa8342a754a5ba416, 0x29873b2d1a053f9d, 0x56e9cbe52a30b6e4, // [0][0x40] + 0x1e383fcee22f9be0, 0x6156cf06d21a1299, 0xe0e5de5e82448912, 0x9f8b2e96b271006b, // [0][0x44] + 0x71463609127ad31a, 0x0e28c6c1224f5a63, 0x8f9bd7997211c1e8, 0xf0f5275142244891, // [0][0x48] + 0xb824d37a8a3b6595, 0xc74a23b2ba0eecec, 0x46f932eaea507767, 0x3997c222da65fe1e, // [0][0x4c] + 0xafba2586f2d042ee, 0xd0d4d54ec2e5cb97, 0x5167c41692bb501c, 0x2e0934dea28ed965, // [0][0x50] + 0x66d8c0f56a91f461, 0x19b6303d5aa47d18, 0x980521650afae693, 0xe76bd1ad3acf6fea, // [0][0x54] + 0x09a6c9329ac4bc9b, 0x76c839faaaf135e2, 0xf77b28a2faafae69, 0x8815d86aca9a2710, // [0][0x58] + 0xc0c42c4102850a14, 0xbfaadc8932b0836d, 0x3e19cdd162ee18e6, 0x41773d1952db919f, // [0][0x5c] + 0x269b24ca6b12f26d, 0x59f5d4025b277b14, 0xd846c55a0b79e09f, 0xa72835923b4c69e6, // [0][0x60] + 0xeff9c1b9f35344e2, 0x90973171c366cd9b, 0x1124202993385610, 0x6e4ad0e1a30ddf69, // [0][0x64] + 0x8087c87e03060c18, 0xffe938b633338561, 0x7e5a29ee636d1eea, 0x0134d92653589793, // [0][0x68] + 0x49e52d0d9b47ba97, 0x368bddc5ab7233ee, 0xb738cc9dfb2ca865, 0xc8563c55cb19211c, // [0][0x6c] + 0x5e7bdbf1e3ac9dec, 0x21152b39d3991495, 0xa0a63a6183c78f1e, 0xdfc8caa9b3f20667, // [0][0x70] + 0x97193e827bed2b63, 0xe877ce4a4bd8a21a, 0x69c4df121b863991, 0x16aa2fda2bb3b0e8, // [0][0x74] + 0xf86737458bb86399, 0x8709c78dbb8deae0, 0x06bad6d5ebd3716b, 0x79d4261ddbe6f812, // [0][0x78] + 0x3105d23613f9d516, 0x4e6b22fe23cc5c6f, 0xcfd833a67392c7e4, 0xb0b6c36e43a74e9d, // [0][0x7c] + 0x9a6c9329ac4bc9b5, 0xe50263e19c7e40cc, 0x64b172b9cc20db47, 0x1bdf8271fc15523e, // [0][0x80] + 0x530e765a340a7f3a, 0x2c608692043ff643, 0xadd397ca54616dc8, 0xd2bd67026454e4b1, // [0][0x84] + 0x3c707f9dc45f37c0, 0x431e8f55f46abeb9, 0xc2ad9e0da4342532, 0xbdc36ec59401ac4b, // [0][0x88] + 0xf5129aee5c1e814f, 0x8a7c6a266c2b0836, 0x0bcf7b7e3c7593bd, 0x74a18bb60c401ac4, // [0][0x8c] + 0xe28c6c1224f5a634, 0x9de29cda14c02f4d, 0x1c518d82449eb4c6, 0x633f7d4a74ab3dbf, // [0][0x90] + 0x2bee8961bcb410bb, 0x548079a98c8199c2, 0xd53368f1dcdf0249, 0xaa5d9839ecea8b30, // [0][0x94] + 0x449080a64ce15841, 0x3bfe706e7cd4d138, 0xba4d61362c8a4ab3, 0xc52391fe1cbfc3ca, // [0][0x98] + 0x8df265d5d4a0eece, 0xf29c951de49567b7, 0x732f8445b4cbfc3c, 0x0c41748d84fe7545, // [0][0x9c] + 0x6bad6d5ebd3716b7, 0x14c39d968d029fce, 0x95708ccedd5c0445, 0xea1e7c06ed698d3c, // [0][0xa0] + 0xa2cf882d2576a038, 0xdda178e515432941, 0x5c1269bd451db2ca, 0x237c997575283bb3, // [0][0xa4] + 0xcdb181ead523e8c2, 0xb2df7122e51661bb, 0x336c607ab548fa30, 0x4c0290b2857d7349, // [0][0xa8] + 0x04d364994d625e4d, 0x7bbd94517d57d734, 0xfa0e85092d094cbf, 0x856075c11d3cc5c6, // [0][0xac] + 0x134d926535897936, 0x6c2362ad05bcf04f, 0xed9073f555e26bc4, 0x92fe833d65d7e2bd, // [0][0xb0] + 0xda2f7716adc8cfb9, 0xa54187de9dfd46c0, 0x24f29686cda3dd4b, 0x5b9c664efd965432, // [0][0xb4] + 0xb5517ed15d9d8743, 0xca3f8e196da80e3a, 0x4b8c9f413df695b1, 0x34e26f890dc31cc8, // [0][0xb8] + 0x7c339ba2c5dc31cc, 0x035d6b6af5e9b8b5, 0x82ee7a32a5b7233e, 0xfd808afa9582aa47, // [0][0xbc] + 0x4d364994d625e4da, 0x3258b95ce6106da3, 0xb3eba804b64ef628, 0xcc8558cc867b7f51, // [0][0xc0] + 0x8454ace74e645255, 0xfb3a5c2f7e51db2c, 0x7a894d772e0f40a7, 0x05e7bdbf1e3ac9de, // [0][0xc4] + 0xeb2aa520be311aaf, 0x944455e88e0493d6, 0x15f744b0de5a085d, 0x6a99b478ee6f8124, // [0][0xc8] + 0x224840532670ac20, 0x5d26b09b16452559, 0xdc95a1c3461bbed2, 0xa3fb510b762e37ab, // [0][0xcc] + 0x35d6b6af5e9b8b5b, 0x4ab846676eae0222, 0xcb0b573f3ef099a9, 0xb465a7f70ec510d0, // [0][0xd0] + 0xfcb453dcc6da3dd4, 0x83daa314f6efb4ad, 0x0269b24ca6b12f26, 0x7d0742849684a65f, // [0][0xd4] + 0x93ca5a1b368f752e, 0xeca4aad306bafc57, 0x6d17bb8b56e467dc, 0x12794b4366d1eea5, // [0][0xd8] + 0x5aa8bf68aecec3a1, 0x25c64fa09efb4ad8, 0xa4755ef8cea5d153, 0xdb1bae30fe90582a, // [0][0xdc] + 0xbcf7b7e3c7593bd8, 0xc399472bf76cb2a1, 0x422a5673a732292a, 0x3d44a6bb9707a053, // [0][0xe0] + 0x759552905f188d57, 0x0afba2586f2d042e, 0x8b48b3003f739fa5, 0xf42643c80f4616dc, // [0][0xe4] + 0x1aeb5b57af4dc5ad, 0x6585ab9f9f784cd4, 0xe436bac7cf26d75f, 0x9b584a0fff135e26, // [0][0xe8] + 0xd389be24370c7322, 0xace74eec0739fa5b, 0x2d545fb4576761d0, 0x523aaf7c6752e8a9, // [0][0xec] + 0xc41748d84fe75459, 0xbb79b8107fd2dd20, 0x3acaa9482f8c46ab, 0x45a459801fb9cfd2, // [0][0xf0] + 0x0d75adabd7a6e2d6, 0x721b5d63e7936baf, 0xf3a84c3bb7cdf024, 0x8cc6bcf387f8795d, // [0][0xf4] + 0x620ba46c27f3aa2c, 0x1d6554a417c62355, 0x9cd645fc4798b8de, 0xe3b8b53477ad31a7, // [0][0xf8] + 0xab69411fbfb21ca3, 0xd407b1d78f8795da, 0x55b4a08fdfd90e51, 0x2ada5047efec8728 // [0][0xfc] + }, + { + 0x0000000000000000, 0x8776a97d73bddf69, 0x3a3474a9bfec2db9, 0xbd42ddd4cc51f2d0, // [1][0x00] + 0x7468e9537fd85b72, 0xf31e402e0c65841b, 0x4e5c9dfac03476cb, 0xc92a3487b389a9a2, // [1][0x04] + 0xe8d1d2a6ffb0b6e4, 0x6fa77bdb8c0d698d, 0xd2e5a60f405c9b5d, 0x55930f7233e14434, // [1][0x08] + 0x9cb93bf58068ed96, 0x1bcf9288f3d532ff, 0xa68d4f5c3f84c02f, 0x21fbe6214c391f46, // [1][0x0c] + 0xe57a831ea7f6fea3, 0x620c2a63d44b21ca, 0xdf4ef7b7181ad31a, 0x58385eca6ba70c73, // [1][0x10] + 0x91126a4dd82ea5d1, 0x1664c330ab937ab8, 0xab261ee467c28868, 0x2c50b799147f5701, // [1][0x14] + 0x0dab51b858464847, 0x8addf8c52bfb972e, 0x379f2511e7aa65fe, 0xb0e98c6c9417ba97, // [1][0x18] + 0x79c3b8eb279e1335, 0xfeb511965423cc5c, 0x43f7cc4298723e8c, 0xc481653febcfe1e5, // [1][0x1c] + 0xfe2c206e177a6e2d, 0x795a891364c7b144, 0xc41854c7a8964394, 0x436efdbadb2b9cfd, // [1][0x20] + 0x8a44c93d68a2355f, 0x0d3260401b1fea36, 0xb070bd94d74e18e6, 0x370614e9a4f3c78f, // [1][0x24] + 0x16fdf2c8e8cad8c9, 0x918b5bb59b7707a0, 0x2cc986615726f570, 0xabbf2f1c249b2a19, // [1][0x28] + 0x62951b9b971283bb, 0xe5e3b2e6e4af5cd2, 0x58a16f3228feae02, 0xdfd7c64f5b43716b, // [1][0x2c] + 0x1b56a370b08c908e, 0x9c200a0dc3314fe7, 0x2162d7d90f60bd37, 0xa6147ea47cdd625e, // [1][0x30] + 0x6f3e4a23cf54cbfc, 0xe848e35ebce91495, 0x550a3e8a70b8e645, 0xd27c97f70305392c, // [1][0x34] + 0xf38771d64f3c266a, 0x74f1d8ab3c81f903, 0xc9b3057ff0d00bd3, 0x4ec5ac02836dd4ba, // [1][0x38] + 0x87ef988530e47d18, 0x009931f84359a271, 0xbddbec2c8f0850a1, 0x3aad4551fcb58fc8, // [1][0x3c] + 0xc881668f76634f31, 0x4ff7cff205de9058, 0xf2b51226c98f6288, 0x75c3bb5bba32bde1, // [1][0x40] + 0xbce98fdc09bb1443, 0x3b9f26a17a06cb2a, 0x86ddfb75b65739fa, 0x01ab5208c5eae693, // [1][0x44] + 0x2050b42989d3f9d5, 0xa7261d54fa6e26bc, 0x1a64c080363fd46c, 0x9d1269fd45820b05, // [1][0x48] + 0x54385d7af60ba2a7, 0xd34ef40785b67dce, 0x6e0c29d349e78f1e, 0xe97a80ae3a5a5077, // [1][0x4c] + 0x2dfbe591d195b192, 0xaa8d4ceca2286efb, 0x17cf91386e799c2b, 0x90b938451dc44342, // [1][0x50] + 0x59930cc2ae4deae0, 0xdee5a5bfddf03589, 0x63a7786b11a1c759, 0xe4d1d116621c1830, // [1][0x54] + 0xc52a37372e250776, 0x425c9e4a5d98d81f, 0xff1e439e91c92acf, 0x7868eae3e274f5a6, // [1][0x58] + 0xb142de6451fd5c04, 0x363477192240836d, 0x8b76aacdee1171bd, 0x0c0003b09dacaed4, // [1][0x5c] + 0x36ad46e16119211c, 0xb1dbef9c12a4fe75, 0x0c993248def50ca5, 0x8bef9b35ad48d3cc, // [1][0x60] + 0x42c5afb21ec17a6e, 0xc5b306cf6d7ca507, 0x78f1db1ba12d57d7, 0xff877266d29088be, // [1][0x64] + 0xde7c94479ea997f8, 0x590a3d3aed144891, 0xe448e0ee2145ba41, 0x633e499352f86528, // [1][0x68] + 0xaa147d14e171cc8a, 0x2d62d46992cc13e3, 0x902009bd5e9de133, 0x1756a0c02d203e5a, // [1][0x6c] + 0xd3d7c5ffc6efdfbf, 0x54a16c82b55200d6, 0xe9e3b1567903f206, 0x6e95182b0abe2d6f, // [1][0x70] + 0xa7bf2cacb93784cd, 0x20c985d1ca8a5ba4, 0x9d8b580506dba974, 0x1afdf1787566761d, // [1][0x74] + 0x3b061759395f695b, 0xbc70be244ae2b632, 0x013263f086b344e2, 0x8644ca8df50e9b8b, // [1][0x78] + 0x4f6efe0a46873229, 0xc8185777353aed40, 0x755a8aa3f96b1f90, 0xf22c23de8ad6c0f9, // [1][0x7c] + 0xa5dbeb4db4510d09, 0x22ad4230c7ecd260, 0x9fef9fe40bbd20b0, 0x189936997800ffd9, // [1][0x80] + 0xd1b3021ecb89567b, 0x56c5ab63b8348912, 0xeb8776b774657bc2, 0x6cf1dfca07d8a4ab, // [1][0x84] + 0x4d0a39eb4be1bbed, 0xca7c9096385c6484, 0x773e4d42f40d9654, 0xf048e43f87b0493d, // [1][0x88] + 0x3962d0b83439e09f, 0xbe1479c547843ff6, 0x0356a4118bd5cd26, 0x84200d6cf868124f, // [1][0x8c] + 0x40a1685313a7f3aa, 0xc7d7c12e601a2cc3, 0x7a951cfaac4bde13, 0xfde3b587dff6017a, // [1][0x90] + 0x34c981006c7fa8d8, 0xb3bf287d1fc277b1, 0x0efdf5a9d3938561, 0x898b5cd4a02e5a08, // [1][0x94] + 0xa870baf5ec17454e, 0x2f0613889faa9a27, 0x9244ce5c53fb68f7, 0x153267212046b79e, // [1][0x98] + 0xdc1853a693cf1e3c, 0x5b6efadbe072c155, 0xe62c270f2c233385, 0x615a8e725f9eecec, // [1][0x9c] + 0x5bf7cb23a32b6324, 0xdc81625ed096bc4d, 0x61c3bf8a1cc74e9d, 0xe6b516f76f7a91f4, // [1][0xa0] + 0x2f9f2270dcf33856, 0xa8e98b0daf4ee73f, 0x15ab56d9631f15ef, 0x92ddffa410a2ca86, // [1][0xa4] + 0xb32619855c9bd5c0, 0x3450b0f82f260aa9, 0x89126d2ce377f879, 0x0e64c45190ca2710, // [1][0xa8] + 0xc74ef0d623438eb2, 0x403859ab50fe51db, 0xfd7a847f9cafa30b, 0x7a0c2d02ef127c62, // [1][0xac] + 0xbe8d483d04dd9d87, 0x39fbe140776042ee, 0x84b93c94bb31b03e, 0x03cf95e9c88c6f57, // [1][0xb0] + 0xcae5a16e7b05c6f5, 0x4d93081308b8199c, 0xf0d1d5c7c4e9eb4c, 0x77a77cbab7543425, // [1][0xb4] + 0x565c9a9bfb6d2b63, 0xd12a33e688d0f40a, 0x6c68ee32448106da, 0xeb1e474f373cd9b3, // [1][0xb8] + 0x223473c884b57011, 0xa542dab5f708af78, 0x180007613b595da8, 0x9f76ae1c48e482c1, // [1][0xbc] + 0x6d5a8dc2c2324238, 0xea2c24bfb18f9d51, 0x576ef96b7dde6f81, 0xd01850160e63b0e8, // [1][0xc0] + 0x19326491bdea194a, 0x9e44cdecce57c623, 0x23061038020634f3, 0xa470b94571bbeb9a, // [1][0xc4] + 0x858b5f643d82f4dc, 0x02fdf6194e3f2bb5, 0xbfbf2bcd826ed965, 0x38c982b0f1d3060c, // [1][0xc8] + 0xf1e3b637425aafae, 0x76951f4a31e770c7, 0xcbd7c29efdb68217, 0x4ca16be38e0b5d7e, // [1][0xcc] + 0x88200edc65c4bc9b, 0x0f56a7a1167963f2, 0xb2147a75da289122, 0x3562d308a9954e4b, // [1][0xd0] + 0xfc48e78f1a1ce7e9, 0x7b3e4ef269a13880, 0xc67c9326a5f0ca50, 0x410a3a5bd64d1539, // [1][0xd4] + 0x60f1dc7a9a740a7f, 0xe7877507e9c9d516, 0x5ac5a8d3259827c6, 0xddb301ae5625f8af, // [1][0xd8] + 0x14993529e5ac510d, 0x93ef9c5496118e64, 0x2ead41805a407cb4, 0xa9dbe8fd29fda3dd, // [1][0xdc] + 0x9376adacd5482c15, 0x140004d1a6f5f37c, 0xa942d9056aa401ac, 0x2e3470781919dec5, // [1][0xe0] + 0xe71e44ffaa907767, 0x6068ed82d92da80e, 0xdd2a3056157c5ade, 0x5a5c992b66c185b7, // [1][0xe4] + 0x7ba77f0a2af89af1, 0xfcd1d67759454598, 0x41930ba39514b748, 0xc6e5a2dee6a96821, // [1][0xe8] + 0x0fcf96595520c183, 0x88b93f24269d1eea, 0x35fbe2f0eaccec3a, 0xb28d4b8d99713353, // [1][0xec] + 0x760c2eb272bed2b6, 0xf17a87cf01030ddf, 0x4c385a1bcd52ff0f, 0xcb4ef366beef2066, // [1][0xf0] + 0x0264c7e10d6689c4, 0x85126e9c7edb56ad, 0x3850b348b28aa47d, 0xbf261a35c1377b14, // [1][0xf4] + 0x9eddfc148d0e6452, 0x19ab5569feb3bb3b, 0xa4e988bd32e249eb, 0x239f21c0415f9682, // [1][0xf8] + 0xeab51547f2d63f20, 0x6dc3bc3a816be049, 0xd08161ee4d3a1299, 0x57f7c8933e87cdf0 // [1][0xfc] + }, + { + 0x0000000000000000, 0xff6e4e1f4e4038be, 0xca05ba6dc417e217, 0x356bf4728a57daa9, // [2][0x00] + 0xa0d25288d0b85745, 0x5fbc1c979ef86ffb, 0x6ad7e8e514afb552, 0x95b9a6fa5aef8dec, // [2][0x04] + 0x757d8342f9e73de1, 0x8a13cd5db7a7055f, 0xbf78392f3df0dff6, 0x4016773073b0e748, // [2][0x08] + 0xd5afd1ca295f6aa4, 0x2ac19fd5671f521a, 0x1faa6ba7ed4888b3, 0xe0c425b8a308b00d, // [2][0x0c] + 0xeafb0685f3ce7bc2, 0x1595489abd8e437c, 0x20febce837d999d5, 0xdf90f2f77999a16b, // [2][0x10] + 0x4a29540d23762c87, 0xb5471a126d361439, 0x802cee60e761ce90, 0x7f42a07fa921f62e, // [2][0x14] + 0x9f8685c70a294623, 0x60e8cbd844697e9d, 0x55833faace3ea434, 0xaaed71b5807e9c8a, // [2][0x18] + 0x3f54d74fda911166, 0xc03a995094d129d8, 0xf5516d221e86f371, 0x0a3f233d50c6cbcf, // [2][0x1c] + 0xe12f2b58bf0b64ef, 0x1e416547f14b5c51, 0x2b2a91357b1c86f8, 0xd444df2a355cbe46, // [2][0x20] + 0x41fd79d06fb333aa, 0xbe9337cf21f30b14, 0x8bf8c3bdaba4d1bd, 0x74968da2e5e4e903, // [2][0x24] + 0x9452a81a46ec590e, 0x6b3ce60508ac61b0, 0x5e57127782fbbb19, 0xa1395c68ccbb83a7, // [2][0x28] + 0x3480fa9296540e4b, 0xcbeeb48dd81436f5, 0xfe8540ff5243ec5c, 0x01eb0ee01c03d4e2, // [2][0x2c] + 0x0bd42ddd4cc51f2d, 0xf4ba63c202852793, 0xc1d197b088d2fd3a, 0x3ebfd9afc692c584, // [2][0x30] + 0xab067f559c7d4868, 0x5468314ad23d70d6, 0x6103c538586aaa7f, 0x9e6d8b27162a92c1, // [2][0x34] + 0x7ea9ae9fb52222cc, 0x81c7e080fb621a72, 0xb4ac14f27135c0db, 0x4bc25aed3f75f865, // [2][0x38] + 0xde7bfc17659a7589, 0x2115b2082bda4d37, 0x147e467aa18d979e, 0xeb100865efcdaf20, // [2][0x3c] + 0xf68770e226815ab5, 0x09e93efd68c1620b, 0x3c82ca8fe296b8a2, 0xc3ec8490acd6801c, // [2][0x40] + 0x5655226af6390df0, 0xa93b6c75b879354e, 0x9c509807322eefe7, 0x633ed6187c6ed759, // [2][0x44] + 0x83faf3a0df666754, 0x7c94bdbf91265fea, 0x49ff49cd1b718543, 0xb69107d25531bdfd, // [2][0x48] + 0x2328a1280fde3011, 0xdc46ef37419e08af, 0xe92d1b45cbc9d206, 0x1643555a8589eab8, // [2][0x4c] + 0x1c7c7667d54f2177, 0xe31238789b0f19c9, 0xd679cc0a1158c360, 0x291782155f18fbde, // [2][0x50] + 0xbcae24ef05f77632, 0x43c06af04bb74e8c, 0x76ab9e82c1e09425, 0x89c5d09d8fa0ac9b, // [2][0x54] + 0x6901f5252ca81c96, 0x966fbb3a62e82428, 0xa3044f48e8bffe81, 0x5c6a0157a6ffc63f, // [2][0x58] + 0xc9d3a7adfc104bd3, 0x36bde9b2b250736d, 0x03d61dc03807a9c4, 0xfcb853df7647917a, // [2][0x5c] + 0x17a85bba998a3e5a, 0xe8c615a5d7ca06e4, 0xddade1d75d9ddc4d, 0x22c3afc813dde4f3, // [2][0x60] + 0xb77a09324932691f, 0x4814472d077251a1, 0x7d7fb35f8d258b08, 0x8211fd40c365b3b6, // [2][0x64] + 0x62d5d8f8606d03bb, 0x9dbb96e72e2d3b05, 0xa8d06295a47ae1ac, 0x57be2c8aea3ad912, // [2][0x68] + 0xc2078a70b0d554fe, 0x3d69c46ffe956c40, 0x0802301d74c2b6e9, 0xf76c7e023a828e57, // [2][0x6c] + 0xfd535d3f6a444598, 0x023d132024047d26, 0x3756e752ae53a78f, 0xc838a94de0139f31, // [2][0x70] + 0x5d810fb7bafc12dd, 0xa2ef41a8f4bc2a63, 0x9784b5da7eebf0ca, 0x68eafbc530abc874, // [2][0x74] + 0x882ede7d93a37879, 0x77409062dde340c7, 0x422b641057b49a6e, 0xbd452a0f19f4a2d0, // [2][0x78] + 0x28fc8cf5431b2f3c, 0xd792c2ea0d5b1782, 0xe2f93698870ccd2b, 0x1d977887c94cf595, // [2][0x7c] + 0xd9d7c79715952601, 0x26b989885bd51ebf, 0x13d27dfad182c416, 0xecbc33e59fc2fca8, // [2][0x80] + 0x7905951fc52d7144, 0x866bdb008b6d49fa, 0xb3002f72013a9353, 0x4c6e616d4f7aabed, // [2][0x84] + 0xacaa44d5ec721be0, 0x53c40acaa232235e, 0x66affeb82865f9f7, 0x99c1b0a76625c149, // [2][0x88] + 0x0c78165d3cca4ca5, 0xf3165842728a741b, 0xc67dac30f8ddaeb2, 0x3913e22fb69d960c, // [2][0x8c] + 0x332cc112e65b5dc3, 0xcc428f0da81b657d, 0xf9297b7f224cbfd4, 0x064735606c0c876a, // [2][0x90] + 0x93fe939a36e30a86, 0x6c90dd8578a33238, 0x59fb29f7f2f4e891, 0xa69567e8bcb4d02f, // [2][0x94] + 0x465142501fbc6022, 0xb93f0c4f51fc589c, 0x8c54f83ddbab8235, 0x733ab62295ebba8b, // [2][0x98] + 0xe68310d8cf043767, 0x19ed5ec781440fd9, 0x2c86aab50b13d570, 0xd3e8e4aa4553edce, // [2][0x9c] + 0x38f8eccfaa9e42ee, 0xc796a2d0e4de7a50, 0xf2fd56a26e89a0f9, 0x0d9318bd20c99847, // [2][0xa0] + 0x982abe477a2615ab, 0x6744f05834662d15, 0x522f042abe31f7bc, 0xad414a35f071cf02, // [2][0xa4] + 0x4d856f8d53797f0f, 0xb2eb21921d3947b1, 0x8780d5e0976e9d18, 0x78ee9bffd92ea5a6, // [2][0xa8] + 0xed573d0583c1284a, 0x1239731acd8110f4, 0x2752876847d6ca5d, 0xd83cc9770996f2e3, // [2][0xac] + 0xd203ea4a5950392c, 0x2d6da45517100192, 0x180650279d47db3b, 0xe7681e38d307e385, // [2][0xb0] + 0x72d1b8c289e86e69, 0x8dbff6ddc7a856d7, 0xb8d402af4dff8c7e, 0x47ba4cb003bfb4c0, // [2][0xb4] + 0xa77e6908a0b704cd, 0x58102717eef73c73, 0x6d7bd36564a0e6da, 0x92159d7a2ae0de64, // [2][0xb8] + 0x07ac3b80700f5388, 0xf8c2759f3e4f6b36, 0xcda981edb418b19f, 0x32c7cff2fa588921, // [2][0xbc] + 0x2f50b77533147cb4, 0xd03ef96a7d54440a, 0xe5550d18f7039ea3, 0x1a3b4307b943a61d, // [2][0xc0] + 0x8f82e5fde3ac2bf1, 0x70ecabe2adec134f, 0x45875f9027bbc9e6, 0xbae9118f69fbf158, // [2][0xc4] + 0x5a2d3437caf34155, 0xa5437a2884b379eb, 0x90288e5a0ee4a342, 0x6f46c04540a49bfc, // [2][0xc8] + 0xfaff66bf1a4b1610, 0x059128a0540b2eae, 0x30fadcd2de5cf407, 0xcf9492cd901cccb9, // [2][0xcc] + 0xc5abb1f0c0da0776, 0x3ac5ffef8e9a3fc8, 0x0fae0b9d04cde561, 0xf0c045824a8ddddf, // [2][0xd0] + 0x6579e37810625033, 0x9a17ad675e22688d, 0xaf7c5915d475b224, 0x5012170a9a358a9a, // [2][0xd4] + 0xb0d632b2393d3a97, 0x4fb87cad777d0229, 0x7ad388dffd2ad880, 0x85bdc6c0b36ae03e, // [2][0xd8] + 0x1004603ae9856dd2, 0xef6a2e25a7c5556c, 0xda01da572d928fc5, 0x256f944863d2b77b, // [2][0xdc] + 0xce7f9c2d8c1f185b, 0x3111d232c25f20e5, 0x047a26404808fa4c, 0xfb14685f0648c2f2, // [2][0xe0] + 0x6eadcea55ca74f1e, 0x91c380ba12e777a0, 0xa4a874c898b0ad09, 0x5bc63ad7d6f095b7, // [2][0xe4] + 0xbb021f6f75f825ba, 0x446c51703bb81d04, 0x7107a502b1efc7ad, 0x8e69eb1dffafff13, // [2][0xe8] + 0x1bd04de7a54072ff, 0xe4be03f8eb004a41, 0xd1d5f78a615790e8, 0x2ebbb9952f17a856, // [2][0xec] + 0x24849aa87fd16399, 0xdbead4b731915b27, 0xee8120c5bbc6818e, 0x11ef6edaf586b930, // [2][0xf0] + 0x8456c820af6934dc, 0x7b38863fe1290c62, 0x4e53724d6b7ed6cb, 0xb13d3c52253eee75, // [2][0xf4] + 0x51f919ea86365e78, 0xae9757f5c87666c6, 0x9bfca3874221bc6f, 0x6492ed980c6184d1, // [2][0xf8] + 0xf12b4b62568e093d, 0x0e45057d18ce3183, 0x3b2ef10f9299eb2a, 0xc440bf10dcd9d394 // [2][0xfc] + }, + { + 0x0000000000000000, 0x8211147cbaf96306, 0x30fb0eaa2d655567, 0xb2ea1ad6979c3661, // [3][0x00] + 0x61f61d545acaaace, 0xe3e70928e033c9c8, 0x510d13fe77afffa9, 0xd31c0782cd569caf, // [3][0x04] + 0xc3ec3aa8b595559c, 0x41fd2ed40f6c369a, 0xf317340298f000fb, 0x7106207e220963fd, // [3][0x08] + 0xa21a27fcef5fff52, 0x200b338055a69c54, 0x92e12956c23aaa35, 0x10f03d2a78c3c933, // [3][0x0c] + 0xb301530233bd3853, 0x3110477e89445b55, 0x83fa5da81ed86d34, 0x01eb49d4a4210e32, // [3][0x10] + 0xd2f74e566977929d, 0x50e65a2ad38ef19b, 0xe20c40fc4412c7fa, 0x601d5480feeba4fc, // [3][0x14] + 0x70ed69aa86286dcf, 0xf2fc7dd63cd10ec9, 0x40166700ab4d38a8, 0xc207737c11b45bae, // [3][0x18] + 0x111b74fedce2c701, 0x930a6082661ba407, 0x21e07a54f1879266, 0xa3f16e284b7ef160, // [3][0x1c] + 0x52db80573fede3cd, 0xd0ca942b851480cb, 0x62208efd1288b6aa, 0xe0319a81a871d5ac, // [3][0x20] + 0x332d9d0365274903, 0xb13c897fdfde2a05, 0x03d693a948421c64, 0x81c787d5f2bb7f62, // [3][0x24] + 0x9137baff8a78b651, 0x1326ae833081d557, 0xa1ccb455a71de336, 0x23dda0291de48030, // [3][0x28] + 0xf0c1a7abd0b21c9f, 0x72d0b3d76a4b7f99, 0xc03aa901fdd749f8, 0x422bbd7d472e2afe, // [3][0x2c] + 0xe1dad3550c50db9e, 0x63cbc729b6a9b898, 0xd121ddff21358ef9, 0x5330c9839bccedff, // [3][0x30] + 0x802cce01569a7150, 0x023dda7dec631256, 0xb0d7c0ab7bff2437, 0x32c6d4d7c1064731, // [3][0x34] + 0x2236e9fdb9c58e02, 0xa027fd81033ced04, 0x12cde75794a0db65, 0x90dcf32b2e59b863, // [3][0x38] + 0x43c0f4a9e30f24cc, 0xc1d1e0d559f647ca, 0x733bfa03ce6a71ab, 0xf12aee7f749312ad, // [3][0x3c] + 0xa5b700ae7fdbc79a, 0x27a614d2c522a49c, 0x954c0e0452be92fd, 0x175d1a78e847f1fb, // [3][0x40] + 0xc4411dfa25116d54, 0x465009869fe80e52, 0xf4ba135008743833, 0x76ab072cb28d5b35, // [3][0x44] + 0x665b3a06ca4e9206, 0xe44a2e7a70b7f100, 0x56a034ace72bc761, 0xd4b120d05dd2a467, // [3][0x48] + 0x07ad2752908438c8, 0x85bc332e2a7d5bce, 0x375629f8bde16daf, 0xb5473d8407180ea9, // [3][0x4c] + 0x16b653ac4c66ffc9, 0x94a747d0f69f9ccf, 0x264d5d066103aaae, 0xa45c497adbfac9a8, // [3][0x50] + 0x77404ef816ac5507, 0xf5515a84ac553601, 0x47bb40523bc90060, 0xc5aa542e81306366, // [3][0x54] + 0xd55a6904f9f3aa55, 0x574b7d78430ac953, 0xe5a167aed496ff32, 0x67b073d26e6f9c34, // [3][0x58] + 0xb4ac7450a339009b, 0x36bd602c19c0639d, 0x84577afa8e5c55fc, 0x06466e8634a536fa, // [3][0x5c] + 0xf76c80f940362457, 0x757d9485facf4751, 0xc7978e536d537130, 0x45869a2fd7aa1236, // [3][0x60] + 0x969a9dad1afc8e99, 0x148b89d1a005ed9f, 0xa66193073799dbfe, 0x2470877b8d60b8f8, // [3][0x64] + 0x3480ba51f5a371cb, 0xb691ae2d4f5a12cd, 0x047bb4fbd8c624ac, 0x866aa087623f47aa, // [3][0x68] + 0x5576a705af69db05, 0xd767b3791590b803, 0x658da9af820c8e62, 0xe79cbdd338f5ed64, // [3][0x6c] + 0x446dd3fb738b1c04, 0xc67cc787c9727f02, 0x7496dd515eee4963, 0xf687c92de4172a65, // [3][0x70] + 0x259bceaf2941b6ca, 0xa78adad393b8d5cc, 0x1560c0050424e3ad, 0x9771d479bedd80ab, // [3][0x74] + 0x8781e953c61e4998, 0x0590fd2f7ce72a9e, 0xb77ae7f9eb7b1cff, 0x356bf38551827ff9, // [3][0x78] + 0xe677f4079cd4e356, 0x6466e07b262d8050, 0xd68cfaadb1b1b631, 0x549deed10b48d537, // [3][0x7c] + 0x7fb7270fa7201c5f, 0xfda633731dd97f59, 0x4f4c29a58a454938, 0xcd5d3dd930bc2a3e, // [3][0x80] + 0x1e413a5bfdeab691, 0x9c502e274713d597, 0x2eba34f1d08fe3f6, 0xacab208d6a7680f0, // [3][0x84] + 0xbc5b1da712b549c3, 0x3e4a09dba84c2ac5, 0x8ca0130d3fd01ca4, 0x0eb1077185297fa2, // [3][0x88] + 0xddad00f3487fe30d, 0x5fbc148ff286800b, 0xed560e59651ab66a, 0x6f471a25dfe3d56c, // [3][0x8c] + 0xccb6740d949d240c, 0x4ea760712e64470a, 0xfc4d7aa7b9f8716b, 0x7e5c6edb0301126d, // [3][0x90] + 0xad406959ce578ec2, 0x2f517d2574aeedc4, 0x9dbb67f3e332dba5, 0x1faa738f59cbb8a3, // [3][0x94] + 0x0f5a4ea521087190, 0x8d4b5ad99bf11296, 0x3fa1400f0c6d24f7, 0xbdb05473b69447f1, // [3][0x98] + 0x6eac53f17bc2db5e, 0xecbd478dc13bb858, 0x5e575d5b56a78e39, 0xdc464927ec5eed3f, // [3][0x9c] + 0x2d6ca75898cdff92, 0xaf7db32422349c94, 0x1d97a9f2b5a8aaf5, 0x9f86bd8e0f51c9f3, // [3][0xa0] + 0x4c9aba0cc207555c, 0xce8bae7078fe365a, 0x7c61b4a6ef62003b, 0xfe70a0da559b633d, // [3][0xa4] + 0xee809df02d58aa0e, 0x6c91898c97a1c908, 0xde7b935a003dff69, 0x5c6a8726bac49c6f, // [3][0xa8] + 0x8f7680a4779200c0, 0x0d6794d8cd6b63c6, 0xbf8d8e0e5af755a7, 0x3d9c9a72e00e36a1, // [3][0xac] + 0x9e6df45aab70c7c1, 0x1c7ce0261189a4c7, 0xae96faf0861592a6, 0x2c87ee8c3cecf1a0, // [3][0xb0] + 0xff9be90ef1ba6d0f, 0x7d8afd724b430e09, 0xcf60e7a4dcdf3868, 0x4d71f3d866265b6e, // [3][0xb4] + 0x5d81cef21ee5925d, 0xdf90da8ea41cf15b, 0x6d7ac0583380c73a, 0xef6bd4248979a43c, // [3][0xb8] + 0x3c77d3a6442f3893, 0xbe66c7dafed65b95, 0x0c8cdd0c694a6df4, 0x8e9dc970d3b30ef2, // [3][0xbc] + 0xda0027a1d8fbdbc5, 0x581133dd6202b8c3, 0xeafb290bf59e8ea2, 0x68ea3d774f67eda4, // [3][0xc0] + 0xbbf63af58231710b, 0x39e72e8938c8120d, 0x8b0d345faf54246c, 0x091c202315ad476a, // [3][0xc4] + 0x19ec1d096d6e8e59, 0x9bfd0975d797ed5f, 0x291713a3400bdb3e, 0xab0607dffaf2b838, // [3][0xc8] + 0x781a005d37a42497, 0xfa0b14218d5d4791, 0x48e10ef71ac171f0, 0xcaf01a8ba03812f6, // [3][0xcc] + 0x690174a3eb46e396, 0xeb1060df51bf8090, 0x59fa7a09c623b6f1, 0xdbeb6e757cdad5f7, // [3][0xd0] + 0x08f769f7b18c4958, 0x8ae67d8b0b752a5e, 0x380c675d9ce91c3f, 0xba1d732126107f39, // [3][0xd4] + 0xaaed4e0b5ed3b60a, 0x28fc5a77e42ad50c, 0x9a1640a173b6e36d, 0x180754ddc94f806b, // [3][0xd8] + 0xcb1b535f04191cc4, 0x490a4723bee07fc2, 0xfbe05df5297c49a3, 0x79f1498993852aa5, // [3][0xdc] + 0x88dba7f6e7163808, 0x0acab38a5def5b0e, 0xb820a95cca736d6f, 0x3a31bd20708a0e69, // [3][0xe0] + 0xe92dbaa2bddc92c6, 0x6b3caede0725f1c0, 0xd9d6b40890b9c7a1, 0x5bc7a0742a40a4a7, // [3][0xe4] + 0x4b379d5e52836d94, 0xc9268922e87a0e92, 0x7bcc93f47fe638f3, 0xf9dd8788c51f5bf5, // [3][0xe8] + 0x2ac1800a0849c75a, 0xa8d09476b2b0a45c, 0x1a3a8ea0252c923d, 0x982b9adc9fd5f13b, // [3][0xec] + 0x3bdaf4f4d4ab005b, 0xb9cbe0886e52635d, 0x0b21fa5ef9ce553c, 0x8930ee224337363a, // [3][0xf0] + 0x5a2ce9a08e61aa95, 0xd83dfddc3498c993, 0x6ad7e70aa304fff2, 0xe8c6f37619fd9cf4, // [3][0xf4] + 0xf836ce5c613e55c7, 0x7a27da20dbc736c1, 0xc8cdc0f64c5b00a0, 0x4adcd48af6a263a6, // [3][0xf8] + 0x99c0d3083bf4ff09, 0x1bd1c774810d9c0f, 0xa93bdda21691aa6e, 0x2b2ac9deac68c968 // [3][0xfc] + }, + { + 0x0000000000000000, 0x373d15f784905d1e, 0x6e7a2bef0920ba3c, 0x59473e188db0e722, // [4][0x00] + 0xdcf457de12417478, 0xebc9422996d12966, 0xb28e7c311b61ce44, 0x85b369c69ff1935a, // [4][0x04] + 0x8d3189ef7c157b9b, 0xba0c9c18f8852685, 0xe34ba2007535c1a7, 0xd476b7f7f1a59cb9, // [4][0x08] + 0x51c5de316e540fe3, 0x66f8cbc6eac452fd, 0x3fbff5de6774b5df, 0x0882e029e3e4e8c1, // [4][0x0c] + 0x2eba358da0bd645d, 0x1987207a242d3943, 0x40c01e62a99dde61, 0x77fd0b952d0d837f, // [4][0x10] + 0xf24e6253b2fc1025, 0xc57377a4366c4d3b, 0x9c3449bcbbdcaa19, 0xab095c4b3f4cf707, // [4][0x14] + 0xa38bbc62dca81fc6, 0x94b6a995583842d8, 0xcdf1978dd588a5fa, 0xfacc827a5118f8e4, // [4][0x18] + 0x7f7febbccee96bbe, 0x4842fe4b4a7936a0, 0x1105c053c7c9d182, 0x2638d5a443598c9c, // [4][0x1c] + 0x5d746b1b417ac8ba, 0x6a497eecc5ea95a4, 0x330e40f4485a7286, 0x04335503ccca2f98, // [4][0x20] + 0x81803cc5533bbcc2, 0xb6bd2932d7abe1dc, 0xeffa172a5a1b06fe, 0xd8c702ddde8b5be0, // [4][0x24] + 0xd045e2f43d6fb321, 0xe778f703b9ffee3f, 0xbe3fc91b344f091d, 0x8902dcecb0df5403, // [4][0x28] + 0x0cb1b52a2f2ec759, 0x3b8ca0ddabbe9a47, 0x62cb9ec5260e7d65, 0x55f68b32a29e207b, // [4][0x2c] + 0x73ce5e96e1c7ace7, 0x44f34b616557f1f9, 0x1db47579e8e716db, 0x2a89608e6c774bc5, // [4][0x30] + 0xaf3a0948f386d89f, 0x98071cbf77168581, 0xc14022a7faa662a3, 0xf67d37507e363fbd, // [4][0x34] + 0xfeffd7799dd2d77c, 0xc9c2c28e19428a62, 0x9085fc9694f26d40, 0xa7b8e9611062305e, // [4][0x38] + 0x220b80a78f93a304, 0x153695500b03fe1a, 0x4c71ab4886b31938, 0x7b4cbebf02234426, // [4][0x3c] + 0xbae8d63682f59174, 0x8dd5c3c10665cc6a, 0xd492fdd98bd52b48, 0xe3afe82e0f457656, // [4][0x40] + 0x661c81e890b4e50c, 0x5121941f1424b812, 0x0866aa0799945f30, 0x3f5bbff01d04022e, // [4][0x44] + 0x37d95fd9fee0eaef, 0x00e44a2e7a70b7f1, 0x59a37436f7c050d3, 0x6e9e61c173500dcd, // [4][0x48] + 0xeb2d0807eca19e97, 0xdc101df06831c389, 0x855723e8e58124ab, 0xb26a361f611179b5, // [4][0x4c] + 0x9452e3bb2248f529, 0xa36ff64ca6d8a837, 0xfa28c8542b684f15, 0xcd15dda3aff8120b, // [4][0x50] + 0x48a6b46530098151, 0x7f9ba192b499dc4f, 0x26dc9f8a39293b6d, 0x11e18a7dbdb96673, // [4][0x54] + 0x19636a545e5d8eb2, 0x2e5e7fa3dacdd3ac, 0x771941bb577d348e, 0x4024544cd3ed6990, // [4][0x58] + 0xc5973d8a4c1cfaca, 0xf2aa287dc88ca7d4, 0xabed1665453c40f6, 0x9cd00392c1ac1de8, // [4][0x5c] + 0xe79cbd2dc38f59ce, 0xd0a1a8da471f04d0, 0x89e696c2caafe3f2, 0xbedb83354e3fbeec, // [4][0x60] + 0x3b68eaf3d1ce2db6, 0x0c55ff04555e70a8, 0x5512c11cd8ee978a, 0x622fd4eb5c7eca94, // [4][0x64] + 0x6aad34c2bf9a2255, 0x5d9021353b0a7f4b, 0x04d71f2db6ba9869, 0x33ea0ada322ac577, // [4][0x68] + 0xb659631caddb562d, 0x816476eb294b0b33, 0xd82348f3a4fbec11, 0xef1e5d04206bb10f, // [4][0x6c] + 0xc92688a063323d93, 0xfe1b9d57e7a2608d, 0xa75ca34f6a1287af, 0x9061b6b8ee82dab1, // [4][0x70] + 0x15d2df7e717349eb, 0x22efca89f5e314f5, 0x7ba8f4917853f3d7, 0x4c95e166fcc3aec9, // [4][0x74] + 0x4417014f1f274608, 0x732a14b89bb71b16, 0x2a6d2aa01607fc34, 0x1d503f579297a12a, // [4][0x78] + 0x98e356910d663270, 0xafde436689f66f6e, 0xf6997d7e0446884c, 0xc1a4688980d6d552, // [4][0x7c] + 0x41088a3e5d7cb183, 0x76359fc9d9ecec9d, 0x2f72a1d1545c0bbf, 0x184fb426d0cc56a1, // [4][0x80] + 0x9dfcdde04f3dc5fb, 0xaac1c817cbad98e5, 0xf386f60f461d7fc7, 0xc4bbe3f8c28d22d9, // [4][0x84] + 0xcc3903d12169ca18, 0xfb041626a5f99706, 0xa243283e28497024, 0x957e3dc9acd92d3a, // [4][0x88] + 0x10cd540f3328be60, 0x27f041f8b7b8e37e, 0x7eb77fe03a08045c, 0x498a6a17be985942, // [4][0x8c] + 0x6fb2bfb3fdc1d5de, 0x588faa44795188c0, 0x01c8945cf4e16fe2, 0x36f581ab707132fc, // [4][0x90] + 0xb346e86def80a1a6, 0x847bfd9a6b10fcb8, 0xdd3cc382e6a01b9a, 0xea01d67562304684, // [4][0x94] + 0xe283365c81d4ae45, 0xd5be23ab0544f35b, 0x8cf91db388f41479, 0xbbc408440c644967, // [4][0x98] + 0x3e7761829395da3d, 0x094a747517058723, 0x500d4a6d9ab56001, 0x67305f9a1e253d1f, // [4][0x9c] + 0x1c7ce1251c067939, 0x2b41f4d298962427, 0x7206caca1526c305, 0x453bdf3d91b69e1b, // [4][0xa0] + 0xc088b6fb0e470d41, 0xf7b5a30c8ad7505f, 0xaef29d140767b77d, 0x99cf88e383f7ea63, // [4][0xa4] + 0x914d68ca601302a2, 0xa6707d3de4835fbc, 0xff3743256933b89e, 0xc80a56d2eda3e580, // [4][0xa8] + 0x4db93f14725276da, 0x7a842ae3f6c22bc4, 0x23c314fb7b72cce6, 0x14fe010cffe291f8, // [4][0xac] + 0x32c6d4a8bcbb1d64, 0x05fbc15f382b407a, 0x5cbcff47b59ba758, 0x6b81eab0310bfa46, // [4][0xb0] + 0xee328376aefa691c, 0xd90f96812a6a3402, 0x8048a899a7dad320, 0xb775bd6e234a8e3e, // [4][0xb4] + 0xbff75d47c0ae66ff, 0x88ca48b0443e3be1, 0xd18d76a8c98edcc3, 0xe6b0635f4d1e81dd, // [4][0xb8] + 0x63030a99d2ef1287, 0x543e1f6e567f4f99, 0x0d792176dbcfa8bb, 0x3a4434815f5ff5a5, // [4][0xbc] + 0xfbe05c08df8920f7, 0xccdd49ff5b197de9, 0x959a77e7d6a99acb, 0xa2a762105239c7d5, // [4][0xc0] + 0x27140bd6cdc8548f, 0x10291e2149580991, 0x496e2039c4e8eeb3, 0x7e5335ce4078b3ad, // [4][0xc4] + 0x76d1d5e7a39c5b6c, 0x41ecc010270c0672, 0x18abfe08aabce150, 0x2f96ebff2e2cbc4e, // [4][0xc8] + 0xaa258239b1dd2f14, 0x9d1897ce354d720a, 0xc45fa9d6b8fd9528, 0xf362bc213c6dc836, // [4][0xcc] + 0xd55a69857f3444aa, 0xe2677c72fba419b4, 0xbb20426a7614fe96, 0x8c1d579df284a388, // [4][0xd0] + 0x09ae3e5b6d7530d2, 0x3e932bace9e56dcc, 0x67d415b464558aee, 0x50e90043e0c5d7f0, // [4][0xd4] + 0x586be06a03213f31, 0x6f56f59d87b1622f, 0x3611cb850a01850d, 0x012cde728e91d813, // [4][0xd8] + 0x849fb7b411604b49, 0xb3a2a24395f01657, 0xeae59c5b1840f175, 0xddd889ac9cd0ac6b, // [4][0xdc] + 0xa69437139ef3e84d, 0x91a922e41a63b553, 0xc8ee1cfc97d35271, 0xffd3090b13430f6f, // [4][0xe0] + 0x7a6060cd8cb29c35, 0x4d5d753a0822c12b, 0x141a4b2285922609, 0x23275ed501027b17, // [4][0xe4] + 0x2ba5befce2e693d6, 0x1c98ab0b6676cec8, 0x45df9513ebc629ea, 0x72e280e46f5674f4, // [4][0xe8] + 0xf751e922f0a7e7ae, 0xc06cfcd57437bab0, 0x992bc2cdf9875d92, 0xae16d73a7d17008c, // [4][0xec] + 0x882e029e3e4e8c10, 0xbf131769baded10e, 0xe6542971376e362c, 0xd1693c86b3fe6b32, // [4][0xf0] + 0x54da55402c0ff868, 0x63e740b7a89fa576, 0x3aa07eaf252f4254, 0x0d9d6b58a1bf1f4a, // [4][0xf4] + 0x051f8b71425bf78b, 0x32229e86c6cbaa95, 0x6b65a09e4b7b4db7, 0x5c58b569cfeb10a9, // [4][0xf8] + 0xd9ebdcaf501a83f3, 0xeed6c958d48adeed, 0xb791f740593a39cf, 0x80ace2b7ddaa64d1 // [4][0xfc] + }, + { + 0x0000000000000000, 0xe9742a79ef04a5d4, 0xe63172a0869ed8c3, 0x0f4558d9699a7d17, // [5][0x00] + 0xf8bbc31255aa22ed, 0x11cfe96bbaae8739, 0x1e8ab1b2d334fa2e, 0xf7fe9bcb3c305ffa, // [5][0x04] + 0xc5aea077f3c3d6b1, 0x2cda8a0e1cc77365, 0x239fd2d7755d0e72, 0xcaebf8ae9a59aba6, // [5][0x08] + 0x3d156365a669f45c, 0xd461491c496d5188, 0xdb2411c520f72c9f, 0x32503bbccff3894b, // [5][0x0c] + 0xbf8466bcbf103e09, 0x56f04cc550149bdd, 0x59b5141c398ee6ca, 0xb0c13e65d68a431e, // [5][0x10] + 0x473fa5aeeaba1ce4, 0xae4b8fd705beb930, 0xa10ed70e6c24c427, 0x487afd77832061f3, // [5][0x14] + 0x7a2ac6cb4cd3e8b8, 0x935eecb2a3d74d6c, 0x9c1bb46bca4d307b, 0x756f9e12254995af, // [5][0x18] + 0x829105d91979ca55, 0x6be52fa0f67d6f81, 0x64a077799fe71296, 0x8dd45d0070e3b742, // [5][0x1c] + 0x4bd1eb2a26b7ef79, 0xa2a5c153c9b34aad, 0xade0998aa02937ba, 0x4494b3f34f2d926e, // [5][0x20] + 0xb36a2838731dcd94, 0x5a1e02419c196840, 0x555b5a98f5831557, 0xbc2f70e11a87b083, // [5][0x24] + 0x8e7f4b5dd57439c8, 0x670b61243a709c1c, 0x684e39fd53eae10b, 0x813a1384bcee44df, // [5][0x28] + 0x76c4884f80de1b25, 0x9fb0a2366fdabef1, 0x90f5faef0640c3e6, 0x7981d096e9446632, // [5][0x2c] + 0xf4558d9699a7d170, 0x1d21a7ef76a374a4, 0x1264ff361f3909b3, 0xfb10d54ff03dac67, // [5][0x30] + 0x0cee4e84cc0df39d, 0xe59a64fd23095649, 0xeadf3c244a932b5e, 0x03ab165da5978e8a, // [5][0x34] + 0x31fb2de16a6407c1, 0xd88f07988560a215, 0xd7ca5f41ecfadf02, 0x3ebe753803fe7ad6, // [5][0x38] + 0xc940eef33fce252c, 0x2034c48ad0ca80f8, 0x2f719c53b950fdef, 0xc605b62a5654583b, // [5][0x3c] + 0x97a3d6544d6fdef2, 0x7ed7fc2da26b7b26, 0x7192a4f4cbf10631, 0x98e68e8d24f5a3e5, // [5][0x40] + 0x6f18154618c5fc1f, 0x866c3f3ff7c159cb, 0x892967e69e5b24dc, 0x605d4d9f715f8108, // [5][0x44] + 0x520d7623beac0843, 0xbb795c5a51a8ad97, 0xb43c04833832d080, 0x5d482efad7367554, // [5][0x48] + 0xaab6b531eb062aae, 0x43c29f4804028f7a, 0x4c87c7916d98f26d, 0xa5f3ede8829c57b9, // [5][0x4c] + 0x2827b0e8f27fe0fb, 0xc1539a911d7b452f, 0xce16c24874e13838, 0x2762e8319be59dec, // [5][0x50] + 0xd09c73faa7d5c216, 0x39e8598348d167c2, 0x36ad015a214b1ad5, 0xdfd92b23ce4fbf01, // [5][0x54] + 0xed89109f01bc364a, 0x04fd3ae6eeb8939e, 0x0bb8623f8722ee89, 0xe2cc484668264b5d, // [5][0x58] + 0x1532d38d541614a7, 0xfc46f9f4bb12b173, 0xf303a12dd288cc64, 0x1a778b543d8c69b0, // [5][0x5c] + 0xdc723d7e6bd8318b, 0x3506170784dc945f, 0x3a434fdeed46e948, 0xd33765a702424c9c, // [5][0x60] + 0x24c9fe6c3e721366, 0xcdbdd415d176b6b2, 0xc2f88cccb8eccba5, 0x2b8ca6b557e86e71, // [5][0x64] + 0x19dc9d09981be73a, 0xf0a8b770771f42ee, 0xffedefa91e853ff9, 0x1699c5d0f1819a2d, // [5][0x68] + 0xe1675e1bcdb1c5d7, 0x0813746222b56003, 0x07562cbb4b2f1d14, 0xee2206c2a42bb8c0, // [5][0x6c] + 0x63f65bc2d4c80f82, 0x8a8271bb3bccaa56, 0x85c729625256d741, 0x6cb3031bbd527295, // [5][0x70] + 0x9b4d98d081622d6f, 0x7239b2a96e6688bb, 0x7d7cea7007fcf5ac, 0x9408c009e8f85078, // [5][0x74] + 0xa658fbb5270bd933, 0x4f2cd1ccc80f7ce7, 0x40698915a19501f0, 0xa91da36c4e91a424, // [5][0x78] + 0x5ee338a772a1fbde, 0xb79712de9da55e0a, 0xb8d24a07f43f231d, 0x51a6607e1b3b86c9, // [5][0x7c] + 0x1b9e8afbc2482e8f, 0xf2eaa0822d4c8b5b, 0xfdaff85b44d6f64c, 0x14dbd222abd25398, // [5][0x80] + 0xe32549e997e20c62, 0x0a51639078e6a9b6, 0x05143b49117cd4a1, 0xec601130fe787175, // [5][0x84] + 0xde302a8c318bf83e, 0x374400f5de8f5dea, 0x3801582cb71520fd, 0xd175725558118529, // [5][0x88] + 0x268be99e6421dad3, 0xcfffc3e78b257f07, 0xc0ba9b3ee2bf0210, 0x29ceb1470dbba7c4, // [5][0x8c] + 0xa41aec477d581086, 0x4d6ec63e925cb552, 0x422b9ee7fbc6c845, 0xab5fb49e14c26d91, // [5][0x90] + 0x5ca12f5528f2326b, 0xb5d5052cc7f697bf, 0xba905df5ae6ceaa8, 0x53e4778c41684f7c, // [5][0x94] + 0x61b44c308e9bc637, 0x88c06649619f63e3, 0x87853e9008051ef4, 0x6ef114e9e701bb20, // [5][0x98] + 0x990f8f22db31e4da, 0x707ba55b3435410e, 0x7f3efd825daf3c19, 0x964ad7fbb2ab99cd, // [5][0x9c] + 0x504f61d1e4ffc1f6, 0xb93b4ba80bfb6422, 0xb67e137162611935, 0x5f0a39088d65bce1, // [5][0xa0] + 0xa8f4a2c3b155e31b, 0x418088ba5e5146cf, 0x4ec5d06337cb3bd8, 0xa7b1fa1ad8cf9e0c, // [5][0xa4] + 0x95e1c1a6173c1747, 0x7c95ebdff838b293, 0x73d0b30691a2cf84, 0x9aa4997f7ea66a50, // [5][0xa8] + 0x6d5a02b4429635aa, 0x842e28cdad92907e, 0x8b6b7014c408ed69, 0x621f5a6d2b0c48bd, // [5][0xac] + 0xefcb076d5befffff, 0x06bf2d14b4eb5a2b, 0x09fa75cddd71273c, 0xe08e5fb4327582e8, // [5][0xb0] + 0x1770c47f0e45dd12, 0xfe04ee06e14178c6, 0xf141b6df88db05d1, 0x18359ca667dfa005, // [5][0xb4] + 0x2a65a71aa82c294e, 0xc3118d6347288c9a, 0xcc54d5ba2eb2f18d, 0x2520ffc3c1b65459, // [5][0xb8] + 0xd2de6408fd860ba3, 0x3baa4e711282ae77, 0x34ef16a87b18d360, 0xdd9b3cd1941c76b4, // [5][0xbc] + 0x8c3d5caf8f27f07d, 0x654976d6602355a9, 0x6a0c2e0f09b928be, 0x83780476e6bd8d6a, // [5][0xc0] + 0x74869fbdda8dd290, 0x9df2b5c435897744, 0x92b7ed1d5c130a53, 0x7bc3c764b317af87, // [5][0xc4] + 0x4993fcd87ce426cc, 0xa0e7d6a193e08318, 0xafa28e78fa7afe0f, 0x46d6a401157e5bdb, // [5][0xc8] + 0xb1283fca294e0421, 0x585c15b3c64aa1f5, 0x57194d6aafd0dce2, 0xbe6d671340d47936, // [5][0xcc] + 0x33b93a133037ce74, 0xdacd106adf336ba0, 0xd58848b3b6a916b7, 0x3cfc62ca59adb363, // [5][0xd0] + 0xcb02f901659dec99, 0x2276d3788a99494d, 0x2d338ba1e303345a, 0xc447a1d80c07918e, // [5][0xd4] + 0xf6179a64c3f418c5, 0x1f63b01d2cf0bd11, 0x1026e8c4456ac006, 0xf952c2bdaa6e65d2, // [5][0xd8] + 0x0eac5976965e3a28, 0xe7d8730f795a9ffc, 0xe89d2bd610c0e2eb, 0x01e901afffc4473f, // [5][0xdc] + 0xc7ecb785a9901f04, 0x2e989dfc4694bad0, 0x21ddc5252f0ec7c7, 0xc8a9ef5cc00a6213, // [5][0xe0] + 0x3f577497fc3a3de9, 0xd6235eee133e983d, 0xd96606377aa4e52a, 0x30122c4e95a040fe, // [5][0xe4] + 0x024217f25a53c9b5, 0xeb363d8bb5576c61, 0xe4736552dccd1176, 0x0d074f2b33c9b4a2, // [5][0xe8] + 0xfaf9d4e00ff9eb58, 0x138dfe99e0fd4e8c, 0x1cc8a6408967339b, 0xf5bc8c396663964f, // [5][0xec] + 0x7868d1391680210d, 0x911cfb40f98484d9, 0x9e59a399901ef9ce, 0x772d89e07f1a5c1a, // [5][0xf0] + 0x80d3122b432a03e0, 0x69a73852ac2ea634, 0x66e2608bc5b4db23, 0x8f964af22ab07ef7, // [5][0xf4] + 0xbdc6714ee543f7bc, 0x54b25b370a475268, 0x5bf703ee63dd2f7f, 0xb28329978cd98aab, // [5][0xf8] + 0x457db25cb0e9d551, 0xac0998255fed7085, 0xa34cc0fc36770d92, 0x4a38ea85d973a846 // [5][0xfc] + }, + { + 0x0000000000000000, 0xfc5d27f6bf353971, 0xcc6369be26fde189, 0x303e4e4899c8d8f8, // [6][0x00] + 0xac1ff52f156c5079, 0x5042d2d9aa596908, 0x607c9c913391b1f0, 0x9c21bb678ca48881, // [6][0x04] + 0x6ce6cc0d724f3399, 0x90bbebfbcd7a0ae8, 0xa085a5b354b2d210, 0x5cd88245eb87eb61, // [6][0x08] + 0xc0f93922672363e0, 0x3ca41ed4d8165a91, 0x0c9a509c41de8269, 0xf0c7776afeebbb18, // [6][0x0c] + 0xd9cd981ae49e6732, 0x2590bfec5bab5e43, 0x15aef1a4c26386bb, 0xe9f3d6527d56bfca, // [6][0x10] + 0x75d26d35f1f2374b, 0x898f4ac34ec70e3a, 0xb9b1048bd70fd6c2, 0x45ec237d683aefb3, // [6][0x14] + 0xb52b541796d154ab, 0x497673e129e46dda, 0x79483da9b02cb522, 0x85151a5f0f198c53, // [6][0x18] + 0x1934a13883bd04d2, 0xe56986ce3c883da3, 0xd557c886a540e55b, 0x290aef701a75dc2a, // [6][0x1c] + 0x8742166691ab5d0f, 0x7b1f31902e9e647e, 0x4b217fd8b756bc86, 0xb77c582e086385f7, // [6][0x20] + 0x2b5de34984c70d76, 0xd700c4bf3bf23407, 0xe73e8af7a23aecff, 0x1b63ad011d0fd58e, // [6][0x24] + 0xeba4da6be3e46e96, 0x17f9fd9d5cd157e7, 0x27c7b3d5c5198f1f, 0xdb9a94237a2cb66e, // [6][0x28] + 0x47bb2f44f6883eef, 0xbbe608b249bd079e, 0x8bd846fad075df66, 0x7785610c6f40e617, // [6][0x2c] + 0x5e8f8e7c75353a3d, 0xa2d2a98aca00034c, 0x92ece7c253c8dbb4, 0x6eb1c034ecfde2c5, // [6][0x30] + 0xf2907b5360596a44, 0x0ecd5ca5df6c5335, 0x3ef312ed46a48bcd, 0xc2ae351bf991b2bc, // [6][0x34] + 0x32694271077a09a4, 0xce346587b84f30d5, 0xfe0a2bcf2187e82d, 0x02570c399eb2d15c, // [6][0x38] + 0x9e76b75e121659dd, 0x622b90a8ad2360ac, 0x5215dee034ebb854, 0xae48f9168bde8125, // [6][0x3c] + 0x3a5d0a9e7bc12975, 0xc6002d68c4f41004, 0xf63e63205d3cc8fc, 0x0a6344d6e209f18d, // [6][0x40] + 0x9642ffb16ead790c, 0x6a1fd847d198407d, 0x5a21960f48509885, 0xa67cb1f9f765a1f4, // [6][0x44] + 0x56bbc693098e1aec, 0xaae6e165b6bb239d, 0x9ad8af2d2f73fb65, 0x668588db9046c214, // [6][0x48] + 0xfaa433bc1ce24a95, 0x06f9144aa3d773e4, 0x36c75a023a1fab1c, 0xca9a7df4852a926d, // [6][0x4c] + 0xe39092849f5f4e47, 0x1fcdb572206a7736, 0x2ff3fb3ab9a2afce, 0xd3aedccc069796bf, // [6][0x50] + 0x4f8f67ab8a331e3e, 0xb3d2405d3506274f, 0x83ec0e15acceffb7, 0x7fb129e313fbc6c6, // [6][0x54] + 0x8f765e89ed107dde, 0x732b797f522544af, 0x43153737cbed9c57, 0xbf4810c174d8a526, // [6][0x58] + 0x2369aba6f87c2da7, 0xdf348c50474914d6, 0xef0ac218de81cc2e, 0x1357e5ee61b4f55f, // [6][0x5c] + 0xbd1f1cf8ea6a747a, 0x41423b0e555f4d0b, 0x717c7546cc9795f3, 0x8d2152b073a2ac82, // [6][0x60] + 0x1100e9d7ff062403, 0xed5dce2140331d72, 0xdd638069d9fbc58a, 0x213ea79f66cefcfb, // [6][0x64] + 0xd1f9d0f5982547e3, 0x2da4f70327107e92, 0x1d9ab94bbed8a66a, 0xe1c79ebd01ed9f1b, // [6][0x68] + 0x7de625da8d49179a, 0x81bb022c327c2eeb, 0xb1854c64abb4f613, 0x4dd86b921481cf62, // [6][0x6c] + 0x64d284e20ef41348, 0x988fa314b1c12a39, 0xa8b1ed5c2809f2c1, 0x54eccaaa973ccbb0, // [6][0x70] + 0xc8cd71cd1b984331, 0x3490563ba4ad7a40, 0x04ae18733d65a2b8, 0xf8f33f8582509bc9, // [6][0x74] + 0x083448ef7cbb20d1, 0xf4696f19c38e19a0, 0xc45721515a46c158, 0x380a06a7e573f829, // [6][0x78] + 0xa42bbdc069d770a8, 0x58769a36d6e249d9, 0x6848d47e4f2a9121, 0x9415f388f01fa850, // [6][0x7c] + 0x74ba153cf78252ea, 0x88e732ca48b76b9b, 0xb8d97c82d17fb363, 0x44845b746e4a8a12, // [6][0x80] + 0xd8a5e013e2ee0293, 0x24f8c7e55ddb3be2, 0x14c689adc413e31a, 0xe89bae5b7b26da6b, // [6][0x84] + 0x185cd93185cd6173, 0xe401fec73af85802, 0xd43fb08fa33080fa, 0x286297791c05b98b, // [6][0x88] + 0xb4432c1e90a1310a, 0x481e0be82f94087b, 0x782045a0b65cd083, 0x847d62560969e9f2, // [6][0x8c] + 0xad778d26131c35d8, 0x512aaad0ac290ca9, 0x6114e49835e1d451, 0x9d49c36e8ad4ed20, // [6][0x90] + 0x01687809067065a1, 0xfd355fffb9455cd0, 0xcd0b11b7208d8428, 0x315636419fb8bd59, // [6][0x94] + 0xc191412b61530641, 0x3dcc66ddde663f30, 0x0df2289547aee7c8, 0xf1af0f63f89bdeb9, // [6][0x98] + 0x6d8eb404743f5638, 0x91d393f2cb0a6f49, 0xa1edddba52c2b7b1, 0x5db0fa4cedf78ec0, // [6][0x9c] + 0xf3f8035a66290fe5, 0x0fa524acd91c3694, 0x3f9b6ae440d4ee6c, 0xc3c64d12ffe1d71d, // [6][0xa0] + 0x5fe7f67573455f9c, 0xa3bad183cc7066ed, 0x93849fcb55b8be15, 0x6fd9b83dea8d8764, // [6][0xa4] + 0x9f1ecf5714663c7c, 0x6343e8a1ab53050d, 0x537da6e9329bddf5, 0xaf20811f8daee484, // [6][0xa8] + 0x33013a78010a6c05, 0xcf5c1d8ebe3f5574, 0xff6253c627f78d8c, 0x033f743098c2b4fd, // [6][0xac] + 0x2a359b4082b768d7, 0xd668bcb63d8251a6, 0xe656f2fea44a895e, 0x1a0bd5081b7fb02f, // [6][0xb0] + 0x862a6e6f97db38ae, 0x7a77499928ee01df, 0x4a4907d1b126d927, 0xb61420270e13e056, // [6][0xb4] + 0x46d3574df0f85b4e, 0xba8e70bb4fcd623f, 0x8ab03ef3d605bac7, 0x76ed1905693083b6, // [6][0xb8] + 0xeacca262e5940b37, 0x169185945aa13246, 0x26afcbdcc369eabe, 0xdaf2ec2a7c5cd3cf, // [6][0xbc] + 0x4ee71fa28c437b9f, 0xb2ba3854337642ee, 0x8284761caabe9a16, 0x7ed951ea158ba367, // [6][0xc0] + 0xe2f8ea8d992f2be6, 0x1ea5cd7b261a1297, 0x2e9b8333bfd2ca6f, 0xd2c6a4c500e7f31e, // [6][0xc4] + 0x2201d3affe0c4806, 0xde5cf45941397177, 0xee62ba11d8f1a98f, 0x123f9de767c490fe, // [6][0xc8] + 0x8e1e2680eb60187f, 0x724301765455210e, 0x427d4f3ecd9df9f6, 0xbe2068c872a8c087, // [6][0xcc] + 0x972a87b868dd1cad, 0x6b77a04ed7e825dc, 0x5b49ee064e20fd24, 0xa714c9f0f115c455, // [6][0xd0] + 0x3b3572977db14cd4, 0xc7685561c28475a5, 0xf7561b295b4cad5d, 0x0b0b3cdfe479942c, // [6][0xd4] + 0xfbcc4bb51a922f34, 0x07916c43a5a71645, 0x37af220b3c6fcebd, 0xcbf205fd835af7cc, // [6][0xd8] + 0x57d3be9a0ffe7f4d, 0xab8e996cb0cb463c, 0x9bb0d72429039ec4, 0x67edf0d29636a7b5, // [6][0xdc] + 0xc9a509c41de82690, 0x35f82e32a2dd1fe1, 0x05c6607a3b15c719, 0xf99b478c8420fe68, // [6][0xe0] + 0x65bafceb088476e9, 0x99e7db1db7b14f98, 0xa9d995552e799760, 0x5584b2a3914cae11, // [6][0xe4] + 0xa543c5c96fa71509, 0x591ee23fd0922c78, 0x6920ac77495af480, 0x957d8b81f66fcdf1, // [6][0xe8] + 0x095c30e67acb4570, 0xf5011710c5fe7c01, 0xc53f59585c36a4f9, 0x39627eaee3039d88, // [6][0xec] + 0x106891def97641a2, 0xec35b628464378d3, 0xdc0bf860df8ba02b, 0x2056df9660be995a, // [6][0xf0] + 0xbc7764f1ec1a11db, 0x402a4307532f28aa, 0x70140d4fcae7f052, 0x8c492ab975d2c923, // [6][0xf4] + 0x7c8e5dd38b39723b, 0x80d37a25340c4b4a, 0xb0ed346dadc493b2, 0x4cb0139b12f1aac3, // [6][0xf8] + 0xd091a8fc9e552242, 0x2ccc8f0a21601b33, 0x1cf2c142b8a8c3cb, 0xe0afe6b4079dfaba // [6][0xfc] + }, + { + 0x0000000000000000, 0x21e9761e252621ac, 0x43d2ec3c4a4c4358, 0x623b9a226f6a62f4, // [7][0x00] + 0x87a5d878949886b0, 0xa64cae66b1bea71c, 0xc4773444ded4c5e8, 0xe59e425afbf2e444, // [7][0x04] + 0x3b9296a271a69e0b, 0x1a7be0bc5480bfa7, 0x78407a9e3beadd53, 0x59a90c801eccfcff, // [7][0x08] + 0xbc374edae53e18bb, 0x9dde38c4c0183917, 0xffe5a2e6af725be3, 0xde0cd4f88a547a4f, // [7][0x0c] + 0x77252d44e34d3c16, 0x56cc5b5ac66b1dba, 0x34f7c178a9017f4e, 0x151eb7668c275ee2, // [7][0x10] + 0xf080f53c77d5baa6, 0xd169832252f39b0a, 0xb35219003d99f9fe, 0x92bb6f1e18bfd852, // [7][0x14] + 0x4cb7bbe692eba21d, 0x6d5ecdf8b7cd83b1, 0x0f6557dad8a7e145, 0x2e8c21c4fd81c0e9, // [7][0x18] + 0xcb12639e067324ad, 0xeafb158023550501, 0x88c08fa24c3f67f5, 0xa929f9bc69194659, // [7][0x1c] + 0xee4a5a89c69a782c, 0xcfa32c97e3bc5980, 0xad98b6b58cd63b74, 0x8c71c0aba9f01ad8, // [7][0x20] + 0x69ef82f15202fe9c, 0x4806f4ef7724df30, 0x2a3d6ecd184ebdc4, 0x0bd418d33d689c68, // [7][0x24] + 0xd5d8cc2bb73ce627, 0xf431ba35921ac78b, 0x960a2017fd70a57f, 0xb7e35609d85684d3, // [7][0x28] + 0x527d145323a46097, 0x7394624d0682413b, 0x11aff86f69e823cf, 0x30468e714cce0263, // [7][0x2c] + 0x996f77cd25d7443a, 0xb88601d300f16596, 0xdabd9bf16f9b0762, 0xfb54edef4abd26ce, // [7][0x30] + 0x1ecaafb5b14fc28a, 0x3f23d9ab9469e326, 0x5d184389fb0381d2, 0x7cf13597de25a07e, // [7][0x34] + 0xa2fde16f5471da31, 0x831497717157fb9d, 0xe12f0d531e3d9969, 0xc0c67b4d3b1bb8c5, // [7][0x38] + 0x25583917c0e95c81, 0x04b14f09e5cf7d2d, 0x668ad52b8aa51fd9, 0x4763a335af833e75, // [7][0x3c] + 0xe84d9340d5a36333, 0xc9a4e55ef085429f, 0xab9f7f7c9fef206b, 0x8a760962bac901c7, // [7][0x40] + 0x6fe84b38413be583, 0x4e013d26641dc42f, 0x2c3aa7040b77a6db, 0x0dd3d11a2e518777, // [7][0x44] + 0xd3df05e2a405fd38, 0xf23673fc8123dc94, 0x900de9deee49be60, 0xb1e49fc0cb6f9fcc, // [7][0x48] + 0x547add9a309d7b88, 0x7593ab8415bb5a24, 0x17a831a67ad138d0, 0x364147b85ff7197c, // [7][0x4c] + 0x9f68be0436ee5f25, 0xbe81c81a13c87e89, 0xdcba52387ca21c7d, 0xfd53242659843dd1, // [7][0x50] + 0x18cd667ca276d995, 0x392410628750f839, 0x5b1f8a40e83a9acd, 0x7af6fc5ecd1cbb61, // [7][0x54] + 0xa4fa28a64748c12e, 0x85135eb8626ee082, 0xe728c49a0d048276, 0xc6c1b2842822a3da, // [7][0x58] + 0x235ff0ded3d0479e, 0x02b686c0f6f66632, 0x608d1ce2999c04c6, 0x41646afcbcba256a, // [7][0x5c] + 0x0607c9c913391b1f, 0x27eebfd7361f3ab3, 0x45d525f559755847, 0x643c53eb7c5379eb, // [7][0x60] + 0x81a211b187a19daf, 0xa04b67afa287bc03, 0xc270fd8dcdeddef7, 0xe3998b93e8cbff5b, // [7][0x64] + 0x3d955f6b629f8514, 0x1c7c297547b9a4b8, 0x7e47b35728d3c64c, 0x5faec5490df5e7e0, // [7][0x68] + 0xba308713f60703a4, 0x9bd9f10dd3212208, 0xf9e26b2fbc4b40fc, 0xd80b1d31996d6150, // [7][0x6c] + 0x7122e48df0742709, 0x50cb9293d55206a5, 0x32f008b1ba386451, 0x13197eaf9f1e45fd, // [7][0x70] + 0xf6873cf564eca1b9, 0xd76e4aeb41ca8015, 0xb555d0c92ea0e2e1, 0x94bca6d70b86c34d, // [7][0x74] + 0x4ab0722f81d2b902, 0x6b590431a4f498ae, 0x09629e13cb9efa5a, 0x288be80deeb8dbf6, // [7][0x78] + 0xcd15aa57154a3fb2, 0xecfcdc49306c1e1e, 0x8ec7466b5f067cea, 0xaf2e30757a205d46, // [7][0x7c] + 0xe44200d2f3d1550d, 0xc5ab76ccd6f774a1, 0xa790eceeb99d1655, 0x86799af09cbb37f9, // [7][0x80] + 0x63e7d8aa6749d3bd, 0x420eaeb4426ff211, 0x203534962d0590e5, 0x01dc42880823b149, // [7][0x84] + 0xdfd096708277cb06, 0xfe39e06ea751eaaa, 0x9c027a4cc83b885e, 0xbdeb0c52ed1da9f2, // [7][0x88] + 0x58754e0816ef4db6, 0x799c381633c96c1a, 0x1ba7a2345ca30eee, 0x3a4ed42a79852f42, // [7][0x8c] + 0x93672d96109c691b, 0xb28e5b8835ba48b7, 0xd0b5c1aa5ad02a43, 0xf15cb7b47ff60bef, // [7][0x90] + 0x14c2f5ee8404efab, 0x352b83f0a122ce07, 0x571019d2ce48acf3, 0x76f96fcceb6e8d5f, // [7][0x94] + 0xa8f5bb34613af710, 0x891ccd2a441cd6bc, 0xeb2757082b76b448, 0xcace21160e5095e4, // [7][0x98] + 0x2f50634cf5a271a0, 0x0eb91552d084500c, 0x6c828f70bfee32f8, 0x4d6bf96e9ac81354, // [7][0x9c] + 0x0a085a5b354b2d21, 0x2be12c45106d0c8d, 0x49dab6677f076e79, 0x6833c0795a214fd5, // [7][0xa0] + 0x8dad8223a1d3ab91, 0xac44f43d84f58a3d, 0xce7f6e1feb9fe8c9, 0xef961801ceb9c965, // [7][0xa4] + 0x319accf944edb32a, 0x1073bae761cb9286, 0x724820c50ea1f072, 0x53a156db2b87d1de, // [7][0xa8] + 0xb63f1481d075359a, 0x97d6629ff5531436, 0xf5edf8bd9a3976c2, 0xd4048ea3bf1f576e, // [7][0xac] + 0x7d2d771fd6061137, 0x5cc40101f320309b, 0x3eff9b239c4a526f, 0x1f16ed3db96c73c3, // [7][0xb0] + 0xfa88af67429e9787, 0xdb61d97967b8b62b, 0xb95a435b08d2d4df, 0x98b335452df4f573, // [7][0xb4] + 0x46bfe1bda7a08f3c, 0x675697a38286ae90, 0x056d0d81edeccc64, 0x24847b9fc8caedc8, // [7][0xb8] + 0xc11a39c53338098c, 0xe0f34fdb161e2820, 0x82c8d5f979744ad4, 0xa321a3e75c526b78, // [7][0xbc] + 0x0c0f93922672363e, 0x2de6e58c03541792, 0x4fdd7fae6c3e7566, 0x6e3409b0491854ca, // [7][0xc0] + 0x8baa4beab2eab08e, 0xaa433df497cc9122, 0xc878a7d6f8a6f3d6, 0xe991d1c8dd80d27a, // [7][0xc4] + 0x379d053057d4a835, 0x1674732e72f28999, 0x744fe90c1d98eb6d, 0x55a69f1238becac1, // [7][0xc8] + 0xb038dd48c34c2e85, 0x91d1ab56e66a0f29, 0xf3ea317489006ddd, 0xd203476aac264c71, // [7][0xcc] + 0x7b2abed6c53f0a28, 0x5ac3c8c8e0192b84, 0x38f852ea8f734970, 0x191124f4aa5568dc, // [7][0xd0] + 0xfc8f66ae51a78c98, 0xdd6610b07481ad34, 0xbf5d8a921bebcfc0, 0x9eb4fc8c3ecdee6c, // [7][0xd4] + 0x40b82874b4999423, 0x61515e6a91bfb58f, 0x036ac448fed5d77b, 0x2283b256dbf3f6d7, // [7][0xd8] + 0xc71df00c20011293, 0xe6f486120527333f, 0x84cf1c306a4d51cb, 0xa5266a2e4f6b7067, // [7][0xdc] + 0xe245c91be0e84e12, 0xc3acbf05c5ce6fbe, 0xa1972527aaa40d4a, 0x807e53398f822ce6, // [7][0xe0] + 0x65e011637470c8a2, 0x4409677d5156e90e, 0x2632fd5f3e3c8bfa, 0x07db8b411b1aaa56, // [7][0xe4] + 0xd9d75fb9914ed019, 0xf83e29a7b468f1b5, 0x9a05b385db029341, 0xbbecc59bfe24b2ed, // [7][0xe8] + 0x5e7287c105d656a9, 0x7f9bf1df20f07705, 0x1da06bfd4f9a15f1, 0x3c491de36abc345d, // [7][0xec] + 0x9560e45f03a57204, 0xb4899241268353a8, 0xd6b2086349e9315c, 0xf75b7e7d6ccf10f0, // [7][0xf0] + 0x12c53c27973df4b4, 0x332c4a39b21bd518, 0x5117d01bdd71b7ec, 0x70fea605f8579640, // [7][0xf4] + 0xaef272fd7203ec0f, 0x8f1b04e35725cda3, 0xed209ec1384faf57, 0xccc9e8df1d698efb, // [7][0xf8] + 0x2957aa85e69b6abf, 0x08bedc9bc3bd4b13, 0x6a8546b9acd729e7, 0x4b6c30a789f1084b // [7][0xfc] + }}; + +/* big endian variant */ +static uint64_t crc64nvme_table_be[8][256] = { + { + 0x0000000000000000, 0x79893530c8f06e7f, 0xf2126b6090e1ddfe, 0x8b9b5e505811b381, // [0][0x00] + 0x8fb6419873e562c9, 0xf63f74a8bb150cb6, 0x7da42af8e304bf37, 0x042d1fc82bf4d148, // [0][0x04] + 0x75fe1468b4ec1ca6, 0x0c7721587c1c72d9, 0x87ec7f08240dc158, 0xfe654a38ecfdaf27, // [0][0x08] + 0xfa4855f0c7097e6f, 0x83c160c00ff91010, 0x085a3e9057e8a391, 0x71d30ba09f18cdee, // [0][0x0c] + 0x816fbe883bffe078, 0xf8e68bb8f30f8e07, 0x737dd5e8ab1e3d86, 0x0af4e0d863ee53f9, // [0][0x10] + 0x0ed9ff10481a82b1, 0x7750ca2080eaecce, 0xfccb9470d8fb5f4f, 0x8542a140100b3130, // [0][0x14] + 0xf491aae08f13fcde, 0x8d189fd047e392a1, 0x0683c1801ff22120, 0x7f0af4b0d7024f5f, // [0][0x18] + 0x7b27eb78fcf69e17, 0x02aede483406f068, 0x893580186c1743e9, 0xf0bcb528a4e72d96, // [0][0x1c] + 0x02df7c1177fec1f1, 0x7b564921bf0eaf8e, 0xf0cd1771e71f1c0f, 0x894422412fef7270, // [0][0x20] + 0x8d693d89041ba338, 0xf4e008b9ccebcd47, 0x7f7b56e994fa7ec6, 0x06f263d95c0a10b9, // [0][0x24] + 0x77216879c312dd57, 0x0ea85d490be2b328, 0x8533031953f300a9, 0xfcba36299b036ed6, // [0][0x28] + 0xf89729e1b0f7bf9e, 0x811e1cd17807d1e1, 0x0a85428120166260, 0x730c77b1e8e60c1f, // [0][0x2c] + 0x83b0c2994c012189, 0xfa39f7a984f14ff6, 0x71a2a9f9dce0fc77, 0x082b9cc914109208, // [0][0x30] + 0x0c0683013fe44340, 0x758fb631f7142d3f, 0xfe14e861af059ebe, 0x879ddd5167f5f0c1, // [0][0x34] + 0xf64ed6f1f8ed3d2f, 0x8fc7e3c1301d5350, 0x045cbd91680ce0d1, 0x7dd588a1a0fc8eae, // [0][0x38] + 0x79f897698b085fe6, 0x0071a25943f83199, 0x8beafc091be98218, 0xf263c939d319ec67, // [0][0x3c] + 0x6f2d6e7abdda5ad7, 0x16a45b4a752a34a8, 0x9d3f051a2d3b8729, 0xe4b6302ae5cbe956, // [0][0x40] + 0xe09b2fe2ce3f381e, 0x99121ad206cf5661, 0x128944825edee5e0, 0x6b0071b2962e8b9f, // [0][0x44] + 0x1ad37a1209364671, 0x635a4f22c1c6280e, 0xe8c1117299d79b8f, 0x914824425127f5f0, // [0][0x48] + 0x95653b8a7ad324b8, 0xecec0ebab2234ac7, 0x677750eaea32f946, 0x1efe65da22c29739, // [0][0x4c] + 0xee42d0f28625baaf, 0x97cbe5c24ed5d4d0, 0x1c50bb9216c46751, 0x65d98ea2de34092e, // [0][0x50] + 0x61f4916af5c0d866, 0x187da45a3d30b619, 0x93e6fa0a65210598, 0xea6fcf3aadd16be7, // [0][0x54] + 0x9bbcc49a32c9a609, 0xe235f1aafa39c876, 0x69aeaffaa2287bf7, 0x10279aca6ad81588, // [0][0x58] + 0x140a8502412cc4c0, 0x6d83b03289dcaabf, 0xe618ee62d1cd193e, 0x9f91db52193d7741, // [0][0x5c] + 0x6df2126bca249b26, 0x147b275b02d4f559, 0x9fe0790b5ac546d8, 0xe6694c3b923528a7, // [0][0x60] + 0xe24453f3b9c1f9ef, 0x9bcd66c371319790, 0x1056389329202411, 0x69df0da3e1d04a6e, // [0][0x64] + 0x180c06037ec88780, 0x61853333b638e9ff, 0xea1e6d63ee295a7e, 0x9397585326d93401, // [0][0x68] + 0x97ba479b0d2de549, 0xee3372abc5dd8b36, 0x65a82cfb9dcc38b7, 0x1c2119cb553c56c8, // [0][0x6c] + 0xec9dace3f1db7b5e, 0x951499d3392b1521, 0x1e8fc783613aa6a0, 0x6706f2b3a9cac8df, // [0][0x70] + 0x632bed7b823e1997, 0x1aa2d84b4ace77e8, 0x9139861b12dfc469, 0xe8b0b32bda2faa16, // [0][0x74] + 0x9963b88b453767f8, 0xe0ea8dbb8dc70987, 0x6b71d3ebd5d6ba06, 0x12f8e6db1d26d479, // [0][0x78] + 0x16d5f91336d20531, 0x6f5ccc23fe226b4e, 0xe4c79273a633d8cf, 0x9d4ea7436ec3b6b0, // [0][0x7c] + 0xb5c94bac29936c9a, 0xcc407e9ce16302e5, 0x47db20ccb972b164, 0x3e5215fc7182df1b, // [0][0x80] + 0x3a7f0a345a760e53, 0x43f63f049286602c, 0xc86d6154ca97d3ad, 0xb1e454640267bdd2, // [0][0x84] + 0xc0375fc49d7f703c, 0xb9be6af4558f1e43, 0x322534a40d9eadc2, 0x4bac0194c56ec3bd, // [0][0x88] + 0x4f811e5cee9a12f5, 0x36082b6c266a7c8a, 0xbd93753c7e7bcf0b, 0xc41a400cb68ba174, // [0][0x8c] + 0x34a6f524126c8ce2, 0x4d2fc014da9ce29d, 0xc6b49e44828d511c, 0xbf3dab744a7d3f63, // [0][0x90] + 0xbb10b4bc6189ee2b, 0xc299818ca9798054, 0x4902dfdcf16833d5, 0x308beaec39985daa, // [0][0x94] + 0x4158e14ca6809044, 0x38d1d47c6e70fe3b, 0xb34a8a2c36614dba, 0xcac3bf1cfe9123c5, // [0][0x98] + 0xceeea0d4d565f28d, 0xb76795e41d959cf2, 0x3cfccbb445842f73, 0x4575fe848d74410c, // [0][0x9c] + 0xb71637bd5e6dad6b, 0xce9f028d969dc314, 0x45045cddce8c7095, 0x3c8d69ed067c1eea, // [0][0xa0] + 0x38a076252d88cfa2, 0x41294315e578a1dd, 0xcab21d45bd69125c, 0xb33b287575997c23, // [0][0xa4] + 0xc2e823d5ea81b1cd, 0xbb6116e52271dfb2, 0x30fa48b57a606c33, 0x49737d85b290024c, // [0][0xa8] + 0x4d5e624d9964d304, 0x34d7577d5194bd7b, 0xbf4c092d09850efa, 0xc6c53c1dc1756085, // [0][0xac] + 0x3679893565924d13, 0x4ff0bc05ad62236c, 0xc46be255f57390ed, 0xbde2d7653d83fe92, // [0][0xb0] + 0xb9cfc8ad16772fda, 0xc046fd9dde8741a5, 0x4bdda3cd8696f224, 0x325496fd4e669c5b, // [0][0xb4] + 0x43879d5dd17e51b5, 0x3a0ea86d198e3fca, 0xb195f63d419f8c4b, 0xc81cc30d896fe234, // [0][0xb8] + 0xcc31dcc5a29b337c, 0xb5b8e9f56a6b5d03, 0x3e23b7a5327aee82, 0x47aa8295fa8a80fd, // [0][0xbc] + 0xdae425d69449364d, 0xa36d10e65cb95832, 0x28f64eb604a8ebb3, 0x517f7b86cc5885cc, // [0][0xc0] + 0x5552644ee7ac5484, 0x2cdb517e2f5c3afb, 0xa7400f2e774d897a, 0xdec93a1ebfbde705, // [0][0xc4] + 0xaf1a31be20a52aeb, 0xd693048ee8554494, 0x5d085adeb044f715, 0x24816fee78b4996a, // [0][0xc8] + 0x20ac702653404822, 0x592545169bb0265d, 0xd2be1b46c3a195dc, 0xab372e760b51fba3, // [0][0xcc] + 0x5b8b9b5eafb6d635, 0x2202ae6e6746b84a, 0xa999f03e3f570bcb, 0xd010c50ef7a765b4, // [0][0xd0] + 0xd43ddac6dc53b4fc, 0xadb4eff614a3da83, 0x262fb1a64cb26902, 0x5fa684968442077d, // [0][0xd4] + 0x2e758f361b5aca93, 0x57fcba06d3aaa4ec, 0xdc67e4568bbb176d, 0xa5eed166434b7912, // [0][0xd8] + 0xa1c3ceae68bfa85a, 0xd84afb9ea04fc625, 0x53d1a5cef85e75a4, 0x2a5890fe30ae1bdb, // [0][0xdc] + 0xd83b59c7e3b7f7bc, 0xa1b26cf72b4799c3, 0x2a2932a773562a42, 0x53a00797bba6443d, // [0][0xe0] + 0x578d185f90529575, 0x2e042d6f58a2fb0a, 0xa59f733f00b3488b, 0xdc16460fc84326f4, // [0][0xe4] + 0xadc54daf575beb1a, 0xd44c789f9fab8565, 0x5fd726cfc7ba36e4, 0x265e13ff0f4a589b, // [0][0xe8] + 0x22730c3724be89d3, 0x5bfa3907ec4ee7ac, 0xd0616757b45f542d, 0xa9e852677caf3a52, // [0][0xec] + 0x5954e74fd84817c4, 0x20ddd27f10b879bb, 0xab468c2f48a9ca3a, 0xd2cfb91f8059a445, // [0][0xf0] + 0xd6e2a6d7abad750d, 0xaf6b93e7635d1b72, 0x24f0cdb73b4ca8f3, 0x5d79f887f3bcc68c, // [0][0xf4] + 0x2caaf3276ca40b62, 0x5523c617a454651d, 0xdeb89847fc45d69c, 0xa731ad7734b5b8e3, // [0][0xf8] + 0xa31cb2bf1f4169ab, 0xda95878fd7b107d4, 0x510ed9df8fa0b455, 0x2887ecef4750da2a // [0][0xfc] + }, + { + 0x0000000000000000, 0x69dfbd737da97687, 0xb92decbfa974343a, 0xd0f251ccd4dd42bd, // [1][0x00] + 0x725bd87f53e96874, 0x1b84650c2e401ef3, 0xcb7634c0fa9d5c4e, 0xa2a989b387342ac9, // [1][0x04] + 0xe4b6b0ffa6d2d1e8, 0x8d690d8cdb7ba76f, 0x5d9b5c400fa6e5d2, 0x3444e133720f9355, // [1][0x08] + 0x96ed6880f53bb99c, 0xff32d5f38892cf1b, 0x2fc0843f5c4f8da6, 0x461f394c21e6fb21, // [1][0x0c] + 0xa3fef6a71e837ae5, 0xca214bd4632a0c62, 0x1ad31a18b7f74edf, 0x730ca76bca5e3858, // [1][0x10] + 0xd1a52ed84d6a1291, 0xb87a93ab30c36416, 0x6888c267e41e26ab, 0x01577f1499b7502c, // [1][0x14] + 0x47484658b851ab0d, 0x2e97fb2bc5f8dd8a, 0xfe65aae711259f37, 0x97ba17946c8ce9b0, // [1][0x18] + 0x35139e27ebb8c379, 0x5ccc23549611b5fe, 0x8c3e729842ccf743, 0xe5e1cfeb3f6581c4, // [1][0x1c] + 0x2d6e7a176e202cfe, 0x44b1c76413895a79, 0x944396a8c75418c4, 0xfd9c2bdbbafd6e43, // [1][0x20] + 0x5f35a2683dc9448a, 0x36ea1f1b4060320d, 0xe6184ed794bd70b0, 0x8fc7f3a4e9140637, // [1][0x24] + 0xc9d8cae8c8f2fd16, 0xa007779bb55b8b91, 0x70f526576186c92c, 0x192a9b241c2fbfab, // [1][0x28] + 0xbb8312979b1b9562, 0xd25cafe4e6b2e3e5, 0x02aefe28326fa158, 0x6b71435b4fc6d7df, // [1][0x2c] + 0x8e908cb070a3561b, 0xe74f31c30d0a209c, 0x37bd600fd9d76221, 0x5e62dd7ca47e14a6, // [1][0x30] + 0xfccb54cf234a3e6f, 0x9514e9bc5ee348e8, 0x45e6b8708a3e0a55, 0x2c390503f7977cd2, // [1][0x34] + 0x6a263c4fd67187f3, 0x03f9813cabd8f174, 0xd30bd0f07f05b3c9, 0xbad46d8302acc54e, // [1][0x38] + 0x187de4308598ef87, 0x71a25943f8319900, 0xa150088f2cecdbbd, 0xc88fb5fc5145ad3a, // [1][0x3c] + 0x314f63768f6681c8, 0x5890de05f2cff74f, 0x88628fc92612b5f2, 0xe1bd32ba5bbbc375, // [1][0x40] + 0x4314bb09dc8fe9bc, 0x2acb067aa1269f3b, 0xfa3957b675fbdd86, 0x93e6eac50852ab01, // [1][0x44] + 0xd5f9d38929b45020, 0xbc266efa541d26a7, 0x6cd43f3680c0641a, 0x050b8245fd69129d, // [1][0x48] + 0xa7a20bf67a5d3854, 0xce7db68507f44ed3, 0x1e8fe749d3290c6e, 0x77505a3aae807ae9, // [1][0x4c] + 0x92b195d191e5fb2d, 0xfb6e28a2ec4c8daa, 0x2b9c796e3891cf17, 0x4243c41d4538b990, // [1][0x50] + 0xe0ea4daec20c9359, 0x8935f0ddbfa5e5de, 0x59c7a1116b78a763, 0x30181c6216d1d1e4, // [1][0x54] + 0x7607252e37372ac5, 0x1fd8985d4a9e5c42, 0xcf2ac9919e431eff, 0xa6f574e2e3ea6878, // [1][0x58] + 0x045cfd5164de42b1, 0x6d83402219773436, 0xbd7111eecdaa768b, 0xd4aeac9db003000c, // [1][0x5c] + 0x1c211961e146ad36, 0x75fea4129cefdbb1, 0xa50cf5de4832990c, 0xccd348ad359bef8b, // [1][0x60] + 0x6e7ac11eb2afc542, 0x07a57c6dcf06b3c5, 0xd7572da11bdbf178, 0xbe8890d2667287ff, // [1][0x64] + 0xf897a99e47947cde, 0x914814ed3a3d0a59, 0x41ba4521eee048e4, 0x2865f85293493e63, // [1][0x68] + 0x8acc71e1147d14aa, 0xe313cc9269d4622d, 0x33e19d5ebd092090, 0x5a3e202dc0a05617, // [1][0x6c] + 0xbfdfefc6ffc5d7d3, 0xd60052b5826ca154, 0x06f2037956b1e3e9, 0x6f2dbe0a2b18956e, // [1][0x70] + 0xcd8437b9ac2cbfa7, 0xa45b8acad185c920, 0x74a9db0605588b9d, 0x1d76667578f1fd1a, // [1][0x74] + 0x5b695f395917063b, 0x32b6e24a24be70bc, 0xe244b386f0633201, 0x8b9b0ef58dca4486, // [1][0x78] + 0x293287460afe6e4f, 0x40ed3a35775718c8, 0x901f6bf9a38a5a75, 0xf9c0d68ade232cf2, // [1][0x7c] + 0x090d51b44debdba5, 0x60d2ecc73042ad22, 0xb020bd0be49fef9f, 0xd9ff007899369918, // [1][0x80] + 0x7b5689cb1e02b3d1, 0x128934b863abc556, 0xc27b6574b77687eb, 0xaba4d807cadff16c, // [1][0x84] + 0xedbbe14beb390a4d, 0x84645c3896907cca, 0x54960df4424d3e77, 0x3d49b0873fe448f0, // [1][0x88] + 0x9fe03934b8d06239, 0xf63f8447c57914be, 0x26cdd58b11a45603, 0x4f1268f86c0d2084, // [1][0x8c] + 0xaaf3a7135368a140, 0xc32c1a602ec1d7c7, 0x13de4bacfa1c957a, 0x7a01f6df87b5e3fd, // [1][0x90] + 0xd8a87f6c0081c934, 0xb177c21f7d28bfb3, 0x618593d3a9f5fd0e, 0x085a2ea0d45c8b89, // [1][0x94] + 0x4e4517ecf5ba70a8, 0x279aaa9f8813062f, 0xf768fb535cce4492, 0x9eb7462021673215, // [1][0x98] + 0x3c1ecf93a65318dc, 0x55c172e0dbfa6e5b, 0x8533232c0f272ce6, 0xecec9e5f728e5a61, // [1][0x9c] + 0x24632ba323cbf75b, 0x4dbc96d05e6281dc, 0x9d4ec71c8abfc361, 0xf4917a6ff716b5e6, // [1][0xa0] + 0x5638f3dc70229f2f, 0x3fe74eaf0d8be9a8, 0xef151f63d956ab15, 0x86caa210a4ffdd92, // [1][0xa4] + 0xc0d59b5c851926b3, 0xa90a262ff8b05034, 0x79f877e32c6d1289, 0x1027ca9051c4640e, // [1][0xa8] + 0xb28e4323d6f04ec7, 0xdb51fe50ab593840, 0x0ba3af9c7f847afd, 0x627c12ef022d0c7a, // [1][0xac] + 0x879ddd043d488dbe, 0xee42607740e1fb39, 0x3eb031bb943cb984, 0x576f8cc8e995cf03, // [1][0xb0] + 0xf5c6057b6ea1e5ca, 0x9c19b8081308934d, 0x4cebe9c4c7d5d1f0, 0x253454b7ba7ca777, // [1][0xb4] + 0x632b6dfb9b9a5c56, 0x0af4d088e6332ad1, 0xda06814432ee686c, 0xb3d93c374f471eeb, // [1][0xb8] + 0x1170b584c8733422, 0x78af08f7b5da42a5, 0xa85d593b61070018, 0xc182e4481cae769f, // [1][0xbc] + 0x384232c2c28d5a6d, 0x519d8fb1bf242cea, 0x816fde7d6bf96e57, 0xe8b0630e165018d0, // [1][0xc0] + 0x4a19eabd91643219, 0x23c657ceeccd449e, 0xf334060238100623, 0x9aebbb7145b970a4, // [1][0xc4] + 0xdcf4823d645f8b85, 0xb52b3f4e19f6fd02, 0x65d96e82cd2bbfbf, 0x0c06d3f1b082c938, // [1][0xc8] + 0xaeaf5a4237b6e3f1, 0xc770e7314a1f9576, 0x1782b6fd9ec2d7cb, 0x7e5d0b8ee36ba14c, // [1][0xcc] + 0x9bbcc465dc0e2088, 0xf2637916a1a7560f, 0x229128da757a14b2, 0x4b4e95a908d36235, // [1][0xd0] + 0xe9e71c1a8fe748fc, 0x8038a169f24e3e7b, 0x50caf0a526937cc6, 0x39154dd65b3a0a41, // [1][0xd4] + 0x7f0a749a7adcf160, 0x16d5c9e9077587e7, 0xc6279825d3a8c55a, 0xaff82556ae01b3dd, // [1][0xd8] + 0x0d51ace529359914, 0x648e1196549cef93, 0xb47c405a8041ad2e, 0xdda3fd29fde8dba9, // [1][0xdc] + 0x152c48d5acad7693, 0x7cf3f5a6d1040014, 0xac01a46a05d942a9, 0xc5de19197870342e, // [1][0xe0] + 0x677790aaff441ee7, 0x0ea82dd982ed6860, 0xde5a7c1556302add, 0xb785c1662b995c5a, // [1][0xe4] + 0xf19af82a0a7fa77b, 0x9845455977d6d1fc, 0x48b71495a30b9341, 0x2168a9e6dea2e5c6, // [1][0xe8] + 0x83c120555996cf0f, 0xea1e9d26243fb988, 0x3aeccceaf0e2fb35, 0x533371998d4b8db2, // [1][0xec] + 0xb6d2be72b22e0c76, 0xdf0d0301cf877af1, 0x0fff52cd1b5a384c, 0x6620efbe66f34ecb, // [1][0xf0] + 0xc489660de1c76402, 0xad56db7e9c6e1285, 0x7da48ab248b35038, 0x147b37c1351a26bf, // [1][0xf4] + 0x52640e8d14fcdd9e, 0x3bbbb3fe6955ab19, 0xeb49e232bd88e9a4, 0x82965f41c0219f23, // [1][0xf8] + 0x203fd6f24715b5ea, 0x49e06b813abcc36d, 0x99123a4dee6181d0, 0xf0cd873e93c8f757 // [1][0xfc] + }, + { + 0x0000000000000000, 0xbe38404e1f4e6eff, 0x17e217c46dba05ca, 0xa9da578a72f46b35, // [2][0x00] + 0x4557b8d08852d2a0, 0xfb6ff89e971cbc5f, 0x52b5af14e5e8d76a, 0xec8def5afaa6b995, // [2][0x04] + 0xe13de7f942837d75, 0x5f05a7b75dcd138a, 0xf6dff03d2f3978bf, 0x48e7b07330771640, // [2][0x08] + 0xa46a5f29cad1afd5, 0x1a521f67d59fc12a, 0xb38848eda76baa1f, 0x0db008a3b825c4e0, // [2][0x0c] + 0xc27bcef38506fbea, 0x7c438ebd9a489515, 0xd599d937e8bcfe20, 0x6ba19979f7f290df, // [2][0x10] + 0x872c76230d54294a, 0x3914366d121a47b5, 0x90ce61e760ee2c80, 0x2ef621a97fa0427f, // [2][0x14] + 0x2346290ac785869f, 0x9d7e6944d8cbe860, 0x34a43eceaa3f8355, 0x8a9c7e80b571edaa, // [2][0x18] + 0x661191da4fd7543f, 0xd829d19450993ac0, 0x71f3861e226d51f5, 0xcfcbc6503d233f0a, // [2][0x1c] + 0xef640bbf582b2fe1, 0x515c4bf14765411e, 0xf8861c7b35912a2b, 0x46be5c352adf44d4, // [2][0x20] + 0xaa33b36fd079fd41, 0x140bf321cf3793be, 0xbdd1a4abbdc3f88b, 0x03e9e4e5a28d9674, // [2][0x24] + 0x0e59ec461aa85294, 0xb061ac0805e63c6b, 0x19bbfb827712575e, 0xa783bbcc685c39a1, // [2][0x28] + 0x4b0e549692fa8034, 0xf53614d88db4eecb, 0x5cec4352ff4085fe, 0xe2d4031ce00eeb01, // [2][0x2c] + 0x2d1fc54cdd2dd40b, 0x93278502c263baf4, 0x3afdd288b097d1c1, 0x84c592c6afd9bf3e, // [2][0x30] + 0x68487d9c557f06ab, 0xd6703dd24a316854, 0x7faa6a5838c50361, 0xc1922a16278b6d9e, // [2][0x34] + 0xcc2222b59faea97e, 0x721a62fb80e0c781, 0xdbc03571f214acb4, 0x65f8753fed5ac24b, // [2][0x38] + 0x89759a6517fc7bde, 0x374dda2b08b21521, 0x9e978da17a467e14, 0x20afcdef650810eb, // [2][0x3c] + 0xb55a8126e27087f6, 0x0b62c168fd3ee909, 0xa2b896e28fca823c, 0x1c80d6ac9084ecc3, // [2][0x40] + 0xf00d39f66a225556, 0x4e3579b8756c3ba9, 0xe7ef2e320798509c, 0x59d76e7c18d63e63, // [2][0x44] + 0x546766dfa0f3fa83, 0xea5f2691bfbd947c, 0x4385711bcd49ff49, 0xfdbd3155d20791b6, // [2][0x48] + 0x1130de0f28a12823, 0xaf089e4137ef46dc, 0x06d2c9cb451b2de9, 0xb8ea89855a554316, // [2][0x4c] + 0x77214fd567767c1c, 0xc9190f9b783812e3, 0x60c358110acc79d6, 0xdefb185f15821729, // [2][0x50] + 0x3276f705ef24aebc, 0x8c4eb74bf06ac043, 0x2594e0c1829eab76, 0x9baca08f9dd0c589, // [2][0x54] + 0x961ca82c25f50169, 0x2824e8623abb6f96, 0x81febfe8484f04a3, 0x3fc6ffa657016a5c, // [2][0x58] + 0xd34b10fcada7d3c9, 0x6d7350b2b2e9bd36, 0xc4a90738c01dd603, 0x7a914776df53b8fc, // [2][0x5c] + 0x5a3e8a99ba5ba817, 0xe406cad7a515c6e8, 0x4ddc9d5dd7e1addd, 0xf3e4dd13c8afc322, // [2][0x60] + 0x1f69324932097ab7, 0xa15172072d471448, 0x088b258d5fb37f7d, 0xb6b365c340fd1182, // [2][0x64] + 0xbb036d60f8d8d562, 0x053b2d2ee796bb9d, 0xace17aa49562d0a8, 0x12d93aea8a2cbe57, // [2][0x68] + 0xfe54d5b0708a07c2, 0x406c95fe6fc4693d, 0xe9b6c2741d300208, 0x578e823a027e6cf7, // [2][0x6c] + 0x9845446a3f5d53fd, 0x267d042420133d02, 0x8fa753ae52e75637, 0x319f13e04da938c8, // [2][0x70] + 0xdd12fcbab70f815d, 0x632abcf4a841efa2, 0xcaf0eb7edab58497, 0x74c8ab30c5fbea68, // [2][0x74] + 0x7978a3937dde2e88, 0xc740e3dd62904077, 0x6e9ab45710642b42, 0xd0a2f4190f2a45bd, // [2][0x78] + 0x3c2f1b43f58cfc28, 0x82175b0deac292d7, 0x2bcd0c879836f9e2, 0x95f54cc98778971d, // [2][0x7c] + 0x0126951597c7d7d9, 0xbf1ed55b8889b926, 0x16c482d1fa7dd213, 0xa8fcc29fe533bcec, // [2][0x80] + 0x44712dc51f950579, 0xfa496d8b00db6b86, 0x53933a01722f00b3, 0xedab7a4f6d616e4c, // [2][0x84] + 0xe01b72ecd544aaac, 0x5e2332a2ca0ac453, 0xf7f96528b8feaf66, 0x49c12566a7b0c199, // [2][0x88] + 0xa54cca3c5d16780c, 0x1b748a72425816f3, 0xb2aeddf830ac7dc6, 0x0c969db62fe21339, // [2][0x8c] + 0xc35d5be612c12c33, 0x7d651ba80d8f42cc, 0xd4bf4c227f7b29f9, 0x6a870c6c60354706, // [2][0x90] + 0x860ae3369a93fe93, 0x3832a37885dd906c, 0x91e8f4f2f729fb59, 0x2fd0b4bce86795a6, // [2][0x94] + 0x2260bc1f50425146, 0x9c58fc514f0c3fb9, 0x3582abdb3df8548c, 0x8bbaeb9522b63a73, // [2][0x98] + 0x673704cfd81083e6, 0xd90f4481c75eed19, 0x70d5130bb5aa862c, 0xceed5345aae4e8d3, // [2][0x9c] + 0xee429eaacfecf838, 0x507adee4d0a296c7, 0xf9a0896ea256fdf2, 0x4798c920bd18930d, // [2][0xa0] + 0xab15267a47be2a98, 0x152d663458f04467, 0xbcf731be2a042f52, 0x02cf71f0354a41ad, // [2][0xa4] + 0x0f7f79538d6f854d, 0xb147391d9221ebb2, 0x189d6e97e0d58087, 0xa6a52ed9ff9bee78, // [2][0xa8] + 0x4a28c183053d57ed, 0xf41081cd1a733912, 0x5dcad64768875227, 0xe3f2960977c93cd8, // [2][0xac] + 0x2c3950594aea03d2, 0x9201101755a46d2d, 0x3bdb479d27500618, 0x85e307d3381e68e7, // [2][0xb0] + 0x696ee889c2b8d172, 0xd756a8c7ddf6bf8d, 0x7e8cff4daf02d4b8, 0xc0b4bf03b04cba47, // [2][0xb4] + 0xcd04b7a008697ea7, 0x733cf7ee17271058, 0xdae6a06465d37b6d, 0x64dee02a7a9d1592, // [2][0xb8] + 0x88530f70803bac07, 0x366b4f3e9f75c2f8, 0x9fb118b4ed81a9cd, 0x218958faf2cfc732, // [2][0xbc] + 0xb47c143375b7502f, 0x0a44547d6af93ed0, 0xa39e03f7180d55e5, 0x1da643b907433b1a, // [2][0xc0] + 0xf12bace3fde5828f, 0x4f13ecade2abec70, 0xe6c9bb27905f8745, 0x58f1fb698f11e9ba, // [2][0xc4] + 0x5541f3ca37342d5a, 0xeb79b384287a43a5, 0x42a3e40e5a8e2890, 0xfc9ba44045c0466f, // [2][0xc8] + 0x10164b1abf66fffa, 0xae2e0b54a0289105, 0x07f45cded2dcfa30, 0xb9cc1c90cd9294cf, // [2][0xcc] + 0x7607dac0f0b1abc5, 0xc83f9a8eefffc53a, 0x61e5cd049d0bae0f, 0xdfdd8d4a8245c0f0, // [2][0xd0] + 0x3350621078e37965, 0x8d68225e67ad179a, 0x24b275d415597caf, 0x9a8a359a0a171250, // [2][0xd4] + 0x973a3d39b232d6b0, 0x29027d77ad7cb84f, 0x80d82afddf88d37a, 0x3ee06ab3c0c6bd85, // [2][0xd8] + 0xd26d85e93a600410, 0x6c55c5a7252e6aef, 0xc58f922d57da01da, 0x7bb7d26348946f25, // [2][0xdc] + 0x5b181f8c2d9c7fce, 0xe5205fc232d21131, 0x4cfa084840267a04, 0xf2c248065f6814fb, // [2][0xe0] + 0x1e4fa75ca5cead6e, 0xa077e712ba80c391, 0x09adb098c874a8a4, 0xb795f0d6d73ac65b, // [2][0xe4] + 0xba25f8756f1f02bb, 0x041db83b70516c44, 0xadc7efb102a50771, 0x13ffafff1deb698e, // [2][0xe8] + 0xff7240a5e74dd01b, 0x414a00ebf803bee4, 0xe89057618af7d5d1, 0x56a8172f95b9bb2e, // [2][0xec] + 0x9963d17fa89a8424, 0x275b9131b7d4eadb, 0x8e81c6bbc52081ee, 0x30b986f5da6eef11, // [2][0xf0] + 0xdc3469af20c85684, 0x620c29e13f86387b, 0xcbd67e6b4d72534e, 0x75ee3e25523c3db1, // [2][0xf4] + 0x785e3686ea19f951, 0xc66676c8f55797ae, 0x6fbc214287a3fc9b, 0xd184610c98ed9264, // [2][0xf8] + 0x3d098e56624b2bf1, 0x8331ce187d05450e, 0x2aeb99920ff12e3b, 0x94d3d9dc10bf40c4 // [2][0xfc] + }, + { + 0x0000000000000000, 0x0663f9ba7c141182, 0x6755652daa0efb30, 0x61369c97d61aeab2, // [3][0x00] + 0xceaaca5a541df661, 0xc8c933e02809e7e3, 0xa9ffaf77fe130d51, 0xaf9c56cd82071cd3, // [3][0x04] + 0x9c5595b5a83aecc3, 0x9a366c0fd42efd41, 0xfb00f098023417f3, 0xfd6309227e200671, // [3][0x08] + 0x52ff5feffc271aa2, 0x549ca65580330b20, 0x35aa3ac25629e192, 0x33c9c3782a3df010, // [3][0x0c] + 0x5338bd33025301b3, 0x555b44897e471031, 0x346dd81ea85dfa83, 0x320e21a4d449eb01, // [3][0x10] + 0x9d927769564ef7d2, 0x9bf18ed32a5ae650, 0xfac71244fc400ce2, 0xfca4ebfe80541d60, // [3][0x14] + 0xcf6d2886aa69ed70, 0xc90ed13cd67dfcf2, 0xa8384dab00671640, 0xae5bb4117c7307c2, // [3][0x18] + 0x01c7e2dcfe741b11, 0x07a41b6682600a93, 0x669287f1547ae021, 0x60f17e4b286ef1a3, // [3][0x1c] + 0xcde3ed3f5780db52, 0xcb8014852b94cad0, 0xaab68812fd8e2062, 0xacd571a8819a31e0, // [3][0x20] + 0x03492765039d2d33, 0x052adedf7f893cb1, 0x641c4248a993d603, 0x627fbbf2d587c781, // [3][0x24] + 0x51b6788affba3791, 0x57d5813083ae2613, 0x36e31da755b4cca1, 0x3080e41d29a0dd23, // [3][0x28] + 0x9f1cb2d0aba7c1f0, 0x997f4b6ad7b3d072, 0xf849d7fd01a93ac0, 0xfe2a2e477dbd2b42, // [3][0x2c] + 0x9edb500c55d3dae1, 0x98b8a9b629c7cb63, 0xf98e3521ffdd21d1, 0xffedcc9b83c93053, // [3][0x30] + 0x50719a5601ce2c80, 0x561263ec7dda3d02, 0x3724ff7babc0d7b0, 0x314706c1d7d4c632, // [3][0x34] + 0x028ec5b9fde93622, 0x04ed3c0381fd27a0, 0x65dba09457e7cd12, 0x63b8592e2bf3dc90, // [3][0x38] + 0xcc240fe3a9f4c043, 0xca47f659d5e0d1c1, 0xab716ace03fa3b73, 0xad1293747fee2af1, // [3][0x3c] + 0x9ac7db7fae00b7a5, 0x9ca422c5d214a627, 0xfd92be52040e4c95, 0xfbf147e8781a5d17, // [3][0x40] + 0x546d1125fa1d41c4, 0x520ee89f86095046, 0x333874085013baf4, 0x355b8db22c07ab76, // [3][0x44] + 0x06924eca063a5b66, 0x00f1b7707a2e4ae4, 0x61c72be7ac34a056, 0x67a4d25dd020b1d4, // [3][0x48] + 0xc83884905227ad07, 0xce5b7d2a2e33bc85, 0xaf6de1bdf8295637, 0xa90e1807843d47b5, // [3][0x4c] + 0xc9ff664cac53b616, 0xcf9c9ff6d047a794, 0xaeaa0361065d4d26, 0xa8c9fadb7a495ca4, // [3][0x50] + 0x0755ac16f84e4077, 0x013655ac845a51f5, 0x6000c93b5240bb47, 0x666330812e54aac5, // [3][0x54] + 0x55aaf3f904695ad5, 0x53c90a43787d4b57, 0x32ff96d4ae67a1e5, 0x349c6f6ed273b067, // [3][0x58] + 0x9b0039a35074acb4, 0x9d63c0192c60bd36, 0xfc555c8efa7a5784, 0xfa36a534866e4606, // [3][0x5c] + 0x57243640f9806cf7, 0x5147cffa85947d75, 0x3071536d538e97c7, 0x3612aad72f9a8645, // [3][0x60] + 0x998efc1aad9d9a96, 0x9fed05a0d1898b14, 0xfedb9937079361a6, 0xf8b8608d7b877024, // [3][0x64] + 0xcb71a3f551ba8034, 0xcd125a4f2dae91b6, 0xac24c6d8fbb47b04, 0xaa473f6287a06a86, // [3][0x68] + 0x05db69af05a77655, 0x03b8901579b367d7, 0x628e0c82afa98d65, 0x64edf538d3bd9ce7, // [3][0x6c] + 0x041c8b73fbd36d44, 0x027f72c987c77cc6, 0x6349ee5e51dd9674, 0x652a17e42dc987f6, // [3][0x70] + 0xcab64129afce9b25, 0xccd5b893d3da8aa7, 0xade3240405c06015, 0xab80ddbe79d47197, // [3][0x74] + 0x98491ec653e98187, 0x9e2ae77c2ffd9005, 0xff1c7bebf9e77ab7, 0xf97f825185f36b35, // [3][0x78] + 0x56e3d49c07f477e6, 0x50802d267be06664, 0x31b6b1b1adfa8cd6, 0x37d5480bd1ee9d54, // [3][0x7c] + 0x5f1c20a70f27b77f, 0x597fd91d7333a6fd, 0x3849458aa5294c4f, 0x3e2abc30d93d5dcd, // [3][0x80] + 0x91b6eafd5b3a411e, 0x97d51347272e509c, 0xf6e38fd0f134ba2e, 0xf080766a8d20abac, // [3][0x84] + 0xc349b512a71d5bbc, 0xc52a4ca8db094a3e, 0xa41cd03f0d13a08c, 0xa27f29857107b10e, // [3][0x88] + 0x0de37f48f300addd, 0x0b8086f28f14bc5f, 0x6ab61a65590e56ed, 0x6cd5e3df251a476f, // [3][0x8c] + 0x0c249d940d74b6cc, 0x0a47642e7160a74e, 0x6b71f8b9a77a4dfc, 0x6d120103db6e5c7e, // [3][0x90] + 0xc28e57ce596940ad, 0xc4edae74257d512f, 0xa5db32e3f367bb9d, 0xa3b8cb598f73aa1f, // [3][0x94] + 0x90710821a54e5a0f, 0x9612f19bd95a4b8d, 0xf7246d0c0f40a13f, 0xf14794b67354b0bd, // [3][0x98] + 0x5edbc27bf153ac6e, 0x58b83bc18d47bdec, 0x398ea7565b5d575e, 0x3fed5eec274946dc, // [3][0x9c] + 0x92ffcd9858a76c2d, 0x949c342224b37daf, 0xf5aaa8b5f2a9971d, 0xf3c9510f8ebd869f, // [3][0xa0] + 0x5c5507c20cba9a4c, 0x5a36fe7870ae8bce, 0x3b0062efa6b4617c, 0x3d639b55daa070fe, // [3][0xa4] + 0x0eaa582df09d80ee, 0x08c9a1978c89916c, 0x69ff3d005a937bde, 0x6f9cc4ba26876a5c, // [3][0xa8] + 0xc0009277a480768f, 0xc6636bcdd894670d, 0xa755f75a0e8e8dbf, 0xa1360ee0729a9c3d, // [3][0xac] + 0xc1c770ab5af46d9e, 0xc7a4891126e07c1c, 0xa6921586f0fa96ae, 0xa0f1ec3c8cee872c, // [3][0xb0] + 0x0f6dbaf10ee99bff, 0x090e434b72fd8a7d, 0x6838dfdca4e760cf, 0x6e5b2666d8f3714d, // [3][0xb4] + 0x5d92e51ef2ce815d, 0x5bf11ca48eda90df, 0x3ac7803358c07a6d, 0x3ca4798924d46bef, // [3][0xb8] + 0x93382f44a6d3773c, 0x955bd6fedac766be, 0xf46d4a690cdd8c0c, 0xf20eb3d370c99d8e, // [3][0xbc] + 0xc5dbfbd8a12700da, 0xc3b80262dd331158, 0xa28e9ef50b29fbea, 0xa4ed674f773dea68, // [3][0xc0] + 0x0b713182f53af6bb, 0x0d12c838892ee739, 0x6c2454af5f340d8b, 0x6a47ad1523201c09, // [3][0xc4] + 0x598e6e6d091dec19, 0x5fed97d77509fd9b, 0x3edb0b40a3131729, 0x38b8f2fadf0706ab, // [3][0xc8] + 0x9724a4375d001a78, 0x91475d8d21140bfa, 0xf071c11af70ee148, 0xf61238a08b1af0ca, // [3][0xcc] + 0x96e346eba3740169, 0x9080bf51df6010eb, 0xf1b623c6097afa59, 0xf7d5da7c756eebdb, // [3][0xd0] + 0x58498cb1f769f708, 0x5e2a750b8b7de68a, 0x3f1ce99c5d670c38, 0x397f102621731dba, // [3][0xd4] + 0x0ab6d35e0b4eedaa, 0x0cd52ae4775afc28, 0x6de3b673a140169a, 0x6b804fc9dd540718, // [3][0xd8] + 0xc41c19045f531bcb, 0xc27fe0be23470a49, 0xa3497c29f55de0fb, 0xa52a85938949f179, // [3][0xdc] + 0x083816e7f6a7db88, 0x0e5bef5d8ab3ca0a, 0x6f6d73ca5ca920b8, 0x690e8a7020bd313a, // [3][0xe0] + 0xc692dcbda2ba2de9, 0xc0f12507deae3c6b, 0xa1c7b99008b4d6d9, 0xa7a4402a74a0c75b, // [3][0xe4] + 0x946d83525e9d374b, 0x920e7ae8228926c9, 0xf338e67ff493cc7b, 0xf55b1fc58887ddf9, // [3][0xe8] + 0x5ac749080a80c12a, 0x5ca4b0b27694d0a8, 0x3d922c25a08e3a1a, 0x3bf1d59fdc9a2b98, // [3][0xec] + 0x5b00abd4f4f4da3b, 0x5d63526e88e0cbb9, 0x3c55cef95efa210b, 0x3a36374322ee3089, // [3][0xf0] + 0x95aa618ea0e92c5a, 0x93c99834dcfd3dd8, 0xf2ff04a30ae7d76a, 0xf49cfd1976f3c6e8, // [3][0xf4] + 0xc7553e615cce36f8, 0xc136c7db20da277a, 0xa0005b4cf6c0cdc8, 0xa663a2f68ad4dc4a, // [3][0xf8] + 0x09fff43b08d3c099, 0x0f9c0d8174c7d11b, 0x6eaa9116a2dd3ba9, 0x68c968acdec92a2b // [3][0xfc] + }, + { + 0x0000000000000000, 0x1e5d9084f7153d37, 0x3cba2009ef2b7a6e, 0x22e7b08d183e4759, // [4][0x00] + 0x78744112de57f4dc, 0x6629d1962942c9eb, 0x44ce611b317c8eb2, 0x5a93f19fc669b385, // [4][0x04] + 0x9b7b157cef89318d, 0x852685f8189c0cba, 0xa7c1357500a24be3, 0xb99ca5f1f7b776d4, // [4][0x08] + 0xe30f546e31dec551, 0xfd52c4eac6cbf866, 0xdfb57467def5bf3f, 0xc1e8e4e329e08208, // [4][0x0c] + 0x5d64bda08d35ba2e, 0x43392d247a208719, 0x61de9da9621ec040, 0x7f830d2d950bfd77, // [4][0x10] + 0x2510fcb253624ef2, 0x3b4d6c36a47773c5, 0x19aadcbbbc49349c, 0x07f74c3f4b5c09ab, // [4][0x14] + 0xc61fa8dc62bc8ba3, 0xd842385895a9b694, 0xfaa588d58d97f1cd, 0xe4f818517a82ccfa, // [4][0x18] + 0xbe6be9cebceb7f7f, 0xa036794a4bfe4248, 0x82d1c9c753c00511, 0x9c8c5943a4d53826, // [4][0x1c] + 0xbac87a411b6b745d, 0xa495eac5ec7e496a, 0x86725a48f4400e33, 0x982fcacc03553304, // [4][0x20] + 0xc2bc3b53c53c8081, 0xdce1abd73229bdb6, 0xfe061b5a2a17faef, 0xe05b8bdedd02c7d8, // [4][0x24] + 0x21b36f3df4e245d0, 0x3feeffb903f778e7, 0x1d094f341bc93fbe, 0x0354dfb0ecdc0289, // [4][0x28] + 0x59c72e2f2ab5b10c, 0x479abeabdda08c3b, 0x657d0e26c59ecb62, 0x7b209ea2328bf655, // [4][0x2c] + 0xe7acc7e1965ece73, 0xf9f15765614bf344, 0xdb16e7e87975b41d, 0xc54b776c8e60892a, // [4][0x30] + 0x9fd886f348093aaf, 0x81851677bf1c0798, 0xa362a6faa72240c1, 0xbd3f367e50377df6, // [4][0x34] + 0x7cd7d29d79d7fffe, 0x628a42198ec2c2c9, 0x406df29496fc8590, 0x5e30621061e9b8a7, // [4][0x38] + 0x04a3938fa7800b22, 0x1afe030b50953615, 0x3819b38648ab714c, 0x26442302bfbe4c7b, // [4][0x3c] + 0x7491f58236d6e8ba, 0x6acc6506c1c3d58d, 0x482bd58bd9fd92d4, 0x5676450f2ee8afe3, // [4][0x40] + 0x0ce5b490e8811c66, 0x12b824141f942151, 0x305f949907aa6608, 0x2e02041df0bf5b3f, // [4][0x44] + 0xefeae0fed95fd937, 0xf1b7707a2e4ae400, 0xd350c0f73674a359, 0xcd0d5073c1619e6e, // [4][0x48] + 0x979ea1ec07082deb, 0x89c33168f01d10dc, 0xab2481e5e8235785, 0xb57911611f366ab2, // [4][0x4c] + 0x29f54822bbe35294, 0x37a8d8a64cf66fa3, 0x154f682b54c828fa, 0x0b12f8afa3dd15cd, // [4][0x50] + 0x5181093065b4a648, 0x4fdc99b492a19b7f, 0x6d3b29398a9fdc26, 0x7366b9bd7d8ae111, // [4][0x54] + 0xb28e5d5e546a6319, 0xacd3cddaa37f5e2e, 0x8e347d57bb411977, 0x9069edd34c542440, // [4][0x58] + 0xcafa1c4c8a3d97c5, 0xd4a78cc87d28aaf2, 0xf6403c456516edab, 0xe81dacc19203d09c, // [4][0x5c] + 0xce598fc32dbd9ce7, 0xd0041f47daa8a1d0, 0xf2e3afcac296e689, 0xecbe3f4e3583dbbe, // [4][0x60] + 0xb62dced1f3ea683b, 0xa8705e5504ff550c, 0x8a97eed81cc11255, 0x94ca7e5cebd42f62, // [4][0x64] + 0x55229abfc234ad6a, 0x4b7f0a3b3521905d, 0x6998bab62d1fd704, 0x77c52a32da0aea33, // [4][0x68] + 0x2d56dbad1c6359b6, 0x330b4b29eb766481, 0x11ecfba4f34823d8, 0x0fb16b20045d1eef, // [4][0x6c] + 0x933d3263a08826c9, 0x8d60a2e7579d1bfe, 0xaf87126a4fa35ca7, 0xb1da82eeb8b66190, // [4][0x70] + 0xeb4973717edfd215, 0xf514e3f589caef22, 0xd7f3537891f4a87b, 0xc9aec3fc66e1954c, // [4][0x74] + 0x0846271f4f011744, 0x161bb79bb8142a73, 0x34fc0716a02a6d2a, 0x2aa19792573f501d, // [4][0x78] + 0x7032660d9156e398, 0x6e6ff6896643deaf, 0x4c8846047e7d99f6, 0x52d5d6808968a4c1, // [4][0x7c] + 0x83b17c5d3e8a0841, 0x9dececd9c99f3576, 0xbf0b5c54d1a1722f, 0xa156ccd026b44f18, // [4][0x80] + 0xfbc53d4fe0ddfc9d, 0xe598adcb17c8c1aa, 0xc77f1d460ff686f3, 0xd9228dc2f8e3bbc4, // [4][0x84] + 0x18ca6921d10339cc, 0x0697f9a5261604fb, 0x247049283e2843a2, 0x3a2dd9acc93d7e95, // [4][0x88] + 0x60be28330f54cd10, 0x7ee3b8b7f841f027, 0x5c04083ae07fb77e, 0x425998be176a8a49, // [4][0x8c] + 0xded5c1fdb3bfb26f, 0xc088517944aa8f58, 0xe26fe1f45c94c801, 0xfc327170ab81f536, // [4][0x90] + 0xa6a180ef6de846b3, 0xb8fc106b9afd7b84, 0x9a1ba0e682c33cdd, 0x8446306275d601ea, // [4][0x94] + 0x45aed4815c3683e2, 0x5bf34405ab23bed5, 0x7914f488b31df98c, 0x6749640c4408c4bb, // [4][0x98] + 0x3dda95938261773e, 0x2387051775744a09, 0x0160b59a6d4a0d50, 0x1f3d251e9a5f3067, // [4][0x9c] + 0x3979061c25e17c1c, 0x27249698d2f4412b, 0x05c32615caca0672, 0x1b9eb6913ddf3b45, // [4][0xa0] + 0x410d470efbb688c0, 0x5f50d78a0ca3b5f7, 0x7db76707149df2ae, 0x63eaf783e388cf99, // [4][0xa4] + 0xa2021360ca684d91, 0xbc5f83e43d7d70a6, 0x9eb83369254337ff, 0x80e5a3edd2560ac8, // [4][0xa8] + 0xda765272143fb94d, 0xc42bc2f6e32a847a, 0xe6cc727bfb14c323, 0xf891e2ff0c01fe14, // [4][0xac] + 0x641dbbbca8d4c632, 0x7a402b385fc1fb05, 0x58a79bb547ffbc5c, 0x46fa0b31b0ea816b, // [4][0xb0] + 0x1c69faae768332ee, 0x02346a2a81960fd9, 0x20d3daa799a84880, 0x3e8e4a236ebd75b7, // [4][0xb4] + 0xff66aec0475df7bf, 0xe13b3e44b048ca88, 0xc3dc8ec9a8768dd1, 0xdd811e4d5f63b0e6, // [4][0xb8] + 0x8712efd2990a0363, 0x994f7f566e1f3e54, 0xbba8cfdb7621790d, 0xa5f55f5f8134443a, // [4][0xbc] + 0xf72089df085ce0fb, 0xe97d195bff49ddcc, 0xcb9aa9d6e7779a95, 0xd5c739521062a7a2, // [4][0xc0] + 0x8f54c8cdd60b1427, 0x91095849211e2910, 0xb3eee8c439206e49, 0xadb37840ce35537e, // [4][0xc4] + 0x6c5b9ca3e7d5d176, 0x72060c2710c0ec41, 0x50e1bcaa08feab18, 0x4ebc2c2effeb962f, // [4][0xc8] + 0x142fddb1398225aa, 0x0a724d35ce97189d, 0x2895fdb8d6a95fc4, 0x36c86d3c21bc62f3, // [4][0xcc] + 0xaa44347f85695ad5, 0xb419a4fb727c67e2, 0x96fe14766a4220bb, 0x88a384f29d571d8c, // [4][0xd0] + 0xd230756d5b3eae09, 0xcc6de5e9ac2b933e, 0xee8a5564b415d467, 0xf0d7c5e04300e950, // [4][0xd4] + 0x313f21036ae06b58, 0x2f62b1879df5566f, 0x0d85010a85cb1136, 0x13d8918e72de2c01, // [4][0xd8] + 0x494b6011b4b79f84, 0x5716f09543a2a2b3, 0x75f140185b9ce5ea, 0x6bacd09cac89d8dd, // [4][0xdc] + 0x4de8f39e133794a6, 0x53b5631ae422a991, 0x7152d397fc1ceec8, 0x6f0f43130b09d3ff, // [4][0xe0] + 0x359cb28ccd60607a, 0x2bc122083a755d4d, 0x09269285224b1a14, 0x177b0201d55e2723, // [4][0xe4] + 0xd693e6e2fcbea52b, 0xc8ce76660bab981c, 0xea29c6eb1395df45, 0xf474566fe480e272, // [4][0xe8] + 0xaee7a7f022e951f7, 0xb0ba3774d5fc6cc0, 0x925d87f9cdc22b99, 0x8c00177d3ad716ae, // [4][0xec] + 0x108c4e3e9e022e88, 0x0ed1deba691713bf, 0x2c366e37712954e6, 0x326bfeb3863c69d1, // [4][0xf0] + 0x68f80f2c4055da54, 0x76a59fa8b740e763, 0x54422f25af7ea03a, 0x4a1fbfa1586b9d0d, // [4][0xf4] + 0x8bf75b42718b1f05, 0x95aacbc6869e2232, 0xb74d7b4b9ea0656b, 0xa910ebcf69b5585c, // [4][0xf8] + 0xf3831a50afdcebd9, 0xedde8ad458c9d6ee, 0xcf393a5940f791b7, 0xd164aaddb7e2ac80 // [4][0xfc] + }, + { + 0x0000000000000000, 0xd4a504ef792a74e9, 0xc3d89e86a07231e6, 0x177d9a69d958450f, // [5][0x00] + 0xed22aa5512c3bbf8, 0x3987aeba6be9cf11, 0x2efa34d3b2b18a1e, 0xfa5f303ccb9bfef7, // [5][0x04] + 0xb1d6c3f377a0aec5, 0x6573c71c0e8ada2c, 0x720e5d75d7d29f23, 0xa6ab599aaef8ebca, // [5][0x08] + 0x5cf469a66563153d, 0x88516d491c4961d4, 0x9f2cf720c51124db, 0x4b89f3cfbc3b5032, // [5][0x0c] + 0x093e10bfbc6684bf, 0xdd9b1450c54cf056, 0xcae68e391c14b559, 0x1e438ad6653ec1b0, // [5][0x10] + 0xe41cbaeaaea53f47, 0x30b9be05d78f4bae, 0x27c4246c0ed70ea1, 0xf361208377fd7a48, // [5][0x14] + 0xb8e8d34ccbc62a7a, 0x6c4dd7a3b2ec5e93, 0x7b304dca6bb41b9c, 0xaf954925129e6f75, // [5][0x18] + 0x55ca7919d9059182, 0x816f7df6a02fe56b, 0x9612e79f7977a064, 0x42b7e370005dd48d, // [5][0x1c] + 0x79efb7262aebd14b, 0xad4ab3c953c1a5a2, 0xba3729a08a99e0ad, 0x6e922d4ff3b39444, // [5][0x20] + 0x94cd1d7338286ab3, 0x4068199c41021e5a, 0x571583f5985a5b55, 0x83b0871ae1702fbc, // [5][0x24] + 0xc83974d55d4b7f8e, 0x1c9c703a24610b67, 0x0be1ea53fd394e68, 0xdf44eebc84133a81, // [5][0x28] + 0x251bde804f88c476, 0xf1beda6f36a2b09f, 0xe6c34006effaf590, 0x326644e996d08179, // [5][0x2c] + 0x70d1a799968d55f4, 0xa474a376efa7211d, 0xb309391f36ff6412, 0x67ac3df04fd510fb, // [5][0x30] + 0x9df30dcc844eee0c, 0x49560923fd649ae5, 0x5e2b934a243cdfea, 0x8a8e97a55d16ab03, // [5][0x34] + 0xc107646ae12dfb31, 0x15a2608598078fd8, 0x02dffaec415fcad7, 0xd67afe033875be3e, // [5][0x38] + 0x2c25ce3ff3ee40c9, 0xf880cad08ac43420, 0xeffd50b9539c712f, 0x3b5854562ab605c6, // [5][0x3c] + 0xf2de6f4d54d6a397, 0x267b6ba22dfcd77e, 0x3106f1cbf4a49271, 0xe5a3f5248d8ee698, // [5][0x40] + 0x1ffcc5184615186f, 0xcb59c1f73f3f6c86, 0xdc245b9ee6672989, 0x08815f719f4d5d60, // [5][0x44] + 0x4308acbe23760d52, 0x97ada8515a5c79bb, 0x80d0323883043cb4, 0x547536d7fa2e485d, // [5][0x48] + 0xae2a06eb31b5b6aa, 0x7a8f0204489fc243, 0x6df2986d91c7874c, 0xb9579c82e8edf3a5, // [5][0x4c] + 0xfbe07ff2e8b02728, 0x2f457b1d919a53c1, 0x3838e17448c216ce, 0xec9de59b31e86227, // [5][0x50] + 0x16c2d5a7fa739cd0, 0xc267d1488359e839, 0xd51a4b215a01ad36, 0x01bf4fce232bd9df, // [5][0x54] + 0x4a36bc019f1089ed, 0x9e93b8eee63afd04, 0x89ee22873f62b80b, 0x5d4b26684648cce2, // [5][0x58] + 0xa71416548dd33215, 0x73b112bbf4f946fc, 0x64cc88d22da103f3, 0xb0698c3d548b771a, // [5][0x5c] + 0x8b31d86b7e3d72dc, 0x5f94dc8407170635, 0x48e946edde4f433a, 0x9c4c4202a76537d3, // [5][0x60] + 0x6613723e6cfec924, 0xb2b676d115d4bdcd, 0xa5cbecb8cc8cf8c2, 0x716ee857b5a68c2b, // [5][0x64] + 0x3ae71b98099ddc19, 0xee421f7770b7a8f0, 0xf93f851ea9efedff, 0x2d9a81f1d0c59916, // [5][0x68] + 0xd7c5b1cd1b5e67e1, 0x0360b52262741308, 0x141d2f4bbb2c5607, 0xc0b82ba4c20622ee, // [5][0x6c] + 0x820fc8d4c25bf663, 0x56aacc3bbb71828a, 0x41d756526229c785, 0x957252bd1b03b36c, // [5][0x70] + 0x6f2d6281d0984d9b, 0xbb88666ea9b23972, 0xacf5fc0770ea7c7d, 0x7850f8e809c00894, // [5][0x74] + 0x33d90b27b5fb58a6, 0xe77c0fc8ccd12c4f, 0xf00195a115896940, 0x24a4914e6ca31da9, // [5][0x78] + 0xdefba172a738e35e, 0x0a5ea59dde1297b7, 0x1d233ff4074ad2b8, 0xc9863b1b7e60a651, // [5][0x7c] + 0x8f2e48c2fb8a9e1b, 0x5b8b4c2d82a0eaf2, 0x4cf6d6445bf8affd, 0x9853d2ab22d2db14, // [5][0x80] + 0x620ce297e94925e3, 0xb6a9e6789063510a, 0xa1d47c11493b1405, 0x757178fe301160ec, // [5][0x84] + 0x3ef88b318c2a30de, 0xea5d8fdef5004437, 0xfd2015b72c580138, 0x29851158557275d1, // [5][0x88] + 0xd3da21649ee98b26, 0x077f258be7c3ffcf, 0x1002bfe23e9bbac0, 0xc4a7bb0d47b1ce29, // [5][0x8c] + 0x8610587d47ec1aa4, 0x52b55c923ec66e4d, 0x45c8c6fbe79e2b42, 0x916dc2149eb45fab, // [5][0x90] + 0x6b32f228552fa15c, 0xbf97f6c72c05d5b5, 0xa8ea6caef55d90ba, 0x7c4f68418c77e453, // [5][0x94] + 0x37c69b8e304cb461, 0xe3639f614966c088, 0xf41e0508903e8587, 0x20bb01e7e914f16e, // [5][0x98] + 0xdae431db228f0f99, 0x0e4135345ba57b70, 0x193caf5d82fd3e7f, 0xcd99abb2fbd74a96, // [5][0x9c] + 0xf6c1ffe4d1614f50, 0x2264fb0ba84b3bb9, 0x3519616271137eb6, 0xe1bc658d08390a5f, // [5][0xa0] + 0x1be355b1c3a2f4a8, 0xcf46515eba888041, 0xd83bcb3763d0c54e, 0x0c9ecfd81afab1a7, // [5][0xa4] + 0x47173c17a6c1e195, 0x93b238f8dfeb957c, 0x84cfa29106b3d073, 0x506aa67e7f99a49a, // [5][0xa8] + 0xaa359642b4025a6d, 0x7e9092adcd282e84, 0x69ed08c414706b8b, 0xbd480c2b6d5a1f62, // [5][0xac] + 0xffffef5b6d07cbef, 0x2b5aebb4142dbf06, 0x3c2771ddcd75fa09, 0xe8827532b45f8ee0, // [5][0xb0] + 0x12dd450e7fc47017, 0xc67841e106ee04fe, 0xd105db88dfb641f1, 0x05a0df67a69c3518, // [5][0xb4] + 0x4e292ca81aa7652a, 0x9a8c2847638d11c3, 0x8df1b22ebad554cc, 0x5954b6c1c3ff2025, // [5][0xb8] + 0xa30b86fd0864ded2, 0x77ae8212714eaa3b, 0x60d3187ba816ef34, 0xb4761c94d13c9bdd, // [5][0xbc] + 0x7df0278faf5c3d8c, 0xa9552360d6764965, 0xbe28b9090f2e0c6a, 0x6a8dbde676047883, // [5][0xc0] + 0x90d28ddabd9f8674, 0x44778935c4b5f29d, 0x530a135c1dedb792, 0x87af17b364c7c37b, // [5][0xc4] + 0xcc26e47cd8fc9349, 0x1883e093a1d6e7a0, 0x0ffe7afa788ea2af, 0xdb5b7e1501a4d646, // [5][0xc8] + 0x21044e29ca3f28b1, 0xf5a14ac6b3155c58, 0xe2dcd0af6a4d1957, 0x3679d44013676dbe, // [5][0xcc] + 0x74ce3730133ab933, 0xa06b33df6a10cdda, 0xb716a9b6b34888d5, 0x63b3ad59ca62fc3c, // [5][0xd0] + 0x99ec9d6501f902cb, 0x4d49998a78d37622, 0x5a3403e3a18b332d, 0x8e91070cd8a147c4, // [5][0xd4] + 0xc518f4c3649a17f6, 0x11bdf02c1db0631f, 0x06c06a45c4e82610, 0xd2656eaabdc252f9, // [5][0xd8] + 0x283a5e967659ac0e, 0xfc9f5a790f73d8e7, 0xebe2c010d62b9de8, 0x3f47c4ffaf01e901, // [5][0xdc] + 0x041f90a985b7ecc7, 0xd0ba9446fc9d982e, 0xc7c70e2f25c5dd21, 0x13620ac05cefa9c8, // [5][0xe0] + 0xe93d3afc9774573f, 0x3d983e13ee5e23d6, 0x2ae5a47a370666d9, 0xfe40a0954e2c1230, // [5][0xe4] + 0xb5c9535af2174202, 0x616c57b58b3d36eb, 0x7611cddc526573e4, 0xa2b4c9332b4f070d, // [5][0xe8] + 0x58ebf90fe0d4f9fa, 0x8c4efde099fe8d13, 0x9b33678940a6c81c, 0x4f966366398cbcf5, // [5][0xec] + 0x0d21801639d16878, 0xd98484f940fb1c91, 0xcef91e9099a3599e, 0x1a5c1a7fe0892d77, // [5][0xf0] + 0xe0032a432b12d380, 0x34a62eac5238a769, 0x23dbb4c58b60e266, 0xf77eb02af24a968f, // [5][0xf4] + 0xbcf743e54e71c6bd, 0x6852470a375bb254, 0x7f2fdd63ee03f75b, 0xab8ad98c972983b2, // [5][0xf8] + 0x51d5e9b05cb27d45, 0x8570ed5f259809ac, 0x920d7736fcc04ca3, 0x46a873d985ea384a // [5][0xfc] + }, + { + 0x0000000000000000, 0x713935bff6275dfc, 0x89e1fd26be6963cc, 0xf8d8c899484e3e30, // [6][0x00] + 0x79506c152ff51fac, 0x086959aad9d24250, 0xf0b19133919c7c60, 0x8188a48c67bb219c, // [6][0x04] + 0x99334f720dcce66c, 0xe80a7acdfbebbb90, 0x10d2b254b3a585a0, 0x61eb87eb4582d85c, // [6][0x08] + 0xe06323672239f9c0, 0x915a16d8d41ea43c, 0x6982de419c509a0c, 0x18bbebfe6a77c7f0, // [6][0x0c] + 0x32679ee41a98cdd9, 0x435eab5becbf9025, 0xbb8663c2a4f1ae15, 0xcabf567d52d6f3e9, // [6][0x10] + 0x4b37f2f1356dd275, 0x3a0ec74ec34a8f89, 0xc2d60fd78b04b1b9, 0xb3ef3a687d23ec45, // [6][0x14] + 0xab54d19617542bb5, 0xda6de429e1737649, 0x22b52cb0a93d4879, 0x538c190f5f1a1585, // [6][0x18] + 0xd204bd8338a13419, 0xa33d883cce8669e5, 0x5be540a586c857d5, 0x2adc751a70ef0a29, // [6][0x1c] + 0x0f5dab9166164287, 0x7e649e2e90311f7b, 0x86bc56b7d87f214b, 0xf78563082e587cb7, // [6][0x20] + 0x760dc78449e35d2b, 0x0734f23bbfc400d7, 0xffec3aa2f78a3ee7, 0x8ed50f1d01ad631b, // [6][0x24] + 0x966ee4e36bdaa4eb, 0xe757d15c9dfdf917, 0x1f8f19c5d5b3c727, 0x6eb62c7a23949adb, // [6][0x28] + 0xef3e88f6442fbb47, 0x9e07bd49b208e6bb, 0x66df75d0fa46d88b, 0x17e6406f0c618577, // [6][0x2c] + 0x3d3a35757c8e8f5e, 0x4c0300ca8aa9d2a2, 0xb4dbc853c2e7ec92, 0xc5e2fdec34c0b16e, // [6][0x30] + 0x446a5960537b90f2, 0x35536cdfa55ccd0e, 0xcd8ba446ed12f33e, 0xbcb291f91b35aec2, // [6][0x34] + 0xa4097a0771426932, 0xd5304fb8876534ce, 0x2de88721cf2b0afe, 0x5cd1b29e390c5702, // [6][0x38] + 0xdd5916125eb7769e, 0xac6023ada8902b62, 0x54b8eb34e0de1552, 0x2581de8b16f948ae, // [6][0x3c] + 0x7529c17b9e0a5d3a, 0x0410f4c4682d00c6, 0xfcc83c5d20633ef6, 0x8df109e2d644630a, // [6][0x40] + 0x0c79ad6eb1ff4296, 0x7d4098d147d81f6a, 0x859850480f96215a, 0xf4a165f7f9b17ca6, // [6][0x44] + 0xec1a8e0993c6bb56, 0x9d23bbb665e1e6aa, 0x65fb732f2dafd89a, 0x14c24690db888566, // [6][0x48] + 0x954ae21cbc33a4fa, 0xe473d7a34a14f906, 0x1cab1f3a025ac736, 0x6d922a85f47d9aca, // [6][0x4c] + 0x474e5f9f849290e3, 0x36776a2072b5cd1f, 0xceafa2b93afbf32f, 0xbf969706ccdcaed3, // [6][0x50] + 0x3e1e338aab678f4f, 0x4f2706355d40d2b3, 0xb7ffceac150eec83, 0xc6c6fb13e329b17f, // [6][0x54] + 0xde7d10ed895e768f, 0xaf4425527f792b73, 0x579cedcb37371543, 0x26a5d874c11048bf, // [6][0x58] + 0xa72d7cf8a6ab6923, 0xd6144947508c34df, 0x2ecc81de18c20aef, 0x5ff5b461eee55713, // [6][0x5c] + 0x7a746aeaf81c1fbd, 0x0b4d5f550e3b4241, 0xf39597cc46757c71, 0x82aca273b052218d, // [6][0x60] + 0x032406ffd7e90011, 0x721d334021ce5ded, 0x8ac5fbd9698063dd, 0xfbfcce669fa73e21, // [6][0x64] + 0xe3472598f5d0f9d1, 0x927e102703f7a42d, 0x6aa6d8be4bb99a1d, 0x1b9fed01bd9ec7e1, // [6][0x68] + 0x9a17498dda25e67d, 0xeb2e7c322c02bb81, 0x13f6b4ab644c85b1, 0x62cf8114926bd84d, // [6][0x6c] + 0x4813f40ee284d264, 0x392ac1b114a38f98, 0xc1f209285cedb1a8, 0xb0cb3c97aacaec54, // [6][0x70] + 0x3143981bcd71cdc8, 0x407aada43b569034, 0xb8a2653d7318ae04, 0xc99b5082853ff3f8, // [6][0x74] + 0xd120bb7cef483408, 0xa0198ec3196f69f4, 0x58c1465a512157c4, 0x29f873e5a7060a38, // [6][0x78] + 0xa870d769c0bd2ba4, 0xd949e2d6369a7658, 0x21912a4f7ed44868, 0x50a81ff088f31594, // [6][0x7c] + 0xea5282f73c15ba74, 0x9b6bb748ca32e788, 0x63b37fd1827cd9b8, 0x128a4a6e745b8444, // [6][0x80] + 0x9302eee213e0a5d8, 0xe23bdb5de5c7f824, 0x1ae313c4ad89c614, 0x6bda267b5bae9be8, // [6][0x84] + 0x7361cd8531d95c18, 0x0258f83ac7fe01e4, 0xfa8030a38fb03fd4, 0x8bb9051c79976228, // [6][0x88] + 0x0a31a1901e2c43b4, 0x7b08942fe80b1e48, 0x83d05cb6a0452078, 0xf2e9690956627d84, // [6][0x8c] + 0xd8351c13268d77ad, 0xa90c29acd0aa2a51, 0x51d4e13598e41461, 0x20edd48a6ec3499d, // [6][0x90] + 0xa165700609786801, 0xd05c45b9ff5f35fd, 0x28848d20b7110bcd, 0x59bdb89f41365631, // [6][0x94] + 0x410653612b4191c1, 0x303f66dedd66cc3d, 0xc8e7ae479528f20d, 0xb9de9bf8630faff1, // [6][0x98] + 0x38563f7404b48e6d, 0x496f0acbf293d391, 0xb1b7c252baddeda1, 0xc08ef7ed4cfab05d, // [6][0x9c] + 0xe50f29665a03f8f3, 0x94361cd9ac24a50f, 0x6ceed440e46a9b3f, 0x1dd7e1ff124dc6c3, // [6][0xa0] + 0x9c5f457375f6e75f, 0xed6670cc83d1baa3, 0x15beb855cb9f8493, 0x64878dea3db8d96f, // [6][0xa4] + 0x7c3c661457cf1e9f, 0x0d0553aba1e84363, 0xf5dd9b32e9a67d53, 0x84e4ae8d1f8120af, // [6][0xa8] + 0x056c0a01783a0133, 0x74553fbe8e1d5ccf, 0x8c8df727c65362ff, 0xfdb4c29830743f03, // [6][0xac] + 0xd768b782409b352a, 0xa651823db6bc68d6, 0x5e894aa4fef256e6, 0x2fb07f1b08d50b1a, // [6][0xb0] + 0xae38db976f6e2a86, 0xdf01ee289949777a, 0x27d926b1d107494a, 0x56e0130e272014b6, // [6][0xb4] + 0x4e5bf8f04d57d346, 0x3f62cd4fbb708eba, 0xc7ba05d6f33eb08a, 0xb68330690519ed76, // [6][0xb8] + 0x370b94e562a2ccea, 0x4632a15a94859116, 0xbeea69c3dccbaf26, 0xcfd35c7c2aecf2da, // [6][0xbc] + 0x9f7b438ca21fe74e, 0xee4276335438bab2, 0x169abeaa1c768482, 0x67a38b15ea51d97e, // [6][0xc0] + 0xe62b2f998deaf8e2, 0x97121a267bcda51e, 0x6fcad2bf33839b2e, 0x1ef3e700c5a4c6d2, // [6][0xc4] + 0x06480cfeafd30122, 0x7771394159f45cde, 0x8fa9f1d811ba62ee, 0xfe90c467e79d3f12, // [6][0xc8] + 0x7f1860eb80261e8e, 0x0e21555476014372, 0xf6f99dcd3e4f7d42, 0x87c0a872c86820be, // [6][0xcc] + 0xad1cdd68b8872a97, 0xdc25e8d74ea0776b, 0x24fd204e06ee495b, 0x55c415f1f0c914a7, // [6][0xd0] + 0xd44cb17d9772353b, 0xa57584c2615568c7, 0x5dad4c5b291b56f7, 0x2c9479e4df3c0b0b, // [6][0xd4] + 0x342f921ab54bccfb, 0x4516a7a5436c9107, 0xbdce6f3c0b22af37, 0xccf75a83fd05f2cb, // [6][0xd8] + 0x4d7ffe0f9abed357, 0x3c46cbb06c998eab, 0xc49e032924d7b09b, 0xb5a73696d2f0ed67, // [6][0xdc] + 0x9026e81dc409a5c9, 0xe11fdda2322ef835, 0x19c7153b7a60c605, 0x68fe20848c479bf9, // [6][0xe0] + 0xe9768408ebfcba65, 0x984fb1b71ddbe799, 0x6097792e5595d9a9, 0x11ae4c91a3b28455, // [6][0xe4] + 0x0915a76fc9c543a5, 0x782c92d03fe21e59, 0x80f45a4977ac2069, 0xf1cd6ff6818b7d95, // [6][0xe8] + 0x7045cb7ae6305c09, 0x017cfec5101701f5, 0xf9a4365c58593fc5, 0x889d03e3ae7e6239, // [6][0xec] + 0xa24176f9de916810, 0xd378434628b635ec, 0x2ba08bdf60f80bdc, 0x5a99be6096df5620, // [6][0xf0] + 0xdb111aecf16477bc, 0xaa282f5307432a40, 0x52f0e7ca4f0d1470, 0x23c9d275b92a498c, // [6][0xf4] + 0x3b72398bd35d8e7c, 0x4a4b0c34257ad380, 0xb293c4ad6d34edb0, 0xc3aaf1129b13b04c, // [6][0xf8] + 0x4222559efca891d0, 0x331b60210a8fcc2c, 0xcbc3a8b842c1f21c, 0xbafa9d07b4e6afe0 // [6][0xfc] + }, + { + 0x0000000000000000, 0xac2126251e76e921, 0x58434c4a3cecd243, 0xf4626a6f229a3b62, // [7][0x00] + 0xb086989478d8a587, 0x1ca7beb166ae4ca6, 0xe8c5d4de443477c4, 0x44e4f2fb5a429ee5, // [7][0x04] + 0x0b9ea671a296923b, 0xa7bf8054bce07b1a, 0x53ddea3b9e7a4078, 0xfffccc1e800ca959, // [7][0x08] + 0xbb183ee5da4e37bc, 0x173918c0c438de9d, 0xe35b72afe6a2e5ff, 0x4f7a548af8d40cde, // [7][0x0c] + 0x163c4de3442d2577, 0xba1d6bc65a5bcc56, 0x4e7f01a978c1f734, 0xe25e278c66b71e15, // [7][0x10] + 0xa6bad5773cf580f0, 0x0a9bf352228369d1, 0xfef9993d001952b3, 0x52d8bf181e6fbb92, // [7][0x14] + 0x1da2eb92e6bbb74c, 0xb183cdb7f8cd5e6d, 0x45e1a7d8da57650f, 0xe9c081fdc4218c2e, // [7][0x18] + 0xad2473069e6312cb, 0x010555238015fbea, 0xf5673f4ca28fc088, 0x59461969bcf929a9, // [7][0x1c] + 0x2c789ac6895a4aee, 0x8059bce3972ca3cf, 0x743bd68cb5b698ad, 0xd81af0a9abc0718c, // [7][0x20] + 0x9cfe0252f182ef69, 0x30df2477eff40648, 0xc4bd4e18cd6e3d2a, 0x689c683dd318d40b, // [7][0x24] + 0x27e63cb72bccd8d5, 0x8bc71a9235ba31f4, 0x7fa570fd17200a96, 0xd38456d80956e3b7, // [7][0x28] + 0x9760a42353147d52, 0x3b4182064d629473, 0xcf23e8696ff8af11, 0x6302ce4c718e4630, // [7][0x2c] + 0x3a44d725cd776f99, 0x9665f100d30186b8, 0x62079b6ff19bbdda, 0xce26bd4aefed54fb, // [7][0x30] + 0x8ac24fb1b5afca1e, 0x26e36994abd9233f, 0xd28103fb8943185d, 0x7ea025de9735f17c, // [7][0x34] + 0x31da71546fe1fda2, 0x9dfb577171971483, 0x69993d1e530d2fe1, 0xc5b81b3b4d7bc6c0, // [7][0x38] + 0x815ce9c017395825, 0x2d7dcfe5094fb104, 0xd91fa58a2bd58a66, 0x753e83af35a36347, // [7][0x3c] + 0x3363a3d540934de8, 0x9f4285f05ee5a4c9, 0x6b20ef9f7c7f9fab, 0xc701c9ba6209768a, // [7][0x40] + 0x83e53b41384be86f, 0x2fc41d64263d014e, 0xdba6770b04a73a2c, 0x7787512e1ad1d30d, // [7][0x44] + 0x38fd05a4e205dfd3, 0x94dc2381fc7336f2, 0x60be49eedee90d90, 0xcc9f6fcbc09fe4b1, // [7][0x48] + 0x887b9d309add7a54, 0x245abb1584ab9375, 0xd038d17aa631a817, 0x7c19f75fb8474136, // [7][0x4c] + 0x255fee3604be689f, 0x897ec8131ac881be, 0x7d1ca27c3852badc, 0xd13d8459262453fd, // [7][0x50] + 0x95d976a27c66cd18, 0x39f8508762102439, 0xcd9a3ae8408a1f5b, 0x61bb1ccd5efcf67a, // [7][0x54] + 0x2ec14847a628faa4, 0x82e06e62b85e1385, 0x7682040d9ac428e7, 0xdaa3222884b2c1c6, // [7][0x58] + 0x9e47d0d3def05f23, 0x3266f6f6c086b602, 0xc6049c99e21c8d60, 0x6a25babcfc6a6441, // [7][0x5c] + 0x1f1b3913c9c90706, 0xb33a1f36d7bfee27, 0x47587559f525d545, 0xeb79537ceb533c64, // [7][0x60] + 0xaf9da187b111a281, 0x03bc87a2af674ba0, 0xf7deedcd8dfd70c2, 0x5bffcbe8938b99e3, // [7][0x64] + 0x14859f626b5f953d, 0xb8a4b94775297c1c, 0x4cc6d32857b3477e, 0xe0e7f50d49c5ae5f, // [7][0x68] + 0xa40307f6138730ba, 0x082221d30df1d99b, 0xfc404bbc2f6be2f9, 0x50616d99311d0bd8, // [7][0x6c] + 0x092774f08de42271, 0xa50652d59392cb50, 0x516438bab108f032, 0xfd451e9faf7e1913, // [7][0x70] + 0xb9a1ec64f53c87f6, 0x1580ca41eb4a6ed7, 0xe1e2a02ec9d055b5, 0x4dc3860bd7a6bc94, // [7][0x74] + 0x02b9d2812f72b04a, 0xae98f4a43104596b, 0x5afa9ecb139e6209, 0xf6dbb8ee0de88b28, // [7][0x78] + 0xb23f4a1557aa15cd, 0x1e1e6c3049dcfcec, 0xea7c065f6b46c78e, 0x465d207a75302eaf, // [7][0x7c] + 0x0d55d1f3d20042e4, 0xa174f7d6cc76abc5, 0x55169db9eeec90a7, 0xf937bb9cf09a7986, // [7][0x80] + 0xbdd34967aad8e763, 0x11f26f42b4ae0e42, 0xe590052d96343520, 0x49b123088842dc01, // [7][0x84] + 0x06cb77827096d0df, 0xaaea51a76ee039fe, 0x5e883bc84c7a029c, 0xf2a91ded520cebbd, // [7][0x88] + 0xb64def16084e7558, 0x1a6cc93316389c79, 0xee0ea35c34a2a71b, 0x422f85792ad44e3a, // [7][0x8c] + 0x1b699c10962d6793, 0xb748ba35885b8eb2, 0x432ad05aaac1b5d0, 0xef0bf67fb4b75cf1, // [7][0x90] + 0xabef0484eef5c214, 0x07ce22a1f0832b35, 0xf3ac48ced2191057, 0x5f8d6eebcc6ff976, // [7][0x94] + 0x10f73a6134bbf5a8, 0xbcd61c442acd1c89, 0x48b4762b085727eb, 0xe495500e1621ceca, // [7][0x98] + 0xa071a2f54c63502f, 0x0c5084d05215b90e, 0xf832eebf708f826c, 0x5413c89a6ef96b4d, // [7][0x9c] + 0x212d4b355b5a080a, 0x8d0c6d10452ce12b, 0x796e077f67b6da49, 0xd54f215a79c03368, // [7][0xa0] + 0x91abd3a12382ad8d, 0x3d8af5843df444ac, 0xc9e89feb1f6e7fce, 0x65c9b9ce011896ef, // [7][0xa4] + 0x2ab3ed44f9cc9a31, 0x8692cb61e7ba7310, 0x72f0a10ec5204872, 0xded1872bdb56a153, // [7][0xa8] + 0x9a3575d081143fb6, 0x361453f59f62d697, 0xc276399abdf8edf5, 0x6e571fbfa38e04d4, // [7][0xac] + 0x371106d61f772d7d, 0x9b3020f30101c45c, 0x6f524a9c239bff3e, 0xc3736cb93ded161f, // [7][0xb0] + 0x87979e4267af88fa, 0x2bb6b86779d961db, 0xdfd4d2085b435ab9, 0x73f5f42d4535b398, // [7][0xb4] + 0x3c8fa0a7bde1bf46, 0x90ae8682a3975667, 0x64cceced810d6d05, 0xc8edcac89f7b8424, // [7][0xb8] + 0x8c093833c5391ac1, 0x20281e16db4ff3e0, 0xd44a7479f9d5c882, 0x786b525ce7a321a3, // [7][0xbc] + 0x3e36722692930f0c, 0x921754038ce5e62d, 0x66753e6cae7fdd4f, 0xca541849b009346e, // [7][0xc0] + 0x8eb0eab2ea4baa8b, 0x2291cc97f43d43aa, 0xd6f3a6f8d6a778c8, 0x7ad280ddc8d191e9, // [7][0xc4] + 0x35a8d45730059d37, 0x9989f2722e737416, 0x6deb981d0ce94f74, 0xc1cabe38129fa655, // [7][0xc8] + 0x852e4cc348dd38b0, 0x290f6ae656abd191, 0xdd6d00897431eaf3, 0x714c26ac6a4703d2, // [7][0xcc] + 0x280a3fc5d6be2a7b, 0x842b19e0c8c8c35a, 0x7049738fea52f838, 0xdc6855aaf4241119, // [7][0xd0] + 0x988ca751ae668ffc, 0x34ad8174b01066dd, 0xc0cfeb1b928a5dbf, 0x6ceecd3e8cfcb49e, // [7][0xd4] + 0x239499b47428b840, 0x8fb5bf916a5e5161, 0x7bd7d5fe48c46a03, 0xd7f6f3db56b28322, // [7][0xd8] + 0x931201200cf01dc7, 0x3f3327051286f4e6, 0xcb514d6a301ccf84, 0x67706b4f2e6a26a5, // [7][0xdc] + 0x124ee8e01bc945e2, 0xbe6fcec505bfacc3, 0x4a0da4aa272597a1, 0xe62c828f39537e80, // [7][0xe0] + 0xa2c870746311e065, 0x0ee956517d670944, 0xfa8b3c3e5ffd3226, 0x56aa1a1b418bdb07, // [7][0xe4] + 0x19d04e91b95fd7d9, 0xb5f168b4a7293ef8, 0x419302db85b3059a, 0xedb224fe9bc5ecbb, // [7][0xe8] + 0xa956d605c187725e, 0x0577f020dff19b7f, 0xf1159a4ffd6ba01d, 0x5d34bc6ae31d493c, // [7][0xec] + 0x0472a5035fe46095, 0xa8538326419289b4, 0x5c31e9496308b2d6, 0xf010cf6c7d7e5bf7, // [7][0xf0] + 0xb4f43d97273cc512, 0x18d51bb2394a2c33, 0xecb771dd1bd01751, 0x409657f805a6fe70, // [7][0xf4] + 0x0fec0372fd72f2ae, 0xa3cd2557e3041b8f, 0x57af4f38c19e20ed, 0xfb8e691ddfe8c9cc, // [7][0xf8] + 0xbf6a9be685aa5729, 0x134bbdc39bdcbe08, 0xe729d7acb946856a, 0x4b08f189a7306c4b // [7][0xfc] + }}; + +/* Calculate a CRC-64 eight bytes at a time on a big-endian architecture. */ +static inline uint64_t s_crc64_sw_be(const uint8_t *input, int length, uint64_t prev_crc64) { + uint64_t crc = ~aws_bswap64_if_be(prev_crc64); + // Read byte by byte until we reach an 8 byte aligned address + while (length > 0 && ((intptr_t)input & 7)) { + crc = (crc << 8) ^ crc64nvme_table_be[0][((crc >> 56) ^ *input++)]; + length--; + } + + int remaining = length; + // Once we are aligned, read 8 bytes at a time + const uint64_t *current = (const uint64_t *)(const void *)input; + while (remaining >= 8) { + uint64_t c1 = *current++ ^ crc; + crc = crc64nvme_table_be[0][c1 & 0xff] ^ crc64nvme_table_be[1][(c1 >> 8) & 0xff] ^ + crc64nvme_table_be[2][(c1 >> 16) & 0xff] ^ crc64nvme_table_be[3][(c1 >> 24) & 0xff] ^ + crc64nvme_table_be[4][(c1 >> 32) & 0xff] ^ crc64nvme_table_be[5][(c1 >> 40) & 0xff] ^ + crc64nvme_table_be[6][(c1 >> 48) & 0xff] ^ crc64nvme_table_be[7][c1 >> 56]; + remaining -= 8; + } + while (remaining > 0) { + crc = (crc << 8) ^ crc64nvme_table_be[0][((crc >> 56) ^ input[length - remaining]) & 0xff]; + remaining--; + } + return ~aws_bswap64_if_be(crc); +} + +/** Slow slice-by-8 lookup table based fallback function to compute CRC64NVME. */ +uint64_t aws_checksums_crc64nvme_sw(const uint8_t *input, int length, uint64_t prev_crc64) { + + if (!input || length <= 0) { + return prev_crc64; + } + + if (aws_is_big_endian()) { + return s_crc64_sw_be(input, length, prev_crc64); + } + + uint64_t crc = ~prev_crc64; + + // Read byte by byte until we reach an 8 byte aligned address + while (length > 0 && ((intptr_t)input & 7)) { + crc = (crc >> 8) ^ crc64nvme_table_le[0][(crc ^ *input++) & 0xff]; + length--; + } + + int remaining = length; + // Once we are aligned, read 8 bytes at a time + const uint64_t *current = (const uint64_t *)(const void *)input; + while (remaining >= 8) { + uint64_t c1 = *current++ ^ crc; + crc = crc64nvme_table_le[7][c1 & 0xff]; + crc ^= crc64nvme_table_le[6][(c1 >> 8) & 0xff]; + crc ^= crc64nvme_table_le[5][(c1 >> 16) & 0xff]; + crc ^= crc64nvme_table_le[4][(c1 >> 24) & 0xff]; + crc ^= crc64nvme_table_le[3][(c1 >> 32) & 0xff]; + crc ^= crc64nvme_table_le[2][(c1 >> 40) & 0xff]; + crc ^= crc64nvme_table_le[1][(c1 >> 48) & 0xff]; + crc ^= crc64nvme_table_le[0][(c1 >> 56) & 0xff]; + remaining -= 8; + } + + // Read any remaining input byte by byte + while (remaining > 0) { + crc = (crc >> 8) ^ crc64nvme_table_le[0][(crc ^ input[length - remaining]) & 0xff]; + remaining--; + } + + return ~crc; +} diff --git a/contrib/restricted/aws/aws-checksums/source/crc_sw.c b/contrib/restricted/aws/aws-checksums/source/crc_sw.c index 9bc326b9e8e..c4329f574a5 100644 --- a/contrib/restricted/aws/aws-checksums/source/crc_sw.c +++ b/contrib/restricted/aws/aws-checksums/source/crc_sw.c @@ -2,7 +2,8 @@ * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. * SPDX-License-Identifier: Apache-2.0. */ -#include <aws/checksums/private/crc_priv.h> +#include <aws/checksums/private/crc32_priv.h> +#include <aws/checksums/private/crc_util.h> #include <stddef.h> /* The Ethernet, gzip, et.al CRC32 polynomial (reverse of 0x04C11DB7) */ @@ -1149,7 +1150,7 @@ static uint32_t s_crc_generic_sb4(const uint8_t *input, int length, uint32_t crc uint32_t(*table)[16][256] = (uint32_t(*)[16][256])table_ptr; while (remaining >= 4) { - crc ^= *current++; + crc ^= aws_bswap32_if_be(*current++); crc = (*table)[3][crc & 0xff] ^ (*table)[2][(crc >> 8) & 0xff] ^ (*table)[1][(crc >> 16) & 0xff] ^ (*table)[0][crc >> 24]; remaining -= 4; @@ -1165,8 +1166,8 @@ static uint32_t s_crc_generic_sb8(const uint8_t *input, int length, uint32_t crc uint32_t(*table)[16][256] = (uint32_t(*)[16][256])table_ptr; while (remaining >= 8) { - uint32_t c1 = *current++ ^ crc; - uint32_t c2 = *current++; + uint32_t c1 = aws_bswap32_if_be(*current++) ^ crc; + uint32_t c2 = aws_bswap32_if_be(*current++); uint32_t t1 = (*table)[7][c1 & 0xff] ^ (*table)[6][(c1 >> 8) & 0xff] ^ (*table)[5][(c1 >> 16) & 0xff] ^ (*table)[4][(c1 >> 24) & 0xff]; uint32_t t2 = (*table)[3][c2 & 0xff] ^ (*table)[2][(c2 >> 8) & 0xff] ^ (*table)[1][(c2 >> 16) & 0xff] ^ @@ -1185,10 +1186,10 @@ static uint32_t s_crc_generic_sb16(const uint8_t *input, int length, uint32_t cr uint32_t(*table)[16][256] = (uint32_t(*)[16][256])table_ptr; while (remaining >= 16) { - uint32_t c1 = *current++ ^ crc; - uint32_t c2 = *current++; - uint32_t c3 = *current++; - uint32_t c4 = *current++; + uint32_t c1 = aws_bswap32_if_be(*current++) ^ crc; + uint32_t c2 = aws_bswap32_if_be(*current++); + uint32_t c3 = aws_bswap32_if_be(*current++); + uint32_t c4 = aws_bswap32_if_be(*current++); uint32_t t1 = (*table)[15][c1 & 0xff] ^ (*table)[14][(c1 >> 8) & 0xff] ^ (*table)[13][(c1 >> 16) & 0xff] ^ (*table)[12][(c1 >> 24) & 0xff]; uint32_t t2 = (*table)[11][c2 & 0xff] ^ (*table)[10][(c2 >> 8) & 0xff] ^ (*table)[9][(c2 >> 16) & 0xff] ^ diff --git a/contrib/restricted/aws/aws-checksums/source/intel/asm/crc32c_sse42_asm.c b/contrib/restricted/aws/aws-checksums/source/intel/asm/crc32c_sse42_asm.c index 3c124ec8447..fe75e3bd9c6 100644 --- a/contrib/restricted/aws/aws-checksums/source/intel/asm/crc32c_sse42_asm.c +++ b/contrib/restricted/aws/aws-checksums/source/intel/asm/crc32c_sse42_asm.c @@ -3,9 +3,10 @@ * SPDX-License-Identifier: Apache-2.0. */ -#include <aws/checksums/private/crc_priv.h> +#include <aws/checksums/private/crc32_priv.h> +#include <aws/checksums/private/crc_util.h> -#include <aws/common/cpuid.h> +/* clang-format off */ /* this implementation is only for the x86_64 intel architecture */ #if defined(__x86_64__) @@ -14,6 +15,13 @@ # pragma clang diagnostic ignored "-Wdollar-in-identifier-extension" # endif +/* use local labels, so that linker doesn't think these are functions it can deadstrip */ +# ifdef __APPLE__ +# define LABEL(label) "L_" #label "_%=" +# else +# define LABEL(label) ".L_" #label "_%=" +# endif + /* * Factored out common inline asm for folding crc0,crc1,crc2 stripes in rcx, r11, r10 using * the specified Magic Constants K1 and K2. @@ -21,8 +29,7 @@ * Utilizes xmm1, xmm2, xmm3, xmm4 as well as clobbering r8, r9, r11 * Result is placed in ecx */ -# define FOLD_K1K2(NAME, K1, K2) \ - "fold_k1k2_" #NAME "_%=: \n" \ +# define FOLD_K1K2(K1, K2) \ "movl " #K1 ", %%r8d # Magic K1 constant \n" \ "movl " #K2 ", %%r9d # Magic K2 constant \n" \ "movq %%rcx, %%xmm1 # crc0 into lower dword of xmm1 \n" \ @@ -50,8 +57,6 @@ */ static inline uint32_t s_crc32c_sse42_clmul_256(const uint8_t *input, uint32_t crc) { __asm__ __volatile__( - "enter_256_%=:" - "xor %%r11, %%r11 # zero all 64 bits in r11, will track crc1 \n" "xor %%r10, %%r10 # zero all 64 bits in r10, will track crc2 \n" @@ -98,7 +103,7 @@ static inline uint32_t s_crc32c_sse42_clmul_256(const uint8_t *input, uint32_t c "crc32q 80(%[in]), %%rcx # crc0 \n" "crc32q 168(%[in]), %%r11 # crc2 \n" - FOLD_K1K2(256, $0x1b3d8f29, $0x39d3b296) /* Magic Constants used to fold crc stripes into ecx */ + FOLD_K1K2($0x1b3d8f29, $0x39d3b296) /* Magic Constants used to fold crc stripes into ecx */ /* output registers [crc] is an input and and output so it is marked read/write (i.e. "+c")*/ @@ -121,14 +126,12 @@ static inline uint32_t s_crc32c_sse42_clmul_256(const uint8_t *input, uint32_t c */ static inline uint32_t s_crc32c_sse42_clmul_1024(const uint8_t *input, uint32_t crc) { __asm__ __volatile__( - "enter_1024_%=:" - "xor %%r11, %%r11 # zero all 64 bits in r11, will track crc1 \n" "xor %%r10, %%r10 # zero all 64 bits in r10, will track crc2 \n" "movl $5, %%r8d # Loop 5 times through 64 byte chunks in 3 parallel stripes \n" - "loop_1024_%=:" + LABEL(loop_1024) ": \n" "prefetcht0 128(%[in]) # \n" "prefetcht0 472(%[in]) # \n" @@ -168,7 +171,7 @@ static inline uint32_t s_crc32c_sse42_clmul_1024(const uint8_t *input, uint32_t "add $64, %[in] # \n" "sub $1, %%r8d # \n" - "jnz loop_1024_%= # \n" + "jnz " LABEL(loop_1024) " # \n" "crc32q 0(%[in]), %%rcx # crc0 \n" "crc32q 344(%[in]), %%r11 # crc1 \n" @@ -181,7 +184,7 @@ static inline uint32_t s_crc32c_sse42_clmul_1024(const uint8_t *input, uint32_t "crc32q 16(%[in]), %%rcx # crc0 \n" "crc32q 696(%[in]), %%r10 # crc2 \n" - FOLD_K1K2(1024, $0xe417f38a, $0x8f158014) /* Magic Constants used to fold crc stripes into ecx + FOLD_K1K2($0xe417f38a, $0x8f158014) /* Magic Constants used to fold crc stripes into ecx output registers [crc] is an input and and output so it is marked read/write (i.e. "+c") @@ -205,14 +208,12 @@ static inline uint32_t s_crc32c_sse42_clmul_1024(const uint8_t *input, uint32_t */ static inline uint32_t s_crc32c_sse42_clmul_3072(const uint8_t *input, uint32_t crc) { __asm__ __volatile__( - "enter_3072_%=:" - "xor %%r11, %%r11 # zero all 64 bits in r11, will track crc1 \n" "xor %%r10, %%r10 # zero all 64 bits in r10, will track crc2 \n" "movl $16, %%r8d # Loop 16 times through 64 byte chunks in 3 parallel stripes \n" - "loop_3072_%=:" + LABEL(loop_3072) ": \n" "prefetcht0 128(%[in]) # \n" "prefetcht0 1152(%[in]) # \n" @@ -252,10 +253,9 @@ static inline uint32_t s_crc32c_sse42_clmul_3072(const uint8_t *input, uint32_t "add $64, %[in] # \n" "sub $1, %%r8d # \n" - "jnz loop_3072_%= # \n" + "jnz " LABEL(loop_3072) " # \n" FOLD_K1K2( - 3072, $0xa51b6135, $0x170076fa) /* Magic Constants used to fold crc stripes into ecx @@ -272,9 +272,6 @@ static inline uint32_t s_crc32c_sse42_clmul_3072(const uint8_t *input, uint32_t return crc; } -static bool detection_performed = false; -static bool detected_clmul = false; - /* * Computes the Castagnoli CRC32c (iSCSI) of the specified data buffer using the Intel CRC32Q (64-bit quad word) and * PCLMULQDQ machine instructions (if present). @@ -282,22 +279,15 @@ static bool detected_clmul = false; * Pass 0 in the previousCrc32 parameter as an initial value unless continuing to update a running CRC in a subsequent * call. */ -uint32_t aws_checksums_crc32c_hw(const uint8_t *input, int length, uint32_t previousCrc32) { - - if (AWS_UNLIKELY(!detection_performed)) { - detected_clmul = aws_cpu_has_feature(AWS_CPU_FEATURE_CLMUL); - /* Simply setting the flag true to skip HW detection next time - Not using memory barriers since the worst that can - happen is a fallback to the non HW accelerated code. */ - detection_performed = true; - } +uint32_t aws_checksums_crc32c_clmul_sse42(const uint8_t *input, int length, uint32_t previousCrc32) { + /* this is called by a higher-level shim and previousCRC32 is already ~ */ uint32_t crc = ~previousCrc32; /* For small input, forget about alignment checks - simply compute the CRC32c one byte at a time */ if (AWS_UNLIKELY(length < 8)) { while (length-- > 0) { - __asm__("loop_small_%=: CRC32B (%[in]), %[crc]" : [ crc ] "+c"(crc) : [ in ] "r"(input)); + __asm__("CRC32B (%[in]), %[crc]" : [ crc ] "+c"(crc) : [ in ] "r"(input)); input++; } return ~crc; @@ -314,12 +304,12 @@ uint32_t aws_checksums_crc32c_hw(const uint8_t *input, int length, uint32_t prev /* spin through the leading unaligned input bytes (if any) one-by-one */ while (leading-- > 0) { - __asm__("loop_leading_%=: CRC32B (%[in]), %[crc]" : [ crc ] "+c"(crc) : [ in ] "r"(input)); + __asm__("CRC32B (%[in]), %[crc]" : [ crc ] "+c"(crc) : [ in ] "r"(input)); input++; } /* Using likely to keep this code inlined */ - if (AWS_LIKELY(detected_clmul)) { + if (AWS_LIKELY(aws_cpu_has_clmul_cached())) { while (AWS_LIKELY(length >= 3072)) { /* Compute crc32c on each block, chaining each crc result */ @@ -344,34 +334,23 @@ uint32_t aws_checksums_crc32c_hw(const uint8_t *input, int length, uint32_t prev /* Spin through remaining (aligned) 8-byte chunks using the CRC32Q quad word instruction */ while (AWS_LIKELY(length >= 8)) { /* Hardcoding %rcx register (i.e. "+c") to allow use of qword instruction */ - __asm__ __volatile__("loop_8_%=: CRC32Q (%[in]), %%rcx" : [ crc ] "+c"(crc) : [ in ] "r"(input)); + __asm__ __volatile__("CRC32Q (%[in]), %%rcx" : [ crc ] "+c"(crc) : [ in ] "r"(input)); input += 8; length -= 8; } /* Finish up with any trailing bytes using the CRC32B single byte instruction one-by-one */ while (length-- > 0) { - __asm__ __volatile__("loop_trailing_%=: CRC32B (%[in]), %[crc]" : [ crc ] "+c"(crc) : [ in ] "r"(input)); + __asm__ __volatile__("CRC32B (%[in]), %[crc]" : [ crc ] "+c"(crc) : [ in ] "r"(input)); input++; } return ~crc; } -uint32_t aws_checksums_crc32_hw(const uint8_t *input, int length, uint32_t previousCrc32) { - return aws_checksums_crc32_sw(input, length, previousCrc32); -} # if defined(__clang__) # pragma clang diagnostic pop # endif -#else -uint32_t aws_checksums_crc32_hw(const uint8_t *input, int length, uint32_t previousCrc32) { - return aws_checksums_crc32_sw(input, length, previousCrc32); -} - -uint32_t aws_checksums_crc32c_hw(const uint8_t *input, int length, uint32_t previousCrc32) { - return aws_checksums_crc32c_sw(input, length, previousCrc32); -} - -#endif +#endif /* x86_64 */ +/* clang-format on */ diff --git a/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc32c_sse42_avx512.c b/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc32c_sse42_avx512.c new file mode 100644 index 00000000000..503da08896c --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc32c_sse42_avx512.c @@ -0,0 +1,227 @@ +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/checksums/private/crc32_priv.h> +#include <aws/checksums/private/crc_util.h> + +#include <aws/common/assert.h> +#include <aws/common/macros.h> + +#include <emmintrin.h> +#include <immintrin.h> +#include <smmintrin.h> + +#if defined(AWS_HAVE_AVX512_INTRINSICS) && defined(AWS_ARCH_INTEL_X64) + +# include <wmmintrin.h> + +AWS_ALIGNED_TYPEDEF(const uint64_t, aligned_512_u64[8], 64); + +// This macro uses casting to ensure the compiler actually uses the unaligned load instructions +# define load_zmm(ptr) _mm512_loadu_si512((const uint8_t *)(const void *)(ptr)) + +/* + * crc32c_avx512(): compute the crc32c of the buffer, where the buffer + * length must be at least 256, and a multiple of 64. Based on: + * + * "Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction" + * V. Gopal, E. Ozturk, et al., 2009, http://download.intel.com/design/intarch/papers/323102.pdf + */ +static uint32_t s_checksums_crc32c_avx512_impl(const uint8_t *input, int length, uint32_t previous_crc) { + AWS_ASSERT( + length >= 256 && "invariant violated. length must be greater than 255 bytes to use avx512 to compute crc."); + + uint32_t crc = previous_crc; + + /* + * Definitions of the bit-reflected domain constants k1,k2,k3,k4,k5,k6 + * are similar to those given at the end of the paper + * + * k1 = ( x ^ ( 512 * 4 + 32 ) mod P(x) << 32 )' << 1 + * k2 = ( x ^ ( 512 * 4 - 32 ) mod P(x) << 32 )' << 1 + * k3 = ( x ^ ( 512 + 32 ) mod P(x) << 32 )' << 1 + * k4 = ( x ^ ( 512 - 32 ) mod P(x) << 32 )' << 1 + * k5 = ( x ^ ( 128 + 32 ) mod P(x) << 32 )' << 1 + * k6 = ( x ^ ( 128 - 32 ) mod P(x) << 32 )' << 1 + */ + + static aligned_512_u64 k1k2 = { + 0xdcb17aa4, 0xb9e02b86, 0xdcb17aa4, 0xb9e02b86, 0xdcb17aa4, 0xb9e02b86, 0xdcb17aa4, 0xb9e02b86}; + static aligned_512_u64 k3k4 = { + 0x740eef02, 0x9e4addf8, 0x740eef02, 0x9e4addf8, 0x740eef02, 0x9e4addf8, 0x740eef02, 0x9e4addf8}; + static aligned_512_u64 k9k10 = { + 0x6992cea2, 0x0d3b6092, 0x6992cea2, 0x0d3b6092, 0x6992cea2, 0x0d3b6092, 0x6992cea2, 0x0d3b6092}; + static aligned_512_u64 k1k4 = { + 0x1c291d04, 0xddc0152b, 0x3da6d0cb, 0xba4fc28e, 0xf20c0dfe, 0x493c7d27, 0x00000000, 0x00000000}; + + __m512i x0, x1, x2, x3, x4, x5, x6, x7, x8, y5, y6, y7, y8; + __m128i a1; + + /* + * There's at least one block of 256. + */ + x1 = load_zmm(input + 0x00); + x2 = load_zmm(input + 0x40); + x3 = load_zmm(input + 0x80); + x4 = load_zmm(input + 0xC0); + + // Load the crc into a zmm register and XOR with the first 64 bytes of input + x5 = _mm512_inserti32x4(_mm512_setzero_si512(), _mm_cvtsi32_si128((int)crc), 0); + x1 = _mm512_xor_si512(x1, x5); + + x0 = load_zmm(k1k2); + + input += 256; + length -= 256; + + /* + * Parallel fold blocks of 256, if any. + */ + while (length >= 256) { + x5 = _mm512_clmulepi64_epi128(x1, x0, 0x00); + x6 = _mm512_clmulepi64_epi128(x2, x0, 0x00); + x7 = _mm512_clmulepi64_epi128(x3, x0, 0x00); + x8 = _mm512_clmulepi64_epi128(x4, x0, 0x00); + + x1 = _mm512_clmulepi64_epi128(x1, x0, 0x11); + x2 = _mm512_clmulepi64_epi128(x2, x0, 0x11); + x3 = _mm512_clmulepi64_epi128(x3, x0, 0x11); + x4 = _mm512_clmulepi64_epi128(x4, x0, 0x11); + + y5 = load_zmm(input + 0x00); + y6 = load_zmm(input + 0x40); + y7 = load_zmm(input + 0x80); + y8 = load_zmm(input + 0xC0); + + x1 = _mm512_ternarylogic_epi64(x1, x5, y5, 0x96); + x2 = _mm512_ternarylogic_epi64(x2, x6, y6, 0x96); + x3 = _mm512_ternarylogic_epi64(x3, x7, y7, 0x96); + x4 = _mm512_ternarylogic_epi64(x4, x8, y8, 0x96); + + input += 256; + length -= 256; + } + + /* + * Fold 256 bytes into 64 bytes. + */ + x0 = load_zmm(k9k10); + x5 = _mm512_clmulepi64_epi128(x1, x0, 0x00); + x6 = _mm512_clmulepi64_epi128(x1, x0, 0x11); + x3 = _mm512_ternarylogic_epi64(x3, x5, x6, 0x96); + + x7 = _mm512_clmulepi64_epi128(x2, x0, 0x00); + x8 = _mm512_clmulepi64_epi128(x2, x0, 0x11); + x4 = _mm512_ternarylogic_epi64(x4, x7, x8, 0x96); + + x0 = load_zmm(k3k4); + y5 = _mm512_clmulepi64_epi128(x3, x0, 0x00); + y6 = _mm512_clmulepi64_epi128(x3, x0, 0x11); + x1 = _mm512_ternarylogic_epi64(x4, y5, y6, 0x96); + + /* + * Single fold blocks of 64, if any. + */ + while (length >= 64) { + x2 = load_zmm(input); + + x5 = _mm512_clmulepi64_epi128(x1, x0, 0x00); + x1 = _mm512_clmulepi64_epi128(x1, x0, 0x11); + x1 = _mm512_ternarylogic_epi64(x1, x2, x5, 0x96); + + input += 64; + length -= 64; + } + + /* + * Fold 512-bits to 128-bits. + */ + x0 = load_zmm(k1k4); + x4 = _mm512_clmulepi64_epi128(x1, x0, 0x00); + x3 = _mm512_clmulepi64_epi128(x1, x0, 0x11); + x2 = _mm512_xor_si512(x3, x4); + a1 = _mm_xor_si128(_mm512_extracti32x4_epi32(x1, 3), _mm512_extracti32x4_epi32(x2, 0)); + a1 = _mm_ternarylogic_epi64(a1, _mm512_extracti32x4_epi32(x2, 1), _mm512_extracti32x4_epi32(x2, 2), 0x96); + + /* + * Fold 128-bits to 32-bits. + */ + uint64_t val; + val = _mm_crc32_u64(0, _mm_extract_epi64(a1, 0)); + return (uint32_t)_mm_crc32_u64(val, _mm_extract_epi64(a1, 1)); +} +#endif /* #if defined(AWS_HAVE_AVX512_INTRINSICS) && (INTPTR_MAX == INT64_MAX) */ + +uint32_t aws_checksums_crc32c_intel_avx512_with_sse_fallback(const uint8_t *input, int length, uint32_t previous_crc) { + /* this is the entry point. We should only do the bit flip once. It should not be done for the subfunctions and + * branches.*/ + uint32_t crc = ~previous_crc; + + /* For small input, forget about alignment checks - simply compute the CRC32c one byte at a time */ + if (length < (int)sizeof(slice_ptr_int_type)) { + while (length-- > 0) { + crc = (uint32_t)_mm_crc32_u8(crc, *input++); + } + return ~crc; + } + + /* Get the 8-byte memory alignment of our input buffer by looking at the least significant 3 bits */ + int input_alignment = (uintptr_t)(input) & 0x7; + + /* Compute the number of unaligned bytes before the first aligned 8-byte chunk (will be in the range 0-7) */ + int leading = (8 - input_alignment) & 0x7; + + /* reduce the length by the leading unaligned bytes we are about to process */ + length -= leading; + + /* spin through the leading unaligned input bytes (if any) one-by-one */ + while (leading-- > 0) { + crc = (uint32_t)_mm_crc32_u8(crc, *input++); + } + +#if defined(AWS_HAVE_AVX512_INTRINSICS) && defined(AWS_ARCH_INTEL_X64) + int chunk_size = length & ~63; + + if (aws_cpu_has_avx512_cached() && aws_cpu_has_vpclmulqdq_cached() && aws_cpu_has_clmul_cached()) { + if (length >= 256) { + crc = s_checksums_crc32c_avx512_impl(input, length, crc); + /* check remaining data */ + length -= chunk_size; + if (!length) { + return ~crc; + } + + /* Fall into the default crc32 for the remaining data. */ + input += chunk_size; + } + } +#endif + +#if defined(AWS_ARCH_INTEL_X64) && !defined(_MSC_VER) + if (aws_cpu_has_sse42_cached() && aws_cpu_has_clmul_cached()) { + // this function is an entry point on its own. It inverts the crc passed to it + // does its thing and then inverts it upon return. In order to keep + // aws_checksums_crc32c_sse42 a standalone function (which it has to be due + // to the way its implemented) it's better that it doesn't need to know it's used + // in a larger computation fallback. + return aws_checksums_crc32c_clmul_sse42(input, length, ~crc); + } +#endif + + /* Spin through remaining (aligned) 8-byte chunks using the CRC32Q quad word instruction */ + while (length >= (int)sizeof(slice_ptr_int_type)) { + crc = (uint32_t)crc_intrin_fn(crc, *(slice_ptr_int_type *)(input)); + input += sizeof(slice_ptr_int_type); + length -= (int)sizeof(slice_ptr_int_type); + } + + /* Finish up with any trailing bytes using the CRC32B single byte instruction one-by-one */ + while (length-- > 0) { + crc = (uint32_t)_mm_crc32_u8(crc, *input); + input++; + } + + return ~crc; +} diff --git a/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc64nvme_avx512.c b/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc64nvme_avx512.c new file mode 100644 index 00000000000..6afbe93009b --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc64nvme_avx512.c @@ -0,0 +1,130 @@ +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/checksums/private/crc64_priv.h> + +#if defined(AWS_HAVE_AVX512_INTRINSICS) && defined(AWS_ARCH_INTEL_X64) + +# include <emmintrin.h> +# include <immintrin.h> +# include <smmintrin.h> +# include <wmmintrin.h> + +# define load_xmm(ptr) _mm_loadu_si128((const __m128i *)(const void *)(ptr)) +# define mask_high_bytes(xmm, count) \ + _mm_and_si128((xmm), load_xmm(aws_checksums_masks_shifts[3] + (intptr_t)(count))) +# define cmull_xmm_hi(xmm1, xmm2) _mm_clmulepi64_si128((xmm1), (xmm2), 0x11) +# define cmull_xmm_lo(xmm1, xmm2) _mm_clmulepi64_si128((xmm1), (xmm2), 0x00) +# define cmull_xmm_pair(xmm1, xmm2) _mm_xor_si128(cmull_xmm_hi((xmm1), (xmm2)), cmull_xmm_lo((xmm1), (xmm2))) +# define xor_xmm(xmm1, xmm2, xmm3) \ + _mm_ternarylogic_epi64((xmm1), (xmm2), (xmm3), 0x96) // The constant 0x96 produces a 3-way XOR + +# define load_zmm(ptr) _mm512_loadu_si512((const uint8_t *)(const void *)(ptr)) +# define cmull_zmm_hi(zmm1, zmm2) _mm512_clmulepi64_epi128((zmm1), (zmm2), 0x11) +# define cmull_zmm_lo(zmm1, zmm2) _mm512_clmulepi64_epi128((zmm1), (zmm2), 0x00) +# define cmull_zmm_pair(zmm1, zmm2) _mm512_xor_si512(cmull_zmm_hi((zmm1), (zmm2)), cmull_zmm_lo((zmm1), (zmm2))) +# define xor_zmm(zmm1, zmm2, zmm3) \ + _mm512_ternarylogic_epi64((zmm1), (zmm2), (zmm3), 0x96) // The constant 0x96 produces a 3-way XOR + +uint64_t aws_checksums_crc64nvme_intel_avx512(const uint8_t *input, int length, const uint64_t previous_crc64) { + + if (length < 512) { + return aws_checksums_crc64nvme_intel_clmul(input, length, previous_crc64); + } + + // The following code assumes a minimum of 256 bytes of input + + // Load the (inverted) CRC into a ZMM register + __m512i x1 = _mm512_inserti32x4(_mm512_setzero_si512(), _mm_cvtsi64_si128((int64_t)~previous_crc64), 0); + // Load the first 64 bytes into a zmm register and XOR with the (inverted) crc + x1 = _mm512_xor_si512(x1, load_zmm(input)); + // Load 192 more bytes of input + __m512i x2 = load_zmm(input + 0x40); + __m512i x3 = load_zmm(input + 0x80); + __m512i x4 = load_zmm(input + 0xc0); + input += 256; + length -= 256; + + const __m512i kp_2048 = load_zmm(aws_checksums_crc64nvme_constants.x2048); + const __m512i kp_512 = load_zmm(aws_checksums_crc64nvme_constants.x512); + + int loops = length / 256; + length &= 255; + + // Parallel fold blocks of 256 bytes, if any + while (loops--) { + x1 = xor_zmm(cmull_zmm_lo(kp_2048, x1), cmull_zmm_hi(kp_2048, x1), load_zmm(input + 0x00)); + x2 = xor_zmm(cmull_zmm_lo(kp_2048, x2), cmull_zmm_hi(kp_2048, x2), load_zmm(input + 0x40)); + x3 = xor_zmm(cmull_zmm_lo(kp_2048, x3), cmull_zmm_hi(kp_2048, x3), load_zmm(input + 0x80)); + x4 = xor_zmm(cmull_zmm_lo(kp_2048, x4), cmull_zmm_hi(kp_2048, x4), load_zmm(input + 0xc0)); + input += 256; + } + + // Fold 2048 bits into 512 bits + const __m512i kp_1536 = load_zmm(aws_checksums_crc64nvme_constants.x1536); + const __m512i kp_1024 = load_zmm(aws_checksums_crc64nvme_constants.x1024); + + x1 = xor_zmm(cmull_zmm_lo(kp_1536, x1), cmull_zmm_hi(kp_1536, x1), cmull_zmm_lo(kp_1024, x2)); + x2 = xor_zmm(cmull_zmm_hi(kp_1024, x2), cmull_zmm_lo(kp_512, x3), cmull_zmm_hi(kp_512, x3)); + x1 = xor_zmm(x1, x2, x4); + + // Fold blocks of 512 bits, if any + loops = length / 64; + length &= 63; + while (loops--) { + x1 = xor_zmm(cmull_zmm_lo(kp_512, x1), cmull_zmm_hi(kp_512, x1), load_zmm(input)); + input += 64; + } + + // Load 64 bytes of constants: x^448, x^384, x^320, x^256, x^192, x^128, N/A, N/A + const __m512i kp_384 = load_zmm(aws_checksums_crc64nvme_constants.x384); + + // Fold 512 bits to 128 bits + x2 = cmull_zmm_pair(kp_384, x1); + __m128i a1 = _mm_xor_si128(_mm512_extracti32x4_epi32(x1, 3), _mm512_extracti32x4_epi32(x2, 0)); + a1 = xor_xmm(a1, _mm512_extracti32x4_epi32(x2, 1), _mm512_extracti32x4_epi32(x2, 2)); + + // Single fold blocks of 128 bits, if any + loops = length / 16; + __m128i kp_128 = _mm512_extracti32x4_epi32(kp_384, 2); + while (loops--) { + a1 = xor_xmm(cmull_xmm_lo(kp_128, a1), cmull_xmm_hi(kp_128, a1), load_xmm(input)); + input += 16; + } + + // The remaining length can be only 0-15 bytes + length &= 15; + + // Load the x^128 constant (note that we don't need x^192). + const __m128i x128 = _mm_set_epi64x(0, aws_checksums_crc64nvme_constants.x128[1]); + if (length == 0) { + // Multiply the lower half of the crc register by x^128 and XOR the result with the upper half of the crc. + a1 = _mm_xor_si128(_mm_bsrli_si128(a1, 8), cmull_xmm_lo(a1, x128)); + } else { + // Handle any trailing input from 1-15 bytes. + __m128i trailing_constants = load_xmm(aws_checksums_crc64nvme_constants.trailing[length - 1]); + // Multiply the crc by a pair of trailing length constants in order to fold it into the trailing input. + a1 = cmull_xmm_pair(a1, trailing_constants); + // Safely load ending at the trailing input and mask out any leading garbage + __m128i trailing_input = mask_high_bytes(load_xmm(input + length - 16), length); + // Multiply the lower half of the trailing input register by x^128 + __m128i mul_by_x128 = cmull_xmm_lo(trailing_input, x128); + // XOR the results with the upper half of the trailing input + a1 = xor_xmm(a1, _mm_bsrli_si128(trailing_input, 8), mul_by_x128); + } + + // Barrett modular reduction + const __m128i mu_poly = load_xmm(&aws_checksums_crc64nvme_constants.mu_poly); + // Multiply the lower half of input by mu + __m128i mul_by_mu = _mm_clmulepi64_si128(mu_poly, a1, 0x00); + // Multiply the lower half of the mul_by_mu result by poly (it's in the upper half) + __m128i mul_by_poly = _mm_clmulepi64_si128(mu_poly, mul_by_mu, 0x01); + // Left shift mul_by_mu to get the low half into the upper half and XOR all the upper halves + __m128i reduced = xor_xmm(a1, _mm_bslli_si128(mul_by_mu, 8), mul_by_poly); + // After the XORs, the CRC falls in the upper half of the register - invert the bits before returning the crc + return ~(uint64_t)_mm_extract_epi64(reduced, 1); +} + +#endif /* defined(AWS_HAVE_AVX512_INTRINSICS) && defined(AWS_ARCH_INTEL_X64)*/ diff --git a/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc64nvme_clmul.c b/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc64nvme_clmul.c new file mode 100644 index 00000000000..f141181b002 --- /dev/null +++ b/contrib/restricted/aws/aws-checksums/source/intel/intrin/crc64nvme_clmul.c @@ -0,0 +1,147 @@ +/** + * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. + * SPDX-License-Identifier: Apache-2.0. + */ + +#include <aws/checksums/private/crc64_priv.h> +#include <aws/common/assert.h> + +// msvc compilers older than 2019 are missing some intrinsics. Gate those off. +#if defined(AWS_ARCH_INTEL_X64) && defined(AWS_HAVE_CLMUL) && !(defined(_MSC_VER) && _MSC_VER < 1920) + +# include <emmintrin.h> +# include <immintrin.h> +# include <smmintrin.h> +# include <wmmintrin.h> + +# define load_xmm(ptr) _mm_loadu_si128((const __m128i *)(const void *)(ptr)) +# define mask_high_bytes(xmm, count) \ + _mm_and_si128((xmm), load_xmm(aws_checksums_masks_shifts[3] + (intptr_t)(count))) +# define cmull_xmm_hi(xmm1, xmm2) _mm_clmulepi64_si128((xmm1), (xmm2), 0x11) +# define cmull_xmm_lo(xmm1, xmm2) _mm_clmulepi64_si128((xmm1), (xmm2), 0x00) +# define cmull_xmm_pair(xmm1, xmm2) _mm_xor_si128(cmull_xmm_hi((xmm1), (xmm2)), cmull_xmm_lo((xmm1), (xmm2))) + +uint64_t aws_checksums_crc64nvme_intel_clmul(const uint8_t *input, int length, uint64_t previous_crc64) { + + // the amount of complexity required to handle vector instructions on + // memory regions smaller than an xmm register does not justify the very negligible performance gains + // we would get for using it on an input this small. + if (length < 16) { + return aws_checksums_crc64nvme_sw(input, length, previous_crc64); + } + + // Invert the previous crc bits and load into the lower half of an xmm register + __m128i a1 = _mm_cvtsi64_si128((int64_t)(~previous_crc64)); + + // There are 16 or more bytes of input - load the first 16 bytes and XOR with the previous crc + a1 = _mm_xor_si128(a1, load_xmm(input)); + input += 16; + length -= 16; + + // Load the folding constants x^128 and x^192 + const __m128i x128 = load_xmm(aws_checksums_crc64nvme_constants.x128); + + if (length >= 48) { + // Load the next 48 bytes + __m128i b1 = load_xmm(input + 0x00); + __m128i c1 = load_xmm(input + 0x10); + __m128i d1 = load_xmm(input + 0x20); + + input += 48; + length -= 48; + + // Load the folding constants x^512 and x^576 + const __m128i x512 = load_xmm(aws_checksums_crc64nvme_constants.x512); + + if (length >= 64) { + // Load the next 64 bytes + __m128i e1 = load_xmm(input + 0x00); + __m128i f1 = load_xmm(input + 0x10); + __m128i g1 = load_xmm(input + 0x20); + __m128i h1 = load_xmm(input + 0x30); + input += 64; + length -= 64; + + // Load the folding constants x^1024 and x^1088 + const __m128i x1024 = load_xmm(aws_checksums_crc64nvme_constants.x1024); + + // Spin through 128 bytes and fold in parallel + int loops = length / 128; + length &= 127; + while (loops--) { + a1 = _mm_xor_si128(cmull_xmm_pair(x1024, a1), load_xmm(input + 0x00)); + b1 = _mm_xor_si128(cmull_xmm_pair(x1024, b1), load_xmm(input + 0x10)); + c1 = _mm_xor_si128(cmull_xmm_pair(x1024, c1), load_xmm(input + 0x20)); + d1 = _mm_xor_si128(cmull_xmm_pair(x1024, d1), load_xmm(input + 0x30)); + e1 = _mm_xor_si128(cmull_xmm_pair(x1024, e1), load_xmm(input + 0x40)); + f1 = _mm_xor_si128(cmull_xmm_pair(x1024, f1), load_xmm(input + 0x50)); + g1 = _mm_xor_si128(cmull_xmm_pair(x1024, g1), load_xmm(input + 0x60)); + h1 = _mm_xor_si128(cmull_xmm_pair(x1024, h1), load_xmm(input + 0x70)); + input += 128; + } + + // Fold 128 to 64 bytes - e1 through h1 fold into a1 through d1 + a1 = _mm_xor_si128(cmull_xmm_pair(x512, a1), e1); + b1 = _mm_xor_si128(cmull_xmm_pair(x512, b1), f1); + c1 = _mm_xor_si128(cmull_xmm_pair(x512, c1), g1); + d1 = _mm_xor_si128(cmull_xmm_pair(x512, d1), h1); + } + + if (length & 64) { + a1 = _mm_xor_si128(cmull_xmm_pair(x512, a1), load_xmm(input + 0x00)); + b1 = _mm_xor_si128(cmull_xmm_pair(x512, b1), load_xmm(input + 0x10)); + c1 = _mm_xor_si128(cmull_xmm_pair(x512, c1), load_xmm(input + 0x20)); + d1 = _mm_xor_si128(cmull_xmm_pair(x512, d1), load_xmm(input + 0x30)); + input += 64; + } + length &= 63; + + // Load the x^256, x^320, x^384, and x^448 constants + const __m128i x384 = load_xmm(aws_checksums_crc64nvme_constants.x384); + const __m128i x256 = load_xmm(aws_checksums_crc64nvme_constants.x256); + + // Fold 64 bytes to 16 bytes + a1 = _mm_xor_si128(d1, cmull_xmm_pair(x384, a1)); + a1 = _mm_xor_si128(a1, cmull_xmm_pair(x256, b1)); + a1 = _mm_xor_si128(a1, cmull_xmm_pair(x128, c1)); + } + + // Process any remaining chunks of 16 bytes + int loops = length / 16; + while (loops--) { + a1 = _mm_xor_si128(cmull_xmm_pair(a1, x128), load_xmm(input)); + input += 16; + } + + // The remaining length can be only 0-15 bytes + length &= 15; + if (length == 0) { + // Multiply the lower half of the crc register by x^128 (it's in the upper half) + __m128i mul_by_x128 = _mm_clmulepi64_si128(a1, x128, 0x10); + // XOR the result with the upper half of the crc + a1 = _mm_xor_si128(_mm_bsrli_si128(a1, 8), mul_by_x128); + } else { // Handle any trailing input from 1-15 bytes + // Multiply the crc by a pair of trailing length constants in order to fold it into the trailing input + a1 = cmull_xmm_pair(a1, load_xmm(aws_checksums_crc64nvme_constants.trailing[length - 1])); + // Safely load (ending at the trailing input) and mask out any leading garbage + __m128i trailing_input = mask_high_bytes(load_xmm(input + length - 16), length); + // Multiply the lower half of the trailing input register by x^128 (it's in the upper half) + __m128i mul_by_x128 = _mm_clmulepi64_si128(trailing_input, x128, 0x10); + // XOR the results with the upper half of the trailing input + a1 = _mm_xor_si128(a1, _mm_bsrli_si128(trailing_input, 8)); + a1 = _mm_xor_si128(a1, mul_by_x128); + } + + // Barrett modular reduction + const __m128i mu_poly = load_xmm(aws_checksums_crc64nvme_constants.mu_poly); + // Multiply the lower half of input by mu + __m128i mul_by_mu = _mm_clmulepi64_si128(mu_poly, a1, 0x00); + // Multiply the lower half of the mul_by_mu result by poly (it's in the upper half) + __m128i mul_by_poly = _mm_clmulepi64_si128(mu_poly, mul_by_mu, 0x01); + // Left shift mul_by_mu to get the low half into the upper half and XOR all the upper halves + __m128i reduced = _mm_xor_si128(_mm_xor_si128(a1, _mm_bslli_si128(mul_by_mu, 8)), mul_by_poly); + // After the XORs, the CRC falls in the upper half of the register - invert the bits before returning the crc + return ~(uint64_t)_mm_extract_epi64(reduced, 1); +} + +#endif /* defined(AWS_ARCH_INTEL_X64) && defined(AWS_HAVE_CLMUL) && !(defined(_MSC_VER) && _MSC_VER < 1920) */ diff --git a/contrib/restricted/aws/aws-checksums/ya.make b/contrib/restricted/aws/aws-checksums/ya.make index db901e9d09b..e0fadf1ea33 100644 --- a/contrib/restricted/aws/aws-checksums/ya.make +++ b/contrib/restricted/aws/aws-checksums/ya.make @@ -1,4 +1,4 @@ -# Generated by devtools/yamaker from nixpkgs 22.05. +# Generated by devtools/yamaker from nixpkgs 24.05. LIBRARY() @@ -6,9 +6,9 @@ LICENSE(Apache-2.0) LICENSE_TEXTS(.yandex_meta/licenses.list.txt) -VERSION(0.1.14) +VERSION(0.2.7) -ORIGINAL_SOURCE(https://github.com/awslabs/aws-checksums/archive/v0.1.14.tar.gz) +ORIGINAL_SOURCE(https://github.com/awslabs/aws-checksums/archive/v0.2.7.tar.gz) PEERDIR( contrib/restricted/aws/aws-c-common @@ -26,18 +26,24 @@ CFLAGS( -DAWS_CHECKSUMS_USE_IMPORT_EXPORT -DAWS_COMMON_USE_IMPORT_EXPORT -DHAVE_SYSCONF + -DINTEL_NO_ITTNOTIFY_API ) -IF (BUILD_TYPE == "DEBUG") - CFLAGS( - -DDEBUG_BUILD - ) -ENDIF() - SRCS( - source/crc.c + source/checksums.c + source/crc32.c + source/crc64.c + source/crc64_sw.c source/crc_sw.c source/intel/asm/crc32c_sse42_asm.c ) +IF (ARCH_X86_64) + SRC_C_AVX(source/intel/intrin/crc64nvme_clmul.c) + SRC_C_AVX512(source/intel/intrin/crc32c_sse42_avx512.c -mvpclmulqdq) + SRC_C_AVX512(source/intel/intrin/crc64nvme_avx512.c -mvpclmulqdq) +ELSEIF (ARCH_ARM64) + SRC(source/arm/crc32c_arm.c -mcrc) +ENDIF() + END() |