Rockbox Technical Forums

Rockbox General => Rockbox General Discussion => Topic started by: TP Diffenbach on May 04, 2007, 02:02:33 AM

Title: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix it
Post by: TP Diffenbach on May 04, 2007, 02:02:33 AM
One (of several) reasons the scroll acceleration is jumpy is that I never got around to parameterizing part of it; I thought I'd be available to do this, but have been away from my PC (on a contract job) for nearly six months.

Check out line 154 of the patch as maintained by senab (Chris Barnes) (and note this is entirely my fault, not his, senab's done a great job maintaining the patch in my absence; the offending line was authored by me):

struct scroll_accel_jump scroll_accel_jumps[] = { { NOACCEL, 0, 0 }, { PAGE, 1, 0  }, { PAGE, 8, 0  } , { PERCENT, 10, 0 } };

Now, scroll accel has 4 (an arbitrary number that just happens to work) "levels": normal, "fast', "faster" and "fastest".

The line of code above assigns, in order normal to fastest, what happens when a particular level is reached. So at normal, no acceleration is performed, at fast acceleration the list is moved (forward or back) a page at a time, at faster 8 pages at a time, and at fastest, the list is moved 10% of its length.

"Page" means, the number of displayable lines on the screen, as set by the current font (and the presence/absence of the status bar). Change the font height, and you change the page length. So one page scrolls by the number of displayable lines on the screen.

It's the "faster" setting that is problematic: for long lists (like my 8600 tracks), 8 pages is great. For short lists, 8 pages is too much. And, of course, font size influences page size, so the smaller the font, the greater the number of lines in eight pages.

So as you change themes, you'll find some work better or worse for you. Exactly how they work, in turn depends on how aggressively you "turn" the scroll wheel.

So there are a lot of factors interacting to determine whether scrolling feels smooth or choppy.

What I eventually want to do is to make the action taken by each threshold user-configurable. (Settings would then update the scroll_accel_jumps array.) I didn't do that originally, because the patch was (and is) an experiment, and because I absolutely abhor writing menu code.

As a short-term fix, I encourage source builders to play with different hard-coded values in that array. Note that the array is of struct scroll_accel_jump, and that (kludgy, I admit) the third member of that struct is used to /report/ the actual number of lines to moved at runtime. So hard-codeing that third member's value will have no affect.

But you /can/ change the first two members.

The first member, jump_type can be:

PAGE, which will get you paged jumps (that is, the number of lines to move will be so number of pages, e.g., some multiple of the current lines_per_page as determined by the font in use)
or
PERCENT, which will page by list size.

The second member sets the number of pages or the percentage.

Note also that there's some sanity checking; since a percentage value for a short list can be less than a page value, it is possible that, e.g., "fastest" (hardcoded as PERCENT) might specify a scroll by fewer lines than "fast" (hardcoded as PAGE). If so, the larger of the two is used is used.

And if the list is less than a screen (page) long, acceleration NEVER happens.

I'll give an example to clarify this. Given a list 200 lines (items) long with a screen size of 20 lines, a "fastest" scroll is 10%, or 20 lines. But a "fast" scroll is 8 pages, or 160 lines. In that case, if the scroll acceleration is "fastest",  the actual number of lines moved will be the greater of the two, or 160 lines.

Note this also means that the first accel after normal, that is the "fast" accel, should probably ALWAYS be one page. And of course the "normal" should always be "NOACCEL". So it's just the "faster" and "fastest" we want to play with.

Now, here's what I suggest: let's get rid of my foolish 8 page scroll. Eight pages is just too choppy.

Let's either change the hardcoding to 4 pages:

struct scroll_accel_jump scroll_accel_jumps[] = { { NOACCEL, 0, 0 }, { PAGE, 1, 0  }, { PAGE, 4, 0  } , { PERCENT, 10, 0 } };

Or, make "faster" and "fastest" both percentages, e.g.,

struct scroll_accel_jump scroll_accel_jumps[] = { { NOACCEL, 0, 0 }, { PAGE, 1, 0  }, { PERCENT, 5, 0  } , { PERCENT, 10, 0 } };

I'm not going to update the patch, even though is a straightforward change, simply because I can't test it. But anyone who can build and test is encouraged to provide this change.

But if you want, give these a try and let me know how it works. Or if someone s interested enough to make the faster and fastest jumps user configurable, all the better.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix it
Post by: Llorean on May 04, 2007, 04:10:09 AM
Out of curiosity, what if your list is short enough that 10% is actually less than 8 pages? Say your list is a mere 70 pages total? Does this mean that if you somehow trigger the last one it'll actually go slower than the previous one? Perhaps there should be a safeguard against this (though making it use a percent for both faster and fastest seems likely to do the case).
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix
Post by: elborak on May 04, 2007, 04:45:54 AM
Out of curiosity, what if your list is short enough that 10% is actually less than 8 pages? Say your list is a mere 70 pages total? Does this mean that if you somehow trigger the last one it'll actually go slower than the previous one? Perhaps there should be a safeguard against this (though making it use a percent for both faster and fastest seems likely to do the case).
I think he covered this case:
Quote
Note also that there's some sanity checking; since a percentage value for a short list can be less than a page value, it is possible that, e.g., "fastest" (hardcoded as PERCENT) might specify a scroll by fewer lines than "fast" (hardcoded as PAGE). If so, the larger of the two is used is used.

And if the list is less than a screen (page) long, acceleration NEVER happens.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix
Post by: TP Diffenbach on May 04, 2007, 04:59:01 AM
Out of curiosity, what if your list is short enough that 10% is actually less than 8 pages? Say your list is a mere 70 pages total? Does this mean that if you somehow trigger the last one it'll actually go slower than the previous one?

But that's the example I gave. The sanity check ensures that the largest* jump less than or equal to your scroll accell factor is made.

* Actually, that's not strictly true, but effectively is true. We actually only check until a larger factor's scroll is greater than a smaller factor's scroll. We assume the order of actions for fast, faster, fastest isn't pathological.

Below, "jump" means the number of lines in the list that we move.

That is, if scroll factor is "fastest", our initial candidate jump is fastest's jump.

We will execute "fastest's" jump unless "faster's" jump is greater than "fastest's" jump.

If "faster's" jump is greater than "fastest's", then faster becomes our new candidate, and we repeat, comparing that jump against "fast's" jump, and taking the larger of those two.

If the scroll accel factor is "faster", our initial candidate jump is the "faster" jump, which is compare against the "fast" jump, ertc.

If the scroll accel factor is "fast", we just use the "fast" jump.

This is easier to explain by just showing the code, so long as I point out that I'm using the kludge of recording teh actual number of lines to jump in the same struct that provides teh type (PAGE, PERCENT) and extent of the jump. Here's the code, annotated:

Code: [Select]
static struct scroll_accel_jump* find_accel_for_list(
        struct gui_list* list, struct scroll_accel_jump* jump, unsigned int raw_accel ) {

// second parameter is the array of jump policies
// third is the accell factor, [0..3]

// find items in the list
    unsigned int l_items = list_items( list );

// find the number of displayable lines on the screen
    unsigned int s_lines = screen_lines( list );

// accel factor == 0 == no accel
    /* never accel in a list <= page long */
    if( raw_accel == 0 || l_items <= s_lines ) {
        return jump;
    }

// jump is the array, we're doing pointer arithmetic,
// eq. to jump[ raw_accel ]

// calculate_jump_lines has a side-effect: it alters its pointed-to first
// param by storing the actual jump in that element's third member

    /* otherwise, find the highest possible accel  */        
    calculate_jump_lines( jump + raw_accel, l_items, s_lines );

// if the factor is > 1 it is "faster" or "fastest"
// so calculate the next lower jump and compare them
// keep doing so until you've compared to "faster" to "fast"
// if the lower accel's jump is bigger, decrement the accel factor

    while( raw_accel > 1 ) {
        calculate_jump_lines( jump + raw_accel - 1, l_items, s_lines );
        if( jump[ raw_accel ].lines > jump[ raw_accel - 1 ].lines ) break;
        --raw_accel;
    }

// return the jump, which is the biggest jump for our accel factor
// that element has been modified to also contain
// the actual line count of the jump
// so we can give the caller the actual jump and the policy that produced it
// in case the caller wants to do something clever.
// of course in any OO language this would be terrible tight coupling
// but this is embedded C, different rules apply

    return jump + raw_accel;
}
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix
Post by: senab on May 04, 2007, 07:44:42 AM
I'm going to have a look at making the setting user configurable. I don't know that much C but i'll get by. I'll keep you posted  ;D

//EDIT: Thomas, check your PM's.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix
Post by: CpuWhiz on May 04, 2007, 01:57:26 PM
I was going to look into this but you beat me to it senab, so I will just go and explain the menu system some in case you want some help deciphering it. The line that creates the menu is in apps/menus/settings_menu.c and looks like this:

Code: [Select]
MENUITEM_SETTING(ipod_scroll_wheel_acceleration_fast, &global_settings.ipod_scroll_wheel_acceleration_fast, NULL);
The first argument is the actual variable that holds the value the user defined, this can be found in apps/settings.h. The next one is a reference to the structure that holds the setting (doesn't need to be changed). The 3rd is the same as the 1st, maybe one is the default value and the other is where to store it, not quite sure. The last is NULL and I have no clue what it does ;D

Then we move on to apps/settings_list.c:

Code: [Select]
INT_SETTING(0, ipod_scroll_wheel_acceleration_fast, LANG_IPOD_SCROLL_WHEEL_FAST, 135,
         "ipod scroll wheel fast threshold in clicks/sec", UNIT_SEC,
         5, 500, 5,
         NULL, NULL, NULL),

ipod_scroll_wheel_acceleration_fast is our variable again. LANG_IPOD_SCROLL_WHEEL_FAST matches a entry in apps/lang/english.lang. The 135 is the default value and the 5, 500, 5 is the minimum value, the maximum value, and the increment between each option in the menu. UNIT_SEC is the "s" that gets added to the options in the menu. Maybe try UNIT_PERCENT. The text is a fall back for the menu name (since we only define the English translation for the menu this is what would show up for other languages). Again, the NULLs I have no clue about. I picked up the menu system from looking at some other menu entries. I don't find it too difficult and I hope you don't either. Good luck senab! I love your builds!

Edit:
Almost forgot, you need to then add the entry to the actual menu:
Code: [Select]
MAKE_MENU(ipod_scroll_wheel_acceleration_menu, ID2P(LANG_IPOD_SCROLL_WHEEL_SPEED), 0, Icon_NOICON,
          &ipod_scroll_wheel_acceleration_fast,
          &ipod_scroll_wheel_acceleration_faster,
          &ipod_scroll_wheel_acceleration_fastest,
         );

Now that I think about it, one of the two ipod_scroll_wheel_acceleration_fast variables above is a local variable for the menu setting and &ipod_scroll_wheel_acceleration_fast is the reference to it that adds it to the main scroll menu. Hope that helps.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix it
Post by: ryran on May 04, 2007, 06:21:03 PM
It's so cool to see that all of TP's work on this isn't going to be abandoned. Yay.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix it
Post by: Toxikator on May 05, 2007, 08:46:24 AM
Maybe I'm missing the point but wouldn't it be smoother/more accurate to jump by lines?

As in, at "normal" one click is one menu line

At "fast" one click is two menu lines (2x)

At "faster" one click is three menu lines (3x)

At "fastest" one click is four menu lines (4x).

Or something like that, with 2x, 4x, 8x, etc.

Seems like it would a) be FAR more consistent and b) not so jumpy since you WONT move from slow scrolling to a few pages down.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix
Post by: TP Diffenbach on May 05, 2007, 11:28:32 PM
Maybe I'm missing the point but wouldn't it be smoother/more accurate to jump by lines?

As in, at "normal" one click is one menu line

At "fast" one click is two menu lines (2x)

At "faster" one click is three menu lines (3x)

At "fastest" one click is four menu lines (4x).

Or something like that, with 2x, 4x, 8x, etc.

Seems like it would a) be FAR more consistent and b) not so jumpy since you WONT move from slow scrolling to a few pages down.

Because it would be too slow. The most "clicks" we can get in one revolution of the dial is 24 (there are 96 positions, but we don't count any movement less than 4 clicks, to suppress jumpiness.)

Our lists (using my numbers, in the database) range from as little as 60 items, to as many as 8600+. True, this is different if you're using directory browsing, but I suspect most ipod users find directory browsing useless.

At 8 lines per scroll, we'd get a maximum of 192 lines per dial; even assuming the user remembers to browse backwards when he knows the target item is in the second half of the list, he needs to be able to go at least  4400 lines, or more than 22 revolutions. This is tedious.

Plus, we wouldn't get really get 192 lines per dial, as the list refresh takes time, during which sending keys is blocked.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix it
Post by: Toxikator on May 07, 2007, 12:16:04 PM
8600 items, yes, but not for most users. Because most users in Tagcache have things ORGANIZED.

8600 songs? Maybe, if you feel some sort of silly urge to browse your entire collection song at a time. Take those 8600 songs and divide them up into maybe 800 Albums. 800 albums into maybe 600 artists or 20 genres. Those are the lists people work with.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix it
Post by: Llorean on May 07, 2007, 02:30:51 PM
Yeah, sorry about that. I'd read your post on a portable device, and probably managed to accidentally jump past your mention of the safeguard, then came back later to type a response I'd kept in my head without re-reading the post.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix it
Post by: Flid on May 07, 2007, 05:04:40 PM
I wasn't going to jump in to this thread, as I didn't want to veer it in another direction... but Toxikator already did that for me.

TPD / Senab. Would your patch work with a REAL acceleration, rather than stepped speed increases?

Wouldn't it be more sensible to make this cross-platform? Could you have a variable acceleration in the same way that FFWD works with button presses in WPS (ie. a user adjustable of 2x scroll speed after 1/2s, 1s, 2s, 3s etc)?

This way, you could have Rockbox just recognise the fact that you were scrolling (regardless of speed of scroll) and then accelerate per second of continued action. This would obviously allow for cross platform usage (where as scrollwheel speed is purely restricted to iPod & Sansa).

Obviously, getting to the end of VERY long lists may take a bit longer, but you wouldn't need to train your fingers to a speed of rotation, just learn how quickly the acceleration builds up (IMHO quite intuitive?!?!).

You may have discussed this at length when you started working on your patch in the first place, so I apologise if this is brining up an old subject.
Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix
Post by: TP Diffenbach on May 08, 2007, 03:55:57 AM
8600 items, yes, but not for most users. Because most users in Tagcache have things ORGANIZED.

8600 songs? Maybe, if you feel some sort of silly urge to browse your entire collection song at a time. Take those 8600 songs and divide them up into maybe 800 Albums. 800 albums into maybe 600 artists or 20 genres. Those are the lists people work with.

Well, maybe I am disorganized and silly, but it's my patch and my time and my analysis.

I agree, there should be a number of different ways to handle scroll acceleration (see my scroll accel API patch, which attempts to give a common API all implementations might use). If you think you have a better way to do it, fork my code or start from scratch.

Title: Re: Why the ipod 4G/5G scroll acceleration patch is jumpy, and how you might fix
Post by: TP Diffenbach on May 08, 2007, 04:15:47 AM
TPD / Senab. Would your patch work with a REAL acceleration, rather than stepped speed increases?

Short answer: yes, in theory. No, according to the tests I've done.

In theory, we should be able to determine the "instantaneous" scroll speed at  any time, and scroll according to that. The problem is that screen updates take a non-trivial amount of time. In fact, by the time we've done one scroll update, the scroll wheel interupt will have fired multiple times.

What I do now (I think -- it's been a while since I wrote the code) is calculate the average speed since last screen update. This could be improved -- I think --, particularly by determining if the user is speeding up or slowing down.

But the other problem is that the user really can scroll faster than we can read the scroll and update the screen. I made several cheap kludgey attempts to average and "dampen" that, but never found anything that worked real well. I would really appreciate any suggestions anyone has for doing that better.

But the best things I found were outside of the scroll per se. That's why the original patch also included list display optimizations, of two sorts (when the page changes, and when the page does not). I believe those chnages are made obsolete by other changes to the list code.

I also rewrote the screen update code in ARM assembly. But I never submitted that patch, because it does no real good. While it was intrinsically considerably faster than what we had at the time, the improvements were completely swamped by the need to sleep the screen update until the broadcomm chip is ready for the next screen update. (The root problem is that our screen update code is based on a broadcomm firmware debug function, not on the (presumably much faster) way Apple updates the screen. Fast code + long wait isn't any faster than slower code   + long wait.

Then I rewrote memcpy in ARM, because the list functions use it. That did produce a speed improvement, but events intervened and I wasn't able to submit that. (see http://www.rockbox.org/mail/archive/rockbox-dev-archive-2006-07/0005.shtml    )

So basically, yes, there are a number of improvements that can be made to scrolling, but considerable trial and error is involved. If you browse the mailing list, you may be able to find some of my findings on these subjects.

Your ideas are good and I encourage you to explore them, as you'll probbaly see something I missed.