lib/verity/rs_encode_char.c

   1 /*
   2  * Reed-Solomon encoder, based on libfec
   3  *
   4  * Copyright (C) 2002, Phil Karn, KA9Q
   5  * libcryptsetup modifications
   6  *   Copyright (C) 2017-2020 Red Hat, Inc. All rights reserved.
   7  *
   8  * This file is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This file is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this file; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22
  23 #include <string.h>
  24 #include <stdlib.h>
  25
  26 #include "rs.h"
  27
  28 /* Initialize a Reed-Solomon codec
  29  * symsize = symbol size, bits
  30  * gfpoly = Field generator polynomial coefficients
  31  * fcr = first root of RS code generator polynomial, index form
  32  * prim = primitive element to generate polynomial roots
  33  * nroots = RS code generator polynomial degree (number of roots)
  34  * pad = padding bytes at front of shortened block
  35  */
  36 struct rs *init_rs_char(int symsize, int gfpoly, int fcr, int prim, int nroots, int pad)
  37 {
  38         struct rs *rs;
  39         int i, j, sr, root, iprim;
  40
  41         /* Check parameter ranges */
  42         if (symsize < 0 || symsize > 8 * (int)sizeof(data_t))
  43                 return NULL;
  44         if (fcr < 0 || fcr >= (1<<symsize))
  45                 return NULL;
  46         if (prim <= 0 || prim >= (1<<symsize))
  47                 return NULL;
  48         if (nroots < 0 || nroots >= (1<<symsize))
  49                 return NULL; /* Can't have more roots than symbol values! */
  50
  51         if (pad < 0 || pad >= ((1<<symsize) - 1 - nroots))
  52                 return NULL; /* Too much padding */
  53
  54         rs = calloc(1, sizeof(struct rs));
  55         if (rs == NULL)
  56                 return NULL;
  57
  58         rs->mm = symsize;
  59         rs->nn = (1<<symsize) - 1;
  60         rs->pad = pad;
  61
  62         rs->alpha_to = malloc(sizeof(data_t) * (rs->nn + 1));
  63         if (rs->alpha_to == NULL) {
  64                 free(rs);
  65                 return NULL;
  66         }
  67         rs->index_of = malloc(sizeof(data_t) * (rs->nn + 1));
  68         if (rs->index_of == NULL) {
  69                 free(rs->alpha_to);
  70                 free(rs);
  71                 return NULL;
  72         }
  73         memset(rs->index_of, 0, sizeof(data_t) * (rs->nn + 1));
  74
  75         /* Generate Galois field lookup tables */
  76         rs->index_of[0] = A0; /* log(zero) = -inf */
  77         rs->alpha_to[A0] = 0; /* alpha**-inf = 0 */
  78         sr = 1;
  79         for (i = 0; i < rs->nn; i++) {
  80                 rs->index_of[sr] = i;
  81                 rs->alpha_to[i] = sr;
  82                 sr <<= 1;
  83                 if(sr & (1<<symsize))
  84                         sr ^= gfpoly;
  85                 sr &= rs->nn;
  86         }
  87         if (sr != 1) {
  88                 /* field generator polynomial is not primitive! */
  89                 free(rs->alpha_to);
  90                 free(rs->index_of);
  91                 free(rs);
  92                 return NULL;
  93         }
  94
  95         /* Form RS code generator polynomial from its roots */
  96         rs->genpoly = malloc(sizeof(data_t) * (nroots + 1));
  97         if (rs->genpoly == NULL) {
  98                 free(rs->alpha_to);
  99                 free(rs->index_of);
 100                 free(rs);
 101                 return NULL;
 102         }
 103
 104         rs->fcr = fcr;
 105         rs->prim = prim;
 106         rs->nroots = nroots;
 107
 108         /* Find prim-th root of 1, used in decoding */
 109         for (iprim = 1; (iprim % prim) != 0; iprim += rs->nn)
 110                 ;
 111         rs->iprim = iprim / prim;
 112
 113         rs->genpoly[0] = 1;
 114         for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
 115                 rs->genpoly[i + 1] = 1;
 116
 117                 /* Multiply rs->genpoly[] by  @**(root + x) */
 118                 for (j = i; j > 0; j--){
 119                         if (rs->genpoly[j] != 0)
 120                                 rs->genpoly[j] = rs->genpoly[j - 1] ^ rs->alpha_to[modnn(rs, rs->index_of[rs->genpoly[j]] + root)];
 121                         else
 122                                 rs->genpoly[j] = rs->genpoly[j - 1];
 123                 }
 124                 /* rs->genpoly[0] can never be zero */
 125                 rs->genpoly[0] = rs->alpha_to[modnn(rs, rs->index_of[rs->genpoly[0]] + root)];
 126         }
 127         /* convert rs->genpoly[] to index form for quicker encoding */
 128         for (i = 0; i <= nroots; i++)
 129                 rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
 130
 131         return rs;
 132 }
 133
 134 void free_rs_char(struct rs *rs)
 135 {
 136         if (!rs)
 137                 return;
 138
 139         free(rs->alpha_to);
 140         free(rs->index_of);
 141         free(rs->genpoly);
 142         free(rs);
 143 }
 144
 145 void encode_rs_char(struct rs *rs, data_t *data, data_t *parity)
 146 {
 147         int i, j;
 148         data_t feedback;
 149
 150         memset(parity, 0, rs->nroots * sizeof(data_t));
 151
 152         for (i = 0; i < rs->nn - rs->nroots - rs->pad; i++) {
 153                 feedback = rs->index_of[data[i] ^ parity[0]];
 154                 if (feedback != A0) {
 155                         /* feedback term is non-zero */
 156 #ifdef UNNORMALIZED
 157                         /* This line is unnecessary when GENPOLY[NROOTS] is unity, as it must
 158                          * always be for the polynomials constructed by init_rs() */
 159                         feedback = modnn(rs, rs->nn - rs->genpoly[rs->nroots] + feedback);
 160 #endif
 161                         for (j = 1; j < rs->nroots; j++)
 162                                 parity[j] ^= rs->alpha_to[modnn(rs, feedback + rs->genpoly[rs->nroots - j])];
 163                 }
 164
 165                 /* Shift */
 166                 memmove(&parity[0], &parity[1], sizeof(data_t) * (rs->nroots - 1));
 167
 168                 if (feedback != A0)
 169                         parity[rs->nroots - 1] = rs->alpha_to[modnn(rs, feedback + rs->genpoly[0])];
 170                 else
 171                         parity[rs->nroots - 1] = 0;
 172         }
 173 }