gbadev.org forum archive

Is there anything that allows the stepping through of assembly code? VBA has the disassemble feature, but it's hard to control. For example, I am implementing binary search, first iteratively and then recursively. Here is the iterative code:

Code:

/* C code
int bsearch2(int array[], int key, int size)
{
int high, low, mid;

low = 0;
high = size - 1;

while(low <= high)
{
mid = (high + low)>>1;

if(array[mid] == key)
return mid;
else if(array[mid] > key)
high = mid - 1;
else
low = mid + 1;
}

return -1;
}
*/
@ r0: pointer to array
@ r1: key to search for
@ r2: size of array
bsearch2:
sub r2, r2, #1 @ r2 = high value
mov r3, #0 @ r3 = low value

loop:
cmp r3, r2 @ if low > high, key not in array
movgt r0, #-1
bxgt lr
add r4, r2, r3 @ r4 = high + low
mov r4, r4, lsr#1 @ r4 = mid = r4/2
add r5, r0, r4
ldr r5, [r5] @ r5 = *(array + mid)
cmp r5, r1 @ array[mid] == key
moveq r0, r4
bxeq lr
subgt r2, r4, #1
addlt r3, r4, #1
b loop

It always returns -1, but I don't know when it is returning -1.

Thanks,
Yasir

No$ allows assembly stepping...

Replace moveq r0, r4 and bxeq lr with b end and add a section:

Code:

end:
/* Debug */
mov r1, #0x0
ldr r1, [r1]

mov r0, r4
bx lr

Fire up the DOS version of VBA (forgot what it was called) and add a read breakpoint for the address 0x00000000. I've also noticed that you used registers 4 and 5, but they are not pushed into stack before hand. Add the neccesary code to solve that.

The freeware version of no$ does not have any debugging features.

strager wrote:

Replace moveq r0, r4 and bxeq lr with b end and add a section:

Code:

end:
/* Debug */
mov r1, #0x0
ldr r1, [r1]

mov r0, r4
bx lr

Fire up the DOS version of VBA (forgot what it was called) and add a read breakpoint for the address 0x00000000. I've also noticed that you used registers 4 and 5, but they are not pushed into stack before hand. Add the neccesary code to solve that.

What does loading contents of address 0x0 do?
Is there someway to set breakpoints in assembly code within GDB?

ymalik wrote:

What does loading contents of address 0x0 do?
Is there someway to set breakpoints in assembly code within GDB?

The data at 0x00000000+ is BIOS, which is not readable and will cause an exception (error).

I don't know how to set up GDB, so I wouldn't know. Sorry.

Ok, an error occurs. Then what?

Make a breakpoint in SDL.

Compile your assembler with -g, like you would with C, and use VBA with insight. Works ok. VBA seems a bit buggy with the size of steps, occasionally skipping several opcodes for some reason, but for the price you can't complain.

Quirky wrote:

Compile your assembler with -g, like you would with C, and use VBA with insight. Works ok. VBA seems a bit buggy with the size of steps, occasionally skipping several opcodes for some reason, but for the price you can't complain.

I thought it was insight that caused this leap stepping... Pissed me off more than I could endure, specially when you are used to win32 debuggers.

One cause seems to be a bug in VBA, stepping through code in the VBA built in debugger shows the behaviour fairly clearly. I assume this behaviour is being passed on to Insight, most of the time it has no effect as each line of C compiles to several operations, but could occasionally cause problems.

Another cause would be compiling with optimistation - that will have a bearing on the way the flow of the code goes and could look weird compared to the C original. I've seen code with 3 calls to a function like this:

Code:

if (whatever)
function(a, b);
else if (something_else)
function(b, c);
else
function(d, e);

Where a break on the first and final function calls would *both* be triggered in a single pass. I assume there's only one real branch instruction to the function and the other paths simply set up the registers. Plus thumb has to add in extra branches depending on the size of your if...else's.

I got binary search to work.
I hooked up the SDL version of VBA with Insight. I was able to step through the assembly code line by line, therefore I don't know where you guys are coming from by saying that VBA skips over multiple lines of code. I could also view the registers. I noticed that the middle index was being computed correctly, but the wrong element was being loaded into r5. I then realized that I was dealing with an array of ints, so I had to multiply the offset by 4.
Insight was very nice. The thing that I hated was the register window kept going into the background when hit the next ASM instruction button, and that I couldn't use the keyboard to step through ASM code. Here is the code:

Code:

/* C code
int bsearch2(int array[], int key, int size)
{
int high, low, mid;

low = 0;
high = size - 1;

while(low <= high)
{
mid = (high + low)>>1;

if(array[mid] == key)
return mid;
else if(array[mid] > key)
high = mid - 1;
else
low = mid + 1;

}

return -1;
}
*/
@ r0: pointer to array of ints
@ r1: key to search for
@ r2: size of array
bsearch2:
stmda r13!, {r4-r5}
sub r2, r2, #1 @ r2 = high value
mov r3, #0 @ r3 = low value

loop:
cmp r3, r2 @ if low > high, key not in array
movgt r4, #-1
bgt end
add r4, r2, r3 @ r4 = high + low
mov r4, r4, lsr#1 @ r4 = mid = r4/2
mov r4, r4, lsl#2 @ offset in multiple of 4 bytes, not 1 byte
@ could have done just lsl#1, but did this for clarity's sake
add r5, r0, r4 @ r5 = array + mid
mov r4, r4, lsr#2 @ change back to logical 1 element offset
ldr r5, [r5] @ r5 = *(array + mid)
cmp r5, r1 @ array[mid] == key
beq end
subgt r2, r4, #1
addlt r3, r4, #1
b loop

end:
mov r0, r4
ldmib r13!, {r4-r5}
bx lr

Now I want to do this recursively.

Last edited by ymalik on Sat Jun 11, 2005 3:41 am; edited 1 time in total

ymalik wrote:

Now I want to do this recursively.

Good for you. :-P

ymalik wrote:

The freeware version of no$ does not have any debugging features.

Is there a reason (e.g. under 18) that you can't use PayPal? Or are you using a computer that can't run Windows or FreeDOS (e.g. a Mac, or a Linux box with the entire HD reformatted to ext3 or Reiser4)?

The only kind of recursion that you should do with bsearch or any other true in-place algorithm is tail recursion, and the asm equivalent of tail recursion is a GOTO, called 'b' in ARM. But for real recursion (e.g. qsort), the procedure is to push r1-3 and r12 (if you need to keep them across calls), bl to the start of the function, pop r1-3 and r12 (if you pushed them), and read the return value out of r0.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

tepples wrote:

Is there a reason (e.g. under 18) that you can't use PayPal? Or are you using a computer that can't run Windows or FreeDOS (e.g. a Mac, or a Linux box with the entire HD reformatted to ext3 or Reiser4)?

PayPal means that there's money involved, and I don't want to spend money on this. I haven't even tested anything on hardware yet.

Quote:

The only kind of recursion that you should do with bsearch or any other true in-place algorithm is tail recursion, and the asm equivalent of tail recursion is a GOTO, called 'b' in ARM. But for real recursion (e.g. qsort), the procedure is to push r1-3 and r12 (if you need to keep them across calls), bl to the start of the function, pop r1-3 and r12 (if you pushed them), and read the return value out of r0.

But I want to learn how to do function calls. Using GOTO won't allow be to do that.

ymalik wrote:

tepples wrote:

the procedure is to push r1-3 and r12 (if you need to keep them across calls), bl to the start of the function, pop r1-3 and r12 (if you pushed them), and read the return value out of r0.

But I want to learn how to do function calls.

That is a function call. Please read the ARM/Thumb Procedure Call Standard (PDF) for details.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

gbadev.org forum archive

ASM > Stepping though ASM: binary search

#45365 - ymalik - Fri Jun 10, 2005 12:19 am

#45370 - Miked0801 - Fri Jun 10, 2005 12:57 am

#45380 - strager - Fri Jun 10, 2005 1:49 am

#45382 - ymalik - Fri Jun 10, 2005 3:04 am

#45412 - strager - Fri Jun 10, 2005 1:18 pm

#45416 - ymalik - Fri Jun 10, 2005 2:59 pm

#45426 - strager - Fri Jun 10, 2005 5:18 pm

#45433 - Quirky - Fri Jun 10, 2005 5:41 pm

#45434 - isildur - Fri Jun 10, 2005 5:43 pm

#45457 - Quirky - Fri Jun 10, 2005 9:07 pm

#45475 - ymalik - Sat Jun 11, 2005 1:08 am

#45478 - strager - Sat Jun 11, 2005 2:37 am

#45485 - tepples - Sat Jun 11, 2005 4:42 am

#45527 - ymalik - Sat Jun 11, 2005 5:13 pm

#45529 - tepples - Sat Jun 11, 2005 5:53 pm