/* CS 341 Spring 2002 */
/* Note segment 6 */
/* 19-Feb-2002 */
/* Taken by Apostolos Paul Pantazis */


More Bit Manipulation.

/* Check out the asm gcc construct */
   |
   |--> Middle of C program you can drop and begin writing assembler.
      Example:
 
      --> consider the following routine:
          void foo(int i, int j, char ** p)
	     {
		char c;
		  for( ; i Pretty smooth transition from hacking C to assembler.
--> Linux Kernel does this a lot when dealing with memory subsystem.
--> Note: It is important to mention(ok maybe not that important) but
    more as a trivia knowledge that if there is something that can be expressed
    in C instead of using asm construct you do:
    #ifdef IA32 ..

    "Any compliler designed for systems programing should have a way of letting
     you ger in assembler"
     Barak P, Feb 19 2002.


     In order to do all of the above you need to know how things work at the bit
     level.

     Example:
     Lets say that we are dealing with a a CPU that does not even have addition implemented
     All that we can use are the logical operations. Lets take two 32 Bit numbers and add
     them together.

     Solution
     ********
     Implement a ripple-carry adder to do so:
     /* What is Microcode */ look jargon files http://www.tuxedo.org --> find link.

    /* Code is written in C++ */ ..God nobody likes Lisp anymore?
    typedef uint32_t u;
    u add(u x, u y) 	/* I hope that all understand C++ and how this works*/
     {
        return(x + y);
     }

    Well at least what is written above is the general Idea.
    Before proceding withn the actuall code lets make a note on the
    logical operations(bitwise) &, |, ^, ~
     
    Truth tables:
    
    AND
   
    0   1
-------------
0 | 0   0
  |
1 | 0   1
  |


 Same format for the rest truth tables are:

 OR --> 00, 01
 ^  --> 01, 10
 ~  --> 10


/* ripple carry adder theory */

We add together 2 numbers and we maintain a carry. take the two bits on the far right and add them.
Put the result on x+y box. Move to the left repeating this process having the cary along
when one is produced.


We4 can hold an integer that we can swing from 0 to 31 but to do this we will need to shift by this amount. Instead we
can start with number all 0's but a 1 in the end. So far for the above operation our mask should look:

000000000000000...1

for next operation we shift mask by 1:

000000000...10

so back to our code:

typedef  uint32_t u;

u add(u x, u y)
{
   u c = 0;    /* the carry */
   u z = 0;   /* our answer*/
   u m = 0x00000001  /* must be m or 0 depending on implementation*/
   for( ; m!=0 m<<=1)
     {
       /* we need a particualr bit of z using OR */
     if(c && (x&m) ^ (y&m) || !c &&!(x&m ^ y&m))
       {
          z /= m;
       }
     }

   
Notes:

--> you could also add z/= c^(x&m) ^ (y&m)
--> or you could do:
    c = c&(x&m | y & m) | x&m & y&m) << 1;
--> Majority calculations are very expensive in logic.

The above could be easily translated in Sparc. It is just a matter of deciding
what variable goes into what register. The key is allocation of temp variables:

consider the following example:

x = y + z * t -r * g;

t_1 = z* t;
t_2 = r * g;
t_3 = y + t;
x = t_3 + t_2;

so each becomes just one assembler statment.


How about Multiplication:

Well the idea is: we take a version of x and another version of x shifted by 1 and then another version of x shifted by
z and so on until we have 1 digit with all other 31 digits thrown away and we add them. If the high digit of y is 1
we include it on the sum if it is 0 we dont include it to the sum.

u mul( u x, u y)
{
   u z = 0;
   while(y) {
    if(y & 1)  /* this should work on any base, other base might do:
     {
        z+=x;
        x <<= 1;
        y >>= 1;
     }
    return z;

} /* end function*/


Algorithm ued for multiplication is of course the schoolboy algorithm.
Truth is that with the exception of one algorithm most fo them require
throwing more hardware at the problem to make it faster.

/* e-mail maximus@cs.unm.edu fro cool trick in mul two 2x2 matrices */

/* also for the multiplicative inverse problem */