Quelle  crc-clmul-template.h   Sprache: C

/* SPDX-License-Identifier: GPL-2.0-or-later */
/* Copyright 2025 Google LLC */

/*
 * This file is a "template" that generates a CRC function optimized using the
 * RISC-V Zbc (scalar carryless multiplication) extension.  The includer of this
 * file must define the following parameters to specify the type of CRC:
 *
 * crc_t: the data type of the CRC, e.g. u32 for a 32-bit CRC
 * LSB_CRC: 0 for a msb (most-significant-bit) first CRC, i.e. natural
 *  mapping between bits and polynomial coefficients
 *          1 for a lsb (least-significant-bit) first CRC, i.e. reflected
 *          mapping between bits and polynomial coefficients
 */

#include <asm/byteorder.h>
#include <linux/minmax.h>

#define CRC_BITS (8 * sizeof(crc_t)) /* a.k.a. 'n' */

static inline unsigned long clmul(unsigned long a, unsigned long b)
{
 unsigned long res;

 asm(".option push\n"
     ".option arch,+zbc\n"
     "clmul %0, %1, %2\n"
     ".option pop\n"
     : "=r" (res) : "r" (a), "r" (b));
 return res;
}

static inline unsigned long clmulh(unsigned long a, unsigned long b)
{
 unsigned long res;

 asm(".option push\n"
     ".option arch,+zbc\n"
     "clmulh %0, %1, %2\n"
     ".option pop\n"
     : "=r" (res) : "r" (a), "r" (b));
 return res;
}

static inline unsigned long clmulr(unsigned long a, unsigned long b)
{
 unsigned long res;

 asm(".option push\n"
     ".option arch,+zbc\n"
     "clmulr %0, %1, %2\n"
     ".option pop\n"
     : "=r" (res) : "r" (a), "r" (b));
 return res;
}

/*
 * crc_load_long() loads one "unsigned long" of aligned data bytes, producing a
 * polynomial whose bit order matches the CRC's bit order.
 */
#ifdef CONFIG_64BIT
#  if LSB_CRC
#    define crc_load_long(x) le64_to_cpup(x)
#  else
#    define crc_load_long(x) be64_to_cpup(x)
#  endif
#else
#  if LSB_CRC
#    define crc_load_long(x) le32_to_cpup(x)
#  else
#    define crc_load_long(x) be32_to_cpup(x)
#  endif
#endif

/* XOR @crc into the end of @msgpoly that represents the high-order terms. */
static inline unsigned long
crc_clmul_prep(crc_t crc, unsigned long msgpoly)
{
#if LSB_CRC
 return msgpoly ^ crc;
#else
 return msgpoly ^ ((unsigned long)crc << (BITS_PER_LONG - CRC_BITS));
#endif
}

/*
 * Multiply the long-sized @msgpoly by x^n (a.k.a. x^CRC_BITS) and reduce it
 * modulo the generator polynomial G.  This gives the CRC of @msgpoly.
 */
static inline crc_t
crc_clmul_long(unsigned long msgpoly, const struct crc_clmul_consts *consts)
{
 unsigned long tmp;

 /*
 * First step of Barrett reduction with integrated multiplication by
 * x^n: calculate floor((msgpoly * x^n) / G).  This is the value by
 * which G needs to be multiplied to cancel out the x^n and higher terms
 * of msgpoly * x^n.  Do it using the following formula:
 *
 * msb-first:
 *    floor((msgpoly * floor(x^(BITS_PER_LONG-1+n) / G)) / x^(BITS_PER_LONG-1))
 * lsb-first:
 *    floor((msgpoly * floor(x^(BITS_PER_LONG-1+n) / G) * x) / x^BITS_PER_LONG)
 *
 * barrett_reduction_const_1 contains floor(x^(BITS_PER_LONG-1+n) / G),
 * which fits a long exactly.  Using any lower power of x there would
 * not carry enough precision through the calculation, while using any
 * higher power of x would require extra instructions to handle a wider
 * multiplication.  In the msb-first case, using this power of x results
 * in needing a floored division by x^(BITS_PER_LONG-1), which matches
 * what clmulr produces.  In the lsb-first case, a factor of x gets
 * implicitly introduced by each carryless multiplication (shown as
 * '* x' above), and the floored division instead needs to be by
 * x^BITS_PER_LONG which matches what clmul produces.
 */
#if LSB_CRC
 tmp = clmul(msgpoly, consts->barrett_reduction_const_1);
#else
 tmp = clmulr(msgpoly, consts->barrett_reduction_const_1);
#endif

 /*
 * Second step of Barrett reduction:
 *
 *    crc := (msgpoly * x^n) + (G * floor((msgpoly * x^n) / G))
 *
 * This reduces (msgpoly * x^n) modulo G by adding the appropriate
 * multiple of G to it.  The result uses only the x^0..x^(n-1) terms.
 * HOWEVER, since the unreduced value (msgpoly * x^n) is zero in those
 * terms in the first place, it is more efficient to do the equivalent:
 *
 *    crc := ((G - x^n) * floor((msgpoly * x^n) / G)) mod x^n
 *
 * In the lsb-first case further modify it to the following which avoids
 * a shift, as the crc ends up in the physically low n bits from clmulr:
 *
 *    product := ((G - x^n) * x^(BITS_PER_LONG - n)) * floor((msgpoly * x^n) / G) * x
 *    crc := floor(product / x^(BITS_PER_LONG + 1 - n)) mod x^n
 *
 * barrett_reduction_const_2 contains the constant multiplier (G - x^n)
 * or (G - x^n) * x^(BITS_PER_LONG - n) from the formulas above.  The
 * cast of the result to crc_t is essential, as it applies the mod x^n!
 */
#if LSB_CRC
 return clmulr(tmp, consts->barrett_reduction_const_2);
#else
 return clmul(tmp, consts->barrett_reduction_const_2);
#endif
}

/* Update @crc with the data from @msgpoly. */
static inline crc_t
crc_clmul_update_long(crc_t crc, unsigned long msgpoly,
        const struct crc_clmul_consts *consts)
{
 return crc_clmul_long(crc_clmul_prep(crc, msgpoly), consts);
}

/* Update @crc with 1 <= @len < sizeof(unsigned long) bytes of data. */
static inline crc_t
crc_clmul_update_partial(crc_t crc, const u8 *p, size_t len,
    const struct crc_clmul_consts *consts)
{
 unsigned long msgpoly;
 size_t i;

#if LSB_CRC
 msgpoly = (unsigned long)p[0] << (BITS_PER_LONG - 8);
 for (i = 1; i < len; i++)
  msgpoly = (msgpoly >> 8) ^ ((unsigned long)p[i] << (BITS_PER_LONG - 8));
#else
 msgpoly = p[0];
 for (i = 1; i < len; i++)
  msgpoly = (msgpoly << 8) ^ p[i];
#endif

 if (len >= sizeof(crc_t)) {
 #if LSB_CRC
  msgpoly ^= (unsigned long)crc << (BITS_PER_LONG - 8*len);
 #else
  msgpoly ^= (unsigned long)crc << (8*len - CRC_BITS);
 #endif
  return crc_clmul_long(msgpoly, consts);
 }
#if LSB_CRC
 msgpoly ^= (unsigned long)crc << (BITS_PER_LONG - 8*len);
 return crc_clmul_long(msgpoly, consts) ^ (crc >> (8*len));
#else
 msgpoly ^= crc >> (CRC_BITS - 8*len);
 return crc_clmul_long(msgpoly, consts) ^ (crc << (8*len));
#endif
}

static inline crc_t
crc_clmul(crc_t crc, const void *p, size_t len,
   const struct crc_clmul_consts *consts)
{
 size_t align;

 /* This implementation assumes that the CRC fits in an unsigned long. */
 BUILD_BUG_ON(sizeof(crc_t) > sizeof(unsigned long));

 /* If the buffer is not long-aligned, align it. */
 align = (unsigned long)p % sizeof(unsigned long);
 if (align && len) {
  align = min(sizeof(unsigned long) - align, len);
  crc = crc_clmul_update_partial(crc, p, align, consts);
  p += align;
  len -= align;
 }

 if (len >= 4 * sizeof(unsigned long)) {
  unsigned long m0, m1;

  m0 = crc_clmul_prep(crc, crc_load_long(p));
  m1 = crc_load_long(p + sizeof(unsigned long));
  p += 2 * sizeof(unsigned long);
  len -= 2 * sizeof(unsigned long);
  /*
 * Main loop.  Each iteration starts with a message polynomial
 * (x^BITS_PER_LONG)*m0 + m1, then logically extends it by two
 * more longs of data to form x^(3*BITS_PER_LONG)*m0 +
 * x^(2*BITS_PER_LONG)*m1 + x^BITS_PER_LONG*m2 + m3, then
 * "folds" that back into a congruent (modulo G) value that uses
 * just m0 and m1 again.  This is done by multiplying m0 by the
 * precomputed constant (x^(3*BITS_PER_LONG) mod G) and m1 by
 * the precomputed constant (x^(2*BITS_PER_LONG) mod G), then
 * adding the results to m2 and m3 as appropriate.  Each such
 * multiplication produces a result twice the length of a long,
 * which in RISC-V is two instructions clmul and clmulh.
 *
 * This could be changed to fold across more than 2 longs at a
 * time if there is a CPU that can take advantage of it.
 */
  do {
   unsigned long p0, p1, p2, p3;

   p0 = clmulh(m0, consts->fold_across_2_longs_const_hi);
   p1 = clmul(m0, consts->fold_across_2_longs_const_hi);
   p2 = clmulh(m1, consts->fold_across_2_longs_const_lo);
   p3 = clmul(m1, consts->fold_across_2_longs_const_lo);
   m0 = (LSB_CRC ? p1 ^ p3 : p0 ^ p2) ^ crc_load_long(p);
   m1 = (LSB_CRC ? p0 ^ p2 : p1 ^ p3) ^
        crc_load_long(p + sizeof(unsigned long));

   p += 2 * sizeof(unsigned long);
   len -= 2 * sizeof(unsigned long);
  } while (len >= 2 * sizeof(unsigned long));

  crc = crc_clmul_long(m0, consts);
  crc = crc_clmul_update_long(crc, m1, consts);
 }

 while (len >= sizeof(unsigned long)) {
  crc = crc_clmul_update_long(crc, crc_load_long(p), consts);
  p += sizeof(unsigned long);
  len -= sizeof(unsigned long);
 }

 if (len)
  crc = crc_clmul_update_partial(crc, p, len, consts);

 return crc;
}