Major rework of the m4a parser for aac/alac playback, seek and resume support. As a result the memory consumption was drastically reduced. This allows to play several files with long duration -- especially on low memory targets. The change builds a lookup table from m4a's sample_to_chunk[] and chunk_offset[] and completely removes the allocation of the large tables chunk_offset[] and sample_byte_size[]. To be able to remove reading and allocating sample_byte_offset[] the aac and alac decoder now buffer a fixed amount of bytes for each frame. The generated lookup table is used for seek/resume and skipping bytes in empty chunks (aac decoder only). The precision for seek/resume is somewhat lower but still equals 0.5 sec for the worst case. Fixes FS#8923.

git-svn-id: svn://svn.rockbox.org/rockbox/trunk@29745 a1c6a512-1295-4272-9138-f99709370657

5 files changed, 133 insertions, 241 deletions

diff --git a/apps/codecs/aac.c b/apps/codecs/aac.c
index 849d87bedf..6bb5ac50ae 100644
--- a/apps/codecs/aac.c
+++ b/apps/codecs/aac.c
@@ -27,6 +27,11 @@
 
 CODEC_HEADER
 
+/* The maximum buffer size handled by faad. 12 bytes are required by libfaad
+ * as headroom (see libfaad/bits.c). FAAD_BYTE_BUFFER_SIZE bytes are buffered 
+ * for each frame. */
+#define FAAD_BYTE_BUFFER_SIZE (2048-12)
+
 /* Global buffers to be used in the mdct synthesis. This way the arrays can
  * be moved to IRAM for some targets */
 #define GB_BUF_SIZE 1024
@@ -159,7 +164,7 @@ next_track:
         /* Resume the desired (byte) position. Important: When resuming SBR
          * upsampling files the resulting sound_samples_done must be expanded 
          * by a factor of 2. This is done via using sbr_fac. */
-        if (alac_seek_raw(&demux_res, &input_stream, file_offset,
+        if (m4a_seek_raw(&demux_res, &input_stream, file_offset,
                           &sound_samples_done, (int*) &i)) {
             sound_samples_done *= sbr_fac;
             elapsed_time = (sound_samples_done * 10) / (ci->id3->frequency / 100);
@@ -188,9 +193,9 @@ next_track:
         if (ci->seek_time) {
             /* Seek to the desired time position. Important: When seeking in SBR
              * upsampling files the seek_time must be divided by 2 when calling 
-             * alac_seek and the resulting sound_samples_done must be expanded 
+             * m4a_seek and the resulting sound_samples_done must be expanded 
              * by a factor 2. This is done via using sbr_fac. */
-            if (alac_seek(&demux_res, &input_stream,
+            if (m4a_seek(&demux_res, &input_stream,
                           ((ci->seek_time-1)/10/sbr_fac)*(ci->id3->frequency/100),
                           &sound_samples_done, (int*) &i)) {
                 sound_samples_done *= sbr_fac;
@@ -211,7 +216,7 @@ next_track:
          * that an good question (but files with gaps do exist, so who 
          * knows?), so we don't support that - for now, at least.
          */    
-        file_offset = get_sample_offset(&demux_res, i);
+        file_offset = m4a_check_sample_offset(&demux_res, i);
 
         if (file_offset > ci->curpos)
         {
@@ -225,7 +230,7 @@ next_track:
         }
         
         /* Request the required number of bytes from the input buffer */
-        buffer=ci->request_buffer(&n, demux_res.sample_byte_size[i]);
+        buffer=ci->request_buffer(&n, FAAD_BYTE_BUFFER_SIZE);
 
         /* Decode one block - returned samples will be host-endian */
         ret = NeAACDecDecode(decoder, &frame_info, buffer, n);
diff --git a/apps/codecs/alac.c b/apps/codecs/alac.c
index 428fc59836..cd9129a278 100644
--- a/apps/codecs/alac.c
+++ b/apps/codecs/alac.c
@@ -25,6 +25,10 @@
 
 CODEC_HEADER
 
+/* The maximum buffer size handled. This amount of bytes is buffered for each 
+ * frame. */
+#define ALAC_BYTE_BUFFER_SIZE 32768
+
 static int32_t outputbuffer[ALAC_MAX_CHANNELS][ALAC_BLOCKSIZE] IBSS_ATTR;
 
 /* this is the codec entry point */
@@ -83,7 +87,7 @@ enum codec_status codec_main(void)
   /* Set i for first frame, seek to desired sample position for resuming. */
   i=0;
   if (samplesdone > 0) {
-    if (alac_seek(&demux_res, &input_stream, samplesdone,
+    if (m4a_seek(&demux_res, &input_stream, samplesdone,
                   &samplesdone, (int*) &i)) {
         elapsedtime = (samplesdone * 10) / (ci->id3->frequency / 100);
         ci->set_elapsed(elapsedtime);
@@ -101,7 +105,7 @@ enum codec_status codec_main(void)
 
     /* Deal with any pending seek requests */
     if (ci->seek_time) {
-      if (alac_seek(&demux_res, &input_stream,
+      if (m4a_seek(&demux_res, &input_stream,
                     ((ci->seek_time-1)/10) * (ci->id3->frequency/100),
                     &samplesdone, (int *)&i)) {
         elapsedtime=(samplesdone*10)/(ci->id3->frequency/100);
@@ -111,11 +115,7 @@ enum codec_status codec_main(void)
     }
 
     /* Request the required number of bytes from the input buffer */
-    buffer=ci->request_buffer(&n, demux_res.sample_byte_size[i]);
-    if (n!=demux_res.sample_byte_size[i]) {
-        retval = CODEC_ERROR;
-        goto done;
-    }
+    buffer=ci->request_buffer(&n, ALAC_BYTE_BUFFER_SIZE);
 
     /* Decode one block - returned samples will be host-endian */
     ci->yield();
diff --git a/apps/codecs/libm4a/demux.c b/apps/codecs/libm4a/demux.c
index e584c37858..1b8deab602 100644
--- a/apps/codecs/libm4a/demux.c
+++ b/apps/codecs/libm4a/demux.c
@@ -354,8 +354,6 @@ static bool read_chunk_stts(qtmovie_t *qtmovie, size_t chunk_len)
 
 static bool read_chunk_stsz(qtmovie_t *qtmovie, size_t chunk_len)
 {
-    unsigned int i;
-    uint32_t numentries;
     size_t size_remaining = chunk_len - 8;
 
     /* version */
@@ -377,35 +375,11 @@ static bool read_chunk_stsz(qtmovie_t *qtmovie, size_t chunk_len)
     }
     size_remaining -= 4;
 
-    numentries = stream_read_uint32(qtmovie->stream);
+    qtmovie->res->num_sample_byte_sizes = stream_read_uint32(qtmovie->stream);
     size_remaining -= 4;
 
-    qtmovie->res->num_sample_byte_sizes = numentries;
-    qtmovie->res->sample_byte_size = malloc(numentries * sizeof(*qtmovie->res->sample_byte_size));
-
-    if (!qtmovie->res->sample_byte_size)
-    {
-        DEBUGF("stsz too large\n");
-        return false;
-    }
-
-    for (i = 0; i < numentries; i++)
-    {
-        uint32_t v = stream_read_uint32(qtmovie->stream);
-        
-        if (v > 0x0000ffff)
-        {
-            DEBUGF("stsz[%d] > 65 kB (%ld)\n", i, (long)v);
-            return false;
-        }
-        
-        qtmovie->res->sample_byte_size[i] = v;
-        size_remaining -= 4;
-    }
-
     if (size_remaining)
     {
-        DEBUGF("ehm, size remianing?\n");
         stream_skip(qtmovie->stream, size_remaining);
     }
     
@@ -426,8 +400,7 @@ static bool read_chunk_stsc(qtmovie_t *qtmovie, size_t chunk_len)
     size_remaining -= 4;
 
     qtmovie->res->num_sample_to_chunks = numentries;
-    qtmovie->res->sample_to_chunk = malloc(numentries *
-        sizeof(*qtmovie->res->sample_to_chunk));
+    qtmovie->res->sample_to_chunk = malloc(numentries * sizeof(sample_to_chunk_t));
 
     if (!qtmovie->res->sample_to_chunk)
     {
@@ -456,8 +429,14 @@ static bool read_chunk_stsc(qtmovie_t *qtmovie, size_t chunk_len)
 
 static bool read_chunk_stco(qtmovie_t *qtmovie, size_t chunk_len)
 {
-    unsigned int i;
+    uint32_t i, k;
     uint32_t numentries;
+    int32_t idx = 0;
+    int32_t frame;
+    int32_t offset;
+    int32_t old_first;
+    int32_t new_first;
+    int32_t old_frame;
     size_t size_remaining = chunk_len - 8;
 
     /* version + flags */
@@ -466,20 +445,57 @@ static bool read_chunk_stco(qtmovie_t *qtmovie, size_t chunk_len)
 
     numentries = stream_read_uint32(qtmovie->stream);
     size_remaining -= 4;
+  
+    qtmovie->res->num_lookup_table = numentries;
+    qtmovie->res->lookup_table = malloc(numentries * sizeof(*qtmovie->res->lookup_table));
 
-    qtmovie->res->num_chunk_offsets = numentries;
-    qtmovie->res->chunk_offset = malloc(numentries * 
-        sizeof(*qtmovie->res->chunk_offset));
-
-    if (!qtmovie->res->chunk_offset)
+    if (!qtmovie->res->lookup_table)
     {
-        DEBUGF("stco too large\n");
+        DEBUGF("stco too large to allocate lookup_table[]\n");
         return false;
     }
 
-    for (i = 0; i < numentries; i++)
+    /* read first offset */
+    offset = stream_read_uint32(qtmovie->stream);
+    size_remaining -= 4;
+    
+    /* Build up lookup table. The lookup table contains the sample index and
+     * byte position in the file for each chunk. This table is used to seek
+     * and resume (see m4a_seek() and m4a_seek_raw() in libm4a/m4a.c) and 
+     * to skip empty chunks (see m4a_check_sample_offset() in codecs/aac.c and
+     * libm4a/m4a.c).
+     * The seek/resume precision is lower than using sample_byte_size[] and 
+     * depends on numentries. Typically the resolution is ~1/10 of all frames
+     * which equals about 1/4-1/2 seconds. The loss of seek precision is 
+     * accepted to be able to avoid allocation of the large sample_byte_size[] 
+     * table. This reduces the memory consumption by a factor of 2 or even 
+     * more. */
+    i = 1;
+    frame = 0;
+    old_frame = qtmovie->res->sample_to_chunk[0].num_samples;
+    old_first = qtmovie->res->sample_to_chunk[0].first_chunk;
+    for (k = 1; k < numentries; ++k)
     {
-        qtmovie->res->chunk_offset[i] = stream_read_uint32(qtmovie->stream);
+        for (; i < qtmovie->res->num_sample_to_chunks; ++i)
+        {
+            old_frame = qtmovie->res->sample_to_chunk[i-1].num_samples;
+            old_first = qtmovie->res->sample_to_chunk[i-1].first_chunk;
+            new_first = qtmovie->res->sample_to_chunk[i  ].first_chunk;
+            
+            if (qtmovie->res->sample_to_chunk[i].first_chunk > k)
+                break;
+            
+            frame += (new_first - old_first) * old_frame;
+        }
+        frame += (k - old_first) * old_frame;
+        
+        qtmovie->res->lookup_table[idx].sample = frame;
+        qtmovie->res->lookup_table[idx].offset = offset;
+        idx++;
+        
+        frame -= (k - old_first) * old_frame;
+        
+        offset = stream_read_uint32(qtmovie->stream);
         size_remaining -= 4;
     }
 
diff --git a/apps/codecs/libm4a/m4a.c b/apps/codecs/libm4a/m4a.c
index 8c4b172bc2..836cdafda3 100644
--- a/apps/codecs/libm4a/m4a.c
+++ b/apps/codecs/libm4a/m4a.c
@@ -7,7 +7,7 @@
  *                     \/            \/     \/    \/            \/
  * $Id$
  *
- * Copyright (C) 2005 Dave Chapman
+ * Copyright (C) 2005 Dave Chapman, 2011 Andree Buschmann
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License
@@ -122,148 +122,46 @@ void stream_create(stream_t *stream,struct codec_api* ci)
     stream->eof=0;
 }
 
-/* This function was part of the original alac decoder implementation */
-
-int get_sample_info(demux_res_t *demux_res, uint32_t samplenum,
-                           uint32_t *sample_duration,
-                           uint32_t *sample_byte_size)
+/* Check if there is a dedicated byte position contained for the given frame.
+ * Return this byte position in case of success or return -1. This allows to
+ * skip empty samples. */
+int m4a_check_sample_offset(demux_res_t *demux_res, uint32_t frame)
 {
-    unsigned int duration_index_accum = 0;
-    unsigned int duration_cur_index = 0;
-
-    if (samplenum >= demux_res->num_sample_byte_sizes) { 
-        return 0;
-    }
-
-    if (!demux_res->num_time_to_samples) {
-        return 0;
-    }
-
-    while ((demux_res->time_to_sample[duration_cur_index].sample_count
-            + duration_index_accum) <= samplenum) {
-        duration_index_accum +=
-        demux_res->time_to_sample[duration_cur_index].sample_count;
-
-        duration_cur_index++;
-        if (duration_cur_index >= demux_res->num_time_to_samples) {
-            return 0;
-        }
+    uint32_t i = 0;
+    for (i=0; i<demux_res->num_lookup_table; ++i)
+    {
+        if (demux_res->lookup_table[i].sample > frame ||
+            demux_res->lookup_table[i].offset == 0)
+            return -1;
+        if (demux_res->lookup_table[i].sample == frame)
+            break;
     }
-
-    *sample_duration =
-     demux_res->time_to_sample[duration_cur_index].sample_duration;
-    *sample_byte_size = demux_res->sample_byte_size[samplenum];
-
-    return 1;
+    return demux_res->lookup_table[i].offset;
 }
 
-unsigned int get_sample_offset(demux_res_t *demux_res, uint32_t sample)
+/* Find the exact or preceding frame in lookup_table[]. Return both frame
+ * and byte position of this match. */
+static void gather_offset(demux_res_t *demux_res, uint32_t *frame, uint32_t *offset)
 {
-    uint32_t chunk = 1;
-    uint32_t range_samples = 0;
-    uint32_t total_samples = 0;
-    uint32_t chunk_sample;
-    uint32_t prev_chunk;
-    uint32_t prev_chunk_samples;
-    uint32_t file_offset;
-    uint32_t i;
-    
-    /* First check we have the appropriate metadata - we should always
-     * have it.
-     */
-       
-    if (sample >= demux_res->num_sample_byte_sizes ||
-        !demux_res->num_sample_to_chunks ||
-        !demux_res->num_chunk_offsets) 
-    {
-        return 0;
-    }
-
-    /* Locate the chunk containing the sample */
-    
-    prev_chunk = demux_res->sample_to_chunk[0].first_chunk;
-    prev_chunk_samples = demux_res->sample_to_chunk[0].num_samples;
-
-    for (i = 1; i < demux_res->num_sample_to_chunks; i++) 
+    uint32_t i = 0;
+    for (i=0; i<demux_res->num_lookup_table; ++i)
     {
-        chunk = demux_res->sample_to_chunk[i].first_chunk;
-        range_samples = (chunk - prev_chunk) * prev_chunk_samples;
-
-        if (sample < total_samples + range_samples)
-        {
+        if (demux_res->lookup_table[i].offset == 0)
+            break;
+        if (demux_res->lookup_table[i].sample > *frame)
             break;
-        }
-
-        total_samples += range_samples;
-        prev_chunk = demux_res->sample_to_chunk[i].first_chunk;
-        prev_chunk_samples = demux_res->sample_to_chunk[i].num_samples;
-    }
-
-    if (prev_chunk_samples > 0 &&
-        sample >= demux_res->sample_to_chunk[0].num_samples)
-    {
-        chunk = prev_chunk + (sample - total_samples) / prev_chunk_samples;
-    }
-    else
-    {
-        chunk = 1;
-    }
-    
-    /* Get sample of the first sample in the chunk */
-    
-    chunk_sample = total_samples + (chunk - prev_chunk) * prev_chunk_samples;
-    
-    /* Get offset in file */
-    
-    if (chunk > demux_res->num_chunk_offsets)
-    {
-        file_offset = demux_res->chunk_offset[demux_res->num_chunk_offsets - 1];
-    }
-    else
-    {
-        file_offset = demux_res->chunk_offset[chunk - 1];
-    }
-    
-    if (chunk_sample > sample) 
-    {
-        return 0;
-    }
- 
-    for (i = chunk_sample; i < sample; i++)
-    {
-        file_offset += demux_res->sample_byte_size[i];
-    }
-    
-    if (file_offset > demux_res->mdat_offset + demux_res->mdat_len)
-    {
-        return 0;
     }
-    
-    return file_offset;
+    i = (i>0) ? i-1 : 0; /* We want the last chunk _before_ *frame. */
+    *frame  = demux_res->lookup_table[i].sample;
+    *offset = demux_res->lookup_table[i].offset;
 }
 
-/* Seek to the sample containing sound_sample_loc. Return 1 on success 
- * (and modify sound_samples_done and current_sample), 0 if failed.
- *
- * Seeking uses the following arrays:
- *
- * 1) the time_to_sample array contains the duration (in sound samples) 
- *    of each sample of data.
- *
- * 2) the sample_byte_size array contains the length in bytes of each
- *    sample.
- *
- * 3) the sample_to_chunk array contains information about which chunk
- *    of samples each sample belongs to.
- *
- * 4) the chunk_offset array contains the file offset of each chunk.
- *
- * So find the sample number we are going to seek to (using time_to_sample)
- * and then find the offset in the file (using sample_to_chunk, 
- * chunk_offset sample_byte_size, in that order.).
+/* Seek to desired sound sample location. Return 1 on success (and modify
+ * sound_samples_done and current_sample), 0 if failed.
  *
- */
-unsigned int alac_seek(demux_res_t* demux_res, stream_t* stream, 
+ * Find the sample (=frame) that contains the given sound sample, find a best
+ * fit for this sample in the lookup_table[], seek to the byte position. */
+unsigned int m4a_seek(demux_res_t* demux_res, stream_t* stream, 
     uint32_t sound_sample_loc, uint32_t* sound_samples_done, 
     int* current_sample)
 {
@@ -300,8 +198,8 @@ unsigned int alac_seek(demux_res_t* demux_res, stream_t* stream,
         ++i;
     }
 
-    /* We know the new block, now calculate the file position. */
-    new_pos = get_sample_offset(demux_res, new_sample);
+    /* We know the new sample (=frame), now calculate the file position. */
+    gather_offset(demux_res, &new_sample, &new_pos);
 
     /* We know the new file position, so let's try to seek to it */
     if (stream->ci->seek_buffer(new_pos))
@@ -319,71 +217,38 @@ unsigned int alac_seek(demux_res_t* demux_res, stream_t* stream,
  *
  * Seeking uses the following arrays:
  *
- * 1) the chunk_offset array contains the file offset of each chunk.
- *
- * 2) the sample_to_chunk array contains information about which chunk
- *    of samples each sample belongs to.
- *
- * 3) the sample_byte_size array contains the length in bytes of each
- *    sample.
+ * 1) the lookup_table array contains the file offset for the first sample
+ *    of each chunk.
  *
- * 4) the time_to_sample array contains the duration (in sound samples) 
+ * 2) the time_to_sample array contains the duration (in sound samples) 
  *    of each sample of data.
  *
- * Locate the chunk containing location (using chunk_offset), find the 
- * sample of that chunk (using sample_to_chunk) and finally the location
- * of that sample (using sample_byte_size). Then use time_to_sample to
+ * Locate the chunk containing location (using lookup_table), find the first
+ * sample of that chunk (using lookup_table). Then use time_to_sample to
  * calculate the sound_samples_done value.
  */
-unsigned int alac_seek_raw(demux_res_t* demux_res, stream_t* stream,
+unsigned int m4a_seek_raw(demux_res_t* demux_res, stream_t* stream,
     uint32_t file_loc, uint32_t* sound_samples_done, 
     int* current_sample)
 {
-    uint32_t chunk_sample = 0;     /* Holds the chunk/frame index. */
-    uint32_t total_samples = 0;    /* Sums up total amount of chunks/frames. */
-    uint32_t new_sound_sample = 0; /* Sums up total amount of samples. */
+    uint32_t i;
+    uint32_t chunk_sample     = 0;
+    uint32_t total_samples    = 0;
+    uint32_t new_sound_sample = 0;
+    uint32_t tmp_dur;
+    uint32_t tmp_cnt;
     uint32_t new_pos;
-    uint32_t chunk;
-    uint32_t i, tmp_dur, tmp_cnt;
-
-    /* There is no metadata available to perform raw seek. */
-    if (!demux_res->num_chunk_offsets || !demux_res->num_sample_to_chunks) 
-    {
-        return 0;
-    }
-
-    /* Locate the chunk containing file_loc. */
-    chunk = 0;
-    while (chunk < demux_res->num_chunk_offsets)
-    {
-        if (file_loc < demux_res->chunk_offset[chunk])
-        {
-            break;
-        }
-        ++chunk;
-    }
-    new_pos = demux_res->chunk_offset[chunk > 0 ? chunk - 1 : 0];
 
-    /* Get the first sample of the chunk. */
-    i = 1;
-    sample_to_chunk_t *tab1 = demux_res->sample_to_chunk;
-    while (i < demux_res->num_sample_to_chunks)
+    /* We know the desired byte offset, search for the chunk right before. 
+     * Return the associated sample to this chunk as chunk_sample. */
+    for (i=0; i < demux_res->num_lookup_table; ++i)
     {
-        if (chunk <= tab1[i].first_chunk)
-        {
+        if (demux_res->lookup_table[i].offset > file_loc)
             break;
-        }
-        chunk_sample += tab1[i-1].num_samples * (tab1[i].first_chunk - tab1[i-1].first_chunk);
-        ++i;
-    }
-    chunk_sample += (chunk - tab1[i-1].first_chunk) * tab1[i-1].num_samples;
-    
-    /* Get the position within the chunk. */
-    while (chunk_sample < demux_res->num_sample_byte_sizes &&
-           file_loc >= new_pos + demux_res->sample_byte_size[chunk_sample])
-    {
-        new_pos += demux_res->sample_byte_size[chunk_sample++];
     }
+    i = (i>0) ? i-1 : 0; /* We want the last chunk _before_ file_loc. */
+    chunk_sample = demux_res->lookup_table[i].sample;
+    new_pos      = demux_res->lookup_table[i].offset;
     
     /* Get sound sample offset. */
     i = 0;
diff --git a/apps/codecs/libm4a/m4a.h b/apps/codecs/libm4a/m4a.h
index 2b361e8784..e49d14b832 100644
--- a/apps/codecs/libm4a/m4a.h
+++ b/apps/codecs/libm4a/m4a.h
@@ -59,6 +59,12 @@ typedef struct
 
 typedef struct
 {
+    uint32_t sample;
+    uint32_t offset;
+} sample_offset_t;
+
+typedef struct
+{
     uint16_t num_channels;
     uint16_t sound_sample_size;
     uint32_t sound_sample_rate;
@@ -68,13 +74,12 @@ typedef struct
     sample_to_chunk_t *sample_to_chunk;
     uint32_t num_sample_to_chunks;
     
-    uint32_t *chunk_offset;
-    uint32_t num_chunk_offsets;
+    sample_offset_t *lookup_table;
+    uint32_t num_lookup_table;
     
     time_to_sample_t *time_to_sample;
     uint32_t num_time_to_samples;
 
-    uint16_t *sample_byte_size;
     uint32_t num_sample_byte_sizes;
 
     uint32_t codecdata_len;
@@ -127,10 +132,11 @@ void stream_create(stream_t *stream,struct codec_api* ci);
 int get_sample_info(demux_res_t *demux_res, uint32_t sample,
     uint32_t *sample_duration, uint32_t *sample_byte_size);
 unsigned int get_sample_offset(demux_res_t *demux_res, uint32_t sample);
-unsigned int alac_seek (demux_res_t* demux_res, stream_t* stream,
+unsigned int m4a_seek (demux_res_t* demux_res, stream_t* stream,
     uint32_t sound_sample_loc, uint32_t* sound_samples_done, 
     int* current_sample);
-unsigned int alac_seek_raw (demux_res_t* demux_res, stream_t* stream,
+unsigned int m4a_seek_raw (demux_res_t* demux_res, stream_t* stream,
     uint32_t file_loc, uint32_t* sound_samples_done, int* current_sample);
+int m4a_check_sample_offset(demux_res_t *demux_res, uint32_t frame);
 
 #endif /* STREAM_H */