string starts with

[AGS]

Can you show me an asm routine that checks if the string in a0 starts with the string in a1? Both are null terminated.

[thomas]

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:

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:

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:

[AGS]

Thanks but as far I can see the bne.s schould be a beq.s? (in your first example)

[thomas]

Forget the first two tries. That was just brainstorming.

[alkis]

Originally Posted by thomas

Forget the first two tries. That was just brainstorming.

*HouseMD voice* Differential diagnosis, people!

[AGS]

Ok, works, thank you. By the way, in my case it can't happen that both strings are equal.

[alkis]

Hmm, I think gcc came up with a better one (unless I have a bug)

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

.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

[thomas]

Originally Posted by alkis

Hmm, I think gcc came up with a better one (unless I have a bug)

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.

[mc6809e]

Originally Posted by AGS

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:

  
 next:
           move.b (a1)+, d0
           beq.s match
           cmp.b (a0)+, d0
           beq.s next
  
 no_match:
           ...
 match:
           ...

[AGS]

In my case:

- there are no empty strings, neither a0 nor a1
- the strings are never just equal

[Lonewolf10]

Originally Posted by mc6809e

           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?

[Thorham]

To thomas:

Test your code before you post it

[alkis]

Originally Posted by Lonewolf10

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"

[StingRay]

Originally Posted by Lonewolf10

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).

[Lonewolf10]

Originally Posted by StingRay

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!

[mc6809e]

Originally Posted by Lonewolf10

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.

[Leffmann]

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.

[mc6809e]

Originally Posted by Leffmann

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

 
 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.

[Leffmann]

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.

[matthey]

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

Originally Posted by mc6809e

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.

Originally Posted by Leffmann

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.

Originally Posted by mc6809e

[/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.