Home | History | Annotate | Download | only in permute 
      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
     39 static double meanSegmentLengthSeconds = 5.0;
     40 // minimum length of each segment of the permutation, in seconds
     41 static double minSegmentLengthSeconds = 1.0;
     42 
     43 
     44 /** Describes each contiguous segment generated */
     45 
     46 typedef struct {
     47     unsigned mFrameStart;
     48     unsigned mFrameLength;
     49     unsigned mPermutedStart;
     50 } Segment;
     51 
     52 
     53 /** Global state during the split phase */
     54 
     55 typedef 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 
     67 static 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 
     79 static 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 
    121 void 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 
    299 out:
    300     // Close the input file
    301     sf_close(sf_in);
    302 }
    303 
    304 
    305 // main program
    306 
    307 int 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