?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Upgraded GRUB2 to 2.00 release.
[AROS.git] / arch / all-pc / boot / grub2-aros / grub-core / lib / reed_solomon.c
blob704ebd3f2559a96ae81b7899779fd9e655acd20e
1 /*
2 * GRUB -- GRand Unified Bootloader
3 * Copyright (C) 2010 Free Software Foundation, Inc.
4 *
5 * GRUB is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * GRUB is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with GRUB. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #ifdef TEST
20 #include <stdio.h>
21 #include <string.h>
22 #include <stdlib.h>
23 #define xmalloc malloc
24 #define grub_memset memset
25 #define grub_memcpy memcpy
26 #endif
27
28 #ifndef STANDALONE
29 #include <assert.h>
30 #endif
31
32 #ifndef STANDALONE
33 #ifdef TEST
34 typedef unsigned int grub_size_t;
35 typedef unsigned char grub_uint8_t;
36 #else
37 #include <grub/types.h>
38 #include <grub/reed_solomon.h>
39 #include <grub/util/misc.h>
40 #include <grub/misc.h>
41 #endif
42 #endif
43
44 #define SECTOR_SIZE 512
45 #define MAX_BLOCK_SIZE (200 * SECTOR_SIZE)
46
47 #ifdef STANDALONE
48 #ifdef TEST
49 typedef unsigned int grub_size_t;
50 typedef unsigned char grub_uint8_t;
51 #else
52 #include <grub/types.h>
53 #include <grub/misc.h>
54 #endif
55 void
56 grub_reed_solomon_recover (void *ptr_, grub_size_t s, grub_size_t rs);
57 #endif
58
59 #define GF_SIZE 8
60 typedef grub_uint8_t gf_single_t;
61 #define GF_POLYNOMIAL 0x1d
62 #define GF_INVERT2 0x8e
63 #if defined (STANDALONE) && !defined (TEST)
64 static gf_single_t * const gf_powx __attribute__ ((section(".text"))) = (void *) 0x100000;
65 static gf_single_t * const gf_powx_inv __attribute__ ((section(".text"))) = (void *) 0x100200;
66 static int *const chosenstat __attribute__ ((section(".text"))) = (void *) 0x100300;
67 static gf_single_t *const sigma __attribute__ ((section(".text"))) = (void *) 0x100700;
68 static gf_single_t *const errpot __attribute__ ((section(".text"))) = (void *) 0x100800;
69 static int *const errpos __attribute__ ((section(".text"))) = (void *) 0x100900;
70 static gf_single_t *const sy __attribute__ ((section(".text"))) = (void *) 0x100d00;
71 static gf_single_t *const mstat __attribute__ ((section(".text"))) = (void *) 0x100e00;
72 static gf_single_t *const errvals __attribute__ ((section(".text"))) = (void *) 0x100f00;
73 static gf_single_t *const eqstat __attribute__ ((section(".text"))) = (void *) 0x101000;
74 /* Next available address: (void *) 0x112000. */
75 #else
76
77 static gf_single_t gf_powx[255 * 2];
78 static gf_single_t gf_powx_inv[256];
79 static int chosenstat[256];
80 static gf_single_t sigma[256];
81 static gf_single_t errpot[256];
82 static int errpos[256];
83 static gf_single_t sy[256];
84 static gf_single_t mstat[256];
85 static gf_single_t errvals[256];
86 static gf_single_t eqstat[65536 + 256];
87 #endif
88
89 static gf_single_t
90 gf_mul (gf_single_t a, gf_single_t b)
91 {
92 if (a == 0 || b == 0)
93 return 0;
94 return gf_powx[(int) gf_powx_inv[a] + (int) gf_powx_inv[b]];
95 }
96
97 static inline gf_single_t
98 gf_invert (gf_single_t a)
99 {
100 return gf_powx[255 - (int) gf_powx_inv[a]];
101 }
102
103 static void
104 init_powx (void)
105 {
106 int i;
107 grub_uint8_t cur = 1;
108
109 gf_powx_inv[0] = 0;
110 for (i = 0; i < 255; i++)
111 {
112 gf_powx[i] = cur;
113 gf_powx[i + 255] = cur;
114 gf_powx_inv[cur] = i;
115 if (cur & (1ULL << (GF_SIZE - 1)))
116 cur = (cur << 1) ^ GF_POLYNOMIAL;
117 else
118 cur <<= 1;
119 }
120 }
121
122 static gf_single_t
123 pol_evaluate (gf_single_t *pol, grub_size_t degree, int log_x)
124 {
125 int i;
126 gf_single_t s = 0;
127 int log_xn = 0;
128 for (i = degree; i >= 0; i--)
129 {
130 if (pol[i])
131 s ^= gf_powx[(int) gf_powx_inv[pol[i]] + log_xn];
132 log_xn += log_x;
133 if (log_xn >= ((1 << GF_SIZE) - 1))
134 log_xn -= ((1 << GF_SIZE) - 1);
135 }
136 return s;
137 }
138
139 #if !defined (STANDALONE)
140 static void
141 rs_encode (gf_single_t *data, grub_size_t s, grub_size_t rs)
142 {
143 gf_single_t *rs_polynomial;
144 int i, j;
145 gf_single_t *m;
146 m = xmalloc ((s + rs) * sizeof (gf_single_t));
147 grub_memcpy (m, data, s * sizeof (gf_single_t));
148 grub_memset (m + s, 0, rs * sizeof (gf_single_t));
149 rs_polynomial = xmalloc ((rs + 1) * sizeof (gf_single_t));
150 grub_memset (rs_polynomial, 0, (rs + 1) * sizeof (gf_single_t));
151 rs_polynomial[rs] = 1;
152 /* Multiply with X - a^r */
153 for (j = 0; j < rs; j++)
154 {
155 for (i = 0; i < rs; i++)
156 if (rs_polynomial[i])
157 rs_polynomial[i] = (rs_polynomial[i + 1]
158 ^ gf_powx[j + (int) gf_powx_inv[rs_polynomial[i]]]);
159 else
160 rs_polynomial[i] = rs_polynomial[i + 1];
161 if (rs_polynomial[rs])
162 rs_polynomial[rs] = gf_powx[j + (int) gf_powx_inv[rs_polynomial[rs]]];
163 }
164 for (j = 0; j < s; j++)
165 if (m[j])
166 {
167 gf_single_t f = m[j];
168 for (i = 0; i <= rs; i++)
169 m[i+j] ^= gf_mul (rs_polynomial[i], f);
170 }
171 free (rs_polynomial);
172 grub_memcpy (data + s, m + s, rs * sizeof (gf_single_t));
173 free (m);
174 }
175 #endif
176
177 static void
178 gauss_eliminate (gf_single_t *eq, int n, int m, int *chosen)
179 {
180 int i, j;
181
182 for (i = 0 ; i < n; i++)
183 {
184 int nzidx;
185 int k;
186 gf_single_t r;
187 for (nzidx = 0; nzidx < m && (eq[i * (m + 1) + nzidx] == 0);
188 nzidx++);
189 if (nzidx == m)
190 continue;
191 chosen[i] = nzidx;
192 r = gf_invert (eq[i * (m + 1) + nzidx]);
193 for (j = 0; j < m + 1; j++)
194 eq[i * (m + 1) + j] = gf_mul (eq[i * (m + 1) + j], r);
195 for (j = i + 1; j < n; j++)
196 {
197 gf_single_t rr = eq[j * (m + 1) + nzidx];
198 for (k = 0; k < m + 1; k++)
199 eq[j * (m + 1) + k] ^= gf_mul (eq[i * (m + 1) + k], rr);
200 }
201 }
202 }
203
204 static void
205 gauss_solve (gf_single_t *eq, int n, int m, gf_single_t *sol)
206 {
207 int i, j;
208
209 for (i = 0; i < n; i++)
210 chosenstat[i] = -1;
211 for (i = 0; i < m; i++)
212 sol[i] = 0;
213 gauss_eliminate (eq, n, m, chosenstat);
214 for (i = n - 1; i >= 0; i--)
215 {
216 gf_single_t s = 0;
217 if (chosenstat[i] == -1)
218 continue;
219 for (j = 0; j < m; j++)
220 s ^= gf_mul (eq[i * (m + 1) + j], sol[j]);
221 s ^= eq[i * (m + 1) + m];
222 sol[chosenstat[i]] = s;
223 }
224 }
225
226 static void
227 rs_recover (gf_single_t *mm, grub_size_t s, grub_size_t rs)
228 {
229 grub_size_t rs2 = rs / 2;
230 int errnum = 0;
231 int i, j;
232
233 for (i = 0; i < (int) rs; i++)
234 sy[i] = pol_evaluate (mm, s + rs - 1, i);
235
236 for (i = 0; i < (int) rs; i++)
237 if (sy[i] != 0)
238 break;
239
240 /* No error detected. */
241 if (i == (int) rs)
242 return;
243
244 {
245
246 for (i = 0; i < (int) rs2; i++)
247 for (j = 0; j < (int) rs2 + 1; j++)
248 eqstat[i * (rs2 + 1) + j] = sy[i+j];
249
250 for (i = 0; i < (int) rs2; i++)
251 sigma[i] = 0;
252
253 gauss_solve (eqstat, rs2, rs2, sigma);
254 }
255
256 for (i = 0; i < (int) (rs + s); i++)
257 if (pol_evaluate (sigma, rs2 - 1, 255 - i) == gf_powx[i])
258 {
259 errpot[errnum] = gf_powx[i];
260 errpos[errnum++] = s + rs - i - 1;
261 }
262 {
263 for (j = 0; j < errnum; j++)
264 eqstat[j] = 1;
265 eqstat[errnum] = sy[0];
266 for (i = 1; i < (int) rs; i++)
267 {
268 for (j = 0; j < (int) errnum; j++)
269 eqstat[(errnum + 1) * i + j] = gf_mul (errpot[j],
270 eqstat[(errnum + 1) * (i - 1)
271 + j]);
272 eqstat[(errnum + 1) * i + errnum] = sy[i];
273 }
274
275 gauss_solve (eqstat, rs, errnum, errvals);
276
277 for (i = 0; i < (int) errnum; i++)
278 mm[errpos[i]] ^= errvals[i];
279 }
280 }
281
282 static void
283 decode_block (gf_single_t *ptr, grub_size_t s,
284 gf_single_t *rptr, grub_size_t rs)
285 {
286 int i, j;
287 for (i = 0; i < SECTOR_SIZE; i++)
288 {
289 grub_size_t ds = (s + SECTOR_SIZE - 1 - i) / SECTOR_SIZE;
290 grub_size_t rr = (rs + SECTOR_SIZE - 1 - i) / SECTOR_SIZE;
291
292 /* Nothing to do. */
293 if (!ds || !rr)
294 continue;
295
296 for (j = 0; j < (int) ds; j++)
297 mstat[j] = ptr[SECTOR_SIZE * j + i];
298 for (j = 0; j < (int) rr; j++)
299 mstat[j + ds] = rptr[SECTOR_SIZE * j + i];
300
301 rs_recover (mstat, ds, rr);
302
303 for (j = 0; j < (int) ds; j++)
304 ptr[SECTOR_SIZE * j + i] = mstat[j];
305 }
306 }
307
308 #if !defined (STANDALONE)
309 static void
310 encode_block (gf_single_t *ptr, grub_size_t s,
311 gf_single_t *rptr, grub_size_t rs)
312 {
313 int i, j;
314 for (i = 0; i < SECTOR_SIZE; i++)
315 {
316 grub_size_t ds = (s + SECTOR_SIZE - 1 - i) / SECTOR_SIZE;
317 grub_size_t rr = (rs + SECTOR_SIZE - 1 - i) / SECTOR_SIZE;
318 gf_single_t *m;
319
320 if (!ds || !rr)
321 continue;
322
323 m = xmalloc (ds + rr);
324 for (j = 0; j < ds; j++)
325 m[j] = ptr[SECTOR_SIZE * j + i];
326 rs_encode (m, ds, rr);
327 for (j = 0; j < rr; j++)
328 rptr[SECTOR_SIZE * j + i] = m[j + ds];
329 free (m);
330 }
331 }
332 #endif
333
334 #if !defined (STANDALONE)
335 void
336 grub_reed_solomon_add_redundancy (void *buffer, grub_size_t data_size,
337 grub_size_t redundancy)
338 {
339 grub_size_t s = data_size;
340 grub_size_t rs = redundancy;
341 gf_single_t *ptr = buffer;
342 gf_single_t *rptr = ptr + s;
343 void *tmp;
344
345 tmp = xmalloc (data_size);
346 grub_memcpy (tmp, buffer, data_size);
347
348 /* Nothing to do. */
349 if (!rs)
350 return;
351
352 init_powx ();
353
354 while (s > 0)
355 {
356 grub_size_t tt;
357 grub_size_t cs, crs;
358 cs = s;
359 crs = rs;
360 tt = cs + crs;
361 if (tt > MAX_BLOCK_SIZE)
362 {
363 cs = ((cs * (MAX_BLOCK_SIZE / 512)) / tt) * 512;
364 crs = ((crs * (MAX_BLOCK_SIZE / 512)) / tt) * 512;
365 }
366 encode_block (ptr, cs, rptr, crs);
367 ptr += cs;
368 rptr += crs;
369 s -= cs;
370 rs -= crs;
371 }
372
373 #ifndef TEST
374 assert (grub_memcmp (tmp, buffer, data_size) == 0);
375 #endif
376 free (tmp);
377 }
378 #endif
379
380 void
381 grub_reed_solomon_recover (void *ptr_, grub_size_t s, grub_size_t rs)
382 {
383 gf_single_t *ptr = ptr_;
384 gf_single_t *rptr = ptr + s;
385
386 /* Nothing to do. */
387 if (!rs)
388 return;
389
390 init_powx ();
391
392 while (s > 0)
393 {
394 grub_size_t tt;
395 grub_size_t cs, crs;
396 cs = s;
397 crs = rs;
398 tt = cs + crs;
399 if (tt > MAX_BLOCK_SIZE)
400 {
401 cs = ((cs * (MAX_BLOCK_SIZE / 512)) / tt) * 512;
402 crs = ((crs * (MAX_BLOCK_SIZE / 512)) / tt) * 512;
403 }
404 decode_block (ptr, cs, rptr, crs);
405 ptr += cs;
406 rptr += crs;
407 s -= cs;
408 rs -= crs;
409 }
410 }
411
412 #ifdef TEST
413 int
414 main (int argc, char **argv)
415 {
416 FILE *in, *out;
417 grub_size_t s, rs;
418 char *buf;
419
420 grub_memset (gf_powx, 0xee, sizeof (gf_powx));
421 grub_memset (gf_powx_inv, 0xdd, sizeof (gf_powx_inv));
422
423 #ifndef STANDALONE
424 init_powx ();
425 #endif
426
427 #ifndef STANDALONE
428 in = fopen ("tst.bin", "rb");
429 if (!in)
430 return 1;
431 fseek (in, 0, SEEK_END);
432 s = ftell (in);
433 fseek (in, 0, SEEK_SET);
434 rs = 0x7007;
435 buf = xmalloc (s + rs + SECTOR_SIZE);
436 fread (buf, 1, s, in);
437 fclose (in);
438
439 grub_reed_solomon_add_redundancy (buf, s, rs);
440
441 out = fopen ("tst_rs.bin", "wb");
442 fwrite (buf, 1, s + rs, out);
443 fclose (out);
444 #else
445 out = fopen ("tst_rs.bin", "rb");
446 fseek (out, 0, SEEK_END);
447 s = ftell (out);
448 fseek (out, 0, SEEK_SET);
449 rs = 0x7007;
450 s -= rs;
451
452 buf = xmalloc (s + rs + SECTOR_SIZE);
453 fread (buf, 1, s + rs, out);
454 fclose (out);
455 #endif
456 #if 1
457 grub_memset (buf + 512 * 15, 0, 512);
458 #endif
459
460 out = fopen ("tst_dam.bin", "wb");
461 fwrite (buf, 1, s + rs, out);
462 fclose (out);
463 grub_reed_solomon_recover (buf, s, rs);
464
465 out = fopen ("tst_rec.bin", "wb");
466 fwrite (buf, 1, s, out);
467 fclose (out);
468
469 return 0;
470 }
471 #endif
Mirror of AROS' svn.