/*

   Generate Verilog for a combinatoric multiplier

   This program generates the Verilog for a combinatoric multiplier
   that is built out of cascaded full adders.  The program is given a
   command line argument for the width of the multiplier operands.  It
   generates the full adder module, the multiplier and the associated
   test bench, which tests the multiplier through the complete range.
   This means that for values larger than 8 the verilog generated
   takes a long time to simulate on Verilog XL.

   The multipler in created by this program is based on the cascade
   multiplier described in "Digital Computer Arithmetic" by Joseph
   J.F. Cavanagh, McGraw-Hill, 1984

    
   To compile on Solaris

      CC genmult.C -o genmult

   To run

      genmult <width>

   For example

      genmult 4

   Author:
     Ian Kaplan

   Copyright and use:

     You are granted the use of this software without limitation as
     long as you include

       Copyright Ian Kaplan, iank@bearcave.com

 */
#include <ctype.h>
#include <string.h>
#include <stdio.h>

enum { 
#ifndef FALSE
FALSE = 0,
#endif
#ifndef TRUE
       TRUE = 1,
#endif
       bogus_filler };

int get_size( char *num_str )
{
  int strok, len, i;
  int size;

  size = 0;

  len = strlen( num_str );
  strok = TRUE;
  // check to make sure that all the characters in
  // the string are digits.
  for (i = 0; i < len; i++) {
    if (! isdigit( num_str[i] )) {
      strok = FALSE;
      break;
    }
  }
  // if the string is OK, convert it to an integer
  if (strok) {
    sscanf( num_str, "%d", &size );
  }

  return size;
} // get_size


void
gen_adder(FILE *fp)
{
  fprintf(fp, "\n");
  fprintf(fp, "module full_addr( a, b, c_in, c_out, sum );\n");
  fprintf(fp, "input a, b, c_in;\n");
  fprintf(fp, "output sum, c_out;\n");
  fprintf(fp, "\n");
  fprintf(fp, "wire a1, a2, a3, a4;\n");
  fprintf(fp, "wire c1, c2, c3, c4;\n");
  fprintf(fp, "\n");
  fprintf(fp, "  assign a1 = (~a) & (~b) &   c_in;\n");
  fprintf(fp, "  assign a2 = (~a) &   b  & (~c_in);\n");
  fprintf(fp, "  assign a3 =   a  & (~b) & (~c_in);\n");
  fprintf(fp, "  assign a4 =   a  &   b  &   c_in;\n");
  fprintf(fp, "  assign sum = a1 | a2 | a3 | a4;\n");
  fprintf(fp, "\n");
  fprintf(fp, "  assign c1 = (~a) &   b  &   c_in;\n");
  fprintf(fp, "  assign c2 =   a  & (~b) &   c_in;\n");
  fprintf(fp, "  assign c3 =   a  &   b  & (~c_in);\n");
  fprintf(fp, "  assign c4 =   a  &   b  &   c_in;\n");
  fprintf(fp, "  assign c_out = c1 | c2 | c3 | c4;\n");
  fprintf(fp, "\n");
  fprintf(fp, "endmodule\n");
  fprintf(fp, "\n");
}  // get_adder



void
gen_header( unsigned int mult_size, FILE *fp = stdout )
{
  fprintf(fp, "module mult( A, B, rslt );\n");
  fprintf(fp, "input  [%2d:0] A, B;\n", mult_size-1 );
  fprintf(fp, "output [%3d:0] rslt;\n\n", (mult_size * 2)-1 );
} // gen_header


void gen_end( FILE *fp )
{
  fprintf(fp, "endmodule\n");
} // gen_end


void
gen_mult(  unsigned int mult_size, FILE *fp = stdout )
{
  int i, j, addr_cnt, rslt_cnt;

  fprintf(fp, "  assign r00 = a00 & b00;\n");

  addr_cnt = 0;

  for (i = 0; i < mult_size - 1; i++) {
    fprintf(fp, "  full_addr fa%03d (", addr_cnt );
    fprintf(fp, "a%02d & b00, a%02d & b01, 1'b0, c%02d, s%02d",
	         i + 1,       i,                 addr_cnt, addr_cnt );
    fprintf(fp, ");\n");
    addr_cnt++;    
  }

  fprintf( fp, "  assign r01 = s00;\n\n");

  rslt_cnt = 2;
  for ( j = 2; j < mult_size; j++ ) {
    for (i = 0; i < mult_size - 1; i++) {
      if (i < mult_size - 2) {
	fprintf(fp, "  full_addr fa%03d (", addr_cnt );
       // module full_adder( a, b, c_in, sum, c_out );
	fprintf(fp, "s%02d , a%02d & b%02d, c%02d, c%02d, s%02d",
	            addr_cnt - (mult_size-2), i, j, addr_cnt - (mult_size-1), 
		addr_cnt, addr_cnt );
	fprintf(fp, ");\n");
	if (i == 0) {
	  fprintf( fp, "  assign r%02d = s%02d;\n", rslt_cnt, addr_cnt );	  
	}
      }
      else {
	fprintf(fp, "  full_addr fa%03d (", addr_cnt );
	fprintf(fp, "a%02d & b%02d, a%02d & b%02d, c%02d, c%02d, s%02d",
		       i+1,    j - 1,   i,     j,    addr_cnt - (i+1), addr_cnt, addr_cnt );
	fprintf(fp, ");\n");
      }
      addr_cnt++;
    }
    rslt_cnt++;
    fprintf(fp, "\n");
  }

  for (i = 0; i < mult_size - 2; i++) {
    if (i == 0) {
      fprintf(fp, "  full_addr fa%03d (", addr_cnt );
      // module full_adder( a, b, c_in, sum, c_out );
      fprintf(fp, "s%02d , 1'b0, c%02d, c%02d, s%02d",
	      addr_cnt - (mult_size-2), addr_cnt - (mult_size-1), 
	      addr_cnt, addr_cnt );
      fprintf(fp, ");\n");
    }
    else {
      fprintf(fp, "  full_addr fa%03d (", addr_cnt );
      // module full_adder( a, b, c_in, sum, c_out );
      fprintf(fp, "s%02d , c%02d, c%02d, c%02d, s%02d",
	      addr_cnt - (mult_size-2), addr_cnt -1, addr_cnt - (mult_size-1), 
	      addr_cnt, addr_cnt );
      fprintf(fp, ");\n");
    }
    fprintf( fp, "  assign r%02d = s%02d;\n", rslt_cnt, addr_cnt );	  
    addr_cnt++;
    rslt_cnt++;
  }

  fprintf(fp, "  full_addr fa%03d (", addr_cnt );
  fprintf(fp, "a%02d & b%02d, c%02d, c%02d, c%02d, s%02d",
              mult_size-1, mult_size-1, addr_cnt-1, addr_cnt - (mult_size-1),
	      addr_cnt, addr_cnt );
  fprintf(fp, ");\n");

  fprintf(fp, "\n");

  fprintf( fp, "  assign r%02d = s%02d;\n", 
	   mult_size + (mult_size -2), addr_cnt );
  fprintf( fp, "  assign r%02d = c%02d;\n", 
	   mult_size + (mult_size - 1), addr_cnt );
} // gen_mult


void
gen_vars(int mult_size, char *name, FILE *fp )
{
  int i, semi;

  for (i = 0; i < mult_size; i++) {
    semi = FALSE;
    if ((i % 8) == 0) {
      if (i > 0) {
	fprintf(fp, ";\n");
	semi = TRUE;
      }
      fprintf( fp, "wire ");
    }
    else if (i < mult_size )
      fprintf(fp, ", ");

    fprintf( fp, "%s%02d", name, i );
  }
  if (! semi)
    fprintf(fp, ";\n");
}


void
gen_assign( unsigned int mult_size, char *dest, char *src, FILE *fp )
{
  int i;

  for (i = 0; i < mult_size; i++) {
    fprintf(fp, "  assign %s%02d = %s[%2d];\n", dest, i, src, i );
  }
} // gen_assign


void
gen_assign2( unsigned int mult_size, char *dest, char *src, FILE *fp )
{
  int i;

  for (i = 0; i < mult_size; i++) {
    fprintf(fp, "  assign %s[%2d] = %s%02d;\n", dest, i, src, i );
  }
} // gen_assign


void
gen_assigns( unsigned int mult_size, FILE *fp )
{
  gen_vars(mult_size, "a", fp);
  fprintf(fp, "\n");
  gen_vars(mult_size, "b", fp);
  fprintf(fp, "\n");
  gen_vars(mult_size * 2, "r", fp );
  fprintf(fp, "\n");
  gen_vars(mult_size * (mult_size-1), "c", fp);
  fprintf(fp, "\n");
  gen_assign(mult_size, "a", "A", fp );
  fprintf(fp, "\n");
  gen_assign(mult_size, "b", "B", fp );
  fprintf(fp, "\n");
  gen_assign2(mult_size * 2, "rslt", "r", fp );
  fprintf(fp, "\n");
} // gen_assigns


void
gen_mult_module( unsigned int mult_size, FILE *fp )
{
  gen_header( mult_size, fp );
  gen_assigns( mult_size, fp );
  gen_mult( mult_size, fp );
  gen_end( fp );
} // gen_mult_module


void
gen_testbench( unsigned int mult_size, FILE *fp )
{
   fprintf(fp, "\n");
   fprintf(fp, "module testbench;\n");
   fprintf(fp, "reg [%2d:0] A, B;\n", mult_size-1);
   fprintf(fp, "wire [%2d:0] rslt;\n", (mult_size * 2)-1);
   fprintf(fp, "\n");
   fprintf(fp, "  mult mult_inst (A, B, rslt);\n");
   fprintf(fp, "\n");
   fprintf(fp, "  initial\n");
   fprintf(fp, "  begin : init\n");
   fprintf(fp, "    parameter FALSE = 0;\n");
   fprintf(fp, "    parameter TRUE = 1;\n");
   fprintf(fp, "    reg [%2d:0] i, j;\n", mult_size);
   fprintf(fp, "    reg passed;\n");
   fprintf(fp, "\n");
   fprintf(fp, "    passed = TRUE;\n");
   fprintf(fp, "    for (j = 1; j < %2d; j = j + 1)\n", 1 << mult_size);
   fprintf(fp, "    begin\n");
   fprintf(fp, "      for (i = 1; i < %2d; i = i + 1)\n", 1 << mult_size );
   fprintf(fp, "      begin\n");
   fprintf(fp, "        A = i;\n");
   fprintf(fp, "        B = j;\n");
   fprintf(fp, "        #1;\n");
   fprintf(fp, "        if (rslt != i * j)\n");
   fprintf(fp, "        begin\n");
   fprintf(fp, "          passed = FALSE;\n");
   fprintf(fp, "          $display(\"test failed for %%d x %%d\", i, j );\n");
   fprintf(fp, "        end // if\n");
   fprintf(fp, "      end // for i\n");
   fprintf(fp, "    end // for j\n");
   fprintf(fp, "\n");
   fprintf(fp, "    if (passed)\n");
   fprintf(fp, "      $display(\"test passed\");\n");
   fprintf(fp, "    else\n");
   fprintf(fp, "      $display(\"test failed\");\n");
   fprintf(fp, "    $finish;\n");
   fprintf(fp, "  end\n");
   fprintf(fp, "\n");
   fprintf(fp, "endmodule\n");
   fprintf(fp, "\n");
} // gen_testbench

void
gen_verilog(  unsigned int mult_size, FILE *fp = stdout )
{
    gen_adder( fp );
    gen_mult_module( mult_size, fp );
    gen_testbench( mult_size, fp );
}  // gen_verilog


int
main(int argc, char *argv[] )
{
  int status;
  char *progname;

  progname = argv[ 0 ];

  status = 0;
  if (argc != 2) {
    printf("usage: %s <multiplier size>\n", progname );
    status = 1;
  }
  else {
    unsigned mult_size;

    mult_size = get_size( argv[ 1 ] );
    if (mult_size > 0) {
      gen_verilog( mult_size );
    }
    else {
      printf("usage: size should be greater than zero\n", progname );      
      status = 1;
    }
  }

  return status;
}