Jumping into ARM assembly

[levi]

Ah, quite right, I'd missed that.  So you're not printing out the number at all yet?

 

[Linux-SWAT]

Indeed. Only the number of digits.


I was so blocked I also had to divide the code ^^.

 

[levi]

Ah, okay, I think I see what you're doing.  I think you just need to fix that gap between the cmp and the bgt instruction then - that's what's stopping your code from finishing.  In terms of a division algorithm, there's no reason why you shouldn't have a cmp and a branch to end before you start, and a cmp and branch to loop after you've done the work each time.  Anything you do with that value, like printing it out or storing it (or incrementing that counter in your case) you'll need to do once again after the loop has finished, since the last digit will be left in R5, but if you macro some of that stuff up, unrolling the loop that one step isn't too untidy, and is just something you need to do in assembler.


On the other hand, if you want to make your design work better, with the least change, conditionally set a register to 1 after the cmp to store the result, then refer back to that register using another cmp before you decide whether to loop or not.  Three extra lines by my count; one to set that register to 0 first of all, one to set it depending on whether r5 is more than 10 (MOVGT Rx, #1), then one to compare that register again before the branch to loop.


Or, thinking it through, since you're losing a free register that way, why not always store the value of r5 before you start, and then use that value in the a cmp before the branch.  Replace the first cmp with an unconditional mov, and put that same cmp instead before the bgt, but make it compare against the new register, rather than r5.


There you are then, three ways to do it.  Take your pick.


Edit: And the ADDS is just a typo.  Change that to ADD and you're golden.

 

[dmarschal]

I hope this example will help you.


To count the digits of a decimal number you have divide the number by 10 (and print out the remainder if you wish) until you get 0.


.include "macro.mac"
.globl _start

printout =1 @ to print out the decimal number reversed
count =1 @ to print out a counter

.text
_start:
ldr r5,=163843

.if count
mov r3,#'1'
.endif

ldr r4,=0x1999999a
loop1:
umull r0,r1, r5,r4
@ r5 * r4 = r1:r0
@ r1 = r5/10
add r0,r1,r1, lsl #2
sub r0,r5,r0, lsl #1
@ r0= r5 MOD 10

.if count
push {r0,r1,r3}
mov r2,#1
add r1,sp,#8
mov r0,#console
invoke sys_write
print " "
pop {r0,r1,r3}
.endif

.if printout
orr r0,#'0'

push {r0,r1}
mov r2,#1
mov r1,sp
mov r0,#console
invoke sys_write
pop {r0,r1}
.endif

.if count
push {r1}
print "\n"
inc r3
pop {r1}
.endif

movs r5,r1
bne loop1

print "\n"

exit 0

.data
.bss
.end



One more thing. "\n" is coded as one "0xA" character in the binary file.

 

[Linux-SWAT]

I'll check out this.


Meanwhile, my code worked when I replaced div reciprocal with :


        MOV R2, #0x19000000    ; R2 is constantly 0x1999999A
        ORR R2, R2, #0x00990000
        ORR R2, R2, #0x00009900
        ORR R2, R2, #0x0000009A


taken from here :


http://www.toves.org/books/arm/

 

[Yoyobuae]

I'll check out this.


Meanwhile, my code worked when I replaced div reciprocal with :


        MOV R2, #0x19000000    ; R2 is constantly 0x1999999A
        ORR R2, R2, #0x00990000
        ORR R2, R2, #0x00009900
        ORR R2, R2, #0x0000009A


taken from here :


http://www.toves.org/books/arm/

I think your issue was that this:


ldr r10, =div_10_reciprocal @ load the magic number for /10


Loads the address of div_10_reciprocal into r10, instead of the value itself.


Maybe you should've defined div_10_reciprocal like this instead:


.set div_10_reciprocal, 429496730 @ ceil((2^32)/10)


Which creates a symbol with the 429496730 value.

 

[levi]

Hmm, in this code you load 0x199999A into R2.  In your original code you loaded a pointer to some memory containing 0x19999D1E into R10.  I don't understand the umull instruction as I've said before, so I can't say which number is more correct, if either, but in one case you use a number, in the other an address.


Edit: As Yoyobuae said.

 

[Linux-SWAT]

Hmm, in this code you load 0x000009A into R2.  In your original code you loaded a pointer to some memory containing 0x19999D1E into R10.  I don't understand the umull instruction as I've said before, so I can't say which number is more correct, if either, but in one case you use a number, in the other an address.

I just copied from the link, but I modified R2 into R10 and it worked.


Yoyobuae, tried your .set, it worked like a charm.


Here's the same dirty previous code with the .set :


.text
.align 2

.macro syswrite @ print the content of r1, must be ascii, buffer length r2 must be set
mov r0, #1 @ file descriptor 1 - stdout
svc 0 @ call the Linux kernel and print the ascii text
.endm

.macro newline
ldr r1, =newline @ point on the buffer to write, \n, a newline
mov r2, #2 @ newline buffer length
syswrite
.endm

.set div_10_reciprocal, 429496730 @ ceil((2^32)/10)

.global _start
_start:

mov r7, #4 @ system call number, 4 is 'write'
mov r5, #16384 @ set the number
mov r11, #0 @ set the digit counter
_loop:

add r11, #1 @ increment the digit counter

cmp r5, #10 @ compare the number with 10
ldr r10, =div_10_reciprocal @ load the magic number for /10
umull r3, r2, r5, r10 @ r2 = r5 / 10, r3 is overwritten
mov r5, r2 @ save the divided value
ldr r1, =asciicounter @ point on =asciicounter
add r6, r11, #48 @ convert the digit counter to ascii
str r6, [r1] @ store it to be displayed
mov r2, #1 @ buffer length
syswrite
newline
bgt _loop @ if r5 was > 10, loop

mov r7, #1 @ exit
svc 0 @ call the Linux kernel and exit

.data
asciicounter: .word 0 @ must be initialized
newline: .asciz "\n" @ \n is a newline




Result :


1
2
3
4
5


I'll go a few posts backward and see how I can optimize things, or at least be cleaner.

 

[levi]

Yes, or to convert your old code to do:


LDR R10, =div_10_reciprocal

LDR R10, [R10]



Mind you, recalling my old ARM coding, it should be possible to do a PC-relative MOV in one instruction, rather than having to load the address then load from it.  I'm just not up to speed with this new LDR meta-instruction, but if I had to guess it'd look something like:

LDR R10, [div_10_reciprocal]

 

[Yoyobuae]

Hmm, in this code you load 0x199999A into R2.  In your original code you loaded a pointer to some memory containing 0x19999D1E into R10.  I don't understand the umull instruction as I've said before, so I can't say which number is more correct, if either, but in one case you use a number, in the other an address.


Edit: As Yoyobuae said.

Both values should be equal:


0x1999999A == 429496730 == ceil(0x100000000 / 10)


Lets say there exists imaginary operation that multiplies two decimal 3 digit numbers (0 to 999) and produces a six digit result (0 to 998001). One could use this operation to synthetise division by some number, say 3:


234 * 334 = 78156


78156 / 1000 = 78 (decimals discarded)


First the number to divide is multiplied by the multiplicative inverse of 3 (ie. ceil(1000 / 3) = 334) and then the lower 3 digits of the result are discarded. umull works in a similar way, but with two 32 digit binary numbers as input and discarding the lower 32 binary digits of the result.

 

[levi]

Ah, quite right; I accidentally transposed a 67 for a 76 when copying the number.  Mystery solved.


Ah, so the umull trick is you're discarding the least significant 32-bit word?  That's why some places talk about shifting the result.  To use your decimal example


reciprocal=1000/divisor


result=input*reciprocal/1000


        =input*1000/divisor/1000


        =input/divisor


Aha!  It works because your implicitly shifting by the value you divided the divisor into in the reciprocal.


I note in your example, you represented 333.3 recursive as 334.  If you do it all by integer maths, you end up one short, but if you use floating point you can see that the result you get is 77.9ish.


So if you needed to be accurate in ARM, you could test the top bit of the least significant word:


UMULL Rlo, Rhi, Rin, [reciprocal]


ANDS R(unused), Rlo, #80000000


ADDNZ Rhi, #1


Edit: Added missing (unused), spare, parameter to the ANDS command.


Edit2: Got my low and high back to front in the umull, I think.

 

[Linux-SWAT]

A nicer code :


.text
.align 2

.macro syswrite @ print the content of r1, must be ascii, buffer length r2 must be set
mov r0, #1 @ file descriptor 1 - stdout
svc 0 @ call the Linux kernel and print the ascii text
.endm

.macro newline
ldr r1, =newline @ point on the buffer to write, \n, a newline
mov r2, #2 @ newline buffer length
syswrite
.endm

@.set div_10_reciprocal, 429496730 @ ceil((2^32)/10)

.global _start
_start:

mov r7, #4 @ system call number, 4 is 'write'
mov r5, #16384 @ set the number
mov r11, #0 @ set the digit counter
_loop:

add r11, #1 @ increment the digit counter
cmp r5, #10 @ compare the number with 10
blt _end @ branch if < 10

ldr r10, =div_10_reciprocal @ load the magic number for /10
ldr r10, [r10]
umull r3, r2, r5, r10 @ r2 = r5 / 10, r3 is overwritten
mov r5, r2 @ save the divided value

b _loop @ back to loop
_end:

ldr r1, =asciicounter @ point on =asciicounter
add r6, r11, #48 @ convert the digit counter to ascii
str r6, [r1] @ store it to be displayed

mov r2, #1 @ buffer length
syswrite
newline

mov r7, #1 @ exit
svc 0 @ call the Linux kernel and exit

.data
asciicounter: .word 0 @ must be initialized
newline: .asciz "\n" @ \n is a newline
div_10_reciprocal: .word 429496730 @ ceil((2^32)/10)






But what if the number of digits exceeds 10 ^^ ?

 

[levi]

Well, if it's more than 10 it'll start printing out A, B, C.  I think you're safe up until 127-48=79 digits with the numbers, capital letters, lower case letters and all the punctuation, which should do for demo code.  You're going to roll this up into a subroutine that doesn't count the digits in a number, it actually prints out the number, each digit of which will be less than 10, eventually, right?


Edit: You're declaring div_10_reciprocal twice there; once as via an @set, and once at the end, with a static word.  I'm honestly not sure which one the assembler will choose to use in this case.


Looks like neat code apart from that gotcha though.


Edit2: Looks to me like you can reuse input and output registers in a umull - just like you can in any other ARM instruction that I know of.

umull r3, r2, r5, r10 @ r2 = r5 / 10, r3 is overwritten


mov r5, r2 @ save the divided value

Can be replaced by:

umull r3, r5, r5, r10 @ r5 = r5 / 10, r3 is overwritten

 

[Linux-SWAT]

Yes I plan to display the state of a register.


@.set is an unremoved commentary.

 

[levi]

Oh yeah, right.


I just noticed my accuracy improver:


UMULL Rlo, Rhi, Rin, [reciprocal]


ANDS R(unused), Rlo, #80000000


ADDNZ Rhi, #1


Could instead be done using the more obvious and clearer:


UMULL Rlo, Rhi, Ri, [reciprocal]


CMP Rlo, #80000000


ADDGE Rhi, #1


However, I note that the reciprocal you're using already rounds up the number (2^32/10 comes out as a number 0x19999999.6), and in my tests, using 0x1999999A rather than 0x9999999 seems to work for both 1000000 and 999999, providing you always round down (which discarding to lowest 32 bits does, in practice).  So perhaps my test to round to nearest isn't actually needed in practice.  It provides the wrong result with 1 followed by 11 zeroes, but the wrong answer still has the right number of digits.


That said, 1 followed by 10 zeroes timed by 0x19999999 divided by 2^32 gives you 999999998.6..., so even if you round that to nearest, you're out by one the other way.  Not surprising I suppose, as 2^32 maths only gives you 9 and a half significant digits accuracy.

 

[Exophase]

However, I note that the reciprocal you're using already rounds up the number (2^32/10 comes out as a number 0x19999999.6), and in my tests, using 0x1999999A rather than 0x9999999 seems to work for both 1000000 and 999999, providing you always round down (which discarding to lowest 32 bits does, in practice).  So perhaps my test to round to nearest isn't actually needed in practice.  It provides the wrong result with 1 followed by 11 zeroes, but the wrong answer still has the right number of digits.


That said, 1 followed by 10 zeroes timed by 0x19999999 divided by 2^32 gives you 999999998.6..., so even if you round that to nearest, you're out by one the other way.  Not surprising I suppose, as 2^32 maths only gives you 9 and a half significant digits accuracy.

We're synthesizing unsigned integer division here, that's supposed to floor/truncate. You can turn that into round to nearest by adding to the dividend beforehand.


When performing (a * reciprocal_b), some positive error is allowed so long as it isn't greater than or equal to 1.0. On the other hand, no negative error is allowed.


So:


(a * reciprocal_b) - (a / b) >= 0

reciprocal_b - (1 / b) >= 0


Meaning that you can't allow any negative error on reciprocal_b, so any fractional part must be rounded to the whole (with ceil). On the other hand...


(a * reciprocal_b) - (a / b) < 1

reciprocal_b - (a / b) < (1 / a)


The error must be < 1 / a. With the format I used reciprocal_b has 0 integer bits and 32 fractional bits, so the positive error is < (1 / (2^32)). So long as a < (2^32) (which is the limit of the number format) this will hold.

 

[Yoyobuae]

(a * reciprocal_b) - (a / b) < 1

reciprocal_b - (a / b) < (1 / a)


The error must be < 1 / a. With the format I used reciprocal_b has 0 integer bits and 32 fractional bits, so the positive error is < (1 / (2^32)). So long as a < (2^32) (which is the limit of the number format) this will hold.

With reciprocal_b=0x1999999A, the assumption:


(a * reciprocal_b) - (a / b) < 1


Fails for a=0x40000005 (1073741829) and other higher numbers ending in 9 decimal digit. For much higher numbers it starts failing for the values of a ending in 7 or 8 decimal digit.


Works perfectly for values of a under 30 bits (0x0 to 0x3FFFFFFF) though.

 

[Exophase]

With reciprocal_b=0x1999999A, the assumption:



(a * reciprocal_b) - (a / b) < 1


Fails for a=0x40000005 (1073741829) and other higher numbers ending in 9 decimal digit. For much higher numbers it starts failing for the values of a ending in 7 or 8 decimal digit.


Works perfectly for values of a under 30 bits (0x0 to 0x3FFFFFFF) though.

You're right, I didn't really work that out right. It's not that (a * reciprocal_b) - (a / b ) < 1 fails in this case (it's about 0.1), but that the error flips it over into the next whole number.


So I guess that should really be formulated as:


((a / b) % 1) + ((a * reciprocal_b) % 1) < 1


Not really sure what bounds that though >_> Getting the first part (non-negative) right is really the key, after that I tend to just iterate the range to make sure it works for what I need...

 

[Linux-SWAT]

Here's a code that displays the digit count of a number, and the number in question on the next line :

                .text
                .align 2

                .macro syswrite         @ print what r1 points at, must be ascii, buffer length r2 must be set
                mov r0, #1              @ file descriptor 1 - stdout
                svc 0                   @ call the Linux kernel and print the ascii text
                .endm

                .macro newline
                ldr r1, =newline        @ point on the buffer to write, \n, a newline
                mov r2, #1              @ newline buffer length
                syswrite
                .endm

                .global _start
_start:

                mov r7, #4              @ system call number, 4 is 'write'
                mov r5, #8192           @ set the number
                mov r11, #0             @ set the digit counter
_loop:

                add r11, #1             @ increment the digit counter
                cmp r5, #10             @ compare the number with 10
                blt _end                @ branch if < 10

                mov r8, r5
                ldr r10, =div_10_reciprocal     @ load the magic number for /10
                ldr r10, [r10]
                umull r3, r2, r5, r10           @ r2 = r5 / 10, r3 is overwritten
                mov r5, r2                      @ save the divided value
                mov r10, #10
                mul r9, r2, r10                 @ multiply the divided value by 10
                sub r8, r9                      @ substract the original value to get the remainder
                push {r8}                       @ push the remainder on the stack
                b _loop                         @ back to loop
_end:

                mov r8, r5                      @ push the last digit, with the highest weight
                push {r8}

                ldr r1, =asciicounter           @ point on =asciicounter
                add r6, r11, #48                @ convert the digit counter to ascii
                str r6, [r1]                    @ store it to be displayed

                mov r2, #1                      @ buffer length
                syswrite
                newline
_reversed:

                pop {r8}                        @ display the number, beginning with the highest weight
                ldr r1, =asciicounter           @ point on =asciicounter
                mov r6, r8
                add r6, #48                     @ convert the number to ascii
                str r6, [r1]                    @ store it to be displayed
                mov r2, #1                      @ buffer length
                syswrite
                subs r11, #1                    @ the digit counter is now used for the number display loop
                bne _reversed

                newline

                mov r7, #1      @ exit
                svc 0           @ call the Linux kernel and exit

                .data
asciicounter:                 .word 0                 @ must be initialized
newline:                      .ascii "\n"             @ \n is a newline
div_10_reciprocal:            .word 429496730         @ ceil((2^32)/10)

 

[levi]

mov r10, #10


mul r9, r2, r10 @ multiply the divided value by 10

That's inefficient, and simply unnecessary (unless I've misread the mul docs).  Why not:


mul r9, r2, #10


?


Also, I note in your newline macro, you declare the length of a newline character is 2 bytes; that's not actually the case on linux and the Pandora - it's a single 0x0a.  I guess it works though because you've defined the contents of the newline address as a zero terminated string, so you've actually stored 0x0a and 0x00 there.  The zero byte isn't considered a printable character, so I guess it just silently ignores it.


Your comment to your syswrite macro is also not quite correct; you're not printing out the contents of r1, you're printing out what r1 points at.  But, eh, it's only a comment.


I've not got round to looking at the logic of the code yet, but initial impressions are favourable, and if you reckon it does what it's meant to then that's promising.