"Fossies" - the Fresh Open Source Software Archive

Member "cryptsetup-2.4.3/lib/verity/rs_encode_char.c" (13 Jan 2022, 4851 Bytes) of package /linux/misc/cryptsetup-2.4.3.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "rs_encode_char.c" see the Fossies "Dox" file reference documentation.

    1 /*
    2  * Reed-Solomon encoder, based on libfec
    3  *
    4  * Copyright (C) 2002, Phil Karn, KA9Q
    5  * libcryptsetup modifications
    6  *   Copyright (C) 2017-2021 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 }