From:	CSBVAX::MRGATE!chase@orc.olivetti.com@SMTP 14-APR-1988 03:33
To:	ARISIA::EVERHART
Subj:	Re: open coding multiplication 


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.com
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 PDT
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.
             <8804020713.AA27646@big-d.aca.mcc.com> 
Date: Wed, 13 Apr 88 16:36:33 -0700

Here is one (possibly correct) algorithm described in the back of the
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)

	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)

	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
----------------------------------------------------------------

Well, I was feeling ambitious, so I decided to program the sucker up.
Please understand that it is NOT optimal, but it is good enough in
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
   quickly in programmer time, not machine time */

/*
   Author: David Chase, Olivetti Research Center
   Date: Wed Apr 13 16:20:00 PDT 1988

   Based on an algorithm described in the Acorn
   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);
    printf("%s", "Rb = Rb + (Rb << 2);\n"); /* Times 5 */
  }

  /* General cases here */
  else if (EVEN(C)) /* EVEN CASE */
    {
      reduce_to_D_and_N(C);
      d = D; n = N; /* pretend it returned d and n */

      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);
      d = D; n = N; /* pretend it returned d and n */

      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);
      d = D; n = N; /* pretend it returned d and n */
      
      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