Re: how is strnatcmp aka "Interpret numbers while sorting" supposed to sort?
codemonkey wrote: > Are you guys aware that there's a quasi-standard regarding this in > the GNU libraries? See the following excerpt from Fedora "info ls" > and "man strverscmp". > > ~ray > > PS: I've found that "ls -v" works well for sorting MP3s with track > numbering, etc. I don't know if it handles all of the cases described in > this thread though. Maybe GNU's implementation is worth borrowing for > rockbox? > > -- > > $ info ls > > (...excerpt...) > > 10.1.4 More details about version sort > -- > > The version sort takes into account the fact that file names frequently > include indices or version numbers. Standard sorting functions usually > do not produce the ordering that people expect because comparisons are > made on a character-by-character basis. The version sort addresses > this problem, and is especially useful when browsing directories that > contain many files with indices/version numbers in their names: > > $ ls -1$ ls -1v > foo.zml-1.gz foo.zml-1.gz > foo.zml-100.gz foo.zml-2.gz > foo.zml-12.gz foo.zml-6.gz > foo.zml-13.gz foo.zml-12.gz > foo.zml-2.gz foo.zml-13.gz > foo.zml-25.gz foo.zml-25.gz > foo.zml-6.gz foo.zml-100.gz > >Note also that numeric parts with leading zeros are considered as > fractional one: > > $ ls -1$ ls -1v > abc-1.007.tgz abc-1.007.tgz > abc-1.012b.tgz abc-1.01a.tgz > abc-1.01a.tgz abc-1.012b.tgz > >This functionality is implemented using the `strverscmp' function. > > -- > > $ man strverscmp > > STRVERSCMP(3) Linux Programmer’s Manual > STRVERSCMP(3) > > NAME >strverscmp - compare two version strings > > SYNOPSIS >#define _GNU_SOURCE >#include > >int strverscmp(const char *s1, const char *s2); > > DESCRIPTION >Often one has files jan1, jan2, ..., jan9, jan10, ... and it > feels >wrong when ls(1) orders them jan1, jan10, ..., jan2, ..., jan9. In >order to rectify this, GNU introduced the -v option to ls(1), which > is >implemented using versionsort(3), which again uses strverscmp(). > >Thus, the task of strverscmp() is to compare two strings and > find >the "right" order, while strcmp(3) only finds the lexicographic > order. >This function does not use the locale category LC_COLLATE, so is > meant >mostly for situations where the strings are expected to be in > ASCII. > >What this function does is the following. If both strings are > equal, >return 0. Otherwise find the position between two bytes with the >property that before it both strings are equal, while directly after > it >there is a difference. Find the largest consecutive digit strings >containing (or starting at, or ending at) this position. If one or > both >of these is empty, then return what strcmp(3) would have returned >(numerical ordering of byte values). Otherwise, compare both digit >strings numerically, where digit strings with one or more leading > zeroes >are interpreted as if they have a decimal point in front (so that in >particular digit strings with more leading zeroes come before digit >strings with fewer leading zeroes). Thus, the ordering is 000, > 00, >01, 010, 09, 0, 1, 9, 10. > > RETURN VALUE >The strverscmp() function returns an integer less than, equal to, or >greater than zero if s1 is found, respectively, to be earlier than, >equal to, or later than s2. > > CONFORMING TO >This function is a GNU extension. > > SEE ALSO >rename(1), strcasecmp(3), strcmp(3), strcoll(3), > feature_test_macros(7) > > GNU 2001-12-19 > STRVERSCMP(3) > > Seems very close. My understanding is natural sort would interpret as: 000, 00, 0, 01, 1, 09, 9, 010, 10.
Re: how is strnatcmp aka "Interpret numbers while sorting" supposed to sort?
Thomas Martitz wrote:
> Bryan VanDyke wrote:
>> Thomas Martitz wrote:
>>
>>> Bryan VanDyke wrote:
>>>
>>>> Thomas Martitz wrote:
>>>>
>>>>
>>>>> Linus Nielsen Feltzing wrote:
>>>>>
>>>>>> Mike Holden wrote:
>>>>>>
>>>>>>> Maybe leading zeros should only be stripped if another digit follows
>>>>>>> them?
>>>>>>>
>>>>>>> I use names like 00RockFaves.m3u, 00ClassicRock.m3u for playlists
>>>>>>> that I
>>>>>>> have created (as opposed to original artist albums), and the leading
>>>>>>> zerozero is deliberately there to sort them at the top.
>>>>>>>
>>>>>> That's an interesting observation. I believe leading zeroes are
>>>>>> treated like whitespace in the current code, but in this case I think
>>>>>> that the final zero should be kept.
>>>>>>
>>>>>> Linus
>>>>>>
>>>>> That's not trivial, and adds complexity. You basically need to
>>>>> look at
>>>>> the current, the next, and one more for this, instead of just the
>>>>> current char.
>>>>>
>>>>>
>>>> Actually it not that bad.
>>>>
>>>> Pseudo code:
>>>>
>>>> get current
>>>> get next
>>>> while (current != null && next != null && current == '0' && next is a
>>>> number)
>>>> {
>>>> current = next
>>>> next = get next
>>>> }
>>>>
>>>>
>>>>
>>> Now imagine this for every char in a string, and for every string in a
>>> file list (with some 100 files). It's three-times (or even more) more
>>> complexity than just.
>>> while (is_zero(a))
>>>a = next;
>>>
>>> We're on embedded, and thus slow systems. Your would surely work well on
>>> a desktop app, but for mp3-players we need fast and small code. The gain
>>> has to justify the code, and I don't think it does it in this example.
>>>
>>>
>>
>> What about something like this. Taking in consideration the isspace
>> function/comparison was removed? And isdigit is supposed to give nonzero
>> on nodigit values.
>>
>> /* skip over leading zeros */
>> while ('0' == ca && nat_isdigit(ca_next) )
>> {
>> ca = to_int(a[++ai]);
>> ca_next = to_int(a[ai+1]);
>> }
>>
>>
>>
> I've found a simpler solution for this. Trying the code raises the
> following problem:
>
> 00 < 0b < 01 < 1
That look right. Zero is a valid number. A leading zero before a zero is
still zero.
00 -> 0
0b -> 0b
01 -> 1
1 -> 1
01 == 1
strcmp -> 01 < 1
right?
>
> Zeros before except the final zeros are ignored, and the final zero
> before characters is not ignored. But the leading zeros of numbers are
> (so that 01 is 1). Obviously 0 sorts before 1.
>
Re: how is strnatcmp aka "Interpret numbers while sorting" supposed to sort?
Thomas Martitz wrote:
> Bryan VanDyke wrote:
>> Thomas Martitz wrote:
>>
>>> Linus Nielsen Feltzing wrote:
>>>
>>>> Mike Holden wrote:
>>>>
>>>>> Maybe leading zeros should only be stripped if another digit follows
>>>>> them?
>>>>>
>>>>> I use names like 00RockFaves.m3u, 00ClassicRock.m3u for playlists
>>>>> that I
>>>>> have created (as opposed to original artist albums), and the leading
>>>>> zerozero is deliberately there to sort them at the top.
>>>>>
>>>> That's an interesting observation. I believe leading zeroes are
>>>> treated like whitespace in the current code, but in this case I think
>>>> that the final zero should be kept.
>>>>
>>>> Linus
>>>>
>>> That's not trivial, and adds complexity. You basically need to look at
>>> the current, the next, and one more for this, instead of just the
>>> current char.
>>>
>>>
>>
>> Actually it not that bad.
>>
>> Pseudo code:
>>
>> get current
>> get next
>> while (current != null && next != null && current == '0' && next is a
>> number)
>> {
>> current = next
>> next = get next
>> }
>>
>>
>>
> Now imagine this for every char in a string, and for every string in a
> file list (with some 100 files). It's three-times (or even more) more
> complexity than just.
> while (is_zero(a))
>a = next;
>
> We're on embedded, and thus slow systems. Your would surely work well on
> a desktop app, but for mp3-players we need fast and small code. The gain
> has to justify the code, and I don't think it does it in this example.
>
What about something like this. Taking in consideration the isspace
function/comparison was removed? And isdigit is supposed to give nonzero
on nodigit values.
/* skip over leading zeros */
while ('0' == ca && nat_isdigit(ca_next) )
{
ca = to_int(a[++ai]);
ca_next = to_int(a[ai+1]);
}
Re: how is strnatcmp aka "Interpret numbers while sorting" supposed to sort?
Thomas Martitz wrote:
> Linus Nielsen Feltzing wrote:
>> Mike Holden wrote:
>>> Maybe leading zeros should only be stripped if another digit follows
>>> them?
>>>
>>> I use names like 00RockFaves.m3u, 00ClassicRock.m3u for playlists that I
>>> have created (as opposed to original artist albums), and the leading
>>> zerozero is deliberately there to sort them at the top.
>>
>> That's an interesting observation. I believe leading zeroes are
>> treated like whitespace in the current code, but in this case I think
>> that the final zero should be kept.
>>
>> Linus
> That's not trivial, and adds complexity. You basically need to look at
> the current, the next, and one more for this, instead of just the
> current char.
>
Actually it not that bad.
Pseudo code:
get current
get next
while (current != null && next != null && current == '0' && next is a
number)
{
current = next
next = get next
}
Re: how is strnatcmp aka "Interpret numbers while sorting" supposed to sort?
Dominik Riebeling wrote: > Hi, > > I started wondering how the value "as whole numbers" for the setting > "interpret numbers while sorting" is intended to work. Currently it > seems to get changed in svn quite often. However, I haven't seen a > consensus how this feature is supposed to work (read: sort) gathered, > especially before committing. A recent discussion is here: > http://www.rockbox.org/irc/log-20090317#17:53:35 > > Maybe I've missed such a consensus -- in this case someone please > point me to the right direction and ignore this mail :) Changing the > behaviour of this setting frequently is a rather bad thing IMO. We > need to specify how we want it to work and implement it that way. > Doing this kind of "discussion in svn" is a bad thing and can only > lead to confusion among users. We didn't do this for the "study mode" > feature either, even if there was a consensus to change it. > > Now, how should this feature sort? From my point of view, I'd expect it to > - treat digits as numbers. A value of "00" equals to zero and thus > gets sorted before the number 1, regardless if that is "1", "01" or > "001". Completely skipping the zero (as it's only leading zeros) is as > broken as to not strip leading zeros -- "003" should equal to 3 and > "01" to 1, thus the latter sorting before the former. A situation > where a folder can contain files starting with "02" and "4" the same > time is something that could happen and still not being intentional > (just think of copying files from various albums to a mix folder). > Either treat digits as number or don't treat them as numbers at all. > - Spaces shouldn't get collapsed. A space is a space, and "interpret > numbers" doesn't tell anything about spaces. At least at some point > during the lifetime of this setting spaces were collapsed. Nothing > that is a number ... > > This still leaves some open issues I'm not sure how to deal about: > - how are floating-point numbers to be treated? "1.001" is smaller as > "1.01" when treating as numbers, so on the one hand I'd expect them to > sort that way. On the other hand, recognizing the dot as decimal > separator is broken as well -- not all languages use it as decimal > separator (like german using the comma). Stopping the number-treating > at dots is also kinda broken -- how should a naming be handled as > "discnumber.tracknumber", i.e. like "1.2", "1.10" -- which one has to > be sorted first? The best solution here might be to treat all numbers > as single numbers, regardless if they might be floating point numbers > -- I guess it's more common to have a "1.3" numbering to mark > discnumber.track instead of a floating point number "1.003". > > I'm pretty sure I've missed some of my points right now :) What do > people think about this sorting thing? > > > - Dominik > I think it should just be the simplest and easiest to understand. Any consecutive run of numbers [0-9] are treated as a its value for sorting purposes. This means any non-digit is treated like a separator. Which would include punctuation, spaces, etc. This also avoid trying to figure out what the person meant by using a period. Was it a separator, equivalent to US comma, region setting, real number, etc? That's just a road nobody is going to agree on. Same thing if a person is using punctuation, leading zeros, etc to control the sort order. There's no way to read the persons mind on what they intended. In all likelihood they're going to use the ASCII sort anyways. The various implementation that have been used by RB have tried to eat spaces so a 1 a001 a 01 Are all equal to a1. I say throw that out too. 1. Numbers sort before Non-numbers. - Leading zeros are striped. A leading zero on a zero is still zero. - 000 becomes 0. - Some of the code that has been used has trouble with this. 2. Lesser number before greater. - 1,2,3,4 etc 3. Anything else strcmp.
Re: Default on or off
Bryan VanDyke wrote: > Mike Holden wrote: >> As a side debate (subject line altered appropriately), should it be >> enabled by default? >> >> Personally I would say no, since it changes current functionality. I have >> no need for this feature since I only play playlists directly, so the >> names of the actual music files have no interest or meaning for me. >> > > I vote off by default. > >> However I do have some "custom" playlists (i.e. mixes, not original artist >> albums), and I labelled them all beginning with 00 (zero zero) so that >> they sorted first in my list of playlists. Once this new feature was >> implemented, my playlists suddenly disappeared into the big list of >> playlists, so that 00Rock.m3u sorted under R while 00ClassicRock.m3u >> sorted under C. > > > The implementation from before the revert had a bug where it stripped > ALL zeros instead of just LEADING zeros. So if the number was 0, with or > without leading zeros,it was removed. ie > > 0 -> 0 > 00 -> nothing > 01 -> 1 > 002 ->2 > > This was reported in FS#10029. I submitted a fix for it FS#10030 but > unfortunately it got lost in the revert. > > The fix did this > 0 -> 0 > 00 -> 0 > 01 -> 1 > 002 -> 2 > > >> Fortunately I follow the discussions on here so I was aware of the change >> and what I needed to alter in my settings to disable it. >> >> I would vote for new features which change existing functionality to be >> disabled by default. Do we have a general policy on this? > > oops. too quick with the copy and paste. before 0 -> nothing 00 -> nothing 01 -> 1 002 -> 2 after 0 -> 0 00 -> 0 01 -> 1 002 -> 2
Re: Default on or off
Mike Holden wrote: > As a side debate (subject line altered appropriately), should it be > enabled by default? > > Personally I would say no, since it changes current functionality. I have > no need for this feature since I only play playlists directly, so the > names of the actual music files have no interest or meaning for me. > I vote off by default. > However I do have some "custom" playlists (i.e. mixes, not original artist > albums), and I labelled them all beginning with 00 (zero zero) so that > they sorted first in my list of playlists. Once this new feature was > implemented, my playlists suddenly disappeared into the big list of > playlists, so that 00Rock.m3u sorted under R while 00ClassicRock.m3u > sorted under C. The implementation from before the revert had a bug where it stripped ALL zeros instead of just LEADING zeros. So if the number was 0, with or without leading zeros,it was removed. ie 0 -> 0 00 -> nothing 01 -> 1 002 ->2 This was reported in FS#10029. I submitted a fix for it FS#10030 but unfortunately it got lost in the revert. The fix did this 0 -> 0 00 -> 0 01 -> 1 002 -> 2 > > Fortunately I follow the discussions on here so I was aware of the change > and what I needed to alter in my settings to disable it. > > I would vote for new features which change existing functionality to be > disabled by default. Do we have a general policy on this?
Re: about FS #10030
Thomas Martitz wrote: > Bryan VanDyke wrote: >> Sorry about posting a file and not a patch. I have patch files now if >> anyone wants/needs them. The task has been closed and I don't know how >> to add them after-the-fact. >> >> Just for clarification, the file isn't a reversion but was intended to >> be a patch for 10029 and the code at the time of 10029, but the task was >> closed and code change before I could post my patch. >> >> Bryan >> >> > Ok, I re-opened. Upload your diff. I'm seeing the differences, but you > removed a lot of code again which I added (code of the original > implementation). > > We still agreed on keeping the original implementation, so don't be sad > if it's getting closed right after again. > > Best regards, kugel. > No problem. Patch uploaded. Thanks. Bryan :)
about FS #10030
Sorry about posting a file and not a patch. I have patch files now if anyone wants/needs them. The task has been closed and I don't know how to add them after-the-fact. Just for clarification, the file isn't a reversion but was intended to be a patch for 10029 and the code at the time of 10029, but the task was closed and code change before I could post my patch. Bryan
Re: Summer of Code 2009
Vladimir Pantelic wrote: > alex wallis wrote: >> >> >>> Robert Menes wrote: On Tue, Feb 24, 2009 at 5:31 AM, Dave Chapman wrote: > I think I would support such an application - audio codecs are always > welcome, even though RealAudio seems to be becoming less and less > used each > year. > While that may be true, there's always the case of that one oddball out there somewhere who hangs on to some old or obscure format and wants to be able to still make use of their files. That being said, I would welcome another new audio codec, and I would welcome RealAudio support. I have a few very old radio shows that I can no longer get that are RA files. >>> >>> transcode them, no? >> >> My understanding is that although it is possible to transcode >> compressed formats it is never a good idea as the resulting file is >> never as good quality as the original. > > you mentioned "very old radio shows", so how "good" are they to start > with :-) > > > You only loose quality if you go from one lossy format to another lossy format right? So why not convert them to a lossless format, Like a wav or flac file?
Re: Call for testers and DSP brains
Bryan VanDyke wrote: > pondlife wrote: >> Hi all, >> >> I'd very much like to see FS#8894 in SVN at some point. This allows speed >> to be changed independently of pitch. It's particularly useful with audio >> books/podcasts (and maybe would be useful for audible fast forward/rewind). >> >> However, it has had problems with locking up when EQ/crossfeed are in use, >> perhaps when CPU usage gets too high (given that it fails on target and >> never on the sim). Or maybe it's something to do with the various DSP >> initialisations being done incorrectly. >> >> However, I can no longer repro this on my real H300, so I wonder if it's due >> to another bug that's recently been fixed. >> >> So... I'd like help with two things: >> >> 1) People to test the patch and report back. >> >> 2) Rockbox DSP gurus to take a look at it. It might be something obvious. >> And if you think you can improve the audio quality, feel free to do that too >> ;) >> >> The other issue to be is that it grabs a chunk of static memory - I think >> this should be allocated from the audio buffer only when the feature is >> first enabled (restarting playback as needed). >> >> pondlife >> >> >> >> > > > Iriver H10 5g > Fresh pull and the 090218 patch. > With Speed turned on. > > Crossfeed - can't get it lock up. Seems to work fine. > > With Bass, Treble, Eq on. > > I can change the settings while a song is playing and everything is fine. > > If I skip to the next song, ffw, or try playing a new song with the > setting already on, lock up. > > Bryan > > Follow up to my previous post. I think the tdspeed_doit function being called in dsp_process in file dsp.c is returning a bad number. If I add a check after it my system no longer freezes. this is against the tdspeed_090218.patch --- dsp.c 2009-02-18 15:55:47.026741200 -0500 +++ dsp2.c 2009-02-18 15:24:04.551093200 -0500 @@ -1177,6 +1177,9 @@ if(dsp->tdspeed_active) samples = tdspeed_doit(tmp, samples); +if (samples <= 0) +break; + if (dsp->apply_gain) dsp->apply_gain(samples, &dsp->data, tmp); Bryan
Re: Call for testers and DSP brains
pondlife wrote: > Hi all, > > I'd very much like to see FS#8894 in SVN at some point. This allows speed > to be changed independently of pitch. It's particularly useful with audio > books/podcasts (and maybe would be useful for audible fast forward/rewind). > > However, it has had problems with locking up when EQ/crossfeed are in use, > perhaps when CPU usage gets too high (given that it fails on target and > never on the sim). Or maybe it's something to do with the various DSP > initialisations being done incorrectly. > > However, I can no longer repro this on my real H300, so I wonder if it's due > to another bug that's recently been fixed. > > So... I'd like help with two things: > > 1) People to test the patch and report back. > > 2) Rockbox DSP gurus to take a look at it. It might be something obvious. > And if you think you can improve the audio quality, feel free to do that too > ;) > > The other issue to be is that it grabs a chunk of static memory - I think > this should be allocated from the audio buffer only when the feature is > first enabled (restarting playback as needed). > > pondlife > > > > Iriver H10 5g Fresh pull and the 090218 patch. With Speed turned on. Crossfeed - can't get it lock up. Seems to work fine. With Bass, Treble, Eq on. I can change the settings while a song is playing and everything is fine. If I skip to the next song, ffw, or try playing a new song with the setting already on, lock up. Bryan
