[Flac-dev] bitbuffer optimizations

Miroslav Lichvar lichvarm at phoenix.inf.upol.cz
Tue Jan 25 15:02:24 PST 2005


On Mon, Jan 24, 2005 at 06:31:21PM -0800, Josh Coalson wrote:
> yes, a mere 2 years later it is checked in!  
> 
> speed improvement for me is roughly 17% testing flac files on
> linux-i386.

Thanks!

In case you would like to check another old patch, I have attached updated
patch for seekable stream decoder, originally posted on 09/07/2003.

-- 
Miroslav Lichvar
-------------- next part --------------
--- seekable_stream_decoder.c.orig	2005-01-25 05:18:31.000000000 +0100
+++ seekable_stream_decoder.c	2005-01-25 23:39:03.000000000 +0100
@@ -857,11 +857,11 @@
 
 FLAC__bool seek_to_absolute_sample_(FLAC__SeekableStreamDecoder *decoder, FLAC__uint64 stream_length, FLAC__uint64 target_sample)
 {
-	FLAC__uint64 first_frame_offset, lower_bound, upper_bound;
-	FLAC__int64 pos = -1, last_pos = -1;
-	int i, lower_seek_point = -1, upper_seek_point = -1;
+	FLAC__uint64 first_frame_offset, lower_bound, upper_bound, lower_bound_sample, upper_bound_sample;
+	FLAC__int64 pos, last_pos = -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 = decoder->private_->stream_info.total_samples;
 	const unsigned min_blocksize = decoder->private_->stream_info.min_blocksize;
@@ -903,12 +903,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
@@ -923,7 +925,7 @@
 		}
 		if(i >= 0) { /* i.e. we found a suitable seek point... */
 			lower_bound = first_frame_offset + decoder->private_->seek_table->points[i].stream_offset;
-			lower_seek_point = i;
+			lower_bound_sample = decoder->private_->seek_table->points[i].sample_number;
 		}
 
 		/* find the closest seek point > target_sample, if it exists */
@@ -933,98 +935,33 @@
 		}
 		if(i < (int)decoder->private_->seek_table->num_points) { /* i.e. we found a suitable seek point... */
 			upper_bound = first_frame_offset + decoder->private_->seek_table->points[i].stream_offset;
-			upper_seek_point = i;
+			upper_bound_sample = decoder->private_->seek_table->points[i].sample_number;
 		}
 	}
 
-	/*
-	 * Now guess at where within those bounds our target
-	 * sample will be.
-	 */
-	if(lower_seek_point >= 0) {
-		/* first see if our sample is within a few frames of the lower seekpoint */
-		if(decoder->private_->seek_table->points[lower_seek_point].sample_number <= target_sample && target_sample < decoder->private_->seek_table->points[lower_seek_point].sample_number + (decoder->private_->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 - decoder->private_->seek_table->points[lower_seek_point].sample_number;
-			const FLAC__uint64 range_samples = decoder->private_->seek_table->points[upper_seek_point].sample_number - decoder->private_->seek_table->points[lower_seek_point].sample_number;
-			const FLAC__uint64 range_bytes = (upper_bound>lower_bound? upper_bound - lower_bound - 1 : 0);
+	decoder->private_->target_sample = target_sample;
+
+	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;
+			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;
+				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, 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;
-#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__SEEKABLE_STREAM_DECODER_TELL_STATUS_OK) {
-			decoder->protected_->state = FLAC__SEEKABLE_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__SEEKABLE_STREAM_DECODER_SEEK_STATUS_OK) {
 				decoder->protected_->state = FLAC__SEEKABLE_STREAM_DECODER_SEEK_ERROR;
 				return false;
@@ -1065,45 +1002,43 @@
 		if(decoder->protected_->state != FLAC__SEEKABLE_STREAM_DECODER_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__SEEKABLE_STREAM_DECODER_TELL_STATUS_OK) {
-						decoder->protected_->state = FLAC__SEEKABLE_STREAM_DECODER_SEEK_ERROR;
-						return false;
-					}
-					last_pos = pos;
-					pos = (FLAC__int64)upos;
-					pos -= FLAC__stream_decoder_get_input_bytes_unconsumed(decoder->private_->stream_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__SEEKABLE_STREAM_DECODER_SEEK_ERROR;
-						return false;
-					}
+				upper_bound_sample = this_frame_sample + decoder->private_->last_frame.header.blocksize;
+				if(!FLAC__seekable_stream_decoder_get_decode_position(decoder, &upper_bound)) {
+					decoder->protected_->state = FLAC__SEEKABLE_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__seekable_stream_decoder_get_decode_position(decoder, &lower_bound)) {
+				decoder->protected_->state = FLAC__SEEKABLE_STREAM_DECODER_SEEK_ERROR;
+				return false;
+			}
+			if(last_pos == (FLAC__int64)lower_bound) {
+				decoder->protected_->state = FLAC__SEEKABLE_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