1 /*****************************************************************************/
2 /* LibreDWG - free implementation of the DWG file format */
3 /* */
4 /* Copyright (C) 2013, 2018-2020, 2023 Free Software Foundation, Inc. */
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 3 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 * reedsolomon.c: Reed-Solomon (255,239) en-,decoding
15 * written by Alex Papazoglou
16 * needs C99
17 */
18
19 #include "config.h"
20 #include <string.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #ifdef HAVE_MALLOC_H
24 # include <malloc.h>
25 #endif
26 #include "common.h"
27 #include "logging.h"
28 #include "reedsolomon.h"
29
30 #define debug(fmt, ...) \
31 HANDLER (OUTPUT, "%s:%d: %s() - " fmt, __FILE__, __LINE__, __func__, \
32 ##__VA_ARGS__)
33 #define POLY_LENGTH 32
34 #define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
35
36 typedef unsigned char *Poly;
37 typedef Poly *PolyRow;
38 typedef PolyRow *PolyMatrix;
39
40 /*
41 * Private functions
42 */
43 static int degree (Poly);
44 static void rowop (PolyMatrix, int, int);
45 static int fix_errors (unsigned char *, unsigned char *, unsigned char *);
46 static void solve_key_equation (unsigned char *, unsigned char *,
47 unsigned char *);
48 static unsigned char evaluate (Poly, int, unsigned char);
49 static void free_matrix (PolyMatrix);
50 static PolyMatrix initialize_matrix (unsigned char *);
51 static unsigned char f256_multiply (unsigned char, unsigned char);
52 static void dump_syndrome (unsigned char *);
53
54 /*
55 * Tables for dealing with the finite field. The specific representation
56 * of F_256 in this case is the residue field of
57 *
58 * X^8 + X^6 + X^5 + X^4 + 1 (0x0169 hex)
59 *
60 * which is primitive (e.g. X is a generator for the multiplicative group).
61 */
62 static const unsigned char f256_inverse[] = {
63 0, /* not defined */
64 0x01, 0xb4, 0xd8, 0x5a, 0x48, 0x6c, 0x78, 0x2d, 0x28, 0x24, 0xa4, 0x36, 0xc9,
65 0x3c, 0x38, 0xa2, 0xcf, 0x14, 0x6a, 0x12, 0x6b, 0x52, 0x47, 0x1b, 0xd1, 0xd0,
66 0x18, 0x1e, 0xbb, 0x1c, 0xba, 0x51, 0xb1, 0xd3, 0xa6, 0x0a, 0xa5, 0x35, 0x69,
67 0x09, 0x2c, 0x81, 0x4f, 0x29, 0x08, 0x97, 0x67, 0xb9, 0xca, 0xdc, 0x45, 0x68,
68 0x26, 0x0c, 0xc8, 0x0f, 0x3d, 0xe9, 0x61, 0x0e, 0x39, 0x5d, 0xfe, 0x9c, 0x8d,
69 0xec, 0xe1, 0xdd, 0x33, 0x53, 0x17, 0x05, 0x5b, 0xe6, 0xcc, 0xae, 0xf8, 0x80,
70 0x2b, 0xb0, 0x20, 0x16, 0x46, 0xf4, 0xe4, 0x93, 0x98, 0xa0, 0x9f, 0x04, 0x49,
71 0xff, 0x3e, 0x87, 0xc5, 0xe8, 0x3b, 0x65, 0x6f, 0x6e, 0x62, 0x96, 0x2f, 0x34,
72 0x27, 0x13, 0x15, 0x06, 0x79, 0x64, 0x63, 0xb3, 0xfa, 0xaa, 0x94, 0xc0, 0xeb,
73 0x84, 0xdf, 0x07, 0x6d, 0xa8, 0xc3, 0x9a, 0xe2, 0x7f, 0x7e, 0x4e, 0x2a, 0xf2,
74 0xc6, 0x76, 0xde, 0xc4, 0x5e, 0xda, 0xef, 0xad, 0xfc, 0x9d, 0x41, 0xbf, 0xd7,
75 0xb6, 0xf1, 0x99, 0x56, 0x73, 0xab, 0x66, 0x2e, 0x57, 0x92, 0x7c, 0xe3, 0x40,
76 0x8c, 0xa1, 0x59, 0x58, 0x9e, 0x10, 0xce, 0x0b, 0x25, 0x23, 0xd2, 0x7a, 0xc2,
77 0x72, 0x95, 0xfd, 0x8a, 0x4c, 0xf9, 0x50, 0x21, 0xfb, 0x70, 0x02, 0xd9, 0x90,
78 0xf0, 0xcb, 0x30, 0x1f, 0x1d, 0xf7, 0xd4, 0xd6, 0x8e, 0x74, 0xea, 0xa9, 0x7b,
79 0x86, 0x5f, 0x83, 0xf3, 0x37, 0x0d, 0x31, 0xb8, 0x4b, 0xe7, 0xa3, 0x11, 0x1a,
80 0x19, 0xa7, 0x22, 0xbd, 0xf6, 0xbe, 0x8f, 0x03, 0xb5, 0x88, 0xee, 0x32, 0x44,
81 0x85, 0x77, 0xed, 0x43, 0x7d, 0x9b, 0x55, 0xf5, 0x4a, 0xcd, 0x60, 0x3a, 0xc1,
82 0x75, 0x42, 0xe0, 0xdb, 0x89, 0xb7, 0x91, 0x82, 0xc7, 0x54, 0xe5, 0xd5, 0xbc,
83 0x4d, 0xaf, 0x71, 0xb2, 0x8b, 0xac, 0x3f, 0x5c,
84 };
85
86 const unsigned char f256_power[] = {
87 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x69, 0xd2, 0xcd, 0xf3, 0x8f,
88 0x77, 0xee, 0xb5, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0, 0xe9, 0xbb, 0x1f,
89 0x3e, 0x7c, 0xf8, 0x99, 0x5b, 0xb6, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 0x29,
90 0x52, 0xa4, 0x21, 0x42, 0x84, 0x61, 0xc2, 0xed, 0xb3, 0x0f, 0x1e, 0x3c, 0x78,
91 0xf0, 0x89, 0x7b, 0xf6, 0x85, 0x63, 0xc6, 0xe5, 0xa3, 0x2f, 0x5e, 0xbc, 0x11,
92 0x22, 0x44, 0x88, 0x79, 0xf2, 0x8d, 0x73, 0xe6, 0xa5, 0x23, 0x46, 0x8c, 0x71,
93 0xe2, 0xad, 0x33, 0x66, 0xcc, 0xf1, 0x8b, 0x7f, 0xfe, 0x95, 0x43, 0x86, 0x65,
94 0xca, 0xfd, 0x93, 0x4f, 0x9e, 0x55, 0xaa, 0x3d, 0x7a, 0xf4, 0x81, 0x6b, 0xd6,
95 0xc5, 0xe3, 0xaf, 0x37, 0x6e, 0xdc, 0xd1, 0xcb, 0xff, 0x97, 0x47, 0x8e, 0x75,
96 0xea, 0xbd, 0x13, 0x26, 0x4c, 0x98, 0x59, 0xb2, 0x0d, 0x1a, 0x34, 0x68, 0xd0,
97 0xc9, 0xfb, 0x9f, 0x57, 0xae, 0x35, 0x6a, 0xd4, 0xc1, 0xeb, 0xbf, 0x17, 0x2e,
98 0x5c, 0xb8, 0x19, 0x32, 0x64, 0xc8, 0xf9, 0x9b, 0x5f, 0xbe, 0x15, 0x2a, 0x54,
99 0xa8, 0x39, 0x72, 0xe4, 0xa1, 0x2b, 0x56, 0xac, 0x31, 0x62, 0xc4, 0xe1, 0xab,
100 0x3f, 0x7e, 0xfc, 0x91, 0x4b, 0x96, 0x45, 0x8a, 0x7d, 0xfa, 0x9d, 0x53, 0xa6,
101 0x25, 0x4a, 0x94, 0x41, 0x82, 0x6d, 0xda, 0xdd, 0xd3, 0xcf, 0xf7, 0x87, 0x67,
102 0xce, 0xf5, 0x83, 0x6f, 0xde, 0xd5, 0xc3, 0xef, 0xb7, 0x07, 0x0e, 0x1c, 0x38,
103 0x70, 0xe0, 0xa9, 0x3b, 0x76, 0xec, 0xb1, 0x0b, 0x16, 0x2c, 0x58, 0xb0, 0x09,
104 0x12, 0x24, 0x48, 0x90, 0x49, 0x92, 0x4d, 0x9a, 0x5d, 0xba, 0x1d, 0x3a, 0x74,
105 0xe8, 0xb9, 0x1b, 0x36, 0x6c, 0xd8, 0xd9, 0xdb, 0xdf, 0xd7, 0xc7, 0xe7, 0xa7,
106 0x27, 0x4e, 0x9c, 0x51, 0xa2, 0x2d, 0x5a, 0xb4,
107 };
108
109 static const unsigned char f256_residue[] = {
110 0x00, 0x69, 0xd2, 0xbb, 0xcd, 0xa4, 0x1f, 0x76, 0xf3, 0x9a, 0x21, 0x48, 0x3e,
111 0x57, 0xec, 0x85, 0x8f, 0xe6, 0x5d, 0x34, 0x42, 0x2b, 0x90, 0xf9, 0x7c, 0x15,
112 0xae, 0xc7, 0xb1, 0xd8, 0x63, 0x0a, 0x77, 0x1e, 0xa5, 0xcc, 0xba, 0xd3, 0x68,
113 0x01, 0x84, 0xed, 0x56, 0x3f, 0x49, 0x20, 0x9b, 0xf2, 0xf8, 0x91, 0x2a, 0x43,
114 0x35, 0x5c, 0xe7, 0x8e, 0x0b, 0x62, 0xd9, 0xb0, 0xc6, 0xaf, 0x14, 0x7d, 0xee,
115 0x87, 0x3c, 0x55, 0x23, 0x4a, 0xf1, 0x98, 0x1d, 0x74, 0xcf, 0xa6, 0xd0, 0xb9,
116 0x02, 0x6b, 0x61, 0x08, 0xb3, 0xda, 0xac, 0xc5, 0x7e, 0x17, 0x92, 0xfb, 0x40,
117 0x29, 0x5f, 0x36, 0x8d, 0xe4, 0x99, 0xf0, 0x4b, 0x22, 0x54, 0x3d, 0x86, 0xef,
118 0x6a, 0x03, 0xb8, 0xd1, 0xa7, 0xce, 0x75, 0x1c, 0x16, 0x7f, 0xc4, 0xad, 0xdb,
119 0xb2, 0x09, 0x60, 0xe5, 0x8c, 0x37, 0x5e, 0x28, 0x41, 0xfa, 0x93, 0xb5, 0xdc,
120 0x67, 0x0e, 0x78, 0x11, 0xaa, 0xc3, 0x46, 0x2f, 0x94, 0xfd, 0x8b, 0xe2, 0x59,
121 0x30, 0x3a, 0x53, 0xe8, 0x81, 0xf7, 0x9e, 0x25, 0x4c, 0xc9, 0xa0, 0x1b, 0x72,
122 0x04, 0x6d, 0xd6, 0xbf, 0xc2, 0xab, 0x10, 0x79, 0x0f, 0x66, 0xdd, 0xb4, 0x31,
123 0x58, 0xe3, 0x8a, 0xfc, 0x95, 0x2e, 0x47, 0x4d, 0x24, 0x9f, 0xf6, 0x80, 0xe9,
124 0x52, 0x3b, 0xbe, 0xd7, 0x6c, 0x05, 0x73, 0x1a, 0xa1, 0xc8, 0x5b, 0x32, 0x89,
125 0xe0, 0x96, 0xff, 0x44, 0x2d, 0xa8, 0xc1, 0x7a, 0x13, 0x65, 0x0c, 0xb7, 0xde,
126 0xd4, 0xbd, 0x06, 0x6f, 0x19, 0x70, 0xcb, 0xa2, 0x27, 0x4e, 0xf5, 0x9c, 0xea,
127 0x83, 0x38, 0x51, 0x2c, 0x45, 0xfe, 0x97, 0xe1, 0x88, 0x33, 0x5a, 0xdf, 0xb6,
128 0x0d, 0x64, 0x12, 0x7b, 0xc0, 0xa9, 0xa3, 0xca, 0x71, 0x18, 0x6e, 0x07, 0xbc,
129 0xd5, 0x50, 0x39, 0x82, 0xeb, 0x9d, 0xf4, 0x4f, 0x26,
130 };
131
132 const unsigned char f256_logarithm[] = {
133 0x00, /* not defined */
134 0x00, 0x01, 0x10, 0x02, 0x20, 0x11, 0xcc, 0x03, 0xdc, 0x21, 0xd7, 0x12, 0x7d,
135 0xcd, 0x30, 0x04, 0x40, 0xdd, 0x77, 0x22, 0x99, 0xd8, 0x8d, 0x13, 0x91, 0x7e,
136 0xec, 0xce, 0xe7, 0x31, 0x19, 0x05, 0x29, 0x41, 0x4a, 0xde, 0xb6, 0x78, 0xf7,
137 0x23, 0x26, 0x9a, 0xa1, 0xd9, 0xfc, 0x8e, 0x3d, 0x14, 0xa4, 0x92, 0x50, 0x7f,
138 0x87, 0xed, 0x6b, 0xcf, 0x9d, 0xe8, 0xd3, 0x32, 0x62, 0x1a, 0xa9, 0x06, 0xb9,
139 0x2a, 0x58, 0x42, 0xaf, 0x4b, 0x72, 0xdf, 0xe1, 0xb7, 0xad, 0x79, 0xe3, 0xf8,
140 0x5e, 0x24, 0xfa, 0x27, 0xb4, 0x9b, 0x60, 0xa2, 0x85, 0xda, 0x7b, 0xfd, 0x1e,
141 0x8f, 0xe5, 0x3e, 0x97, 0x15, 0x2c, 0xa5, 0x39, 0x93, 0x5a, 0x51, 0xc2, 0x80,
142 0x08, 0x88, 0x66, 0xee, 0xbb, 0x6c, 0xc6, 0xd0, 0x4d, 0x9e, 0x47, 0xe9, 0x74,
143 0xd4, 0x0d, 0x33, 0x44, 0x63, 0x36, 0x1b, 0xb1, 0xaa, 0x55, 0x07, 0x65, 0xba,
144 0xc5, 0x2b, 0x38, 0x59, 0xc1, 0x43, 0x35, 0xb0, 0x54, 0x4c, 0x46, 0x73, 0x0c,
145 0xe0, 0xac, 0xe2, 0x5d, 0xb8, 0x57, 0xae, 0x71, 0x7a, 0x1d, 0xe4, 0x96, 0xf9,
146 0xb3, 0x5f, 0x84, 0x25, 0xa0, 0xfb, 0x3c, 0x28, 0x49, 0xb5, 0xf6, 0x9c, 0xd2,
147 0x61, 0xa8, 0xa3, 0x4f, 0x86, 0x6a, 0xdb, 0xd6, 0x7c, 0x2f, 0xfe, 0x0f, 0x1f,
148 0xcb, 0x90, 0xeb, 0xe6, 0x18, 0x3f, 0x76, 0x98, 0x8c, 0x16, 0x8a, 0x2d, 0xc9,
149 0xa6, 0x68, 0x3a, 0xf4, 0x94, 0x82, 0x5b, 0x6f, 0x52, 0x0a, 0xc3, 0xbf, 0x81,
150 0x6e, 0x09, 0xbe, 0x89, 0xc8, 0x67, 0xf3, 0xef, 0xf0, 0xbc, 0xf1, 0x6d, 0xbd,
151 0xc7, 0xf2, 0xd1, 0xa7, 0x4e, 0x69, 0x9f, 0x3b, 0x48, 0xf5, 0xea, 0x17, 0x75,
152 0x8b, 0xd5, 0x2e, 0x0e, 0xca, 0x34, 0x53, 0x45, 0x0b, 0x64, 0xc4, 0x37, 0xc0,
153 0x1c, 0x95, 0xb2, 0x83, 0xab, 0x5c, 0x56, 0x70
154 };
155
156 /*
157 * The generator polynomial
158 */
159 static const unsigned char rsgen[] = {
160 0x6a, 0xe3, 0x63, 0x1f, 0xa1, 0x24, 0x9e, 0x44, 0x13,
161 0x1e, 0x2f, 0xfc, 0xfd, 0xce, 0xa9, 0xdb, 0x01,
162 };
163
164 static unsigned char
165 f256_multiply (unsigned char a, unsigned char b)
166 {
167 unsigned int prod = 0;
168 unsigned int A = a;
169 unsigned int B = b;
170
171 while (B != 0)
172 {
173 if (B & 1)
174 prod ^= A;
175
176 B >>= 1;
177 A <<= 1;
178 }
179
180 prod ^= f256_residue[prod >> 8];
181 return prod & 0xff;
182 }
183
184 /*
185 * Encode a block. Only the trailing 16 parity bytes are computed in
186 * a buffer which caller preallocates.
187 */
188 void
189 rs_encode_block (unsigned char *parity, unsigned char *src, int count)
190 {
191 int i, j;
192 unsigned char leader, coeff;
193
194 memset (parity, 0, 16);
195
196 i = count;
197 /* Horner's method / long division */
198 while (i--)
199 {
200 leader = parity[15];
201 for (j = 15; j > 0; j--)
202 parity[j] = parity[j - 1] ^ f256_multiply (leader, rsgen[j]);
203
204 parity[0] = src[i] ^ f256_multiply (leader, rsgen[0]);
205 }
206
207 for (i = 16; i > 0; i--)
208 {
209 leader = parity[15];
210 for (j = 15; j > 0; j--)
211 parity[j] = parity[j - 1] ^ f256_multiply (leader, rsgen[j]);
212 parity[0] = f256_multiply (leader, rsgen[0]);
213 }
214 }
215
216 /*
217 * Decode a 255-byte block in place. Returns number of corrected errors,
218 * if fix is set, or -1 in case of unfixed errors.
219 */
220 int
221 rs_decode_block (unsigned char *blk, int fix)
222 {
223 int i, j;
224 unsigned char leader;
225 unsigned char *synbuf, *sigma, *omega;
226 int errflag = 0;
227
228 synbuf = (unsigned char *)malloc (POLY_LENGTH);
229 memset (synbuf, 0, 16);
230
231 for (j = 0; j < 16; j++)
232 {
233 synbuf[j] = evaluate (blk, 255, f256_power[j + 1]);
234 if (synbuf[j] != 0)
235 errflag = 1;
236 }
237
238 if (!errflag)
239 {
240 debug ("No error in Reed-Solomon block\n");
241 free (synbuf);
242 return 0;
243 }
244
245 debug ("Errors detected in Reed-Solomon block\n");
246 dump_syndrome (synbuf);
247
248 if (!fix)
249 {
250 free (synbuf);
251 return -1;
252 }
253
254 sigma = (unsigned char *)malloc (POLY_LENGTH);
255 memset (sigma, 0, POLY_LENGTH);
256
257 omega = (unsigned char *)malloc (POLY_LENGTH);
258 memset (omega, 0, POLY_LENGTH);
259
260 solve_key_equation (synbuf, sigma, omega);
261 i = fix_errors (blk, sigma, omega);
262
263 free (sigma);
264 free (omega);
265 free (synbuf);
266 if (i < 0)
267 debug ("Errors in Reed-Solomon block are not recoverable\n");
268 else
269 debug ("Fixed errors in Reed-Solomon block: %d\n", i);
270
271 return i;
272 }
273
274 static int
275 degree (Poly poly)
276 {
277 int i;
278 i = POLY_LENGTH - 1;
279
280 while (i--)
281 if (poly[i] != 0)
282 break;
283 return i;
284 }
285
286 static void
287 rowop (PolyMatrix matrix, int dst, int src)
288 {
289 int dstd, srcd;
290 int limit;
291 int power;
292 unsigned char coeff;
293 int i, j, k, l;
294
295 dstd = degree (matrix[dst][2]); // 0..31
296 srcd = degree (matrix[src][2]); // 0..31
297 power = dstd - srcd; // -31..31
298
299 coeff = f256_inverse[matrix[src][2][srcd]];
300 coeff = f256_multiply (coeff, matrix[dst][2][dstd]);
301
302 /* row operation */
303 GCC14_DIAG_IGNORE (-Wanalyzer-possible-null-dereference)
304 for (j = 0; j < 3; j++)
305 {
306 limit = MIN (17 - power, POLY_LENGTH); // -14..48
307 for (i = 0; i < limit; i++)
308 {
309 // i + power: -31..78
310 matrix[dst][j][i + power]
311 ^= f256_multiply (coeff, matrix[src][j][i]);
312 }
313 }
314 GCC14_DIAG_RESTORE
315 }
316
317 static PolyMatrix
318 initialize_matrix (unsigned char *s)
319 {
320 int deg;
321 PolyMatrix matrix;
322 int i, j;
323
324 matrix = (PolyMatrix)calloc (2, sizeof (PolyRow));
325 if (!matrix)
326 return NULL;
327 for (i = 0; i < 2; i++)
328 {
329 matrix[i] = (PolyRow)calloc (3, sizeof (Poly));
330 if (!matrix[i])
331 {
332 free_matrix (matrix);
333 return NULL;
334 }
335 for (j = 0; j < 3; j++)
336 {
337 matrix[i][j] = (Poly)calloc (1, POLY_LENGTH);
338 if (!matrix[i][j])
339 {
340 free_matrix (matrix);
341 return NULL;
342 }
343 }
344 }
345
346 /* Initialize matrix */
347 matrix[0][0][0] = 1;
348 memcpy (matrix[0][2], s, 16);
349
350 matrix[1][1][0] = 1;
351 matrix[1][2][16] = 1;
352
353 return matrix;
354 }
355
356 static void
357 free_matrix (PolyMatrix matrix)
358 {
359 int i, j;
360
361 for (i = 0; i < 2; i++)
362 {
363 for (j = 0; j < 2; j++)
364 {
365 GCC14_DIAG_IGNORE (-Wanalyzer-null-dereference)
366 if (matrix[i][j])
367 free (matrix[i][j]);
368 GCC14_DIAG_RESTORE
369 }
370 GCC14_DIAG_IGNORE (-Wanalyzer-malloc-leak)
371 if (matrix[i])
372 free (matrix[i]);
373 GCC14_DIAG_RESTORE
374 }
375 free (matrix);
376 }
377
378 static unsigned char
379 evaluate (Poly poly, int deg, unsigned char x)
380 {
381 unsigned char y;
382
383 y = poly[deg];
384 while (deg >= 0)
385 {
386 y = f256_multiply (x, y) ^ poly[deg];
387 deg--;
388 }
389 return y;
390 }
391
392 static void
393 solve_key_equation (unsigned char *s, unsigned char *sigma,
394 unsigned char *omega)
395 {
396 int fixed_row;
397 PolyMatrix matrix;
398 unsigned char leader0, leader1;
399 int x, i;
400
401 matrix = initialize_matrix (s);
402 if (!matrix)
403 return;
404 fixed_row = 0;
405
406 while (degree (matrix[fixed_row][0]) > 8
407 || degree (matrix[fixed_row][2]) > 7)
408 {
409 if (degree (matrix[0][2]) < degree (matrix[1][2]))
410 {
411 fixed_row = 0;
412 rowop (matrix, 1, 0);
413 }
414 else
415 {
416 fixed_row = 1;
417 rowop (matrix, 0, 1);
418 }
419 }
420
421 memcpy (sigma, matrix[fixed_row][0], POLY_LENGTH);
422 memcpy (omega, matrix[fixed_row][2], POLY_LENGTH);
423
424 free_matrix (matrix);
425 }
426
427 static int
428 fix_errors (unsigned char *blk, unsigned char *sigma, unsigned char *omega)
429 {
430 int i, j, x, d;
431 int nerr;
432 unsigned char errorval;
433 unsigned char roots[8];
434 unsigned char chaff;
435
436 nerr = 0;
437
438 for (x = 0; x < 256; x++)
439 {
440 if (evaluate (sigma, 8, x) == 0)
441 roots[nerr++] = x;
442 }
443
444 d = degree (sigma);
445 if (nerr != d)
446 return -1; /* if sigma doesn't split, the error is not recoverable */
447
448 /* differentiate sigma in place*/
449 for (i = 0; i < 8; i++)
450 {
451 sigma[2 * i] = sigma[2 * i + 1];
452 sigma[2 * i + 1] = 0;
453 }
454
455 for (i = 0; i < nerr; i++)
456 {
457 int pos;
458 unsigned char sigmaval = evaluate (sigma, 16, roots[i]);
459 unsigned char omegaval = evaluate (omega, 16, roots[i]);
460
461 chaff = f256_inverse[sigmaval];
462 errorval = f256_multiply (chaff, omegaval);
463 pos = f256_logarithm[f256_inverse[roots[i]]];
464
465 blk[pos] ^= errorval;
466 }
467 return nerr;
468 }
469
470 /*
471 * Some debugging code, for developer use.
472 */
473 #ifdef DEBUG
474 static void
475 debug_row (PolyRow row)
476 {
477 int j, k;
478 for (j = 0; j < 4; j++)
479 {
480 for (k = 0; k < 3; k++)
481 {
482 HANDLER (OUTPUT, " %02x %02x %02x %02x ", row[k][4 * j + 0],
483 row[k][4 * j + 1], row[k][4 * j + 2], row[k][4 * j + 3]);
484 if (k != 2)
485 {
486 HANDLER (OUTPUT, " | ");
487 }
488 }
489 HANDLER (OUTPUT, "\n");
490 }
491 HANDLER (OUTPUT, " %02x | %02x | %02x \n", row[0][16],
492 row[1][16], row[2][16]);
493 }
494
495 static void
496 dump_matrix (PolyMatrix matrix)
497 {
498 debug ("Matrix:\n");
499 debug_row (matrix[0]);
500 HANDLER (OUTPUT, "\n");
501 debug_row (matrix[1]);
502 }
503
504 #endif
505
506 static void
507 dump_syndrome (unsigned char *s)
508 {
509 int i;
510 debug ("Syndrome: ");
511 for (i = 0; i < 16; i++)
512 {
513 if (i)
514 HANDLER (OUTPUT, "-");
515 HANDLER (OUTPUT, "%02x", s[i]);
516 }
517 HANDLER (OUTPUT, "\n");
518 }