[Flac-dev] better seeking
Miroslav Lichvar
lichvarm at phoenix.inf.upol.cz
Sat Oct 28 12:16:32 PDT 2006
Ok, the patch from 2003 about improving seeking still didn't make it
to CVS, so here is another try.
I made some benchmarking with the test_seeking utility from flac
sources to show how bad the current seeking is, especially without
seektable. Track used for the experiment had about 50 minutes.
In the following table is average number of seeks and number of
decoded frames required for one complete absolute seek. I tried
several files encoded with fixed/variable block size, seektable with
seekpoints every 10s, 100s and no seektable.
unpatched patched
block size seek decoded decoded
points seeks frames seeks frames
fixed
10s 1.22 2.04 1.16 1.83
100s 6.37 12.26 2.22 3.21
- 16.80 341.61 3.84 5.23
variable
10s 1.18 2.93 1.42 2.57
100s 8.80 16.65 2.58 3.67
- 31.35 445.08 4.28 5.67
And another table shows the worst seek for the same files.
block size seek decoded decoded
points seeks frames seeks frames
fixed
10s 49 49 3 6
100s 55 55 5 8
- 1 1038 6 9
variable
10s 53 53 9 9
100s 87 9 8 8
- 1 1620 10 13
Attached is the new patch.
--
Miroslav Lichvar
-------------- next part --------------
Index: stream_decoder.c
===================================================================
RCS file: /cvsroot/flac/flac/src/libFLAC/stream_decoder.c,v
retrieving revision 1.117
diff -u -r1.117 stream_decoder.c
--- stream_decoder.c 16 Oct 2006 15:49:18 -0000 1.117
+++ stream_decoder.c 28 Oct 2006 17:12:19 -0000
@@ -2923,18 +2923,18 @@
FLAC__bool seek_to_absolute_sample_(FLAC__StreamDecoder *decoder, FLAC__uint64 stream_length, FLAC__uint64 target_sample)
{
- FLAC__uint64 first_frame_offset = decoder->private_->first_frame_offset, lower_bound, upper_bound;
+ FLAC__uint64 first_frame_offset = decoder->private_->first_frame_offset, lower_bound, upper_bound, lower_bound_sample, upper_bound_sample;
FLAC__int64 pos = -1, last_pos = -1;
- int i, lower_seek_point = -1, upper_seek_point = -1;
+ int i;
unsigned approx_bytes_per_frame;
- FLAC__uint64 last_frame_sample = FLAC__U64L(0xffffffffffffffff);
+ FLAC__uint64 last_frame_sample = FLAC__U64L(0xffffffffffffffff), this_frame_sample;
FLAC__bool needs_seek;
const FLAC__uint64 total_samples = FLAC__stream_decoder_get_total_samples(decoder);
const unsigned min_blocksize = decoder->private_->stream_info.data.stream_info.min_blocksize;
const unsigned max_blocksize = decoder->private_->stream_info.data.stream_info.max_blocksize;
const unsigned max_framesize = decoder->private_->stream_info.data.stream_info.max_framesize;
- const unsigned channels = FLAC__stream_decoder_get_channels(decoder);
- const unsigned bps = FLAC__stream_decoder_get_bits_per_sample(decoder);
+ const unsigned channels = decoder->private_->stream_info.data.stream_info.channels;
+ const unsigned bps = decoder->private_->stream_info.data.stream_info.bits_per_sample;
const FLAC__StreamMetadata_SeekTable *seek_table = decoder->private_->has_seek_table? &decoder->private_->seek_table.data.seek_table : 0;
/* we are just guessing here, but we want to guess high, not low */
@@ -2961,12 +2961,14 @@
* the first and last frames.
*/
lower_bound = first_frame_offset;
+ lower_bound_sample = 0;
/* calc the upper_bound, beyond which we never want to seek */
if(max_framesize > 0)
upper_bound = stream_length - (max_framesize + 128 + 2); /* 128 for a possible ID3V1 tag, 2 for indexing differences */
else
upper_bound = stream_length - ((channels * bps * FLAC__MAX_BLOCK_SIZE) / 8 + 128 + 2);
+ upper_bound_sample = total_samples > 0 ? total_samples : target_sample;
/*
* Now we refine the bounds if we have a seektable with
@@ -2981,7 +2983,7 @@
}
if(i >= 0) { /* i.e. we found a suitable seek point... */
lower_bound = first_frame_offset + seek_table->points[i].stream_offset;
- lower_seek_point = i;
+ lower_bound_sample = seek_table->points[i].sample_number;
}
/* find the closest seek point > target_sample, if it exists */
@@ -2991,98 +2993,32 @@
}
if(i < (int)seek_table->num_points) { /* i.e. we found a suitable seek point... */
upper_bound = first_frame_offset + seek_table->points[i].stream_offset;
- upper_seek_point = i;
+ upper_bound_sample = seek_table->points[i].sample_number;
}
}
+ decoder->private_->target_sample = target_sample;
- /*
- * Now guess at where within those bounds our target
- * sample will be.
- */
- if(seek_table && lower_seek_point >= 0) {
- /* first see if our sample is within a few frames of the lower seekpoint */
- if(seek_table->points[lower_seek_point].sample_number <= target_sample && target_sample < seek_table->points[lower_seek_point].sample_number + (seek_table->points[lower_seek_point].frame_samples * 4)) {
- pos = (FLAC__int64)lower_bound;
- }
- else if(upper_seek_point >= 0) {
- const FLAC__uint64 target_offset = target_sample - seek_table->points[lower_seek_point].sample_number;
- const FLAC__uint64 range_samples = seek_table->points[upper_seek_point].sample_number - seek_table->points[lower_seek_point].sample_number;
- const FLAC__uint64 range_bytes = (upper_bound>lower_bound? upper_bound - lower_bound - 1 : 0);
+ needs_seek = true;
+ while(1) {
+ if(needs_seek) {
#ifndef FLAC__INTEGER_ONLY_LIBRARY
#if defined _MSC_VER || defined __MINGW32__
- /* with MSVC you have to spoon feed it the casting */
- pos = (FLAC__int64)lower_bound + (FLAC__int64)(((FLAC__double)(FLAC__int64)target_offset / (FLAC__double)(FLAC__int64)range_samples) * (FLAC__double)(FLAC__int64)(range_bytes-1)) - approx_bytes_per_frame;
+ /* with VC++ you have to spoon feed it the casting */
+ pos = (FLAC__int64)lower_bound + (FLAC__int64)((FLAC__double)(FLAC__int64)(target_sample - lower_bound_sample) / (FLAC__double)(FLAC__int64)(upper_bound_sample - lower_bound_sample) * (FLAC__double)(FLAC__int64)(upper_bound - lower_bound)) - approx_bytes_per_frame;
#else
- pos = (FLAC__int64)lower_bound + (FLAC__int64)(((FLAC__double)target_offset / (FLAC__double)range_samples) * (FLAC__double)range_bytes) - approx_bytes_per_frame;
+ pos = (FLAC__int64)lower_bound + (FLAC__int64)((FLAC__double)(target_sample - lower_bound_sample) / (FLAC__double)(upper_bound_sample - lower_bound_sample) * (FLAC__double)(upper_bound - lower_bound)) - approx_bytes_per_frame;
#endif
#else
/* a little less accurate: */
- if (range_bytes <= 0xffffffff)
- pos = (FLAC__int64)lower_bound + (FLAC__int64)((target_offset * range_bytes) / range_samples) - approx_bytes_per_frame;
+ if (upper_bound - lower_bound < 0xffffffff)
+ pos = (FLAC__int64)lower_bound + (FLAC__int64)(((target_sample - lower_bound_sample) * (upper_bound - lower_bound)) / (upper_bound_sample - lower_bound_sample)) - approx_bytes_per_frame;
else /* @@@ WATCHOUT, ~2TB limit */
- pos = (FLAC__int64)lower_bound + (FLAC__int64)(((target_offset>>8) * (range_bytes>>8)) / (range_samples>>16)) - approx_bytes_per_frame;
-#endif
- }
- }
-
- /*
- * If there's no seek table, we need to use the metadata (if we
- * have it) and the filelength to estimate the position of the
- * frame with the correct sample.
- */
- if(pos < 0 && total_samples > 0) {
- /*
- * For max accuracy we should be using
- * (stream_length-first_frame_offset-1) in the divisor, but the
- * difference is trivial and (stream_length-first_frame_offset)
- * has no chance of underflow.
- */
-#ifndef FLAC__INTEGER_ONLY_LIBRARY
-#if defined _MSC_VER || defined __MINGW32__
- /* with VC++ you have to spoon feed it the casting */
- pos = (FLAC__int64)first_frame_offset + (FLAC__int64)(((FLAC__double)(FLAC__int64)target_sample / (FLAC__double)(FLAC__int64)total_samples) * (FLAC__double)(FLAC__int64)(stream_length-first_frame_offset)) - approx_bytes_per_frame;
-#else
- pos = (FLAC__int64)first_frame_offset + (FLAC__int64)(((FLAC__double)target_sample / (FLAC__double)total_samples) * (FLAC__double)(stream_length-first_frame_offset)) - approx_bytes_per_frame;
-#endif
-#else
- /* a little less accurate: */
- if (stream_length < 0xffffffff)
- pos = (FLAC__int64)first_frame_offset + (FLAC__int64)((target_sample * (stream_length-first_frame_offset)) / total_samples) - approx_bytes_per_frame;
- else /* @@@ WATCHOUT, ~2TB limit */
- pos = (FLAC__int64)first_frame_offset + (FLAC__int64)(((target_sample>>8) * ((stream_length-first_frame_offset)>>8)) / (total_samples>>16)) - approx_bytes_per_frame;
+ pos = (FLAC__int64)lower_bound + (FLAC__int64)((((target_sample - lower_bound_sample)>>8) * ((upper_bound - lower_bound)>>8)) / ((upper_bound_sample - lower_bound_sample)>>16)) - approx_bytes_per_frame;
#endif
- }
-
- /*
- * If there's no seek table and total_samples is unknown, we
- * don't even bother trying to figure out a target, we just use
- * our current position.
- */
- if(pos < 0) {
- FLAC__uint64 upos;
- if(decoder->private_->tell_callback(decoder, &upos, decoder->private_->client_data) != FLAC__STREAM_DECODER_TELL_STATUS_OK) {
- decoder->protected_->state = FLAC__STREAM_DECODER_SEEK_ERROR;
- return false;
- }
- pos = (FLAC__int64)upos;
- needs_seek = false;
- }
- else
- needs_seek = true;
-
- /* clip the position to the bounds, lower bound takes precedence */
- if(pos >= (FLAC__int64)upper_bound) {
- pos = (FLAC__int64)upper_bound-1;
- needs_seek = true;
- }
- if(pos < (FLAC__int64)lower_bound) {
- pos = (FLAC__int64)lower_bound;
- needs_seek = true;
- }
-
- decoder->private_->target_sample = target_sample;
- while(1) {
- if(needs_seek) {
+ if(pos >= (FLAC__int64)upper_bound)
+ pos = (FLAC__int64)upper_bound - 1;
+ if(pos < (FLAC__int64)lower_bound)
+ pos = (FLAC__int64)lower_bound;
if(decoder->private_->seek_callback(decoder, (FLAC__uint64)pos, decoder->private_->client_data) != FLAC__STREAM_DECODER_SEEK_STATUS_OK) {
decoder->protected_->state = FLAC__STREAM_DECODER_SEEK_ERROR;
return false;
@@ -3113,45 +3049,43 @@
if(!decoder->private_->is_seeking) {
break;
}
- else { /* we need to narrow the search */
- const FLAC__uint64 this_frame_sample = decoder->private_->last_frame.header.number.sample_number;
- FLAC__ASSERT(decoder->private_->last_frame.header.number_type == FLAC__FRAME_NUMBER_TYPE_SAMPLE_NUMBER);
- if(this_frame_sample == last_frame_sample && pos < last_pos) {
- /* our last move backwards wasn't big enough, double it */
- pos -= (last_pos - pos);
- needs_seek = true;
+ /* we need to narrow the search */
+ this_frame_sample = decoder->private_->last_frame.header.number.sample_number;
+ FLAC__ASSERT(decoder->private_->last_frame.header.number_type == FLAC__FRAME_NUMBER_TYPE_SAMPLE_NUMBER);
+
+ approx_bytes_per_frame = decoder->private_->last_frame.header.blocksize * channels * bps/8 + 64;
+
+ if(target_sample < this_frame_sample) {
+ if(this_frame_sample == last_frame_sample) {
+ /* our last move backwards wasn't big enough */
+ upper_bound -= approx_bytes_per_frame;
}
else {
- if(target_sample < this_frame_sample) {
- last_pos = pos;
- approx_bytes_per_frame = decoder->private_->last_frame.header.blocksize * channels * bps/8 + 64;
- pos -= approx_bytes_per_frame;
- needs_seek = true;
- }
- else { /* target_sample >= this_frame_sample + this frame's blocksize */
- FLAC__uint64 upos;
- if(decoder->private_->tell_callback(decoder, &upos, decoder->private_->client_data) != FLAC__STREAM_DECODER_TELL_STATUS_OK) {
- decoder->protected_->state = FLAC__STREAM_DECODER_SEEK_ERROR;
- return false;
- }
- last_pos = pos;
- pos = (FLAC__int64)upos;
- pos -= FLAC__stream_decoder_get_input_bytes_unconsumed(decoder);
- needs_seek = false;
- /*
- * if we haven't hit the target frame yet and our position hasn't changed,
- * it means we're at the end of the stream and the seek target does not exist.
- */
- if(last_pos == pos) {
- decoder->protected_->state = FLAC__STREAM_DECODER_SEEK_ERROR;
- return false;
- }
- }
+ upper_bound_sample = this_frame_sample + decoder->private_->last_frame.header.blocksize;
+ if(!FLAC__stream_decoder_get_decode_position(decoder, &upper_bound)) {
+ decoder->protected_->state = FLAC__STREAM_DECODER_SEEK_ERROR;
+ return false;
+ }
}
- if(pos < (FLAC__int64)lower_bound)
- pos = (FLAC__int64)lower_bound;
- last_frame_sample = this_frame_sample;
}
+ else {
+ /* target_sample >= this_frame_sample + this frame's blocksize */
+
+ if(target_sample < this_frame_sample + 4 * decoder->private_->last_frame.header.blocksize)
+ needs_seek = false;
+
+ lower_bound_sample = this_frame_sample + decoder->private_->last_frame.header.blocksize;
+ if(!FLAC__stream_decoder_get_decode_position(decoder, &lower_bound)) {
+ decoder->protected_->state = FLAC__STREAM_DECODER_SEEK_ERROR;
+ return false;
+ }
+ if(last_pos == (FLAC__int64)lower_bound) {
+ decoder->protected_->state = FLAC__STREAM_DECODER_SEEK_ERROR;
+ return false;
+ }
+ last_pos = lower_bound;
+ }
+ last_frame_sample = this_frame_sample;
}
return true;
More information about the Flac-dev
mailing list