On Mon, 2022-03-14 at 18:04 -0700, Andrew Pinski via Gcc-patches wrote:
> On Mon, Mar 14, 2022 at 5:33 PM Joern Rennecke
> <joern.renne...@embecosm.com> wrote:
> >
> > Most microprocessors have efficient ways to perform CRC operations, be
> > that with lookup tables, rotates, or even special instructions.
> > However, because we lack a representation for CRC in the compiler, we
> > can't do proper instruction selection. With this patch I seek out to
> > rectify this,
> > I've avoided using a mode name for the built-in functions because that
> > would tie the semantics to the size of the addressable unit. We
> > generally use abbreviations like s/l/ll for type names, which is all
> > right when the type can be widened without changing semantics. For
> > the data input, however, we also have to consider the shift count that
> > is tied to it. That is why I used a number to designate the width of
> > the data input and shift.
> >
> > For machine support, I made a start with 8 and 16 bit little-endian
> > CRC for RISCV using a
> > lookup table. I am sure once we have the basic infrastructure in the
> > tree, we'll get more
> > contributions of suitable named patterns for various ports.
>
>
> A few points.
> There are at least 9 different polynomials for the CRC-8 in common use today.
> For CRC-32 there are 5 different polynomials used.
> You don't have a patch to invoke.texi adding the descriptions of the builtins.
> How is your polynom 3rd argument described? Is it similar to how it is
> done on the wiki for the CRC?
> Does it make sense to have to list the most common polynomials in the
> documentation?
>
> Also I am sorry but micro-optimizing coremarks is just wrong. Maybe it
> is better to pick the CRC32 that is inside zip instead for a testcase
> and benchmarking against?
> Or even the CRC32C for iSCSI/ext4.
>
> I see you also don't optimize the case where you have three other
> variants of polynomials that are reversed, reciprocal and reversed
> reciocal.
In my own CRC library I've got ~30 'commonly used' CRC types, based on
the following generic definition:
template <
// number of crc result bits (polynomial order in bits)
unsigned int BitCount,
// normal polynomial without the leading 1 bit.
typename crc_impl_detail::select_int<BitCount>::type TruncPoly,
// initial remainder
typename crc_impl_detail::select_int<BitCount>::type InitRem = 0,
// final xor value
typename crc_impl_detail::select_int<BitCount>::type FinalXor = 0,
// input data byte reflected before processing (LSB / MSB first)
bool ReflectInput = false,
// output CRC reflected before the xor
bool ReflectRemainder = false >
class crc
{
...
};
and then it goes like ...
// CRC-1 (most hardware; also known as parity bit)
// x + 1
typedef crc < 1, 0x01 > crc_1;
// CRC-3
typedef crc < 3, 0x03, 0x07, 0x00, true, true> crc_3;
...
// CRC-32 (ISO 3309, ANSI X3.66, FIPS PUB 71, FED-STD-1003, ITU-T V.42,
Ethernet, SATA, MPEG-2, Gzip, PKZIP, POSIX cksum, PNG, ZMODEM)
// x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 +
x^4 + x^2 + x + 1
typedef crc < 32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true > crc_32;
typedef crc < 32, 0x04C11DB7, 0x7FFFFFFF, 0x7FFFFFFF, false, false >
crc_32_mpeg2;
typedef crc < 32, 0x04C11db7, 0x00000000, 0xFFFFFFFF, false, false >
crc_32_posix;
...
It then generates the lookup tables at compile time into .rodata for
the types that are used in the program, which is great for MCUs with
more flash/ROM than RAM.
Specific CRC types can be overridden if the system has a better way to
calculate the CRC, e.g. as hardware peripheral.
This being a library makes it relatively easy to tune and customize for
various systems.
How would that work together with your proposal?
Cheers,
Oleg
