1 /* dvdisaster: Additional error correction for optical media.
2 * Copyright (C) 2004-2015 Carsten Gnoerlich.
3 * Copyright (C) 2006 Andrei Grecu
4 *
5 * Email: carsten@dvdisaster.org -or- cgnoerlich@fsfe.org
6 * Project homepage: http://www.dvdisaster.org
7 *
8 * This file is part of dvdisaster.
9 *
10 * dvdisaster is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14 *
15 * dvdisaster is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with dvdisaster. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24 #include "dvdisaster.h"
25
26 /***
27 *** Auxiliary functions for collecting some stuff incrementally
28 ***/
29
30 /*
31 * Update count of different bytes read for each position
32 */
33
UpdateByteCounts(RawBuffer * rb)34 void UpdateByteCounts(RawBuffer *rb)
35 {
36 int i, j;
37
38 /* The first time there is not much to do */
39 if(rb->samplesRead == 1)
40 {
41 memset(rb->byteCount, 1, rb->sampleSize);
42 return;
43 }
44
45 /* Update byte counts */
46 for(i = 0; i < rb->sampleSize; i++)
47 {
48 char found = 0;
49 for(j = 0; j < rb->samplesRead - 1; j++)
50 {
51 if(rb->rawBuf[rb->samplesRead - 1][i] == rb->rawBuf[j][i])
52 {
53 found = 1;
54 break;
55 }
56 }
57
58 if(!found) rb->byteCount[i]++;
59 }
60 }
61
62 /*
63 * Determine work load of P/Q vectors in the given frame
64 */
65
CalculatePQLoad(RawBuffer * rb)66 void CalculatePQLoad(RawBuffer *rb)
67 { unsigned char p_vector[P_VECTOR_SIZE];
68 unsigned char q_vector[Q_VECTOR_SIZE];
69 int frame_idx = rb->samplesRead - 1;
70 unsigned char *new_frame = rb->rawBuf[frame_idx];
71 int ignore[2];
72 int q, p;
73 int err;
74
75 for(q = 0; q < N_Q_VECTORS; q++)
76 {
77 GetQVector(new_frame, q_vector, q);
78 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
79 if(err < 0) rb->qLoad[frame_idx] += 2;
80 if(err == 1) rb->qLoad[frame_idx]++; /* We assume without any erasures specified there can't be more than 1 errors corrected. */
81 }
82
83 for(p = 0; p < N_P_VECTORS; p++)
84 {
85 GetPVector(new_frame, p_vector, p);
86 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
87 if(err < 0) rb->pLoad[frame_idx] += 2;
88 if(err == 1) rb->pLoad[frame_idx]++; /* We assume without any erasures specified there can't be more than 1 errors corrected. */
89 }
90 }
91
92 /*
93 * Collect a list of all seen P/Q parity bytes.
94 */
95
UpdatePQParityList(RawBuffer * rb,unsigned char * new_frame)96 void UpdatePQParityList(RawBuffer *rb, unsigned char *new_frame)
97 { unsigned char p_vector[P_VECTOR_SIZE];
98 unsigned char q_vector[Q_VECTOR_SIZE];
99 int i,p,q;
100
101 /*** See if new frame has any Q parity bytes different from the existing ones. */
102
103 for(q=0; q<N_Q_VECTORS; q++)
104 { int qfound = FALSE;
105
106 GetQVector(new_frame, q_vector, q);
107
108 for(i=0; i<rb->qParityN[q][0]; i++)
109 if(rb->qParity1[q][i] == q_vector[43])
110 { qfound = TRUE;
111 break;
112 }
113
114 if(!qfound)
115 rb->qParity1[q][rb->qParityN[q][0]++] = q_vector[43];
116
117 qfound = FALSE;
118
119 for(i=0; i<rb->qParityN[q][1]; i++)
120 if(rb->qParity2[q][i] == q_vector[44])
121 { qfound = TRUE;
122 break;
123 }
124
125 if(!qfound)
126 rb->qParity2[q][rb->qParityN[q][1]++] = q_vector[44];
127 }
128
129 /*** See if new frame has any P parity bytes different from the existing ones. */
130
131 for(p=0; p<N_P_VECTORS; p++)
132 { int pfound = FALSE;
133
134 GetPVector(new_frame, p_vector, p);
135
136 for(i=0; i<rb->pParityN[p][0]; i++)
137 if(rb->pParity1[p][i] == p_vector[24])
138 { pfound = TRUE;
139 break;
140 }
141
142 if(!pfound)
143 rb->pParity1[p][rb->pParityN[p][0]++] = p_vector[24];
144
145 pfound = FALSE;
146
147 for(i=0; i<rb->pParityN[p][1]; i++)
148 if(rb->pParity2[p][i] == p_vector[25])
149 { pfound = TRUE;
150 break;
151 }
152
153 if(!pfound)
154 rb->pParity2[p][rb->pParityN[p][1]++] = p_vector[25];
155 }
156 }
157
158 /***
159 *** Heuristic L-EC attempt
160 *** Andrei Grecu, 2006
161 */
162
eval_q_candidate(RawBuffer * rb,unsigned char * q_vector,int q,int * p_failures_out,int * p_errors_out)163 static int eval_q_candidate(RawBuffer *rb, unsigned char *q_vector, int q,
164 int *p_failures_out, int *p_errors_out)
165 {
166 unsigned char p_vector[P_VECTOR_SIZE];
167 unsigned char old_q_vector[Q_VECTOR_SIZE];
168 int ignore[2];
169 int p, p_errors = 0;
170 int p_failures = 0;
171 int err;
172
173 GetQVector(rb->recovered, old_q_vector, q);
174 SetQVector(rb->recovered, q_vector, q);
175
176 /* Count P failures after setting our Q vector. */
177
178 for(p = 0; p < N_P_VECTORS; p++)
179 {
180 GetPVector(rb->recovered, p_vector, p);
181 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
182 if(err < 0) p_failures++;
183 else if(err == 1) p_errors++;
184 }
185
186 SetQVector(rb->recovered, old_q_vector, q);
187
188 *p_failures_out = p_failures;
189 *p_errors_out = p_errors;
190
191 return TRUE;
192 }
193
eval_p_candidate(RawBuffer * rb,unsigned char * p_vector,int p,int * q_failures_out,int * q_errors_out)194 static void eval_p_candidate(RawBuffer *rb, unsigned char *p_vector, int p,
195 int *q_failures_out, int *q_errors_out)
196 {
197 unsigned char q_vector[Q_VECTOR_SIZE];
198 unsigned char old_p_vector[P_VECTOR_SIZE];
199 int ignore[2];
200 int q, q_errors = 0;
201 int q_failures = 0;
202 int err;
203
204 GetPVector(rb->recovered, old_p_vector, p);
205 SetPVector(rb->recovered, p_vector, p);
206
207 /* Count Q failures after setting our P vector. */
208
209 for(q = 0; q < N_Q_VECTORS; q++)
210 {
211 GetQVector(rb->recovered, q_vector, q);
212 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
213 if(err < 0) q_failures++;
214 else if(err == 1) q_errors++;
215 }
216
217 SetPVector(rb->recovered, old_p_vector, p);
218
219 *q_failures_out = q_failures;
220 *q_errors_out = q_errors;
221 }
222
223
224 /*
225 * An enhanced L-EC loop
226 */
227
228 //#define DEBUG_HEURISTIC_LEC
229
HeuristicLEC(unsigned char * cd_frame,RawBuffer * rb,unsigned char * out)230 int HeuristicLEC(unsigned char *cd_frame, RawBuffer *rb, unsigned char *out)
231 {
232 unsigned char p_vector[P_VECTOR_SIZE];
233 unsigned char q_vector[Q_VECTOR_SIZE];
234 unsigned char p_state[P_VECTOR_SIZE];
235 unsigned char q_state[Q_VECTOR_SIZE];
236 int erasures[Q_VECTOR_SIZE], decimated_erasures[2], erasure_count;
237 int ignore[2];
238 int p_failures, q_failures;
239 int p_corrected, q_corrected;
240 int i,p,q;
241 int iteration=1;
242 int p_err, q_err;
243 int p_decimated, q_decimated;
244 int last_p_err = N_P_VECTORS;
245 int last_q_err = N_Q_VECTORS;
246 int last_p_failures = N_P_VECTORS;
247 int last_q_failures = N_Q_VECTORS;
248 int max_p_failures = 0;
249 int max_p_errors = 0;
250 int max_q_failures = 0;
251 int max_q_errors = 0;
252 int err;
253
254 memset(rb->byteState, FRAME_BYTE_UNKNOWN, rb->sampleSize);
255
256 /* Count initial P failures */
257
258 for(p = 0; p < N_P_VECTORS; p++)
259 {
260 GetPVector(rb->recovered, p_vector, p);
261 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
262 if(err < 0) max_p_failures++;
263 if(err == 1) max_p_errors++;
264 }
265
266 /* Count initial Q failures */
267
268 for(q = 0; q < N_Q_VECTORS; q++)
269 {
270 GetQVector(rb->recovered, q_vector, q);
271 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
272 if(err < 0) max_q_failures++;
273 if(err == 1) max_q_errors++;
274 }
275
276 #ifdef DEBUG_HEURISTIC_LEC
277 Verbose(" P-failures/corrected/errors + decimated: %2d/%2d/ 0 + 0\n", max_p_failures, max_p_errors);
278 Verbose(" Q-failures/corrected/errors + decimated: %2d/%2d/ 0 + 0\n", max_q_failures, max_q_errors);
279 #endif
280
281 for(; ;) /* iterate over P- and Q-Parity until failures converge */
282 {
283 p_failures = q_failures = 0;
284 p_corrected = q_corrected = 0;
285 p_err = q_err = 0;
286 p_decimated = q_decimated = 0;
287
288 /* Perform P-Parity error correction */
289
290 for(p=0; p<N_P_VECTORS; p++)
291 {
292 /* Determine number of erasures */
293
294 GetPVector(rb->byteState, p_state, p);
295 erasure_count = 0;
296
297 for(i=0; i<P_VECTOR_SIZE; i++)
298 if(p_state[i] == FRAME_BYTE_ERROR) erasures[erasure_count++] = i;
299
300 /* First try to see whether P is correctable without erasure markings. */
301
302 GetPVector(rb->recovered, p_vector, p);
303 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
304
305 if(err == 1) /* Store back corrected vector */
306 {
307 SetPVector(rb->recovered, p_vector, p);
308 FillPVector(rb->byteState, FRAME_BYTE_GOOD, p);
309 p_corrected++;
310 p_err += err;
311 }
312
313 /* Erasure markings are overly pessimistic as each failing vector will mark
314 a full row as an erasure. We assume that there are only 2 real erasures
315 and try all combinations.
316 The case for 2 erasure is also included here. */
317
318 if(err < 0 && erasure_count > 1)
319 { unsigned char best_p[P_VECTOR_SIZE];
320 int best_q_failures = N_Q_VECTORS;
321 int best_q_errors = N_Q_VECTORS;
322 int candidate = FALSE;
323 int a, b;
324
325 /* Try error correction with decimated erasures */
326
327 for(a = 0; a < erasure_count - 1; a++)
328 {
329 for(b = a + 1; b < erasure_count; b++)
330 {
331 decimated_erasures[0] = erasures[a];
332 decimated_erasures[1] = erasures[b];
333 GetPVector(rb->recovered, p_vector, p);
334 err = DecodePQ(rb->rt, p_vector, P_PADDING, decimated_erasures, 2);
335 if(err == 2)
336 { int q_err, q_fail;
337
338 candidate = TRUE;
339 eval_p_candidate(rb, p_vector, p, &q_fail, &q_err);
340
341 if(q_fail <= best_q_failures && q_err <= best_q_errors)
342 { best_q_failures = q_fail;
343 best_q_errors = q_err;
344 memcpy(best_p, p_vector, P_VECTOR_SIZE);
345 }
346 }
347 }
348 }
349
350 if(!candidate) err = -1; /* If P failed */
351 else
352 { FillPVector(rb->byteState, FRAME_BYTE_GOOD, p);
353 SetPVector(rb->recovered, best_p, p);
354
355 err = 0;
356 p_err += 2;
357 p_corrected++;
358 p_decimated++;
359 }
360 }
361
362 if(err == 0) FillPVector(rb->byteState, FRAME_BYTE_GOOD, p);
363 if(err < 0) /* Uncorrectable. */
364 {
365 p_failures++;
366 FillPVector(rb->byteState, FRAME_BYTE_ERROR, p);
367 }
368 }
369
370 if(CheckEDC(rb->recovered, rb->xaMode)) break;
371
372 /* Perform Q-Parity error correction */
373
374 for(q=0; q<N_Q_VECTORS; q++)
375 {
376 /* Determine number of erasures */
377
378 GetQVector(rb->byteState, q_state, q);
379 erasure_count = 0;
380
381 for(i=0; i<Q_VECTOR_SIZE-2; i++)
382 if(q_state[i] == FRAME_BYTE_ERROR) erasures[erasure_count++] = i;
383
384 /* First try to see whether Q is correctable without erasure markings. */
385
386 GetQVector(rb->recovered, q_vector, q);
387 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
388
389 if(err == 1) /* Store back corrected vector */
390 {
391 SetQVector(rb->recovered, q_vector, q);
392 FillQVector(rb->byteState, FRAME_BYTE_GOOD, q);
393 q_corrected++;
394 q_err++;
395 }
396
397 /* If there are more than 2 erasures we have have to decimate them to 2. */
398 /* The case for 2 erasure is also included here. */
399
400 if(err < 0 && erasure_count > 1)
401 { unsigned char best_q[Q_VECTOR_SIZE];
402 int best_p_failures = N_P_VECTORS;
403 int best_p_errors = N_P_VECTORS;
404 int candidate = FALSE;
405 int a, b;
406
407 /* Try error correction with decimated erasures */
408
409 for(a = 0; a < erasure_count - 1; a++)
410 {
411 for(b = a + 1; b < erasure_count; b++)
412 {
413 decimated_erasures[0] = erasures[a];
414 decimated_erasures[1] = erasures[b];
415 GetQVector(rb->recovered, q_vector, q);
416 err = DecodePQ(rb->rt, q_vector, Q_PADDING, decimated_erasures, 2);
417 if(err == 2)
418 { int p_err, p_fail;
419
420 candidate = TRUE;
421 eval_q_candidate(rb, q_vector, q, &p_fail, &p_err);
422
423 if(p_fail <= best_p_failures && p_err <= best_p_errors)
424 { best_p_failures = p_fail;
425 best_p_errors = p_err;
426 memcpy(best_q, q_vector, Q_VECTOR_SIZE);
427 }
428 }
429 }
430 }
431
432 if(!candidate) err = -1; /* If Q failed */
433 else
434 { FillQVector(rb->byteState, FRAME_BYTE_GOOD, q);
435 SetQVector(rb->recovered, best_q, q);
436
437 err = 0;
438 q_err += 2;
439 q_corrected++;
440 q_decimated++;
441 }
442 }
443
444 if(err == 0) FillQVector(rb->byteState, FRAME_BYTE_GOOD, q);
445 if(err < 0) /* Uncorrectable. Mark bytes are erasure. */
446 {
447 q_failures++;
448 FillQVector(rb->byteState, FRAME_BYTE_ERROR, q);
449 }
450 }
451
452 /* See if there was an improvement */
453
454 #ifdef DEBUG_HEURISTIC_LEC
455 Verbose("L-EC: iteration %d\n", iteration);
456 Verbose(" P-failures/corrected/errors + decimated: %2d/%2d/%2d + %2d\n", p_failures, p_corrected, p_err, p_decimated);
457 Verbose(" Q-failures/corrected/errors + decimated: %2d/%2d/%2d + %2d\n", q_failures, q_corrected, q_err, q_decimated);
458 #endif
459
460 if(p_failures + p_err + q_failures + q_err == 0) break;
461 if(last_p_err <= p_err && last_q_err <= q_err && last_p_failures <= p_failures && last_q_failures <= q_failures) break;
462
463 if(iteration > N_P_VECTORS + N_Q_VECTORS) break;
464
465 if(CheckEDC(rb->recovered, rb->xaMode)) break;
466
467 last_p_err = p_err;
468 last_q_err = q_err;
469 last_p_failures = p_failures;
470 last_q_failures = q_failures;
471 iteration++;
472 }
473
474 return TRUE;
475 }
476
477 /***
478 *** Heuristic search for best sector
479 *** Andrei Grecu, 2006
480 */
481
482 //#define DEBUG_SEARCHPLAUSIBLESECTOR
483
check_q_plausibility(RawBuffer * rb,unsigned char * target_q_vector,int q,int pos_a,int pos_b)484 static int check_q_plausibility(RawBuffer *rb, unsigned char *target_q_vector,
485 int q, int pos_a, int pos_b)
486 { unsigned char q_vector[Q_VECTOR_SIZE];
487 int plausible = FALSE;
488 int q_index;
489 int i;
490
491 /* If no position was given, then find it out. */
492
493 if(pos_a == -1)
494 {
495 GetQVector(rb->recovered, q_vector, q);
496 for(i = 0; i < Q_VECTOR_SIZE; i++)
497 if(target_q_vector[i] != q_vector[i])
498 {
499 pos_a = i;
500 break;
501 }
502
503 /* pos_a == -1 implies that only 1 byte was corrected
504 -> don't care about pos_b */
505
506 pos_b = -1;
507 }
508
509 /* Check plausibility of pos_a. */
510
511 q_index = QToByteIndex(q, pos_a);
512
513 for(i = 0; i < rb->samplesRead; i++)
514 if(rb->rawBuf[i][q_index] == target_q_vector[pos_a])
515 {
516 plausible = TRUE;
517 break;
518 }
519
520 if(!plausible) return FALSE;
521
522 /* pos_b only != -1 when Q corrected in erasure mode */
523
524 plausible = FALSE;
525
526 if(pos_b != -1)
527 {
528 /* Check plausibility of pos_b. */
529
530 q_index = QToByteIndex(q, pos_b);
531
532 for(i = 0; i < rb->samplesRead; i++)
533 if(rb->rawBuf[i][q_index] == target_q_vector[pos_b])
534 {
535 plausible = TRUE;
536 break;
537 }
538
539 if(!plausible) return FALSE;
540 }
541
542 return TRUE;
543 }
544
check_p_plausibility(RawBuffer * rb,unsigned char * target_p_vector,int p,int pos_a,int pos_b)545 static int check_p_plausibility(RawBuffer *rb, unsigned char *target_p_vector,
546 int p, int pos_a, int pos_b)
547 { unsigned char p_vector[P_VECTOR_SIZE];
548 int plausible = FALSE;
549 int p_index;
550 int i;
551
552 /* If no position was given, then find it out. */
553
554 if(pos_a == -1)
555 {
556 GetPVector(rb->recovered, p_vector, p);
557 for(i = 0; i < P_VECTOR_SIZE; i++)
558 {
559 if(target_p_vector[i] != p_vector[i])
560 {
561 pos_a = i;
562 break;
563 }
564 }
565
566 /* pos_a == -1 implies that only 1 byte was corrected
567 -> don't care about pos_b */
568
569 pos_b = -1;
570 }
571
572 /* Check plausibility of pos_a. */
573
574 p_index = PToByteIndex(p, pos_a);
575
576 for(i = 0; i < rb->samplesRead; i++)
577 if(rb->rawBuf[i][p_index] == target_p_vector[pos_a])
578 {
579 plausible = TRUE;
580 break;
581 }
582
583 if(!plausible) return FALSE;
584
585 /* pos_b only != -1 when P corrected in erasure mode */
586
587 plausible = FALSE;
588
589 if(pos_b != -1)
590 {
591 /* Check plausibility of pos_b. */
592
593 p_index = PToByteIndex(p, pos_b);
594
595 for(i = 0; i < rb->samplesRead; i++)
596 if(rb->rawBuf[i][p_index] == target_p_vector[pos_b])
597 {
598 plausible = TRUE;
599 break;
600 }
601
602 if(!plausible) return FALSE;
603 }
604
605 return TRUE;
606 }
607
find_better_p(RawBuffer * rb,int p,int refError)608 static int find_better_p(RawBuffer *rb, int p, int refError)
609 { unsigned char p_vector[P_VECTOR_SIZE];
610 int np1, np2;
611 int ignore[2];
612 int err;
613
614 /* Try all possible Ps and see whether we get a better load. */
615
616 for(np1 = 0; np1 < rb->pParityN[p][0]; np1++)
617 {
618 for(np2 = 0; np2 < rb->pParityN[p][1]; np2++)
619 {
620 GetPVector(rb->recovered, p_vector, p);
621 p_vector[24] = rb->pParity1[p][np1];
622 p_vector[25] = rb->pParity2[p][np2];
623
624 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
625 if(err < refError && err >= 0)
626 {
627 SetPVector(rb->recovered, p_vector, p);
628 return TRUE;
629 }
630 }
631 }
632
633 return FALSE;
634 }
635
find_better_q(RawBuffer * rb,int q,int refError)636 static int find_better_q(RawBuffer *rb, int q, int refError)
637 { unsigned char q_vector[Q_VECTOR_SIZE];
638 int nq1, nq2;
639 int ignore[2];
640 int err;
641
642 /* Try all possible Qs and see whether we get a better load. */
643
644 for(nq1 = 0; nq1 < rb->qParityN[q][0]; nq1++)
645 {
646 for(nq2 = 0; nq2 < rb->qParityN[q][1]; nq2++)
647 {
648 GetQVector(rb->recovered, q_vector, q);
649 q_vector[43] = rb->qParity1[q][nq1];
650 q_vector[44] = rb->qParity2[q][nq2];
651
652 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
653 if(err < refError && err >= 0)
654 {
655 SetQVector(rb->recovered, q_vector, q);
656 return TRUE;
657 }
658 }
659 }
660
661 return FALSE;
662 }
663
initialize_frame(RawBuffer * rb)664 static void initialize_frame(RawBuffer *rb)
665 { int best_sector = 0;
666 int max_load = 2 * (N_P_VECTORS + N_Q_VECTORS);
667 int i;
668
669 /* Initialize sector header. */
670
671 InitializeCDFrame(rb->recovered, rb->lba, rb->xaMode, 0);
672
673 /* Search for block with least P and Q load and load into the frame. */
674
675 for(i = 0; i < rb->samplesRead; i++)
676 {
677 if(rb->qLoad[i] + rb->pLoad[i] < max_load)
678 {
679 max_load = rb->pLoad[i] + rb->qLoad[i];
680 best_sector = i;
681 }
682 }
683
684 memcpy(&(rb->recovered[16]), &(rb->rawBuf[best_sector][16]), rb->sampleSize - 16);
685 if(!rb->xaMode)
686 memset(&(rb->recovered[2068]), 0, 8); /* 8 zero fill bytes */
687 }
688
689 //#define DEBUG_SEARCH_PLAUSIBLE
690
SearchPlausibleSector(RawBuffer * rb,int noCreateBuffer)691 int SearchPlausibleSector(RawBuffer *rb, int noCreateBuffer)
692 {
693 unsigned char p_vector[26];
694 unsigned char q_vector[45];
695 unsigned char cp_vector[26];
696 unsigned char cq_vector[45];
697 int decimated_erasures[2];
698 int ignore[2];
699 int p_failures, q_failures;
700 int p_corrected, q_corrected;
701 int p,q;
702 int iteration=1;
703 int p_err, q_err;
704 int p_decimated, q_decimated;
705 int last_p_err = N_P_VECTORS;
706 int last_q_err = N_Q_VECTORS;
707 int last_p_failures = N_P_VECTORS;
708 int last_q_failures = N_Q_VECTORS;
709 int err;
710
711 /* Initialize sector */
712
713 if(!noCreateBuffer) initialize_frame(rb);
714 else InitializeCDFrame(rb->recovered, rb->lba, rb->xaMode, 1);
715
716 for(; ;) /* iterate over P- and Q-Parity until failures converge */
717 {
718 p_failures = q_failures = 0;
719 p_corrected = q_corrected = 0;
720 p_err = q_err = 0;
721 p_decimated = q_decimated = 0;
722
723 /* Perform Q-Parity error correction */
724
725 for(q=0; q<N_Q_VECTORS; q++)
726 {
727 /* Check whether Q is correct. */
728 GetQVector(rb->recovered, q_vector, q);
729 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
730
731 /* If it is not correct. */
732 if(err == 1 || err < 0)
733 {
734 /* If Q is correctable. */
735 if(err == 1)
736 {
737 /* Check correction for plausibility: if corrected byte was read in one of the read attempts. */
738 if(check_q_plausibility(rb, q_vector, q, -1, -1))
739 {
740 /* Store back corrected vector */
741 SetQVector(rb->recovered, q_vector, q);
742 q_corrected++;
743 q_err++;
744 }
745 else
746 {
747 /* See whether we can find some Q parity bytes accepting the original Q vector. */
748 if(find_better_q(rb, q, 1))
749 {
750 q_corrected++;
751 q_err++;
752 }
753 else err = -1;
754 }
755 }
756
757 /* If correction is not plausible or possible then try 2 error-decimation. */
758 if(err < 0)
759 {
760 /* Try error correction with decimated erasures.
761 Note that no erasure information for the parity bytes is available */
762 int a, b;
763 int solFound = FALSE;
764
765 GetQVector(rb->byteCount, cq_vector, q);
766
767 for(a = 0; a < Q_VECTOR_SIZE - 2; a++)
768 {
769 if(cq_vector[a] == 1) continue; /* no alternatives */
770 for(b = a + 1; b < Q_VECTOR_SIZE - 2; b++)
771 {
772 if(cq_vector[b] == 1) continue; /* again, no alternatives present */
773
774 decimated_erasures[0] = a;
775 decimated_erasures[1] = b;
776 GetQVector(rb->recovered, q_vector, q);
777 err = DecodePQ(rb->rt, q_vector, Q_PADDING, decimated_erasures, 2);
778 if(err == 2)
779 {
780 if(check_q_plausibility(rb, q_vector, q, a, b)) { solFound = TRUE; break; }
781 }
782 }
783 if(solFound) break;
784 }
785 if(solFound)
786 {
787 /* Store back corrected vector */
788 SetQVector(rb->recovered, q_vector, q);
789 q_err += 2;
790 q_corrected++;
791 q_decimated++;
792 }
793 else
794 {
795 /* See whether we can find some Q parity bytes accepting the original Q vector. */
796 if(find_better_q(rb, q, 2))
797 {
798 q_corrected++;
799 q_err++;
800 }
801 else q_failures++; /* If Q failed */
802 }
803 }
804 }
805 }
806
807 /* Perform P-Parity error correction */
808
809 for(p=0; p<N_P_VECTORS; p++)
810 {
811 /* Check whether P is correct. */
812 GetPVector(rb->recovered, p_vector, p);
813 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
814
815 /* If it is not correct. */
816 if(err == 1 || err < 0)
817 {
818 /* If Q is correctable. */
819 if(err == 1)
820 {
821 /* Check correction for plausibility: if corrected byte was read in one of the read attempts. */
822 if(check_p_plausibility(rb, p_vector, p, -1, -1))
823 {
824 /* Store back corrected vector */
825 SetPVector(rb->recovered, p_vector, p);
826 p_corrected++;
827 p_err++;
828 }
829 else
830 {
831 /* See whether we can find some P parity bytes accepting the original P vector. */
832 if(find_better_p(rb, p, 1))
833 {
834 p_corrected++;
835 p_err++;
836 }
837 else err = -1;
838 }
839 }
840
841 /* If correction is not plausible or possible then try 2 error-decimation. */
842 if(err < 0)
843 {
844 /* Try error correction with decimated erasures */
845 int a, b;
846 int solFound = FALSE;
847 GetPVector(rb->byteCount, cp_vector, p);
848 for(a = 0; a < P_VECTOR_SIZE-2; a++) /* fixme: why -2? */
849 { if(cp_vector[a] == 1) continue;
850
851 for(b = a + 1; b < P_VECTOR_SIZE-2; b++) /* fixme: why -2? */
852 { if(cp_vector[b] == 1) continue;
853
854 decimated_erasures[0] = a;
855 decimated_erasures[1] = b;
856 GetPVector(rb->recovered, p_vector, p);
857 err = DecodePQ(rb->rt, p_vector, P_PADDING, decimated_erasures, 2);
858 if(err == 2)
859 {
860 if(check_p_plausibility(rb, p_vector, p, a, b)) { solFound = TRUE; break; }
861 }
862 }
863 if(solFound) break;
864 }
865 if(solFound)
866 {
867 /* Store back corrected vector */
868 SetPVector(rb->recovered, p_vector, p);
869 p_err += 2;
870 p_corrected++;
871 p_decimated++;
872 }
873 else
874 {
875 /* See whether we can find some P parity bytes accepting the original P vector. */
876 if(find_better_p(rb, p, 2))
877 {
878 p_corrected++;
879 p_err++;
880 }
881 else p_failures++; /* If P failed */
882 }
883 }
884 }
885 }
886
887 /* See if there was an improvement */
888
889 #ifdef DEBUG_SEARCH_PLAUSIBLE
890 Verbose("SPS L-EC: iteration %d\n", iteration);
891 Verbose(" Q-f/c/e + d: %2d/%2d/%2d + %2d\n", q_failures, q_corrected, q_err, q_decimated);
892 Verbose(" P-f/c/e + d: %2d/%2d/%2d + %2d\n", p_failures, p_corrected, p_err, p_decimated);
893 #endif
894
895 if(p_failures + p_err + q_failures + q_err == 0) break;
896 if(last_p_err <= p_err && last_q_err <= q_err && last_p_failures <= p_failures && last_q_failures <= q_failures) break;
897
898 if(iteration > N_P_VECTORS + N_Q_VECTORS) break;
899 if(p_failures == 0)
900 {
901 if(CheckEDC(rb->recovered, rb->xaMode)) break;
902 }
903
904 last_p_err = p_err;
905 last_q_err = q_err;
906 last_p_failures = p_failures;
907 last_q_failures = q_failures;
908 iteration++;
909 }
910
911 return TRUE;
912 }
913
914 /***
915 *** Correction by mutual Acknowledgement
916 *** Andrei Grecu, 2007
917 */
918
919 /* checks wether P acknowledges a Q byte */
920 /* the value to be used as the final Q byte is returned in *val */
does_P_ack(RawBuffer * rb,int q,int qpos,unsigned char * val,unsigned char * q_status)921 int does_P_ack(RawBuffer *rb, int q, int qpos, unsigned char *val, unsigned char *q_status)
922 {
923 unsigned char p_vector[26];
924 unsigned char q_vector[45];
925 unsigned char tp_vector[26];
926 unsigned char tq_vector[45];
927 int decimated_erasures[2];
928 int ignore[2];
929 int err;
930 int p, ppos;
931 int idx;
932
933 int tryAllErasures = 0;
934
935 /* initialize q vectors */
936 GetPVector(rb->recovered, q_vector, q);
937 GetPVector(rb->recovered, tq_vector, q);
938 q_vector[qpos] = *val;
939
940 /* check corresponding p for errors */
941 idx = QToByteIndex(q, qpos);
942 ByteIndexToP(idx, &p, &ppos);
943
944 GetPVector(rb->recovered, p_vector, p);
945 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
946
947 /* well we do have a problem here: p shows no error, but q does */
948 if(err == 0)
949 {
950 /* this is a special case of p and q want to correct the same byte */
951 /* provisoric heuristic solution: usually we should leave the byte untouched */
952 /* but if q wants to correct this byte to something which was already read */
953 /* then we will take the corrected byte */
954 if(!check_q_plausibility(rb, tq_vector, q, qpos, -1) && check_q_plausibility(rb, q_vector, q, qpos, -1)) return 1;
955 }
956
957 /* p and q show an error */
958 if(err == 1)
959 {
960 /* get position of corrected byte */
961 int tpos = -1, i;
962 GetPVector(rb->recovered, tp_vector, p);
963 for(i = 0; i < 26; i++)
964 {
965 if(p_vector[i] != tp_vector[i]) { tpos = i; break; }
966 }
967
968 /* looks good, p wants to correct this byte too */
969 if(tpos == ppos)
970 {
971 /* fantastic, p and q want to correct this byte to the same value */
972 if(q_vector[qpos] == p_vector[ppos]) return 1;
973 /* not good, p and q want to correct this byte to different values */
974 /* possibility 1: q has more than one faulty byte */
975 /* possibility 2: p has more than one faulty byte */
976 /* possibility 3: q, p have more than one faulty byte */
977 /* provisoric heuristic solution: take the version which was already read, if it was already read */
978 else
979 {
980 if(check_q_plausibility(rb, q_vector, q, qpos, -1)) { return 1; }
981 if(check_p_plausibility(rb, p_vector, p, ppos, -1)) { *val = p_vector[ppos]; return 1; }
982 }
983 }
984 /* looks bad, p wants to correct another byte */
985 /* possibility 1: q has more than one faulty byte */
986 /* possibility 2: p has more than one faulty byte */
987 /* possibility 3: q, p have more than one faulty byte */
988 /* provisoric heuristic solution: consider p has failed */
989 else tryAllErasures = 1;
990 }
991
992 /* p failure... we have to try all 2-erasure combinations containing this position */
993 if(err < 0) tryAllErasures = 1;
994
995 /* try all p 2-erasures for this position */
996 if(tryAllErasures)
997 {
998 int a;
999 for(a = 0; a < P_VECTOR_SIZE; a++)
1000 {
1001 int qi, qposi;
1002
1003 if(a == ppos) continue;
1004
1005 if(q_status != NULL)
1006 {
1007 /* if the corresponding q does not show an error we should not try to correct it */
1008 idx = PToByteIndex(p, a); ByteIndexToQ(idx, &qi, &qposi);
1009 if(q_status[qi] == 0) continue;
1010 }
1011
1012 decimated_erasures[0] = ppos < a ? ppos : a;
1013 decimated_erasures[1] = ppos < a ? a : ppos;
1014 GetPVector(rb->recovered, p_vector, p);
1015 err = DecodePQ(rb->rt, p_vector, P_PADDING, decimated_erasures, 2);
1016 if(err == 2)
1017 {
1018 /* please note: there can be more matching versions */
1019 /* provisoric heuristic solution: ignore the others */
1020 if(p_vector[ppos] == q_vector[qpos])
1021 {
1022 return 1;
1023 }
1024 }
1025 }
1026 }
1027
1028 return 0;
1029 }
1030
1031 /* checks wether Q acknowledges a P byte */
1032 /* the value to be used as the final P byte is returned in *val */
does_Q_ack(RawBuffer * rb,int p,int ppos,unsigned char * val,unsigned char * p_status)1033 int does_Q_ack(RawBuffer *rb, int p, int ppos, unsigned char *val, unsigned char *p_status)
1034 {
1035 unsigned char p_vector[26];
1036 unsigned char q_vector[45];
1037 unsigned char tp_vector[26];
1038 unsigned char tq_vector[45];
1039 int decimated_erasures[2];
1040 int ignore[2];
1041 int err;
1042 int q, qpos;
1043 int idx;
1044
1045 int tryAllErasures = 0;
1046
1047 /* initialize p vectors */
1048 GetPVector(rb->recovered, p_vector, p);
1049 GetPVector(rb->recovered, tp_vector, p);
1050 p_vector[ppos] = *val;
1051
1052 /* check corresponding q for errors */
1053 idx = PToByteIndex(p, ppos);
1054 ByteIndexToQ(idx, &q, &qpos);
1055
1056 GetQVector(rb->recovered, q_vector, q);
1057 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
1058
1059 /* well we do have a problem here: q shows no error, but p does */
1060 if(err == 0)
1061 {
1062 /* this is a special case of p and q want to correct the same byte */
1063 /* provisoric heuristic solution: usually we should leave the byte untouched */
1064 /* but if q wants to correct this byte to something which was already read */
1065 /* then we will take the corrected byte */
1066 if(!check_p_plausibility(rb, tp_vector, p, ppos, -1) && check_p_plausibility(rb, p_vector, p, ppos, -1)) return 1;
1067 }
1068
1069 /* p and q show an error */
1070 if(err == 1)
1071 {
1072 /* get position of corrected byte */
1073 int tpos = -1, i;
1074 GetQVector(rb->recovered, tq_vector, q);
1075 for(i = 0; i < 45; i++)
1076 {
1077 if(q_vector[i] != tq_vector[i]) { tpos = i; break; }
1078 }
1079
1080 /* looks good, q wants to correct this byte too */
1081 if(tpos == ppos)
1082 {
1083 /* fantastic, p and q want to correct this byte to the same value */
1084 if(p_vector[ppos] == q_vector[qpos]) return 1;
1085 /* not good, p and q want to correct this byte to different values */
1086 /* possibility 1: q has more than one faulty byte */
1087 /* possibility 2: p has more than one faulty byte */
1088 /* possibility 3: q, p have more than one faulty byte */
1089 /* provisoric heuristic solution: take the version which was already read, if it was already read */
1090 else
1091 {
1092 if(check_p_plausibility(rb, p_vector, p, qpos, -1)) { return 1; }
1093 if(check_q_plausibility(rb, q_vector, q, ppos, -1)) { *val = q_vector[qpos]; return 1; }
1094 }
1095 }
1096 /* looks bad, q wants to correct another byte */
1097 /* possibility 1: q has more than one faulty byte */
1098 /* possibility 2: p has more than one faulty byte */
1099 /* possibility 3: q, p have more than one faulty byte */
1100 /* provisoric heuristic solution: consider p has failed */
1101 else tryAllErasures = 1;
1102 }
1103
1104 /* q failure... we have to try all 2-erasure combinations containing this position */
1105 if(err < 0) tryAllErasures = 1;
1106
1107 /* try all q 2-erasures for this position */
1108 if(tryAllErasures)
1109 {
1110 int a;
1111 for(a = 0; a < Q_VECTOR_SIZE; a++)
1112 {
1113 int pi, pposi;
1114
1115 if(a == qpos) continue;
1116
1117 if(p_status != NULL)
1118 {
1119 /* if the corresponding p does not show an error we should not try to correct it */
1120 idx = QToByteIndex(q, a); ByteIndexToP(idx, &pi, &pposi);
1121 if(p_status[pi] == 0) continue;
1122 }
1123
1124 decimated_erasures[0] = qpos < a ? qpos : a;
1125 decimated_erasures[1] = qpos < a ? a : qpos;
1126 GetQVector(rb->recovered, q_vector, q);
1127 err = DecodePQ(rb->rt, q_vector, Q_PADDING, decimated_erasures, 2);
1128 if(err == 2)
1129 {
1130 /* please note: there can be more matching versions */
1131 /* provisoric heuristic solution: ignore the others */
1132 if(q_vector[qpos] == p_vector[ppos])
1133 {
1134 return 1;
1135 }
1136 }
1137 }
1138 }
1139
1140 return 0;
1141 }
1142
1143 int byteBadProbACK[2][4][4][2];
1144
AckHeuristic(RawBuffer * rb)1145 int AckHeuristic(RawBuffer *rb)
1146 {
1147 unsigned char p_vector[26];
1148 unsigned char q_vector[45];
1149 unsigned char tp_vector[26];
1150 unsigned char tq_vector[45];
1151 unsigned char qp_sector[45][26 * 2];
1152 unsigned char pq_sector[26][45 * 2];
1153 unsigned char qp_sector_valid[45][26];
1154 unsigned char pq_sector_valid[26][45];
1155 unsigned char qp_sector_exist[45];
1156 unsigned char pq_sector_exist[26];
1157 unsigned char p_status[N_P_VECTORS];
1158 unsigned char q_status[N_Q_VECTORS];
1159 int decimated_erasures[2];
1160 int ignore[2];
1161 int p_failures, q_failures;
1162 int p_corrected, q_corrected;
1163 int p, q;
1164 int i, j;
1165 int iteration=1;
1166 int p_err, q_err;
1167 int last_p_err = N_P_VECTORS;
1168 int last_q_err = N_Q_VECTORS;
1169 int last_p_failures = N_P_VECTORS;
1170 int last_q_failures = N_Q_VECTORS;
1171 int err;
1172 int qpos, ppos, tpos, idx;
1173
1174 /* Re-Initialize sector */
1175 InitializeCDFrame(rb->recovered, rb->lba, rb->xaMode, 1);
1176
1177 /* initialize counters */
1178 memset(qp_sector_exist, 0, 45);
1179 memset(pq_sector_exist, 0, 26);
1180
1181 for(; ;) /* iterate over P- and Q-Parity until failures converge */
1182 {
1183 p_failures = q_failures = 0;
1184 p_corrected = q_corrected = 0;
1185 p_err = q_err = 0;
1186
1187 /* Get the entire Q status */
1188 for(q = 0; q < N_Q_VECTORS; q++)
1189 {
1190 GetQVector(rb->recovered, q_vector, q);
1191 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
1192 if(err < 0) q_status[q] = 2;
1193 if(err == 1) q_status[q] = 1;
1194 if(!err) q_status[q] = 0;
1195 }
1196
1197 /* Get the entire P status */
1198 for(p = 0; p < N_P_VECTORS; p++)
1199 {
1200 GetPVector(rb->recovered, p_vector, p);
1201 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
1202 if(err < 0) p_status[p] = 2;
1203 if(err == 1) p_status[p] = 1;
1204 if(!err) p_status[p] = 0;
1205 }
1206
1207 /* Perform Q-Parity error correction */
1208 for(q = 0; q < N_Q_VECTORS; q++)
1209 {
1210 /* Check whether Q is correct. */
1211 GetQVector(rb->recovered, q_vector, q);
1212 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
1213
1214 /* if Q is correctable */
1215 if(err == 1)
1216 {
1217 q_err++;
1218
1219 /* get position of corrected byte */
1220 qpos = -1;
1221 GetQVector(rb->recovered, tq_vector, q);
1222 for(i = 0; i < 45; i++) if(q_vector[i] != tq_vector[i]) { qpos = i; break; }
1223
1224 /* Q wants to correct itself */
1225 if(qpos == 43 || qpos == 44)
1226 {
1227 /* we only allow this if the byte was already read */
1228 if(check_q_plausibility(rb, q_vector, q, qpos, -1)) { q_corrected++; SetQVector(rb->recovered, q_vector, q); }
1229 }
1230 else {
1231 if(does_P_ack(rb, q, qpos, &q_vector[qpos], q_status)) { q_corrected++; SetQVector(rb->recovered, q_vector, q); }
1232 }
1233 }
1234
1235 /* q failure... we have to try all 2-erasure combinations of q and check p (try all 2-erasure combinations of p if necessary) */
1236 if(err < 0)
1237 {
1238 int a, b;
1239 int manySols = 0;
1240 int undecidable = 0;
1241 int bestCompFound = 0;
1242 int bestA = 0;
1243 int bestB = 0;
1244 int bestPSol1 = 0;
1245 int bestPSol2 = 0;
1246 int bestP1 = 0;
1247 int bestP2 = 0;
1248 int bestP1_ACK = 0;
1249 int bestP2_ACK = 0;
1250
1251 q_failures++; q_err += 2;
1252
1253 /* try 2-erasure combinations of p */
1254 for(i = 0; i < 45 - 2; i++)
1255 {
1256 int tryAllErasures = 0;
1257 /* check corresponding p for errors */
1258 idx = QToByteIndex(q, i);
1259 ByteIndexToP(idx, &p, &ppos);
1260
1261 GetPVector(rb->recovered, p_vector, p);
1262 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
1263
1264 /* if p shows no error, then fill vector with already existing bytes */
1265 if(err == 0)
1266 {
1267 qp_sector_exist[i] = 0;
1268 }
1269
1270 if(err == 1)
1271 {
1272 /* get position of corrected byte */
1273 tpos = -1;
1274 GetPVector(rb->recovered, tp_vector, p);
1275 for(j = 0; j < 26; j++) if(p_vector[j] != tp_vector[j]) { tpos = j; break; }
1276
1277 /* looks good, p wants to correct this byte too */
1278 if(tpos == ppos)
1279 {
1280 for(j = 0; j < 26; j++)
1281 {
1282 qp_sector[i][j * 2 ] = p_vector[ppos];
1283 qp_sector[i][j * 2 + 1] = p_vector[j];
1284 qp_sector_valid[i][j] = 1;
1285 }
1286 qp_sector_exist[i] = 2;
1287 }
1288 /* p wants to correct another byte */
1289 /* provisoric heuristic solution: consider p has failed */
1290 else tryAllErasures = 1;
1291 }
1292
1293 /* p failure... we have to try all 2-erasure combinations containing this position */
1294 if(err < 0) tryAllErasures = 1;
1295
1296 if(tryAllErasures)
1297 {
1298 for(a = 0; a < P_VECTOR_SIZE; a++)
1299 {
1300 int qi, qposi;
1301
1302 if(a == ppos) continue;
1303
1304 idx = PToByteIndex(p, a); ByteIndexToQ(idx, &qi, &qposi);
1305
1306 /* if this q does not show an error we should not try to correct it */
1307 if(q_status[qi] == 0)
1308 {
1309 qp_sector_valid[i][a] = 0;
1310 continue;
1311 }
1312
1313 decimated_erasures[0] = ppos < a ? ppos : a;
1314 decimated_erasures[1] = ppos < a ? a : ppos;
1315 GetPVector(rb->recovered, p_vector, p);
1316 err = DecodePQ(rb->rt, p_vector, P_PADDING, decimated_erasures, 2);
1317 if(err == 2)
1318 {
1319 qp_sector[i][a * 2 ] = p_vector[ppos];
1320 qp_sector[i][a * 2 + 1] = p_vector[a];
1321 qp_sector_valid[i][a] = 1;
1322 }
1323 else qp_sector_valid[i][a] = 0;
1324 }
1325
1326 qp_sector_exist[i] = 1;
1327 }
1328 }
1329
1330 /* try 2-erasure combinations of q */
1331 for(a = 0; a < 45 - 1; a++)
1332 {
1333 if(a < 45 - 2 && !qp_sector_exist[a]) continue; /* if p reported no problems for first byte then we cannot do much here */
1334
1335 for(b = a + 1; b < 45; b++)
1336 {
1337 int compFound = 0;
1338 int pSol1 = -1, pSol2 = -1;
1339 int aMul = 0, bMul = 0;
1340
1341 if(b < 45 - 2 && !qp_sector_exist[b]) continue; /* if p reported no problems for second byte then we cannot do much here */
1342
1343 decimated_erasures[0] = a;
1344 decimated_erasures[1] = b;
1345 GetQVector(rb->recovered, q_vector, q);
1346 err = DecodePQ(rb->rt, q_vector, Q_PADDING, decimated_erasures, 2);
1347 if(err == 2)
1348 {
1349 int ppos1, ppos2;
1350 int p1, p2;
1351 idx = QToByteIndex(q, a); ByteIndexToP(idx, &p1, &ppos1);
1352 idx = QToByteIndex(q, b); ByteIndexToP(idx, &p2, &ppos2);
1353
1354 /* check first q corrected byte with all its p counterparts */
1355 if(a < 45 - 2 && qp_sector_exist[a])
1356 {
1357 for(i = 0; i < P_VECTOR_SIZE; i++)
1358 {
1359 if(i == ppos1) continue;
1360 if(qp_sector_valid[a][i] == 0) continue;
1361
1362 if(qp_sector[a][i * 2] == q_vector[a])
1363 {
1364 aMul++;
1365
1366 /* we found matching q and p corrected bytes */
1367 compFound |= 0x01;
1368 /* if p also wants to correct this byte with same value */
1369 if(qp_sector_exist[a] == 2)
1370 {
1371 compFound |= 0x04;
1372 break;
1373 }
1374
1375 pSol1 = i;
1376 }
1377 }
1378 }
1379
1380 /* check second q corrected byte with all its p counterparts */
1381 if(b < 45 - 2 && qp_sector_exist[b])
1382 {
1383 for(i = 0; i < P_VECTOR_SIZE; i++)
1384 {
1385 if(i == ppos2) continue;
1386 if(qp_sector_valid[b][i] == 0) continue;
1387
1388 if(qp_sector[b][i * 2] == q_vector[b])
1389 {
1390 bMul++;
1391
1392 /* we found matching q and p corrected bytes */
1393 compFound |= 0x02;
1394 /* if p also wants to correct this byte with same value */
1395 if(qp_sector_exist[b] == 2)
1396 {
1397 compFound |= 0x08;
1398 break;
1399 }
1400
1401 pSol2 = i;
1402 }
1403 }
1404 }
1405
1406 /* both bytes were acknowledged by the respective ps so save the change into temporary parameters */
1407 if(compFound & 0x01 || compFound & 0x02 || compFound & 0x04 || compFound & 0x08)
1408 {
1409 if(aMul <= 1 && bMul <= 1)
1410 {
1411 /* FIXME: maybe error: did original code really want "+" precede "&"? */
1412 #if 0 /* original code */
1413 int quality = compFound & 0x03 + ( compFound & 0x04) * 2 + ( compFound & 0x08) * 2;
1414 int bestQuality = bestCompFound & 0x03 + (bestCompFound & 0x04) * 2 + (bestCompFound & 0x08) * 2;
1415 #endif
1416 int quality = (compFound & 0x03) + ( compFound & 0x04) * 2 + ( compFound & 0x08) * 2;
1417 int bestQuality = (bestCompFound & 0x03) + (bestCompFound & 0x04) * 2 + (bestCompFound & 0x08) * 2;
1418 int P1_ACK = 0, P2_ACK = 0;
1419
1420 unsigned char c;
1421
1422 if(compFound & 0x01 && !(compFound & 0x04))
1423 {
1424 c = qp_sector[a][pSol1 * 2 + 1];
1425 if(does_Q_ack(rb, p1, pSol1, &c, NULL)) P1_ACK = 1;
1426
1427 p_vector[pSol1] = qp_sector[a][pSol1 * 2 + 1];
1428 if(check_p_plausibility(rb, p_vector, p1, pSol1, -1)) P1_ACK = 1;
1429
1430 if(check_q_plausibility(rb, q_vector, q, a, -1)) P1_ACK = 1;
1431 }
1432
1433 if(compFound & 0x02 && !(compFound & 0x08))
1434 {
1435 c = qp_sector[b][pSol2 * 2 + 1];
1436 if(does_Q_ack(rb, p2, pSol2, &c, NULL)) P2_ACK = 1;
1437
1438 p_vector[pSol2] = qp_sector[b][pSol2 * 2 + 1];
1439 if(check_p_plausibility(rb, p_vector, p2, pSol2, -1)) P2_ACK = 1;
1440
1441 if(check_q_plausibility(rb, q_vector, q, b, -1)) P2_ACK = 1;
1442 }
1443
1444 if(!P1_ACK && !P2_ACK && !(compFound & 0x04) && !(compFound & 0x08)) quality = 0;
1445
1446 if(quality > bestQuality)
1447 {
1448 bestA = a;
1449 bestB = b;
1450 bestPSol1 = pSol1;
1451 bestPSol2 = pSol2;
1452 bestP1 = p1;
1453 bestP2 = p2;
1454 bestP1_ACK = P1_ACK;
1455 bestP2_ACK = P2_ACK;
1456
1457 bestCompFound = compFound;
1458
1459 manySols++;
1460 }
1461 else if(quality == bestQuality) undecidable = 1;
1462
1463 }
1464
1465 if(aMul > 1 || bMul > 1)
1466 {
1467 aMul++;
1468 bMul++;
1469 }
1470 }
1471
1472 /* if both parity bytes should be corrected */
1473 /* take them only if they were already read */
1474 if(a == 45 - 2)
1475 {
1476 if(check_q_plausibility(rb, q_vector, q, a, b))
1477 {
1478 /* this solution has low priority, because here we have no acknowledging p */
1479 if(manySols == 0)
1480 {
1481 bestA = a;
1482 bestB = b;
1483 bestCompFound = 0x10;
1484
1485 manySols++;
1486 }
1487 }
1488 }
1489 }
1490 }
1491 }
1492
1493 /* after the best heuristic solution was found */
1494 if(!undecidable && manySols > 0)
1495 {
1496 int qquality = 0;
1497
1498 decimated_erasures[0] = bestA;
1499 decimated_erasures[1] = bestB;
1500 GetQVector(rb->recovered, q_vector, q);
1501 DecodePQ(rb->rt, q_vector, Q_PADDING, decimated_erasures, 2);
1502
1503 /* take both q corrections */
1504 SetQVector(rb->recovered, q_vector, q);
1505
1506 idx = QToByteIndex(q, bestA); qquality += rb->recovered[idx] == rb->reference[idx];
1507 idx = QToByteIndex(q, bestB); qquality += rb->recovered[idx] == rb->reference[idx];
1508
1509 byteBadProbACK[1][bestCompFound & 0x03][((bestCompFound & 0x04) >> 2) + ((bestCompFound & 0x08) >> 2)][!(qquality == 2)]++;
1510
1511 if(bestCompFound & 0x01 && !(bestCompFound & 0x04) && bestP1_ACK)
1512 {
1513 idx = PToByteIndex(bestP1, bestPSol1);
1514 rb->recovered[idx] = qp_sector[bestA][bestPSol1 * 2 + 1];
1515
1516 p_failures++; p_err += 2; p_corrected = 2;
1517 }
1518
1519 /* take second p correction if it was a two erasure correction */
1520 if(bestCompFound & 0x02 && !(bestCompFound & 0x08) && bestP2_ACK)
1521 {
1522 idx = PToByteIndex(bestP2, bestPSol2);
1523 rb->recovered[idx] = qp_sector[bestB][bestPSol2 * 2 + 1];
1524
1525 p_failures++; p_err += 2; p_corrected = 2;
1526 }
1527
1528 q_corrected += 2;
1529 }
1530 }
1531 }
1532
1533 if(CheckEDC(rb->recovered, rb->xaMode)) break;
1534
1535 /* Get the entire Q status */
1536 for(q = 0; q < N_Q_VECTORS; q++)
1537 {
1538 GetQVector(rb->recovered, q_vector, q);
1539 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
1540 if(err < 0) q_status[q] = 2;
1541 if(err == 1) q_status[q] = 1;
1542 if(!err) q_status[q] = 0;
1543 }
1544
1545 /* Get the entire P status */
1546 for(p = 0; p < N_P_VECTORS; p++)
1547 {
1548 GetPVector(rb->recovered, p_vector, p);
1549 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
1550 if(err < 0) p_status[p] = 2;
1551 if(err == 1) p_status[p] = 1;
1552 if(!err) p_status[p] = 0;
1553 }
1554
1555 /* Perform P-Parity error correction */
1556 for(p = 0; p < N_P_VECTORS; p++)
1557 {
1558 /* Check whether P is correct. */
1559 GetPVector(rb->recovered, p_vector, p);
1560 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
1561
1562 /* if P is correctable */
1563 if(err == 1)
1564 {
1565 p_err++;
1566
1567 /* get position of corrected byte */
1568 ppos = -1;
1569 GetPVector(rb->recovered, tp_vector, p);
1570 for(i = 0; i < 26; i++) if(p_vector[i] != tp_vector[i]) { ppos = i; break; }
1571
1572 if(does_Q_ack(rb, p, ppos, &p_vector[ppos], p_status)) { p_corrected++; SetPVector(rb->recovered, p_vector, p); }
1573 }
1574
1575 /* p failure... we have to try all 2-erasure combinations of q and check p (try all 2-erasure combinations of q if necessary) */
1576 if(err < 0)
1577 {
1578 int a, b;
1579 int manySols = 0;
1580 int undecidable = 0;
1581 int bestCompFound = 0;
1582 int bestA = 0;
1583 int bestB = 0;
1584 int bestQSol1 = 0;
1585 int bestQSol2 = 0;
1586 int bestQ1 = 0;
1587 int bestQ2 = 0;
1588 int bestQ1_ACK = 0;
1589 int bestQ2_ACK = 0;
1590
1591 p_failures++; p_err += 2;
1592
1593 /* try 2-erasure combinations of p */
1594 for(i = 0; i < 26; i++)
1595 {
1596 int tryAllErasures = 0;
1597 /* check corresponding q for errors */
1598 idx = PToByteIndex(p, i);
1599 ByteIndexToQ(idx, &q, &qpos);
1600
1601 GetQVector(rb->recovered, q_vector, q);
1602 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
1603
1604 /* if q shows no error, then fill vector with already existing bytes */
1605 if(err == 0)
1606 {
1607 pq_sector_exist[i] = 0;
1608 }
1609
1610 if(err == 1)
1611 {
1612 /* get position of corrected byte */
1613 tpos = -1;
1614 GetQVector(rb->recovered, tq_vector, q);
1615 for(j = 0; j < 45; j++) if(q_vector[j] != tq_vector[j]) { tpos = j; break; }
1616
1617 /* looks good, q wants to correct this byte too */
1618 if(tpos == qpos)
1619 {
1620 for(j = 0; j < 45; j++)
1621 {
1622 pq_sector[i][j * 2 ] = q_vector[qpos];
1623 pq_sector[i][j * 2 + 1] = q_vector[j];
1624 pq_sector_valid[i][j] = 1;
1625 }
1626 pq_sector_exist[i] = 2;
1627 }
1628 /* q wants to correct another byte */
1629 /* provisoric heuristic solution: consider q has failed */
1630 else if(tpos != 43 && tpos != 44) tryAllErasures = 1;
1631 }
1632
1633 /* q failure... we have to try all 2-erasure combinations containing this position */
1634 if(err < 0) tryAllErasures = 1;
1635
1636 if(tryAllErasures)
1637 {
1638 for(a = 0; a < Q_VECTOR_SIZE; a++)
1639 {
1640 int pi, pposi;
1641
1642 if(a == qpos) continue;
1643
1644 idx = QToByteIndex(q, a); ByteIndexToP(idx, &pi, &pposi);
1645
1646 /* if this q does not show an error we should not try to correct it */
1647 if(p_status[pi] == 0)
1648 {
1649 pq_sector_valid[i][a] = 0;
1650 continue;
1651 }
1652
1653 decimated_erasures[0] = qpos < a ? qpos : a;
1654 decimated_erasures[1] = qpos < a ? a : qpos;
1655 GetQVector(rb->recovered, q_vector, q);
1656 err = DecodePQ(rb->rt, q_vector, Q_PADDING, decimated_erasures, 2);
1657 if(err == 2)
1658 {
1659 pq_sector[i][a * 2 ] = q_vector[qpos];
1660 pq_sector[i][a * 2 + 1] = q_vector[a];
1661 pq_sector_valid[i][a] = 1;
1662 }
1663 else pq_sector_valid[i][a] = 0;
1664 }
1665
1666 pq_sector_exist[i] = 1;
1667 }
1668 }
1669
1670 /* try 2-erasure combinations of q */
1671 for(a = 0; a < 26 - 1; a++)
1672 {
1673 if(!pq_sector_exist[a]) continue; /* if q reported no problems for first byte then we cannot do much here */
1674
1675 for(b = a + 1; b < 26; b++)
1676 {
1677 int compFound = 0;
1678 int qSol1 = -1, qSol2 = -1;
1679 int aMul = 0, bMul = 0;
1680
1681 if(!pq_sector_exist[b]) continue; /* if q reported no problems for second byte then we cannot do much here */
1682
1683 decimated_erasures[0] = a;
1684 decimated_erasures[1] = b;
1685 GetPVector(rb->recovered, p_vector, p);
1686 err = DecodePQ(rb->rt, p_vector, P_PADDING, decimated_erasures, 2);
1687 if(err == 2)
1688 {
1689 int qpos1, qpos2;
1690 int q1, q2;
1691 idx = PToByteIndex(p, a); ByteIndexToQ(idx, &q1, &qpos1);
1692 idx = PToByteIndex(p, b); ByteIndexToQ(idx, &q2, &qpos2);
1693
1694 /* check first q corrected byte with all its p counterparts */
1695 if(pq_sector_exist[a])
1696 {
1697 for(i = 0; i < Q_VECTOR_SIZE; i++)
1698 {
1699 if(i == qpos1) continue;
1700 if(pq_sector_valid[a][i] == 0) continue;
1701
1702 if(pq_sector[a][i * 2] == p_vector[a])
1703 {
1704 aMul++;
1705
1706 /* we found matching q and p corrected bytes */
1707 compFound |= 0x01;
1708 /* if p also wants to correct this byte with same value */
1709 if(pq_sector_exist[a] == 2)
1710 {
1711 compFound |= 0x04;
1712 break;
1713 }
1714
1715 qSol1 = i;
1716 }
1717 }
1718 }
1719
1720 /* check second q corrected byte with all its p counterparts */
1721 if(pq_sector_exist[b])
1722 {
1723 for(i = 0; i < Q_VECTOR_SIZE; i++)
1724 {
1725 if(i == qpos2) continue;
1726 if(pq_sector_valid[b][i] == 0) continue;
1727
1728 if(pq_sector[b][i * 2] == p_vector[b])
1729 {
1730 bMul++;
1731
1732 /* we found matching q and p corrected bytes */
1733 compFound |= 0x02;
1734 /* if p also wants to correct this byte with same value */
1735 if(pq_sector_exist[b] == 2)
1736 {
1737 compFound |= 0x08;
1738 break;
1739 }
1740
1741 qSol2 = i;
1742 }
1743 }
1744 }
1745
1746 /* both bytes were acknowledged by the respective ps so save the change into temporary parameters */
1747 if(compFound & 0x01 || compFound & 0x02 || compFound & 0x04 || compFound & 0x08)
1748 {
1749 if(aMul <= 1 && bMul <= 1)
1750 {
1751 /* FIXME: same probs as above */
1752 #if 0
1753 int quality = compFound & 0x03 + ( compFound & 0x04) * 2 + ( compFound & 0x08) * 2;
1754 int bestQuality = bestCompFound & 0x03 + (bestCompFound & 0x04) * 2 + (bestCompFound & 0x08) * 2;
1755 #endif
1756 int quality = (compFound & 0x03) + ( compFound & 0x04) * 2 + ( compFound & 0x08) * 2;
1757 int bestQuality = (bestCompFound & 0x03) + (bestCompFound & 0x04) * 2 + (bestCompFound & 0x08) * 2;
1758 int Q1_ACK = 0, Q2_ACK = 0;
1759
1760 unsigned char c;
1761
1762 if(compFound & 0x01 && !(compFound & 0x04))
1763 {
1764 if(qSol1 < 43)
1765 {
1766 c = pq_sector[a][qSol1 * 2 + 1];
1767 if(does_P_ack(rb, q1, qSol1, &c, NULL)) Q1_ACK = 1;
1768 }
1769
1770 q_vector[qSol1] = pq_sector[a][qSol1 * 2 + 1];
1771 if(check_q_plausibility(rb, q_vector, q1, qSol1, -1)) Q1_ACK = 1;
1772
1773 if(check_p_plausibility(rb, p_vector, p, a, -1)) Q1_ACK = 1;
1774 }
1775
1776 if(compFound & 0x02 && !(compFound & 0x08))
1777 {
1778 if(qSol2 < 43)
1779 {
1780 c = pq_sector[b][qSol2 * 2 + 1];
1781 if(does_P_ack(rb, q2, qSol2, &c, NULL)) Q2_ACK = 1;
1782 }
1783
1784 q_vector[qSol2] = pq_sector[b][qSol2 * 2 + 1];
1785 if(check_q_plausibility(rb, q_vector, q2, qSol2, -1)) Q2_ACK = 1;
1786
1787 if(check_p_plausibility(rb, p_vector, p, b, -1)) Q2_ACK = 1;
1788 }
1789
1790 if(!Q1_ACK && !Q2_ACK && !(compFound & 0x04) && !(compFound & 0x08)) quality = 0;
1791
1792 if(quality > bestQuality)
1793 {
1794 bestA = a;
1795 bestB = b;
1796 bestQSol1 = qSol1;
1797 bestQSol2 = qSol2;
1798 bestQ1 = q1;
1799 bestQ2 = q2;
1800 bestQ1_ACK = Q1_ACK;
1801 bestQ2_ACK = Q2_ACK;
1802
1803 bestCompFound = compFound;
1804
1805 manySols++;
1806 }
1807 else if(quality == bestQuality) undecidable = 1;
1808
1809 }
1810
1811 if(aMul > 1 || bMul > 1)
1812 {
1813 aMul++;
1814 bMul++;
1815 }
1816 }
1817 }
1818 }
1819 }
1820
1821 /* after the best heuristic solution was found */
1822 if(!undecidable && manySols > 0)
1823 {
1824 int pquality = 0;
1825
1826 decimated_erasures[0] = bestA;
1827 decimated_erasures[1] = bestB;
1828 GetPVector(rb->recovered, p_vector, p);
1829 DecodePQ(rb->rt, p_vector, P_PADDING, decimated_erasures, 2);
1830
1831 /* take both p corrections */
1832 SetPVector(rb->recovered, p_vector, p);
1833
1834 idx = PToByteIndex(p, bestA); pquality += rb->recovered[idx] == rb->reference[idx];
1835 idx = PToByteIndex(p, bestB); pquality += rb->recovered[idx] == rb->reference[idx];
1836
1837 byteBadProbACK[1][bestCompFound & 0x03][((bestCompFound & 0x04) >> 2) + ((bestCompFound & 0x08) >> 2)][!(pquality == 2)]++;
1838
1839 if(bestCompFound & 0x01 && !(bestCompFound & 0x04) && bestQ1_ACK)
1840 {
1841 idx = QToByteIndex(bestQ1, bestQSol1);
1842 rb->recovered[idx] = pq_sector[bestA][bestQSol1 * 2 + 1];
1843
1844 q_failures++; q_err += 2; q_corrected = 2;
1845 }
1846
1847 /* take second p correction if it was a two erasure correction */
1848 if(bestCompFound & 0x02 && !(bestCompFound & 0x08) && bestQ2_ACK)
1849 {
1850 idx = QToByteIndex(bestQ2, bestQSol2);
1851 rb->recovered[idx] = pq_sector[bestB][bestQSol2 * 2 + 1];
1852
1853 q_failures++; q_err += 2; q_corrected = 2;
1854 }
1855
1856 p_corrected += 2;
1857 }
1858 }
1859 }
1860
1861 /* See if there was an improvement */
1862
1863 #ifdef DEBUG_ACK_HEURISTIC
1864 printf("AH L-EC: iteration %d\n", iteration);
1865 printf(" Q-f/c/e + d: %2d/%2d/%2d\n", q_failures, q_corrected, q_err);
1866 printf(" P-f/c/e + d: %2d/%2d/%2d\n", p_failures, p_corrected, p_err);
1867 #endif
1868
1869 if(p_failures + p_err + q_failures + q_err == 0) break;
1870 if(last_p_err <= p_err && last_q_err <= q_err && last_p_failures <= p_failures && last_q_failures <= q_failures) break;
1871
1872 if(iteration > N_P_VECTORS + N_Q_VECTORS) break;
1873 if(p_failures == 0)
1874 {
1875 if(CheckEDC(rb->recovered, rb->xaMode)) break;
1876 }
1877
1878 last_p_err = p_err;
1879 last_q_err = q_err;
1880 last_p_failures = p_failures;
1881 last_q_failures = q_failures;
1882 iteration++;
1883 }
1884
1885 return 1;
1886 }
1887
BruteForceSearchPlausibleSector(RawBuffer * rb)1888 int BruteForceSearchPlausibleSector(RawBuffer *rb)
1889 {
1890 unsigned char p_vector[26];
1891 unsigned char q_vector[45];
1892 unsigned char cp_vector[26];
1893 unsigned char cq_vector[45];
1894 int ignore[2];
1895 int p_failures, q_failures;
1896 int p_corrected, q_corrected;
1897 int p,q;
1898 int iteration=1;
1899 int p_err, q_err;
1900 int last_p_err = N_P_VECTORS;
1901 int last_q_err = N_Q_VECTORS;
1902 int last_p_failures = N_P_VECTORS;
1903 int last_q_failures = N_Q_VECTORS;
1904 int err;
1905
1906 unsigned char zList[45][256]; /* stores different bytes which were read for each position in a sector */
1907 unsigned char czList[45]; /* counts different bytes which were read for each position in a sector */
1908 int zStack[45], pzStack;
1909
1910 /* Re-Initialize sector */
1911 InitializeCDFrame(rb->recovered, rb->lba, rb->xaMode, 1);
1912
1913 for(; ;) /* iterate over P- and Q-Parity until failures converge */
1914 {
1915 p_failures = q_failures = 0;
1916 p_corrected = q_corrected = 0;
1917 p_err = q_err = 0;
1918
1919 /* Perform Q-Parity error correction */
1920 for(q = 0; q < N_Q_VECTORS; q++)
1921 {
1922 int referr;
1923 /* Check whether Q is correct. */
1924 GetQVector(rb->recovered, q_vector, q);
1925 referr = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
1926
1927 /* If it is not correct. */
1928 if(referr == 1 || referr < 0)
1929 {
1930 int a, b, c, complexity = 1;
1931
1932 if(referr < 0) { q_failures++; q_err += 2; }
1933 if(referr == 1) { q_err++; }
1934
1935 /* generate zList */
1936 for(a = 0; a < 45; a++)
1937 {
1938 czList[a] = 0;
1939
1940 if(a < 45 - 2)
1941 {
1942 int p, ppos;
1943 int idx = QToByteIndex(q, a);
1944 ByteIndexToP(idx, &p, &ppos);
1945
1946 GetPVector(rb->recovered, p_vector, p);
1947 err = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
1948 if(!err)
1949 {
1950 zList[a][czList[a]] = p_vector[ppos];
1951 czList[a]++;
1952 continue;
1953 }
1954 }
1955
1956 for(b = 0; b < rb->samplesRead; b++)
1957 {
1958 int found = 0;
1959 int idx = QToByteIndex(q, a);
1960
1961 for(c = 0; c < czList[a]; c++)
1962 {
1963 if(rb->rawBuf[b][idx] == zList[a][c]) { found = 1; break; }
1964 }
1965
1966 if(!found)
1967 {
1968 zList[a][czList[a]] = rb->rawBuf[b][idx];
1969 czList[a]++;
1970 }
1971 }
1972
1973 complexity *= czList[a];
1974 if(complexity > 65536) break;
1975 }
1976
1977 /* do not let the enumeration get too complex */
1978 if(complexity > 65536) continue;
1979 /* no degrees of freedom */
1980 if(complexity == 1) continue;
1981
1982 memset(zStack, 0, 45 * sizeof(int));
1983 while(1)
1984 {
1985 for(a = 0; a < 45; a++)
1986 {
1987 cq_vector[a] = zList[a][zStack[a]];
1988 }
1989
1990 err = DecodePQ(rb->rt, cq_vector, Q_PADDING, ignore, 0);
1991 if((referr < 0 && err >= 0) || (referr == 1 && err == 0))
1992 {
1993 SetQVector(rb->recovered, cq_vector, q);
1994 q_corrected++;
1995
1996 referr = err;
1997 if(referr == 0) break;
1998 }
1999
2000 pzStack = 0;
2001 while(pzStack < 45)
2002 {
2003 zStack[pzStack]++;
2004 if(zStack[pzStack] == czList[pzStack])
2005 {
2006 zStack[pzStack] = 0;
2007 pzStack++;
2008 }
2009 else break;
2010 }
2011
2012 if(pzStack == 45) break;
2013 }
2014 }
2015 }
2016
2017 /* Perform P-Parity error correction */
2018 for(p = 0; p < N_P_VECTORS; p++)
2019 {
2020 int referr;
2021 /* Check whether Q is correct. */
2022 GetPVector(rb->recovered, p_vector, p);
2023 referr = DecodePQ(rb->rt, p_vector, P_PADDING, ignore, 0);
2024
2025 /* If it is not correct. */
2026 if(referr == 1 || referr < 0)
2027 {
2028 int a, b, c, complexity = 1;
2029
2030 if(referr < 0) { p_failures++; p_err += 2; }
2031 if(referr == 1) { p_err++; }
2032
2033 /* generate zList */
2034 for(a = 0; a < 26; a++)
2035 {
2036 czList[a] = 0;
2037
2038 {
2039 int q, qpos;
2040 int idx = PToByteIndex(p, a);
2041 ByteIndexToQ(idx, &q, &qpos);
2042
2043 GetQVector(rb->recovered, q_vector, q);
2044 err = DecodePQ(rb->rt, q_vector, Q_PADDING, ignore, 0);
2045 if(!err)
2046 {
2047 zList[a][czList[a]] = q_vector[qpos];
2048 czList[a]++;
2049 continue;
2050 }
2051 }
2052
2053 for(b = 0; b < rb->samplesRead; b++)
2054 {
2055 int found = 0;
2056 int idx = PToByteIndex(p, a);
2057
2058 for(c = 0; c < czList[a]; c++)
2059 {
2060 if(rb->rawBuf[b][idx] == zList[a][c]) { found = 1; break; }
2061 }
2062
2063 if(!found)
2064 {
2065 zList[a][czList[a]] = rb->rawBuf[b][idx];
2066 czList[a]++;
2067 }
2068 }
2069
2070 complexity *= czList[a];
2071 if(complexity > 65536) break;
2072 }
2073
2074 /* do not let the enumeration get too complex */
2075 if(complexity > 65536) continue;
2076 /* no degrees of freedom */
2077 if(complexity == 1) continue;
2078
2079 memset(zStack, 0, 26 * sizeof(int));
2080 while(1)
2081 {
2082 for(a = 0; a < 26; a++)
2083 {
2084 cp_vector[a] = zList[a][zStack[a]];
2085 }
2086
2087 err = DecodePQ(rb->rt, cp_vector, P_PADDING, ignore, 0);
2088 if((referr < 0 && err >= 0) || (referr == 1 && err == 0))
2089 {
2090 SetPVector(rb->recovered, cp_vector, p);
2091 p_corrected++;
2092
2093 referr = err;
2094 if(referr == 0) break;
2095 }
2096
2097 pzStack = 0;
2098 while(pzStack < 26)
2099 {
2100 zStack[pzStack]++;
2101 if(zStack[pzStack] == czList[pzStack])
2102 {
2103 zStack[pzStack] = 0;
2104 pzStack++;
2105 }
2106 else break;
2107 }
2108
2109 if(pzStack == 26) break;
2110 }
2111 }
2112 }
2113
2114 /* See if there was an improvement */
2115
2116 #ifdef DEBUG_SEARCH_PLAUSIBLE
2117 Verbose("SPS L-EC: iteration %d\n", iteration);
2118 Verbose(" Q-f/c/e + d: %2d/%2d/%2d\n", q_failures, q_corrected, q_err);
2119 Verbose(" P-f/c/e + d: %2d/%2d/%2d\n", p_failures, p_corrected, p_err);
2120 #endif
2121
2122 if(p_failures + p_err + q_failures + q_err == 0) break;
2123 if(last_p_err <= p_err && last_q_err <= q_err && last_p_failures <= p_failures && last_q_failures <= q_failures) break;
2124
2125 if(iteration > N_P_VECTORS + N_Q_VECTORS) break;
2126 if(p_failures == 0)
2127 {
2128 if(CheckEDC(rb->recovered, rb->xaMode)) break;
2129 }
2130
2131 last_p_err = p_err;
2132 last_q_err = q_err;
2133 last_p_failures = p_failures;
2134 last_q_failures = q_failures;
2135 iteration++;
2136 }
2137
2138 return 1;
2139 }
2140