QSort 32 bit vs 64 bit FB

[Dinosaur]

Hi All

I am converting a rather large program from Win XP embedded to Linux.
On my Laptop I have 32 bit Linux Mint and of course FB 32 bit installed, and it compiled and ran ok.
On my Industrial Fitlet I have 64 bit Linux & FB installed and there it compiles, but fails when it tries to access msort.c

FreeBASIC Compiler - Version 1.04.0 (10-01-2015), built for linux-x86_64 (64bit)

The code for the sort routine I got from someone on the Forum a long time ago.
I know there may be better sort routines but really don't want to modify the program.

Code: Select all

Declare Sub Sort overload (sortArray() As String )
Sub Sort overload (sortArray() As String )
	Dim As Long arrayLength = Ubound( sortArray ) - Lbound( sortArray ) + 1
	QSort(  @sortArray( 0 ), arrayLength, 12, ProcPtr(String_Compare) )
End Sub

And this is where I call it from.

Code: Select all

Sub GetFileList
    Dim FileNaam As ZString * 17
    Dim FileSpec As String
    Dim As Long FileCount, FileNbr,SF,Xr
    FileSpec = Paths.Root + "/recipes/*.JVP"
    FileNaam = Dir(FileSpec, 55 )
    FileCount = 0
    Do												'Firstly count how many files
        FileNaam = Dir( )                           'look for next FileNaam
        FileCount += 1                              'update number of files found.    	
    Loop While Len(FileNaam) > 0
    Dim As String SortArray(FileCount)				'Then Dim array to that lenth
    'Now do it again
    FileSpec = Paths.Root + "/recipes/*.JVP"
    FileNaam = Dir(FileSpec, 55 )
    FileArray.Nbr  = FileCount
    FileCount = 0
    If FileArray.Nbr > 0 Then 
        If FileArray.Nbr < 500 Then         
            For Xr = 1 To FileArray.Nbr
                SortArray(Xr) = FileNaam					'save each FileNaam
                FileNaam = Dir( )                           'look for next FileNaam
            Next
        EndIf
    EndIf
	Sort (SortArray())								'now get the names sorted.
	'If FileExists(ErrControl.ErrFile) Then 
    	If FileArray.Nbr > 0 Then
            If FileArray.Nbr < 500 Then 	
            	For Xr = 1 To FileArray.Nbr
    		        FileArray.Name(Xr) = SortArray(Xr)
    	        Next
    	    Endif
    	EndIf 
	'EndIf
End Sub

I suspect that the problem is 64 bit version of FB has a different sort routine in the library, so can SKS advise me how to solve this problem.

Regards

[fxm]

Size of string descriptor = 3 Integers (12 Bytes for 32-bit, 24 Bytes for 64-bit)

Code: Select all

Declare Sub Sort overload (sortArray() As String )
Sub Sort overload (sortArray() As String )
   Dim As Long arrayLength = Ubound( sortArray ) - Lbound( sortArray ) + 1
   QSort(  @sortArray( 0 ), arrayLength, 3*Sizeof(Integer), ProcPtr(String_Compare) )
End Sub

[Dinosaur]

Hi All

fxm, thank you for that.
Such an easy fix when you know what you are doing.

Regards

[fxm]

More readable:

Code: Select all

Declare Sub Sort overload (sortArray() As String )
Sub Sort overload (sortArray() As String )
   Dim As Long arrayLength = Ubound( sortArray ) - Lbound( sortArray ) + 1
   QSort(  @sortArray( 0 ), arrayLength, Sizeof( sortArray( 0 ) ), ProcPtr(String_Compare) )
End Sub

[edit]
Corrected typo:
Sizeof( array( 0 ) )
Sizeof( sortArray( 0 ) )

[Dinosaur]

Hi All

Even better, as then I don't have to modify it for 32 bit operation.
Thank you.

Regards

[fxm]

Each array element is a string descriptor containing 3 fields (pointer to the first string character, the string size, the allocated memory size), so:
- first pointer address = first array element address
- offset between pointers = array element size.

[Dinosaur]

Hi All

fxm, the original error was raised by Allegro.
At this point I don't know where the Qsort routine resides.
Is it part of Allegro or FB. (I guess not FB as there was no reference to it.

Where would I find a description of the the calling protocol ?

Regards

[fxm]

FreeBASIC Manual / Miscellaneous / C Standard Library Functions / Searching and Sorting

[MichaelW]

qsort and bsearch are CRT functions exported from msvcrt.dll:

qsort

bsearch

The functions require a type-specific external comparison function which, because it is called from an inner loop, makes the functions relatively slow.

A type-specific sort function would be more efficient.

[Dinosaur]

Hi All

Thanks for those links MichaelW, they explain the sort routine really well.
Because I never wrote this part, I never fully understood it.

The only conflict in the description is

width
Element size in bytes.

I guess that is Integers now.

Regards

[dodicat]

Windows:
Here is the msvcrt.dll qsort, called by #include "crt/stdlib.bi"

Linux I believe can use the C language qsort in a similar way, possibly using inbuilt Gcc., but I have not used Linux for a few years.

Datatype as string here:

Code: Select all

#include "crt/stdlib.bi"

type datatype as string

Function callback Cdecl(n1 As Any Ptr,n2 As Any Ptr) As Long
    If *Cptr(DataType Ptr,n1) < *Cptr(DataType Ptr,n2) Then Return -1  'CHANGE TO  1 FOR SORTING DOWN
    If *Cptr(DataType Ptr,n1) > *Cptr(DataType Ptr,n2) Then Return  1  'CHANGE TO -1 FOR SORTING DOWN
End Function

sub sort(s() as DataType)  
qsort( @s(Lbound(s)),(Ubound(s)-Lbound(s)+1),Sizeof(s),@callback)
end sub


'=======================  EXAMPLE ===================================
#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))
#define q IntRange(97,122)         'lcase alphabet
#define RandomString chr(q,q,q,q,q,q,32,q,q,q,q,q,q,q,q,32,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q)

                print "__________original _____________"
                Dim As Long num=100
                dim as long n
                
                Redim As string s(num)
                
                For n =lbound(s) To ubound(s)
                    s(n)=RandomString 'max allowed chr( ... )=32?
                    print s(n)
                Next n
                print
                print "__________sorted _______________"
                print
                dim as double t1=timer
                sort(s())
                dim as double t2=timer
                For n =lbound(s) To ubound(s)
                    Print s(n)
                Next
                print
                print "Time taken "; t2-t1
                Sleep
                
 

And a standard quicksort, no external library, datatype string.:

Code: Select all

type datatype as string

 Sub sort(array() As DataType,begin As Long=0,Finish As Long=-1)
            If begin>finish Then begin=Lbound(array):Finish=Ubound(array)
            Dim As Long i=begin,j=finish
            static As DataType x :x=array(((I+J)\2))
                While I <= J
                While array(I) < X :I+=1:Wend 'CHANGE TO > FOR SORTING DOWN
                While array(J) > X :J-=1:Wend 'CHANGE TO < FOR SORTING DOWN
                        If I<=J Then Swap array(I),array(J): I+=1:J-=1
                Wend
                    If J >begin Then  sort(array(),begin,J)
                    If I <Finish Then sort(array(),I,Finish)
End Sub

'=======================  EXAMPLE ===================================
#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))
#define q IntRange(97,122)
#define RandomString chr(q,q,q,q,q,q,32,q,q,q,q,q,q,q,q,32,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q)

                print "__________original _____________"
                Dim As Long num=100
                dim as long n
                
                Redim As string s(num)
                
                For n =lbound(s) To ubound(s)
                    s(n)=RandomString ' Question --- max allowed chr( ... )=32?
                    print s(n)
                Next n
                print
                print "__________sorted _______________"
                print
                dim as double t1=timer
                sort(s())
                dim as double t2=timer
                For n =lbound(s) To ubound(s)
                    Print s(n)
                Next
                print
                print "Time taken "; t2-t1
                Sleep 

The standard quicksort is slightly faster on this box-(not much).
64 bit FreeBASIC is faster than 32 bit FreeBASIC for these sorts.

[Dinosaur]

Hi All

Thanks for that dodicat, I will investigate using the latter, which will mean library changes won't bother me.
The sort routine is used to display filenames on the screen in a concrete plant which are numerical names.
So instead of having to look for a number (about 400 on the screen) they can pick it from the rough area.


Regards

[MrSwiss]

@Dinosaur,

The only conflict in the description is: width = Element size in bytes.

No conflict. Explanation:
In case of a String: length of String, since a single String (of String-Array) has to have a defined length.
Aka: fixed length String = 1 Element (Size) of String-Array.
If you want to sort UIntegers: 4 Byte on FBC 32, 8 Byte on FBC 64; better defined as: SizeOf(UInteger).

[MichaelW]

For the CRT qsort, when sorting numeric arrays the comparison function need only return the result of a subtraction operation:

Code: Select all

#include "crt.bi"

''-----------------------------------------------
'' Long instead of integer so the code will work
'' without alteration on 32-bit and 64-bit FB.
''-----------------------------------------------

function compare cdecl( p1 as any ptr, p2 as any ptr ) as long
    return *cptr(long ptr, p1) - *cptr(long ptr, p2)
end function

dim as long numarray(0 to 99)

for i as integer = 0 to 99
    numarray(i) = int(rnd * 100)
    print numarray(i);chr(9);
next

qsort( @numarray(0), 100, 4, @compare )

print

for i as integer = 0 to 99
    print numarray(i);chr(9);
next

sleep

Change the order of the subtraction operation to change the order of the sort.

For sorting arrays of null-terminated strings, the comparison function must return the same value that the appropriate CRT string comparison function would return.

[dodicat]

The qsort routine lies deep within a C compiler or a C runtime.
It lies mysteriously out of our reach (or most of our reaches anyways), but the compare (callback) function is written in FreeBASIC and thus can be customised in millions of ways.
Here is an example for big integers.

Code: Select all

#include "crt/stdlib.bi"

type datatype as string


Function callback Cdecl(n1 As Any Ptr,n2 As Any Ptr) As Long
    dim as long k=1   'CHANGE TO -1 FOR SORTING DOWN
    If len(*Cptr(DataType Ptr,n1)) < len(*Cptr(DataType Ptr,n2)) Then Return -k 
    If len(*Cptr(DataType Ptr,n1)) > len(*Cptr(DataType Ptr,n2)) Then Return  k 
    if (*Cptr(DataType Ptr,n1)) > (*Cptr(DataType Ptr,n2)) Then Return  k  else return -k
End Function

sub sort(s() as DataType)  
qsort( @s(Lbound(s)),(Ubound(s)-Lbound(s)+1),Sizeof(s),@callback)
end sub


#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))
#define q IntRange(48,57)         'digit
#define RandomString chr(q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q)

  
                print "__________original _____________"
                Dim As Long num=150
                dim as long n
                
                Redim As datatype s(num)
                
                For n =lbound(s) To ubound(s)
                    s(n)=RandomString 'max allowed chr( ... )=32?
                    s(n)+=RandomString
                    dim as string tmp=(mid(s(n),1,Intrange(1,64)))
                    s(n)=iif(len(tmp)=1,tmp,ltrim(tmp,"0"))
                    if len(s(n))=0 then s(n)="0"
    
                    print s(n)
                Next n
                print
                print "__________sorted _______________"
                print
                dim as double t1=timer
                sort(s())
                dim as double t2=timer
                For n =lbound(s) To ubound(s)
                    Print s(n)
                Next
                print
                print "Time taken "; t2-t1
                Sleep   

For fun only.