Bug Summary

File:rscodec.cpp
Warning:line 102, column 39
The left operand of '+' is a garbage value due to array index out of bounds

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name rscodec.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/runner/work/LibreCAD/LibreCAD/libraries/libdxfrw -fcoverage-compilation-dir=/home/runner/work/LibreCAD/LibreCAD/libraries/libdxfrw -resource-dir /usr/lib/llvm-18/lib/clang/18 -D _REENTRANT -D MUPARSER_STATIC -D QT_NO_DEBUG -I . -I ../../../Qt/6.9.0/gcc_64/mkspecs/linux-g++ -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/x86_64-linux-gnu/c++/14 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/backward -internal-isystem /usr/lib/llvm-18/lib/clang/18/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -std=gnu++1z -fdeprecated-macro -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fcxx-exceptions -fexceptions -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/runner/work/LibreCAD/LibreCAD/out/2025-05-09-020939-6317-1 -x c++ src/intern/rscodec.cpp
1/******************************************************************************
2** libDXFrw - Library to read/write DXF files (ascii & binary) **
3** **
4** Copyright (C) 2011-2014 J.F. Soriano (Rallaz), rallazz@gmail.com **
5** **
6** This library is free software, licensed under the terms of the GNU **
7** General Public License as published by the Free Software Foundation, **
8** either version 2 of the License, or (at your option) any later version. **
9** You should have received a copy of the GNU General Public License **
10** along with this program. If not, see <http://www.gnu.org/licenses/>. **
11******************************************************************************/
12
13/**
14 * Reed-Solomon codec
15 * Reed Solomon code lifted from encoder/decoder for Reed-Solomon written by Simon Rockliff
16 *
17 * Original code:
18 * This program may be freely modified and/or given to whoever wants it.
19 * A condition of such distribution is that the author's contribution be
20 * acknowledged by his name being left in the comments heading the program,
21 * however no responsibility is accepted for any financial or other loss which
22 * may result from some unforseen errors or malfunctioning of the program
23 * during use.
24 * Simon Rockliff, 26th June 1991
25 */
26
27
28#include "rscodec.h"
29#include <new> // std::nothrow
30#include <fstream>
31
32RScodec::RScodec(unsigned int pp, int mm, int tt) {
33 this->mm = mm;
34 this->tt = tt;
35 nn = (1<<mm) -1; //mm==8 nn=255
1
Assuming right operand of bit shift is non-negative but less than 32
→
36 kk = nn -(tt*2);
37 isOk = true;
38
39 alpha_to = new (std::nothrow) int[nn+1];
40 index_of = new (std::nothrow) unsigned int[nn+1];
2
←
Storing uninitialized value
→
41 gg = new (std::nothrow) int[nn-kk+1];
42
43 RSgenerate_gf(pp) ;
44 /* compute the generator polynomial for this RS code */
45 RSgen_poly() ;
3
←
Calling 'RScodec::RSgen_poly'
→
46}
47
48RScodec::~RScodec() {
49 delete[] alpha_to;
50 delete[] index_of;
51 delete[] gg;
52}
53
54
55/* generate GF(2^mm) from the irreducible polynomial p(X) in pp[0]..pp[mm]
56 lookup tables: index->polynomial form alpha_to[] contains j=alpha**i;
57 polynomial form -> index form index_of[j=alpha**i] = i
58 alpha=2 is the primitive element of GF(2^mm)
59*/
60void RScodec::RSgenerate_gf(unsigned int pp) {
61 int i, mask ;
62 int pb;
63
64 mask = 1 ;
65 alpha_to[mm] = 0 ;
66 for (i=0; i<mm; i++) {
67 alpha_to[i] = mask ;
68 index_of[alpha_to[i]] = i ;
69 pb = (pp >>(mm-1-i)) & 1;
70 if (pb!=0) {
71 alpha_to[mm] ^= mask;
72 }
73 mask <<= 1 ;
74 }
75 index_of[alpha_to[mm]] = mm ;
76 mask >>= 1 ;
77 for (i=mm+1; i<nn; i++) {
78 if (alpha_to[i-1] >= mask) {
79 alpha_to[i] = alpha_to[mm] ^ ((alpha_to[i-1]^mask)<<1) ;
80 } else alpha_to[i] = alpha_to[i-1]<<1 ;
81 index_of[alpha_to[i]] = i ;
82 }
83 index_of[0] = -1 ;
84}
85
86
87/* Obtain the generator polynomial of the tt-error correcting, length
88 nn=(2^mm -1) Reed Solomon code from the product of (X+alpha**i), i=1..2*tt
89*/
90void RScodec::RSgen_poly() {
91 int i,j ;
92 int tmp;
93 int bb = nn-kk;; //nn-kk length of parity data
94
95 gg[0] = 2 ; /* primitive element alpha = 2 for GF(2**mm) */
96 gg[1] = 1 ; /* g(x) = (X+alpha) initially */
4
←
Assigning 1
→
97 for (i=2; i<=bb; i++) {
5
←
Assuming 'i' is <= 'bb'
→
6
←
Loop condition is true. Entering loop body
→
98 gg[i] = 1 ;
99 for (j=i-1; j>0; j--)
7
←
The value 1 is assigned to 'j'
→
8
←
Loop condition is true. Entering loop body
→
100 if (gg[j] != 0) {
9
←
Taking true branch
→
101 if (gg[j]<0) { isOk=false; return; }
10
←
Taking false branch
→
102 tmp = (index_of[gg[j]]+i)%nn;
11
←
The left operand of '+' is a garbage value due to array index out of bounds
103 if (tmp<0) { isOk=false; return; }
104 gg[j] = gg[j-1]^ alpha_to[tmp] ;
105 } else {
106 gg[j] = gg[j-1] ;
107 }
108 gg[0] = alpha_to[(index_of[gg[0]]+i)%nn] ; /* gg[0] can never be zero */
109 }
110 /* convert gg[] to index form for quicker encoding */
111 for (i=0; i<=bb; i++) gg[i] = index_of[gg[i]] ;
112}
113
114int RScodec::calcDecode(unsigned char* data, int* recd, int** elp, int* d, int* l, int* u_lu, int* s, int* root, int* loc, int* z, int* err, int* reg, int bb)
115{
116 if (!isOk) return -1;
117 int count = 0;
118 int syn_error = 0;
119 int i, j, u, q;
120
121 // for (int i=0; i<nn; i++)
122 // recd[i] = index_of[recd[i]] ; /* put recd[i] into index form */
123 for (int i = 0, j = bb; i<kk; i++, j++)
124 recd[j] = index_of[data[j]]; /* put data in recd[i] into index form */
125 for (int i = kk, j = 0; i<nn; i++, j++)
126 recd[j] = index_of[data[j]]; /* put data in recd[i] into index form */
127
128 /* first form the syndromes */
129 for (i = 1; i <= bb; i++) {
130 s[i] = 0;
131 for (j = 0; j<nn; j++) {
132 if (recd[j] != -1) {
133 s[i] ^= alpha_to[(recd[j] + i*j) % nn]; /* recd[j] in index form */
134 }
135 }
136 /* convert syndrome from polynomial form to index form */
137 if (s[i] != 0) syn_error = 1; /* set flag if non-zero syndrome => error */
138 s[i] = index_of[s[i]];
139 }
140
141 if (!syn_error) { /* if no errors, ends */
142 /* no non-zero syndromes => no errors: output is received codeword */
143 return 0;
144 }
145
146 /* errors are present, try and correct */
147 /* compute the error location polynomial via the Berlekamp iterative algorithm,
148 following the terminology of Lin and Costello : d[u] is the 'mu'th
149 discrepancy, where u='mu'+1 and 'mu' (the Greek letter!) is the step number
150 ranging from -1 to 2*tt (see L&C), l[u] is the
151 degree of the elp at that step, and u_l[u] is the difference between the
152 step number and the degree of the elp.
153 */
154 /* initialise table entries */
155 d[0] = 0; /* index form */
156 d[1] = s[1]; /* index form */
157 elp[0][0] = 0; /* index form */
158 elp[1][0] = 1; /* polynomial form */
159 for (i = 1; i<bb; i++) {
160 elp[0][i] = -1; /* index form */
161 elp[1][i] = 0; /* polynomial form */
162 }
163 l[0] = 0;
164 l[1] = 0;
165 u_lu[0] = -1;
166 u_lu[1] = 0;
167 u = 0;
168
169 do {
170 u++;
171 if (d[u] == -1) {
172 l[u + 1] = l[u];
173 for (i = 0; i <= l[u]; i++) {
174 elp[u + 1][i] = elp[u][i];
175 elp[u][i] = index_of[elp[u][i]];
176 }
177 }
178 else {
179 /* search for words with greatest u_lu[q] for which d[q]!=0 */
180 q = u - 1;
181 while ((d[q] == -1) && (q>0)) q--;
182 /* have found first non-zero d[q] */
183 if (q>0) {
184 j = q;
185 do {
186 j--;
187 if ((d[j] != -1) && (u_lu[q]<u_lu[j]))
188 q = j;
189 } while (j>0);
190 }
191
192 /* have now found q such that d[u]!=0 and u_lu[q] is maximum */
193 /* store degree of new elp polynomial */
194 if (l[u]>l[q] + u - q) {
195 l[u + 1] = l[u];
196 }
197 else {
198 l[u + 1] = l[q] + u - q;
199 }
200
201 /* form new elp(x) */
202 for (i = 0; i<bb; i++) elp[u + 1][i] = 0;
203 for (i = 0; i <= l[q]; i++){
204 if (elp[q][i] != -1) {
205 elp[u + 1][i + u - q] = alpha_to[(d[u] + nn - d[q] + elp[q][i]) % nn];
206 }
207 }
208 for (i = 0; i <= l[u]; i++) {
209 elp[u + 1][i] ^= elp[u][i];
210 elp[u][i] = index_of[elp[u][i]]; /*convert old elp value to index*/
211 }
212 }
213 u_lu[u + 1] = u - l[u + 1];
214
215 /* form (u+1)th discrepancy */
216 if (u<bb){ /* no discrepancy computed on last iteration */
217 if (s[u + 1] != -1) {
218 d[u + 1] = alpha_to[s[u + 1]];
219 }
220 else {
221 d[u + 1] = 0;
222 }
223 for (i = 1; i <= l[u + 1]; i++){
224 if ((s[u + 1 - i] != -1) && (elp[u + 1][i] != 0)) {
225 d[u + 1] ^= alpha_to[(s[u + 1 - i] + index_of[elp[u + 1][i]]) % nn];
226 }
227 }
228 d[u + 1] = index_of[d[u + 1]]; /* put d[u+1] into index form */
229 }
230 } while ((u<bb) && (l[u + 1] <= tt));
231
232 u++;
233 if (l[u]>tt) { /* elp has degree has degree >tt hence cannot solve */
234 return -1; /* just output is received codeword as is */
235 }
236
237 /* can correct error */
238 /* put elp into index form */
239 for (i = 0; i <= l[u]; i++) elp[u][i] = index_of[elp[u][i]];
240
241 /* find roots of the error location polynomial */
242 for (i = 1; i <= l[u]; i++) {
243 reg[i] = elp[u][i];
244 }
245 count = 0;
246 for (i = 1; i <= nn; i++) {
247 q = 1;
248 for (j = 1; j <= l[u]; j++) {
249 if (reg[j] != -1) {
250 reg[j] = (reg[j] + j) % nn;
251 q ^= alpha_to[reg[j]];
252 }
253 }
254 if (!q) { /* store root and error location number indices */
255 root[count] = i;
256 loc[count] = nn - i;
257 count++;
258 }
259 }
260
261 if (count != l[u]) { /* no. roots != degree of elp => >tt errors and cannot solve */
262 return -1; /* just output is received codeword as is */
263 }
264
265 /* no. roots = degree of elp hence <= tt errors */
266 /* form polynomial z(x) */
267 for (i = 1; i <= l[u]; i++) { /* Z[0] = 1 always - do not need */
268 if ((s[i] != -1) && (elp[u][i] != -1)) {
269 z[i] = alpha_to[s[i]] ^ alpha_to[elp[u][i]];
270 }
271 else if ((s[i] != -1) && (elp[u][i] == -1)) {
272 z[i] = alpha_to[s[i]];
273 }
274 else if ((s[i] == -1) && (elp[u][i] != -1)) {
275 z[i] = alpha_to[elp[u][i]];
276 }
277 else {
278 z[i] = 0;
279 }
280 for (j = 1; j<i; j++) {
281 if ((s[j] != -1) && (elp[u][i - j] != -1)) {
282 z[i] ^= alpha_to[(elp[u][i - j] + s[j]) % nn];
283 }
284 }
285 z[i] = index_of[z[i]]; /* put into index form */
286 }
287
288 /* evaluate errors at locations given by error location numbers loc[i] */
289 for (i = 0; i<nn; i++) err[i] = 0;
290 for (i = 0; i<l[u]; i++) { /* compute numerator of error term first */
291 err[loc[i]] = 1; /* accounts for z[0] */
292 for (j = 1; j <= l[u]; j++) {
293 if (z[j] != -1) {
294 err[loc[i]] ^= alpha_to[(z[j] + j*root[i]) % nn];
295 }
296 }
297 if (err[loc[i]] != 0) {
298 err[loc[i]] = index_of[err[loc[i]]];
299 q = 0; /* form denominator of error term */
300 for (j = 0; j<l[u]; j++) {
301 if (j != i) {
302 q += index_of[1 ^ alpha_to[(loc[j] + root[i]) % nn]];
303 }
304 }
305 q = q % nn;
306 err[loc[i]] = alpha_to[(err[loc[i]] - q + nn) % nn];
307 data[loc[i]] ^= err[loc[i]]; /*change errors by correct data, in polynomial form */
308 }
309 }
310 return count;
311}
312
313/** take the string of symbols in data[i], i=0..(k-1) and encode systematically
314 to produce 2*tt parity symbols in bd[0]..bd[2*tt-1]
315 data[] is input and bd[] is output in polynomial form.
316 Encoding is done by using a feedback shift register with appropriate
317 connections specified by the elements of gg[], which was generated above.
318 Codeword is c(X) = data(X)*X**(nn-kk)+ b(X) */
319bool RScodec::encode(unsigned char *data, unsigned char *parity) {
320 if (!isOk) return false;
321 int i,j ;
322 int feedback ;
323 unsigned char *idata = data;
324 unsigned char *bd = parity;
325 int bb = nn-kk;; //nn-kk length of parity data
326
327 for (i=0; i<bb; i++) bd[i] = 0 ;
328 for (i=kk-1; i>=0; i--) {
329 feedback = index_of[idata[i]^bd[bb-1]] ;
330 if (feedback != -1) {
331 for (j=bb-1; j>0; j--)
332 if (gg[j] != -1)
333 bd[j] = bd[j-1]^alpha_to[(gg[j]+feedback)%nn] ;
334 else
335 bd[j] = bd[j-1] ;
336 bd[0] = alpha_to[(gg[0]+feedback)%nn] ;
337 } else {
338 for (j=bb-1; j>0; j--)
339 bd[j] = bd[j-1] ;
340 bd[0] = 0 ;
341 }
342 }
343 return true;
344}
345
346
347/* assume we have received bits grouped into mm-bit symbols in recd[i],
348 i=0..(nn-1), and recd[i] is index form (ie as powers of alpha).
349 We first compute the 2*tt syndromes by substituting alpha**i into rec(X) and
350 evaluating, storing the syndromes in s[i], i=1..2tt (leave s[0] zero) .
351 Then we use the Berlekamp iteration to find the error location polynomial
352 elp[i]. If the degree of the elp is >tt, we cannot correct all the errors
353 and hence just put out the information symbols uncorrected. If the degree of
354 elp is <=tt, we substitute alpha**i , i=1..n into the elp to get the roots,
355 hence the inverse roots, the error location numbers. If the number of errors
356 located does not equal the degree of the elp, we have more than tt errors
357 and cannot correct them. Otherwise, we then solve for the error value at
358 the error location and correct the error. The procedure is that found in
359 Lin and Costello. For the cases where the number of errors is known to be too
360 large to correct, the information symbols as received are output (the
361 advantage of systematic encoding is that hopefully some of the information
362 symbols will be okay and that if we are in luck, the errors are in the
363 parity part of the transmitted codeword). Of course, these insoluble cases
364 can be returned as error flags to the calling routine if desired. */
365/** return value: number of corrected errors or -1 if can't correct it */
366int RScodec::decode(unsigned char *data) {
367 if (!isOk) return -1;
368 int bb = nn-kk;; //nn-kk length of parity data
369
370 int *recd = new (std::nothrow) int[nn];
371 int **elp = new int*[bb + 2];
372 for (int i = 0; i < bb + 2; ++i)
373 elp[i] = new int[bb];
374 int *d = new int[bb + 2];
375 int *l = new int[bb + 2];
376 int *u_lu = new int[bb + 2];
377 int *s = new int[bb + 1];
378 int *root = new int[tt];
379 int *loc = new int[tt];
380 int *z = new int[tt+1];
381 int *err = new int[nn];
382 int *reg = new int[tt + 1];
383
384 int res = calcDecode(data, recd, elp ,d ,l, u_lu, s, root, loc ,z, err, reg, bb);
385
386 delete[] recd;
387 for (int i = 0; i < bb + 2; ++i)
388 delete[] elp[i];
389 delete[] elp;
390 delete[] d;
391 delete[] l;
392 delete[] u_lu;
393 delete[] s;
394 delete[] root;
395 delete[] loc;
396 delete[] z;
397 delete[] err;
398 delete[] reg;
399
400 return res;
401}