^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Generic Reed Solomon encoder / decoder library
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * Reed Solomon code lifted from reed solomon library written by Phil Karn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * Copyright 2002 Phil Karn, KA9Q
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * Description:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * The generic Reed Solomon library provides runtime configurable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * encoding / decoding of RS codes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * Each user must call init_rs to get a pointer to a rs_control structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * for the given rs parameters. The control struct is unique per instance.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * It points to a codec which can be shared by multiple control structures.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * If a codec is newly allocated then the polynomial arrays for fast
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * encoding / decoding are built. This can take some time so make sure not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * to call this function from a time critical path. Usually a module /
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * driver should initialize the necessary rs_control structure on module /
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * driver init and release it on exit.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * The encoding puts the calculated syndrome into a given syndrome buffer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * The decoding is a two step process. The first step calculates the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * syndrome over the received (data + syndrome) and calls the second stage,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * which does the decoding / error correction itself. Many hw encoders
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) * provide a syndrome calculation over the received data + syndrome and can
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * call the second stage directly.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) #include <linux/errno.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) #include <linux/init.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) #include <linux/module.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) #include <linux/rslib.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) #include <linux/mutex.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) enum {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) RS_DECODE_LAMBDA,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) RS_DECODE_SYN,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) RS_DECODE_B,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) RS_DECODE_T,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) RS_DECODE_OMEGA,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) RS_DECODE_ROOT,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) RS_DECODE_REG,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) RS_DECODE_LOC,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) RS_DECODE_NUM_BUFFERS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) /* This list holds all currently allocated rs codec structures */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) static LIST_HEAD(codec_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) /* Protection for the list */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) static DEFINE_MUTEX(rslistlock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * codec_init - Initialize a Reed-Solomon codec
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * @symsize: symbol size, bits (1-8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * @gfpoly: Field generator polynomial coefficients
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * @gffunc: Field generator function
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * @fcr: first root of RS code generator polynomial, index form
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * @prim: primitive element to generate polynomial roots
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * @nroots: RS code generator polynomial degree (number of roots)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * @gfp: GFP_ flags for allocations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * Allocate a codec structure and the polynom arrays for faster
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * en/decoding. Fill the arrays according to the given parameters.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) int fcr, int prim, int nroots, gfp_t gfp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) int i, j, sr, root, iprim;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) struct rs_codec *rs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) rs = kzalloc(sizeof(*rs), gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) if (!rs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) INIT_LIST_HEAD(&rs->list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) rs->mm = symsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) rs->nn = (1 << symsize) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) rs->fcr = fcr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) rs->prim = prim;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) rs->nroots = nroots;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) rs->gfpoly = gfpoly;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) rs->gffunc = gffunc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) /* Allocate the arrays */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) rs->alpha_to = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) if (rs->alpha_to == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) goto err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) rs->index_of = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) if (rs->index_of == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) goto err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) rs->genpoly = kmalloc_array(rs->nroots + 1, sizeof(uint16_t), gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) if(rs->genpoly == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) goto err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) /* Generate Galois field lookup tables */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) rs->index_of[0] = rs->nn; /* log(zero) = -inf */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) if (gfpoly) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) sr = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) for (i = 0; i < rs->nn; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) rs->index_of[sr] = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) rs->alpha_to[i] = sr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) sr <<= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) if (sr & (1 << symsize))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) sr ^= gfpoly;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) sr &= rs->nn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) sr = gffunc(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) for (i = 0; i < rs->nn; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) rs->index_of[sr] = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) rs->alpha_to[i] = sr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) sr = gffunc(sr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) /* If it's not primitive, exit */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) if(sr != rs->alpha_to[0])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) goto err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) /* Find prim-th root of 1, used in decoding */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) /* prim-th root of 1, index form */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) rs->iprim = iprim / prim;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) /* Form RS code generator polynomial from its roots */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) rs->genpoly[0] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) rs->genpoly[i + 1] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) /* Multiply rs->genpoly[] by @**(root + x) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) for (j = i; j > 0; j--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) if (rs->genpoly[j] != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) rs->genpoly[j] = rs->genpoly[j -1] ^
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) rs->alpha_to[rs_modnn(rs,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) rs->index_of[rs->genpoly[j]] + root)];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) rs->genpoly[j] = rs->genpoly[j - 1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) /* rs->genpoly[0] can never be zero */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) rs->genpoly[0] =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) rs->alpha_to[rs_modnn(rs,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) rs->index_of[rs->genpoly[0]] + root)];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) /* convert rs->genpoly[] to index form for quicker encoding */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) for (i = 0; i <= nroots; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) rs->users = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) list_add(&rs->list, &codec_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) return rs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) err:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) kfree(rs->genpoly);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) kfree(rs->index_of);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) kfree(rs->alpha_to);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) kfree(rs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) * free_rs - Free the rs control structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) * @rs: The control structure which is not longer used by the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) * caller
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) * Free the control structure. If @rs is the last user of the associated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) * codec, free the codec as well.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) void free_rs(struct rs_control *rs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) struct rs_codec *cd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) if (!rs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) cd = rs->codec;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) mutex_lock(&rslistlock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) cd->users--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) if(!cd->users) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) list_del(&cd->list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) kfree(cd->alpha_to);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) kfree(cd->index_of);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) kfree(cd->genpoly);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) kfree(cd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) mutex_unlock(&rslistlock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) kfree(rs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) EXPORT_SYMBOL_GPL(free_rs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) * init_rs_internal - Allocate rs control, find a matching codec or allocate a new one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) * @symsize: the symbol size (number of bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) * @gfpoly: the extended Galois field generator polynomial coefficients,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) * with the 0th coefficient in the low order bit. The polynomial
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) * must be primitive;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) * @gffunc: pointer to function to generate the next field element,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) * or the multiplicative identity element if given 0. Used
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) * instead of gfpoly if gfpoly is 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) * @fcr: the first consecutive root of the rs code generator polynomial
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) * in index form
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) * @prim: primitive element to generate polynomial roots
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) * @nroots: RS code generator polynomial degree (number of roots)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) * @gfp: GFP_ flags for allocations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) static struct rs_control *init_rs_internal(int symsize, int gfpoly,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) int (*gffunc)(int), int fcr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) int prim, int nroots, gfp_t gfp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) struct list_head *tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) struct rs_control *rs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) unsigned int bsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) /* Sanity checks */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) if (symsize < 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) if (fcr < 0 || fcr >= (1<<symsize))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) if (prim <= 0 || prim >= (1<<symsize))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) if (nroots < 0 || nroots >= (1<<symsize))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) * The decoder needs buffers in each control struct instance to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) * avoid variable size or large fixed size allocations on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) * stack. Size the buffers to arrays of [nroots + 1].
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) rs = kzalloc(sizeof(*rs) + bsize, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) if (!rs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) mutex_lock(&rslistlock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) /* Walk through the list and look for a matching entry */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) list_for_each(tmp, &codec_list) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) struct rs_codec *cd = list_entry(tmp, struct rs_codec, list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) if (symsize != cd->mm)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) if (gfpoly != cd->gfpoly)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) if (gffunc != cd->gffunc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) if (fcr != cd->fcr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) if (prim != cd->prim)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) if (nroots != cd->nroots)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) /* We have a matching one already */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) cd->users++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) rs->codec = cd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) /* Create a new one */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) if (!rs->codec) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) kfree(rs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) rs = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) mutex_unlock(&rslistlock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) return rs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) * init_rs_gfp - Create a RS control struct and initialize it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) * @symsize: the symbol size (number of bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) * @gfpoly: the extended Galois field generator polynomial coefficients,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) * with the 0th coefficient in the low order bit. The polynomial
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) * must be primitive;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) * @fcr: the first consecutive root of the rs code generator polynomial
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) * in index form
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) * @prim: primitive element to generate polynomial roots
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) * @nroots: RS code generator polynomial degree (number of roots)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) * @gfp: Memory allocation flags.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) int nroots, gfp_t gfp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) EXPORT_SYMBOL_GPL(init_rs_gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) * init_rs_non_canonical - Allocate rs control struct for fields with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) * non-canonical representation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) * @symsize: the symbol size (number of bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) * @gffunc: pointer to function to generate the next field element,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) * or the multiplicative identity element if given 0. Used
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) * instead of gfpoly if gfpoly is 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) * @fcr: the first consecutive root of the rs code generator polynomial
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) * in index form
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) * @prim: primitive element to generate polynomial roots
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) * @nroots: RS code generator polynomial degree (number of roots)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) int fcr, int prim, int nroots)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) EXPORT_SYMBOL_GPL(init_rs_non_canonical);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) #ifdef CONFIG_REED_SOLOMON_ENC8
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) * encode_rs8 - Calculate the parity for data values (8bit data width)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) * @rsc: the rs control structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) * @data: data field of a given type
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) * @len: data length
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) * @par: parity data, must be initialized by caller (usually all 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) * @invmsk: invert data mask (will be xored on data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) * The parity uses a uint16_t data type to enable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) * symbol size > 8. The calling code must take care of encoding of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) * syndrome result for storage itself.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) uint16_t invmsk)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) #include "encode_rs.c"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) EXPORT_SYMBOL_GPL(encode_rs8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) #ifdef CONFIG_REED_SOLOMON_DEC8
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) * decode_rs8 - Decode codeword (8bit data width)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) * @rsc: the rs control structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) * @data: data field of a given type
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) * @par: received parity data field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) * @len: data length
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) * @s: syndrome data field, must be in index form
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) * (if NULL, syndrome is calculated)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) * @no_eras: number of erasures
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) * @eras_pos: position of erasures, can be NULL
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) * @invmsk: invert data mask (will be xored on data, not on parity!)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) * @corr: buffer to store correction bitmask on eras_pos
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) * The syndrome and parity uses a uint16_t data type to enable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) * symbol size > 8. The calling code must take care of decoding of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) * syndrome result and the received parity before calling this code.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) * Note: The rs_control struct @rsc contains buffers which are used for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) * decoding, so the caller has to ensure that decoder invocations are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) * serialized.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) * Returns the number of corrected symbols or -EBADMSG for uncorrectable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) * errors. The count includes errors in the parity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) uint16_t *corr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) #include "decode_rs.c"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) EXPORT_SYMBOL_GPL(decode_rs8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) #ifdef CONFIG_REED_SOLOMON_ENC16
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) * encode_rs16 - Calculate the parity for data values (16bit data width)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) * @rsc: the rs control structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) * @data: data field of a given type
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) * @len: data length
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) * @par: parity data, must be initialized by caller (usually all 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) * @invmsk: invert data mask (will be xored on data, not on parity!)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) * Each field in the data array contains up to symbol size bits of valid data.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) uint16_t invmsk)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) #include "encode_rs.c"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) EXPORT_SYMBOL_GPL(encode_rs16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) #ifdef CONFIG_REED_SOLOMON_DEC16
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) * decode_rs16 - Decode codeword (16bit data width)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) * @rsc: the rs control structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) * @data: data field of a given type
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) * @par: received parity data field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) * @len: data length
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) * @s: syndrome data field, must be in index form
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) * (if NULL, syndrome is calculated)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) * @no_eras: number of erasures
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) * @eras_pos: position of erasures, can be NULL
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) * @invmsk: invert data mask (will be xored on data, not on parity!)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) * @corr: buffer to store correction bitmask on eras_pos
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) * Each field in the data array contains up to symbol size bits of valid data.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) * Note: The rc_control struct @rsc contains buffers which are used for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) * decoding, so the caller has to ensure that decoder invocations are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) * serialized.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) * Returns the number of corrected symbols or -EBADMSG for uncorrectable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) * errors. The count includes errors in the parity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) uint16_t *corr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) #include "decode_rs.c"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) EXPORT_SYMBOL_GPL(decode_rs16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) MODULE_LICENSE("GPL");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) MODULE_AUTHOR("Phil Karn, Thomas Gleixner");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424)
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags