1 /*
2 TiMidity++ -- MIDI to WAVE converter and player
3 Copyright (C) 1999-2004 Masanao Izumo <iz@onicos.co.jp>
4 Copyright (C) 1995 Tuukka Toivonen <tt@cgs.fi>
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19
20 recache.c
21
22 Code related to resample cache.
23 */
24
25 #ifdef HAVE_CONFIG_H
26 #include "config.h"
27 #endif /* HAVE_CONFIG_H */
28 #ifdef __POCC__
29 #include <sys/types.h>
30 #endif //for off_t
31 #include <stdio.h>
32 #ifdef HAVE_UNISTD_H
33 #include <unistd.h>
34 #endif /* HAVE_UNISTD_H */
35 #include <stdlib.h>
36
37 #ifndef NO_STRING_H
38 #include <string.h>
39 #else
40 #include <strings.h>
41 #endif
42
43 #include "timidity.h"
44 #include "common.h"
45 #include "instrum.h"
46 #include "playmidi.h"
47 #include "output.h"
48 #include "controls.h"
49 #include "tables.h"
50 #include "mblock.h"
51 #include "recache.h"
52 #include "resample.h"
53
54 #define HASH_TABLE_SIZE 251
55 #define MIXLEN 256
56
57 #define MIN_LOOPSTART MIXLEN
58 #define MIN_LOOPLEN 1024
59 #define MAX_EXPANDLEN (1024 * 32)
60 #define CACHE_DATA_LEN (allocate_cache_size / sizeof(sample_t))
61
62 #define sp_hash(sp, note) ((unsigned long) (sp) + (unsigned int) (note))
63 #define CACHE_RESAMPLING_OK 0
64 #define CACHE_RESAMPLING_NOTOK 1
65 #define SORT_THRESHOLD 20
66 #define RESAMPLATION_CACHE _x = do_resamplation(src, ofs, &resrc); \
67 dest[i] = (int16) ((_x > 32767) ? 32767 \
68 : ((_x < -32768) ? -32768 : _x))
69
70 static sample_t *cache_data = NULL;
71 int32 allocate_cache_size = DEFAULT_CACHE_DATA_SIZE;
72 static splen_t cache_data_len;
73 static struct cache_hash *cache_hash_table[HASH_TABLE_SIZE];
74 static MBlockList hash_entry_pool;
75
76 static struct {
77 int32 on[128];
78 struct cache_hash *cache[128];
79 } channel_note_table[MAX_CHANNELS];
80
81 static double sample_resamp_info(Sample *, int,
82 splen_t *, splen_t *, splen_t *);
83 static void qsort_cache_array(struct cache_hash **, long, long);
84 static void insort_cache_array(struct cache_hash **, long);
85 static int cache_resampling(struct cache_hash *);
86 static void loop_connect(sample_t *, int32, int32);
87
free_cache_data(void)88 void free_cache_data(void) {
89 free(cache_data);
90 reuse_mblock(&hash_entry_pool);
91 }
92
resamp_cache_reset(void)93 void resamp_cache_reset(void)
94 {
95 if (cache_data == NULL) {
96 cache_data = (sample_t *)
97 safe_large_malloc((CACHE_DATA_LEN + 1) * sizeof(sample_t));
98 memset(cache_data, 0, (CACHE_DATA_LEN + 1) * sizeof(sample_t));
99 init_mblock(&hash_entry_pool);
100 }
101 cache_data_len = 0;
102 memset(cache_hash_table, 0, sizeof(cache_hash_table));
103 memset(channel_note_table, 0, sizeof(channel_note_table));
104 reuse_mblock(&hash_entry_pool);
105 }
106
resamp_cache_fetch(Sample * sp,int note)107 struct cache_hash *resamp_cache_fetch(Sample *sp, int note)
108 {
109 unsigned int addr;
110 struct cache_hash *p;
111
112 if (sp->vibrato_control_ratio || (sp->modes & MODES_PINGPONG)
113 || (sp->sample_rate == play_mode->rate
114 && sp->root_freq == get_note_freq(sp, sp->note_to_use)))
115 return NULL;
116 addr = sp_hash(sp, note) % HASH_TABLE_SIZE;
117 p = cache_hash_table[addr];
118 while (p && (p->note != note || p->sp != sp))
119 p = p->next;
120 if (p && p->resampled != NULL)
121 return p;
122 return NULL;
123 }
124
resamp_cache_refer_on(Voice * vp,int32 sample_start)125 void resamp_cache_refer_on(Voice *vp, int32 sample_start)
126 {
127 unsigned int addr;
128 struct cache_hash *p;
129 int note, ch;
130
131 ch = vp->channel;
132 if (vp->vibrato_control_ratio || channel[ch].portamento
133 || (vp->sample->modes & MODES_PINGPONG)
134 || vp->orig_frequency != vp->frequency
135 || (vp->sample->sample_rate == play_mode->rate
136 && vp->sample->root_freq
137 == get_note_freq(vp->sample, vp->sample->note_to_use)))
138 return;
139 note = vp->note;
140 if (channel_note_table[ch].cache[note])
141 resamp_cache_refer_off(ch, note, sample_start);
142 addr = sp_hash(vp->sample, note) % HASH_TABLE_SIZE;
143 p = cache_hash_table[addr];
144 while (p && (p->note != note || p->sp != vp->sample))
145 p = p->next;
146 if (! p) {
147 p = (struct cache_hash *)
148 new_segment(&hash_entry_pool, sizeof(struct cache_hash));
149 p->cnt = 0;
150 p->note = vp->note;
151 p->sp = vp->sample;
152 p->resampled = NULL;
153 p->next = cache_hash_table[addr];
154 cache_hash_table[addr] = p;
155 }
156 channel_note_table[ch].cache[note] = p;
157 channel_note_table[ch].on[note] = sample_start;
158 }
159
resamp_cache_refer_off(int ch,int note,int32 sample_end)160 void resamp_cache_refer_off(int ch, int note, int32 sample_end)
161 {
162 int32 sample_start, len;
163 struct cache_hash *p;
164 Sample *sp;
165
166 p = channel_note_table[ch].cache[note];
167 if (p == NULL)
168 return;
169 sp = p->sp;
170 if (sp->sample_rate == play_mode->rate
171 && sp->root_freq == get_note_freq(sp, sp->note_to_use))
172 return;
173 sample_start = channel_note_table[ch].on[note];
174 len = sample_end - sample_start;
175 if (len < 0) {
176 channel_note_table[ch].cache[note] = NULL;
177 return;
178 }
179 if (! (sp->modes & MODES_LOOPING)) {
180 double a;
181 int32 slen;
182
183 a = ((double) sp->root_freq * play_mode->rate)
184 / ((double) sp->sample_rate * get_note_freq(sp, note));
185 slen = (int32) ((sp->data_length >> FRACTION_BITS) * a);
186 if (len > slen)
187 len = slen;
188 }
189 p->cnt += len;
190 channel_note_table[ch].cache[note] = NULL;
191 }
192
resamp_cache_refer_alloff(int ch,int32 sample_end)193 void resamp_cache_refer_alloff(int ch, int32 sample_end)
194 {
195 int i;
196
197 for (i = 0; i < 128; i++)
198 resamp_cache_refer_off(ch, i, sample_end);
199 }
200
resamp_cache_create(void)201 void resamp_cache_create(void)
202 {
203 int i, skip;
204 int32 n, t1, t2, total;
205 struct cache_hash **array;
206
207 /* It is NP completion that solve the best cache hit rate.
208 * So I thought better algorism O(n log n), but not a best solution.
209 * Follows implementation takes good hit rate, and it is fast.
210 */
211 n = t1 = t2 = 0;
212 total = 0;
213 /* set size per count */
214 for (i = 0; i < HASH_TABLE_SIZE; i++) {
215 struct cache_hash *p, *q;
216
217 p = cache_hash_table[i], q = NULL;
218 while (p) {
219 struct cache_hash *tmp;
220
221 t1 += p->cnt;
222 tmp = p, p = p->next;
223 if (tmp->cnt > 0) {
224 Sample *sp;
225 splen_t newlen;
226
227 sp = tmp->sp;
228 sample_resamp_info(sp, tmp->note, NULL, NULL, &newlen);
229 if (newlen > 0) {
230 total += tmp->cnt;
231 tmp->r = (double) newlen / tmp->cnt;
232 tmp->next = q, q = tmp;
233 n++;
234 }
235 }
236 }
237 cache_hash_table[i] = q;
238 }
239 if (n == 0) {
240 ctl->cmsg(CMSG_INFO, VERB_VERBOSE, "No pre-resampling cache hit");
241 return;
242 }
243 array = (struct cache_hash **) new_segment(&hash_entry_pool,
244 n * sizeof(struct cache_hash *));
245 n = 0;
246 for (i = 0; i < HASH_TABLE_SIZE; i++) {
247 struct cache_hash *p;
248
249 for (p = cache_hash_table[i]; p; p = p->next)
250 array[n++] = p;
251 }
252 if (total > CACHE_DATA_LEN)
253 qsort_cache_array(array, 0, n - 1);
254 skip = 0;
255 for (i = 0; i < n; i++) {
256 if (array[i]->r != 0
257 && cache_resampling(array[i]) == CACHE_RESAMPLING_OK)
258 t2 += array[i]->cnt;
259 else
260 skip++;
261 }
262 ctl->cmsg(CMSG_INFO, VERB_NOISY,
263 "Resample cache: Key %d/%d(%.1f%%) Sample %.1f%c/%.1f%c(%.1f%%)",
264 n - skip, n, 100.0 * (n - skip) / n,
265 t2 / ((t2 >= 1048576) ? 1048576.0 : 1024.0),
266 (t2 >= 1048576) ? 'M' : 'K',
267 t1 / ((t1 >= 1048576) ? 1048576.0 : 1024.0),
268 (t1 >= 1048576) ? 'M' : 'K',
269 100.0 * t2 / t1);
270 /* update cache_hash_table */
271 if (skip)
272 for (i = 0; i < HASH_TABLE_SIZE; i++) {
273 struct cache_hash *p, *q;
274
275 p = cache_hash_table[i], q = NULL;
276 while (p) {
277 struct cache_hash *tmp;
278
279 tmp = p, p = p->next;
280 if (tmp->resampled)
281 tmp->next = q, q = tmp;
282 }
283 cache_hash_table[i] = q;
284 }
285 }
286
sample_resamp_info(Sample * sp,int note,splen_t * loop_start,splen_t * loop_end,splen_t * data_length)287 static double sample_resamp_info(Sample *sp, int note,
288 splen_t *loop_start, splen_t *loop_end, splen_t *data_length)
289 {
290 splen_t xls, xle, ls, le, ll, newlen;
291 double a, xxls, xxle, xn;
292
293 a = ((double) sp->sample_rate * get_note_freq(sp, note))
294 / ((double) sp->root_freq * play_mode->rate);
295 a = TIM_FSCALENEG((double) (int32) TIM_FSCALE(a, FRACTION_BITS),
296 FRACTION_BITS);
297 xn = sp->data_length / a;
298 if (xn >= SPLEN_T_MAX) {
299 /* Ignore this sample */
300 *data_length = 0;
301 return 0.0;
302 }
303 newlen = (splen_t) (TIM_FSCALENEG(xn, FRACTION_BITS) + 0.5);
304 ls = sp->loop_start;
305 le = sp->loop_end;
306 ll = le - ls;
307 xxls = ls / a + 0.5;
308 if (xxls >= SPLEN_T_MAX) {
309 /* Ignore this sample */
310 *data_length = 0;
311 return 0.0;
312 }
313 xls = (splen_t) xxls;
314 xxle = le / a + 0.5;
315 if (xxle >= SPLEN_T_MAX) {
316 /* Ignore this sample */
317 *data_length = 0;
318 return 0.0;
319 }
320 xle = (splen_t) xxle;
321 if ((sp->modes & MODES_LOOPING)
322 && ((xle - xls) >> FRACTION_BITS) < MIN_LOOPLEN) {
323 splen_t n;
324 splen_t newxle;
325 double xl; /* Resampled new loop length */
326 double xnewxle;
327
328 xl = ll / a;
329 if (xl >= SPLEN_T_MAX) {
330 /* Ignore this sample */
331 *data_length = 0;
332 return 0.0;
333 }
334 n = (splen_t) (0.0001 + MIN_LOOPLEN
335 / TIM_FSCALENEG(xl, FRACTION_BITS)) + 1;
336 xnewxle = le / a + n * xl + 0.5;
337 if (xnewxle >= SPLEN_T_MAX) {
338 /* Ignore this sample */
339 *data_length = 0;
340 return 0.0;
341 }
342 newxle = (splen_t) xnewxle;
343 newlen += (newxle - xle) >> FRACTION_BITS;
344 xle = newxle;
345 }
346 if (loop_start)
347 *loop_start = (splen_t) (xls & ~FRACTION_MASK);
348 if (loop_end)
349 *loop_end = (splen_t) (xle & ~FRACTION_MASK);
350 *data_length = newlen << FRACTION_BITS;
351 return a;
352 }
353
qsort_cache_array(struct cache_hash ** a,long first,long last)354 static void qsort_cache_array(struct cache_hash **a, long first, long last)
355 {
356 long i = first, j = last;
357 struct cache_hash *x, *t;
358
359 if (j - i < SORT_THRESHOLD) {
360 insort_cache_array(a + i, j - i + 1);
361 return;
362 }
363 x = a[(first + last) / 2];
364 for (;;) {
365 while (a[i]->r < x->r)
366 i++;
367 while (x->r < a[j]->r)
368 j--;
369 if (i >= j)
370 break;
371 t = a[i], a[i] = a[j], a[j] = t;
372 i++, j--;
373 }
374 if (first < i - 1)
375 qsort_cache_array(a, first, i - 1);
376 if (j + 1 < last)
377 qsort_cache_array(a, j + 1, last);
378 }
379
insort_cache_array(struct cache_hash ** data,long n)380 static void insort_cache_array(struct cache_hash **data, long n)
381 {
382 long i, j;
383 struct cache_hash *x;
384
385 for (i = 1; i < n; i++) {
386 x = data[i];
387 for (j = i - 1; j >= 0 && x->r < data[j]->r; j--)
388 data[j + 1] = data[j];
389 data[j + 1] = x;
390 }
391 }
392
cache_resampling(struct cache_hash * p)393 static int cache_resampling(struct cache_hash *p)
394 {
395 Sample *sp, *newsp;
396 sample_t *src, *dest;
397 splen_t newlen, ofs, le, ls, ll, xls, xle;
398 int32 i, incr, _x;
399 resample_rec_t resrc;
400 double a;
401 int8 note;
402
403 sp = p->sp;
404 if (sp->note_to_use)
405 note = sp->note_to_use;
406 else
407 note = p->note;
408 a = sample_resamp_info(sp, note, &xls, &xle, &newlen);
409 if (newlen == 0)
410 return CACHE_RESAMPLING_NOTOK;
411 newlen >>= FRACTION_BITS;
412 if (cache_data_len + newlen + 1 > CACHE_DATA_LEN)
413 return CACHE_RESAMPLING_NOTOK;
414 resrc.loop_start = ls = sp->loop_start;
415 resrc.loop_end = le = sp->loop_end;
416 resrc.data_length = sp->data_length;
417 ll = sp->loop_end - sp->loop_start;
418 dest = cache_data + cache_data_len;
419 src = sp->data;
420 newsp = (Sample *) new_segment(&hash_entry_pool, sizeof(Sample));
421 memcpy(newsp, sp, sizeof(Sample));
422 newsp->data = dest;
423 ofs = 0;
424 incr = (splen_t) (TIM_FSCALE(a, FRACTION_BITS) + 0.5);
425 if (sp->modes & MODES_LOOPING)
426 for (i = 0; i < newlen; i++) {
427 if (ofs >= le)
428 ofs -= ll;
429 RESAMPLATION_CACHE;
430 ofs += incr;
431 }
432 else
433 for (i = 0; i < newlen; i++) {
434 RESAMPLATION_CACHE;
435 ofs += incr;
436 }
437 newsp->loop_start = xls;
438 newsp->loop_end = xle;
439 newsp->data_length = newlen << FRACTION_BITS;
440 if (sp->modes & MODES_LOOPING)
441 loop_connect(dest, (int32) (xls >> FRACTION_BITS),
442 (int32) (xle >> FRACTION_BITS));
443 dest[xle >> FRACTION_BITS] = dest[xls >> FRACTION_BITS];
444 newsp->root_freq = get_note_freq(newsp, note);
445 newsp->sample_rate = play_mode->rate;
446 p->resampled = newsp;
447 cache_data_len += newlen + 1;
448 return CACHE_RESAMPLING_OK;
449 }
450
loop_connect(sample_t * data,int32 start,int32 end)451 static void loop_connect(sample_t *data, int32 start, int32 end)
452 {
453 int i, mixlen;
454 int32 t0, t1;
455
456 mixlen = MIXLEN;
457 if (start < mixlen)
458 mixlen = start;
459 if (end - start < mixlen)
460 mixlen = end - start;
461 if (mixlen <= 0)
462 return;
463 t0 = start - mixlen;
464 t1 = end - mixlen;
465 for (i = 0; i < mixlen; i++) {
466 double x, b;
467
468 b = i / (double) mixlen; /* 0 <= b < 1 */
469 x = b * data[t0 + i] + (1.0 - b) * data[t1 + i];
470 #ifdef LOOKUP_HACK
471 if (x < -128)
472 data[t1 + i] = -128;
473 else if (x > 127)
474 data[t1 + i] = 127;
475 #else
476 if (x < -32768)
477 data[t1 + i] = -32768;
478 else if (x > 32767)
479 data[t1 + i] = 32767;
480 #endif /* LOOKUP_HACK */
481 else
482 data[t1 + i] = (sample_t) x;
483 }
484 }
485
486