libparanoia/paranoia.c

   1 /*
   2  * This file has been modified for the cdrkit suite.
   3  *
   4  * The behaviour and appearence of the program code below can differ to a major
   5  * extent from the version distributed by the original author(s).
   6  *
   7  * For details, see Changelog file distributed with the cdrkit package. If you
   8  * received this file from another source then ask the distributing person for
   9  * a log of modifications.
  10  *
  11  */
  12
  13 /* @(#)paranoia.c       1.33 04/08/17 J. Schilling from cdparanoia-III-alpha9.8 */
  14 /*
  15  *      Modifications to make the code portable Copyright (c) 2002 J. Schilling
  16  */
  17 /*
  18  * CopyPolicy: GNU Public License 2 applies
  19  * Copyright (C) by Monty (xiphmont@mit.edu)
  20  *
  21  * Toplevel file for the paranoia abstraction over the cdda lib
  22  *
  23  */
  24
  25 /* immediate todo:: */
  26 /* Allow disabling of root fixups? */
  27
  28 /*
  29  * Dupe bytes are creeping into cases that require greater overlap
  30  * than a single fragment can provide.  We need to check against a
  31  * larger area* (+/-32 sectors of root?) to better eliminate
  32  *  dupes. Of course this leads to other problems... Is it actually a
  33  *  practically solvable problem?
  34  */
  35 /* Bimodal overlap distributions break us. */
  36 /* scratch detection/tolerance not implemented yet */
  37
  38 /*
  39  * Da new shtick: verification now a two-step assymetric process.
  40  *
  41  * A single 'verified/reconstructed' data segment cache, and then the
  42  * multiple fragment cache
  43  *
  44  * verify a newly read block against previous blocks; do it only this
  45  * once. We maintain a list of 'verified sections' from these matches.
  46  *
  47  * We then glom these verified areas into a new data buffer.
  48  * Defragmentation fixups are allowed here alone.
  49  *
  50  * We also now track where read boundaries actually happened; do not
  51  * verify across matching boundaries.
  52  */
  53
  54 /*
  55  * Silence.  "It's BAAAAAAaaack."
  56  *
  57  * audio is now treated as great continents of values floating on a
  58  * mantle of molten silence.  Silence is not handled by basic
  59  * verification at all; we simply anchor sections of nonzero audio to a
  60  * position and fill in everything else as silence.  We also note the
  61  * audio that interfaces with silence; an edge must be 'wet'.
  62  */
  63
  64 #include <mconfig.h>
  65 #include <allocax.h>
  66 #include <stdxlib.h>
  67 #include <unixstd.h>
  68 #include <standard.h>
  69 #include <utypes.h>
  70 #include <stdio.h>
  71 #include <strdefs.h>
  72 #include "p_block.h"
  73 #include "cdda_paranoia.h"
  74 #include "overlap.h"
  75 #include "gap.h"
  76 #include "isort.h"
  77 #include "pmalloc.h"
  78
  79 /*
  80  * used by: i_iterate_stage2() / i_stage2_each()
  81  */
  82 typedef struct sync_result {
  83         long            offset;
  84         long            begin;
  85         long            end;
  86 } sync_result;
  87
  88 static inline long re(root_block *root);
  89 static inline long rb(root_block *root);
  90 static inline long rs(root_block *root);
  91 static inline Int16_t *rv(root_block *root);
  92 static inline long i_paranoia_overlap(Int16_t *buffA, Int16_t *buffB,
  93                                       long offsetA, long offsetB,
  94                                       long sizeA, long sizeB,
  95                                       long *ret_begin, long *ret_end);
  96 static inline long i_paranoia_overlap2(Int16_t *buffA, Int16_t *buffB,
  97                                        Uchar *flagsA, Uchar *flagsB,
  98                                        long offsetA, long offsetB,
  99                                        long sizeA, long sizeB,
 100                                        long *ret_begin, long *ret_end);
 101 static inline long do_const_sync(c_block *A,
 102                                  sort_info *B, Uchar *flagB,
 103                                  long posA, long posB,
 104                                  long *begin, long *end, long *offset);
 105 static inline long try_sort_sync(cdrom_paranoia *p,
 106                                  sort_info *A, Uchar *Aflags,
 107                                  c_block *B,
 108                                  long post, long *begin, long *end,
 109                                  long *offset, void (*callback) (long, int));
 110 static inline void stage1_matched(c_block *old, c_block *new,
 111                                   long matchbegin, long matchend,
 112                                                                                          long matchoffset,
 113                                                                                          void (*callback) (long, int));
 114 static long i_iterate_stage1(cdrom_paranoia *p, c_block *old, c_block *new,
 115                              void (*callback) (long, int));
 116 static long i_stage1(cdrom_paranoia *p, c_block *new,
 117                                                         void (*callback) (long, int));
 118 static long i_iterate_stage2(cdrom_paranoia *p, v_fragment *v, sync_result *r,
 119                                                                           void (*callback)(long, int));
 120 static void i_silence_test(root_block *root);
 121 static long i_silence_match(root_block *root, v_fragment *v,
 122                             void (*callback) (long, int));
 123 static long i_stage2_each(root_block *root, v_fragment *v,
 124                           void (*callback) (long, int));
 125 static int i_init_root(root_block *root, v_fragment *v,
 126                        long begin, void (*callback)(long, int));
 127 static int vsort(const void *a, const void *b);
 128 static int i_stage2(cdrom_paranoia *p, long beginword, long endword,
 129                                                   void (*callback)(long, int));
 130 static void i_end_case(cdrom_paranoia *p, long endword,
 131                        void (*callback)(long, int));
 132 static void verify_skip_case(cdrom_paranoia *p,
 133                              void (*callback)(long, int));
 134 void paranoia_free(cdrom_paranoia *p);
 135 void paranoia_modeset(cdrom_paranoia *p, int enable);
 136 long paranoia_seek(cdrom_paranoia *p, long seek, int mode);
 137 c_block *i_read_c_block(cdrom_paranoia *p, long beginword, long endword,
 138                                                                 void (*callback)(long,int));
 139 Int16_t *paranoia_read(cdrom_paranoia *p, void (*callback)(long, int));
 140 Int16_t *paranoia_read_limited(cdrom_paranoia *p, void (*callback)(long, int),
 141                                int max_retries);
 142 void paranoia_overlapset(cdrom_paranoia *p, long overlap);
 143
 144
 145 static inline long re(root_block *root)
 146 {
 147         if (!root)
 148                 return (-1);
 149         if (!root->vector)
 150                 return (-1);
 151         return (ce(root->vector));
 152 }
 153
 154 static inline long rb(root_block *root)
 155 {
 156         if (!root)
 157                 return (-1);
 158         if (!root->vector)
 159                 return (-1);
 160         return (cb(root->vector));
 161 }
 162
 163 static inline long rs(root_block *root)
 164 {
 165         if (!root)
 166                 return (-1);
 167         if (!root->vector)
 168                 return (-1);
 169         return (cs(root->vector));
 170 }
 171
 172 static inline Int16_t *rv(root_block *root)
 173 {
 174         if (!root)
 175                 return (NULL);
 176         if (!root->vector)
 177                 return (NULL);
 178         return (cv(root->vector));
 179 }
 180
 181 #define rc(r)   ((r)->vector)
 182
 183 /*
 184  * matching and analysis code
 185  */
 186 static inline long
 187 i_paranoia_overlap(Int16_t *buffA, Int16_t *buffB, long offsetA, long offsetB,
 188                    long sizeA, long sizeB, long *ret_begin, long *ret_end)
 189 {
 190         long    beginA = offsetA;
 191         long    endA = offsetA;
 192         long    beginB = offsetB;
 193         long    endB = offsetB;
 194
 195         for (; beginA >= 0 && beginB >= 0; beginA--, beginB--)
 196                 if (buffA[beginA] != buffB[beginB])
 197                         break;
 198         beginA++;
 199         beginB++;
 200
 201         for (; endA < sizeA && endB < sizeB; endA++, endB++)
 202                 if (buffA[endA] != buffB[endB])
 203                         break;
 204
 205         if (ret_begin)
 206                 *ret_begin = beginA;
 207         if (ret_end)
 208                 *ret_end = endA;
 209         return (endA - beginA);
 210 }
 211
 212 static inline long
 213 i_paranoia_overlap2(Int16_t *buffA, Int16_t *buffB, Uchar *flagsA,
 214                     Uchar *flagsB, long offsetA, long offsetB, long sizeA,
 215                     long sizeB, long *ret_begin, long *ret_end)
 216 {
 217         long            beginA = offsetA;
 218         long            endA = offsetA;
 219         long            beginB = offsetB;
 220         long            endB = offsetB;
 221
 222         for (; beginA >= 0 && beginB >= 0; beginA--, beginB--) {
 223                 if (buffA[beginA] != buffB[beginB])
 224                         break;
 225                 /*
 226                  * don't allow matching across matching sector boundaries
 227                  */
 228                 if ((flagsA[beginA] & flagsB[beginB] & 1)) {
 229                         beginA--;
 230                         beginB--;
 231                         break;
 232                 }
 233                 /*
 234                  * don't allow matching through known missing data
 235                  */
 236                 if ((flagsA[beginA] & 2) || (flagsB[beginB] & 2))
 237                         break;
 238         }
 239         beginA++;
 240         beginB++;
 241
 242         for (; endA < sizeA && endB < sizeB; endA++, endB++) {
 243                 if (buffA[endA] != buffB[endB])
 244                         break;
 245                 /*
 246                  * don't allow matching across matching sector boundaries
 247                  */
 248                 if ((flagsA[endA] & flagsB[endB] & 1) && endA != beginA) {
 249                         break;
 250                 }
 251                 /*
 252                  * don't allow matching through known missing data
 253                  */
 254                 if ((flagsA[endA] & 2) || (flagsB[endB] & 2))
 255                         break;
 256         }
 257
 258         if (ret_begin)
 259                 *ret_begin = beginA;
 260         if (ret_end)
 261                 *ret_end = endA;
 262         return (endA - beginA);
 263 }
 264
 265 /* Top level of the first stage matcher */
 266
 267 /*
 268  * We match each analysis point of new to the preexisting blocks
 269  * recursively.  We can also optionally maintain a list of fragments of
 270  * the preexisting block that didn't match anything, and match them back
 271  * afterward.
 272  */
 273 #define OVERLAP_ADJ     (MIN_WORDS_OVERLAP/2-1)
 274
 275 static inline long
 276 do_const_sync(c_block *A, sort_info *B, Uchar *flagB, long posA, long posB,
 277               long *begin, long *end, long *offset)
 278 {
 279         Uchar           *flagA = A->flags;
 280         long            ret = 0;
 281
 282         if (flagB == NULL)
 283                 ret = i_paranoia_overlap(cv(A), iv(B), posA, posB,
 284                         cs(A), is(B), begin, end);
 285         else if ((flagB[posB] & 2) == 0)
 286                 ret = i_paranoia_overlap2(cv(A), iv(B), flagA, flagB, posA, posB, cs(A),
 287                         is(B), begin, end);
 288
 289         if (ret > MIN_WORDS_SEARCH) {
 290                 *offset = (posA + cb(A)) - (posB + ib(B));
 291                 *begin += cb(A);
 292                 *end += cb(A);
 293                 return (ret);
 294         }
 295         return (0);
 296 }
 297
 298 /*
 299  * post is w.r.t. B.  in stage one, we post from old.  In stage 2 we
 300  * post from root. Begin, end, offset count from B's frame of
 301  * reference
 302  */
 303 static inline long
 304 try_sort_sync(cdrom_paranoia *p, sort_info *A, Uchar *Aflags, c_block *B,
 305               long post, long *begin, long *end, long *offset,
 306               void (*callback)(long, int))
 307 {
 308
 309         long            dynoverlap = p->dynoverlap;
 310         sort_link       *ptr = NULL;
 311         Uchar           *Bflags = B->flags;
 312
 313         /*
 314          * block flag matches 0x02 (unmatchable)
 315          */
 316         if (Bflags == NULL || (Bflags[post - cb(B)] & 2) == 0) {
 317                 /*
 318                  * always try absolute offset zero first!
 319                  */
 320                 {
 321                         long            zeropos = post - ib(A);
 322
 323                         if (zeropos >= 0 && zeropos < is(A)) {
 324                                 if (cv(B)[post - cb(B)] == iv(A)[zeropos]) {
 325                                         if (do_const_sync(B, A, Aflags,
 326                                                         post - cb(B), zeropos,
 327                                                         begin, end, offset)) {
 328
 329                                                 offset_add_value(p, &(p->stage1), *offset, callback);
 330
 331                                                 return (1);
 332                                         }
 333                                 }
 334                         }
 335                 }
 336         } else
 337                 return (0);
 338
 339         ptr = sort_getmatch(A, post - ib(A), dynoverlap, cv(B)[post - cb(B)]);
 340
 341         while (ptr) {
 342
 343                 if (do_const_sync(B, A, Aflags,
 344                                 post - cb(B), ipos(A, ptr),
 345                                 begin, end, offset)) {
 346                         offset_add_value(p, &(p->stage1), *offset, callback);
 347                         return (1);
 348                 }
 349                 ptr = sort_nextmatch(A, ptr);
 350         }
 351
 352         *begin = -1;
 353         *end = -1;
 354         *offset = -1;
 355         return (0);
 356 }
 357
 358 static inline void
 359 stage1_matched(c_block *old, c_block *new, long matchbegin, long matchend,
 360                long matchoffset, void (*callback)(long, int))
 361 {
 362         long            i;
 363         long            oldadjbegin = matchbegin - cb(old);
 364         long            oldadjend = matchend - cb(old);
 365         long            newadjbegin = matchbegin - matchoffset - cb(new);
 366         long            newadjend = matchend - matchoffset - cb(new);
 367
 368         if (matchbegin - matchoffset <= cb(new) ||
 369                 matchbegin <= cb(old) ||
 370                 (new->flags[newadjbegin] & 1) ||
 371                 (old->flags[oldadjbegin] & 1)) {
 372                 if (matchoffset)
 373                         if (callback)
 374                                 (*callback) (matchbegin, PARANOIA_CB_FIXUP_EDGE);
 375         } else if (callback)
 376                 (*callback) (matchbegin, PARANOIA_CB_FIXUP_ATOM);
 377
 378         if (matchend - matchoffset >= ce(new) ||
 379                 (new->flags[newadjend] & 1) ||
 380                 matchend >= ce(old) ||
 381                 (old->flags[oldadjend] & 1)) {
 382                 if (matchoffset)
 383                         if (callback)
 384                                 (*callback) (matchend, PARANOIA_CB_FIXUP_EDGE);
 385         } else if (callback)
 386                 (*callback) (matchend, PARANOIA_CB_FIXUP_ATOM);
 387
 388         /*
 389          * Mark the verification flags.  Don't mark the first or last OVERLAP/2
 390          * elements so that overlapping fragments have to overlap by OVERLAP to
 391          * actually merge. We also remove elements from the sort such that
 392          * later sorts do not have to sift through already matched data
 393          */
 394         newadjbegin += OVERLAP_ADJ;
 395         newadjend -= OVERLAP_ADJ;
 396         for (i = newadjbegin; i < newadjend; i++)
 397                 new->flags[i] |= 4;     /* mark verified */
 398
 399         oldadjbegin += OVERLAP_ADJ;
 400         oldadjend -= OVERLAP_ADJ;
 401         for (i = oldadjbegin; i < oldadjend; i++)
 402                 old->flags[i] |= 4;     /* mark verified */
 403
 404 }
 405
 406 #define CB_NULL         (void (*)(long, int))0
 407
 408 static long
 409 i_iterate_stage1(cdrom_paranoia *p, c_block *old, c_block *new,
 410                  void (*callback)(long, int))
 411 {
 412
 413         long            matchbegin = -1;
 414         long            matchend = -1;
 415         long            matchoffset;
 416
 417         /*
 418          * we no longer try to spread the stage one search area by dynoverlap
 419          */
 420         long            searchend = min(ce(old), ce(new));
 421         long            searchbegin = max(cb(old), cb(new));
 422         long            searchsize = searchend - searchbegin;
 423         sort_info       *i = p->sortcache;
 424         long            ret = 0;
 425         long            j;
 426
 427         long            tried = 0;
 428         long            matched = 0;
 429
 430         if (searchsize <= 0)
 431                 return (0);
 432
 433         /*
 434          * match return values are in terms of the new vector, not old
 435          */
 436         for (j = searchbegin; j < searchend; j += 23) {
 437                 if ((new->flags[j - cb(new)] & 6) == 0) {
 438                         tried++;
 439                         if (try_sort_sync(p, i, new->flags, old, j, &matchbegin, &matchend, &matchoffset,
 440                                         callback) == 1) {
 441
 442                                 matched += matchend - matchbegin;
 443
 444                                 /*
 445                                  * purely cosmetic: if we're matching zeros,
 446                                  * don't use the callback because they will
 447                                  * appear to be all skewed
 448                                  */
 449                                 {
 450                                         long            jj = matchbegin - cb(old);
 451                                         long            end = matchend - cb(old);
 452
 453                                         for (; jj < end; jj++)
 454                                                 if (cv(old)[jj] != 0)
 455                                                         break;
 456                                         if (jj < end) {
 457                                                 stage1_matched(old, new, matchbegin, matchend, matchoffset, callback);
 458                                         } else {
 459                                                 stage1_matched(old, new, matchbegin, matchend, matchoffset, CB_NULL);
 460                                         }
 461                                 }
 462                                 ret++;
 463                                 if (matchend - 1 > j)
 464                                         j = matchend - 1;
 465                         }
 466                 }
 467         }
 468 #ifdef NOISY
 469         fprintf(stderr, "iterate_stage1: search area=%ld[%ld-%ld] tried=%ld matched=%ld spans=%ld\n",
 470                 searchsize, searchbegin, searchend, tried, matched, ret);
 471 #endif
 472
 473         return (ret);
 474 }
 475
 476 static long
 477 i_stage1(cdrom_paranoia *p, c_block *new, void (*callback)(long, int))
 478 {
 479
 480         long            size = cs(new);
 481         c_block         *ptr = c_last(p);
 482         int             ret = 0;
 483         long            begin = 0;
 484         long            end;
 485
 486         if (ptr)
 487                 sort_setup(p->sortcache, cv(new), &cb(new), cs(new),
 488                         cb(new), ce(new));
 489
 490         while (ptr && ptr != new) {
 491
 492                 if (callback)
 493                         (*callback) (cb(new), PARANOIA_CB_VERIFY);
 494                 i_iterate_stage1(p, ptr, new, callback);
 495
 496                 ptr = c_prev(ptr);
 497         }
 498
 499         /*
 500          * parse the verified areas of new into v_fragments
 501          */
 502         begin = 0;
 503         while (begin < size) {
 504                 for (; begin < size; begin++)
 505                         if (new->flags[begin] & 4)
 506                                 break;
 507                 for (end = begin; end < size; end++)
 508                         if ((new->flags[end] & 4) == 0)
 509                                 break;
 510                 if (begin >= size)
 511                         break;
 512
 513                 ret++;
 514
 515                 new_v_fragment(p, new, cb(new) + max(0, begin - OVERLAP_ADJ),
 516                         cb(new) + min(size, end + OVERLAP_ADJ),
 517                         (end + OVERLAP_ADJ >= size && new->lastsector));
 518
 519                 begin = end;
 520         }
 521
 522         return (ret);
 523 }
 524
 525 /*
 526  * reconcile v_fragments to root buffer.  Free if matched, fragment/fixup root
 527  * if necessary
 528  *
 529  * do *not* match using zero posts
 530  */
 531 static long
 532 i_iterate_stage2(cdrom_paranoia *p, v_fragment *v, sync_result *r,
 533                  void (*callback)(long, int))
 534 {
 535         root_block      *root = &(p->root);
 536         long            matchbegin = -1;
 537         long            matchend = -1;
 538         long            offset;
 539         long            fbv;
 540         long            fev;
 541
 542 #ifdef NOISY
 543         fprintf(stderr, "Stage 2 search: fbv=%ld fev=%ld\n", fb(v), fe(v));
 544 #endif
 545
 546         if (min(fe(v) + p->dynoverlap, re(root)) -
 547                 max(fb(v) - p->dynoverlap, rb(root)) <= 0)
 548                 return (0);
 549
 550         if (callback)
 551                 (*callback) (fb(v), PARANOIA_CB_VERIFY);
 552
 553         /*
 554          * just a bit of v; determine the correct area
 555          */
 556         fbv = max(fb(v), rb(root) - p->dynoverlap);
 557
 558         /*
 559          * we want to avoid zeroes
 560          */
 561         while (fbv < fe(v) && fv(v)[fbv - fb(v)] == 0)
 562                 fbv++;
 563         if (fbv == fe(v))
 564                 return (0);
 565         fev = min(min(fbv + 256, re(root) + p->dynoverlap), fe(v));
 566
 567         {
 568                 /*
 569                  * spread the search area a bit.  We post from root, so
 570                  * containment must strictly adhere to root
 571                  */
 572                 long            searchend = min(fev + p->dynoverlap, re(root));
 573                 long            searchbegin = max(fbv - p->dynoverlap, rb(root));
 574                 sort_info       *i = p->sortcache;
 575                 long            j;
 576
 577                 sort_setup(i, fv(v), &fb(v), fs(v), fbv, fev);
 578                 for (j = searchbegin; j < searchend; j += 23) {
 579                         while (j < searchend && rv(root)[j - rb(root)] == 0)
 580                                 j++;
 581                         if (j == searchend)
 582                                 break;
 583
 584                         if (try_sort_sync(p, i, (Uchar *)0, rc(root), j,
 585                                         &matchbegin, &matchend, &offset, callback)) {
 586
 587                                 r->begin = matchbegin;
 588                                 r->end = matchend;
 589                                 r->offset = -offset;
 590                                 if (offset)
 591                                         if (callback)
 592                                                 (*callback) (r->begin, PARANOIA_CB_FIXUP_EDGE);
 593                                 return (1);
 594                         }
 595                 }
 596         }
 597         return (0);
 598 }
 599
 600 /*
 601  * simple test for a root vector that ends in silence
 602  */
 603 static void i_silence_test(root_block *root)
 604 {
 605         Int16_t         *vec = rv(root);
 606         long            end = re(root) - rb(root) - 1;
 607         long            j;
 608
 609         for (j = end - 1; j >= 0; j--)
 610                 if (vec[j] != 0)
 611                         break;
 612         if (j < 0 || end - j > MIN_SILENCE_BOUNDARY) {
 613                 if (j < 0)
 614                         j = 0;
 615                 root->silenceflag = 1;
 616                 root->silencebegin = rb(root) + j;
 617                 if (root->silencebegin < root->returnedlimit)
 618                         root->silencebegin = root->returnedlimit;
 619         }
 620 }
 621
 622 /*
 623  * match into silence vectors at offset zero if at all possible.  This
 624  * also must be called with vectors in ascending begin order in case
 625  * there are nonzero islands
 626  */
 627 static long
 628 i_silence_match(root_block *root, v_fragment *v, void (*callback)(long, int))
 629 {
 630
 631         cdrom_paranoia  *p = v->p;
 632         Int16_t *vec = fv(v);
 633         long            end = fs(v);
 634         long            begin;
 635         long            j;
 636
 637         /*
 638          * does this vector begin wet?
 639          */
 640         if (end < MIN_SILENCE_BOUNDARY)
 641                 return (0);
 642         for (j = 0; j < end; j++)
 643                 if (vec[j] != 0)
 644                         break;
 645         if (j < MIN_SILENCE_BOUNDARY)
 646                 return (0);
 647         j += fb(v);
 648
 649         /*
 650          * is the new silent section ahead of the end of the old
 651          * by < p->dynoverlap?
 652          */
 653         if (fb(v) >= re(root) && fb(v) - p->dynoverlap < re(root)) {
 654                 /*
 655                  * extend the zeroed area of root
 656                  * XXX dynarrays are not needed here.
 657                  */
 658                 long            addto = fb(v) + MIN_SILENCE_BOUNDARY - re(root);
 659 /*              Int16_t         avec[addto];*/
 660 #ifdef  HAVE_ALLOCA
 661                 Int16_t         *avec = alloca(addto * sizeof (Int16_t));
 662 #else
 663                 Int16_t         *avec = _pmalloc(addto * sizeof (Int16_t));
 664 #endif
 665
 666                 memset(avec, 0, sizeof (avec));
 667                 c_append(rc(root), avec, addto);
 668 #ifndef HAVE_ALLOCA
 669                 _pfree(avec);
 670 #endif
 671         }
 672         /*
 673          * do we have an 'effortless' overlap?
 674          */
 675         begin = max(fb(v), root->silencebegin);
 676         end = min(j, re(root));
 677
 678         if (begin < end) {
 679                 /*
 680                  * don't use it unless it will extend...
 681                  */
 682                 if (fe(v) > re(root)) {
 683                         long            voff = begin - fb(v);
 684
 685                         c_remove(rc(root), begin - rb(root), -1);
 686                         c_append(rc(root), vec + voff, fs(v) - voff);
 687                 }
 688                 offset_add_value(p, &p->stage2, 0, callback);
 689
 690         } else {
 691                 if (j < begin) {
 692                         /*
 693                          * OK, we'll have to force it a bit as the root is
 694                          * jittered forward
 695                          */
 696                         long            voff = j - fb(v);
 697
 698                         /*
 699                          * don't use it unless it will extend...
 700                          */
 701                         if (begin + fs(v) - voff > re(root)) {
 702                                 c_remove(rc(root), root->silencebegin - rb(root), -1);
 703                                 c_append(rc(root), vec + voff, fs(v) - voff);
 704                         }
 705                         offset_add_value(p, &p->stage2, end - begin, callback);
 706                 } else
 707                         return (0);
 708         }
 709
 710         /*
 711          * test the new root vector for ending in silence
 712          */
 713         root->silenceflag = 0;
 714         i_silence_test(root);
 715
 716         if (v->lastsector)
 717                 root->lastsector = 1;
 718         free_v_fragment(v);
 719         return (1);
 720 }
 721
 722 static long
 723 i_stage2_each(root_block *root, v_fragment *v, void (*callback)(long, int))
 724 {
 725
 726         cdrom_paranoia *p = v->p;
 727         long            dynoverlap = p->dynoverlap / 2 * 2;
 728
 729         if (!v || !v->one)
 730                 return (0);
 731
 732         if (!rv(root)) {
 733                 return (0);
 734         } else {
 735                 sync_result     r;
 736
 737                 if (i_iterate_stage2(p, v, &r, callback)) {
 738
 739                         long            begin = r.begin - rb(root);
 740                         long            end = r.end - rb(root);
 741                         long            offset = r.begin + r.offset - fb(v) - begin;
 742                         long            temp;
 743                         c_block         *l = NULL;
 744
 745                         /*
 746                          * we have a match! We don't rematch off rift, we chase
 747                          * the match all the way to both extremes doing rift
 748                          * analysis.
 749                          */
 750 #ifdef NOISY
 751                         fprintf(stderr, "Stage 2 match\n");
 752 #endif
 753
 754                         /*
 755                          * chase backward
 756                          * note that we don't extend back right now, only
 757                          * forward.
 758                          */
 759                         while ((begin + offset > 0 && begin > 0)) {
 760                                 long            matchA = 0,
 761                                                 matchB = 0,
 762                                                 matchC = 0;
 763                                 long            beginL = begin + offset;
 764
 765                                 if (l == NULL) {
 766                                         Int16_t *buff = _pmalloc(fs(v) * sizeof (Int16_t));
 767
 768                                         l = c_alloc(buff, fb(v), fs(v));
 769                                         memcpy(buff, fv(v), fs(v) * sizeof (Int16_t));
 770                                 }
 771                                 i_analyze_rift_r(rv(root), cv(l),
 772                                         rs(root), cs(l),
 773                                         begin - 1, beginL - 1,
 774                                         &matchA, &matchB, &matchC);
 775
 776 #ifdef NOISY
 777                                 fprintf(stderr, "matching rootR: matchA:%ld matchB:%ld matchC:%ld\n",
 778                                         matchA, matchB, matchC);
 779 #endif
 780
 781                                 if (matchA) {
 782                                         /*
 783                                          * a problem with root
 784                                          */
 785                                         if (matchA > 0) {
 786                                                 /*
 787                                                  * dropped bytes; add back from v
 788                                                  */
 789                                                 if (callback)
 790                                                         (*callback) (begin + rb(root) - 1, PARANOIA_CB_FIXUP_DROPPED);
 791                                                 if (rb(root) + begin < p->root.returnedlimit)
 792                                                         break;
 793                                                 else {
 794                                                         c_insert(rc(root), begin, cv(l) + beginL - matchA,
 795                                                                 matchA);
 796                                                         offset -= matchA;
 797                                                         begin += matchA;
 798                                                         end += matchA;
 799                                                 }
 800                                         } else {
 801                                                 /*
 802                                                  * duplicate bytes; drop from root
 803                                                  */
 804                                                 if (callback)
 805                                                         (*callback) (begin + rb(root) - 1, PARANOIA_CB_FIXUP_DUPED);
 806                                                 if (rb(root) + begin + matchA < p->root.returnedlimit)
 807                                                         break;
 808                                                 else {
 809                                                         c_remove(rc(root), begin + matchA, -matchA);
 810                                                         offset -= matchA;
 811                                                         begin += matchA;
 812                                                         end += matchA;
 813                                                 }
 814                                         }
 815                                 } else if (matchB) {
 816                                         /*
 817                                          * a problem with the fragment
 818                                          */
 819                                         if (matchB > 0) {
 820                                                 /*
 821                                                  * dropped bytes
 822                                                  */
 823                                                 if (callback)
 824                                                         (*callback) (begin + rb(root) - 1, PARANOIA_CB_FIXUP_DROPPED);
 825                                                 c_insert(l, beginL, rv(root) + begin - matchB,
 826                                                         matchB);
 827                                                 offset += matchB;
 828                                         } else {
 829                                                 /*
 830                                                  * duplicate bytes
 831                                                  */
 832                                                 if (callback)
 833                                                         (*callback) (begin + rb(root) - 1, PARANOIA_CB_FIXUP_DUPED);
 834                                                 c_remove(l, beginL + matchB, -matchB);
 835                                                 offset += matchB;
 836                                         }
 837                                 } else if (matchC) {
 838                                         /*
 839                                          * Uhh... problem with both
 840                                          * Set 'disagree' flags in root
 841                                          */
 842                                         if (rb(root) + begin - matchC < p->root.returnedlimit)
 843                                                 break;
 844                                         c_overwrite(rc(root), begin - matchC,
 845                                                 cv(l) + beginL - matchC, matchC);
 846
 847                                 } else {
 848                                         /*
 849                                          * do we have a mismatch due to silence
 850                                          * beginning/end case?
 851                                          * in the 'chase back' case, we don't
 852                                          * do anything.
 853                                          * Did not determine nature of
 854                                          * difficulty... report and bail
 855                                          */
 856                                         /* RRR(*callback)(post,PARANOIA_CB_XXX); */
 857                                         break;
 858                                 }
 859                                 /*
 860                                  * not the most efficient way, but it will do
 861                                  * for now
 862                                  */
 863                                 beginL = begin + offset;
 864                                 i_paranoia_overlap(rv(root), cv(l),
 865                                         begin, beginL,
 866                                         rs(root), cs(l),
 867                                         &begin, &end);
 868                         }
 869
 870                         /*
 871                          * chase forward
 872                          */
 873                         temp = l ? cs(l) : fs(v);
 874                         while (end + offset < temp && end < rs(root)) {
 875                                 long    matchA = 0,
 876                                         matchB = 0,
 877                                         matchC = 0;
 878                                 long    beginL = begin + offset;
 879                                 long    endL = end + offset;
 880
 881                                 if (l == NULL) {
 882                                         Int16_t *buff = _pmalloc(fs(v) * sizeof (Int16_t));
 883
 884                                         l = c_alloc(buff, fb(v), fs(v));
 885                                         memcpy(buff, fv(v), fs(v) * sizeof (Int16_t));
 886                                 }
 887                                 i_analyze_rift_f(rv(root), cv(l),
 888                                         rs(root), cs(l),
 889                                         end, endL,
 890                                         &matchA, &matchB, &matchC);
 891
 892 #ifdef NOISY
 893                                 fprintf(stderr, "matching rootF: matchA:%ld matchB:%ld matchC:%ld\n",
 894                                         matchA, matchB, matchC);
 895 #endif
 896
 897                                 if (matchA) {
 898                                         /*
 899                                          * a problem with root
 900                                          */
 901                                         if (matchA > 0) {
 902                                                 /*
 903                                                  * dropped bytes; add back from v
 904                                                  */
 905                                                 if (callback)
 906                                                         (*callback) (end + rb(root), PARANOIA_CB_FIXUP_DROPPED);
 907                                                 if (end + rb(root) < p->root.returnedlimit)
 908                                                         break;
 909                                                 c_insert(rc(root), end, cv(l) + endL, matchA);
 910                                         } else {
 911                                                 /*
 912                                                  * duplicate bytes; drop from root
 913                                                  */
 914                                                 if (callback)
 915                                                         (*callback) (end + rb(root), PARANOIA_CB_FIXUP_DUPED);
 916                                                 if (end + rb(root) < p->root.returnedlimit)
 917                                                         break;
 918                                                 c_remove(rc(root), end, -matchA);
 919                                         }
 920                                 } else if (matchB) {
 921                                         /*
 922                                          * a problem with the fragment
 923                                          */
 924                                         if (matchB > 0) {
 925                                                 /*
 926                                                  * dropped bytes
 927                                                  */
 928                                                 if (callback)
 929                                                         (*callback) (end + rb(root), PARANOIA_CB_FIXUP_DROPPED);
 930                                                 c_insert(l, endL, rv(root) + end, matchB);
 931                                         } else {
 932                                                 /*
 933                                                  * duplicate bytes
 934                                                  */
 935                                                 if (callback)
 936                                                         (*callback) (end + rb(root), PARANOIA_CB_FIXUP_DUPED);
 937                                                 c_remove(l, endL, -matchB);
 938                                         }
 939                                 } else if (matchC) {
 940                                         /*
 941                                          * Uhh... problem with both
 942                                          * Set 'disagree' flags in root
 943                                          */
 944                                         if (end + rb(root) < p->root.returnedlimit)
 945                                                 break;
 946                                         c_overwrite(rc(root), end, cv(l) + endL, matchC);
 947                                 } else {
 948                                         analyze_rift_silence_f(rv(root), cv(l),
 949                                                 rs(root), cs(l),
 950                                                 end, endL,
 951                                                 &matchA, &matchB);
 952                                         if (matchA) {
 953                                                 /*
 954                                                  * silence in root
 955                                                  * Can only do this if we haven't
 956                                                  * already returned data
 957                                                  */
 958                                                 if (end + rb(root) >= p->root.returnedlimit) {
 959                                                         c_remove(rc(root), end, -1);
 960                                                 }
 961                                         } else if (matchB) {
 962                                                 /*
 963                                                  * silence in fragment; lose it
 964                                                  */
 965                                                 if (l)
 966                                                         i_cblock_destructor(l);
 967                                                 free_v_fragment(v);
 968                                                 return (1);
 969
 970                                         } else {
 971                                                 /*
 972                                                  * Could not determine nature of
 973                                                  * difficulty... report and bail
 974                                                  */
 975                                                 /* RRR(*callback)(post,PARANOIA_CB_XXX); */
 976                                         }
 977                                         break;
 978                                 }
 979                                 /*
 980                                  * not the most efficient way, but it will do for now
 981                                  */
 982                                 i_paranoia_overlap(rv(root), cv(l),
 983                                         begin, beginL,
 984                                         rs(root), cs(l),
 985                                         (long *)0, &end);
 986                         }
 987
 988                         /*
 989                          * if this extends our range, let's glom
 990                          */
 991                         {
 992                                 long    sizeA = rs(root);
 993                                 long    sizeB;
 994                                 long    vecbegin;
 995                                 Int16_t *vector;
 996
 997                                 if (l) {
 998                                         sizeB = cs(l);
 999                                         vector = cv(l);
1000                                         vecbegin = cb(l);
1001                                 } else {
1002                                         sizeB = fs(v);
1003                                         vector = fv(v);
1004                                         vecbegin = fb(v);
1005                                 }
1006
1007                                 if (sizeB - offset > sizeA || v->lastsector) {
1008                                         if (v->lastsector) {
1009                                                 root->lastsector = 1;
1010                                         }
1011                                         if (end < sizeA)
1012                                                 c_remove(rc(root), end, -1);
1013
1014                                         if (sizeB - offset - end)
1015                                                 c_append(rc(root), vector + end + offset,
1016                                                         sizeB - offset - end);
1017
1018                                         i_silence_test(root);
1019
1020                                         /*
1021                                          * add offset into dynoverlap stats
1022                                          */
1023                                         offset_add_value(p, &p->stage2, offset + vecbegin - rb(root), callback);
1024                                 }
1025                         }
1026                         if (l)
1027                                 i_cblock_destructor(l);
1028                         free_v_fragment(v);
1029                         return (1);
1030
1031                 } else {
1032                         /*
1033                          * D'oh.  No match.  What to do with the fragment?
1034                          */
1035                         if (fe(v) + dynoverlap < re(root) && !root->silenceflag) {
1036                                 /*
1037                                  * It *should* have matched.  No good; free it.
1038                                  */
1039                                 free_v_fragment(v);
1040                         }
1041                         /*
1042                          * otherwise, we likely want this for an upcoming match
1043                          * we don't free the sort info (if it was collected)
1044                          */
1045                         return (0);
1046
1047                 }
1048         }
1049 }
1050
1051 static int
1052 i_init_root(root_block *root, v_fragment *v, long begin,
1053             void (*callback)(long, int))
1054 {
1055         if (fb(v) <= begin && fe(v) > begin) {
1056
1057                 root->lastsector = v->lastsector;
1058                 root->returnedlimit = begin;
1059
1060                 if (rv(root)) {
1061                         i_cblock_destructor(rc(root));
1062                         rc(root) = NULL;
1063                 }
1064                 {
1065                         Int16_t         *buff = _pmalloc(fs(v) * sizeof (Int16_t));
1066
1067                         memcpy(buff, fv(v), fs(v) * sizeof (Int16_t));
1068                         root->vector = c_alloc(buff, fb(v), fs(v));
1069                 }
1070                 i_silence_test(root);
1071
1072                 return (1);
1073         } else
1074                 return (0);
1075 }
1076
1077 static int vsort(const void *a, const void *b)
1078 {
1079         return ((*(v_fragment **) a)->begin - (*(v_fragment **) b)->begin);
1080 }
1081
1082 static int
1083 i_stage2(cdrom_paranoia *p, long beginword, long endword,
1084          void (*callback)(long, int))
1085 {
1086
1087         int             flag = 1;
1088         int             ret = 0;
1089         root_block      *root = &(p->root);
1090
1091 #ifdef NOISY
1092         fprintf(stderr, "Fragments:%ld\n", p->fragments->active);
1093         fflush(stderr);
1094 #endif
1095
1096         /*
1097          * even when the 'silence flag' is lit, we try to do non-silence
1098          * matching in the event that there are still audio vectors with
1099          * content to be sunk before the silence
1100          */
1101         while (flag) {
1102                 /*
1103                  * loop through all the current fragments
1104                  */
1105                 v_fragment      *first = v_first(p);
1106                 long            active = p->fragments->active,
1107                                 count = 0;
1108 #ifdef  HAVE_DYN_ARRAYS
1109                 v_fragment      *list[active];
1110 #else
1111                 v_fragment      **list = _pmalloc(active * sizeof (v_fragment *));
1112 #endif
1113
1114                 while (first) {
1115                         v_fragment      *next = v_next(first);
1116
1117                         list[count++] = first;
1118                         first = next;
1119                 }
1120
1121                 flag = 0;
1122                 if (count) {
1123                         /*
1124                          * sorted in ascending order of beginning
1125                          */
1126                         qsort(list, active, sizeof (v_fragment *), vsort);
1127
1128                         /*
1129                          * we try a nonzero based match even if in silent mode
1130                          * in the case that there are still cached vectors to
1131                          * sink behind continent->ocean boundary
1132                          */
1133                         for (count = 0; count < active; count++) {
1134                                 first = list[count];
1135                                 if (first->one) {
1136                                         if (rv(root) == NULL) {
1137                                                 if (i_init_root(&(p->root), first, beginword, callback)) {
1138                                                         free_v_fragment(first);
1139                                                         flag = 1;
1140                                                         ret++;
1141                                                 }
1142                                         } else {
1143                                                 if (i_stage2_each(root, first, callback)) {
1144                                                         ret++;
1145                                                         flag = 1;
1146                                                 }
1147                                         }
1148                                 }
1149                         }
1150
1151                         /*
1152                          * silence handling
1153                          */
1154                         if (!flag && p->root.silenceflag) {
1155                                 for (count = 0; count < active; count++) {
1156                                         first = list[count];
1157                                         if (first->one) {
1158                                                 if (rv(root) != NULL) {
1159                                                         if (i_silence_match(root, first, callback)) {
1160                                                                 ret++;
1161                                                                 flag = 1;
1162                                                         }
1163                                                 }
1164                                         }
1165                                 }
1166                         }
1167                 }
1168 #ifndef HAVE_DYN_ARRAYS
1169                 _pfree(list);
1170 #endif
1171         }
1172         return (ret);
1173 }
1174
1175 static void
1176 i_end_case(cdrom_paranoia *p, long endword, void (*callback)(long, int))
1177 {
1178
1179         root_block      *root = &p->root;
1180
1181         /*
1182          * have an 'end' flag; if we've just read in the last sector in a
1183          * session, set the flag.  If we verify to the end of a fragment
1184          * which has the end flag set, we're done (set a done flag).
1185          * Pad zeroes to the end of the read
1186          */
1187         if (root->lastsector == 0)
1188                 return;
1189         if (endword < re(root))
1190                 return;
1191
1192         {
1193                 long            addto = endword - re(root);
1194                 char            *temp = _pcalloc(addto, sizeof (char) * 2);
1195
1196                 c_append(rc(root), (void *) temp, addto);
1197                 _pfree(temp);
1198
1199                 /*
1200                  * trash da cache
1201                  */
1202                 paranoia_resetcache(p);
1203
1204         }
1205 }
1206
1207 /*
1208  * We want to add a sector. Look through the caches for something that
1209  * spans.  Also look at the flags on the c_block... if this is an
1210  * obliterated sector, get a bit of a chunk past the obliteration.
1211  *
1212  * Not terribly smart right now, actually.  We can probably find
1213  * *some* match with a cache block somewhere.  Take it and continue it
1214  * through the skip
1215  */
1216 static void
1217 verify_skip_case(cdrom_paranoia *p, void (*callback)(long, int))
1218 {
1219
1220         root_block      *root = &(p->root);
1221         c_block         *graft = NULL;
1222         int             vflag = 0;
1223         int             gend = 0;
1224         long            post;
1225
1226 #ifdef NOISY
1227         fprintf(stderr, "\nskipping\n");
1228 #endif
1229
1230         if (rv(root) == NULL) {
1231                 post = 0;
1232         } else {
1233                 post = re(root);
1234         }
1235         if (post == -1)
1236                 post = 0;
1237
1238         if (callback)
1239                 (*callback) (post, PARANOIA_CB_SKIP);
1240
1241         if (p->enable & PARANOIA_MODE_NEVERSKIP)
1242                 return;
1243
1244         /*
1245          * We want to add a sector.  Look for a c_block that spans,
1246          * preferrably a verified area
1247          */
1248         {
1249                 c_block         *c = c_first(p);
1250
1251                 while (c) {
1252                         long            cbegin = cb(c);
1253                         long            cend = ce(c);
1254
1255                         if (cbegin <= post && cend > post) {
1256                                 long            vend = post;
1257
1258                                 if (c->flags[post - cbegin] & 4) {
1259                                         /*
1260                                          * verified area!
1261                                          */
1262                                         while (vend < cend && (c->flags[vend - cbegin] & 4))
1263                                                 vend++;
1264                                         if (!vflag || vend > vflag) {
1265                                                 graft = c;
1266                                                 gend = vend;
1267                                         }
1268                                         vflag = 1;
1269                                 } else {
1270                                         /*
1271                                          * not a verified area
1272                                          */
1273                                         if (!vflag) {
1274                                                 while (vend < cend && (c->flags[vend - cbegin] & 4) == 0)
1275                                                         vend++;
1276                                                 if (graft == NULL || gend > vend) {
1277                                                         /*
1278                                                          * smallest unverified area
1279                                                          */
1280                                                         graft = c;
1281                                                         gend = vend;
1282                                                 }
1283                                         }
1284                                 }
1285                         }
1286                         c = c_next(c);
1287                 }
1288
1289                 if (graft) {
1290                         long            cbegin = cb(graft);
1291                         long            cend = ce(graft);
1292
1293                         while (gend < cend && (graft->flags[gend - cbegin] & 4))
1294                                 gend++;
1295                         gend = min(gend + OVERLAP_ADJ, cend);
1296
1297                         if (rv(root) == NULL) {
1298                                 Int16_t *buff = _pmalloc(cs(graft));
1299
1300                                 memcpy(buff, cv(graft), cs(graft));
1301                                 rc(root) = c_alloc(buff, cb(graft), cs(graft));
1302                         } else {
1303                                 c_append(rc(root), cv(graft) + post - cbegin,
1304                                         gend - post);
1305                         }
1306
1307                         root->returnedlimit = re(root);
1308                         return;
1309                 }
1310         }
1311
1312         /*
1313          * No?  Fine.  Great.  Write in some zeroes :-P
1314          */
1315         {
1316                 void    *temp = _pcalloc(CD_FRAMESIZE_RAW, sizeof (Int16_t));
1317
1318                 if (rv(root) == NULL) {
1319                         rc(root) = c_alloc(temp, post, CD_FRAMESIZE_RAW);
1320                 } else {
1321                         c_append(rc(root), temp, CD_FRAMESIZE_RAW);
1322                         _pfree(temp);
1323                 }
1324                 root->returnedlimit = re(root);
1325         }
1326 }
1327
1328 /*
1329  * toplevel
1330  */
1331 void paranoia_free(cdrom_paranoia *p)
1332 {
1333         paranoia_resetall(p);
1334         sort_free(p->sortcache);
1335         _pfree(p);
1336 }
1337
1338 void paranoia_modeset(cdrom_paranoia *p, int enable)
1339 {
1340         p->enable = enable;
1341 }
1342
1343 long paranoia_seek(cdrom_paranoia *p, long seek, int mode)
1344 {
1345         long    sector;
1346         long    ret;
1347
1348         switch (mode) {
1349         case SEEK_SET:
1350                 sector = seek;
1351                 break;
1352         case SEEK_END:
1353                 sector = cdda_disc_lastsector(p->d) + seek;
1354                 break;
1355         default:
1356                 sector = p->cursor + seek;
1357                 break;
1358         }
1359
1360         if (cdda_sector_gettrack(p->d, sector) == -1)
1361                 return (-1);
1362
1363         i_cblock_destructor(p->root.vector);
1364         p->root.vector = NULL;
1365         p->root.lastsector = 0;
1366         p->root.returnedlimit = 0;
1367
1368         ret = p->cursor;
1369         p->cursor = sector;
1370
1371         i_paranoia_firstlast(p);
1372
1373         /*
1374          * Evil hack to fix pregap patch for NEC drives! To be rooted out in a10
1375          */
1376         p->current_firstsector = sector;
1377
1378         return (ret);
1379 }
1380
1381 /*
1382  * returns last block read, -1 on error
1383  */
1384 c_block *i_read_c_block(cdrom_paranoia *p, long beginword, long endword,
1385                         void (*callback)(long, int))
1386 {
1387         /*
1388          * why do it this way?  We need to read lots of sectors to kludge
1389          * around stupid read ahead buffers on cheap drives, as well as avoid
1390          * expensive back-seeking. We also want to 'jiggle' the start address
1391          * to try to break borderline drives more noticeably (and make broken
1392          * drives with unaddressable sectors behave more often).
1393          */
1394         long            readat;
1395         long            firstread;
1396         long            totaltoread = p->readahead;
1397         long            sectatonce = p->nsectors;
1398         long            driftcomp = (float) p->dyndrift / CD_FRAMEWORDS + .5;
1399         c_block         *new = NULL;
1400         root_block      *root = &p->root;
1401         Int16_t         *buffer = NULL;
1402         void            *bufbase = NULL;
1403         Uchar           *flags = NULL;
1404         long            sofar;
1405         long            dynoverlap = (p->dynoverlap + CD_FRAMEWORDS - 1) / CD_FRAMEWORDS;
1406         long            anyflag = 0;
1407         int             reduce = 0;
1408 static  int             pagesize = -1;
1409 #define valign(x, a)    (((char *)(x)) + ((a) - 1 - ((((UIntptr_t)(x))-1)%(a))))
1410
1411         /*
1412          * What is the first sector to read?  want some pre-buffer if we're not
1413          * at the extreme beginning of the disc
1414          */
1415         if (p->enable & (PARANOIA_MODE_VERIFY | PARANOIA_MODE_OVERLAP)) {
1416
1417                 /*
1418                  * we want to jitter the read alignment boundary
1419                  */
1420                 long    target;
1421
1422                 if (rv(root) == NULL || rb(root) > beginword)
1423                         target = p->cursor - dynoverlap;
1424                 else
1425                         target = re(root) / (CD_FRAMEWORDS) - dynoverlap;
1426
1427                 if (target + MIN_SECTOR_BACKUP > p->lastread && target <= p->lastread)
1428                         target = p->lastread - MIN_SECTOR_BACKUP;
1429
1430                 /*
1431                  * we want to jitter the read alignment boundary, as some
1432                  * drives, beginning from a specific point, will tend to
1433                  * lose bytes between sectors in the same place.  Also, as
1434                  * our vectors are being made up of multiple reads, we want
1435                  * the overlap boundaries to move....
1436                  */
1437                 readat = (target & (~((long) JIGGLE_MODULO - 1))) + p->jitter;
1438                 if (readat > target)
1439                         readat -= JIGGLE_MODULO;
1440                 p->jitter++;
1441                 if (p->jitter >= JIGGLE_MODULO)
1442                         p->jitter = 0;
1443
1444         } else {
1445                 readat = p->cursor;
1446         }
1447
1448         readat += driftcomp;
1449
1450         if (p->enable & (PARANOIA_MODE_OVERLAP | PARANOIA_MODE_VERIFY)) {
1451                 flags = _pcalloc(totaltoread * CD_FRAMEWORDS, 1);
1452                 new = new_c_block(p);
1453                 recover_cache(p);
1454         } else {
1455                 /*
1456                  * in the case of root it's just the buffer
1457                  */
1458                 paranoia_resetall(p);
1459                 new = new_c_block(p);
1460         }
1461
1462         /*
1463          * Do not use valloc() as valloc() in glibc is buggy and returns memory
1464          * that cannot be passed to free().
1465          */
1466         if (pagesize < 0) {
1467                 pagesize = getpagesize();
1468                 if (pagesize < 0)
1469                         pagesize = 4096;        /* Just a guess */
1470         }
1471         reduce = pagesize / CD_FRAMESIZE_RAW;
1472         bufbase = _pmalloc(totaltoread * CD_FRAMESIZE_RAW + pagesize);
1473         buffer = (Int16_t *)valign(bufbase, pagesize);
1474         sofar = 0;
1475         firstread = -1;
1476
1477         /*
1478          * actual read loop
1479          */
1480         while (sofar < totaltoread) {
1481                 long    secread = sectatonce;
1482                 long    adjread = readat;
1483                 long    thisread;
1484
1485                 /*
1486                  * don't under/overflow the audio session
1487                  */
1488                 if (adjread < p->current_firstsector) {
1489                         secread -= p->current_firstsector - adjread;
1490                         adjread = p->current_firstsector;
1491                 }
1492                 if (adjread + secread - 1 > p->current_lastsector)
1493                         secread = p->current_lastsector - adjread + 1;
1494
1495                 if (sofar + secread > totaltoread)
1496                         secread = totaltoread - sofar;
1497
1498                 /*
1499                  * If we are inside the buffer, the transfers are no longer
1500                  * page aligned. Reduce the transfer size to avoid problems.
1501                  * Such problems are definitely known to appear on FreeBSD.
1502                  */
1503                 if ((sofar > 0) && (secread > (sectatonce - reduce)))
1504                         secread = sectatonce - reduce;
1505
1506                 if (secread > 0) {
1507
1508                         if (firstread < 0)
1509                                 firstread = adjread;
1510                         if ((thisread = cdda_read(p->d, buffer + sofar * CD_FRAMEWORDS, adjread,
1511                                                 secread)) < secread) {
1512
1513                                 if (thisread < 0)
1514                                         thisread = 0;
1515
1516                                 /*
1517                                  * Uhhh... right.  Make something up. But
1518                                  * don't make us seek backward!
1519                                  */
1520                                 if (callback)
1521                                         (*callback) ((adjread + thisread) * CD_FRAMEWORDS, PARANOIA_CB_READERR);
1522                                 memset(buffer + (sofar + thisread) * CD_FRAMEWORDS, 0,
1523                                         CD_FRAMESIZE_RAW * (secread - thisread));
1524                                 if (flags)
1525                                         memset(flags + (sofar + thisread) * CD_FRAMEWORDS, 2,
1526                                                 CD_FRAMEWORDS * (secread - thisread));
1527                         }
1528                         if (thisread != 0)
1529                                 anyflag = 1;
1530
1531                         if (flags && sofar != 0) {
1532                                 /*
1533                                  * Don't verify across overlaps that are too
1534                                  * close to one another
1535                                  */
1536                                 int     i = 0;
1537
1538                                 for (i = -MIN_WORDS_OVERLAP / 2; i < MIN_WORDS_OVERLAP / 2; i++)
1539                                         flags[sofar * CD_FRAMEWORDS + i] |= 1;
1540                         }
1541                         p->lastread = adjread + secread;
1542
1543                         if (adjread + secread - 1 == p->current_lastsector)
1544                                 new->lastsector = -1;
1545
1546                         if (callback)
1547                                 (*callback) ((adjread + secread - 1) * CD_FRAMEWORDS, PARANOIA_CB_READ);
1548
1549                         sofar += secread;
1550                         readat = adjread + secread;
1551                 } else if (readat < p->current_firstsector) {
1552                         readat += sectatonce;
1553                                                 /*
1554                                                  * due to being before the
1555                                                  * readable area
1556                                                  */
1557                 } else {
1558                         break;  /* due to being past the readable area */
1559                 }
1560         }
1561
1562         if (anyflag) {
1563                 new->vector = _pmalloc(totaltoread * CD_FRAMESIZE_RAW);
1564                 memcpy(new->vector, buffer, totaltoread * CD_FRAMESIZE_RAW);
1565                 _pfree(bufbase);
1566
1567                 new->begin = firstread * CD_FRAMEWORDS - p->dyndrift;
1568                 new->size = sofar * CD_FRAMEWORDS;
1569                 new->flags = flags;
1570         } else {
1571                 if (new)
1572                         free_c_block(new);
1573                 if (bufbase)
1574                         _pfree(bufbase);
1575                 if (flags)
1576                         _pfree(flags);
1577                 new = NULL;
1578                 bufbase = NULL;
1579                 flags = NULL;
1580         }
1581         return (new);
1582 }
1583
1584 /*
1585  * The returned buffer is *not* to be freed by the caller.  It will
1586  * persist only until the next call to paranoia_read() for this p
1587  */
1588 Int16_t *paranoia_read(cdrom_paranoia *p, void (*callback)(long, int))
1589 {
1590         return (paranoia_read_limited(p, callback, 20));
1591 }
1592
1593 /*
1594  * I added max_retry functionality this way in order to avoid breaking any
1595  * old apps using the nerw libs.  cdparanoia 9.8 will need the updated libs,
1596  * but nothing else will require it.
1597  */
1598 Int16_t *paranoia_read_limited(cdrom_paranoia *p, void (*callback)(long, int),
1599                                int max_retries)
1600 {
1601         long            beginword = p->cursor * (CD_FRAMEWORDS);
1602         long            endword = beginword + CD_FRAMEWORDS;
1603         long            retry_count = 0;
1604         long            lastend = -2;
1605         root_block      *root = &p->root;
1606
1607         if (beginword > p->root.returnedlimit)
1608                 p->root.returnedlimit = beginword;
1609         lastend = re(root);
1610
1611         /*
1612          * First, is the sector we want already in the root?
1613          */
1614         while (rv(root) == NULL ||
1615                 rb(root) > beginword ||
1616                 (re(root) < endword + p->maxdynoverlap &&
1617                         p->enable & (PARANOIA_MODE_VERIFY | PARANOIA_MODE_OVERLAP)) ||
1618                 re(root) < endword) {
1619
1620                 /*
1621                  * Nope; we need to build or extend the root verified range
1622                  */
1623                 if (p->enable & (PARANOIA_MODE_VERIFY | PARANOIA_MODE_OVERLAP)) {
1624                         i_paranoia_trim(p, beginword, endword);
1625                         recover_cache(p);
1626                         if (rb(root) != -1 && p->root.lastsector)
1627                                 i_end_case(p, endword + p->maxdynoverlap,
1628                                         callback);
1629                         else
1630                                 i_stage2(p, beginword,
1631                                         endword + p->maxdynoverlap,
1632                                         callback);
1633                 } else
1634                         i_end_case(p, endword + p->maxdynoverlap,
1635                                 callback);      /* only trips if we're already */
1636                                                 /* done */
1637
1638                 if (!(rb(root) == -1 || rb(root) > beginword ||
1639                                 re(root) < endword + p->maxdynoverlap))
1640                         break;
1641
1642                 /*
1643                  * Hmm, need more.  Read another block
1644                  */
1645                 {
1646                         c_block *new = i_read_c_block(p, beginword, endword, callback);
1647
1648                         if (new) {
1649                                 if (p->enable & (PARANOIA_MODE_OVERLAP | PARANOIA_MODE_VERIFY)) {
1650
1651                                         if (p->enable & PARANOIA_MODE_VERIFY)
1652                                                 i_stage1(p, new, callback);
1653                                         else {
1654                                                 /*
1655                                                  * just make v_fragments from the
1656                                                  * boundary information.
1657                                                  */
1658                                                 long    begin = 0,
1659                                                         end = 0;
1660
1661                                                 while (begin < cs(new)) {
1662                                                         while (end < cs(new) && (new->flags[begin] & 1))
1663                                                                 begin++;
1664                                                         end = begin + 1;
1665                                                         while (end < cs(new) && (new->flags[end] & 1) == 0)
1666                                                                 end++;
1667                                                         {
1668                                                                 new_v_fragment(p, new, begin + cb(new),
1669                                                                         end + cb(new),
1670                                                                         (new->lastsector && cb(new) + end == ce(new)));
1671                                                         }
1672                                                         begin = end;
1673                                                 }
1674                                         }
1675
1676                                 } else {
1677
1678                                         if (p->root.vector)
1679                                                 i_cblock_destructor(p->root.vector);
1680                                         free_elem(new->e, 0);
1681                                         p->root.vector = new;
1682
1683                                         i_end_case(p, endword + p->maxdynoverlap,
1684                                                 callback);
1685
1686                                 }
1687                         }
1688                 }
1689
1690                 /*
1691                  * Are we doing lots of retries?  **********************
1692                  *
1693                  * Check unaddressable sectors first.  There's no backoff
1694                  * here; jiggle and minimum backseek handle that for us
1695                  */
1696                 if (rb(root) != -1 && lastend + 588 < re(root)) {
1697                         /*
1698                          * If we've not grown half a sector
1699                          */
1700                         lastend = re(root);
1701                         retry_count = 0;
1702                 } else {
1703                         /*
1704                          * increase overlap or bail
1705                          */
1706                         retry_count++;
1707
1708                         /*
1709                          * The better way to do this is to look at how many
1710                          * actual matches we're getting and what kind of gap
1711                          */
1712                         if (retry_count % 5 == 0) {
1713                                 if (p->dynoverlap == p->maxdynoverlap ||
1714                                                 retry_count == max_retries) {
1715                                         verify_skip_case(p, callback);
1716                                         retry_count = 0;
1717                                 } else {
1718                                         if (p->stage1.offpoints != -1) {        /* hack */
1719                                                 p->dynoverlap *= 1.5;
1720                                                 if (p->dynoverlap > p->maxdynoverlap)
1721                                                         p->dynoverlap = p->maxdynoverlap;
1722                                                 if (callback)
1723                                                         (*callback) (p->dynoverlap, PARANOIA_CB_OVERLAP);
1724                                         }
1725                                 }
1726                         }
1727                 }
1728         }
1729         p->cursor++;
1730
1731         return (rv(root) + (beginword - rb(root)));
1732 }
1733
1734 /*
1735  * a temporary hack
1736  */
1737 void paranoia_overlapset(cdrom_paranoia *p, long overlap)
1738 {
1739         p->dynoverlap = overlap * CD_FRAMEWORDS;
1740         p->stage1.offpoints = -1;
1741 }