English Amiga Board


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

 
 
Thread Tools
Old 20 August 2014, 21:23   #1
AGS
XoXo/Tasko Developer
AGS's Avatar
 
Join Date: Dec 2013
Location: Munich
Age: 44
Posts: 450
Question string starts with

Can you show me an asm routine that checks if the string in a0 starts with the string in a1? Both are null terminated.
AGS is offline  
Old 20 August 2014, 21:29   #2
thomas
Registered User
thomas's Avatar
 
Join Date: Jan 2002
Location: Germany
Posts: 5,852
Code:
loop:
	cmp.b	(a0)+,(a1)+
	bne.s	loop
	subq.l	#1,a1
	tst.b	(a1)
	bne	does_not_match

Edit: no, that one does not stop if both strings are equal. This one is better:

Code:
loop:
	move.b	(a0)+,d0
	cmp.b	d0,(a1)+
	bne	does_not_match
	tst.b	d0
	bne.s	loop
Edit2: no, does not work. This should do:

Code:
loop:
	move.b	(a0)+,d0
	move.b	(a1)+,d1
	cmp.b	d0,d1
	bne	check

	tst.b	d0
	bne.s	loop

	bra	strings_are_equal

check:
	tst.b	d1
	bne	does_not_match

does_match:

Last edited by thomas; 20 August 2014 at 21:40.
thomas is online now  
Old 20 August 2014, 21:32   #3
AGS
XoXo/Tasko Developer
AGS's Avatar
 
Join Date: Dec 2013
Location: Munich
Age: 44
Posts: 450
Thanks but as far I can see the bne.s schould be a beq.s? (in your first example)
AGS is offline  
Old 20 August 2014, 21:46   #4
thomas
Registered User
thomas's Avatar
 
Join Date: Jan 2002
Location: Germany
Posts: 5,852
Forget the first two tries. That was just brainstorming.
thomas is online now  
Old 20 August 2014, 21:52   #5
alkis
Registered User

 
Join Date: Dec 2010
Location: Athens/Greece
Age: 48
Posts: 492
Quote:
Originally Posted by thomas View Post
Forget the first two tries. That was just brainstorming.
*HouseMD voice* Differential diagnosis, people!
alkis is offline  
Old 20 August 2014, 22:07   #6
AGS
XoXo/Tasko Developer
AGS's Avatar
 
Join Date: Dec 2013
Location: Munich
Age: 44
Posts: 450
Ok, works, thank you. By the way, in my case it can't happen that both strings are equal.
AGS is offline  
Old 20 August 2014, 22:23   #7
alkis
Registered User

 
Join Date: Dec 2010
Location: Athens/Greece
Age: 48
Posts: 492
Hmm, I think gcc came up with a better one (unless I have a bug)

Code:
loop:   move.b (a1)+,d0
        cmp.b (a0)+,d0
        beq.s loop
        tst.b d0
        bne does_not_start_with_a1
;a0 starts with a1 here
Edit: The above code doesn't guard for the '\0' char. So, in theory it might not work in case where strings are equal and have at least one byte common after their ending. Adding the guard for the \0 char, makes gcc copy Thomas

Code:
.L3:
        move.b (%a0)+,%d0
        move.b (%a1)+,%d1
        cmp.b %d0,%d1
        jne .L2
        tst.b %d0
        jne .L3
        ;match here
        
.L2:   tst.b %d1
        bne do_not_match

Last edited by alkis; 20 August 2014 at 22:49.
alkis is offline  
Old 20 August 2014, 22:43   #8
thomas
Registered User
thomas's Avatar
 
Join Date: Jan 2002
Location: Germany
Posts: 5,852
Quote:
Originally Posted by alkis View Post
Hmm, I think gcc came up with a better one (unless I have a bug)

Code:
loop:   move.b (a1)+,d0
        cmp.b (a0)+,d0
        beq.s loop
        tst.b d0
        bne does_not_start_with_a1
;a0 starts with a1 here
It reads past the end if both strings are equal.
thomas is online now  
Old 20 August 2014, 22:47   #9
mc6809e
Registered User
 
Join Date: Jan 2012
Location: USA
Posts: 304
Quote:
Originally Posted by AGS View Post
Can you show me an asm routine that checks if the string in a0 starts with the string in a1? Both are null terminated.
If the empty string always matches (this is often true by convention), then this should work:

Code:
  
 next:
           move.b (a1)+, d0
           beq.s match
           cmp.b (a0)+, d0
           beq.s next
  
 no_match:
           ...
 match:
           ...
mc6809e is offline  
Old 20 August 2014, 22:52   #10
AGS
XoXo/Tasko Developer
AGS's Avatar
 
Join Date: Dec 2013
Location: Munich
Age: 44
Posts: 450
In my case:

- there are no empty strings, neither a0 nor a1
- the strings are never just equal
AGS is offline  
Old 21 August 2014, 22:31   #11
Lonewolf10
AMOS Extensions Developer
Lonewolf10's Avatar
 
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 40
Posts: 1,920
Quote:
Originally Posted by mc6809e View Post
Code:
           beq.s next

Alkis and mc6809e, I thought there was no beq.s instruction and that the minimum conditional branch was beq.w? I know Devpac accepts beq.s, but I believe it converts it to beq.w. Am I wrong?
Lonewolf10 is offline  
Old 21 August 2014, 23:49   #12
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 43
Posts: 3,086
To thomas:

Test your code before you post it
Thorham is offline  
Old 22 August 2014, 17:28   #13
alkis
Registered User

 
Join Date: Dec 2010
Location: Athens/Greece
Age: 48
Posts: 492
Quote:
Originally Posted by Lonewolf10 View Post
Alkis and mc6809e, I thought there was no beq.s instruction and that the minimum conditional branch was beq.w? I know Devpac accepts beq.s, but I believe it converts it to beq.w. Am I wrong?
Umm, I was hand-polishing the code that gcc produced, I think it was a 'jeq'.

Nevertheless, after you raised the point, I checked with the first 68000 manual that I found on my hard disk, and it says that the displacement for bCC is either a byte or word. I guess that makes beq.s valid.

Edit: Also, I compiled to .o and when I 'objdump' it, gcc says "beq.s"

Last edited by alkis; 22 August 2014 at 17:34.
alkis is offline  
Old 22 August 2014, 17:41   #14
StingRay
move.l #$c0ff33,throat

StingRay's Avatar
 
Join Date: Dec 2005
Location: Berlin/Joymoney
Posts: 6,238
Quote:
Originally Posted by Lonewolf10 View Post
Alkis and mc6809e, I thought there was no beq.s instruction and that the minimum conditional branch was beq.w? I know Devpac accepts beq.s, but I believe it converts it to beq.w. Am I wrong?
Strictly speaking, there is indeed no beq.s instruction (but most assemblers accept that syntax) but there sure is beq.b, i.e. a short distance (byte) branch! It won't be converted to beq.w (unless the distance is too large).
StingRay is offline  
Old 22 August 2014, 19:31   #15
Lonewolf10
AMOS Extensions Developer
Lonewolf10's Avatar
 
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 40
Posts: 1,920
Quote:
Originally Posted by StingRay View Post
Strictly speaking, there is indeed no beq.s instruction (but most assemblers accept that syntax) but there sure is beq.b, i.e. a short distance (byte) branch! It won't be converted to beq.w (unless the distance is too large).
alkis and Stingray, thanks

So there is a bytewise short distance conditional branch. I'll have to change some of my game code as I have been using word branch's (e.g. beq.w) where a byte one would be sufficient!
Lonewolf10 is offline  
Old 22 August 2014, 20:55   #16
mc6809e
Registered User
 
Join Date: Jan 2012
Location: USA
Posts: 304
Quote:
Originally Posted by Lonewolf10 View Post
Alkis and mc6809e, I thought there was no beq.s instruction and that the minimum conditional branch was beq.w? I know Devpac accepts beq.s, but I believe it converts it to beq.w. Am I wrong?
As others have pointed out it's just a branch with signed byte displacement.

It saves one word of space and takes eight cycles when a branch is not taken versus 12 cycles for the the 16-bit displacement version.

That doesn't sound like a big win since those four cycles are only saved if the branch isn't taken, but it can make a difference in loops where there's a bailout branch in the middle of the loop that usually falls through.
mc6809e is offline  
Old 22 August 2014, 21:52   #17
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,265
Just type
BEQ
without the size extension and let the assembler worry about it it will always do a better job than the programmer when it comes to this kind of peephole optimizations.
Leffmann is offline  
Old 23 August 2014, 00:04   #18
mc6809e
Registered User
 
Join Date: Jan 2012
Location: USA
Posts: 304
Quote:
Originally Posted by Leffmann View Post
Just type
BEQ
without the size extension and let the assembler worry about it it will always do a better job than the programmer when it comes to this kind of peephole optimizations.
Almost always

Code:
 
 nextstring: move.l (a2)+, d1
           beq nextstring
            move.l -4(a2), a1
 loop1: move (a0)+, d0
           beq match
           cmp.b (a1)+, d0
           beq loop1
  
 nomatch:
 ...
 match: org $2000
 ...
Suppose that
beq nextstring 
is optimized into
beq.s nextstring 
and that moves
match: 
from being 126 bytes away to 128 bytes away from
beq match
?

In that case
beq match 
must be turned into
beq.w match
.

The faster code sequence then is data-dependent.

If more time is spent searching for the next string, then the first branch should be a short branch.
If more time is spent searching for the substring then the first branch should be word sized.
mc6809e is offline  
Old 23 August 2014, 13:56   #19
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,265
Sure but this is not a very common scenario, and I would say at this point you're reasoning and optimizing on algorithm level, so it's outside the scope of what the assembler does.

The reality is that a programmer who is not using an optimizing assembler will always end up spending more time writing more clutter into the code, and get a worse result.
Leffmann is offline  
Old 23 August 2014, 14:32   #20
matthey
Banned
 
Join Date: Jan 2010
Location: Kansas
Posts: 1,284
There is a longword displacement branch for the 68020 also.

Bcc.B = Bcc.S signed 8 bit displacement, 2 byte instruction length
Bcc.W signed 16 bit displacement, 4 byte instruction length
Bcc.L signed 32 bit displacement, 6 byte instruction length
DBcc signed 16 bit displacement, 4 byte instruction length
FBcc.W signed 16 bit displacement, 4 byte instruction length
FBcc.L signed 32 bit displacement, 6 byte instruction length

Quote:
Originally Posted by mc6809e View Post
As others have pointed out it's just a branch with signed byte displacement.

It saves one word of space and takes eight cycles when a branch is not taken versus 12 cycles for the the 16-bit displacement version.

That doesn't sound like a big win since those four cycles are only saved if the branch isn't taken, but it can make a difference in loops where there's a bailout branch in the middle of the loop that usually falls through.
Byte displacement branches save instruction fetch and one word of ICache also. If you want to be lazy then program in C which knows how to optimize this.

Quote:
Originally Posted by Leffmann View Post
Just type
BEQ
without the size extension and let the assembler worry about it it will always do a better job than the programmer when it comes to this kind of peephole optimizations.
Most assemblers can't optimize forward branches but a warning message can usually be turned on. Vasm is the only assembler I am aware of that can optimize branches in both directions. This is one of the nicest features of vasm as I too leave my branches unsized allowing for optimization.

Quote:
Originally Posted by mc6809e View Post
[/code] Suppose that
beq nextstring 
is optimized into
beq.s nextstring 
and that moves
match: 
from being 126 bytes away to 128 bytes away from
beq match
?
Vasm does multiple optimization passes which I believe takes care of displacements that come into range due to optimizations.
matthey 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
highlight string kkhard Coders. C/C++ 0 15 August 2014 04:26
Project 500 starts... Paul_s Hardware pics 34 03 July 2008 01:01
The updating starts :) Galahad/FLT Amiga scene 14 30 September 2005 18:58
Winuae stop starts! stainy support.WinUAE 1 14 November 2001 01:36

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 08:36.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.
Page generated in 0.09233 seconds with 15 queries