/*  Optimal divide-by-constant code generator (ARM version)
    Copyright (C) Advanced RISC Machines
*/


#include <stdio.h>
#include <stdlib.h>

#define BANNER          "generated by ARM divc"

#define DIVIDE_BY_2_MINUS_1             0
#define DIVIDE_BY_2_PLUS_1              1


typedef unsigned int uint;


uint log2( uint n )
{
  uint bit, pow, logn;

  for( bit = 0, pow = 1; bit < 31; bit++, pow <<= 1 )
  {
    if( n == pow ) logn = bit;
  }

  return( logn );
}


int powerof2( int n )
{
  return( n == ( n & (-n) ) );
}


void dodiv2m1( uint logd, uint logmsb )
{
  /* Output instructions to do division by 2^n - 1 */
  printf( "\tMOV     a1, a1, lsr #1\n" );

  while( logd < 32 )
  {
    printf( "\tADD     a1, a1, a1, lsr #%d\n", logd );
    logd <<= 1;
  }
  printf( "\tMOV     a1, a1, lsr #%d\n", logmsb - 1 );
}


void dodiv2p1( uint logd, uint logmsb )
{
  /* Output instructions to do division by 2^n + 1 */
  printf( "\tSUB     a1, a1, a1, lsr #%d\n", logd );

  while( logd < 16 )
  {
    logd <<= 1;
    printf( "\tADD     a1, a1, a1, lsr #%d\n", logd );
  }

  printf( "\tMOV     a1, a1, lsr #%d\n", logmsb );
}


void loada4( uint type, uint lsb, uint msb )
{
  /* Constant is too big to be used as an immediate constant, */
  /* so load it into register a4.                             */
  printf( "\tMOV     a4, #0x%x\n", msb );

  switch( type )
  {
  case DIVIDE_BY_2_MINUS_1:
    printf( "\tSUB     a4, a4, #0x%x\n", lsb );
    break;

  case DIVIDE_BY_2_PLUS_1:
    printf( "\tADD     a4, a4, #0x%x\n", lsb );
    break;

  default:
    fputs( "Internal error", stderr );
  }
}


void divideby2( uint type, uint n, uint lsb, uint msb )
{
  uint loglsb;
  uint logmsb;
  uint usinga4;

  loglsb = log2( lsb );
  logmsb = log2( msb );

  printf( "; %s\n\n", BANNER );
  printf( "\tCODE32\n\n" );
  printf( "\tAREA |div%d$code|, CODE, READONLY\n\n", n );
  printf( "\tEXPORT udiv%d\n\n", n );
  printf( "udiv%d\n", n );
  printf( "; takes argument in a1\n" );
  printf( "; returns quotient in a1, remainder in a2\n" );
  printf( "; cycles could be saved if only divide or remainder is required\n" );

  usinga4 = ( n >> loglsb ) > 255;
  if( usinga4 )
  {
    loada4( type, lsb, msb );
    printf( "\tSUB     a2, a1, a4\n" );
  }
  else
  {
    printf( "\tSUB     a2, a1, #%d\n", n );
  }

  /* 1/n as a binary number consists of a simple repeating pattern     */
  /* The multiply by 1/n is expanded as a sequence of ARM instructions */
  /* (there is a rounding error which must be corrected later)         */
  switch( type )
  {
  case DIVIDE_BY_2_MINUS_1:
    dodiv2m1( logmsb - loglsb, logmsb );
    /* Now do multiply-by-n */
    printf( "\tRSB     a3, a1, a1, lsl #%d\n", logmsb - loglsb );
    break;

  case DIVIDE_BY_2_PLUS_1:
    dodiv2p1( logmsb - loglsb, logmsb );
    /* Now do multiply-by-n */
    printf( "\tADD     a3, a1, a1, lsl #%d\n", logmsb - loglsb );
    break;

  default:
    fputs( "Internal error", stderr );
  }

  /* Subtract from adjusted original to obtain remainder */
  printf( "\tSUBS    a2, a2, a3, lsl #%d\n", loglsb );

  /* Apply corrections */
  printf( "\tADDPL   a1, a1, #1\n" );
  if( usinga4 )
  {
    printf( "\tADDMI   a2, a2, a4\n" );
  }
  else
  {
    printf( "\tADDMI   a2, a2, #%d\n", n );
  }

  /* Additional test required for divide-by-3, as result could be  */
  /* off by 2 lsb due to accumulated rounding errors.              */
  if( n == 3 )
  {
    printf( "\tCMP     a2, #3\n" );
    printf( "\tADDGE   a1, a1, #1\n" );
    printf( "\tSUBGE   a2, a2, #3\n" );
  }

  printf( "\tMOV     pc, lr\n\n" );
  printf( "\tEND\n" );
}


int main( int argc, char *argv[] )
{
  if( argc != 2 )
  {
    printf( "Usage: divc <n>\n" );
    printf( "Generates optimal ARM code for divide-by-constant\n" );
    printf( "where <n> is one of (2^n-2^m) or (2^n+2^m) eg. 10\n" );
  }
  else
  {
    int num;

    num = atoi( argv[ 1 ] );
    if( num <= 1 )
    {
      fprintf( stderr, "%d is not sensible\n", num );
    }
    else
    {
      uint lsb = 1;

      /* find least-significant bit */
      while( ( num & lsb ) == 0 )
      {
        lsb <<= 1;
      }

      if( powerof2( num ) )
      {
        fprintf( stderr, "%d is an easy case\n", num );
      }
      else if( powerof2( num + lsb ) )
      {
        divideby2( DIVIDE_BY_2_MINUS_1, num, lsb, num + lsb );
      }
      else if( powerof2( num - lsb ) )
      {
        divideby2( DIVIDE_BY_2_PLUS_1, num, lsb, num - lsb );
      }
      else
      {
        fprintf( stderr, "%d is not one of (2^n-2^m) or (2^n+2^m)\n", num );
      }
    }
  }
  return( 0 );
}