Re: What exactly is our CRC algorithm?

On 01/09/2015 10:32 AM, Abhijit Menon-Sen wrote:
> 2. The sse4.2 patch has only some minor compile fixes.
>
> I have built and tested both patches individually on little-endian
> (amd64) and big-endian (ppc) systems. I verified that the _sse is
> chosen at startup on the former, and _sb8 on the latter, and that
> both implementations function correctly with respect to HEAD.

I'd like to arrange this somewhat differently, to keep the really
low-level assembler blocks and such separate from the higher level
parts. Especially now that pg_crc.c is in src/common and src/port, it
doesn't seem appropriate to have assembler code in there. Also, some of
the high-level code can be reused if we later add support e.g. for the
ARMv8 CRC instructions.

I propose that we add a new header file in src/port, let's call it
crc_instructions.h. That file contains the very low-level stuff, the
pg_asm_crc32q() and pg_asm_crc32b() inline functions, which just contain
the single assembler instruction. Or the corresponding mnemomic or macro
depending on the compiler; the point of the crc_instructions.h header is
to hide the differences between compilers and architectures.

If the CRC instructions are available, crc_instructions.h defines
PG_HAVE_CRC32C_INSTRUCTIONS, as well as the pg_asm_crc32q() and
pg_asm_crc32b() macros/functions. It also defines
pg_crc32_instructions_runtime_check(), to perform the runtime check to
determine whether the instructions can be used on the current platform
(i.e. if you're running on a CPU with SSE 4.2 support). There's another
symbol PG_CRC32C_INSTRUCTIONS_NEED_RUNTIME_CHECK, which indicates
whether the runtime check is needed. That's currently always defined
when PG_HAVE_CRC32C_INSTRUCTIONS is, but conceivably you might want to
build a version that skips the runtime check altogether, and doesn't
therefore require the slicing-by-8 fallback implementation at all.
Gentoo users might like that ;-), as well as possible future
architectures that always have CRC32 instructions.

Attached is a patch along those lines. I haven't done much testing, but
it demonstrates the code structure I have in mind.

A couple of remarks on your original patch, which also apply to the
attached version:

> +static inline pg_crc32
> +pg_asm_crc32b(pg_crc32 crc, unsigned char data)
> +{
> +#if defined(__GNUC__) && defined(__x86_64__)
> +    __asm__ ("crc32b %[data], %[crc]\n" : [crc] "+r" (crc) : [data] "rm" (data));
> +    return crc;
> +#elif defined(_MSC_VER)
> +    return _mm_crc32_u8(crc, data);
> +#else
> +    /* Can't generate crc32b, but keep the compiler quiet. */
> +    return 0;
> +#endif

I believe the CRC instructions are also available in 32-bit mode, so the
check for __x86_64__ is not needed. Right? Any CPU recent enough to have
these instructions certainly supports the x86-64 instruction set, but
you might nevertheless have compiled and be running in i386 mode.

It would be nice to use GCC's builtin intrinsics, __builtin_ia32_crc32*
where available, but I guess those are only available if you build with
-msse4.2, and that would defeat the point of the runtime check.

I believe the _mm_* mnemonics would also work with the Intel compiler.

- Heikki