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 cache_data = 0;
91 reuse_mblock(&hash_entry_pool);
92 }
93
resamp_cache_reset(void)94 void resamp_cache_reset(void)
95 {
96 if (cache_data == NULL) {
97 cache_data = (sample_t *)
98 safe_large_malloc((CACHE_DATA_LEN + 1) * sizeof(sample_t));
99 memset(cache_data, 0, (CACHE_DATA_LEN + 1) * sizeof(sample_t));
100 init_mblock(&hash_entry_pool);
101 }
102 cache_data_len = 0;
103 memset(cache_hash_table, 0, sizeof(cache_hash_table));
104 memset(channel_note_table, 0, sizeof(channel_note_table));
105 reuse_mblock(&hash_entry_pool);
106 }
107
resamp_cache_fetch(Sample * sp,int note)108 struct cache_hash *resamp_cache_fetch(Sample *sp, int note)
109 {
110 unsigned int addr;
111 struct cache_hash *p;
112
113 if (sp->vibrato_control_ratio || (sp->modes & MODES_PINGPONG)
114 || (sp->sample_rate == play_mode->rate
115 && sp->root_freq == get_note_freq(sp, sp->note_to_use)))
116 return NULL;
117 addr = sp_hash(sp, note) % HASH_TABLE_SIZE;
118 p = cache_hash_table[addr];
119 while (p && (p->note != note || p->sp != sp))
120 p = p->next;
121 if (p && p->resampled != NULL)
122 return p;
123 return NULL;
124 }
125
resamp_cache_refer_on(Voice * vp,int32 sample_start)126 void resamp_cache_refer_on(Voice *vp, int32 sample_start)
127 {
128 unsigned int addr;
129 struct cache_hash *p;
130 int note, ch;
131
132 ch = vp->channel;
133 if (vp->vibrato_control_ratio || channel[ch].portamento
134 || (vp->sample->modes & MODES_PINGPONG)
135 || vp->orig_frequency != vp->frequency
136 || (vp->sample->sample_rate == play_mode->rate
137 && vp->sample->root_freq
138 == get_note_freq(vp->sample, vp->sample->note_to_use)))
139 return;
140 note = vp->note;
141 if (channel_note_table[ch].cache[note])
142 resamp_cache_refer_off(ch, note, sample_start);
143 addr = sp_hash(vp->sample, note) % HASH_TABLE_SIZE;
144 p = cache_hash_table[addr];
145 while (p && (p->note != note || p->sp != vp->sample))
146 p = p->next;
147 if (! p) {
148 p = (struct cache_hash *)
149 new_segment(&hash_entry_pool, sizeof(struct cache_hash));
150 p->cnt = 0;
151 p->note = vp->note;
152 p->sp = vp->sample;
153 p->resampled = NULL;
154 p->next = cache_hash_table[addr];
155 cache_hash_table[addr] = p;
156 }
157 channel_note_table[ch].cache[note] = p;
158 channel_note_table[ch].on[note] = sample_start;
159 }
160
resamp_cache_refer_off(int ch,int note,int32 sample_end)161 void resamp_cache_refer_off(int ch, int note, int32 sample_end)
162 {
163 int32 sample_start, len;
164 struct cache_hash *p;
165 Sample *sp;
166
167 p = channel_note_table[ch].cache[note];
168 if (p == NULL)
169 return;
170 sp = p->sp;
171 if (sp->sample_rate == play_mode->rate
172 && sp->root_freq == get_note_freq(sp, sp->note_to_use))
173 return;
174 sample_start = channel_note_table[ch].on[note];
175 len = sample_end - sample_start;
176 if (len < 0) {
177 channel_note_table[ch].cache[note] = NULL;
178 return;
179 }
180 if (! (sp->modes & MODES_LOOPING)) {
181 double a;
182 int32 slen;
183
184 a = ((double) sp->root_freq * play_mode->rate)
185 / ((double) sp->sample_rate * get_note_freq(sp, note));
186 slen = (int32) ((sp->data_length >> FRACTION_BITS) * a);
187 if (len > slen)
188 len = slen;
189 }
190 p->cnt += len;
191 channel_note_table[ch].cache[note] = NULL;
192 }
193
resamp_cache_refer_alloff(int ch,int32 sample_end)194 void resamp_cache_refer_alloff(int ch, int32 sample_end)
195 {
196 int i;
197
198 for (i = 0; i < 128; i++)
199 resamp_cache_refer_off(ch, i, sample_end);
200 }
201
resamp_cache_create(void)202 void resamp_cache_create(void)
203 {
204 int i, skip;
205 int32 n, t1, t2, total;
206 struct cache_hash **array;
207
208 /* It is NP completion that solve the best cache hit rate.
209 * So I thought better algorism O(n log n), but not a best solution.
210 * Follows implementation takes good hit rate, and it is fast.
211 */
212 n = t1 = t2 = 0;
213 total = 0;
214 /* set size per count */
215 for (i = 0; i < HASH_TABLE_SIZE; i++) {
216 struct cache_hash *p, *q;
217
218 p = cache_hash_table[i], q = NULL;
219 while (p) {
220 struct cache_hash *tmp;
221
222 t1 += p->cnt;
223 tmp = p, p = p->next;
224 if (tmp->cnt > 0) {
225 Sample *sp;
226 splen_t newlen;
227
228 sp = tmp->sp;
229 sample_resamp_info(sp, tmp->note, NULL, NULL, &newlen);
230 if (newlen > 0) {
231 total += tmp->cnt;
232 tmp->r = (double) newlen / tmp->cnt;
233 tmp->next = q, q = tmp;
234 n++;
235 }
236 }
237 }
238 cache_hash_table[i] = q;
239 }
240 if (n == 0) {
241 ctl->cmsg(CMSG_INFO, VERB_VERBOSE, "No pre-resampling cache hit");
242 return;
243 }
244 array = (struct cache_hash **) new_segment(&hash_entry_pool,
245 n * sizeof(struct cache_hash *));
246 n = 0;
247 for (i = 0; i < HASH_TABLE_SIZE; i++) {
248 struct cache_hash *p;
249
250 for (p = cache_hash_table[i]; p; p = p->next)
251 array[n++] = p;
252 }
253 if (total > CACHE_DATA_LEN)
254 qsort_cache_array(array, 0, n - 1);
255 skip = 0;
256 for (i = 0; i < n; i++) {
257 if (array[i]->r != 0
258 && cache_resampling(array[i]) == CACHE_RESAMPLING_OK)
259 t2 += array[i]->cnt;
260 else
261 skip++;
262 }
263 ctl->cmsg(CMSG_INFO, VERB_NOISY,
264 "Resample cache: Key %d/%d(%.1f%%) Sample %.1f%c/%.1f%c(%.1f%%)",
265 n - skip, n, 100.0 * (n - skip) / n,
266 t2 / ((t2 >= 1048576) ? 1048576.0 : 1024.0),
267 (t2 >= 1048576) ? 'M' : 'K',
268 t1 / ((t1 >= 1048576) ? 1048576.0 : 1024.0),
269 (t1 >= 1048576) ? 'M' : 'K',
270 100.0 * t2 / t1);
271 /* update cache_hash_table */
272 if (skip)
273 for (i = 0; i < HASH_TABLE_SIZE; i++) {
274 struct cache_hash *p, *q;
275
276 p = cache_hash_table[i], q = NULL;
277 while (p) {
278 struct cache_hash *tmp;
279
280 tmp = p, p = p->next;
281 if (tmp->resampled)
282 tmp->next = q, q = tmp;
283 }
284 cache_hash_table[i] = q;
285 }
286 }
287
sample_resamp_info(Sample * sp,int note,splen_t * loop_start,splen_t * loop_end,splen_t * data_length)288 static double sample_resamp_info(Sample *sp, int note,
289 splen_t *loop_start, splen_t *loop_end, splen_t *data_length)
290 {
291 splen_t xls, xle, ls, le, ll, newlen;
292 double a, xxls, xxle, xn;
293
294 a = ((double) sp->sample_rate * get_note_freq(sp, note))
295 / ((double) sp->root_freq * play_mode->rate);
296 a = TIM_FSCALENEG((double) (int32) TIM_FSCALE(a, FRACTION_BITS),
297 FRACTION_BITS);
298 xn = sp->data_length / a;
299 if (xn >= SPLEN_T_MAX) {
300 /* Ignore this sample */
301 *data_length = 0;
302 return 0.0;
303 }
304 newlen = (splen_t) (TIM_FSCALENEG(xn, FRACTION_BITS) + 0.5);
305 ls = sp->loop_start;
306 le = sp->loop_end;
307 ll = le - ls;
308 xxls = ls / a + 0.5;
309 if (xxls >= SPLEN_T_MAX) {
310 /* Ignore this sample */
311 *data_length = 0;
312 return 0.0;
313 }
314 xls = (splen_t) xxls;
315 xxle = le / a + 0.5;
316 if (xxle >= SPLEN_T_MAX) {
317 /* Ignore this sample */
318 *data_length = 0;
319 return 0.0;
320 }
321 xle = (splen_t) xxle;
322 if ((sp->modes & MODES_LOOPING)
323 && ((xle - xls) >> FRACTION_BITS) < MIN_LOOPLEN) {
324 splen_t n;
325 splen_t newxle;
326 double xl; /* Resampled new loop length */
327 double xnewxle;
328
329 xl = ll / a;
330 if (xl >= SPLEN_T_MAX) {
331 /* Ignore this sample */
332 *data_length = 0;
333 return 0.0;
334 }
335 n = (splen_t) (0.0001 + MIN_LOOPLEN
336 / TIM_FSCALENEG(xl, FRACTION_BITS)) + 1;
337 xnewxle = le / a + n * xl + 0.5;
338 if (xnewxle >= SPLEN_T_MAX) {
339 /* Ignore this sample */
340 *data_length = 0;
341 return 0.0;
342 }
343 newxle = (splen_t) xnewxle;
344 newlen += (newxle - xle) >> FRACTION_BITS;
345 xle = newxle;
346 }
347 if (loop_start)
348 *loop_start = (splen_t) (xls & ~FRACTION_MASK);
349 if (loop_end)
350 *loop_end = (splen_t) (xle & ~FRACTION_MASK);
351 *data_length = newlen << FRACTION_BITS;
352 return a;
353 }
354
qsort_cache_array(struct cache_hash ** a,long first,long last)355 static void qsort_cache_array(struct cache_hash **a, long first, long last)
356 {
357 long i = first, j = last;
358 struct cache_hash *x, *t;
359
360 if (j - i < SORT_THRESHOLD) {
361 insort_cache_array(a + i, j - i + 1);
362 return;
363 }
364 x = a[(first + last) / 2];
365 for (;;) {
366 while (a[i]->r < x->r)
367 i++;
368 while (x->r < a[j]->r)
369 j--;
370 if (i >= j)
371 break;
372 t = a[i], a[i] = a[j], a[j] = t;
373 i++, j--;
374 }
375 if (first < i - 1)
376 qsort_cache_array(a, first, i - 1);
377 if (j + 1 < last)
378 qsort_cache_array(a, j + 1, last);
379 }
380
insort_cache_array(struct cache_hash ** data,long n)381 static void insort_cache_array(struct cache_hash **data, long n)
382 {
383 long i, j;
384 struct cache_hash *x;
385
386 for (i = 1; i < n; i++) {
387 x = data[i];
388 for (j = i - 1; j >= 0 && x->r < data[j]->r; j--)
389 data[j + 1] = data[j];
390 data[j + 1] = x;
391 }
392 }
393
cache_resampling(struct cache_hash * p)394 static int cache_resampling(struct cache_hash *p)
395 {
396 Sample *sp, *newsp;
397 sample_t *src, *dest;
398 splen_t newlen, ofs, le, ls, ll, xls, xle;
399 int32 i, incr, _x;
400 resample_rec_t resrc;
401 double a;
402 int8 note;
403
404 sp = p->sp;
405 if (sp->note_to_use)
406 note = sp->note_to_use;
407 else
408 note = p->note;
409 a = sample_resamp_info(sp, note, &xls, &xle, &newlen);
410 if (newlen == 0)
411 return CACHE_RESAMPLING_NOTOK;
412 newlen >>= FRACTION_BITS;
413 if (cache_data_len + newlen + 1 > CACHE_DATA_LEN)
414 return CACHE_RESAMPLING_NOTOK;
415 resrc.loop_start = ls = sp->loop_start;
416 resrc.loop_end = le = sp->loop_end;
417 resrc.data_length = sp->data_length;
418 ll = sp->loop_end - sp->loop_start;
419 dest = cache_data + cache_data_len;
420 src = sp->data;
421 newsp = (Sample *) new_segment(&hash_entry_pool, sizeof(Sample));
422 memcpy(newsp, sp, sizeof(Sample));
423 newsp->data = dest;
424 ofs = 0;
425 incr = (splen_t) (TIM_FSCALE(a, FRACTION_BITS) + 0.5);
426 if (sp->modes & MODES_LOOPING)
427 for (i = 0; i < newlen; i++) {
428 if (ofs >= le)
429 ofs -= ll;
430 RESAMPLATION_CACHE;
431 ofs += incr;
432 }
433 else
434 for (i = 0; i < newlen; i++) {
435 RESAMPLATION_CACHE;
436 ofs += incr;
437 }
438 newsp->loop_start = xls;
439 newsp->loop_end = xle;
440 newsp->data_length = newlen << FRACTION_BITS;
441 if (sp->modes & MODES_LOOPING)
442 loop_connect(dest, (int32) (xls >> FRACTION_BITS),
443 (int32) (xle >> FRACTION_BITS));
444 dest[xle >> FRACTION_BITS] = dest[xls >> FRACTION_BITS];
445 newsp->root_freq = get_note_freq(newsp, note);
446 newsp->sample_rate = play_mode->rate;
447 p->resampled = newsp;
448 cache_data_len += newlen + 1;
449 return CACHE_RESAMPLING_OK;
450 }
451
loop_connect(sample_t * data,int32 start,int32 end)452 static void loop_connect(sample_t *data, int32 start, int32 end)
453 {
454 int i, mixlen;
455 int32 t0, t1;
456
457 mixlen = MIXLEN;
458 if (start < mixlen)
459 mixlen = start;
460 if (end - start < mixlen)
461 mixlen = end - start;
462 if (mixlen <= 0)
463 return;
464 t0 = start - mixlen;
465 t1 = end - mixlen;
466 for (i = 0; i < mixlen; i++) {
467 double x, b;
468
469 b = i / (double) mixlen; /* 0 <= b < 1 */
470 x = b * data[t0 + i] + (1.0 - b) * data[t1 + i];
471 #ifdef LOOKUP_HACK
472 if (x < -128)
473 data[t1 + i] = -128;
474 else if (x > 127)
475 data[t1 + i] = 127;
476 #else
477 if (x < -32768)
478 data[t1 + i] = -32768;
479 else if (x > 32767)
480 data[t1 + i] = 32767;
481 #endif /* LOOKUP_HACK */
482 else
483 data[t1 + i] = (sample_t) x;
484 }
485 }
486
487