English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Asm / Hardware

 
 
Thread Tools
Old 23 September 2013, 16:10   #1
h0ffman
Registered User
 
Join Date: Aug 2008
Location: Salisbury
Posts: 469
String sort in assembly

Does anyone have a bit of assembly for sorting strings? Trying to add an alpha sort on my file list and for some reason I can't work it out!
h0ffman is offline  
Old 23 September 2013, 17:44   #2
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,161
What's the problem, how to lexicographically compare two strings, or how to implement the sorting? Or do you have those parts down but just can't find some other bug? You'd have to also describe how you store your strings, in what encoding, and how you index them, or you'd just have to rewrite any example code I write.
Leffmann is offline  
Old 23 September 2013, 22:25   #3
h0ffman
Registered User
 
Join Date: Aug 2008
Location: Salisbury
Posts: 469
They are filenames picked up from the folder just stored one after the other with a length and BPM.

I've written the BPM sort as that is working on a word of data for comparison, so nice and easy but basically I'm just doing a bubble sort on those. I know its not the best method but its doesnt have to be particularly fast code.

Do I just compare the strings byte by byte and run the routine till theres no changes left (ala bubble sort)? Also I suppose a good thing would be to ignore the case too!
h0ffman is offline  
Old 23 September 2013, 23:49   #4
hooverphonique
ex. demoscener "Bigmama"
 
Join Date: Jun 2012
Location: Fyn / Denmark
Posts: 786
that's a simple way to do it.. it'll probably be simplest if you make sure, all strings are the same length while sorting, and swapping strings by using an array of pointers to the strings and swapping pointers..

otherwise you could do insertion sort while scanning the directory :-p
radix sort is also a good candidate for string sorting..

excellent set on sundown, btw :-)

Last edited by hooverphonique; 24 September 2013 at 11:32.
hooverphonique is offline  
Old 24 September 2013, 00:05   #5
alkis
Registered User

 
Join Date: Dec 2010
Location: Athens/Greece
Age: 47
Posts: 431
Assuming you have more or less the following structure:
Code:
struct foo {
  char *filename;
  long length;
  long bpn;
};
and also assuming you have a list of pointers to your structures that you're gonna sort (and not the structures themselves)...

find attached the .c and the produced .s from gcc for reference.
Attached Files
File Type: c foo.c (902 Bytes, 74 views)
File Type: s foo.s (1.3 KB, 72 views)
alkis is offline  
Old 24 September 2013, 00:41   #6
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,161
Quote:
Originally Posted by h0ffman View Post
Do I just compare the strings byte by byte and run the routine till theres no changes left (ala bubble sort)? Also I suppose a good thing would be to ignore the case too!
The basic lexicographical string comparison takes two characters at a time and compares them, if they are equal and non-zero it loops back, otherwise it returns the numerical difference. It's easier to work with null-terminated strings:

Code:
compare   move.b    (a0)+, d0
          move.b    (a1)+, d1
          beq       .done
          cmp.b     d0, d1
          beq       compare

.done     sub.b     d1, d0
          rts
If a borrow occurs it means A<B, zero means A=B, neither zero nor borrow means A>B, so the relative order is dictated by the character encoding.

EDIT: this one ignores leading spaces and converts upper to lower case

Code:
compare

.skip1    cmp.b     #32, (a0)+    ; skip leading spaces
          beq       .skip1
.skip2    cmp.b     #32, (a1)+
          beq       .skip2
          sub       #1, a0
          sub       #1, a1

.cmp      move.b    (a0)+, d1     ; run until end of string or until
          bsr       lowcase       ; characters differ
          move.b    d1, d0
          move.b    (a1)+, d1
          beq       .done
          bsr       lowcase
          cmp.b     d0, d1
          beq       .cmp

.done     sub.b     d1, d0        ; update condition codes with result
          rts


lowcase   cmp.b     #65, d1       ; check range 'A' to 'Z'
          blo       .noascii
          cmp.b     #90, d1
          bls       .makelow

.noascii  cmp.b     #192, d1      ; 'À' to 'Þ' and ignore 'ß' 'ÿ' '×' '÷' 
          blo       .done
          cmp.b     #222, d1
          bhi       .done
          cmp.b     #215, d1
          beq       .done

.makelow  add.b     #32, d1
.done     rts

Last edited by Leffmann; 24 September 2013 at 00:56.
Leffmann is offline  
Old 24 September 2013, 12:42   #7
pmc
rebooting...
pmc's Avatar
 
Join Date: Apr 2007
Location: Elsewhere
Posts: 1,595
h0ff: Looks like Leffmann's given you the lowdown on string comparisons. In relation to the BPM sorting, I have a very short (50 or 60 bytes or so from memory I think...?) asm insertion sort routine that you're more than welcome to.

If you want it, drop me a line at any of the usual places and I'll send it over
pmc is offline  
Old 24 September 2013, 16:33   #8
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
Radix sort is the best sort to use for string sorting.
Mrs Beanbag is offline  
Old 24 September 2013, 17:10   #9
h0ffman
Registered User
 
Join Date: Aug 2008
Location: Salisbury
Posts: 469
Bpm sort works a treat already. The ASM string examples are perfect I shall get them implemented ASAP!!
h0ffman is offline  
Old 24 September 2013, 17:25   #10
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
sorry if this is a stupid question but what does BPM mean in this context?
Mrs Beanbag is offline  
Old 24 September 2013, 17:25   #11
alkis
Registered User

 
Join Date: Dec 2010
Location: Athens/Greece
Age: 47
Posts: 431
Probably beats per minute
alkis is offline  
Old 24 September 2013, 19:14   #12
h0ffman
Registered User
 
Join Date: Aug 2008
Location: Salisbury
Posts: 469
Yes it is beat per minute.
h0ffman is offline  
Old 24 September 2013, 19:34   #13
h0ffman
Registered User
 
Join Date: Aug 2008
Location: Salisbury
Posts: 469
And cheers Leffman, the comparison works a treat My file list in my DJ app now can be sorted by file name ignoring case and BPM!

God some people can write much more elegant code that I CAN!
h0ffman is offline  
Old 25 September 2013, 16:10   #14
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,161
No probs!
Leffmann is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
ARexx string length limit amiga support.Apps 5 15 August 2015 06:00
Join variable and string in scripts. olesio support.Apps 3 31 January 2013 11:44
SetPatch 44+ copyright string amiga_user support.Apps 20 03 April 2011 01:55
LHA/LZX format string fc.studio support.Apps 12 20 December 2005 13:32

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 00:01.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.
Page generated in 0.10913 seconds with 14 queries