BBC BASIC
« Sortlib queries »

Welcome Guest. Please Login or Register.
Jan 20th, 2018, 6:02pm


Cross-platform BBC BASIC (Win32, Linux x86, Android, Mac OS-X, Raspberry Pi)

« Previous Topic | Next Topic »
Pages: 1  Notify Send Topic Print
 thread  Author  Topic: Sortlib queries  (Read 376 times)
mavison
New Member
Image


member is offline

Avatar




PM


Posts: 27
xx Sortlib queries
« Thread started 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
 
User IP Logged

Richard Russell
Administrator
ImageImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 689
xx Re: Sortlib queries
« Reply #1 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.
« Last Edit: Feb 21st, 2017, 2:32pm by Richard Russell » User IP Logged

mavison
New Member
Image


member is offline

Avatar




PM


Posts: 27
xx Re: Sortlib queries
« Reply #2 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!
User IP Logged

Richard Russell
Administrator
ImageImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 689
xx Re: Sortlib queries
« Reply #3 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.
User IP Logged

mavison
New Member
Image


member is offline

Avatar




PM


Posts: 27
xx Re: Sortlib queries
« Reply #4 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.
User IP Logged

Richard Russell
Administrator
ImageImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 689
xx Re: Sortlib queries
« Reply #5 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.
User IP Logged

mavison
New Member
Image


member is offline

Avatar




PM


Posts: 27
xx Re: Sortlib queries
« Reply #6 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.
User IP Logged

Richard Russell
Administrator
ImageImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 689
xx Re: Sortlib queries
« Reply #7 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.
User IP Logged

mavison
New Member
Image


member is offline

Avatar




PM


Posts: 27
xx Re: Sortlib queries
« Reply #8 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

User IP Logged

Pages: 1  Notify Send Topic Print
« Previous Topic | Next Topic »

Donate $6.99 for 50,000 Ad-Free Pageviews!


This forum powered for FREE by Conforums ©
Sign up for your own Free Message Board today!
Terms of Service | Privacy Policy | Conforums Support | Parental Controls