Thursday, May 10, 2012

Binary Shift operation

Binary manipulation is one of the vital part in programming. We can do some manipulation through this in very efficient way. Bitwise operations are necessary for much low-level programming.
It will be frequently used in device driver development ,protocol developemnt and low-level graphics.

There are three types of shift operations present in the binary world
1)  Arithmetic (Signed Shift) or >> / <<
2)  Logical  ( Unsigned Shift) or >>> / <<<
3)  Rotational

The general logic behind shifting is

·        Shifting left by n bits on a signed or unsigned binary number "Y" has the effect of multiplying it by 2n.

                  result = (Y x 2n )

For example
Consider a binary number 139   ( 1000 1011)
139 << 1 =  278 (1 0001 0110) : Here 1 is overflow.
If you get any confusion here check the same with the value 8( 0000 1000)
8 << 1 =  8 x 21 =  16 ( 0001 0000)
·    Shifting right by n bits on a signed or unsigned binary number has the effect of dividing it by  2n.

                  result = (Y / 2n )

For example
Consider a binary number 139   ( 1000 1011)
139 >> 1 =  69

Apply the formula
result  = ( 139 / 21) =  69.5

(which rounds towards 0 for arithmetic shift and towards negative infinity for Logical shift This is one of the main different between  arithmetic and logical shift)
    
Logical shift (Un signed):
·        It always rounds down (towards negative infinity). Refer the above written example for the sample Logical shift.

Arithmetic shift (Signed):
·    It is similar to Logical shift except that left most bits will be filled with the sign bit of the original number instead of  0's
·    Consider a binary number 139   ( 1000 1011). In arithmetic shift this 1st bit represent the sign of the number. 
      1 -- represent negative
      0 -- represent positive .

      139 >> 1 =  69


     ·    It always rounds towards 0
   Arithmetic shifts can be useful as efficient ways of performing multiplication or division of signed integers

Example 1:
Calculate the result of  -16 divide by 4
      -16 / 2  = - 8
(Divide a number by 2 is equivalent to right shift a number by 1)

Binary equivalent of  16 = ( 0001 0000).


To represent the negative number we need to calculate the 2's complement of the original number
 16                         ----->   0001 0000
1's Complement      ----->   1110 1111
2's Complement      ----->   1111 0000
-16                         ----->   1111 0000

now -16 >> 1 =  1111 1000 ( This is equivalent to -8)


Rotational/ Circular  Shift :
·     Rotation shift is a circular shift. Instead of pushing  "0" it will push discarded bit.

For example if we do normal right shift operation , LSB at the right end will be discarded and a '0' will be pushed into the MSB from the left end.

But in rotational shift LSB at the right end will be removed and it will be pushed as the  MSB from the left end.
Here we need do convert a integer number into binary. Then we are going to break the binary number into smaller pieces to get the certain range of values

Sample program in C :
Consider a  integer 92 .Binary equivalent of 91 is "0101 1100"

In this binary number bits from 0 to 2 representing a particular value. And 4 to 6 representing some other value.
Bits from 0 to 2 is - "100"  Bits from 4 to 6 is - "101" .So here the requirement is break the binary number into above mentioned  range. And return the result.

#include<Stdio.h>
#include<math.h>

const int BIT_LENGTH = 31; //(0 to 31)bits
int aBArray[32];
void toBinary(long,int);
void print();

long getSensor() {
    return 2543133;
}

int getRainfall(long sensorReading) {
    int RAINFALL_START = 7;
    int RAINFALL_END = 0;
    toBinary(sensorReading, BIT_LENGTH);
    print();
    return getResult(RAINFALL_START, RAINFALL_END);
}

int getHumidity(long sensorReading) {
    int HUMIDITY_START = 15;
    int HUMIDITY_END = 11;
    return getResult(HUMIDITY_START, HUMIDITY_END);
}

int getTemperature(long sensorReading) {
    int TEMP_START = 23;
    int TEMP_END = 18;
    return getResult(RAINFALL_START, RAINFALL_END);
}
void print( ){
    int i;
    printf("\n******************RESULT: BINARY************************\n");
   
    for(i = 0; i <= BIT_LENGTH; i++) {
        printf( " %d",aBArray[i]);
        if((i + 1) % 4 ==0){
            printf(" ")
        }
     }
    printf("\n**************************************************************\n");
}

int getResult(long aStart, int aEnd) {

     int initPower = (aStart - aEnd), bit, result = 0;
     printf("\n");
    for(bit = (BIT_LENGTH - aStart);bit <= (BIT_LENGTH - aEnd); bit++) {
            result = result + (aBArray[bit] * pow(2,initPower--) );
    }
    return result;
}
void toBinary(long number, int index) {

      int remainder;
      if(number <= 1) {

           aBArray[index] = number;
          return;
      }
       remainder = number % 2;
       aBArray[index] = remainder;
       toBinary(number >> 1, --index);  
}

int main() {
   long sensorReading = getSensor();
   clrscr();
   printf("\nRainfall : %d\n", getRainfall(sensorReading));
   printf("\nHumidity : %d\n", getHumidity(sensorReading));
   printf("\nTemperature : %d\n", getTemperature(sensorReading));
   return 0;
}






Monday, May 7, 2012

Android Handler vs Asynctask

Android UI thread

If you freshly launch your application android will create a thread called "main".(Also called UI Thread).
UI thread will take care of following tasks
1) Dispatching events (Like touch, click, fling...etc) to the appropriate widgets 
2) Interacts with running components of the Android UI toolkit.

For example , if you touch the a button on screen, the UI thread dispatches the touch event to the widget, which in turn sets its pressed state and posts an invalidate request to the event queue. The UI thread de-queues the request and notifies the widget to redraw itself.

If android follows single threaded model it will do all the operation in the UI thread will lead to poor performance.

For example
Let say the user is trying to do two operations like accessing the network and pressing a button both at same time.
First it will try to finish the network operation. After finishing the network operation it will respond to the button click. Because of this applications will be appeared like hanged.

If the UI thread is blocked for more than a few seconds (Currently About 5 sec) android will show a dialog called "application not responding" (ANR) dialog.

General solution to avoid such a problem is create separate thread to do the network operation

Solution 1:                
public void onClick(View aView) {
  new Thread(new Runnable() {
    public void run() {
      Bitmap b = loadImageFromNetwork(); //Network operation
      mImageView.setImageBitmap(b);
    }
  }).start();
}

It will be looking like a solution to our problem.
But it violates the single-threaded model for the UI: The Android UI toolkit is not thread-safe and must always be manipulated on the UI thread.
Android OS will not allow threads to touch the UI element other than UI thread or main thread.

So you will get the famous exception "Called from Wrong Thread Exception"

Sample error message:

ERROR/AndroidRuntime(315): FATAL EXCEPTION: Thread-8
12-07 16:24:29.089: ERROR/AndroidRuntime(315): android.view.ViewRoot$CalledFromWrongThreadException: Only the original thread that created a view hierarchy can touch its views.


Ways to interact with the UI thread :

Following mechanisms are provided by the android through which we can interact with UI thread from any other thread.


Solution 2:
public void onClick(View v) {
  new Thread(new Runnable() {
     public void run() {
            final Bitmap b = loadImageFromNetwork();
                 mImageView.post(new Runnable() {
                   public void run() {
                          mImageView.setImageBitmap(b);
                   }
               });

  }).start();
}
    }

While implementing complex operation the code will be more complicated and difficult to read. To solve this problem android provides a new technique called Asynctask & Handler.

Threading through Handler  :

Generally Handler will be associated with the application's main thread/ UI thread.
By default UI thread will have a Handler called UI handler associated with it.

It will handle and schedule messages and runnable send from the background threads to the app UIthead /main thread.

Looper:
Looper is nothing but a MessageQueue. It will have the list of messages posted by the handler
Handler :
Assume handler as a man who is taking care of sending messages into the Loopers message queue.

Pipeline  thread :

By default thread will not have any message queue associated with it. If we want to change a thread into the pipeline thread we need to attach a Looper with it.

Every thread in java will be in one of the following states in its life cycle.

  
   
                     Normal Thread Life Cycle

Once it finished its run() method it will go to the dead state.  We can't start a dead thread once again. If we try to do it will give the IllegalThreadState exception.

But through Looper we are trying to reuse the same thread again and again until finish all the messages or jobs posted in the message queue or until call the looper.quit().
So if we want to change a Thread into a pipeline thread we need to attach a Looper with it.
Relation between Looper, Handler and Thread :
  • One important character of the Looper is that it will be associated with only one thread in  which the Looper is created.And it will be associated with a single thread through out the life time of a thread.(This association is kept for ever and can't be broken nor changed)
  • One thread can't be associated with more than one Looper.
  • But one looper can be associated with more than one Handler.
 If you see the Looper source code we can come to know that this Looper object is stored in a thread-local storage.
Sample code snippet from Looper class:

public class Looper {
          ....
          private static final ThreadLocal sThreadLocal = new ThreadLocal();
          ....

          public static final void prepare() {
                   if(sThreadLocal.get() != null) {
                             throw new RunTimeException("....");
                   }
                   sThreadLocal.set(new Looper());
          }
}

This code will ensure following things.
      1)   Looper can't be created via its constructor directly
      2)   The one and only way to create a Looper object for a thread is to call the static method
       prepare() present in the Looper class.


- prepare method first examines ThreadLocal of current thread to make sure that there isn't already a Looper associated with the thread. After the examination, a new Looper is created and saved in ThreadLocal variable   "sThreadLocal".

After creating the Looper for a thread we can call the static method loop() to check for new messages.  If any message is present in the queue it will be dispatched to the appropriate Handlers .


Sample code snippet from Looper class:

public static final void loop() {
         
          .....
          Message msg = queue.next()
          if(null != msg) {
                   msg.target.dispatchMessage(msg);
          }
          ........
}
msg.target - is the Handler from which the message is created.

So this message is dispatched to the Handlers in which the message is created and handleMessage() method will be called on this Handler and the tasks given in the handleMessage() will be executed in the Thread.

Sample code snippet from Handler:

public void handleMessage(Message aMsg) {

          switch (msg.what) {
                   cause DO_MOVIE_DOWNLOAD:
                    // Our task
                   break;
                   cause SING_THE_SONG:
                    // Our task
                   break;
                   cause DO_BREAK_DANCE:
                    // Our task
                   break;
          }
}

Handler class is mainly responsible for handling (adding, removing, dispatching) messages of current thread's MessageQueue.

A Handler instance is also bound to a thread. Looper act as a intermediate between Handler and Thread.
The binding between Handler and Thread is achieved via Looper and MessageQueue.

The relationships between Looper, Handler and MessageQueue is shown below:
       Handler (*) ---------------> (1) Looper (MessageQueue) (1) <--------------- (1) Thread

Unlike Looper, multiple Handler instances can be bound to the same thread. Whenever we call post or any methods alike on the Handler, a new message is added to the associated MessageQueue.
The target field of the message is set to current Handler instance. When the Looper received this message, it invokes dispatchMessage on message's target field, so that the message routes back to the Handler instance to be handled, but on the correct thread.