Moduls in ARM assembly question

[LoGiCaL__]

Hi Guys,

First time posting on the forums. So, my question is about some code I'm using as a tutorial. The reference is from this link: https://thinkingeek.com/2013/01/20/arm- ... -chapter-6 . The C version of the code I fully understand and I should also mention that I under stand what the over goal of the code is. Here is the C version:

Code: Select all

n = ...;
while(n != 1)
{
    if(n % 2 == 0)
        n = n  / 2;
    else
        n = 3 * n + 1;
}

Pretty trivial code when viewed in C. Now below is the assembly code:

Code: Select all

.text
.global main
main:
    mov r1, #123           /* r1 ← 123 */
    mov r2, #0             /* r2 ← 0 */
loop:
    cmp r1, #1             /* compare r1 and 1 */
    beq end                /* branch to end if r1 == 1 */
 
    and r3, r1, #1         /* r3 ← r1 & 1 */
    cmp r3, #0             /* compare r3 and 0 */
    bne odd                /* branch to odd if r3 != 0 */
even:
    mov r1, r1, ASR #1     /* r1 ← (r1 >> 1) */
    b end_loop
odd:
    add r1, r1, r1, LSL #1 /* r1 ← r1 + (r1 << 1) */
    add r1, r1, #1         /* r1 ← r1 + 1 */
 
end_loop:
    add r2, r2, #1         /* r2 ← r2 + 1 */
    b loop                 /* branch to loop */
 
end:
    mov r0, r2
    bx lr

My question is about line 10 and the 'and' instruction. I understand this is the logical bit wise and. However, I don't understand how it works in this context. I believe this to be the modulo part from the C version of the code. I can't put into words how this is computing to 0 or 1. For example how would and r3, #123, #1 compute to 1? I would greatly appreciate any explanation or link point to an in depth explanation. Thanks in advance!

[jahboater]

"%" here is the remainder after dividing by 2. Clearly it can only return 1 or 0. And happily that is just the value of the least significant bit.

'&' is the logical and between each of the 32 bits

1 and 1 gives 1
1 and 0 gives 0
0 and 1 gives 0
0 and 0 gives 0

This is done for each of the 32 bit positions of the two operands.
In this case only the least significant bit is ever looked at because it is and'ed with one.
So and'ing a number with one sets all the bits above the first one to zero.
Here is what it looks like in binary, using a calculator:-

Code: Select all

>> 1
Bin (63) 00000000 00000000 00000000 00000000 | 00000000 00000000 | 00000000 | 00000001 (0)
Oct 1,  Dec 1,  Hex 1,  Ascii SOH,  Roman I
>> 123
Bin (63) 00000000 00000000 00000000 00000000 | 00000000 00000000 | 00000000 | 01111011 (0)
Oct 173,  Dec 123,  Hex 7B,  Ascii '{',  Roman CXXIII
>> 123 & 1
Bin (63) 00000000 00000000 00000000 00000000 | 00000000 00000000 | 00000000 | 00000001 (0)
Oct 1,  Dec 1,  Hex 1,  Ascii SOH,  Roman I
>> 123 % 2
Bin (63) 00000000 00000000 00000000 00000000 | 00000000 00000000 | 00000000 | 00000001 (0)
Oct 1,  Dec 1,  Hex 1,  Ascii SOH,  Roman I

For "123 & 1" you can see the far right bit is set for both numbers and so returns 1.

Code: Select all

>> 122
Bin (63) 00000000 00000000 00000000 00000000 | 00000000 00000000 | 00000000 | 01111010 (0)
Oct 172,  Dec 122,  Hex 7A,  Ascii 'z',  Roman CXXII
>> 122 & 1
Bin (63) 00000000 00000000 00000000 00000000 | 00000000 00000000 | 00000000 | 00000000 (0)
Oct 0,  Dec 0,  Hex 0,  Ascii NUL
>> 122 % 2 
Bin (63) 00000000 00000000 00000000 00000000 | 00000000 00000000 | 00000000 | 00000000 (0)
Oct 0,  Dec 0,  Hex 0,  Ascii NUL

For "122 & 1" the far right bit is not set for 122, and so 0 must be returned - see the truth table above.

These are exactly the same as 123 remainder 2, or 122 remainder 2 (except that "and" is far far quicker to execute).

"remainder" on the Pi involves two costly instructions. First division (sdiv), then it multiplies the result and subtracts it from the original - using a special "multiply and subtract" instruction (mls).
"and" on the other hand is one single very fast instruction (one clock cycle or better).
On a Pi Zero division/remainder requires a library function call which is horribly slow.

Some programmers would have written:-

Code: Select all

  if( n & 1 )
    n = 3 * n + 1; 
  else
    n >>= 1;

But of course a modern C compiler would make these obvious optimizations for you.

[LoGiCaL__]

Got it! Thanks so much for taking the time to provide an in-depth explanation. It was exactly what I needed. Cheers!