B From:	CSBVAX::MRGATE!chase@orc.olivetti.com@SMTP 14-APR-1988 03:33 To:	ARISIA::EVERHART% Subj:	Re: open coding multiplication      K Received: from UNIX.SRI.COM by prep.ai.mit.edu; Wed, 13 Apr 88 18:42:27 EST % Received: by unix.SRI.COM (5.31/5.14) ( 	id AA07497; Wed, 13 Apr 88 16:56:20 PST From: chase@orc.olivetti.comG Received: from ozona.orc.olivetti.com by orc.olivetti.com (3.2/SMI-3.2) ( 	id AA28697; Wed, 13 Apr 88 16:36:19 PDT@ Received: from localhost by ozona.orc.olivetti.com (3.2/SMI-3.2)( 	id AA17119; Wed, 13 Apr 88 16:36:34 PDT7 Message-Id: <8804132336.AA17119@ozona.orc.olivetti.com>  To: info-gcc@prep.ai.mit.edu. Reply-To: David Chase <chase@orc.olivetti.com>( Subject: Re: open coding multiplication ; In-Reply-To: Your message of Sat, 02 Apr 88 01:13:53 -0600. 4              <8804020713.AA27646@big-d.aca.mcc.com> # Date: Wed, 13 Apr 88 16:36:33 -0700   E Here is one (possibly correct) algorithm described in the back of the 0 Acorn Risc Machine CPU Software Manual (v 1.00).  @ ---------------------------------------------------------------- 	For Rb := Ra * C   & 	case C even (C = 2^n * D, with D odd) 		case D = 1 			Rb := (Ra << n)
 		case D != 1 # 			(recursively solve Rb := Ra * D)  			Rb := (Rb << n)  1 	case C mod 4 = 1 (C = 2^n * D + 1, D odd, n > 1)  		case D = 1 			Rb := Ra + (Ra << n) 
 		case D != 1 # 			(recursively solve Rb := Ra * D)  			Rb := Ra + (Rb << n)   0 	case C mod 3 = 1 (C= 2^n * D - 1, D odd, n > 1) 		case D = 1 			Rb := (Ra << n) - Ra 
 		case D != 1 # 			(recursively solve Rb := Ra * D)  			Rb := (Rb << n) - Ra @ ----------------------------------------------------------------  E Well, I was feeling ambitious, so I decided to program the sucker up. B Please understand that it is NOT optimal, but it is good enough inE many cases.  Also note that (because it is recursive) that fixing one = small special case (e.g., 45) can fix many others (e.g., 90).   @ ----------------------------------------------------------------+ /* Let's see if we can hack up an algorithm $    to do a constant multiply by C */- /* Pardon the style; this is intended to work 2    quickly in programmer time, not machine time */   /*0    Author: David Chase, Olivetti Research Center%    Date: Wed Apr 13 16:20:00 PDT 1988   /    Based on an algorithm described in the Acorn 2    Risc Machine CPU software manual, version 1.00. */   #include <stdio.h>   int D; int N;    #define EVEN(x) (((x) & 1) == 0) #define ODD(x) (((x) & 1) != 0) + #define SHIFTR(x) (((x) >> 1) & 0x7FFFFFFF)    fail(s) char * s; {    printf("%s\n", s);   fclose(stdout); 
   abort(); }     void reduce_to_D_and_N(C) int C; { /* C SHOULD be even */?   if (ODD(C)) fail("reduce_to_D_and_N called with odd number");      D = C; N = 0;      while (EVEN(D)) {      N++;     D = SHIFTR(D);   }  }    constant_multiply (C)       int C;  {    int d, n;     $   /* Start with the special cases */   if (C == 1) {      printf("%s", "Rb = Ra;\n");    }    else if (C == -1) {     constant_multiply(0);#    printf("%s", "Rb = Rb - Ra;\n");    }    else if (C == 0) {     printf("%s", "Rb = 0;\n");   } >   else if (C == 45) { /* Demonstrate a special special case */     constant_multiply(9); 9     printf("%s", "Rb = Rb + (Rb << 2);\n"); /* Times 5 */    }      /* General cases here */#   else if (EVEN(C)) /* EVEN CASE */      {        reduce_to_D_and_N(C); 5       d = D; n = N; /* pretend it returned d and n */   0       if (d == 1) printf("Rb = Ra << %d;\n", n);       else { 	constant_multiply(d); 	printf("Rb = Rb << %d;\n", n);        }      }    else if ((C & 3) == 1) {       reduce_to_D_and_N(C - 1); 5       d = D; n = N; /* pretend it returned d and n */   7       if (d == 1) printf("Rb = Ra + (Ra << %d);\n", n);        else { 	constant_multiply(d);& 	printf("Rb = Ra + (Rb << %d);\n", n);       }           }    else /* C mod 4 == 3 */ {        reduce_to_D_and_N(C + 1); 5       d = D; n = N; /* pretend it returned d and n */        7       if (d == 1) printf("Rb = (Ra << %d) - Ra;\n", n);        else { 	constant_multiply(d);& 	printf("Rb = (Rb << %d) - Ra;\n", n);       }    }  }    main() {   int i;     scanf("%d", &i);   while (! feof(stdin)) {      constant_multiply(i);      printf("\n");      scanf("%d", &i);   }  } @ ----------------------------------------------------------------   David Chase % Oliveetti Research Center, Menlo Park 