xueye/cdrtools
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases 1 Wiki Activity
main
cdrtools/libparanoia/paranoia.c

3370 lines
103 KiB
C
Raw Permalink Normal View History

Initial commit
2025-06-15 04:19:58 +08:00
/* @(#)paranoia.c 1.48 15/11/17 J. Schilling from cdparanoia-III-alpha9.8 */
#include <schily/mconfig.h>
#ifndef lint
static UConst char sccsid[] =
"@(#)paranoia.c 1.48 15/11/17 J. Schilling from cdparanoia-III-alpha9.8";
#endif
/*
* CopyPolicy: GNU Lesser General Public License v2.1 applies
* Copyright (C) 1997-2001,2008 by Monty (xiphmont@mit.edu)
* Copyright (C) 2002-2015 by J. Schilling
*
* Toplevel file for the paranoia abstraction over the cdda lib
*
*/
/* immediate todo:: */
/* Allow disabling of root fixups? */
/*
* Dupe bytes are creeping into cases that require greater overlap
* than a single fragment can provide. We need to check against a
* larger area* (+/-32 sectors of root?) to better eliminate
* dupes. Of course this leads to other problems... Is it actually a
* practically solvable problem?
*/
/* Bimodal overlap distributions break us. */
/* scratch detection/tolerance not implemented yet */
/*
* Da new shtick: verification now a two-step assymetric process.
*
* A single 'verified/reconstructed' data segment cache, and then the
* multiple fragment cache
*
* verify a newly read block against previous blocks; do it only this
* once. We maintain a list of 'verified sections' from these matches.
*
* We then glom these verified areas into a new data buffer.
* Defragmentation fixups are allowed here alone.
*
* We also now track where read boundaries actually happened; do not
* verify across matching boundaries.
*/
/*
* Silence. "It's BAAAAAAaaack."
*
* audio is now treated as great continents of values floating on a
* mantle of molten silence. Silence is not handled by basic
* verification at all; we simply anchor sections of nonzero audio to a
* position and fill in everything else as silence. We also note the
* audio that interfaces with silence; an edge must be 'wet'.
*/
/*
* Let's translate the above vivid metaphor into something a mere mortal
* can understand:
*
* Non-silent audio is "solid." Silent audio is "wet" and fluid. The reason
* to treat silence as fluid is that if there's a long enough span of
* silence, we can't reliably detect jitter or dropped samples within that
* span (since all silence looks alike). Non-silent audio, on the other
* hand, is distinctive and can be reliably reassembled.
*
* So we treat long spans of silence specially. We only consider an edge
* of a non-silent region ("continent" or "island") to be "wet" if it borders
* a long span of silence. Short spans of silence are merely damp and can
* be reliably placed within a continent.
*
* We position ("anchor") the non-silent regions somewhat arbitrarily (since
* they may be jittered and we have no way to verify their exact position),
* and fill the intervening space with silence.
*
* See i_silence_match() for the gory details.
*/
#include <schily/alloca.h>
#include <schily/stdlib.h>
#include <schily/unistd.h>
#include <schily/standard.h>
#include <schily/utypes.h>
#include <schily/stdio.h>
#include <schily/string.h>
#include "p_block.h"
#include "cdda_paranoia.h"
#include "overlap.h"
#include "gap.h"
#include "isort.h"
#include "pmalloc.h"
/*
* used by: i_iterate_stage2() / i_stage2_each()
*/
typedef struct sync_result {
long offset;
long begin;
long end;
} sync_result;
struct c2errs {
long c2errs; /* # of reads with C2 errors */
long c2bytes; /* # of bytes with C2 errors */
long c2secs; /* # of sectorss with C2 errors */
long c2maxerrs; /* Max. # of C2 errors per sector */
};
LOCAL inline long re __PR((root_block * root));
LOCAL inline long rb __PR((root_block * root));
LOCAL inline long rs __PR((root_block * root));
LOCAL inline Int16_t *rv __PR((root_block * root));
LOCAL inline long i_paranoia_overlap __PR((Int16_t * buffA, Int16_t * buffB,
long offsetA, long offsetB,
long sizeA, long sizeB,
long *ret_begin, long *ret_end));
LOCAL inline long i_paranoia_overlap2 __PR((Int16_t * buffA, Int16_t * buffB,
Uchar *flagsA, Uchar *flagsB,
long offsetA, long offsetB,
long sizeA, long sizeB,
long *ret_begin, long *ret_end));
LOCAL inline long do_const_sync __PR((c_block * A,
sort_info * B, Uchar *flagB,
long posA, long posB,
long *begin, long *end, long *offset));
LOCAL inline long try_sort_sync __PR((cdrom_paranoia * p,
sort_info * A, Uchar *Aflags,
c_block * B,
long post, long *begin, long *end,
long *offset, void (*callback) (long, int)));
LOCAL inline void stage1_matched __PR((c_block * old, c_block * new,
long matchbegin, long matchend,
long matchoffset, void (*callback) (long, int)));
LOCAL long i_iterate_stage1 __PR((cdrom_paranoia * p, c_block * old, c_block * new,
void (*callback) (long, int)));
LOCAL long i_stage1 __PR((cdrom_paranoia * p, c_block * new,
void (*callback) (long, int)));
LOCAL long i_iterate_stage2 __PR((cdrom_paranoia * p, v_fragment * v,
sync_result * r, void (*callback) (long, int)));
LOCAL void i_silence_test __PR((root_block * root));
LOCAL long i_silence_match __PR((root_block * root, v_fragment * v,
void (*callback) (long, int)));
LOCAL long i_stage2_each __PR((root_block * root, v_fragment * v,
void (*callback) (long, int)));
LOCAL int i_init_root __PR((root_block * root, v_fragment * v, long begin,
void (*callback) (long, int)));
LOCAL int vsort __PR((const void *a, const void *b));
LOCAL int i_stage2 __PR((cdrom_paranoia * p, long beginword, long endword,
void (*callback) (long, int)));
LOCAL void i_end_case __PR((cdrom_paranoia * p, long endword,
void (*callback) (long, int)));
LOCAL void verify_skip_case __PR((cdrom_paranoia * p, void (*callback) (long, int)));
EXPORT void paranoia_free __PR((cdrom_paranoia * p));
EXPORT void paranoia_modeset __PR((cdrom_paranoia * p, int enable));
EXPORT long paranoia_seek __PR((cdrom_paranoia * p, long seek, int mode));
LOCAL void c2_audiocopy __PR((void *to, void *from, int nsectors));
LOCAL int bits __PR((int c));
LOCAL void c2_errcopy __PR((void *to, void *from, int nsectors, struct c2errs *errp));
c_block *i_read_c_block __PR((cdrom_paranoia * p, long beginword, long endword,
void (*callback) (long, int)));
EXPORT Int16_t *paranoia_read __PR((cdrom_paranoia * p, void (*callback) (long, int)));
EXPORT Int16_t *paranoia_read_limited __PR((cdrom_paranoia * p, void (*callback) (long, int),
int max_retries));
EXPORT void paranoia_overlapset __PR((cdrom_paranoia * p, long overlap));
/*
* Return end offset of current block.
* End offset counts in multiples of samples (16 bits).
*/
LOCAL inline long
re(root)
root_block *root;
{
if (!root)
return (-1);
if (!root->vector)
return (-1);
return (ce(root->vector));
}
/*
* Return begin offset of current block.
* Begin offset counts in multiples of samples (16 bits).
*/
LOCAL inline long
rb(root)
root_block *root;
{
if (!root)
return (-1);
if (!root->vector)
return (-1);
return (cb(root->vector));
}
/*
* Return size of current block.
* Size counts in multiples of samples (16 bits).
*/
LOCAL inline long
rs(root)
root_block *root;
{
if (!root)
return (-1);
if (!root->vector)
return (-1);
return (cs(root->vector));
}
/*
* Return data vector from current block.
*/
LOCAL inline Int16_t *
rv(root)
root_block *root;
{
if (!root)
return (NULL);
if (!root->vector)
return (NULL);
return (cv(root->vector));
}
#define rc(r) ((r)->vector)
/*
* Flags indicating the status of a read samples.
*
* Imagine the below enumeration values are #defines to be used in a
* bitmask rather than distinct values of an enum.
*
* The variable part of the declaration is trickery to force the enum
* symbol values to be recorded in debug symbol tables. They are used
* to allow one refer to the enumeration value names in a debugger
* and in debugger expressions.
*/
#define FLAGS_EDGE 0x1 /**< first/last N words of frame */
#define FLAGS_UNREAD 0x2 /**< unread, hence missing and unmatchable */
#define FLAGS_VERIFIED 0x4 /**< block read and verified */
#define FLAGS_C2 0x8 /**< sample with C2 error */
/*
* matching and analysis code
*/
/*
* i_paranoia_overlap() (internal)
*
* This function is called when buffA[offsetA] == buffB[offsetB]. This
* function searches backward and forward to see how many consecutive
* samples also match.
*
* This function is called by do_const_sync() when we're not doing any
* verification. Its more complicated sibling is i_paranoia_overlap2.
*
* This function returns the number of consecutive matching samples.
* If (ret_begin) or (ret_end) are not NULL, it fills them with the
* offsets of the first and last matching samples in A.
*/
LOCAL inline long
i_paranoia_overlap(buffA, buffB, offsetA, offsetB, sizeA, sizeB, ret_begin, ret_end)
Int16_t *buffA;
Int16_t *buffB;
long offsetA;
long offsetB;
long sizeA;
long sizeB;
long *ret_begin;
long *ret_end;
{
long beginA = offsetA;
long endA = offsetA;
long beginB = offsetB;
long endB = offsetB;
/*
* Scan backward to extend the matching run in that direction.
*/
for (; beginA >= 0 && beginB >= 0; beginA--, beginB--)
if (buffA[beginA] != buffB[beginB])
break;
beginA++;
beginB++;
/*
* Scan forward to extend the matching run in that direction.
*/
for (; endA < sizeA && endB < sizeB; endA++, endB++)
if (buffA[endA] != buffB[endB])
break;
/*
* Return the result of our search.
*/
if (ret_begin)
*ret_begin = beginA;
if (ret_end)
*ret_end = endA;
return (endA - beginA);
}
/*
* i_paranoia_overlap2() (internal)
*
* This function is called when buffA[offsetA] == buffB[offsetB]. This
* function searches backward and forward to see how many consecutive
* samples also match.
*
* This function is called by do_const_sync() when we're verifying the
* data coming off the CD. Its less complicated sibling is
* i_paranoia_overlap, which is a good place to look to see the simplest
* outline of how this function works.
*
* This function returns the number of consecutive matching samples.
* If (ret_begin) or (ret_end) are not NULL, it fills them with the
* offsets of the first and last matching samples in A.
*/
LOCAL inline long
i_paranoia_overlap2(buffA, buffB, flagsA, flagsB, offsetA, offsetB, sizeA, sizeB, ret_begin, ret_end)
Int16_t *buffA;
Int16_t *buffB;
Uchar *flagsA;
Uchar *flagsB;
long offsetA;
long offsetB;
long sizeA;
long sizeB;
long *ret_begin;
long *ret_end;
{
long beginA = offsetA;
long endA = offsetA;
long beginB = offsetB;
long endB = offsetB;
/*
* Scan backward to extend the matching run in that direction.
*/
for (; beginA >= 0 && beginB >= 0; beginA--, beginB--) {
if (buffA[beginA] != buffB[beginB])
break;
/*
* don't allow matching across matching sector boundaries. The
* liklihood of the drive skipping identically in two
* different reads with the same sector read boundary is actually
* relatively very high compared to the liklihood of it skipping
* when one read is continuous across the boundary and other was
* discontinuous.
* Stop if both samples were at the edges of a low-level read.
*/
if ((flagsA[beginA] & flagsB[beginB] & FLAGS_EDGE)) {
beginA--;
beginB--;
break;
}
/*
* don't allow matching through known missing data
*/
if ((flagsA[beginA] & FLAGS_UNREAD) || (flagsB[beginB] & FLAGS_UNREAD))
break;
}
beginA++;
beginB++;
/*
* Scan forward to extend the matching run in that direction.
*/
for (; endA < sizeA && endB < sizeB; endA++, endB++) {
if (buffA[endA] != buffB[endB])
break;
/*
* don't allow matching across matching sector boundaries
*/
if ((flagsA[endA] & flagsB[endB] & FLAGS_EDGE) && endA != beginA) {
break;
}
/*
* don't allow matching through known missing data
* Stop if both samples were at the edges of a low-level read.
*/
if ((flagsA[endA] & FLAGS_UNREAD) || (flagsB[endB] & FLAGS_UNREAD))
break;
}
/*
* Return the result of our search.
*/
if (ret_begin)
*ret_begin = beginA;
if (ret_end)
*ret_end = endA;
return (endA - beginA);
}
/*
* do_const_sync() (internal)
*
* This function is called when samples A[posA] == B[posB]. It tries to
* build a matching run from that point, looking forward and backward to
* see how many consecutive samples match. Since the starting samples
* might only be coincidentally identical, we only consider the run to
* be a true match if it's longer than MIN_WORDS_SEARCH.
*
* This function returns the length of the run if a matching run was found,
* or 0 otherwise. If a matching run was found, (begin) and (end) are set
* to the absolute positions of the beginning and ending samples of the
* run in A, and (offset) is set to the jitter between the c_blocks.
* (I.e., offset indicates the distance between what A considers sample N
* on the CD and what B considers sample N.)
*/
LOCAL inline long
do_const_sync(A, B, flagB, posA, posB, begin, end, offset)
c_block *A;
sort_info *B;
Uchar *flagB;
long posA;
long posB;
long *begin;
long *end;
long *offset;
{
Uchar *flagA = A->flags;
long ret = 0;
/*
* If we're doing any verification whatsoever, we have flags in stage
* 1, and will take them into account. Otherwise (e.g. in stage 2),
* we just do the simple equality test for samples on both sides of
* the initial match.
*/
if (flagB == NULL)
ret = i_paranoia_overlap(cv(A), iv(B), posA, posB,
cs(A), is(B), begin, end);
else if ((flagB[posB] & FLAGS_UNREAD) == 0)
ret = i_paranoia_overlap2(cv(A), iv(B), flagA, flagB, posA, posB, cs(A),
is(B), begin, end);
/*
* Small matching runs could just be coincidental. We only consider this
* a real match if it's long enough.
*/
if (ret > MIN_WORDS_SEARCH) {
*offset = (posA + cb(A)) - (posB + ib(B));
/*
* Note that try_sort_sync()'s swaps A & B when it calls this function,
* so while we adjust begin & end to be relative to A here, that means
* it's relative to B in try_sort_sync().
*/
*begin += cb(A);
*end += cb(A);
return (ret);
}
return (0);
}
/*
* try_sort_sync() (internal)
*
* Starting from the sample in B with the absolute position (post), look
* for a matching run in A. This search will look in A for a first
* matching sample within (p->dynoverlap) samples around (post). If it
* finds one, it will then determine how many consecutive samples match
* both A and B from that point, looking backwards and forwards. If
* this search produces a matching run longer than MIN_WORDS_SEARCH, we
* consider it a match.
*
* When used by stage 1, the "post" is planted with respect to the old
* c_block being compare to the new c_block. In stage 2, the "post" is
* planted with respect to the verified root.
*
* This function returns 1 if a match is found and 0 if not. When a match
* is found, (begin) and (end) are set to the boundaries of the run, and
* (offset) is set to the difference in position of the run in A and B.
* (begin) and (end) are the absolute positions of the samples in
* B. (offset) transforms A to B's frame of reference. I.e., an offset of
* 2 would mean that A's absolute 3 is equivalent to B's 5.
*
* post is w.r.t. B. in stage one, we post from old. In stage 2 we
* post from root. Begin, end, offset count from B's frame of
* reference
*/
LOCAL inline long
try_sort_sync(p, A, Aflags, B, post, begin, end, offset, callback)
cdrom_paranoia *p;
sort_info *A;
Uchar *Aflags;
c_block *B;
long post;
long *begin;
long *end;
long *offset;
void (*callback) __PR((long, int));
{
long dynoverlap = p->dynoverlap;
sort_link *ptr = NULL;
Uchar *Bflags = B->flags;
/*
* block flag matches FLAGS_UNREAD (unmatchable)
*/
if (Bflags == NULL || (Bflags[post - cb(B)] & FLAGS_UNREAD) == 0) {
/*
* always try absolute offset zero first!
*/
{
long zeropos = post - ib(A);
if (zeropos >= 0 && zeropos < is(A)) {
/*
* Before we bother with the search for a matching samples,
* we check the simple case. If there's no jitter at all
* (i.e. the absolute positions of A's and B's samples are
* consistent), A's sample at (post) should be identical
* to B's sample at the same position.
*/
if (cv(B)[post - cb(B)] == iv(A)[zeropos]) {
/*
* The first sample matched, now try to grow the matching run
* in both directions. We only consider it a match if more
* than MIN_WORDS_SEARCH consecutive samples match.
*/
if (do_const_sync(B, A, Aflags,
post - cb(B), zeropos,
begin, end, offset)) {
offset_add_value(p, &(p->stage1), *offset, callback);
return (1);
}
}
}
}
} else
return (0);
/*
* If the samples with the same absolute position didn't match, it's
* either a bad sample, or the two c_blocks are jittered with respect
* to each other. Now we search through A for samples that do have
* the same value as B's post. The search looks from first to last
* occurrence witin (dynoverlap) samples of (post).
*/
ptr = sort_getmatch(A, post - ib(A), dynoverlap, cv(B)[post - cb(B)]);
while (ptr) {
/*
* We've found a matching sample, so try to grow the matching run in
* both directions. If we find a long enough run (longer than
* MIN_WORDS_SEARCH), we've found a match.
*/
if (do_const_sync(B, A, Aflags,
post - cb(B), ipos(A, ptr),
begin, end, offset)) {
offset_add_value(p, &(p->stage1), *offset, callback);
return (1);
}
/*
* The matching sample was just a fluke -- there weren't enough adjacent
* samples that matched to consider a matching run. So now we check
* for the next occurrence of that value in A.
*/
ptr = sort_nextmatch(A, ptr);
}
/*
* We didn't find any matches.
*/
*begin = -1;
*end = -1;
*offset = -1;
return (0);
}
/*
* STAGE 1 MATCHING
*/
/* Top level of the first stage matcher */
/*
* We match each analysis point of new to the preexisting blocks
* recursively. We can also optionally maintain a list of fragments of
* the preexisting block that didn't match anything, and match them back
* afterward.
*/
#define OVERLAP_ADJ (MIN_WORDS_OVERLAP/2-1)
/*
* stage1_matched() (internal)
*
* This function is called whenever stage 1 verification finds two identical
* runs of samples from different reads. The runs must be more than
* MIN_WORDS_SEARCH samples long. They may be jittered (i.e. their absolute
* positions on the CD may not match due to inaccurate seeking) with respect
* to each other, but they have been verified to have no dropped samples
* within them.
*
* This function provides feedback via the callback mechanism and marks the
* runs as verified. The details of the marking are somehwat subtle and
* are described near the relevant code.
*
* Subsequent portions of the stage 1 code will build a verified fragment
* from this run. The verified fragment will eventually be merged
* into the verified root (and its absolute position determined) in
* stage 2.
*/
LOCAL inline void
stage1_matched(old, new, matchbegin, matchend, matchoffset, callback)
c_block *old;
c_block *new;
long matchbegin;
long matchend;
long matchoffset;
void (*callback) __PR((long, int));
{
long i;
long oldadjbegin = matchbegin - cb(old);
long oldadjend = matchend - cb(old);
long newadjbegin = matchbegin - matchoffset - cb(new);
long newadjend = matchend - matchoffset - cb(new);
/*
* Provide feedback via the callback about the samples we've just
* verified.
*
* "???: How can matchbegin ever be < cb(old)?"
* Sorry, old bulletproofing habit. I often use <= to mean "not >"
* --Monty
*
* "???: Why do edge samples get logged only when there's jitter
* between the matched runs (matchoffset != 0)?"
* FIXUP_EDGE is actually logging a jitter event, not a rift--
* a rift is FIXUP_ATOM --Monty
*/
if (matchbegin - matchoffset <= cb(new) ||
matchbegin <= cb(old) ||
(new->flags[newadjbegin] & FLAGS_EDGE) ||
(old->flags[oldadjbegin] & FLAGS_EDGE)) {
if (matchoffset)
if (callback)
(*callback) (matchbegin, PARANOIA_CB_FIXUP_EDGE);
} else if (callback)
(*callback) (matchbegin, PARANOIA_CB_FIXUP_ATOM);
if (matchend - matchoffset >= ce(new) ||
(new->flags[newadjend] & FLAGS_EDGE) ||
matchend >= ce(old) ||
(old->flags[oldadjend] & FLAGS_EDGE)) {
if (matchoffset)
if (callback)
(*callback) (matchend, PARANOIA_CB_FIXUP_EDGE);
} else if (callback)
(*callback) (matchend, PARANOIA_CB_FIXUP_ATOM);
/* BEGIN CSTYLED */
/*
* Mark verified samples as "verified," but trim the verified region
* by OVERLAP_ADJ samples on each side. There are several significant
* implications of this trimming:
*
* 1) Why we trim at all: We have to trim to distinguish between two
* adjacent verified runs and one long verified run. We encounter this
* situation when samples have been dropped:
*
* matched portion of read 1 ....)(.... matched portion of read 1
* read 2 adjacent run .....)(..... read 2 adjacent run
* ||
* dropped samples in read 2
*
* So at this point, the fact that we have two adjacent runs means
* that we have not yet verified that the two runs really are adjacent.
* (In fact, just the opposite: there are two runs because they were
* matched by separate runs, indicating that some samples didn't match
* across the length of read 2.)
*
* If we verify that they are actually adjacent (e.g. if the two runs
* are simply a result of matching runs from different reads, not from
* dropped samples), we will indeed mark them as one long merged run.
*
* 2) Why we trim by this amount: We want to ensure that when we
* verify the relationship between these two runs, we do so with
* an overlapping fragment at least OVERLAP samples long. Following
* from the above example:
*
* (..... matched portion of read 3 .....)
* read 2 adjacent run .....)(..... read 2 adjacent run
*
* Assuming there were no dropped samples between the adjacent runs,
* the matching portion of read 3 will need to be at least OVERLAP
* samples long to mark the two runs as one long verified run.
* If there were dropped samples, read 3 wouldn't match across the
* two runs, proving our caution worthwhile.
*
* 3) Why we partially discard the work we've done: We don't.
* When subsequently creating verified fragments from this run,
* we compensate for this trimming. Thus the verified fragment will
* contain the full length of verified samples. Only the c_blocks
* will reflect this trimming.
*
* Mark the verification flags. Don't mark the first or last OVERLAP/2
* elements so that overlapping fragments have to overlap by OVERLAP to
* actually merge. We also remove elements from the sort such that
* later sorts do not have to sift through already matched data
*/
/* END CSTYLED */
newadjbegin += OVERLAP_ADJ;
newadjend -= OVERLAP_ADJ;
for (i = newadjbegin; i < newadjend; i++)
new->flags[i] |= FLAGS_VERIFIED; /* mark verified */
oldadjbegin += OVERLAP_ADJ;
oldadjend -= OVERLAP_ADJ;
for (i = oldadjbegin; i < oldadjend; i++)
old->flags[i] |= FLAGS_VERIFIED; /* mark verified */
}
#define CB_NULL (void (*) __PR((long, int)))0
/*
* i_iterate_stage1 (internal)
*
* This function is called by i_stage1() to compare newly read samples with
* previously read samples, searching for contiguous runs of identical
* samples. Matching runs indicate that at least two reads of the CD
* returned identical data, with no dropped samples in that run.
* The runs may be jittered (i.e. their absolute positions on the CD may
* not be accurate due to inaccurate seeking) at this point. Their
* positions will be determined in stage 2.
*
* This function compares the new c_block (which has been indexed in
* p->sortcache) to a previous c_block. It is called for each previous
* c_block. It searches for runs of identical samples longer than
* MIN_WORDS_SEARCH. Samples in matched runs are marked as verified.
*
* Subsequent stage 1 code builds verified fragments from the runs of
* verified samples. These fragments are merged into the verified root
* in stage 2.
*
* This function returns the number of distinct runs verified in the new
* c_block when compared against this old c_block.
*/
LOCAL long
i_iterate_stage1(p, old, new, callback)
cdrom_paranoia *p;
c_block *old;
c_block *new;
void (*callback) __PR((long, int));
{
long matchbegin = -1;
long matchend = -1;
long matchoffset;
/*
* "???: Why do we limit our search only to the samples with overlapping
* absolute positions? It could be because it eliminates some further
* bounds checking."
* Short answer is yes --Monty
*
* "Why do we "no longer try to spread the ... search" as mentioned
* below?"
* The search is normally much faster without the spread,
* even in heavy jitter. Dynoverlap tends to be a bigger deal in
* stage 2. --Monty
*/
/*
* we no longer try to spread the stage one search area by dynoverlap
*/
long searchend = min(ce(old), ce(new));
long searchbegin = max(cb(old), cb(new));
long searchsize = searchend - searchbegin;
sort_info *i = p->sortcache;
long ret = 0;
long j;
long tried = 0;
long matched = 0;
if (searchsize <= 0)
return (0);
/*
* match return values are in terms of the new vector, not old
* "???: Why 23?" Odd, prime number --Monty
*/
for (j = searchbegin; j < searchend; j += 23) {
/*
* Skip past any samples verified in previous comparisons to
* other old c_blocks. Also, obviously, don't bother verifying
* unread/unmatchable samples.
*/
if ((new->flags[j - cb(new)] & (FLAGS_VERIFIED|FLAGS_UNREAD)) == 0) {
tried++;
/*
* Starting from the sample in the old c_block with the absolute
* position j, look for a matching run in the new c_block. This
* search will look a certain distance around j, and if successful
* will extend the matching run as far backward and forward as
* it can.
*
* The search will only return 1 if it finds a matching run long
* enough to be deemed significant.
*/
if (try_sort_sync(p, i, new->flags, old, j, &matchbegin, &matchend, &matchoffset,
callback) == 1) {
matched += matchend - matchbegin;
/*
* purely cosmetic: if we're matching zeros,
* don't use the callback because they will
* appear to be all skewed
*/
{
long jj = matchbegin - cb(old);
long end = matchend - cb(old);
for (; jj < end; jj++)
if (cv(old)[jj] != 0)
break;
/*
* Mark the matched samples in both c_blocks as verified.
* In reality, not all the samples are marked. See
* stage1_matched() for details.
*/
if (jj < end) {
stage1_matched(old, new, matchbegin, matchend, matchoffset, callback);
} else {
stage1_matched(old, new, matchbegin, matchend, matchoffset, CB_NULL);
}
}
ret++;
/*
* Skip past this verified run to look for more matches.
*/
if (matchend - 1 > j)
j = matchend - 1;
}
}
}
#ifdef NOISY
fprintf(stderr, "iterate_stage1: search area=%ld[%ld-%ld] tried=%ld matched=%ld spans=%ld\n",
searchsize, searchbegin, searchend, tried, matched, ret);
#endif
return (ret);
}
/*
* i_stage1() (internal)
*
* Compare newly read samples against previously read samples, searching
* for contiguous runs of identical samples. Matching runs indicate that
* at least two reads of the CD returned identical data, with no dropped
* samples in that run. The runs may be jittered (i.e. their absolute
* positions on the CD may not be accurate due to inaccurate seeking) at
* this point. Their positions will be determined in stage 2.
*
* This function compares a new c_block against all other c_blocks in memory,
* searching for sufficiently long runs of identical samples. Since each
* c_block represents a separate call to read_c_block, this ensures that
* multiple reads have returned identical data. (Additionally, read_c_block
* varies the reads so that multiple reads are unlikely to produce identical
* errors, so any matches between reads are considered verified. See
* i_read_c_block for more details.)
*
* Each time we find such a run (longer than MIN_WORDS_SEARCH), we mark
* the samples as "verified" in both c_blocks. Runs of verified samples in
* the new c_block are promoted into verified fragments, which will later
* be merged into the verified root in stage 2.
*
* In reality, not all the verified samples are marked as "verified."
* See stage1_matched() for an explanation.
*
* This function returns the number of verified fragments created by the
* stage 1 matching.
*/
LOCAL long
i_stage1(p, new, callback)
cdrom_paranoia *p;
c_block *new;
void (*callback) __PR((long, int));
{
long size = cs(new);
c_block *ptr = c_last(p);
int ret = 0;
long begin = 0;
long end;
/*
* We're going to be comparing the new c_block against the other
* c_blocks in memory. Initialize the "sort cache" index to allow
* for fast searching through the new c_block. (The index will
* actually be built the first time we search.)
*/
if (ptr)
sort_setup(p->sortcache, cv(new), &cb(new), cs(new),
cb(new), ce(new));
/*
* Iterate from oldest to newest c_block, comparing the new c_block
* to each, looking for a sufficiently long run of identical samples
* (longer than MIN_WORDS_SEARCH), which will be marked as "verified"
* in both c_blocks.
*
* Since the new c_block is already in the list (at the head), don't
* compare it against itself.
*/
while (ptr && ptr != new) {
if (callback)
(*callback) (cb(new), PARANOIA_CB_VERIFY);
i_iterate_stage1(p, ptr, new, callback);
ptr = c_prev(ptr);
}
/*
* parse the verified areas of new into v_fragments
*
* Find each run of contiguous verified samples in the new c_block
* and create a verified fragment from each run.
*/
begin = 0;
while (begin < size) {
for (; begin < size; begin++)
if (new->flags[begin] & FLAGS_VERIFIED)
break;
for (end = begin; end < size; end++)
if ((new->flags[end] & FLAGS_VERIFIED) == 0)
break;
if (begin >= size)
break;
ret++;
/*
* We create a new verified fragment from the contiguous run
* of verified samples.
*
* We expand the "verified" range by OVERLAP_ADJ on each side
* to compensate for trimming done to the verified range by
* stage1_matched(). The samples were actually verified, and
* hence belong in the verified fragment. See stage1_matched()
* for an explanation of the trimming.
*/
new_v_fragment(p, new, cb(new) + max(0, begin - OVERLAP_ADJ),
cb(new) + min(size, end + OVERLAP_ADJ),
(end + OVERLAP_ADJ >= size && new->lastsector));
begin = end;
}
/*
* Return the number of distinct verified fragments we found with
* stage 1 matching.
*/
return (ret);
}
/*
* STAGE 2 MATCHING
*/
/*
* reconcile v_fragments to root buffer. Free if matched, fragment/fixup root
* if necessary
*
* do *not* match using zero posts
*/
/*
* i_iterate_stage2 (internal)
*
* This function searches for a sufficiently long run of identical samples
* between the passed verified fragment and the verified root. The search
* is similar to that performed by i_iterate_stage1. Of course, what we do
* as a result of a match is different.
*
* Our search is slightly different in that we refuse to match silence to
* silence. All silence looks alike, and it would result in too many false
* positives here, so we handle silence separately.
*
* Also, because we're trying to determine whether this fragment as a whole
* overlaps with the root at all, we narrow our search (since it should match
* immediately or not at all). This is in contrast to stage 1, where we
* search the entire vector looking for all possible matches.
*
* This function returns 0 if no match was found (including failure to find
* one due to silence), or 1 if we found a match.
*
* When a match is found, the sync_result_t is set to the boundaries of
* matching run (begin/end, in terms of the root) and how far out of sync
* the fragment is from the canonical root (offset). Note that this offset
* is opposite in sign from the notion of offset used by try_sort_sync()
* and stage 1 generally.
*/
LOCAL long
i_iterate_stage2(p, v, r, callback)
cdrom_paranoia *p;
v_fragment *v;
sync_result *r;
void (*callback) __PR((long, int));
{
root_block *root = &(p->root);
long matchbegin = -1;
long matchend = -1;
long offset;
long fbv;
long fev;
#ifdef NOISY
fprintf(stderr, "Stage 2 search: fbv=%ld fev=%ld\n", fb(v), fe(v));
#endif
/*
* Quickly check whether there could possibly be any overlap between
* the verified fragment and the root. Our search will allow up to
* (p->dynoverlap) jitter between the two, so we expand the fragment
* search area by p->dynoverlap on both sides and see if that expanded
* area overlaps with the root.
*
* We could just as easily expand root's boundaries by p->dynoverlap
* instead and achieve the same result.
*/
if (min(fe(v) + p->dynoverlap, re(root)) -
max(fb(v) - p->dynoverlap, rb(root)) <= 0)
return (0);
if (callback)
(*callback) (fb(v), PARANOIA_CB_VERIFY);
/*
* We're going to try to match the fragment to the root while allowing
* for p->dynoverlap jitter, so we'll actually be looking at samples
* in the fragment whose position claims to be up to p->dynoverlap
* outside the boundaries of the root. But, of course, don't extend
* past the edges of the fragment.
*/
fbv = max(fb(v), rb(root) - p->dynoverlap);
/*
* Skip past leading zeroes in the fragment, and bail if there's nothing
* but silence. We handle silence later separately.
*/
while (fbv < fe(v) && fv(v)[fbv - fb(v)] == 0)
fbv++;
if (fbv == fe(v))
return (0);
/*
* This is basically the same idea as the initial calculation for fbv
* above. Look at samples up to p->dynoverlap outside the boundaries
* of the root, but don't extend past the edges of the fragment.
*
* However, we also limit the search to no more than 256 samples.
* Unlike stage 1, we're not trying to find all possible matches within
* two runs -- rather, we're trying to see if the fragment as a whole
* overlaps with the root. If we can't find a match within 256 samples,
* there's probably no match to be found (because this fragment doesn't
* overlap with the root).
*
* "??? Is this why? Why 256?" 256 is simply a 'large enough number'. --Monty
*/
fev = min(min(fbv + 256, re(root) + p->dynoverlap), fe(v));
{
/*
* Because we'll allow for up to (p->dynoverlap) jitter between the
* fragment and the root, we expand the search area (fbv to fev) by
* p->dynoverlap on both sides. But, because we're iterating through
* root, we need to constrain the search area not to extend beyond
* the root's boundaries.
*/
long searchend = min(fev + p->dynoverlap, re(root));
long searchbegin = max(fbv - p->dynoverlap, rb(root));
sort_info *i = p->sortcache;
long j;
/*
* Initialize the "sort cache" index to allow for fast searching
* through the verified fragment between (fbv,fev). (The index will
* actually be built the first time we search.)
*/
sort_setup(i, fv(v), &fb(v), fs(v), fbv, fev);
for (j = searchbegin; j < searchend; j += 23) {
/*
* Skip past silence in the root. If there are just a few silent
* samples, the effect is minimal. The real reason we need this is
* for large regions of silence. All silence looks alike, so you
* could false-positive "match" two runs of silence that are either
* unrelated or ought to be jittered, and try_sort_sync can't
* accurately determine jitter (offset) from silence.
*
* Therefore, we want to post on a non-zero sample. If there's
* nothing but silence left in the root, bail. We don't want
* to match it here.
*/
while (j < searchend && rv(root)[j - rb(root)] == 0)
j++;
if (j == searchend)
break;
/*
* Starting from the (non-zero) sample in the root with the absolute
* position j, look for a matching run in the verified fragment. This
* search will look a certain distance around j, and if successful
* will extend the matching run as far backward and forward as
* it can.
*
* The search will only return 1 if it finds a matching run long
* enough to be deemed significant. Note that the search is limited
* by the boundaries given to sort_setup() above.
*
* Note also that flags aren't used in stage 2 (since neither verified
* fragments nor the root have them).
*/
if (try_sort_sync(p, i, (Uchar *)0, rc(root), j,
&matchbegin, &matchend, &offset, callback)) {
/*
* If we found a matching run, we return the results of our match.
*
* Note that we flip the sign of (offset) because try_sort_sync()
* returns it in terms of the fragment (i.e. what we add
* to the fragment's position to yield the corresponding position
* in the root), but here we consider the root to be canonical,
* and so our returned "offset" reflects how the fragment is offset
* from the root.
*
* E.g.: If the fragment's sample 10 corresponds to root's 12,
* try_sort_sync() would return 2. But since root is canonical,
* we say that the fragment is off by -2.
*/
r->begin = matchbegin;
r->end = matchend;
r->offset = -offset;
if (offset)
if (callback)
(*callback) (r->begin, PARANOIA_CB_FIXUP_EDGE);
return (1);
}
}
}
return (0);
}
/*
* i_silence_test() (internal)
*
* If the entire root is silent, or there's enough trailing silence
* to be significant (MIN_SILENCE_BOUNDARY samples), mark the beginning
* of the silence and "light" the silence flag. This flag will remain lit
* until i_silence_match() appends some non-silent samples to the root.
*
* We do this because if there's a long enough span of silence, we can't
* reliably detect jitter or dropped samples within that span. See
* i_silence_match() for details on how we recover from this situation.
*/
LOCAL void
i_silence_test(root)
root_block *root;
{
Int16_t *vec = rv(root);
long end = re(root) - rb(root) - 1;
long j;
/*
* Look backward from the end of the root to find the first non-silent
* sample.
*/
for (j = end - 1; j >= 0; j--)
if (vec[j] != 0)
break;
/*
* If the entire root is silent, or there's enough trailing silence
* to be significant, mark the beginning of the silence and "light"
* the silence flag.
*/
if (j < 0 || end - j > MIN_SILENCE_BOUNDARY) {
if (j < 0)
j = 0;
root->silenceflag = 1;
root->silencebegin = rb(root) + j;
if (root->silencebegin < root->returnedlimit)
root->silencebegin = root->returnedlimit;
}
}
/*
* i_silence_match() (internal)
*
* This function is merges verified fragments into the verified root in cases
* where there is a problematic amount of silence (MIN_SILENCE_BOUNDARY
* samples) at the end of the root.
*
* We need a special approach because if there's a long enough span of
* silence, we can't reliably detect jitter or dropped samples within that
* span (since all silence looks alike).
*
* Only fragments that begin with MIN_SILENCE_BOUNDARY samples are eligible
* to be merged in this case. Fragments that are too far beyond the edge
* of the root to possibly overlap are also disregarded.
*
* Our first approach is to assume that such fragments have no jitter (since
* we can't establish otherwise) and merge them. However, if it's clear
* that there must be jitter (i.e. because non-silent samples overlap when
* we assume no jitter), we assume the fragment has the minimum possible
* jitter and then merge it.
*
* This function extends silence fairly aggressively, so it must be called
* with fragments in ascending order (beginning position) in case there are
* small non-silent regions within the silence.
*/
LOCAL long
i_silence_match(root, v, callback)
root_block *root;
v_fragment *v;
void (*callback) __PR((long, int));
{
cdrom_paranoia *p = v->p;
Int16_t *vec = fv(v);
long end = fs(v);
long begin;
long j;
/*
* See how much leading silence this fragment has. If there are fewer than
* MIN_SILENCE_BOUNDARY leading silent samples, we don't do this special
* silence matching.
*
* This fragment could actually belong here, but we can't be sure unless
* it has enough silence on its leading edge. This fragment will likely
* stick around until we do successfully extend the root, at which point
* it will be merged using the usual method.
*/
if (end < MIN_SILENCE_BOUNDARY)
return (0);
for (j = 0; j < end; j++)
if (vec[j] != 0)
break;
if (j < MIN_SILENCE_BOUNDARY)
return (0);
/*
* Convert the offset of the first non-silent sample to an absolute
* position. For the time being, we will assume that this position
* is accurate, with no jitter.
*/
j += fb(v);
/*
* If this fragment is ahead of the root, see if that could just be due
* to jitter (if it's within p->dynoverlap samples of the end of root).
*/
if (fb(v) >= re(root) && fb(v) - p->dynoverlap < re(root)) {
/*
* This fragment is within jitter range of the root, so we extend the
* root's silence so that it overlaps with this fragment. At this point
* we know that the fragment has at least MIN_SILENCE_BOUNDARY silent
* samples at the beginning, so we overlap by that amount.
*
* XXX dynarrays are not needed here.
*/
long addto = fb(v) + MIN_SILENCE_BOUNDARY - re(root);
#ifdef HAVE_DYN_ARRAYS
Int16_t avec[addto];
#else
#ifdef HAVE_ALLOCA
Int16_t *avec = alloca(addto * sizeof (Int16_t));
#else
Int16_t *avec = _pmalloc(addto * sizeof (Int16_t));
#endif
#endif
memset(avec, 0, addto * sizeof (Int16_t));
c_append(rc(root), avec, addto);
#ifndef HAVE_DYN_ARRAYS
#ifndef HAVE_ALLOCA
_pfree(avec);
#endif
#endif
}
/*
* Calculate the overlap of the root's trailing silence and the fragment's
* leading silence. (begin,end) are the boundaries of that overlap.
*/
begin = max(fb(v), root->silencebegin);
end = min(j, re(root));
/*
* If there is an overlap, we assume that both the root and the fragment
* are jitter-free (since there's no way for us to tell otherwise).
*/
if (begin < end) {
/*
* If the fragment will extend the root, then we append it to the root.
* Otherwise, no merging is necessary, as the fragment should already
* be contained within the root.
*/
if (fe(v) > re(root)) {
long voff = begin - fb(v);
/*
* Truncate the overlapping silence from the end of the root.
*/
c_remove(rc(root), begin - rb(root), -1);
/*
* Append the fragment to the root, starting from the point of overlap.
*/
c_append(rc(root), vec + voff, fs(v) - voff);
}
/*
* Record the fact that we merged this fragment assuming zero jitter.
*/
offset_add_value(p, &p->stage2, 0, callback);
} else {
/*
* We weren't able to merge the fragment assuming zero jitter.
*
* Check whether the fragment's leading silence ends before the root's
* trailing silence begins. If it does, we assume that the root is
* jittered forward.
*/
if (j < begin) {
/*
* We're going to append the non-silent samples of the fragment
* to the root where its silence begins.
*
* "??? This seems to be a very strange approach. At this point
* the root has a lot of trailing silence, and the fragment has
* the lot of leading silence. This merge will drop the silence
* and just splice the non-silence together.
*
* In theory, rift analysis will either confirm or fix this result.
* What circumstances motivated this approach?"
*
* This is an 'all bets are off' situation and we choose to make
* the best guess we can, based on absolute position being
* returned by the most recent reads. There are drives that
* will randomly lose what they're doing during a read and just
* pad out the results with zeros and return no error. This at
* least has a shot of addressing that situation. --Monty
*
* Compute the amount of silence at the beginning of the fragment.
*/
long voff = j - fb(v);
/*
* If attaching the non-silent tail of the fragment to the end
* of the non-silent portion of the root will extend the root,
* then we'll append the samples to the root. Otherwise, no
* merging is necessary, as the fragment should already be contained
* within the root.
*/
if (begin + fs(v) - voff > re(root)) {
/*
* Truncate the trailing silence from the root.
*/
c_remove(rc(root), root->silencebegin - rb(root), -1);
/*
* Append the non-silent tail of the fragment to the root.
*/
c_append(rc(root), vec + voff, fs(v) - voff);
}
/*
* Record the fact that we merged this fragment assuming (end-begin)
* jitter.
*/
offset_add_value(p, &p->stage2, end - begin, callback);
} else {
/*
* We only get here if the fragment is past the end of the root,
* which means it must be farther than (dynoverlap) away, due to our
* root extension above.
*
* We weren't able to merge this fragment into the root after all.
*/
return (0);
}
}
/*
* We only get here if we merged the fragment into the root. Update
* the root's silence flag.
*
* Note that this is the only place silenceflag is reset. In other words,
* once i_silence_test() lights the silence flag, it can only be reset
* by i_silence_match().
*/
root->silenceflag = 0;
/*
* Now see if the new, extended root ends in silence.
*/
i_silence_test(root);
/*
* Since we merged the fragment, we can free it now. But first we propagate
* its lastsector flag.
*/
if (v->lastsector)
root->lastsector = 1;
free_v_fragment(v);
return (1);
}
/*
* i_stage2_each (internal)
*
* This function (which is entirely too long) attempts to merge the passed
* verified fragment into the verified root.
*
* First this function looks for a run of identical samples between
* the root and the fragment. If it finds a long enough run, it then
* checks for "rifts" (see below) and fixes the root and/or fragment as
* necessary. Finally, if the fragment will extend the tail of the root,
* we merge the fragment and extend the root.
*
* Most of the ugliness in this function has to do with handling "rifts",
* which are points of disagreement between the root and the verified
* fragment. This can happen when a drive consistently drops a few samples
* or stutters and repeats a few samples. It has to be consistent enough
* to result in a verified fragment (i.e. it happens twice), but inconsistent
* enough (e.g. due to the jiggled reads) not to happen every time.
*
* This function returns 1 if the fragment was successfully merged into the
* root, and 0 if not.
*/
LOCAL long
i_stage2_each(root, v, callback)
root_block *root;
v_fragment *v;
void (*callback) __PR((long, int));
{
cdrom_paranoia *p;
long dynoverlap;
/*
* If this fragment has already been merged & freed, abort.
*/
if (!v || !v->one)
return (0);
p = v->p;
/*
* "??? Why do we round down to an even dynoverlap?" Dynoverlap is
* in samples, not stereo frames --Monty
*/
dynoverlap = p->dynoverlap / 2 * 2;
/*
* If there's no verified root yet, abort.
*/
if (!rv(root)) {
return (0);
} else {
sync_result r;
/*
* Search for a sufficiently long run of identical samples between
* the verified fragment and the verified root. There's a little
* bit of subtlety in the search when silence is involved.
*/
if (i_iterate_stage2(p, v, &r, callback)) {
/*
* Convert the results of the search to be relative to the root.
*/
long begin = r.begin - rb(root);
long end = r.end - rb(root);
/*
* Convert offset into a value that will transform a relative
* position in the root to the corresponding relative position in
* the fragment. I.e., if offset = -2, then the sample at relative
* position 2 in the root is at relative position 0 in the fragment.
*
* While a bit opaque, this does reduce the number of calculations
* below.
*/
long offset = r.begin + r.offset - fb(v) - begin;
long temp;
c_block *l = NULL;
/*
* we have a match! We don't rematch off rift, we chase
* the match all the way to both extremes doing rift
* analysis.
*/
#ifdef NOISY
fprintf(stderr, "Stage 2 match\n");
#endif
/*
* Convert offset into a value that will transform a relative
* position in the root to the corresponding relative position in
* the fragment. I.e., if offset = -2, then the sample at relative
* position 2 in the root is at relative position 0 in the fragment.
*
* While a bit opaque, this does reduce the number of calculations
* below.
*/
/*
* Now that we've found a sufficiently long run of identical samples
* between the fragment and the root, we need to check for rifts.
*
* A "rift", as mentioned above, is a disagreement between the
* fragment and the root. When there's a rift, the matching run
* found by i_iterate_stage2() will obviously stop where the root
* and the fragment disagree.
*
* So we detect rifts by checking whether the matching run extends
* to the ends of the fragment and root. If the run does extend to
* the ends of the fragment and root, then all overlapping samples
* agreed, and there's no rift. If, however, the matching run
* stops with samples left over in both the root and the fragment,
* that means the root and fragment disagreed at that point.
* Leftover samples at the beginning of the match indicate a
* leading rift, and leftover samples at the end of the match indicate
* a trailing rift.
*
* Once we detect a rift, we attempt to fix it, depending on the
* nature of the disagreement. See i_analyze_rift_[rf] for details
* on how we determine what kind of rift it is. See below for
* how we attempt to fix the rifts.
*/
/*
* First, check for a leading rift, fix it if possible, and then
* extend the match forward until either we hit the limit of the
* overlapping samples, or until we encounter another leading rift.
* Keep doing this until we hit the beginning of the overlap.
*
* Note that while we do fix up leading rifts, we don't extend
* the root backward (earlier samples) -- only forward (later
* samples).
*/
/*
* If the beginning of the match didn't reach the beginning of
* either the fragment or the root, we have a leading rift to be
* examined.
*
* Remember that (begin) is the offset into the root, and (begin+offset)
* is the equivalent offset into the fragment. If neither one is at
* zero, then they both have samples before the match, and hence a
* rift.
*/
while ((begin + offset > 0 && begin > 0)) {
long matchA = 0,
matchB = 0,
matchC = 0;
/*
* (begin) is the offset into the root of the first matching sample,
* (beginL) is the offset into the fragment of the first matching
* sample. These samples are at the edge of the rift.
*/
long beginL = begin + offset;
/*
* The first time we encounter a leading rift, allocate a
* scratch copy of the verified fragment which we'll use if
* we need to fix up the fragment before merging it into
* the root.
*/
if (l == NULL) {
Int16_t *buff = _pmalloc(fs(v) * sizeof (Int16_t));
l = c_alloc(buff, fb(v), fs(v));
memcpy(buff, fv(v), fs(v) * sizeof (Int16_t));
}
/* BEGIN CSTYLED */
/*
* Starting at the first mismatching sample, see how far back the
* rift goes, and determine what kind of rift it is. Note that
* we're searching through the fixed up copy of the fragment.
*
* matchA > 0 if there are samples missing from the root
* matchA < 0 if there are duplicate samples (stuttering) in the root
* matchB > 0 if there are samples missing from the fragment
* matchB < 0 if there are duplicate samples in the fragment
* matchC != 0 if there's a section of garbage, after which
* the fragment and root agree and are in sync
*/
/* END CSTYLED */
i_analyze_rift_r(rv(root), cv(l),
rs(root), cs(l),
begin - 1, beginL - 1,
&matchA, &matchB, &matchC);
#ifdef NOISY
fprintf(stderr, "matching rootR: matchA:%ld matchB:%ld matchC:%ld\n",
matchA, matchB, matchC);
#endif
/*
* "??? The root.returnedlimit checks below are presently a mystery."
* Those are for the case where our backtracking wants to take
* us to back before bytes we've already returned to the
* application. In short, it's a "we're screwed"
* check. --Monty
*/
if (matchA) {
/*
* There's a problem with the root
*/
if (matchA > 0) {
/*
* There were (matchA) samples dropped from the root. We'll add
* them back from the fixed up fragment.
*/
if (callback)
(*callback) (begin + rb(root) - 1, PARANOIA_CB_FIXUP_DROPPED);
if (rb(root) + begin < p->root.returnedlimit)
break;
else {
/*
* At the edge of the rift in the root, insert the missing
* samples from the fixed up fragment. They're the (matchA)
* samples immediately preceding the edge of the rift in the
* fragment.
*/
c_insert(rc(root), begin, cv(l) + beginL - matchA,
matchA);
/*
* We just inserted (matchA) samples into the root, so update
* our begin/end offsets accordingly. Also adjust the
* (offset) to compensate (since we use it to find samples in
* the fragment, and the fragment hasn't changed).
*/
offset -= matchA;
begin += matchA;
end += matchA;
}
} else {
/*
* There were (-matchA) duplicate samples (stuttering) in the
* root. We'll drop them.
*/
if (callback)
(*callback) (begin + rb(root) - 1, PARANOIA_CB_FIXUP_DUPED);
if (rb(root) + begin + matchA < p->root.returnedlimit)
break;
else {
/*
* Remove the (-matchA) samples immediately preceding the
* edge of the rift in the root.
*/
c_remove(rc(root), begin + matchA, -matchA);
/*
* We just removed (-matchA) samples from the root, so update
* our begin/end offsets accordingly. Also adjust the offset
* to compensate. Remember that matchA < 0, so we're actually
* subtracting from begin/end.
*/
offset -= matchA;
begin += matchA;
end += matchA;
}
}
} else if (matchB) {
/*
* There's a problem with the fragment
*/
if (matchB > 0) {
/*
* There were (matchB) samples dropped from the fragment. We'll
* add them back from the root.
*/
if (callback)
(*callback) (begin + rb(root) - 1, PARANOIA_CB_FIXUP_DROPPED);
/*
* At the edge of the rift in the fragment, insert the missing
* samples from the root. They're the (matchB) samples
* immediately preceding the edge of the rift in the root.
* Note that we're fixing up the scratch copy of the fragment.
*/
c_insert(l, beginL, rv(root) + begin - matchB,
matchB);
/*
* We just inserted (matchB) samples into the fixed up fragment,
* so update (offset), since we use it to find samples in the
* fragment based on the root's unchanged offsets.
*/
offset += matchB;
} else {
/*
* There were (-matchB) duplicate samples (stuttering) in the
* fixed up fragment. We'll drop them.
*/
if (callback)
(*callback) (begin + rb(root) - 1, PARANOIA_CB_FIXUP_DUPED);
/*
* Remove the (-matchB) samples immediately preceding the edge
* of the rift in the fixed up fragment.
*/
c_remove(l, beginL + matchB, -matchB);
/*
* We just removed (-matchB) samples from the fixed up fragment,
* so update (offset), since we use it to find samples in the
* fragment based on the root's unchanged offsets.
*/
offset += matchB;
}
} else if (matchC) {
/*
* There are (matchC) samples that simply disagree between the
* fragment and the root. On the other side of the mismatch, the
* fragment and root agree again. We can't classify the mismatch
* as either a stutter or dropped samples, and we have no way of
* telling whether the fragment or the root is right.
*
* "The original comment indicated that we set "disagree"
* flags in the root, but it seems to be historical." The
* disagree flags were from a time when we did interpolation
* over samples we simply couldn't get to agree. Yes,
* historical functionality that didn;t work well. --Monty
*/
if (rb(root) + begin - matchC < p->root.returnedlimit)
break;
/*
* Overwrite the mismatching (matchC) samples in root with the
* samples from the fixed up fragment.
*
* "??? Do we think the fragment is more likely correct, is this
* just arbitrary, or is there some other reason for overwriting
* the root?"
* We think these samples are more likely to be correct --Monty
*/
c_overwrite(rc(root), begin - matchC,
cv(l) + beginL - matchC, matchC);
} else {
/*
* We may have had a mismatch because we ran into leading silence.
*
* "??? To be studied: why would this cause a mismatch?
* Neither i_analyze_rift_r nor i_iterate_stage2() nor
* i_paranoia_overlap() appear to take silence into
* consideration in this regard. It could be due to our
* skipping of silence when searching for a match." Jitter
* and or skipping in sections of silence could end up with
* two sets of verified vectors that agree completely except
* for the length of the silence. Silence is a huge bugaboo
* in general because there's no entropy within it to base
* verification on. --Monty
*
* Since we don't extend the root in that direction, we don't
* do anything, just move on to trailing rifts.
*/
/*
* If the rift was too complex to fix (see i_analyze_rift_r),
* we just stop and leave the leading edge where it is.
*/
/* RRR(*callback)(post,PARANOIA_CB_XXX); */
break;
}
/*
* Recalculate the offset of the edge of the rift in the fixed
* up fragment, in case it changed.
*
* "??? Why is this done here rather than in the (matchB) case above,
* which should be the only time beginL will change."
* Because there's no reason not to? --Monty
*/
beginL = begin + offset;
/*
* Now that we've fixed up the root or fragment as necessary, see
* how far we can extend the matching run. This function is
* overkill, as it tries to extend the matching run in both
* directions (and rematches what we already matched), but it works.
*/
i_paranoia_overlap(rv(root), cv(l),
begin, beginL,
rs(root), cs(l),
&begin, &end);
}
/*
* Second, check for a trailing rift, fix it if possible, and then
* extend the match forward until either we hit the limit of the
* overlapping samples, or until we encounter another trailing rift.
* Keep doing this until we hit the end of the overlap.
*
* If the end of the match didn't reach the end of either the fragment
* or the root, we have a trailing rift to be examined.
*
* Remember that (end) is the offset into the root, and (end+offset)
* is the equivalent offset into the fragment. If neither one is
* at the end of the vector, then they both have samples after the
* match, and hence a rift.
*
* (temp) is the size of the (potentially fixed-up) fragment. If
* there was a leading rift, (l) is the fixed up fragment, and
* (offset) is now relative to it.
*/
temp = l ? cs(l) : fs(v);
while (end + offset < temp && end < rs(root)) {
long matchA = 0,
matchB = 0,
matchC = 0;
/*
* (begin) is the offset into the root of the first matching sample,
* (beginL) is the offset into the fragment of the first matching
* sample. We know these samples match and will use these offsets
* later when we try to extend the matching run.
*/
long beginL = begin + offset;
/*
* (end) is the offset into the root of the first mismatching sample
* after the matching run, (endL) is the offset into the fragment of
* the equivalent sample. These samples are at the edge of the rift.
*/
long endL = end + offset;
/*
* The first time we encounter a rift, allocate a scratch copy of
* the verified fragment which we'll use if we need to fix up the
* fragment before merging it into the root.
*
* Note that if there was a leading rift, we'll already have
* this (potentially fixed-up) scratch copy allocated.
*/
if (l == NULL) {
Int16_t *buff = _pmalloc(fs(v) * sizeof (Int16_t));
l = c_alloc(buff, fb(v), fs(v));
memcpy(buff, fv(v), fs(v) * sizeof (Int16_t));
}
/* BEGIN CSTYLED */
/*
* Starting at the first mismatching sample, see how far forward the
* rift goes, and determine what kind of rift it is. Note that we're
* searching through the fixed up copy of the fragment.
*
* matchA > 0 if there are samples missing from the root
* matchA < 0 if there are duplicate samples (stuttering) in the root
* matchB > 0 if there are samples missing from the fragment
* matchB < 0 if there are duplicate samples in the fragment
* matchC != 0 if there's a section of garbage, after which
* the fragment and root agree and are in sync
*/
/* END CSTYLED */
i_analyze_rift_f(rv(root), cv(l),
rs(root), cs(l),
end, endL,
&matchA, &matchB, &matchC);
#ifdef NOISY
fprintf(stderr, "matching rootF: matchA:%ld matchB:%ld matchC:%ld\n",
matchA, matchB, matchC);
#endif
if (matchA) {
/*
* There's a problem with the root
*/
if (matchA > 0) {
/*
* There were (matchA) samples dropped from the root. We'll add
* them back from the fixed up fragment.
*/
if (callback)
(*callback) (end + rb(root), PARANOIA_CB_FIXUP_DROPPED);
if (end + rb(root) < p->root.returnedlimit)
break;
/*
* At the edge of the rift in the root, insert the missing
* samples from the fixed up fragment. They're the (matchA)
* samples immediately preceding the edge of the rift in the
* fragment.
*/
c_insert(rc(root), end, cv(l) + endL, matchA);
/*
* Although we just inserted samples into the root, we did so
* after (begin) and (end), so we needn't update those offsets.
*/
} else {
/*
* There were (-matchA) duplicate samples (stuttering) in the
* root. We'll drop them.
*/
if (callback)
(*callback) (end + rb(root), PARANOIA_CB_FIXUP_DUPED);
if (end + rb(root) < p->root.returnedlimit)
break;
/*
* Remove the (-matchA) samples immediately following the edge
* of the rift in the root.
*/
c_remove(rc(root), end, -matchA);
/*
* Although we just removed samples from the root, we did so
* after (begin) and (end), so we needn't update those offsets.
*/
}
} else if (matchB) {
/*
* There's a problem with the fragment
*/
if (matchB > 0) {
/*
* There were (matchB) samples dropped from the fragment. We'll
* add them back from the root.
*/
if (callback)
(*callback) (end + rb(root), PARANOIA_CB_FIXUP_DROPPED);
/*
* At the edge of the rift in the fragment, insert the missing
* samples from the root. They're the (matchB) samples
* immediately following the dge of the rift in the root.
* Note that we're fixing up the scratch copy of the fragment.
*/
c_insert(l, endL, rv(root) + end, matchB);
/*
* Although we just inserted samples into the fragment, we did so
* after (begin) and (end), so (offset) hasn't changed either.
*/
} else {
/*
* There were (-matchB) duplicate samples (stuttering) in thea
* fixed up fragment. We'll drop them.
*/
if (callback)
(*callback) (end + rb(root), PARANOIA_CB_FIXUP_DUPED);
/*
* Remove the (-matchB) samples immediately following the edge
* of the rift in the fixed up fragment.
*/
c_remove(l, endL, -matchB);
/*
* Although we just removed samples from the fragment, we did so
* after (begin) and (end), so (offset) hasn't changed either.
*/
}
} else if (matchC) {
/*
* There are (matchC) samples that simply disagree between the
* fragment and the root. On the other side of the mismatch, the
* fragment and root agree again. We can't classify the mismatch
* as either a stutter or dropped samples, and we have no way of
* telling whether the fragment or the root is right.
*
* The original comment indicated that we set "disagree" flags
* in the root, but it seems to be historical.
*/
if (end + rb(root) < p->root.returnedlimit)
break;
/*
* Overwrite the mismatching (matchC) samples in root with the
* samples from the fixed up fragment.
*/
c_overwrite(rc(root), end, cv(l) + endL, matchC);
} else {
/*
* We may have had a mismatch because we ran into trailing silence.
*
* At this point we have a trailing rift. We check whether
* one of the vectors (fragment or root) has trailing silence.
*/
analyze_rift_silence_f(rv(root), cv(l),
rs(root), cs(l),
end, endL,
&matchA, &matchB);
if (matchA) {
/*
* The contents of the root's trailing rift are silence. The
* fragment's are not (otherwise there wouldn't be a rift).
* We therefore assume that the root has garbage from this
* point forward and truncate it.
*
* This will have the effect of eliminating the trailing
* rift, causing the fragment's samples to be appended to
* the root.
*
* Can only do this if we haven't
* already returned data
*/
if (end + rb(root) >= p->root.returnedlimit) {
c_remove(rc(root), end, -1);
}
} else if (matchB) {
/*
* The contents of the fragment's trailing rift are silence.
* The root's are not (otherwise there wouldn't be a rift).
* We therefore assume that the fragment has garbage from this
* point forward.
*
* We needn't actually truncate the fragment, because the root
* has already been fixed up from this fragment as much as
* possible, and the truncated fragment wouldn't extend the
* root. Therefore, we can consider this (truncated) fragment
* to be already merged into the root. So we dispose of it and
* return a success.
*/
if (l)
i_cblock_destructor(l);
free_v_fragment(v);
return (1);
} else {
/*
* If the rift was too complex to fix (see i_analyze_rift_f),
* we just stop and leave the trailing edge where it is.
*/
/* RRR(*callback)(post,PARANOIA_CB_XXX); */
}
break;
}
/*
* Now that we've fixed up the root or fragment as necessary, see
* how far we can extend the matching run. This function is
* overkill, as it tries to extend the matching run in both
* directions (and rematches what we already matched), but it works.
*/
i_paranoia_overlap(rv(root), cv(l),
begin, beginL,
rs(root), cs(l),
(long *)0, &end);
}
/*
* Third and finally, if the overlapping verified fragment extends
* our range forward (later samples), we append ("glom") the new
* samples to the end of the root.
*
* Note that while we did fix up leading rifts, we don't extend
* the root backward (earlier samples) -- only forward (later
* samples).
*
* This is generally fine, since the verified root is supposed to
* slide from earlier samples to later samples across multiple calls
* to paranoia_read().
*
* "??? But, is this actually right? Because of this, we don't
* extend the root to hold the earliest read sample, if we
* happened to initialize the root with a later sample due to
* jitter. There are probably some ugly side effects from
* extending the root backward, in the general case, but it may
* not be so dire if we're near sample 0. To be investigated."
* In the begin case, any start position is arbitrary due to
* inexact seeking. Later, we can't back-extend the root as the
* samples preceeding the beginning have already been returned
* to the application! --Monty
*/
{
long sizeA = rs(root);
long sizeB;
long vecbegin;
Int16_t *vector;
/*
* If there were any rifts, we'll use the fixed up fragment (l),
* otherwise, we use the original fragment (v).
*/
if (l) {
sizeB = cs(l);
vector = cv(l);
vecbegin = cb(l);
} else {
sizeB = fs(v);
vector = fv(v);
vecbegin = fb(v);
}
/*
* Convert the fragment-relative offset (sizeB) into an offset
* relative to the root (A), and see if the offset is past the
* end of the root (> sizeA). If it is, this fragment will extend
* our root.
*
* "??? Why do we check for v->lastsector separately?" Because
* of the case where root extends *too* far; if we never get a
* read that accidentally extends that far again, we could
* hang and loop forever. --Monty
*/
if (sizeB - offset > sizeA || v->lastsector) {
if (v->lastsector) {
root->lastsector = 1;
}
/*
* "??? Why would end be < sizeA? Why do we truncate root?"
* Because it can happen (seeking is very very inexact) and
* end of disk tends to be very problematic in terms of
* stopping point. We also generally believe more recent
* information over previous information when they disagree
* and both are 'verified'. --Monty
*/
if (end < sizeA)
c_remove(rc(root), end, -1);
/*
* Extend the root with the samples from the end of the
* (potentially fixed up) fragment.
*/
if (sizeB - offset - end)
c_append(rc(root), vector + end + offset,
sizeB - offset - end);
/*
* Any time we update the root we need to check whether it ends
* with a large span of silence.
*/
i_silence_test(root);
/*
* Add the dynoverlap offset into our stage 2 statistics.
*
* Note that we convert our peculiar offset (which is in terms of
* the relative positions of samples within each vector) back into
* the actual offset between what A considers sample N and what B
* considers sample N.
*
* We do this at the end of rift handling because any original
* offset returned by i_iterate_stage2() might have been due to
* dropped or duplicated samples. Once we've fixed up the root
* and the fragment, we have an offset which more reliably
* indicates jitter.
*/
offset_add_value(p, &p->stage2, offset + vecbegin - rb(root), callback);
}
}
if (l)
i_cblock_destructor(l);
free_v_fragment(v);
return (1);
} else {
/*
* We were unable to merge this fragment into the root.
*
* Check whether the fragment should have overlapped with the root,
* even taking possible jitter into account. (I.e., If the fragment
* ends so far before the end of the root that even (dynoverlap)
* samples of jitter couldn't push it beyond the end of the root,
* it should have overlapped.)
*
* It is, however, possible that we failed to match using the normal
* tests because we're dealing with silence, which we handle
* separately.
*
* If the fragment should have overlapped, and we're not dealing
* with the special silence case, we don't know what to make of
* this fragment, and we just discard it.
*/
if (fe(v) + dynoverlap < re(root) && !root->silenceflag) {
/*
* It *should* have matched. No good; free it.
*/
free_v_fragment(v);
}
/*
* otherwise, we likely want this for an upcoming match
* we don't free the sort info (if it was collected)
*/
return (0);
}
}
}
LOCAL int
i_init_root(root, v, begin, callback)
root_block *root;
v_fragment *v;
long begin;
void (*callback) __PR((long, int));
{
if (fb(v) <= begin && fe(v) > begin) {
root->lastsector = v->lastsector;
root->returnedlimit = begin;
if (rv(root)) {
i_cblock_destructor(rc(root));
rc(root) = NULL;
}
{
Int16_t *buff = _pmalloc(fs(v) * sizeof (Int16_t));
memcpy(buff, fv(v), fs(v) * sizeof (Int16_t));
root->vector = c_alloc(buff, fb(v), fs(v));
}
/*
* Check whether the new root has a long span of trailing silence.
*/
i_silence_test(root);
return (1);
} else
return (0);
}
LOCAL int
vsort(a, b)
const void *a;
const void *b;
{
return ((*(v_fragment **) a)->begin - (*(v_fragment **) b)->begin);
}
/*
* i_stage2 (internal)
*
* This function attempts to extend the verified root by merging verified
* fragments into it. It keeps extending the tail end of the root until
* it runs out of matching fragments. See i_stage2_each (and
* i_iterate_stage2) for details of fragment matching and merging.
*
* This function is called by paranoia_read_limited when the verified root
* doesn't contain sufficient data to satisfy the request for samples.
* If this function fails to extend the verified root far enough (having
* exhausted the currently available verified fragments), the caller
* will then read the device again to try and establish more verified
* fragments.
*
* We first try to merge all the fragments in ascending order using the
* standard method (i_stage2_each()), and then we try to merge the
* remaining fragments using silence matching (i_silence_match())
* if the root has a long span of trailing silence. See the initial
* comments on silence and i_silence_match() for an explanation of this
* distinction.
*
* This function returns the number of verified fragments successfully
* merged into the verified root.
*/
LOCAL int
i_stage2(p, beginword, endword, callback)
cdrom_paranoia *p;
long beginword;
long endword;
void (*callback) __PR((long, int));
{
int flag = 1;
int ret = 0;
root_block *root = &(p->root);
#ifdef NOISY
fprintf(stderr, "Fragments:%ld\n", p->fragments->active);
fflush(stderr);
#endif
/*
* even when the 'silence flag' is lit, we try to do non-silence
* matching in the event that there are still audio vectors with
* content to be sunk before the silence
*/
/*
* This flag is not the silence flag. Rather, it indicates whether
* we succeeded in adding a verified fragment to the verified root.
* In short, we keep adding fragments until we no longer find a
* match.
*/
while (flag) {
/*
* Convert the linked list of verified fragments into an array,
* to be sorted in order of beginning sample position
*/
v_fragment *first = v_first(p);
long active = p->fragments->active,
count = 0;
#ifdef HAVE_DYN_ARRAYS
v_fragment *list[active];
#else
v_fragment **list = _pmalloc(active * sizeof (v_fragment *));
#endif
while (first) {
v_fragment *next = v_next(first);
list[count++] = first;
first = next;
}
/*
* Reset the flag so that if we don't match any fragments, we
* stop looping. Then, proceed only if there are any fragments
* to match.
*/
flag = 0;
if (count) {
/*
* Sort the array of verified fragments in order of beginning
* sample position.
*/
qsort(list, active, sizeof (v_fragment *), vsort);
/*
* We don't check for the silence flag yet, because even if the
* verified root ends in silence (and thus the silence flag is set),
* there may be a non-silent region at the beginning of the verified
* root, into which we can merge the verified fragments.
*
* Iterate through the verified fragments, starting at the fragment
* with the lowest beginning sample position.
*/
for (count = 0; count < active; count++) {
first = list[count];
/*
* Make sure this fragment hasn't already been merged (and
* thus freed).
*/
if (first->one) {
/*
* If we don't have a verified root yet, just promote the first
* fragment (with lowest beginning sample) to be the verified
* root.
*
* "??? It seems that this could be fairly arbitrary if jitter
* is an issue. If we've verified two fragments allegedly
* beginning at "0" (which are actually slightly offset due to
* jitter), the root might not begin at the earliest read
* sample. Additionally, because subsequent fragments are
* only merged at the tail end of the root, this situation
* won't be fixed by merging the earlier samples.
*
* Practically, this ends up not being critical since most
* drives insert some extra silent samples at the beginning
* of the stream. Missing a few of them doesn't cause any
* real lost data. But it is non-deterministic."
*
* On such a drive, the entire act of CDDA read is highly
* nondeterministic. All redbook says is +/- 75 sectors.
* If you insist on the earliest possible sample, you can
* get into a situation where the first read was far earlier
* than all the others and no other read ever repeats the
* early positioning. --Monty
*/
if (rv(root) == NULL) {
if (i_init_root(&(p->root), first, beginword, callback)) {
free_v_fragment(first);
/*
* Consider this a merged fragment, so set the flag
* to keep looping.
*/
flag = 1;
ret++;
}
} else {
/*
* Try to merge this fragment with the verified root,
* extending the tail of the root.
*/
if (i_stage2_each(root, first, callback)) {
/*
* If we successfully merged the fragment, set the flag
* to keep looping.
*/
ret++;
flag = 1;
}
}
}
}
/*
* silence handling
*
* If the verified root ends in a long span of silence, iterate
* through the remaining unmerged fragments to see if they can be
* merged using our special silence matching.
*/
if (!flag && p->root.silenceflag) {
for (count = 0; count < active; count++) {
first = list[count];
/*
* Make sure this fragment hasn't already been merged (and
* thus freed).
*/
if (first->one) {
if (rv(root) != NULL) {
/*
* Try to merge the fragment into the root. This will only
* succeed if the fragment overlaps and begins with sufficient
* silence to be a presumed match.
*
* Note that the fragments must be passed to i_silence_match()
* in ascending order, as they are here.
*/
if (i_silence_match(root, first, callback)) {
/*
* If we successfully merged the fragment, set the flag
* to keep looping.
*/
ret++;
flag = 1;
}
}
}
}
}
}
#ifndef HAVE_DYN_ARRAYS
_pfree(list);
#endif
/*
* If we were able to extend the verified root at all during this pass
* through the loop, loop again to see if we can merge any remaining
* fragments with the extended root.
*/
}
/*
* Return the number of fragments we successfully merged into the
* verified root.
*/
return (ret);
}
LOCAL void
i_end_case(p, endword, callback)
cdrom_paranoia *p;
long endword;
void (*callback) __PR((long, int));
{
root_block *root = &p->root;
/*
* have an 'end' flag; if we've just read in the last sector in a
* session, set the flag. If we verify to the end of a fragment
* which has the end flag set, we're done (set a done flag).
* Pad zeroes to the end of the read
*/
if (root->lastsector == 0)
return;
if (endword < re(root))
return;
{
long addto = endword - re(root);
char *temp = _pcalloc(addto, sizeof (char) * 2);
c_append(rc(root), (void *) temp, addto);
_pfree(temp);
/*
* trash da cache
*/
paranoia_resetcache(p);
}
}
/*
* We want to add a sector. Look through the caches for something that
* spans. Also look at the flags on the c_block... if this is an
* obliterated sector, get a bit of a chunk past the obliteration.
*
* Not terribly smart right now, actually. We can probably find
* *some* match with a cache block somewhere. Take it and continue it
* through the skip
*/
LOCAL void
verify_skip_case(p, callback)
cdrom_paranoia *p;
void (*callback) __PR((long, int));
{
root_block *root = &(p->root);
c_block *graft = NULL;
int vflag = 0;
int gend = 0;
long post;
#ifdef NOISY
fprintf(stderr, "\nskipping\n");
#endif
if (rv(root) == NULL) {
post = 0;
} else {
post = re(root);
}
if (post == -1)
post = 0;
if (callback)
(*callback) (post, PARANOIA_CB_SKIP);
if (p->enable & PARANOIA_MODE_NEVERSKIP)
return;
/*
* We want to add a sector. Look for a c_block that spans,
* preferrably a verified area
*/
{
c_block *c = c_first(p);
while (c) {
long cbegin = cb(c);
long cend = ce(c);
if (cbegin <= post && cend > post) {
long vend = post;
if (c->flags[post - cbegin] & FLAGS_VERIFIED) {
/*
* verified area!
*/
while (vend < cend && (c->flags[vend - cbegin] & FLAGS_VERIFIED))
vend++;
if (!vflag || vend > vflag) {
graft = c;
gend = vend;
}
vflag = 1;
} else {
/*
* not a verified area
*/
if (!vflag) {
while (vend < cend && (c->flags[vend - cbegin] & FLAGS_VERIFIED) == 0)
vend++;
if (graft == NULL || gend > vend) {
/*
* smallest unverified area
*/
graft = c;
gend = vend;
}
}
}
}
c = c_next(c);
}
if (graft) {
long cbegin = cb(graft);
long cend = ce(graft);
while (gend < cend && (graft->flags[gend - cbegin] & FLAGS_VERIFIED))
gend++;
gend = min(gend + OVERLAP_ADJ, cend);
if (rv(root) == NULL) {
Int16_t *buff = _pmalloc(cs(graft));
memcpy(buff, cv(graft), cs(graft));
rc(root) = c_alloc(buff, cb(graft), cs(graft));
} else {
c_append(rc(root), cv(graft) + post - cbegin,
gend - post);
}
root->returnedlimit = re(root);
return;
}
}
/*
* No? Fine. Great. Write in some zeroes :-P
*/
{
void *temp = _pcalloc(CD_FRAMESIZE_RAW, sizeof (Int16_t));
if (rv(root) == NULL) {
rc(root) = c_alloc(temp, post, CD_FRAMESIZE_RAW);
} else {
c_append(rc(root), temp, CD_FRAMESIZE_RAW);
_pfree(temp);
}
root->returnedlimit = re(root);
}
}
/*
* toplevel
*/
EXPORT void
paranoia_free(p)
cdrom_paranoia *p;
{
paranoia_resetall(p);
sort_free(p->sortcache);
free_list(p->cache, 1);
free_list(p->fragments, 1);
_pfree(p);
}
EXPORT void
paranoia_modeset(p, enable)
cdrom_paranoia *p;
int enable;
{
p->enable = enable;
if (enable & PARANOIA_MODE_C2CHECK) {
p->sectsize = CD_C2SIZE_RAW;
p->sectwords = CD_C2SIZE_RAW/2;
} else {
p->sectsize = CD_FRAMESIZE_RAW;
p->sectwords = CD_FRAMESIZE_RAW/2;
}
}
EXPORT int
paranoia_modeget(p)
cdrom_paranoia *p;
{
return (p->enable);
}
EXPORT void
paranoia_set_readahead(p, readahead)
cdrom_paranoia *p;
int readahead;
{
p->readahead = readahead;
sort_free(p->sortcache);
p->sortcache = sort_alloc(p->readahead * CD_FRAMEWORDS);
}
EXPORT int
paranoia_get_readahead(p)
cdrom_paranoia *p;
{
return (p->readahead);
}
EXPORT long
paranoia_seek(p, seek, mode)
cdrom_paranoia *p;
long seek;
int mode;
{
long sector;
long ret;
switch (mode) {
case SEEK_SET:
sector = seek;
break;
case SEEK_END:
sector = p->d_disc_lastsector(p->d) + seek;
break;
default:
sector = p->cursor + seek;
break;
}
if (p->d_sector_gettrack(p->d, sector) == -1)
return (-1);
i_cblock_destructor(p->root.vector);
p->root.vector = NULL;
p->root.lastsector = 0;
p->root.returnedlimit = 0;
ret = p->cursor;
p->cursor = sector;
i_paranoia_firstlast(p);
/*
* Evil hack to fix pregap patch for NEC drives! To be rooted out in a10
*/
p->current_firstsector = sector;
return (ret);
}
LOCAL void
c2_audiocopy(to, from, nsectors)
void *to;
void *from;
int nsectors;
{
char *tocp = to;
char *fromcp = from;
while (--nsectors >= 0) {
memmove(tocp, fromcp, CD_FRAMESIZE_RAW);
tocp += CD_FRAMESIZE_RAW;
fromcp += CD_C2SIZE_RAW;
}
}
/*
* Stolen from readcd(1)
*/
LOCAL int
bits(c)
int c;
{
int n = 0;
if (c & 0x01)
n++;
if (c & 0x02)
n++;
if (c & 0x04)
n++;
if (c & 0x08)
n++;
if (c & 0x10)
n++;
if (c & 0x20)
n++;
if (c & 0x40)
n++;
if (c & 0x80)
n++;
return (n);
}
LOCAL void
c2_errcopy(to, from, nsectors, errp)
void *to;
void *from;
int nsectors;
struct c2errs *errp;
{
char dummy[CD_C2PTR_RAW * 4];
char *tocp = to;
char *fromcp = from;
int errs = 0;
UInt8_t *ep;
UInt8_t e;
int i;
errp->c2errs = 0;
errp->c2bytes = 0;
errp->c2secs = 0;
errp->c2maxerrs = 0;
while (--nsectors >= 0) {
if (to == NULL)
tocp = dummy;
ep = (UInt8_t *)(fromcp + CD_FRAMESIZE_RAW);
for (i = CD_C2PTR_RAW; --i >= 0; tocp += 4) {
if ((e = *ep++) != 0) {
if (e & 0xC0)
tocp[0] |= FLAGS_C2;
if (e & 0x30)
tocp[1] |= FLAGS_C2;
if (e & 0x0C)
tocp[2] |= FLAGS_C2;
if (e & 0x03)
tocp[3] |= FLAGS_C2;
errs += bits(e);
}
}
if (errs > 0) {
errp->c2bytes += errs;
errp->c2secs++;
if (errs > errp->c2maxerrs)
errp->c2maxerrs = errs;
errs = 0;
}
fromcp += CD_C2SIZE_RAW;
}
if (errp->c2secs > 0)
errp->c2errs++;
}
/*
* read_c_block() (internal)
*
* This funtion reads many (p->readahead) sectors, encompassing at least
* the requested words.
*
* It returns a c_block which encapsulates these sectors' data and sector
* number. The sectors come come from multiple low-level read requests.
*
* This function reads many sectors in order to exhaust any caching on the
* drive itself, as caching would simply return the same incorrect data
* over and over. Paranoia depends on truly re-reading portions of the
* disc to make sure the reads are accurate and correct any inaccuracies.
*
* Which precise sectors are read varies ("jiggles") between calls to
* read_c_block, to prevent consistent errors across multiple reads
* from being misinterpreted as correct data.
*
* The size of each low-level read is determined by the underlying driver
* (p->d->nsectors), which allows the driver to specify how many sectors
* can be read in a single request. Historically, the Linux kernel could
* only read 8 sectors at a time, with likely dropped samples between each
* read request. Other operating systems may have different limitations.
*
* This function is called by paranoia_read_limited(), which breaks the
* c_block of read data into runs of samples that are likely to be
* contiguous, verifies them and stores them in verified fragments, and
* eventually merges the fragments into the verified root.
*
* This function returns the last c_block read or NULL on error.
*/
EXPORT c_block *
i_read_c_block(p, beginword, endword, callback)
cdrom_paranoia *p;
long beginword;
long endword;
void (*callback) __PR((long, int));
{
/*
* why do it this way? We need to read lots of sectors to kludge
* around stupid read ahead buffers on cheap drives, as well as avoid
* expensive back-seeking. We also want to 'jiggle' the start address
* to try to break borderline drives more noticeably (and make broken
* drives with unaddressable sectors behave more often).
*/
long readat;
long firstread;
long totaltoread = p->readahead;
long sectatonce = p->nsectors;
long driftcomp = (float) p->dyndrift / CD_FRAMEWORDS + .5;
c_block *new = NULL;
root_block *root = &p->root;
Int16_t *buffer = NULL;
void *bufbase = NULL;
Uchar *flags = NULL;
long sofar;
long dynoverlap = (p->dynoverlap + CD_FRAMEWORDS - 1) / CD_FRAMEWORDS;
long anyflag = 0;
int reduce = 0;
static int pagesize = -1;
#define valign(x, a) (((char *)(x)) + ((a) - 1 - ((((UIntptr_t)(x))-1)%(a))))
/*
* Calculate the first sector to read. This calculation takes
* into account the need to jitter the starting point of the read
* to reveal consistent errors as well as the low reliability of
* the edge words of a read.
*/
/*
* What is the first sector to read? want some pre-buffer if we're not
* at the extreme beginning of the disc
*/
if (p->enable & (PARANOIA_MODE_VERIFY | PARANOIA_MODE_OVERLAP)) {
/*
* we want to jitter the read alignment boundary
*/
long target;
if (rv(root) == NULL || rb(root) > beginword)
target = p->cursor - dynoverlap;
else
target = re(root) / (CD_FRAMEWORDS) - dynoverlap;
if (target + MIN_SECTOR_BACKUP > p->lastread && target <= p->lastread)
target = p->lastread - MIN_SECTOR_BACKUP;
/*
* we want to jitter the read alignment boundary, as some
* drives, beginning from a specific point, will tend to
* lose bytes between sectors in the same place. Also, as
* our vectors are being made up of multiple reads, we want
* the overlap boundaries to move....
*/
readat = (target & (~((long) JIGGLE_MODULO - 1))) + p->jitter;
if (readat > target)
readat -= JIGGLE_MODULO;
p->jitter++;
if (p->jitter >= JIGGLE_MODULO)
p->jitter = 0;
} else {
readat = p->cursor;
}
readat += driftcomp;
/*
* Create a new, empty c_block and add it to the head of the
* list of c_blocks in memory. It will be empty until the end of
* this subroutine.
*/
if (p->enable & (PARANOIA_MODE_OVERLAP | PARANOIA_MODE_VERIFY)) {
flags = _pcalloc(totaltoread * CD_FRAMEWORDS, 1);
new = new_c_block(p);
recover_cache(p);
} else {
/*
* in the case of root it's just the buffer
*/
paranoia_resetall(p);
new = new_c_block(p);
}
/*
* Do not use valloc() as valloc() in glibc is buggy and returns memory
* that cannot be passed to free().
*/
if (pagesize < 0) {
#ifdef _SC_PAGESIZE
pagesize = sysconf(_SC_PAGESIZE);
#else
pagesize = getpagesize();
#endif
if (pagesize < 0)
pagesize = 4096; /* Just a guess */
}
reduce = pagesize / p->sectsize;
bufbase = _pmalloc(totaltoread * p->sectsize + pagesize);
buffer = (Int16_t *)valign(bufbase, pagesize);
sofar = 0;
firstread = -1;
/*
* Issue each of the low-level reads; the optimal read size is
* approximately the cachemodel's cdrom cache size. The only reason
* to read less would be memory considerations.
*
* p->readahead = total number of sectors to read
* p->d->nsectors = number of sectors to read per request
*/
/*
* actual read loop
*/
while (sofar < totaltoread) {
long secread = sectatonce; /* number of sectors to read this request */
long adjread = readat; /* first sector to read for this request */
long thisread; /* how many sectors were read this request */
/*
* don't under/overflow the audio session
*/
if (adjread < p->current_firstsector) {
secread -= p->current_firstsector - adjread;
adjread = p->current_firstsector;
}
if (adjread + secread - 1 > p->current_lastsector)
secread = p->current_lastsector - adjread + 1;
if (sofar + secread > totaltoread)
secread = totaltoread - sofar;
/*
* If we are inside the buffer, the transfers are no longer
* page aligned. Reduce the transfer size to avoid problems.
* Such problems are definitely known to appear on FreeBSD.
*/
if ((sofar > 0) && (secread > (sectatonce - reduce)))
secread = sectatonce - reduce;
if (secread > 0) {
struct c2errs c2errs;
/*
* We only evaluate it when the PARANOIA_MODE_C2CHECK
* flag is present, but let us be nice.
*/
c2errs.c2errs = c2errs.c2bytes = c2errs.c2secs =
c2errs.c2maxerrs = 0;
if (firstread < 0)
firstread = adjread;
/*
* Issue the low-level read to the driver.
*
* If the low-level read returned too few sectors, pad the result
* with null data and mark it as invalid (FLAGS_UNREAD). We pad
* because we're going to be appending further reads to the current
* c_block.
*
* "???: Why not re-read? It might be to keep you from getting
* hung up on a bad sector. Or it might be to avoid
* interrupting the streaming as much as possible."
*
* There are drives on which you will never get a full read in
* some positions. They always abort out early due to firmware
* boundary cases. Reread will cause exactly the same thing to
* happen again. NEC MultiSpeed 4x is one such drive. In these
* cases, you take what part of the read you know is good, and
* you get substantially better performance. --Monty
*/
if ((thisread = p->d_read(p->d, buffer + sofar * p->sectwords, adjread,
secread)) < secread) {
if (thisread < 0)
thisread = 0;
/*
* Uhhh... right. Make something up. But
* don't make us seek backward!
*/
if (callback)
(*callback) ((adjread + thisread) * CD_FRAMEWORDS, PARANOIA_CB_READERR);
memset(buffer + (sofar + thisread) * CD_FRAMEWORDS, 0,
CD_FRAMESIZE_RAW * (secread - thisread));
if (flags)
memset(flags + (sofar + thisread) * CD_FRAMEWORDS, FLAGS_UNREAD,
CD_FRAMEWORDS * (secread - thisread));
}
if (thisread != 0)
anyflag = 1;
/* BEGIN CSTYLED */
/*
* Because samples are likely to be dropped between read requests,
* mark the samples near the the boundaries of the read requests
* as suspicious (FLAGS_EDGE). This means that any span of samples
* against which these adjacent read requests are compared must
* overlap beyond the edges and into the more trustworthy data.
* Such overlapping spans are accordingly at least MIN_WORDS_OVERLAP
* words long (and naturally longer if any samples were dropped
* between the read requests).
*
* (EEEEE...overlapping span...EEEEE)
* (read 1 ...........EEEEE) (EEEEE...... read 2 ......EEEEE) ...
* dropped samples --^
*/
/* END CSTYLED */
if (flags && sofar != 0) {
/*
* Don't verify across overlaps that are too
* close to one another
*/
int i = 0;
for (i = -MIN_WORDS_OVERLAP / 2; i < MIN_WORDS_OVERLAP / 2; i++)
flags[sofar * CD_FRAMEWORDS + i] |= FLAGS_EDGE;
}
if (flags && p->enable & PARANOIA_MODE_C2CHECK) {
c2_errcopy(flags + sofar * CD_FRAMEWORDS,
buffer + sofar * p->sectwords, thisread, &c2errs);
}
p->lastread = adjread + secread;
if (adjread + secread - 1 == p->current_lastsector)
new->lastsector = -1;
if (callback) {
(*callback) (thisread, PARANOIA_CB_SECS);
if (p->enable & PARANOIA_MODE_C2CHECK) {
if (c2errs.c2errs > 0)
(*callback) (adjread * CD_FRAMEWORDS, PARANOIA_CB_C2ERR);
if (c2errs.c2bytes > 0)
(*callback) (c2errs.c2bytes, PARANOIA_CB_C2BYTES);
if (c2errs.c2secs > 0)
(*callback) (c2errs.c2secs, PARANOIA_CB_C2SECS);
if (c2errs.c2maxerrs > 0)
(*callback) (c2errs.c2maxerrs, PARANOIA_CB_C2MAXERRS);
}
(*callback) ((adjread + secread - 1) * CD_FRAMEWORDS, PARANOIA_CB_READ);
}
sofar += secread;
readat = adjread + secread;
} else if (readat < p->current_firstsector) {
readat += sectatonce;
/*
* due to being before the
* readable area
*/
} else {
break; /* due to being past the readable area */
}
/*
* Keep issuing read requests until we've read enough sectors to
* exhaust the drive's cache.
*/
}
/*
* If we managed to read any sectors at all (anyflag), fill in the
* previously allocated c_block with the read data. Otherwise, free
* our buffers, dispose of the c_block, and return NULL.
*/
if (anyflag) {
new->vector = _pmalloc(totaltoread * CD_FRAMESIZE_RAW);
if (p->enable & PARANOIA_MODE_C2CHECK) {
c2_audiocopy(new->vector, buffer, totaltoread);
} else {
memcpy(new->vector, buffer, totaltoread * CD_FRAMESIZE_RAW);
}
_pfree(bufbase);
new->begin = firstread * CD_FRAMEWORDS - p->dyndrift;
new->size = sofar * CD_FRAMEWORDS;
new->flags = flags;
} else {
if (new)
free_c_block(new);
if (bufbase)
_pfree(bufbase);
if (flags)
_pfree(flags);
new = NULL;
bufbase = NULL;
flags = NULL;
}
return (new);
}
/*
* paranoia_read(), paranoia_read_limited()
*
* These functions "read" the next sector of audio data and returns
* a pointer to a full sector of verified samples (2352 bytes).
*
* The returned buffer is *not* to be freed by the caller. It will
* persist only until the next call to paranoia_read() for this p
*/
EXPORT Int16_t *
paranoia_read(p, callback)
cdrom_paranoia *p;
void (*callback) __PR((long, int));
{
return (paranoia_read_limited(p, callback, 20));
}
/*
* I added max_retry functionality this way in order to avoid breaking any
* old apps using the nerw libs. cdparanoia 9.8 will need the updated libs,
* but nothing else will require it.
*/
EXPORT Int16_t *
paranoia_read_limited(p, callback, max_retries)
cdrom_paranoia *p;
void (*callback) __PR((long, int));
int max_retries;
{
long beginword = p->cursor * (CD_FRAMEWORDS);
long endword = beginword + CD_FRAMEWORDS;
long retry_count = 0;
long lastend = -2;
root_block *root = &p->root;
if (beginword > p->root.returnedlimit)
p->root.returnedlimit = beginword;
lastend = re(root);
/*
* Since paranoia reads and verifies chunks of data at a time
* (which it needs to counteract dropped samples and inaccurate
* seeking), the requested samples may already be in memory,
* in the verified "root".
*
* The root is where paranoia stores samples that have been
* verified and whose position has been accurately determined.
*
* First, is the sector we want already in the root?
*/
while (rv(root) == NULL ||
rb(root) > beginword ||
(re(root) < endword + p->maxdynoverlap &&
p->enable & (PARANOIA_MODE_VERIFY | PARANOIA_MODE_OVERLAP)) ||
re(root) < endword) {
/*
* Nope; we need to build or extend the root verified range
*
* We may have already read the necessary samples and placed
* them into verified fragments, but not yet merged them into
* the verified root. We'll check that before we actually
* try to read data from the drive.
*/
if (p->enable & (PARANOIA_MODE_VERIFY | PARANOIA_MODE_OVERLAP)) {
/*
* We need to make sure our memory consumption doesn't grow
* to the size of the whole CD. But at the same time, we
* need to hang onto some of the verified data (even perhaps
* data that's already been returned by paranoia_read()) in
* order to verify and accurately position future samples.
*
* Therefore, we free some of the verified data that we
* no longer need.
*/
i_paranoia_trim(p, beginword, endword);
recover_cache(p);
if (rb(root) != -1 && p->root.lastsector) {
i_end_case(p, endword + p->maxdynoverlap,
callback);
} else {
/*
* Merge as many verified fragments into the verified root
* as we need to satisfy the pending request. We may
* not have all the fragments we need, in which case we'll
* read data from the CD further below.
*/
i_stage2(p, beginword,
endword + p->maxdynoverlap,
callback);
}
} else
i_end_case(p, endword + p->maxdynoverlap,
callback); /* only trips if we're already */
/* done */
/*
* If we were able to fill the verified root with data already
* in memory, we don't need to read any more data from the drive.
*/
if (!(rb(root) == -1 || rb(root) > beginword ||
re(root) < endword + p->maxdynoverlap))
break;
/*
* Hmm, need more. Read another block
*/
{
/*
* Read many sectors, encompassing at least the requested words.
*
* The returned c_block encapsulates these sectors' data and
* sector number. The sectors come come from multiple low-level
* read requests, and words which were near the boundaries of
* those read requests are marked with FLAGS_EDGE.
*/
c_block *new = i_read_c_block(p, beginword, endword, callback);
if (new) {
if (p->enable & (PARANOIA_MODE_OVERLAP | PARANOIA_MODE_VERIFY)) {
/*
* If we need to verify these samples, send them to
* stage 1 verification, which will add verified samples
* to the set of verified fragments. Verified fragments
* will be merged into the verified root during stage 2
* overlap analysis.
*/
if (p->enable & PARANOIA_MODE_VERIFY)
i_stage1(p, new, callback);
else {
/*
* If we're only doing overlapping reads (no stage 1
* verification), consider each low-level read in the
* c_block to be a verified fragment. We exclude the
* edges from these fragments to enforce the requirement
* that we overlap the reads by the minimum amount.
* These fragments will be merged into the verified
* root during stage 2 overlap analysis.
*/
/*
* just make v_fragments from the
* boundary information.
*/
long begin = 0,
end = 0;
while (begin < cs(new)) {
while (end < cs(new) && (new->flags[begin] & FLAGS_EDGE))
begin++;
end = begin + 1;
while (end < cs(new) && (new->flags[end] & FLAGS_EDGE) == 0)
end++;
{
new_v_fragment(p, new, begin + cb(new),
end + cb(new),
(new->lastsector && cb(new) + end == ce(new)));
}
begin = end;
}
}
} else {
/*
* If we're not doing any overlapping reads or verification
* of data, skip over the stage 1 and stage 2 verification and
* promote this c_block directly to the current "verified" root.
*/
if (p->root.vector)
i_cblock_destructor(p->root.vector);
free_elem(new->e, 0);
p->root.vector = new;
i_end_case(p, endword + p->maxdynoverlap,
callback);
}
}
}
/*
* Are we doing lots of retries? **********************
*
* Check unaddressable sectors first. There's no backoff
* here; jiggle and minimum backseek handle that for us
*/
if (rb(root) != -1 && lastend + 588 < re(root)) {
/*
* If we've not grown half a sector
*/
lastend = re(root);
retry_count = 0;
} else {
/*
* increase overlap or bail
*/
retry_count++;
/*
* The better way to do this is to look at how many
* actual matches we're getting and what kind of gap
*/
if (retry_count % 5 == 0) {
if (p->dynoverlap == p->maxdynoverlap ||
retry_count == max_retries) {
verify_skip_case(p, callback);
retry_count = 0;
} else {
if (p->stage1.offpoints != -1) { /* hack */
p->dynoverlap *= 1.5;
if (p->dynoverlap > p->maxdynoverlap)
p->dynoverlap = p->maxdynoverlap;
if (callback)
(*callback) (p->dynoverlap, PARANOIA_CB_OVERLAP);
}
}
}
}
/*
* Having read data from the drive and placed it into verified
* fragments, we now loop back to try to extend the root with
* the newly loaded data. Alternatively, if the root already
* contains the needed data, we'll just fall through.
*/
}
p->cursor++;
/*
* Return a pointer into the verified root. Thus, the caller
* must NOT free the returned pointer!
*/
return (rv(root) + (beginword - rb(root)));
}
/*
* a temporary hack
*/
EXPORT void
paranoia_overlapset(p, overlap)
cdrom_paranoia *p;
long overlap;
{
p->dynoverlap = overlap * CD_FRAMEWORDS;
p->stage1.offpoints = -1;
}
Reference in New Issue Copy Permalink