1/*
2 * Copyright (C) 2010 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/** Permute is a host tool to randomly permute an audio file.
18 *  It takes as input an ordinary .wav file and produces as output a
19 *  permuted .wav file and .map which can be given the seek torture test
20 *  located in seekTorture.c.  A build prerequisite is libsndfile;
21 *  see installation instructions at http://www.mega-nerd.com/libsndfile/
22 *  The format of the .map file is a sequence of lines, each of which is:
23 *     seek_position_in_ms  duration_in_ms
24 */
25
26
27#include <assert.h>
28#include <stdio.h>
29#include <stdlib.h>
30#include <string.h>
31#include <sndfile.h>
32
33
34/** Global variables */
35
36// command line options
37
38// mean length of each segment of the permutation, in seconds
39static double meanSegmentLengthSeconds = 5.0;
40// minimum length of each segment of the permutation, in seconds
41static double minSegmentLengthSeconds = 1.0;
42
43
44/** Describes each contiguous segment generated */
45
46typedef struct {
47    unsigned mFrameStart;
48    unsigned mFrameLength;
49    unsigned mPermutedStart;
50} Segment;
51
52
53/** Global state during the split phase */
54
55typedef struct {
56    // derived from command line options combined with file properties
57    unsigned mMinSegmentLengthFrames;
58    //unsigned mMeanSegmentLengthFrames;
59    unsigned mSegmentMax;   // maximum number of segments allowed
60    unsigned mSegmentCount; // number of segments generated so far
61    Segment *mSegmentArray; // storage for the segments [max]
62} State;
63
64
65/** Called by qsort as the comparison handler */
66
67static int qsortCompare(const void *x, const void *y)
68{
69    const Segment *x_ = (Segment *) x;
70    const Segment *y_ = (Segment *) y;
71    return x_->mFrameStart - y_->mFrameStart;
72}
73
74
75/** Split the specified range of frames, using the allowed budget of segments.
76 *  Returns the actual number of segments consumed.
77 */
78
79static unsigned split(State *s, unsigned frameStart, unsigned frameLength, unsigned segmentBudget)
80{
81    if (frameLength <= 0)
82        return 0;
83    assert(segmentBudget > 0);
84    if ((frameLength <= s->mMinSegmentLengthFrames*2) || (segmentBudget <= 1)) {
85        assert(s->mSegmentCount < s->mSegmentMax);
86        Segment *seg = &s->mSegmentArray[s->mSegmentCount++];
87        seg->mFrameStart = frameStart;
88        seg->mFrameLength = frameLength;
89        seg->mPermutedStart = ~0;
90        return 1;
91    }
92    // slop is how much wiggle room we have to play with
93    unsigned slop = frameLength - s->mMinSegmentLengthFrames*2;
94    assert(slop > 0);
95    // choose a random cut point within the slop region
96    unsigned r = rand() & 0x7FFFFFFF;
97    unsigned cut = r % slop;
98    unsigned leftStart = frameStart;
99    unsigned leftLength = s->mMinSegmentLengthFrames + cut;
100    unsigned rightStart = frameStart + leftLength;
101    unsigned rightLength = s->mMinSegmentLengthFrames + (slop - cut);
102    assert(leftLength + rightLength == frameLength);
103    // process the two sides in random order
104    assert(segmentBudget >= 2);
105    unsigned used;
106    if (leftLength <= rightLength) {
107        used = split(s, leftStart, leftLength, segmentBudget / 2);
108        used += split(s, rightStart, rightLength, segmentBudget - used);
109    } else {
110        used = split(s, rightStart, rightLength, segmentBudget / 2);
111        used += split(s, leftStart, leftLength, segmentBudget - used);
112    }
113    assert(used >= 2);
114    assert(used <= segmentBudget);
115    return used;
116}
117
118
119/** Permute the specified input file */
120
121void permute(char *path_in)
122{
123
124    // Open the file using libsndfile
125    SNDFILE *sf_in;
126    SF_INFO sfinfo_in;
127    sfinfo_in.format = 0;
128    sf_in = sf_open(path_in, SFM_READ, &sfinfo_in);
129    if (NULL == sf_in) {
130        perror(path_in);
131        return;
132    }
133
134    // Check if it is a supported file format: must be WAV
135    unsigned type = sfinfo_in.format & SF_FORMAT_TYPEMASK;
136    switch (type) {
137    case SF_FORMAT_WAV:
138        break;
139    default:
140        fprintf(stderr, "%s: unsupported type 0x%X\n", path_in, type);
141        goto out;
142    }
143
144    // Must be 16-bit signed or 8-bit unsigned PCM
145    unsigned subtype = sfinfo_in.format & SF_FORMAT_SUBMASK;
146    unsigned sampleSizeIn = 0;
147    switch (subtype) {
148    case SF_FORMAT_PCM_16:
149        sampleSizeIn = 2;
150        break;
151    case SF_FORMAT_PCM_U8:
152        sampleSizeIn = 1;
153        break;
154    default:
155        fprintf(stderr, "%s: unsupported subtype 0x%X\n", path_in, subtype);
156        goto out;
157    }
158    // always read shorts
159    unsigned sampleSizeRead = 2;
160
161    // Must be little-endian
162    unsigned endianness = sfinfo_in.format & SF_FORMAT_ENDMASK;
163    switch (endianness) {
164    case SF_ENDIAN_FILE:
165    case SF_ENDIAN_LITTLE:
166        break;
167    default:
168        fprintf(stderr, "%s: unsupported endianness 0x%X\n", path_in, endianness);
169        goto out;
170    }
171
172    // Must be a known sample rate
173    switch (sfinfo_in.samplerate) {
174    case 8000:
175    case 11025:
176    case 16000:
177    case 22050:
178    case 32000:
179    case 44100:
180    case 48000:
181        break;
182    default:
183        fprintf(stderr, "%s: unsupported sample rate %d\n", path_in, sfinfo_in.samplerate);
184        goto out;
185    }
186
187    // Must be either stereo or mono
188    unsigned frameSizeIn = 0;
189    unsigned frameSizeRead = 0;
190    switch (sfinfo_in.channels) {
191    case 1:
192    case 2:
193        frameSizeIn = sampleSizeIn * sfinfo_in.channels;
194        frameSizeRead = sampleSizeRead * sfinfo_in.channels;
195        break;
196    default:
197        fprintf(stderr, "%s: unsupported channels %d\n", path_in, sfinfo_in.channels);
198        goto out;
199    }
200
201    // Duration must be known
202    switch (sfinfo_in.frames) {
203    case (sf_count_t) 0:
204    case (sf_count_t) ~0:
205        fprintf(stderr, "%s: unsupported frames %d\n", path_in, (int) sfinfo_in.frames);
206        goto out;
207    default:
208        break;
209    }
210
211    // Allocate space to hold the audio data, based on duration
212    double durationSeconds = (double) sfinfo_in.frames / (double) sfinfo_in.samplerate;
213    State s;
214    s.mMinSegmentLengthFrames = minSegmentLengthSeconds * sfinfo_in.samplerate;
215    if (s.mMinSegmentLengthFrames <= 0)
216        s.mMinSegmentLengthFrames = 1;
217    s.mSegmentMax = durationSeconds / meanSegmentLengthSeconds;
218    if (s.mSegmentMax <= 0)
219        s.mSegmentMax = 1;
220    s.mSegmentCount = 0;
221    s.mSegmentArray = (Segment *) malloc(sizeof(Segment) * s.mSegmentMax);
222    assert(s.mSegmentArray != NULL);
223    unsigned used;
224    used = split(&s, 0, sfinfo_in.frames, s.mSegmentMax);
225    assert(used <= s.mSegmentMax);
226    assert(used == s.mSegmentCount);
227
228    // now permute the segments randomly using a bad algorithm
229    unsigned i;
230    for (i = 0; i < used; ++i) {
231        unsigned r = rand() & 0x7FFFFFFF;
232        unsigned j = r % used;
233        if (j != i) {
234            Segment temp = s.mSegmentArray[i];
235            s.mSegmentArray[i] = s.mSegmentArray[j];
236            s.mSegmentArray[j] = temp;
237        }
238    }
239
240    // read the entire file into memory
241    void *ptr = malloc(sfinfo_in.frames * frameSizeRead);
242    assert(NULL != ptr);
243    sf_count_t count;
244    count = sf_readf_short(sf_in, ptr, sfinfo_in.frames);
245    if (count != sfinfo_in.frames) {
246        fprintf(stderr, "%s: expected to read %d frames but actually read %d frames\n", path_in,
247            (int) sfinfo_in.frames, (int) count);
248        goto out;
249    }
250
251    // Create a permuted output file
252    char *path_out = malloc(strlen(path_in) + 8);
253    assert(path_out != NULL);
254    strcpy(path_out, path_in);
255    strcat(path_out, ".wav");
256    SNDFILE *sf_out;
257    SF_INFO sfinfo_out;
258    memset(&sfinfo_out, 0, sizeof(SF_INFO));
259    sfinfo_out.samplerate = sfinfo_in.samplerate;
260    sfinfo_out.channels = sfinfo_in.channels;
261    sfinfo_out.format = sfinfo_in.format;
262    sf_out = sf_open(path_out, SFM_WRITE, &sfinfo_out);
263    if (sf_out == NULL) {
264        perror(path_out);
265        goto out;
266    }
267    unsigned permutedStart = 0;
268    for (i = 0; i < used; ++i) {
269        s.mSegmentArray[i].mPermutedStart = permutedStart;
270        count = sf_writef_short(sf_out, &((short *) ptr)[sfinfo_in.channels * s.mSegmentArray[i]
271            .mFrameStart], s.mSegmentArray[i].mFrameLength);
272        if (count != s.mSegmentArray[i].mFrameLength) {
273            fprintf(stderr, "%s: expected to write %d frames but actually wrote %d frames\n",
274                path_out, (int) s.mSegmentArray[i].mFrameLength, (int) count);
275            break;
276        }
277        permutedStart += s.mSegmentArray[i].mFrameLength;
278    }
279    assert(permutedStart == sfinfo_in.frames);
280    sf_close(sf_out);
281
282    // now create a seek map to let us play this back in a reasonable order
283    qsort((void *) s.mSegmentArray, used, sizeof(Segment), qsortCompare);
284    char *path_map = malloc(strlen(path_in) + 8);
285    assert(path_map != NULL);
286    strcpy(path_map, path_in);
287    strcat(path_map, ".map");
288    FILE *fp_map = fopen(path_map, "w");
289    if (fp_map == NULL) {
290        perror(path_map);
291    } else {
292        for (i = 0; i < used; ++i)
293            fprintf(fp_map, "%u %u\n", (unsigned) ((s.mSegmentArray[i].mPermutedStart * 1000.0) /
294                sfinfo_in.samplerate), (unsigned) ((s.mSegmentArray[i].mFrameLength * 1000.0) /
295                sfinfo_in.samplerate));
296        fclose(fp_map);
297    }
298
299out:
300    // Close the input file
301    sf_close(sf_in);
302}
303
304
305// main program
306
307int main(int argc, char **argv)
308{
309    int i;
310    for (i = 1; i < argc; ++i) {
311        char *arg = argv[i];
312
313        // process command line options
314        if (!strncmp(arg, "-m", 2)) {
315            double mval = atof(&arg[2]);
316            if (mval >= 0.1 && mval <= 1000.0)
317                minSegmentLengthSeconds = mval;
318            else
319                fprintf(stderr, "%s: invalid value %s\n", argv[0], arg);
320            continue;
321        }
322        if (!strncmp(arg, "-s", 2)) {
323            double sval = atof(&arg[2]);
324            if (sval >= 0.1 && sval <= 1000.0)
325                meanSegmentLengthSeconds = sval;
326            else
327                fprintf(stderr, "%s: invalid value %s\n", argv[0], arg);
328            continue;
329        }
330        if (!strncmp(arg, "-r", 2)) {
331            srand(atoi(&arg[2]));
332            continue;
333        }
334        if (meanSegmentLengthSeconds < minSegmentLengthSeconds)
335            meanSegmentLengthSeconds = minSegmentLengthSeconds * 2.0;
336
337        // Permute the file
338        permute(arg);
339
340    }
341    return EXIT_SUCCESS;
342}
343