''' A forum member suggested that I should post this sample
''' code here. It is a comb sort, generally faster than a
''' bubble sort.
'''
TYPE my_type
my_sortkey AS STRING * 80 '' Key record
my_stuff AS STRING * 80 '' More data
more_stuff AS STRING * 240 '' Still more data
END TYPE
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
FUNCTION PBMAIN() AS LONG
'''
DIM this_one (0 TO 5000) AS GLOBAL my_type
DIM stp (0 TO 5000) AS GLOBAL my_type POINTER
‘’’ Below: variables used in comb-sort algorithm
DIM
chgd AS GLOBAL INTEGER, _ ' Set to 0 (nothing changed
' on this iteration), or to 1
ktr AS GLOBAL INTEGER, _ ' Number of instances,
' or items to sort
ktra AS GLOBAL INTEGER, _ ' Working value of ktr,
' gradually diminished
ng AS GLOBAL INTEGER ' A measure of the separation
' between two items to be
' compared, initially ktr \ 2,
' eventually 1
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
ktr = 0
' ' ' Read several thousand instances of this_one,
' ' ' letting ktr = number of instances. Each instance
' ' ' consists of a my_sortkey and two other strings,
‘ ‘ ‘ all read in from files, with appropriate editing.
' ' ' The reading / editing step is not a bottleneck, and
' ' ' is fairly fast.
' ' ' No data are placed in instance (0), which is a dummy,
' ' ' so instance (ktr) is the last one populated.
'' Below: Make POINTERs for instances 0 to 5000,
'' even if ktr < 5000 . . .
FOR k = 0 To 5000
stp(k) = VARPTR(this_one(k)) '' Computing POINTERs
NEXT k
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
ktra = ktr '' working value of ktr
ng = ktr \ 2 '' half of ktr (integer division)
' ' ' Below, the CALL passes stp(0), but this will quickly
' ' ' be incremented, so stp(1) will be the first instance
' ' ' to be considered . . .
' ' ' ASM routine to do sorting on my_sortkey . . .
CALL do_sort (stp(0))
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
''' Output all results to a properly-formatted file.
''' Output is in a loop on k from 1 to ktr, and is
'[' essentially as follows:
'''
''' @stp (k).my_stuff
''' followed by
''' @stp (k).more_stuff
''' discarding my_sortkey
'''
''' . . . with appropriate headers, blank-padding,
''' blank lines, formatting, and paging. It is a
''' relatively fast step, not a bottleneck.
'''''''''''''''''''''''''''''''''''''''''''''''''''''''
''' SUB do_sort follows. It is a comb-sort, and works
''' perfectly, but is still the slowest step in this
''' application.
'''
''''''''''''''''''''''''''''''''''''''''''''''''''''''
''''''''''''''''''''''''''''''''''''''''''''''''''''''
''''''''''''''''''''''''''''''''''''''''''''''''''''''
SUB do_sort (BYREF StrucPtr AS DWORD)
'' Power Basic pushes EBX, ESI, EDI.
ASM CLD
Very_top: ' Scan from the top
ASM MOV chgd, 0 ; Set or reset "changed" flag . . .
ASM LEA EBX, ktra ; Pointer to ktra
ASM MOV EAX, [EBX] ; EAX = ktra
ASM CMP EAX, 1 ; Testing for exit, if ktra has been
' decremented to 1
ASM JE Labexit
ASM LEA EBX, ng ; Pointer to ng
ASM SUB EAX, [EBX] ; Subtract ng from ktra.
ASM MOV ECX, EAX ; This ECX is based on (ktra - ng).
' It determines how far down in the
' table the testing goes on the current
' iteration.
ASM MOV EAX, [EBX] ; EAX = ng
ASM SAL EAX, 2 ; Quadrupled
ASM LEA EBX, disp
ASM MOV [EBX], EAX ; disp (displacement) in bytes =
' 4 * ng between stp( ) pointers
' of the two strings to be compared
ASM MOV EDX, StrucPtr ; Pointer to stp(0). Scan will
' start with stp(1). Below this
' point, EDX will always = stp ( ).
''' Scan will go from the top of the array to a bottom
''' which gradually moves up as "heavier" items sink to
''' the bottom and "lighter" ones rise to the top. When
''' ktra, the working value of the bottom of the set,
''' has been decremented all the way to 1 (top of the
''' set), sorting is finished. It is also finished if
''' an iteration fails to exchange a pair of items,
''' provided that at least one bubble-sorting iteration
''' has been made.
'''
''' "Very_top" starts a new iteration from the top to the
''' current bottom.
'''
''' "Intermediate" starts a comparison between two
''' my_sortkey strings and a possible exchange of
''' this_one pointers.
Intermediate:
ASM PUSH ECX ; Save master counter.
ASM ADD EDX, 4 ; Pointer to next stp ( ), initially stp(1)
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
''' Compare my_sortkey #1 with my_sortkey #2, where #2 is
''' farther down in the this_one( ) array, at least
''' according to the stp ( ) pointers. [The instances of
''' this_one are never moved. Only their stp( )
''' pointers are moved.]
ASM MOV ECX, 80 ; ECX becomes the counter to compare 80
' bytes (length of any my_sortkey).
ASM MOV ESI, [EDX] ; ESI points to my_sortkey #1.
ASM LEA EBX, disp
ASM MOV EAX, [EBX] ; disp in EAX
ASM ADD EAX, EDX ; EAX = EDX + disp, for my_sortkey #2.
ASM MOV EDI, [EAX] ; EDI points to my_sortkey #2.
ASM REPE CMPSB ; Compare strings. ESI and EDI change
' in this process. This is "repeat
' while equal," so it exits at first
' mismatch.
ASM JB Past_exchange ; "Below" = smaller ASCII value, so
' jump to avoid changing order,
' else . . .
'' Exchanging pointers to change order . . .
ASM MOV ESI, [EDX] ; First, restore original ESI and EDI.
ASM MOV EDI, [EAX]
ASM MOV [EDX], EDI ; Then, exchange their locations in the
' stp( ) array . . .
ASM MOV [EAX], ESI
ASM MOV chgd, 1 ; Set "changed" flag.
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Past_exchange:
''' Master counter (the one based on ktra) . . .
ASM POP ECX
'' Decrement and check counter, for loop-back to
'' Intermediate . . .
ASM DEC ECX
ASM JNZ Intermediate ; to compare another pair of instances
' on current iteration
'' Current iteration has ended, so narrow the range ng
‘’ (unless ng = 1) . . .
ASM LEA EBX, ng
ASM MOV EAX, [EBX] ; EAX = [EBX] = ng
ASM CMP EAX, 1 ; To test for ng = 1
ASM JE SHORT Keep_ng ; If ng was = 1, keep it, else (below)
' scale it down . .
'' Scaling down ng by 3/4. Scale factor is not an exact
'' science, and an assunmption must be made. Literature
'' suggests division by 1.3, with integer rounding, so
'' this is close . . .
ASM SAL EAX, 1 ; Double it.
ASM ADD EAX, [EBX] ; Triple it.
ASM SAR EAX, 2 ; Integer division by 4,
' can go down to 0.
ASM CMP EAX, 0 ; Testing for EAX = new ng = 0
ASM JNE SHORT Save_ng
ASM MOV EAX, 1 ; Force EAX = 1 (to be stored as ng,
' below), but only if it was = 0
' above. With ng = 1, sort will
' become a bubble-sort.
Save_ng:
ASM MOV [EBX], EAX ; Save ng, which may or may not = 1.
' [EBX] still = ng here, but not after
' this point.
ASM JMP Very_top ; To start new iteration
Keep_ng:
ASM LEA EBX, chgd ; Check "changed" flag . . .
' Note: No ehecking of chgd unless this
' iteration was a bubble-sort, using
' ng = 1
ASM MOV EAX, [EBX]
ASM SUB EAX, 0 ; To compare chgd with 0
ASM JZ Labexit ; To Labexit if no change on this
' iteration, else . . .
ASM LEA EBX, ktra
ASM MOV EAX, [EBX]
ASM DEC EAX ; Decrement ktra (move bottom upward).
ASM MOV [EBX], EAX ; Store new ktra.
ASM JMP Very_top ; To start new iteration
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Labexit:
'' Nothing to POP
END SUB '' do_sort
''' code here. It is a comb sort, generally faster than a
''' bubble sort.
'''
TYPE my_type
my_sortkey AS STRING * 80 '' Key record
my_stuff AS STRING * 80 '' More data
more_stuff AS STRING * 240 '' Still more data
END TYPE
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
FUNCTION PBMAIN() AS LONG
'''
DIM this_one (0 TO 5000) AS GLOBAL my_type
DIM stp (0 TO 5000) AS GLOBAL my_type POINTER
‘’’ Below: variables used in comb-sort algorithm
DIM
chgd AS GLOBAL INTEGER, _ ' Set to 0 (nothing changed
' on this iteration), or to 1
ktr AS GLOBAL INTEGER, _ ' Number of instances,
' or items to sort
ktra AS GLOBAL INTEGER, _ ' Working value of ktr,
' gradually diminished
ng AS GLOBAL INTEGER ' A measure of the separation
' between two items to be
' compared, initially ktr \ 2,
' eventually 1
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
ktr = 0
' ' ' Read several thousand instances of this_one,
' ' ' letting ktr = number of instances. Each instance
' ' ' consists of a my_sortkey and two other strings,
‘ ‘ ‘ all read in from files, with appropriate editing.
' ' ' The reading / editing step is not a bottleneck, and
' ' ' is fairly fast.
' ' ' No data are placed in instance (0), which is a dummy,
' ' ' so instance (ktr) is the last one populated.
'' Below: Make POINTERs for instances 0 to 5000,
'' even if ktr < 5000 . . .
FOR k = 0 To 5000
stp(k) = VARPTR(this_one(k)) '' Computing POINTERs
NEXT k
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
ktra = ktr '' working value of ktr
ng = ktr \ 2 '' half of ktr (integer division)
' ' ' Below, the CALL passes stp(0), but this will quickly
' ' ' be incremented, so stp(1) will be the first instance
' ' ' to be considered . . .
' ' ' ASM routine to do sorting on my_sortkey . . .
CALL do_sort (stp(0))
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
''' Output all results to a properly-formatted file.
''' Output is in a loop on k from 1 to ktr, and is
'[' essentially as follows:
'''
''' @stp (k).my_stuff
''' followed by
''' @stp (k).more_stuff
''' discarding my_sortkey
'''
''' . . . with appropriate headers, blank-padding,
''' blank lines, formatting, and paging. It is a
''' relatively fast step, not a bottleneck.
'''''''''''''''''''''''''''''''''''''''''''''''''''''''
''' SUB do_sort follows. It is a comb-sort, and works
''' perfectly, but is still the slowest step in this
''' application.
'''
''''''''''''''''''''''''''''''''''''''''''''''''''''''
''''''''''''''''''''''''''''''''''''''''''''''''''''''
''''''''''''''''''''''''''''''''''''''''''''''''''''''
SUB do_sort (BYREF StrucPtr AS DWORD)
'' Power Basic pushes EBX, ESI, EDI.
ASM CLD
Very_top: ' Scan from the top
ASM MOV chgd, 0 ; Set or reset "changed" flag . . .
ASM LEA EBX, ktra ; Pointer to ktra
ASM MOV EAX, [EBX] ; EAX = ktra
ASM CMP EAX, 1 ; Testing for exit, if ktra has been
' decremented to 1
ASM JE Labexit
ASM LEA EBX, ng ; Pointer to ng
ASM SUB EAX, [EBX] ; Subtract ng from ktra.
ASM MOV ECX, EAX ; This ECX is based on (ktra - ng).
' It determines how far down in the
' table the testing goes on the current
' iteration.
ASM MOV EAX, [EBX] ; EAX = ng
ASM SAL EAX, 2 ; Quadrupled
ASM LEA EBX, disp
ASM MOV [EBX], EAX ; disp (displacement) in bytes =
' 4 * ng between stp( ) pointers
' of the two strings to be compared
ASM MOV EDX, StrucPtr ; Pointer to stp(0). Scan will
' start with stp(1). Below this
' point, EDX will always = stp ( ).
''' Scan will go from the top of the array to a bottom
''' which gradually moves up as "heavier" items sink to
''' the bottom and "lighter" ones rise to the top. When
''' ktra, the working value of the bottom of the set,
''' has been decremented all the way to 1 (top of the
''' set), sorting is finished. It is also finished if
''' an iteration fails to exchange a pair of items,
''' provided that at least one bubble-sorting iteration
''' has been made.
'''
''' "Very_top" starts a new iteration from the top to the
''' current bottom.
'''
''' "Intermediate" starts a comparison between two
''' my_sortkey strings and a possible exchange of
''' this_one pointers.
Intermediate:
ASM PUSH ECX ; Save master counter.
ASM ADD EDX, 4 ; Pointer to next stp ( ), initially stp(1)
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
''' Compare my_sortkey #1 with my_sortkey #2, where #2 is
''' farther down in the this_one( ) array, at least
''' according to the stp ( ) pointers. [The instances of
''' this_one are never moved. Only their stp( )
''' pointers are moved.]
ASM MOV ECX, 80 ; ECX becomes the counter to compare 80
' bytes (length of any my_sortkey).
ASM MOV ESI, [EDX] ; ESI points to my_sortkey #1.
ASM LEA EBX, disp
ASM MOV EAX, [EBX] ; disp in EAX
ASM ADD EAX, EDX ; EAX = EDX + disp, for my_sortkey #2.
ASM MOV EDI, [EAX] ; EDI points to my_sortkey #2.
ASM REPE CMPSB ; Compare strings. ESI and EDI change
' in this process. This is "repeat
' while equal," so it exits at first
' mismatch.
ASM JB Past_exchange ; "Below" = smaller ASCII value, so
' jump to avoid changing order,
' else . . .
'' Exchanging pointers to change order . . .
ASM MOV ESI, [EDX] ; First, restore original ESI and EDI.
ASM MOV EDI, [EAX]
ASM MOV [EDX], EDI ; Then, exchange their locations in the
' stp( ) array . . .
ASM MOV [EAX], ESI
ASM MOV chgd, 1 ; Set "changed" flag.
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Past_exchange:
''' Master counter (the one based on ktra) . . .
ASM POP ECX
'' Decrement and check counter, for loop-back to
'' Intermediate . . .
ASM DEC ECX
ASM JNZ Intermediate ; to compare another pair of instances
' on current iteration
'' Current iteration has ended, so narrow the range ng
‘’ (unless ng = 1) . . .
ASM LEA EBX, ng
ASM MOV EAX, [EBX] ; EAX = [EBX] = ng
ASM CMP EAX, 1 ; To test for ng = 1
ASM JE SHORT Keep_ng ; If ng was = 1, keep it, else (below)
' scale it down . .
'' Scaling down ng by 3/4. Scale factor is not an exact
'' science, and an assunmption must be made. Literature
'' suggests division by 1.3, with integer rounding, so
'' this is close . . .
ASM SAL EAX, 1 ; Double it.
ASM ADD EAX, [EBX] ; Triple it.
ASM SAR EAX, 2 ; Integer division by 4,
' can go down to 0.
ASM CMP EAX, 0 ; Testing for EAX = new ng = 0
ASM JNE SHORT Save_ng
ASM MOV EAX, 1 ; Force EAX = 1 (to be stored as ng,
' below), but only if it was = 0
' above. With ng = 1, sort will
' become a bubble-sort.
Save_ng:
ASM MOV [EBX], EAX ; Save ng, which may or may not = 1.
' [EBX] still = ng here, but not after
' this point.
ASM JMP Very_top ; To start new iteration
Keep_ng:
ASM LEA EBX, chgd ; Check "changed" flag . . .
' Note: No ehecking of chgd unless this
' iteration was a bubble-sort, using
' ng = 1
ASM MOV EAX, [EBX]
ASM SUB EAX, 0 ; To compare chgd with 0
ASM JZ Labexit ; To Labexit if no change on this
' iteration, else . . .
ASM LEA EBX, ktra
ASM MOV EAX, [EBX]
ASM DEC EAX ; Decrement ktra (move bottom upward).
ASM MOV [EBX], EAX ; Store new ktra.
ASM JMP Very_top ; To start new iteration
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Labexit:
'' Nothing to POP
END SUB '' do_sort
Comment