1 /* dvdisaster: Additional error correction for optical media.
2 * Copyright (C) 2004-2015 Carsten Gnoerlich.
3 *
4 * Email: carsten@dvdisaster.org -or- cgnoerlich@fsfe.org
5 * Project homepage: http://www.dvdisaster.org
6 *
7 * This file is part of dvdisaster.
8 *
9 * dvdisaster is free software: you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation, either version 3 of the License, or
12 * (at your option) any later version.
13 *
14 * dvdisaster is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with dvdisaster. If not, see <http://www.gnu.org/licenses/>.
21 */
22
23 #include "dvdisaster.h"
24
25 #include "rs03-includes.h"
26 #include "galois-inlines.h"
27
28 /***
29 *** Internal housekeeping
30 ***/
31
32 typedef struct
33 { RS03Widgets *wl;
34 RS03Layout *lay;
35 GaloisTables *gt;
36 ReedSolomonTables *rt;
37 Image *image;
38 int earlyTermination;
39 char *msg;
40 unsigned char *imgBlock[255];
41 } fix_closure;
42
fix_cleanup(gpointer data)43 static void fix_cleanup(gpointer data)
44 { fix_closure *fc = (fix_closure*)data;
45 int i;
46
47 UnregisterCleanup();
48
49 if(Closure->guiMode)
50 { if(fc->earlyTermination)
51 SwitchAndSetFootline(fc->wl->fixNotebook, 1,
52 fc->wl->fixFootline,
53 _("<span %s>Aborted by unrecoverable error.</span>"),
54 Closure->redMarkup);
55 AllowActions(TRUE);
56 }
57
58 /** Clean up */
59
60 if(fc->msg) g_free(fc->msg);
61 if(fc->image) CloseImage(fc->image);
62
63 for(i=0; i<255; i++)
64 { if(fc->imgBlock[i])
65 g_free(fc->imgBlock[i]);
66 }
67
68 if(fc->lay) g_free(fc->lay);
69 if(fc->gt) FreeGaloisTables(fc->gt);
70 if(fc->rt) FreeReedSolomonTables(fc->rt);
71
72 g_free(fc);
73
74 if(Closure->guiMode)
75 g_thread_exit(0);
76 }
77
78 /*
79 * Expand a truncated image
80 */
81
expand_image(Image * image,EccHeader * eh,gint64 new_size)82 static void expand_image(Image *image, EccHeader *eh, gint64 new_size)
83 { int last_percent, percent;
84 gint64 sectors, new_sectors;
85
86 if(!LargeSeek(image->file, image->file->size))
87 Stop(_("Failed seeking to end of image: %s\n"), strerror(errno));
88
89 last_percent = 0;
90 new_sectors = new_size - image->sectorSize;
91
92 for(sectors = 0; sectors < new_sectors; sectors++)
93 { unsigned char buf[2048];
94 int length,n;
95
96 CreateMissingSector(buf, image->sectorSize+sectors,
97 image->imageFP, FINGERPRINT_SECTOR,
98 "RS03 fix placeholder");
99
100 if(sectors != new_sectors-1) length = 2048;
101 else length = eh->inLast; /* non-image file may be clipped */
102
103 n = LargeWrite(image->file, buf, length);
104 if(n != length)
105 Stop(_("Failed expanding the image: %s\n"), strerror(errno));
106
107 percent = (100*sectors) / new_sectors;
108 if(last_percent != percent)
109 { if(Closure->guiMode)
110 ;
111 else PrintProgress(_("Expanding image: %3d%%"), percent);
112 last_percent = percent;
113 }
114 }
115
116 if(Closure->guiMode)
117 ;
118 else
119 { PrintProgress(_("Expanding image: %3d%%"), 100);
120 PrintProgress("\n");
121 }
122 }
123
124 /***
125 *** Test and fix the current image.
126 ***/
127
RS03Fix(Image * image)128 void RS03Fix(Image *image)
129 { Method *self = FindMethod("RS03");
130 RS03Widgets *wl = (RS03Widgets*)self->widgetList;
131 RS03Layout *lay;
132 fix_closure *fc = g_malloc0(sizeof(fix_closure));
133 EccHeader *eh;
134 gint32 *gf_index_of;
135 gint32 *gf_alpha_to;
136 gint64 block_idx[255];
137 gint64 s;
138 guint32 *crc_buf, last_crc_sector1[512], last_crc_sector2[512];
139 int nroots,ndata;
140 int crc_idx;
141 int crc_valid = TRUE;
142 int cache_size, cache_sector, cache_offset;
143 int erasure_count,erasure_list[255],erasure_map[255];
144 int error_count;
145 int percent, last_percent;
146 int worst_ecc = 0, local_plot_max = 0;
147 int i,j;
148 gint64 crc_errors=0;
149 gint64 data_count=0;
150 gint64 ecc_count=0;
151 gint64 crc_count=0;
152 gint64 data_corr=0;
153 gint64 ecc_corr=0;
154 gint64 corrected=0;
155 gint64 uncorrected=0;
156 gint64 damaged_sectors=0;
157 gint64 damaged_eccblocks=0;
158 gint64 damaged_eccsecs=0;
159 gint64 expected_sectors;
160 char *t=NULL,*msg;
161
162 /*** Register the cleanup procedure for GUI mode */
163
164 fc->image = image;
165 fc->wl = wl;
166 fc->earlyTermination = TRUE;
167 RegisterCleanup(_("Repairing of image aborted"), fix_cleanup, fc);
168
169 if(image->eccFileHeader)
170 eh = image->eccFileHeader;
171 else eh = image->eccHeader;
172
173 /*** Open the image file */
174
175 if(Closure->guiMode)
176 SetLabelText(GTK_LABEL(wl->fixHeadline),
177 _("<big>Repairing the image.</big>\n<i>%s</i>"),
178 _("Opening files..."));
179
180 /* Calculate the layout and optinally open thee ecc file */
181
182 if(eh->methodFlags[0] & MFLAG_ECC_FILE)
183 { lay = fc->lay = CalcRS03Layout(image, ECC_FILE);
184 }
185 else
186 { lay = fc->lay = CalcRS03Layout(image, ECC_IMAGE);
187 }
188
189 ndata = lay->ndata;
190 nroots = lay->nroots;
191
192 /*** Set up the Galois field arithmetic */
193
194 fc->gt = CreateGaloisTables(RS_GENERATOR_POLY);
195 fc->rt = CreateReedSolomonTables(fc->gt, RS_FIRST_ROOT, RS_PRIM_ELEM, nroots);
196 gf_index_of = fc->gt->indexOf;
197 gf_alpha_to = fc->gt->alphaTo;
198
199 /*** Expand a truncated image with "dead sector" markers.
200 If the images have the same number of sectors but a
201 different number of bytes in the last sector,
202 expand_image() is not called here as the missing bytes
203 are honoured in the RS03ReadSectors() functions and
204 the error correction will expand the image by writing
205 out the correct number of bytes. */
206
207 if(eh->methodFlags[0] & MFLAG_ECC_FILE)
208 expected_sectors = lay->dataSectors;
209 else expected_sectors = lay->totalSectors;
210
211 if(image->sectorSize < expected_sectors)
212 expand_image(image, eh, expected_sectors);
213
214 /*** Announce what we are going to do */
215
216 if(Closure->guiMode)
217 { if(eh->methodFlags[0] & MFLAG_ECC_FILE)
218 msg = g_strdup_printf(_("Error correction file using Method RS03, %d roots, %4.1f%% redundancy."),
219 eh->eccBytes,
220 ((double)eh->eccBytes*100.0)/(double)eh->dataBytes);
221 else
222 msg = g_strdup_printf(_("Image contains error correction data: Method RS03, %d roots, %4.1f%% redundancy."),
223 eh->eccBytes,
224 ((double)eh->eccBytes*100.0)/(double)eh->dataBytes);
225
226 SetLabelText(GTK_LABEL(wl->fixHeadline),
227 _("<big>Repairing the image.</big>\n<i>%s</i>"), msg);
228 RS03SetFixMaxValues(wl, eh->dataBytes, eh->eccBytes, expected_sectors);
229 g_free(msg);
230 }
231
232 PrintLog(_("\nFix mode(%s): Repairable sectors will be fixed in the image.\n"),
233 eh->methodFlags[0] & MFLAG_ECC_FILE ? "RS03f" : "RS03i");
234
235 /*** Image is a few bytes too long */
236
237 if(image->sectorSize == expected_sectors && image->inLast > eh->inLast)
238 { int difference = image->inLast - eh->inLast;
239 guint64 expected_image_size = 2048*(expected_sectors-1)+eh->inLast;
240
241 if(Closure->guiMode)
242 { int answer = ModalDialog(GTK_MESSAGE_QUESTION, GTK_BUTTONS_OK_CANCEL, NULL,
243 _("The image file is %d bytes longer than noted\n"
244 "in the ecc file. Shall the superfluous bytes\n"
245 "be removed from the image file?\n"),
246 difference);
247
248 if(!answer)
249 { SwitchAndSetFootline(fc->wl->fixNotebook, 1,
250 fc->wl->fixFootline,
251 _("<span %s>Aborted by user request!</span>"),
252 Closure->redMarkup);
253 fc->earlyTermination = FALSE; /* suppress respective error message */
254 goto terminate;
255 }
256 }
257
258 if(!Closure->guiMode && !Closure->truncate)
259 Stop(_("The image file is %d bytes longer than noted\n"
260 "in the ecc file.\n"
261 "Add the --truncate option to the program call\n"
262 "to have the superfluous sectors removed."),
263 difference);
264
265 if(!LargeTruncate(image->file, expected_image_size))
266 Stop(_("Could not truncate %s: %s\n"),Closure->imageName,strerror(errno));
267
268 PrintLog(_("Image has been truncated by %d bytes.\n"), difference);
269 image->inLast = eh->inLast;
270 }
271
272 /*** Truncate an image with trailing garbage (more than one sector) */
273
274 if(image->sectorSize > expected_sectors)
275 { gint64 diff = image->sectorSize - expected_sectors;
276 guint64 expected_image_size = 2048*(expected_sectors-1)+eh->inLast;
277 char *trans = _("The image file is %lld sectors longer as noted in the\n"
278 "ecc data. This might simply be zero padding, but could\n"
279 "also mean that the image was manipulated after appending\n"
280 "the error correction information.\n\n%s");
281
282 if(diff>0 && diff<=2)
283 { int answer = ModalWarning(GTK_MESSAGE_QUESTION, GTK_BUTTONS_OK_CANCEL, NULL,
284 _("Image file is %lld sectors longer than expected.\n"
285 "Assuming this is a TAO mode medium.\n"
286 "%lld sectors will be removed from the image end.\n"),
287 diff, diff);
288
289 if(!answer)
290 { SwitchAndSetFootline(fc->wl->fixNotebook, 1,
291 fc->wl->fixFootline,
292 _("<span %s>Aborted by user request!</span>"),
293 Closure->redMarkup);
294 fc->earlyTermination = FALSE; /* suppress respective error message */
295 goto terminate;
296 }
297
298 image->sectorSize -= diff;
299
300 if(!LargeTruncate(image->file, (gint64)expected_image_size))
301 Stop(_("Could not truncate %s: %s\n"),Closure->imageName,strerror(errno));
302 }
303
304 if(diff>2 && Closure->guiMode)
305 { int answer = ModalDialog(GTK_MESSAGE_QUESTION, GTK_BUTTONS_OK_CANCEL, NULL,
306 trans,
307 diff,
308 _("Is it okay to remove the superfluous sectors?"));
309
310 if(!answer)
311 { SwitchAndSetFootline(fc->wl->fixNotebook, 1,
312 fc->wl->fixFootline,
313 _("<span %s>Aborted by user request!</span>"),
314 Closure->redMarkup);
315 fc->earlyTermination = FALSE; /* suppress respective error message */
316 goto terminate;
317 }
318
319 image->sectorSize -= diff;
320
321 if(!LargeTruncate(image->file, (gint64)expected_image_size))
322 Stop(_("Could not truncate %s: %s\n"),Closure->imageName,strerror(errno));
323
324 PrintLog(_("Image has been truncated by %lld sectors.\n"), diff);
325 }
326
327 if(diff>2 && !Closure->guiMode)
328 { if(!Closure->truncate)
329 Stop(trans,
330 diff,
331 _("Add the --truncate option to the program call\n"
332 "to have the superfluous sectors removed."));
333
334 image->sectorSize -= diff;
335
336 if(!LargeTruncate(image->file, (gint64)expected_image_size))
337 Stop(_("Could not truncate %s: %s\n"),Closure->imageName,strerror(errno));
338
339 PrintLog(_("Image has been truncated by %lld sectors.\n"), diff);
340 }
341 }
342
343 /*** Prepare buffers for ecc code processing.
344 The first lay->dataSectors+lay->crcSectors are protected by ecc information.
345 The medium is logically divided into ndata layers and nroots slices.
346 Taking one sector from each layer and slice produces on ecc block
347 on which the error correction is carried out.
348 There is a total of lay->sectorsPerLayer ecc blocks.
349 A portion of cache_size sectors is read ahead from each layer,
350 giving a total cache size of 255*cache_size. */
351
352 cache_size = 2*Closure->cacheMiB; /* ndata+nroots=255 medium sectors are approx. 0.5MiB */
353
354 for(i=0; i<255; i++)
355 fc->imgBlock[i] = g_malloc(cache_size*2048);
356
357 /*** Setup the block counters for mapping medium sectors to ecc blocks.
358 We begin at the first ecc block (0) */
359
360 for(s=0, i=0; i<lay->ndata; s+=lay->sectorsPerLayer, i++)
361 block_idx[i] = s;
362
363 cache_sector = cache_size; /* forces instant reload of imgBlock cache */
364 cache_offset = 2048*cache_sector;
365
366 /*** CRC sums for the first ecc block are stored in the last CRC sector.
367 Error handling is done later when this sector is actually used. */
368
369 RS03ReadSectors(image, lay,
370 (unsigned char*)last_crc_sector2,
371 lay->ndata-1, lay->sectorsPerLayer-1, 1, RS03_READ_CRC);
372
373 /*** Test ecc blocks and attempt error correction */
374
375 last_percent = -1;
376
377 for(s=0; s<lay->sectorsPerLayer; s++)
378 { int bi;
379
380 /* See if user hit the Stop button */
381
382 if(Closure->stopActions)
383 { if(Closure->stopActions == STOP_CURRENT_ACTION) /* suppress memleak warning when closing window */
384 SwitchAndSetFootline(fc->wl->fixNotebook, 1,
385 fc->wl->fixFootline,
386 _("<span %s>Aborted by user request!</span>"),
387 Closure->redMarkup);
388 fc->earlyTermination = FALSE; /* suppress respective error message */
389 goto terminate;
390 }
391
392 /* Fill cache with the next batch of cache_size ecc blocks. */
393
394 if(cache_sector >= cache_size)
395 {
396 if(lay->sectorsPerLayer-s < cache_size)
397 cache_size = lay->sectorsPerLayer-s;
398
399 /* Read the data portion */
400
401 for(i=0; i<ndata-1; i++)
402 {
403 RS03ReadSectors(image, lay, fc->imgBlock[i], i, s,
404 cache_size, RS03_READ_DATA);
405 }
406
407 /* Read from the CRC layer */
408
409 RS03ReadSectors(image, lay, fc->imgBlock[ndata-1], ndata-1, s,
410 cache_size, RS03_READ_CRC);
411
412 /* Keep a copy of the last CRC sector for the next pass */
413 memcpy(last_crc_sector1, last_crc_sector2, 2048);
414 memcpy(last_crc_sector2, fc->imgBlock[ndata-1]+2048*(cache_size-1), 2048);
415
416 /* and finally the ecc portion */
417
418 for(i=0; i<nroots; i++)
419 {
420 RS03ReadSectors(image, lay, fc->imgBlock[i+ndata], i+ndata, s,
421 cache_size, RS03_READ_ECC);
422 }
423
424 cache_sector = cache_offset = 0;
425 }
426
427 /* Set crc ptr to beginning of CRC sector. The first ECC block has no
428 CRC sector; the checksums are taken from the Ecc header instead. */
429
430 if(cache_sector==0)
431 { int err;
432
433 crc_buf = last_crc_sector1;
434 err = CheckForMissingSector((unsigned char*)crc_buf,
435 lay->firstCrcPos,
436 eh->mediumFP, eh->fpSector);
437 crc_valid = (err == SECTOR_PRESENT);
438 }
439 else
440 { int err;
441
442 crc_buf = (guint32*)(fc->imgBlock[ndata-1]+cache_offset-2048);
443
444 err = CheckForMissingSector((unsigned char*)crc_buf,
445 block_idx[ndata-1],
446 eh->mediumFP, eh->fpSector);
447 crc_valid = (err == SECTOR_PRESENT);
448 }
449 crc_idx = 0;
450
451 /*** Look for erasures based on the "dead sector" marker and CRC sums */
452
453 erasure_count = error_count = 0;
454
455 /* Check the data sectors */
456
457 for(i=0; i<lay->ndata; i++)
458 { int err = CheckForMissingSector(fc->imgBlock[i]+cache_offset, block_idx[i],
459 eh->mediumFP, eh->fpSector);
460 /* FIXME: sector number is wrong for CRC layer in ecc files */
461 /* FIXME: Auto-replace the padding sectors */
462
463 if(err == SECTOR_PRESENT)
464 { erasure_map[i] = 0;
465 }
466 else
467 { erasure_map[i] = 1;
468 erasure_list[erasure_count++] = i;
469 damaged_sectors++;
470 }
471
472 if(i < ndata-1) /* only data sectors have CRCs */
473 { guint32 crc = Crc32(fc->imgBlock[i]+cache_offset, 2048);
474
475 if(crc_valid && !erasure_map[i] && crc != crc_buf[crc_idx])
476 { erasure_map[i] = 3;
477 erasure_list[erasure_count++] = i;
478 PrintCLI(_("CRC error in sector %lld\n"),block_idx[i]);
479 damaged_sectors++;
480 crc_errors++;
481 }
482
483 data_count++;
484 crc_idx++;
485 }
486 else crc_count++;
487 }
488
489 /* Check the ecc sectors */
490
491 for(i=lay->ndata; i<GF_FIELDMAX; i++)
492 { int err = CheckForMissingSector(fc->imgBlock[i]+cache_offset,
493 RS03SectorIndex(lay, i, s),
494 eh->mediumFP, eh->fpSector);
495
496 if(err)
497 { erasure_map[i] = 1;
498 erasure_list[erasure_count++] = i;
499 damaged_sectors++;
500 }
501 else erasure_map[i] = 0;
502
503 ecc_count++;
504 }
505
506 /* Trivially reject uncorrectable ecc block */
507
508 if(erasure_count>lay->nroots) /* uncorrectable */
509 { if(!Closure->guiMode)
510 { int sep_printed = 0;
511
512 PrintCLI(_("* Ecc block %lld: %3d unrepairable sectors: "), s, erasure_count);
513
514 for(i=0; i<erasure_count; i++)
515 { /* sector counting wraps to 0 for ecc files after the data layer */
516 if(eh->methodFlags[0] & MFLAG_ECC_FILE && erasure_list[i] >= ndata-1 && ! sep_printed)
517 { PrintCLI("; ecc file: ");
518 sep_printed = 1;
519 }
520 PrintCLI("%lld ", RS03SectorIndex(lay, erasure_list[i], s));
521 }
522 PrintCLI("\n");
523 }
524
525 uncorrected += erasure_count;
526 goto skip;
527 }
528
529 /* Build ecc block and attempt to correct it */
530
531 for(bi=0; bi<2048; bi++) /* Run through each ecc block byte */
532 { int offset = cache_offset+bi;
533 int r, deg_lambda, el, deg_omega;
534 int u,q,tmp,num1,num2,den,discr_r;
535 int lambda[nroots+1], syn[nroots]; /* Err+Eras Locator poly * and syndrome poly */
536 int b[nroots+1], t[nroots+1], omega[nroots+1];
537 int root[nroots], reg[nroots+1], loc[nroots];
538 int syn_error, count;
539 int k;
540
541 /* Form the syndromes; i.e., evaluate data(x) at roots of g(x) */
542
543 for(i=0; i<nroots; i++)
544 syn[i] = fc->imgBlock[0][offset];
545
546 for(j=1; j<GF_FIELDMAX; j++)
547 { int data = fc->imgBlock[j][offset];
548
549 for(i=0;i<nroots;i++)
550 { if(syn[i] == 0) syn[i] = data;
551 else syn[i] = data ^ gf_alpha_to[mod_fieldmax(gf_index_of[syn[i]] + (RS_FIRST_ROOT+i)*RS_PRIM_ELEM)];
552 }
553 }
554
555 /* Convert syndromes to index form, check for nonzero condition */
556
557 syn_error = 0;
558 for(i=0; i<nroots; i++)
559 { syn_error |= syn[i];
560 syn[i] = gf_index_of[syn[i]];
561 }
562
563 /* If it is already correct by coincidence, we have nothing to do any further */
564
565 if(syn_error) damaged_eccblocks++;
566 else continue;
567
568 //printf("Syndrome error for ecc block %lld, byte %d\n",s,bi);
569
570 /* If we have found any erasures,
571 initialize lambda to be the erasure locator polynomial */
572
573 memset(lambda+1, 0, nroots*sizeof(lambda[0]));
574 lambda[0] = 1;
575
576 if(erasure_count > 0)
577 { lambda[1] = gf_alpha_to[mod_fieldmax(RS_PRIM_ELEM*(GF_FIELDMAX-1-erasure_list[0]))];
578 for(i=1; i<erasure_count; i++)
579 { u = mod_fieldmax(RS_PRIM_ELEM*(GF_FIELDMAX-1-erasure_list[i]));
580 for(j=i+1; j>0; j--)
581 { tmp = gf_index_of[lambda[j-1]];
582 if(tmp != GF_ALPHA0)
583 lambda[j] ^= gf_alpha_to[mod_fieldmax(u + tmp)];
584 }
585 }
586 }
587
588 for(i=0; i<nroots+1; i++)
589 b[i] = gf_index_of[lambda[i]];
590
591 /* Begin Berlekamp-Massey algorithm to determine error+erasure locator polynomial */
592
593 r = erasure_count; /* r is the step number */
594 el = erasure_count;
595 while(++r <= nroots) /* Compute discrepancy at the r-th step in poly-form */
596 {
597 discr_r = 0;
598 for(i=0; i<r; i++)
599 if((lambda[i] != 0) && (syn[r-i-1] != GF_ALPHA0))
600 discr_r ^= gf_alpha_to[mod_fieldmax(gf_index_of[lambda[i]] + syn[r-i-1])];
601
602 discr_r = gf_index_of[discr_r]; /* Index form */
603
604 if(discr_r == GF_ALPHA0)
605 { /* B(x) = x*B(x) */
606 memmove(b+1, b, nroots*sizeof(b[0]));
607 b[0] = GF_ALPHA0;
608 }
609 else
610 { /* T(x) = lambda(x) - discr_r*x*b(x) */
611 t[0] = lambda[0];
612 for(i=0; i<nroots; i++)
613 { if(b[i] != GF_ALPHA0)
614 t[i+1] = lambda[i+1] ^ gf_alpha_to[mod_fieldmax(discr_r + b[i])];
615 else t[i+1] = lambda[i+1];
616 }
617
618 if(2*el <= r+erasure_count-1)
619 { el = r + erasure_count - el;
620
621 /* B(x) <-- inv(discr_r) * lambda(x) */
622 for(i=0; i<=nroots; i++)
623 b[i] = (lambda[i] == 0) ? GF_ALPHA0 : mod_fieldmax(gf_index_of[lambda[i]] - discr_r + GF_FIELDMAX);
624 }
625 else
626 { /* 2 lines below: B(x) <-- x*B(x) */
627 memmove(b+1, b, nroots*sizeof(b[0]));
628 b[0] = GF_ALPHA0;
629 }
630
631 memcpy(lambda,t,(nroots+1)*sizeof(t[0]));
632 }
633 }
634
635 /* Convert lambda to index form and compute deg(lambda(x)) */
636 deg_lambda = 0;
637 for(i=0; i<nroots+1; i++)
638 { lambda[i] = gf_index_of[lambda[i]];
639 if(lambda[i] != GF_ALPHA0)
640 deg_lambda = i;
641 }
642
643 /* Find roots of the error+erasure locator polynomial by Chien search */
644 memcpy(reg+1, lambda+1, nroots*sizeof(reg[0]));
645 count = 0; /* Number of roots of lambda(x) */
646
647 for(i=1, k=RS_PRIMTH_ROOT-1; i<=GF_FIELDMAX; i++, k=mod_fieldmax(k+RS_PRIMTH_ROOT))
648 { q=1; /* lambda[0] is always 0 */
649
650 for(j=deg_lambda; j>0; j--)
651 { if(reg[j] != GF_ALPHA0)
652 { reg[j] = mod_fieldmax(reg[j] + j);
653 q ^= gf_alpha_to[reg[j]];
654 }
655 }
656
657 if(q != 0) continue; /* Not a root */
658
659 /* store root (index-form) and error location number */
660
661 root[count] = i;
662 loc[count] = k;
663
664 /* If we've already found max possible roots, abort the search to save time */
665
666 if(++count == deg_lambda) break;
667 }
668
669 /* deg(lambda) unequal to number of roots => uncorrectable error detected */
670
671 if(deg_lambda != count)
672 { int sep_printed = 0;
673 PrintLog("Decoder problem (%d != %d) for %d sectors: ", deg_lambda, count, erasure_count);
674
675 for(i=0; i<erasure_count; i++)
676 { /* sector counting wraps to 0 for ecc files after the data layer */
677 if(eh->methodFlags[0] & MFLAG_ECC_FILE && erasure_list[i] >= ndata-1 && ! sep_printed)
678 { PrintCLI(_("; ecc file: "));
679 sep_printed = 1;
680 }
681 PrintCLI("%lld ", RS03SectorIndex(lay, erasure_list[i], s));
682 }
683 PrintCLI("\n");
684 uncorrected += erasure_count;
685 goto skip;
686 }
687
688 /* Compute err+eras evaluator poly omega(x) = syn(x)*lambda(x)
689 (modulo x**nroots). in index form. Also find deg(omega). */
690
691 deg_omega = deg_lambda-1;
692
693 for(i=0; i<=deg_omega; i++)
694 { tmp = 0;
695 for(j=i; j>=0; j--)
696 { if((syn[i - j] != GF_ALPHA0) && (lambda[j] != GF_ALPHA0))
697 tmp ^= gf_alpha_to[mod_fieldmax(syn[i - j] + lambda[j])];
698 }
699
700 omega[i] = gf_index_of[tmp];
701 }
702
703 /* Compute error values in poly-form.
704 num1 = omega(inv(X(l))),
705 num2 = inv(X(l))**(FIRST_ROOT-1) and
706 den = lambda_pr(inv(X(l))) all in poly-form. */
707
708 for(j=count-1; j>=0; j--)
709 { num1 = 0;
710
711 for(i=deg_omega; i>=0; i--)
712 { if(omega[i] != GF_ALPHA0)
713 num1 ^= gf_alpha_to[mod_fieldmax(omega[i] + i * root[j])];
714 }
715
716 num2 = gf_alpha_to[mod_fieldmax(root[j] * (RS_FIRST_ROOT - 1) + GF_FIELDMAX)];
717 den = 0;
718
719 /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
720
721 for(i=MIN(deg_lambda, nroots-1) & ~1; i>=0; i-=2)
722 { if(lambda[i+1] != GF_ALPHA0)
723 den ^= gf_alpha_to[mod_fieldmax(lambda[i+1] + i * root[j])];
724 }
725
726 /* Apply error to data */
727
728 if(num1 != 0)
729 { int location = loc[j];
730
731 if(erasure_map[location] != 1) /* erasure came from CRC error */
732 { int old = fc->imgBlock[location][offset];
733 int new = old ^ gf_alpha_to[mod_fieldmax(gf_index_of[num1] + gf_index_of[num2] + GF_FIELDMAX - gf_index_of[den])];
734 char *msg, *type;
735 gint64 sector;
736
737 if(erasure_map[location] == 3) /* erasure came from CRC error */
738 { msg = _("-> CRC-predicted error in sector %lld%s at byte %4d (value %02x '%c', expected %02x '%c')\n");
739 }
740 else
741 { msg = _("-> Non-predicted error in sector %lld%s at byte %4d (value %02x '%c', expected %02x '%c')\n");
742 if(erasure_map[location] == 0) /* remember error location */
743 { erasure_map[location] = 7;
744 error_count++;
745 }
746 }
747
748 sector = RS03SectorIndex(lay, location, s);
749 if(eh->methodFlags[0] & MFLAG_ECC_FILE && location >= ndata-1)
750 type="(ecc)";
751 else
752 type="";
753
754 PrintCLI(msg,
755 sector, type, bi,
756 old, isprint(old) ? old : '.',
757 new, isprint(new) ? new : '.');
758 }
759
760 fc->imgBlock[location][offset] ^= gf_alpha_to[mod_fieldmax(gf_index_of[num1] + gf_index_of[num2] + GF_FIELDMAX - gf_index_of[den])];
761 }
762 }
763 }
764
765 /* Write corrected sectors back to disc
766 and report them */
767
768 erasure_count += error_count; /* total errors encountered */
769
770 if(erasure_count)
771 { int sep_printed = 0;
772 PrintCLI(_(" %3d repaired sectors: "), erasure_count);
773
774 for(i=0; i<255; i++)
775 { gint64 sec;
776 char type='?';
777 int length,n;
778
779 if(!erasure_map[i]) continue;
780
781 switch(erasure_map[i])
782 { case 1: /* dead sector */
783 type = 'd';
784 break;
785
786 case 3: /* crc error */
787 type = 'c';
788 break;
789
790 case 7: /* other (new) error */
791 type = 'n';
792 damaged_sectors++;
793 break;
794 }
795
796 sec = RS03SectorIndex(lay, i, s);
797 if(i < ndata) { data_corr++; }
798 else { ecc_corr++; }
799 corrected++;
800
801 if(eh->methodFlags[0] & MFLAG_ECC_FILE && i >= ndata-1 && ! sep_printed)
802 { PrintCLI(_("; ecc file: "));
803 sep_printed = 1;
804 }
805 PrintCLI("%lld%c ", sec, type);
806
807 /* Write the recovered sector */
808
809 if(sec != lay->dataSectors-1) length = 2048;
810 else length = eh->inLast; /* non-image file may be clipped */
811
812 /* Write back into the image */
813
814 if( lay->target == ECC_IMAGE
815 || i < ndata-1)
816 {
817 if(!LargeSeek(image->file, (gint64)(2048*sec)))
818 Stop(_("Failed seeking to sector %lld in image [%s]: %s"),
819 sec, "FW", strerror(errno));
820
821 n = LargeWrite(image->file, cache_offset+fc->imgBlock[i], length);
822 if(n != length)
823 Stop(_("could not write medium sector %lld:\n%s"), sec, strerror(errno));
824 }
825
826 /* Write back into the error correction file
827 (for the CRC and ECC portion of the ecc block).
828 Note that "sec" contains the virtual adresses as
829 if we were processing an augmented image. */
830
831 if(lay->target == ECC_FILE && i >= ndata-1)
832 {
833 if(!LargeSeek(image->eccFile, (gint64)(2048*sec)))
834 Stop(_("Failed seeking to sector %lld in ecc file [%s]: %s"),
835 sec, "FW", strerror(errno));
836
837 n = LargeWrite(image->eccFile, cache_offset+fc->imgBlock[i], 2048);
838 if(n != 2048)
839 Stop(_("could not write ecc file sector %lld:\n%s"),
840 sec, strerror(errno));
841 }
842 }
843 PrintCLI("\n");
844 }
845
846 skip:
847 /* Collect some damage statistics */
848
849 if(erasure_count)
850 damaged_eccsecs++;
851
852 if(erasure_count>worst_ecc)
853 worst_ecc = erasure_count;
854
855 if(erasure_count>local_plot_max)
856 local_plot_max = erasure_count;
857
858 /* Advance the cache pointers */
859
860 cache_sector++;
861 cache_offset += 2048;
862
863 /* Report progress */
864
865 percent = (1000*s)/lay->sectorsPerLayer;
866
867 if(last_percent != percent)
868 { if(Closure->guiMode)
869 {
870 RS03AddFixValues(wl, percent, local_plot_max);
871 local_plot_max = 0;
872
873 //if(last_corrected != corrected || last_uncorrected != uncorrected)
874 RS03UpdateFixResults(wl, corrected, uncorrected);
875 }
876 else PrintProgress(_("Ecc progress: %3d.%1d%%"),percent/10,percent%10);
877 last_percent = percent;
878 }
879
880 /* Increment the block indices */
881
882 for(i=0; i<lay->ndata; i++)
883 block_idx[i]++;
884 }
885
886 /*** Print results */
887
888 PrintProgress(_("Ecc progress: 100.0%%\n"));
889
890 if(corrected > 0) PrintLog(_("Repaired sectors: %lld (%lld data, %lld ecc)\n"),
891 corrected, data_corr, ecc_corr);
892 if(uncorrected > 0)
893 { PrintLog(_("Unrepaired sectors: %lld\n"), uncorrected);
894 if(Closure->guiMode)
895 SwitchAndSetFootline(wl->fixNotebook, 1, wl->fixFootline,
896 _("Image sectors could not be fully restored "
897 "(%lld repaired; <span %s>%lld unrepaired</span>)"),
898 corrected, Closure->redMarkup, uncorrected);
899 exitCode = 2;
900 }
901 else
902 { if(!corrected)
903 { t=_("Good! All sectors are already present.");
904 PrintLog("%s\n", t);
905 exitCode = 0;
906 }
907 else
908 { t=_("Good! All sectors are repaired.");
909 PrintLog("%s\n", t);
910 exitCode = 1;
911 }
912 }
913 if(corrected > 0 || uncorrected > 0)
914 PrintLog(_("Erasure counts per ecc block: avg = %.1f; worst = %d.\n"),
915 (double)damaged_sectors/(double)damaged_eccsecs,worst_ecc);
916
917 if(Closure->guiMode && t)
918 SwitchAndSetFootline(wl->fixNotebook, 1, wl->fixFootline,
919 "%s %s", _("Repair results:"), t);
920
921 Verbose("\nSummary of processed sectors:\n");
922 Verbose("%lld damaged sectors\n", damaged_sectors);
923 Verbose("%lld CRC errors\n", crc_errors);
924 Verbose("%lld of %lld ecc blocks damaged (%lld / %lld sectors)\n",
925 damaged_eccblocks, 2048*lay->sectorsPerLayer,
926 damaged_eccsecs, lay->sectorsPerLayer);
927 if(data_count != (ndata-1)*lay->sectorsPerLayer)
928 g_printf("ONLY %lld of %lld data sectors processed\n",
929 (long long int)data_count, (long long int)(ndata-1)*lay->sectorsPerLayer);
930 else Verbose("all data sectors processed\n");
931
932 if(crc_count != lay->sectorsPerLayer)
933 g_printf("%lld of %lld crc sectors processed\n",
934 (long long int)crc_count, (long long int)lay->sectorsPerLayer);
935 else Verbose("all crc sectors processed\n");
936
937 if(ecc_count != nroots*lay->sectorsPerLayer)
938 g_printf("%lld of %lld ecc sectors processed\n",
939 (long long int)ecc_count, (long long int)nroots*lay->sectorsPerLayer);
940 else Verbose("all ecc sectors processed\n");
941
942 /*** Clean up */
943
944 fc->earlyTermination = FALSE;
945
946 terminate:
947 fix_cleanup((gpointer)fc);
948 }
949