Assembly Language Program Design

Question

This is a homework assignment problem and I tried to solve this all last night but I am still a newbie in Assembly language.

Dont give me the full solution, just give me a hint.

Design an ARM Assembly Language program that will examine a 32-bit value stored in R1 and count the number of contiguous sequences of 1s. For example, the value: 01110001000111101100011100011111 contains six sequences of 1s.

Write the final value in register, R2.

Now, the algorithm I think is to read each character one by one, and increase i by 1 everytime it faces 2 continuous 1s. But how to do it in Assembly Language?

Answer 1

Write a loop to shift the word left or right (doesn't matter) until the word is all zeros. The carry flag gives you the value of the next bit.

If carry is 1 and the previous carry was zero you're starting a new sequence of 1s. Then set a previous-was-a-first-one flag. (I assume that by contiguous you mean at least 2.)

If carry is 1 and previous-was-a-first-one is set you have a contiguous series, and increment your counter. Clear the previous-was-a-first-one flag.

If carry is 0 then clear the previous-was-a-first-one.

edit
Apparently "contiguous" doesn't require more than 1 bit, and then it's even simpler:

Set `previous' to `0`.
Shift left until word is all zeros.
If `carry` = `1` and `previous` = `0` increment counter.
Set `previous` to `carry`.

Answer 2

Here's a solution that iterates over the number of strings, rather than the number of bits in the word. Since I'm not really familiar with ARM assembly language, I'll give it in C. Since it only uses bitwise operators, it'll translate pretty much directly into assembly code.

int nstrings (unsigned long int x)
{
   int result = 0;

   /* convert x into a word that has a '1' for every transition from
    * 0 to 1 or 1 to 0 in the original word.
    */
   x ^= (x << 1);

   /* every pair of ones in the new word represents a string of ones in
    * the original word. Remove them two at a time and keep count.
    */
   while (x) {
     /* remove the lowest set bit from x; this represents the start of a
      * string of ones.
      */
     x &= ~(x & -x);
     ++result;

     /* remove the next set bit from x; this represents the end of that
      * string of ones.
      */
     x &= ~(x & -x);
   }
   return result;
}

Answer 3

Just suggestion as asked. You need to shift throught each bits, this can be done by shifting the number to the right. Before shifting, check the value of the rightmost bit, this can be achieved by the operation AND with the costant 1. Use some temp to store the last value checked, to increment a counter on the "rising edge" ie when the previous value change from 0 to 1, in pseudo code

SET T1=0
SET CNT=0
WHILE INPUT != 0 DO
    IF INPUT AND 1 != 0 AND T1 == 0 INC CNT
    T1 =  INPUT AND 1
    RIGHT SHIFT INPUT
END WHILE

Answer 4

1. A given register X will have the result. Init it with zero.
2. Take the original value to be processed and store it in two registers, say A and B.
3. Rotate A to the right one bit, do a XOR of A with B, put the result in A.
4. Apply a 1h mask to A, putting the result in B.
5. Sum B to X.
6. Shift A one bit to the right and, if not zero, loop to step 4
7. Divide X by 2 (shift it right one bit)

This works because the result of the XOR in step 3 will have a pair of 1's at each point in which there was a transition. So if you then count how many 1's you have, and divide it by 2, you'll have how many transitions there were. Which gives you the number of blocks of consecutive values.

Now, if X results in 0 you either have all 1's or all 0's. So you could start by checking if the original value is 0 and returning imediately with zero in such case, without even runing the steps above. If it is not, and X is 0, you return 1. If not, you divide it by 2 again (since the number of blocks with 1 has to be half the number of distinct blocks, of course).