FS#10766 - Enable Binary Skip / Search as an option for Skip Length

Attached to Project: Rockbox
Opened by Sean Inglis (seani) - Friday, 06 November 2009, 18:10 GMT
Task Type Patches
Category Music playback
Status Unconfirmed
Assigned To No-one
Operating System All players
Severity Low
Priority Normal
Reported Version Release 3.4
Due in Version Undecided
Due Date Undecided
Percent Complete 0%
Votes 0
Private No


Adds "Binary Skip" to the skip length menu,

This allows navigation by means of binary search within a track.

If no search key is pressed for 5 seconds, the current binary search is considered as having "finished" and pressing a search key subsequently initiates a new binary search.
This task depends upon

Comment by alex wallis (alexwallis646) - Thursday, 10 December 2009, 11:54 GMT
Hi. Ok, maybe its because I am not really that technical, but I don't understand what functionality this patch would actually add? I understand its a new search method for navigating within a track, but why for example would someone want to use it over the existing methods? and how is it different to existing methods of track navigation?
Comment by Sean Inglis (seani) - Thursday, 10 December 2009, 12:16 GMT
Hi Alex,

There was a bit of discussion around this here that might answer the question:

As an appendix to that, I'd contend that it *is* the fastest method of navigating within a long file *including* directly specifying the position numerically.

It's a typical example of something that seems very cumbersome to explain, but is actually very easy to use,

Ideally, I'd add an speech "announcement" of the position in the file after each skip for blind users, but I haven't got round to that yet.
Comment by alex wallis (alexwallis646) - Tuesday, 13 July 2010, 17:05 GMT
hi, I have been somewhat out of the loop with rockbox for a while, but I am starting to get back into it.

I am just looking at some of the tasks on the tracker, and decided to take another look at yours.
I think I understand how this works,
but can I give you a usage example and ask if your patch might be useful for this?

I have a hard disc player, an h140, there is a strange issue which only happens some times, this is that sometimes the disc spins up and for some reason, the player will randomly jump a few tracks, or even a hole folder sometimes.
So say I was listening to an hour long track,
could I some how turn this binary search mode on to start searching through the track to find the point which I was at before the track jumped?

I also had a thought of how this could be fine tuned even further.
say the search is jumping you through at ten minute chunks in the file, could some functionality be added into the patch so that as you get closer to the point you are looking for in the file you could hit a button and start to reduce the jumps that are made within the track each time you press the search button, and as you get closer you could keep reducing the jumps that are made within the file till eventually you could reduce it to jumps of say a minute at a time.

last point, but isn't this binary searching very similar to I believe the feature is called skip length? it has gone through several name changes, I am not sure what it is called now.

I am looking forward to trying this out on target.
Comment by alex wallis (alexwallis646) - Tuesday, 13 July 2010, 18:39 GMT
Hi, just tried to patch a clean build with this patch, and it appears to have gone out of sync, could it please be resynced?
Comment by Dave Hooper (stripwax) - Wednesday, 11 August 2010, 08:21 GMT
Re alex wallis's first 13July post - this feature is 'similar' to skip length, in fact the author of the patch mentioned that Binary Skip is added to the Skip Length menu. The critical difference is that it does *not* use the same length chunks for skipping, so your assertion that the search could be jumping through at ten minute chunks is incorrect: each skip is half the size of the previous skip.

Also it's a manual search method, it's not something you can use to automatically find the spot where the player randomly skipped, you are still in control of which point it jumps to. But it's an alternative to the existing 'hold down the >> button until you find the right place' search method, and an alternative to a fixed-chunk skip length.

Example: for a one hour file you want to find the 35-minute mark:
Press right (jumps from 0 to 30 mins), press right again (jumps from 30 to 45), press left (jumps from 45 to 37.5), press left again (jumps from 37.5 to 33.75) - at this point you're probably close enough.

I haven't tried this yet but assuming it's intuitive to use (e.g. easy to do binary skip for a bit and then search linearly from that point) I see no conceptual objections to adding it.
Comment by Dave Hooper (stripwax) - Wednesday, 11 August 2010, 08:34 GMT
Although, looking at the patch, I'm not sure I see how the upper/lower bounds get reset on a track change - weird things might happen if, while you're skipping-binarily through the track, the track naturally changes and you haven't hit the 5-second timer yet so (if you now skip) it thinks your upper/lower bounds are still relative to the last skip you did on the previous track. Easiest solution might be just to reset search_timeout to zero on a track change.
Comment by Sean Inglis (seani) - Wednesday, 11 August 2010, 12:55 GMT
Ooh, good catch. I tdidn't crop up because you need to have landed to within 5 seconds of the end of your current track as a result of the last binary skip.

Resetting the search timeout makes sense, ta!
Comment by Václav Brožík (pabouk) - Friday, 13 August 2010, 14:16 GMT
Hi Seani, it is a great new functionality. Thanks!

Did you think about automatic increase of playback speed during the binary search to be able to identify the current place in the track more quickly?

A problem could be how to determine the maximum possible speed. At this time the maximum playback speed could possibly be configured as a parameter. In the future it could be determined automatically (what is the CPU able to cope with).

Maybe the increased speed of playback would require possibility of quick manual switching of the binary search mode...
For example on H100 series players long press of PLAY is not utilized.
Comment by Sean Inglis (seani) - Friday, 13 August 2010, 14:34 GMT

I think that previewing as you fast forward / rewind has cropped up a few times. It's a good idea, but I'd imagine quite a complex change - not one I'd feel comfortable tackling at the minute . Also there'd be a limit to how fast you could navigate and still get intelligible feedback.
Comment by Václav Brožík (pabouk) - Friday, 13 August 2010, 17:13 GMT
Unfortunately I did not try your patch yet as I do not have a build environment to compile it but I think you can use binary search two ways:

- without listening - You just know the destination time where you want to get.

- with listening - After each skip you have to listen a while and decide if your next skip will go forward or backward.
In this case speeded-up playback will shorten your listening part of the searching. In Rockbox I use speed-up for listening podcasts and from my experience 2 times speeded-up playback is comprehensible very well.
As the variable playback speed is already implemented in Rockbox I suppose just a function call is required to change playback speed.

I was not talking about audible fast forward / rewind.
Comment by alex wallis (alexwallis646) - Friday, 13 August 2010, 17:35 GMT
I think I understand your suggestion.
Your suggesting that after each skip, playback should be speeded up to enable you to decide if you have skipped to the right point.

If this is what you are suggesting, I am afraid I don't like it. You would basically be forcing people into a situation which they might not want to be.

It would force them to listen to speeded up audio. Also, when you have decided you have reached the right bit, you would need to some how slow the audio back to normal speed.
If of course you had some kind of preset timer to return audio to normal speed after a bit of time, that would be ok, but the suggestion of messing around with speed after using this setting even if it is only for a short while just sounds messy.

Also, how long do you need to work out if your in the right place? I can usually tell within about 4 or 5 seconds. I don't think this is a good idea at all.
Comment by Václav Brožík (pabouk) - Friday, 13 August 2010, 21:30 GMT
Alex, you understood it right.
I see that not everyone would like my suggestion so if it gets implemented it should be optional (for example by selecting the percentage of speed-up).

I can imagine multiple possibilities of completing the search process and switching back to normal speed:
- after a timeout
- after invoking a different function - like rewind, fast forward, pause...
- after pressing a special key (like long PLAY as I suggested above)

Taking you example of needing 4 seconds to decide. Let us say that we have a one-hour track and we would like to find a place with precision of 2 minutes.
This means that we would need 5 skips x 4 seconds = 20 seconds spent by searching. The speeded-up playback could shorten the search time to 10 seconds of less.
I think that the original idea of binary search is to make the search faster.
Comment by Sean Inglis (seani) - Saturday, 14 August 2010, 20:05 GMT
This version syncs to the current source:

1) Voicing the position in the file when a binary skip takes place is now a voice menu option

2) Double-click to skip track now cancels pending skip announcement

3) Long press seek ffwd / bkwd resets the skip timeout

4) Track change resets the timeout
Comment by Sean Inglis (seani) - Saturday, 14 August 2010, 22:32 GMT
This version syncs to the current source:

1) Voicing the position in the file when a binary skip takes place is now a voice menu option

2) Double-click to skip track now cancels pending skip announcement

3) Long press seek ffwd / bkwd resets the skip timeout

4) Track change resets the timeout
Comment by Sean Inglis (seani) - Saturday, 14 August 2010, 22:34 GMT
Gah, clumsy refresh, sorry for the double post above.

This adds search-timeout-reset to play, pause, stop, hotkey and volume controls.
Comment by Sean Inglis (seani) - Sunday, 15 August 2010, 18:17 GMT
Somehow managed to revert the voice track position option in the last patch.