BBC BASIC
Programming >> Libraries >> Sortlib queries
http://bbcbasic.conforums.com/index.cgi?board=libraries&action=display&num=1487680565
Sortlib queries
Post by mavison on Feb 21st, 2017, 11:36am

Just about the last problem I have to resolve with converting a program from RISC OS to BBC4W to BBCSDL is related to sorting.

From what I can see, the SDL sortlib always sorts strings as if an smode of 2 (ASCII) is specified. Case is never ignored.

The BBC4W version is different - in that, case is always ignored!

I note that the SORTTEST.BBC in General examples does not seem to test with mixed case strings.

Is this me or the libraries? Here is some example code of mine...
Code:
   10 REM TestSort   20   30 INSTALL @lib$ + "sortlib"   40 DIM array$(100)   50   60 FOR D% = 0 TO 1   70   IF D% THEN PRINT "Descending" ELSE PRINT "Ascending"   80   PRINT "  Mode     1     2     3     4     5     6     7     8     9     10"   90   PROCsort(D%,0)                  :REM word sort, case sensitive  100   PROCsort(D%,1)                  :REM word sort, ignore case  110   PROCsort(D%,2)                  :REM ASCII sort  120   PROCsort(D%,&1000)              :REM string sort, case  sensitive  130   PROCsort(D%,&1001)              :REM string sort, ignore cas  140 NEXT  150 END  160  170 DEF PROCsort(D%,M%)  180 array$() = "??","AAA" ,"bbb","ccc","DDD","eee","fff","GGG","HHH","iii","JJJ"  190 C% =10  200 @%=&5  210 PRINT ~M%;  220 sort% = FN_sortinit(D%,M%)  230 CALL sort%,array$(1)  240 FOR I% = 1 TO C%  250   PRINT TAB(5+I%*6);array$(I%);  260 NEXT  270 PRINT  280 ENDPROC
Re: Sortlib queries
Post by Richard Russell on Feb 21st, 2017, 1:58pm

on Feb 21st, 2017, 11:36am, mavison wrote:
From what I can see, the SDL sortlib always sorts strings as if an smode of 2 (ASCII) is specified.

That's correct, the smode value is ignored in BBCSDL. With BB4W it determines whether the strings are compared using the Windows CompareString API function (and if so with what parameters) or using a simple ASCII code comparison (repz cmpsb instruction). In BBCSDL the option of using CompareString is of course not available, so the ASCII method is used all the time.

Attempting to reproduce the case-insensitive comparison performed by CompareString would be difficult; I'm not even sure that the algorithm is published. If you read the description of the NORM_IGNORECASE flag at MSDN it will give you an idea of just how problematic emulating that behaviour would be!

What I do if I want to perform a case-insensitive sort, whilst preserving the case of the sorted items, is to create a 'key' array containing the strings converted to lowercase. Sorting the original string array using the lowercase array as the key achieves the desired result. This method gives you complete control over how the key array is generated so is more flexible.

Richard.
Re: Sortlib queries
Post by mavison on Feb 21st, 2017, 2:31pm

OK, I can probably use a lowercase key array.

But it would have saved me a lot of time and frustration if the SDL sort had rejected the smode that it could not handle!
Re: Sortlib queries
Post by Richard Russell on Feb 21st, 2017, 2:53pm

on Feb 21st, 2017, 2:31pm, mavison wrote:
But it would have saved me a lot of time and frustration if the SDL sort had rejected the smode that it could not handle!

It never occurred to me to do that. I think I was fixated on the complication of how to make SORTLIB work on an ARM processor - particularly because I don't know ARM assembly language - rather than 'trivial' issues like the smode value. As it is, making a cross-platform version of the library was probably one of the hardest things I've ever done.

That's not meant to be an excuse, but rather an explanation of how things that might (reasonably) seem important to you were not uppermost in my mind. The whole exercise of creating BBCSDL has been a race against time because of my mental deterioration.

On the salient point, one complication is deciding which values of smode should be accepted and which rejected. Would you prefer any value other than 2 to be rejected (even though for many practical purposes 0, 2 and &1000 do much the same thing) or should only the case-insensitive values (1 and &1001) be rejected?

Richard.
Re: Sortlib queries
Post by mavison on Feb 21st, 2017, 3:29pm

No need to apologise - BB4W & BBCSDL are both great achievements!

I think if smode=2 is the only one that works as documented, all others that do not should be rejected. I believe in safe coding!

I am used to using ARM code under BBC Basic under RISC OS - just ask if you want anything checking.
Re: Sortlib queries
Post by Richard Russell on Feb 21st, 2017, 4:18pm

on Feb 21st, 2017, 3:29pm, mavison wrote:
I am used to using ARM code under BBC Basic under RISC OS - just ask if you want anything checking.

Thank you, although I can't see myself attempting to write ARM assembler code even with some hand-holding! What I ended up doing for SORTLIB, as I may have mentioned before, is translating the x86 assembler code to C and then compiling that for ARM as a 'binary blob', which is incorporated in the library as hex data statements.

I encountered various challenges which will sound silly to anybody familiar with the ARM CPU. One of those was that the compiler generated 16-bit 'thumb' code and I was initially puzzled as to why it crashed. Of course all I had to do was add 1 to the value returned by FN_sortinit(), the LSB of the called address being the flag that indicates that it is thumb rather than 32-bit ARM code. Obvious when you know!

As an 'outsider' as far as the ARM is concerned I find it interesting that when I compile BBCSDL for Android it always generates thumb code, presumably because the saving in code size outweighs any performance hit from the even-more-reduced instruction set! It makes me wonder whether a thumb-like 16-bit instruction set would have been a better choice from the very start, or is it only recent advances in CPU architecture that have made it competitive?

Are there any situations in which one would choose to compile to 32-bit ARM code these days?

Richard.
Re: Sortlib queries
Post by mavison on Feb 21st, 2017, 5:31pm

I am the wrong person to ask! I have only written 'normal' 32 bit ARM code (as used in RISC OS), never Thumb code. I believe Thumb is becomming more popular because it is now being used in memory-limited environments. But there are probably more complex reasons.
Re: Sortlib queries
Post by Richard Russell on Feb 21st, 2017, 5:58pm

on Feb 21st, 2017, 3:29pm, mavison wrote:
I think if smode=2 is the only one that works as documented, all others that do not should be rejected.

OK, but I can't see how to achieve it. The smode parameter is only relevant when the array being sorted is a string array, but that isn't known when FN_sortinit() is called. Only later when the machine-code sort routine is CALLed does it become evident that a string-sort is involved, but a BASIC error cannot be raised at that point.

If that analysis is correct, all I can reasonably offer is to reject values other than 0 and 2, because an smode value of zero must be allowed when only a numeric sort is being performed. That doesn't fulfil your request, and it will also reject a 'valid' set of parameters (e.g. smode being set to 1 and a numeric sort being performed).

Am I missing something?

Richard.
Re: Sortlib queries
Post by mavison on Feb 22nd, 2017, 4:03pm

Hmmm yes - I see your problem. Other values of smode can be valid if strings not sorted. If it cannot be trapped easily, then in the absence of updated SDL docs (and I hope someone helps you with those) perhaps the only way is to put a big REMark in the sortlib itself. Certainly I looked in there for any clues why I was having problems, and perhaps others might too.

[The sort module I wrote for RISC OS to do very similar functions allows asc/desc & case/sign ignores to be set for each array, which is why I did not immediately see there was a problem with my request!]

Thanks
Martin