1 /* @(#)overlap.c 1.16 09/07/11 J. Schilling from cdparanoia-III-alpha9.8 */
2 #include <schily/mconfig.h>
3 #ifndef lint
4 static UConst char sccsid[] =
5 "@(#)overlap.c 1.16 09/07/11 J. Schilling from cdparanoia-III-alpha9.8";
6
7 #endif
8 /*
9 * CopyPolicy: GNU Lesser General Public License v2.1 applies
10 * Copyright (C) 1997-2001,2008 by Monty (xiphmont@mit.edu)
11 * Copyright (C) 2002-2009 by J. Schilling
12 *
13 * Statistic code and cache management for overlap settings
14 *
15 */
16
17 #include <schily/stdlib.h>
18 #include <schily/standard.h>
19 #include <schily/utypes.h>
20 #include "p_block.h"
21 #include "cdda_paranoia.h"
22 #include "overlap.h"
23 #include "isort.h"
24
25 EXPORT void paranoia_resetcache __PR((cdrom_paranoia * p));
26 EXPORT void paranoia_resetall __PR((cdrom_paranoia * p));
27 EXPORT void i_paranoia_trim __PR((cdrom_paranoia * p,
28 long beginword, long endword));
29 EXPORT void offset_adjust_settings __PR((cdrom_paranoia * p,
30 void (*callback) (long, int)));
31 EXPORT void offset_add_value __PR((cdrom_paranoia * p,
32 offsets * o, long value,
33 void (*callback) (long, int)));
34
35 /*
36 * Internal cache management
37 */
38 EXPORT void
paranoia_resetcache(p)39 paranoia_resetcache(p)
40 cdrom_paranoia *p;
41 {
42 c_block *c = c_first(p);
43 v_fragment *v;
44
45 while (c) {
46 free_c_block(c);
47 c = c_first(p);
48 }
49
50 v = v_first(p);
51 while (v) {
52 free_v_fragment(v);
53 v = v_first(p);
54 }
55 }
56
57 EXPORT void
paranoia_resetall(p)58 paranoia_resetall(p)
59 cdrom_paranoia *p;
60 {
61 p->root.returnedlimit = 0;
62 p->dyndrift = 0;
63 p->root.lastsector = 0;
64
65 if (p->root.vector) {
66 i_cblock_destructor(p->root.vector);
67 p->root.vector = NULL;
68 }
69 paranoia_resetcache(p);
70 }
71
72 EXPORT void
i_paranoia_trim(p,beginword,endword)73 i_paranoia_trim(p, beginword, endword)
74 cdrom_paranoia *p;
75 long beginword;
76 long endword;
77 {
78 root_block *root = &(p->root);
79
80 if (root->vector != NULL) {
81 long target = beginword - p->maxdynoverlap;
82 long rbegin = cb(root->vector);
83 long rend = ce(root->vector);
84
85 if (rbegin > beginword)
86 goto rootfree;
87
88 if (rbegin + p->maxdynoverlap < beginword) {
89 if (target + MIN_WORDS_OVERLAP > rend)
90 goto rootfree;
91
92 {
93 long offset = target - rbegin;
94
95 c_removef(root->vector, offset);
96 }
97 } {
98 c_block *c = c_first(p);
99
100 while (c) {
101 c_block *next = c_next(c);
102
103 if (ce(c) < beginword - p->maxdynoverlap)
104 free_c_block(c);
105 c = next;
106 }
107 }
108
109 }
110 return;
111
112 rootfree:
113
114 i_cblock_destructor(root->vector);
115 root->vector = NULL;
116 root->returnedlimit = -1;
117 root->lastsector = 0;
118
119 }
120
121 /*
122 * Statistical and heuristic[al? :-] management
123 *
124 * offset_adjust_settings (internal)
125 *
126 * This function is called by offset_add_value() every time 10 samples have
127 * been accumulated. This function updates the internal statistics for
128 * paranoia (dynoverlap, dyndrift) that compensate for jitter and drift.
129 *
130 * (dynoverlap) influences how far stage 1 and stage 2 search for matching
131 * runs. In low-jitter conditions, it will be very small (or even 0),
132 * narrowing our search. In high-jitter conditions, it will be much larger,
133 * widening our search at the cost of speed.
134 */
135 EXPORT void
offset_adjust_settings(p,callback)136 offset_adjust_settings(p, callback)
137 cdrom_paranoia *p;
138 void (*callback) __PR((long, int));
139 {
140 if (p->stage2.offpoints >= 10) {
141 /*
142 * drift: look at the average offset value. If it's over one
143 * sector, frob it. We just want a little hysteresis [sp?]
144 */
145 long av = (p->stage2.offpoints ? p->stage2.offaccum / p->stage2.offpoints : 0);
146
147 if (abs(av) > p->dynoverlap / 4) {
148 av = (av / MIN_SECTOR_EPSILON) * MIN_SECTOR_EPSILON;
149
150 if (callback)
151 (*callback) (ce(p->root.vector), PARANOIA_CB_DRIFT);
152 p->dyndrift += av;
153
154 /*
155 * Adjust all the values in the cache otherwise we get
156 * a (potentially unstable) feedback loop
157 */
158 {
159 c_block *c = c_first(p);
160 v_fragment *v = v_first(p);
161
162 while (v && v->one) {
163 /*
164 * safeguard beginning bounds case with
165 * a hammer
166 */
167 if (fb(v) < av || cb(v->one) < av) {
168 v->one = NULL;
169 } else {
170 fb(v) -= av;
171 }
172 v = v_next(v);
173 }
174 while (c) {
175 long adj = min(av, cb(c));
176
177 c_set(c, cb(c) - adj);
178 c = c_next(c);
179 }
180 }
181
182 p->stage2.offaccum = 0;
183 p->stage2.offmin = 0;
184 p->stage2.offmax = 0;
185 p->stage2.offpoints = 0;
186 p->stage2.newpoints = 0;
187 p->stage2.offdiff = 0;
188 }
189 }
190 if (p->stage1.offpoints >= 10) {
191 /*
192 * dynoverlap: we arbitrarily set it to 4x the running
193 * difference value, unless min/max are more
194 */
195 p->dynoverlap = (p->stage1.offpoints ? p->stage1.offdiff /
196 p->stage1.offpoints * 3 : CD_FRAMEWORDS);
197
198 if (p->dynoverlap < -p->stage1.offmin * 1.5)
199 p->dynoverlap = -p->stage1.offmin * 1.5;
200
201 if (p->dynoverlap < p->stage1.offmax * 1.5)
202 p->dynoverlap = p->stage1.offmax * 1.5;
203
204 if (p->dynoverlap < p->mindynoverlap)
205 p->dynoverlap = p->mindynoverlap;
206 if (p->dynoverlap > p->maxdynoverlap)
207 p->dynoverlap = p->maxdynoverlap;
208
209 if (callback)
210 (*callback) (p->dynoverlap, PARANOIA_CB_OVERLAP);
211
212 if (p->stage1.offpoints > 600) {
213 /*
214 * bit of a bug; this routine is called too often
215 * due to the overlap mesh alg we use in stage 1
216 */
217 p->stage1.offpoints /= 1.2;
218 p->stage1.offaccum /= 1.2;
219 p->stage1.offdiff /= 1.2;
220 }
221 p->stage1.offmin = 0;
222 p->stage1.offmax = 0;
223 p->stage1.newpoints = 0;
224 }
225 }
226
227 /*
228 * offset_add_value (internal)
229 *
230 * This function adds the given jitter detected (value) to the statistics
231 * for the given stage (o). It is called whenever jitter has been identified
232 * by stage 1 or 2. After every 10 samples, we update the overall jitter-
233 * compensation settings (e.g. dynoverlap). This allows us to narrow our
234 * search for matching runs (in both stages) in low-jitter conditions
235 * and also widen our search appropriately when there is jitter.
236 *
237 *
238 * "???BUG???:
239 * Note that there is a bug in the way that this is called by try_sort_sync().
240 * Silence looks like zero jitter, and dynoverlap may be incorrectly reduced
241 * when there's lots of silence but also jitter."
242 *
243 * Strictly speaking, this is only sort-of true. The silence will
244 * incorrectly somewhat reduce dynoverlap. However, it will increase
245 * again once past the silence (even if reduced to zero, it will be
246 * increased by the block read loop if we're not getting matches).
247 * In reality, silence usually passes rapidly. Anyway, long streaks
248 * of silence benefit performance-wise from having dynoverlap decrease
249 * momentarily. There is no correctness bug. --Monty
250 *
251 */
252 EXPORT void
offset_add_value(p,o,value,callback)253 offset_add_value(p, o, value, callback)
254 cdrom_paranoia *p;
255 offsets *o;
256 long value;
257 void (*callback) __PR((long, int));
258 {
259 if (o->offpoints != -1) {
260
261 /*
262 * Track the average magnitude of jitter (in either direction)
263 */
264 o->offdiff += abs(value);
265 o->offpoints++;
266 o->newpoints++;
267 /*
268 * Track the net value of the jitter (to track drift)
269 */
270 o->offaccum += value;
271 /*
272 * Track the largest jitter we've encountered in each direction
273 */
274 if (value < o->offmin)
275 o->offmin = value;
276 if (value > o->offmax)
277 o->offmax = value;
278
279 /*
280 * After 10 samples, update dynoverlap, etc.
281 */
282 if (o->newpoints >= 10)
283 offset_adjust_settings(p, callback);
284 }
285 }
286