#include <stdio.h>
#include "util.h"
#include "vpack.h"
#include "globals.h"
#include "cluster.h"
#include "output_clustering.h"
#include "path_length.h"

#define PINS 4
#define ABSORB_GAIN 3.0
/*------------------------------------------------------------
*  Copyright 2002 By Kara K.W. Poon and Steve Wilton
*
* Permission to use, copy, and modify this software and its documentation is
* hereby granted only under the following terms and conditions.  Both the
* above copyright notice and this permission notice must appear in all copies
* of the software, derivative works or modified versions, and any portions
* thereof, and both notices must appear in supporting documentation.
* Permission is granted ONLY for non-commercial use.  For
* commercial use, please contact the authors.
*
* This software may be distributed (but not offered for sale or transferred
									* for compensation) to third parties, provided such third parties agree to
* abide by the terms and conditions of this notice.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS, AS
* WELL AS THE UNIVERSITY OF BRITISH COLUMBIA AND THE
* UNIVERSITY OF TORONTO DISCLAIM ALL WARRANTIES WITH
* REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS.   IN NO EVENT SHALL THE
* AUTHORS OR THE UNIVERSITY OF BRITISH COLUMBIA OR THE
* UNIVERSITY OF TORONTO BE LIABLE FOR ANY SPECIAL, DIRECT,
* INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
* PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
* OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
* WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*------------------------------------------------------------*/

/*
 T-Vpack was written by Vaughn Betz at the University of Toronto.
 
 May 2001   Modified by Dr. Steve Wilton at the University 
 of British Columbia to propagate signal 
 activities
 July 2001  Further modified by Kara Poon at the University 
 of British Columbia to propagate both
 static probability and transition density
 
 */

enum e_gain_update {GAIN, NO_GAIN};
enum e_feasibility {FEASIBLE, INFEASIBLE};
enum e_gain_type {HILL_CLIMBING, NOT_HILL_CLIMBING};
enum e_removal_policy {REMOVE_CLUSTERED, LEAVE_CLUSTERED};
enum e_net_relation_to_clustered_block {INPUT, OUTPUT};


/* Linked list structure.  Stores one integer (iblk). */
struct s_ilink {int iblk; struct s_ilink *next;};

/* 1/MARKED_FRAC is the fraction of nets or blocks that must be *
* marked in order for the brute force (go through the whole    *
									   * data structure linearly) gain update etc. code to be used.   *
* This is done for speed only; make MARKED_FRAC whatever       *
* number speeds the code up most.                              */
#define MARKED_FRAC 2   

/* [0..num_blocks-1].  Which cluster (numbered from 0 to num_cluster - 1) *
* is this block in?  If not assigned to a cluster yet, it is NO_CLUSTER. *
* this value is also used in path_length.c*/
int *cluster_of_block;

/* [0..num_nets-1].  How many pins of each net are contained in the *
* currently open cluster?                                          */
static int *num_pins_of_net_in_cluster;

/* [0..num_nets-1].  Is the driver for this net in the open cluster? */
static boolean *net_output_in_cluster;

/* [0..num_blocks-1]. How suitable is this block for absorbtion into the*
* current cluster. Calculated using the cost function                  *
* gain[i]=alpha*lengthgain[i] + (1-alpha)*sharinggain[i]/(lut_size+x)  *
* where alpha is the tradeoff variable that determines wheter timing or*
* area is more important, and x is 1 if gloabal clocks, 2 otherwise */
static float *gain;

/* [0..num_blocks-1]. What is the criticality score of this block? This*
* is determined by the most critical net between this block and any   *
* block in the current cluster */
static float *lengthgain;

/* [0..num_blocks-1]. How many connections will be absorbed if this block*
* is placed in the cluster under consideration */
static int *connectiongain;

/* [0..num_blocks-1]. How many nets on this block are already in the    *
* cluster under consideration */
static int *sharinggain;

/* [0..num_blocks-1]. Sum of transition densities of all the shared nets*
* between this block and the blocks already in the cluster under       *
* consideration */
static float *powergain;

/* [0..num_blocks-1]. This is the gain used for hill-climbing. It stores*
* the reduction in the number of pins that adding this block to the the*
* current cluster will have. This reflects the fact that sometimes the *
* addition of a block to a cluster may reduce the number of inputs     *
* required if it shares inputs with all other BLEs and it's output is  *
* used by all other BLEs in the cluster.                               */
static int *hillgain;

/* [0..num_marked_nets] and [0..num_marked_blocks] respectively.  List  *
* the indices of the nets and blocks that have had their num_pins_of_  *
* net_in_cluster and gain entries altered.                             */
static int *marked_nets, *marked_blocks;
static int num_marked_nets, num_marked_blocks;

/* [0..num_blocks-1]. */

/* To speed up some linear searches and such, I store the index of the *
* first clusterable (LUT, LATCH, etc.) block.                         */
static int first_clusterable_block = -1;

/* Keeps a linked list of the unclustered blocks to speed up looking for *
* unclustered blocks with a certain number of *external* inputs.        *
* [0..lut_size].  Unclustered_list_head[i] points to the head of the    *
* list of LUTs with i inputs to be hooked up via external interconnect. */
static struct s_ilink *unclustered_list_head;
static struct s_ilink *memory_pool; /*Declared here so I can free easily.*/


/* What is the increase in a blocks gain for each net that it shares    *
* with blocks that are already in the cluster. Set to be               *
* (1-alpha)/(lut_size+x), where x is 1 if global clocks, or 2 otherwise*/   
static float gain_for_each_net_shared;
static float power_gain_for_each_net_shared;

/* Does the block that drives the output of this net also appear as a   *
* receiver (input) pin of the net?  [0..num_nets-1].  This is used     *
* in the gain routines to avoid double counting the connections from   *
* the current cluster to other blocks (hence yielding better           *
									   * clusterings).  The only time a block should connect to the same net  *
* twice is when one connection is an output and the other is an input, *
* so this should take care of all multiple connections.                */
static boolean *net_output_feeds_driving_block_input;

static float avg_dens;

static int *is_start_chain;
static int *is_on_chain;
static int num_start_carry_chain;
static int num_on_carry_chain;
static int current_blk;

static void init_is_start_chain()
{
	int i;
	int num;
	
	is_start_chain = (int *)my_malloc(sizeof(int)*num_blocks);
	is_on_chain = (int *)my_malloc(sizeof(int)*num_blocks);

	//init the chain
	for(i=0;i<num_blocks;i++) {
		is_start_chain[i] = 0;
		is_on_chain[i] = 0;
	}
	
	for(i=0;i<num_blocks;i++) {
		if ((block[i].type == LUT) ||
			(block[i].type == LUT_AND_LATCH)) 
		{
			
			if (block[i].nets[B_CIN] == OPEN  && block[i].nets[B_COUT] != OPEN)
			{
				//start of carry chain
				is_start_chain[i] = 1;
				is_on_chain[i] = 0;
			}
			else if (block[i].nets[B_CIN] == OPEN  && block[i].nets[B_COUT] == OPEN)
			{
				//not a carry chain
				is_start_chain[i] = 0;
				is_on_chain[i] = 0;
			}
			else if (block[i].nets[B_CIN] != OPEN  && block[i].nets[B_COUT] != OPEN)
			{
				//Carry chain body
				is_start_chain[i] = 0;
				is_on_chain[i] = 1;


			}
			else if (block[i].nets[B_CIN] != OPEN  && block[i].nets[B_COUT] == OPEN)
			{
				//just end of carry chain
				is_start_chain[i] = 0;
				is_on_chain[i] = 1;
			}
	
		}
	}

	//check for the CIN of the carry body belong to the LUT / FF or not.
	//if yes, this carry body become the carry head
	
	for(i=0;i<num_blocks;i++) 
	{
		if ((block[i].type == LUT) ||
			(block[i].type == LUT_AND_LATCH)) 
		{
			if (is_start_chain[i] == 0&&
				is_on_chain[i] == 1)
			{
//				printf("check carry body  block %d(%s) \n", i, block[i].name);
//				printf("CIN %d , connect block %d (%s), connect block B_Q %d, use_ff %d\n", block[i].nets[B_CIN], net[block[i].nets[B_CIN]].pins[0], block[net[block[i].nets[B_CIN]].pins[0]].name, block[net[block[i].nets[B_CIN]].pins[0]].nets[B_Q], block[net[block[i].nets[B_CIN]].pins[0]].use_ff);
				if (block[net[block[i].nets[B_CIN]].pins[0]].nets[B_Q] ==  block[i].nets[B_CIN])
				{
					//printf("change block %d(%s) to carry head \n", i, block[i].name);
					is_start_chain[i] = 1;
					is_on_chain[i] = 0;

				}
				else if (block[net[block[i].nets[B_CIN]].pins[0]].nets[B_Y] ==  block[i].nets[B_CIN])
				{
					//printf("change block %d(%s) to carry head \n", i, block[i].name);
					is_start_chain[i] = 1;
					is_on_chain[i] = 0;

				}
				else if (block[net[block[i].nets[B_CIN]].pins[0]].nets[B_FX] ==  block[i].nets[B_CIN])
				{
					is_start_chain[i] = 1;
					is_on_chain[i] = 0;
				}

			}

		}
	}

	/*
	for(i=0;i<num_blocks;i++) {
		if ((block[i].type == LUT) ||
			(block[i].type == LUT_AND_LATCH)) {
			if (block[i].carryout_to != -1) {
				is_start_chain[block[i].carryout_to] = 0;
				is_on_chain[block[i].carryout_to] = 1;
			}
		}
	}
	*/
	num_start_carry_chain = 0;
	num_on_carry_chain = 0;
	for(i=0;i<num_blocks;i++) {
		if ((block[i].type == LUT) ||
			(block[i].type == LUT_AND_LATCH)) {
			if (is_start_chain[i]) num_start_carry_chain++;
			if (is_on_chain[i]) num_on_carry_chain++;
		}
	}
	if (num_start_carry_chain == 0) 
	{
		printf("No carry chains detected.\n");
	} else {
		printf("%d carry chains detected: ",num_start_carry_chain);
		
		for(i=0;i<num_blocks;i++) {
			if ((block[i].type == LUT) ||
				(block[i].type == LUT_AND_LATCH)) {
				if (is_start_chain[i]) printf("%s(%d) \n",block[i].name, i);
			}
		}
		
		printf("\nNumber of nodes on carry chains: %d\n",num_on_carry_chain);
	}
}



static int get_carry_chain_seed_block(int lut_size, int inputs_avail, int clocks_avail)
{
    struct s_ilink *ptr, *prev_ptr;
    int retval,n,nstart,iblk;
	
    retval = -1;
    nstart = min(lut_size, inputs_avail);
	nstart = lut_size + B_LUT_IN - B_CLK-1;

    for(n=nstart; n>=0; n--) 
	{		
		prev_ptr = &unclustered_list_head[n];
		ptr = unclustered_list_head[n].next;
		
		while (ptr != NULL) 
		{
            iblk = ptr->iblk;
/*
			if (iblk == 469)
			{
				output_block(469, 4);
				if (cluster_of_block[iblk] == NO_CLUSTER)
				{
					printf("block 469 NO_CLUSTER \n");
				}
				else
				{
					printf("block 469 CLUSTER \n");
				}
				
			}
*/			
            if (cluster_of_block[iblk] == NO_CLUSTER) 
			{
                if (is_start_chain[iblk]) 
				{
					retval = iblk;
				}	   
                prev_ptr = ptr;
            } else 
			{
				prev_ptr->next = ptr->next;
            }
            ptr = ptr->next;
        }
    }
    if (retval == -1) {
        printf("Error: couldn't find the start of a carry chain for the seed node, but it\n");
        printf("should have been there\n");
        exit(0);
    }
    num_start_carry_chain --;
    num_on_carry_chain --;
    is_start_chain[retval] = 0;
    is_on_chain[retval] = 0;
    return(retval);
}



static void calc_avg_dens()
{
    int iblk, inet, net_pin_count = 0;
    float total_density = 0.0;
	
    for (iblk=0; iblk<num_blocks; iblk++)
    {
        inet = block[iblk].nets[0];	/* get output net */
        net_pin_count += net[inet].num_pins;
        total_density += net[inet].density*((float) net[inet].num_pins);
    }
	
    avg_dens = total_density/((float) net_pin_count);
}


int num_input_pins (int iblk, int lutsize) {
    /* Returns the number of used input pins on this block. */
    int conn_inps;
	int i;
	
	conn_inps = 0;
    switch (block[iblk].type) {
		
		case LUT:
			for (i= B_CIN; i < B_LUT_IN + lutsize; i++)
			{
				if(block[iblk].nets[i] != OPEN)
				{
					conn_inps ++	;
				}
			}
			//conn_inps = block[iblk].num_nets - 1;   /* -1 for output. */
			break;
			
		case LUT_AND_LATCH:
			for (i= B_CIN; i < B_LUT_IN + lutsize; i++)
			{
				if(block[iblk].nets[i] != OPEN)
				{
					conn_inps ++	;
				}
			}
			//conn_inps = block[iblk].num_nets - 2;  /* -2 for output + clock */
			break;
			
		case LATCH:
			for (i= B_CIN; i < B_LUT_IN + lutsize; i++)
			{
				if(block[iblk].nets[i] != OPEN)
				{
					conn_inps ++	;
				}
			}
			//conn_inps = block[iblk].num_nets - 2;  /* -2 for output + clock */
			break;
			
		default:
			/* This routine should only be used for logic blocks. */
			printf("Error in num_input_pins:  Unexpected block type %d"
				   "\n for block %d.  Aborting.\n", block[iblk].type, iblk);
			exit(1);
			break;
    }
	
//	printf("conn_inps %d \n", conn_inps);	
    return (conn_inps);
}


int get_cluster_of_block(int blkidx) {
	
    return(cluster_of_block[blkidx]);
}


static int num_ext_inputs (int iblk, int lut_size) {
    /* Returns the number of input pins on this block that must be hooked *
	* up through external interconnect.  That is, the number of input    *
	* pins used - the number which connect (internally) to the output.   */
	
    int ext_inps, output_net, ipin;
	int opin;
	
    ext_inps = num_input_pins(iblk, lut_size);
//	printf("num input pin %d , lut_size %d\n", ext_inps, lut_size);	
    
	
    /* NB:  I could speed things up a bit by computing the number of inputs *
		* and number of external inputs for each logic block at the start of   *
		* clustering and storing them in arrays.  Look into if speed is a      *
		* problem.                                                             */
	for (opin = B_COUT; opin < B_CLK; opin ++)
	{
		output_net = block[iblk].nets[opin];
		if (output_net != OPEN)
		{
			for (ipin=B_CIN;ipin< B_LUT_IN + lut_size;ipin++) 
			{
				if (block[iblk].nets[ipin] == output_net)
					ext_inps--;
			}

		}
		
	}
	
    return (ext_inps);
}


static void check_clocks (boolean *is_clock, int lut_size) {
    /* Checks that nets used as clock inputs to latches are never also used *
	* as LUT inputs.  It's electrically questionable, and more importantly *
	* would break the clustering code.                                     */
	
    int inet, iblk, ipin;
	
    for (iblk=0;iblk<num_blocks;iblk++) 
	{
        if (block[iblk].type == LUT || block[iblk].type == LATCH ||
			block[iblk].type == LUT_AND_LATCH)
		{
            for (ipin=B_CIN;ipin<lut_size+B_LUT_IN ;ipin++) 
			{
                inet = block[iblk].nets[ipin];
                if (inet != OPEN) {
                    if (is_clock[inet]) {
                        printf("Error in check_clocks.  Net %d (%s) is a clock, but "
                               "also\n"
                               "\tconnects to a LUT input on block %d (%s).\n", inet,
                               net[inet].name, iblk, block[iblk].name);
                        printf("This would break the current clustering "
                               "implementation and is electrically\n"
                               "\tquestionable, so clustering has been aborted.\n");
                        exit (1);
                    }
                }
			}
		}
    }
}

static void check_net_consistent(int lut_size)
{
	int iblk, ipin, inet;
	int net_pin;
	int find_connection;
	for (iblk = 0; iblk < num_blocks ; iblk ++)
	{
		if (block[iblk].type == LUT ||
			block[iblk].type == LATCH ||
			block[iblk].type == LUT_AND_LATCH)
		{
			for (ipin =0; ipin<	lut_size + B_LUT_IN; ipin ++)
			{
				inet = block[iblk].nets[ipin];
				if (inet != OPEN)
				{
					find_connection = 0;
					for (net_pin = 0; net_pin < net[inet].num_pins; net_pin ++)
					{
						if (net[inet].pins[net_pin] == iblk)
						{
							find_connection = 1;
						}	
					}
				
					if (find_connection == 0)
					{
						printf("Error in check_net_consistent block %d (%s) can't find in net %d (%s) \n", iblk, block[iblk].name, inet, net[inet].name);
						printf("Use FF %d \n", block[iblk].use_ff);
						exit(1);
					}		
				}
			}
		}		
	}
}



static void check_for_duplicate_inputs (int lut_size) {
    /* Checks that each input pin of a LUT connects to a distinct net.  *
	* It doesn't make sense from a tech-mapping point of view to feed  *
	* the same input into a LUT more than once, and more importantly,  *
	* some of the clustering code assumes that all LUT inputs are      *
	* unique.                                                          */
	
    int iblk, ipin, inet;
    int *num_conns_to_net;
	
    num_conns_to_net = (int*) my_malloc (num_nets * sizeof(net));
	
    for (inet=0;inet<num_nets;inet++)
        num_conns_to_net[inet] = 0;
	
    for (iblk=0;iblk<num_blocks;iblk++) {
        if (block[iblk].type == LUT || block[iblk].type == LATCH ||
			block[iblk].type == LUT_AND_LATCH) 
			 {
            for (ipin=B_CLK;ipin<lut_size + B_LUT_IN;ipin++) {
                inet = block[iblk].nets[ipin];
                if (inet != OPEN) {
                    num_conns_to_net[inet]++;
                    if (num_conns_to_net[inet] != 1) {
						printf("num_pins = %d \n", net[inet].num_pins);

                        printf("\nError in check_for_duplicate_inputs.\n"
                               "Block #%d (%s) connects multiple input pins to"
                               " net #%d (%s).\n", iblk, block[iblk].name, inet,
                               net[inet].name);
                        printf("Multiple connections to a LUT's inputs doesn't "
                               "make sense from a technology \n"
                               "mapping standpoint, and the clusterer assumes "
                               "LUT inputs are unique.\n"
                               "Aborting.\n");
                        exit(1);
                    }
                }
            }
			
            /* Reset count for next block. */
			for (ipin=B_CLK;ipin<lut_size + B_LUT_IN;ipin++) {
            //for (ipin=1;ipin<=lut_size;ipin++) {
                inet = block[iblk].nets[ipin];
                if (inet != OPEN)
                    num_conns_to_net[inet] = 0;
            }
        }
    }
	
    free (num_conns_to_net);
}


static void alloc_and_init_clustering (int lut_size, int cluster_size,
                                       boolean global_clocks, float alpha, float beta) {
    /* Allocates the main data structures used for clustering and properly *
	* initializes them.                                                   */
	
    int i, ext_inps, ipin, driving_blk, inet;
    struct s_ilink *next_ptr;
	
    cluster_of_block = (int *) my_malloc (num_blocks * sizeof(int));
    gain = (float *) my_malloc (num_blocks * sizeof (float));
    lengthgain=(float*) my_malloc (num_blocks * sizeof (float));
    sharinggain=(int*) my_malloc (num_blocks * sizeof (int));
    hillgain =(int*) my_malloc (num_blocks * sizeof (int));
    connectiongain = (int*) my_malloc (num_blocks * sizeof (int));
    powergain = (float*) my_malloc (num_blocks * sizeof (float));
	
//    calc_avg_dens();
    printf("Average Density = %f\n", avg_dens);
	

    if (global_clocks)
    {
        //gain_for_each_net_shared=(1.0-alpha)*(1.0-beta)/(float)(lut_size+1);
        //power_gain_for_each_net_shared=(1.0-alpha)*beta/(float)(lut_size+1);
		gain_for_each_net_shared=(1.0-alpha)*(1.0-beta)/(float)(lut_size+ B_LUT_IN);
		power_gain_for_each_net_shared=(1.0-alpha)*beta/(float)(lut_size+ B_LUT_IN);
    }
    else
    {
        //gain_for_each_net_shared=(1.0-alpha)*(1.0-beta)/(float)(lut_size+2);
        //power_gain_for_each_net_shared=(1.0-alpha)*beta/(float)(lut_size+2);
		gain_for_each_net_shared=(1.0-alpha)*(1.0-beta)/(float)(lut_size+B_LUT_IN + 1);
		power_gain_for_each_net_shared=(1.0-alpha)*beta/(float)(lut_size+B_LUT_IN +1);
    }


	
    for (i=0;i<num_blocks;i++) {
		
        gain[i] = 0.0;
        lengthgain[i]= 0.0;
        connectiongain[i] = 0;
        sharinggain[i]=NOT_VALID;
        hillgain[i]=NOT_VALID;
        powergain[i] = 0.0;
		
        if (block[i].type == LUT || block[i].type == LUT_AND_LATCH ||
			block[i].type == LATCH ) {
            cluster_of_block[i] = NO_CLUSTER;
            if (first_clusterable_block == -1)
                first_clusterable_block = i;
        }
        else
            cluster_of_block[i] = NEVER_CLUSTER;
			//printf("Block %d, cluster_of_block %d \n", i, cluster_of_block[i]);
    }
	
    num_pins_of_net_in_cluster = (int *) my_malloc (num_nets * sizeof(int));
    net_output_in_cluster = (boolean *) my_malloc (num_nets * sizeof(boolean));
	
    for (i=0;i<num_nets;i++) {
        num_pins_of_net_in_cluster[i] = 0;
        net_output_in_cluster[i] = FALSE;
    }
	
    //marked_nets = (int *) my_malloc ((lut_size + 2) * cluster_size * sizeof(int));
	marked_nets = (int *) my_malloc ((lut_size +  B_LUT_IN ) * cluster_size * sizeof(int));
    marked_blocks = (int *) my_malloc (num_blocks * sizeof(int));
	
    num_marked_nets = 0;
    num_marked_blocks = 0;

	
    //unclustered_list_head = (struct s_ilink *) my_malloc ((lut_size+1) *sizeof(struct s_ilink));
	unclustered_list_head = (struct s_ilink *) my_malloc ((lut_size+B_LUT_IN - B_CLK ) *sizeof(struct s_ilink));
    //for (i=0;i<=lut_size;i++)
	for (i=0;i<lut_size + B_LUT_IN - B_CLK;i++)
        unclustered_list_head[i].next = NULL;



	
	printf("memory_pool size = %d \n", num_blocks - first_clusterable_block);
    memory_pool = (struct s_ilink *) my_malloc ((num_blocks -
												 first_clusterable_block) * sizeof (struct s_ilink));
    next_ptr = memory_pool;

//	for (i=0;i<num_nets;i++)
//	{
//		printf("net[%d].num_pins = %d, netname = %s\n", i, net[i].num_pins, net[i].name);
//	}

	printf("Max number of pins = %d \n", lut_size + B_LUT_IN -B_CLK);

//	printf("number of block %d, first_clusterable_block %d \n", num_blocks, first_clusterable_block);	
    for (i=first_clusterable_block;i<num_blocks;i++) {
        if (block[i].type == LUT || block[i].type == LUT_AND_LATCH ||
			block[i].type == LATCH) {
            ext_inps = num_ext_inputs(i, lut_size);
//			printf("block %d (%s) , ext_inps = %d, is_on_chain = %d, is_start_chain = %d , C_IN = %d , C_OUT = %d\n", i, block[i].name,ext_inps, is_on_chain[i], is_start_chain[i], block[i].nets[B_CIN], block[i].nets[B_COUT]);
            next_ptr->next = unclustered_list_head[ext_inps].next;
            unclustered_list_head[ext_inps].next = next_ptr;
            next_ptr->iblk = i;
            next_ptr++;
        }
    }
	

    net_output_feeds_driving_block_input = (boolean *) my_malloc (
																  num_nets * sizeof (boolean));
//	printf("finish net_output_feeds_driving_block_input \n");

    for (inet=0;inet<num_nets;inet++) {
        net_output_feeds_driving_block_input[inet] = FALSE;
        driving_blk = net[inet].pins[0];

//		printf("net[%d].num_pins = %d, netname = %s\n", inet, net[inet].num_pins, net[inet].name);
        for (ipin=1;ipin<net[inet].num_pins;ipin++) {
            if (net[inet].pins[ipin] == driving_blk) {
                net_output_feeds_driving_block_input[inet] = TRUE;
                break;
            }
        }
    }
	//printf("finishe alloc_and_init_clustering\n");
}


/*****************************************/
static void free_clustering (void) {
	
    /* Releases all the memory used by clustering data structures.   */

    free (cluster_of_block);
    free (gain);
    free (hillgain);
    free (lengthgain);
    free (sharinggain);	
    free (powergain);
    free (connectiongain);
    free (num_pins_of_net_in_cluster);
    free (net_output_in_cluster);
    free (marked_nets);
    free (marked_blocks);
    free (unclustered_list_head);
    free (memory_pool);
    free (net_output_feeds_driving_block_input);
	
    free (block);
    free (net);
	
}


static boolean clocks_feasible (int iblk, int idummy, int clocks_avail,
                                int lut_size, boolean *dummy) {
    /* Checks if block iblk could be adding to the open cluster without *
	* violating clocking constraints.  Returns TRUE if it's OK.  Some  *
	* parameters are unused since this function needs the same inter-  *
	* face as the other feasibility checkers.                          */
	
    int inet;
	
    /* Recall that LUT output can't internally connect to clocks. */
	
    //inet = block[iblk].nets[lut_size+1];
	inet = block[iblk].nets[B_CLK];
    if (inet != OPEN) {
        if (num_pins_of_net_in_cluster[inet] == 0) {
            clocks_avail--;
        }
        else if (num_pins_of_net_in_cluster[inet] == 1 &&
                 net_output_in_cluster[inet]) {
            clocks_avail--;
        }
    }
	
    if (clocks_avail >= 0)
        return (TRUE);
    else
        return (FALSE);
}


static int get_block_by_num_ext_inputs (int ext_inps, int lut_size, int
                                        clocks_avail, enum e_removal_policy remove_flag) {
	
    /* This routine returns a block which has not been clustered, has  *
	* no connection to the current cluster, satisfies the cluster     *
	* clock constraints, and has ext_inps external inputs.  If        *
	* there is no such block it returns NO_CLUSTER.  Remove_flag      *
	* controls whether or not blocks that have already been clustered *
	* are removed from the unclustered_list data structures.  NB:     *
	* to get a block regardless of clock constraints just set clocks_ *
	* avail > 0.                                                      */
	
    struct s_ilink *ptr, *prev_ptr;
    int iblk;
	
	//printf("get_block_by_num_ext_inputs\n");
    prev_ptr = &unclustered_list_head[ext_inps];
    ptr = unclustered_list_head[ext_inps].next;
	
    while (ptr != NULL) {
        iblk = ptr->iblk;
		//printf("iblk = %d \n", iblk);
        if (cluster_of_block[iblk] == NO_CLUSTER) {
            if (!is_on_chain[iblk]) 
				if (clocks_feasible (iblk, 0, clocks_avail, lut_size, NULL))
					return (iblk);
			
            prev_ptr = ptr;
			
        }
		
        else if (remove_flag == REMOVE_CLUSTERED) {
            prev_ptr->next = ptr->next;
        }
		
        ptr = ptr->next;
    }
	
    return (NO_CLUSTER);
}


static int get_min_power_seed_block(int lut_size, int inputs_avail, int clocks_avail)
{
    int i, n, nstart, iblk, inet, min_connectivity_blk, flag = 0;
    float degree, separation, connectivity, min_connectivity;
    struct s_ilink *ptr, *prev_ptr;
	
    min_connectivity = 100000000000.0;
	
    nstart = min(lut_size, inputs_avail);
    for(n=nstart; n>=0; n--)
    {
        prev_ptr = &unclustered_list_head[n];
        ptr = unclustered_list_head[n].next;
		
        while (ptr != NULL)
        {
            iblk = ptr->iblk;
            if (cluster_of_block[iblk] == NO_CLUSTER)
            {
            	if (clocks_feasible(iblk, 0, clocks_avail, lut_size, NULL))
            	{
                    flag = 1;
					
					degree = 0.0;
					separation = 0.0;		
                    for(i=0; i<=lut_size; i++)
                    {
                        inet = block[iblk].nets[i];
                        if (inet != OPEN)
						{
							if (net[inet].num_clusters > 0)
								degree += 1.5*net[inet].density;
							else
								degree += net[inet].density;
							separation += net[inet].num_pins;
						}
                    }
					connectivity = separation/(degree*degree);
					
                    if (connectivity < min_connectivity)
                    {
                        min_connectivity = connectivity;
                        min_connectivity_blk = iblk;
                    }
                }
                prev_ptr = ptr;
            }
            else
            {
                prev_ptr->next = ptr->next;
            }
            ptr = ptr->next;
        }
    }
	
    if (flag == 1) return min_connectivity_blk;
	
    return NO_CLUSTER;
}


static int get_max_dens_n_input_block(int n, int lut_size,
                                      int clocks_avail, enum e_removal_policy remove_flag)
{
    int i, iblk, inet, max_density_blk, flag = 0;
    float total_density, max_density;
    struct s_ilink *ptr, *prev_ptr;
	
    prev_ptr = &unclustered_list_head[n];
    ptr = unclustered_list_head[n].next;
    max_density = 0.0;
    while (ptr != NULL)
    {
        iblk = ptr->iblk;
        total_density = 0.0;
        if (cluster_of_block[iblk] == NO_CLUSTER)
        {
            if (clocks_feasible(iblk, 0, clocks_avail, lut_size, NULL))
            {
                flag = 1;
                for(i=0; i<=lut_size; i++)
                {
                    inet = block[iblk].nets[i];
                    if (inet != OPEN)
                        if (net[inet].num_pins < PINS && net[inet].num_clusters == 0)
                            total_density += ABSORB_GAIN*net[inet].density;
                        else
                            total_density += net[inet].density;
                }
				
                if (total_density >= max_density)
                {
                    max_density = total_density;
                    max_density_blk = iblk;
                }
            }
			
            prev_ptr = ptr;
        }
		
        else if (remove_flag == REMOVE_CLUSTERED)
        {
            prev_ptr->next = ptr->next;
        }
		
        ptr = ptr->next;
    }
	
    if (flag == 1)
        return max_density_blk;
	
    return NO_CLUSTER;
}


static int get_highest_density_unclustered_block(int lut_size, int inputs_avail,
												 int clocks_avail)
{
    int iblk, ext_inps, istart;
	
    istart = min(lut_size, inputs_avail);
	
    for(ext_inps=istart; ext_inps>=0; ext_inps--)
    {
        iblk = get_max_dens_n_input_block(ext_inps, lut_size, clocks_avail,
                                          REMOVE_CLUSTERED);
		
        if (iblk != NO_CLUSTER)
            return iblk;
    }
	
    return NO_CLUSTER;
}



static int get_free_block_with_most_ext_inputs (int lut_size, int inputs_avail,
												int clocks_avail) {
	
    /* This routine is used to find the first seed block for the clustering   *
	* and to find new blocks for clustering when there are no feasible       *
	* blocks with any attraction to the current cluster (i.e. it finds       *
	* blocks which are unconnected from the current cluster).  It returns    *
	* the block with the largest number of used inputs that satisfies the    *
	* clocking and number of inputs constraints.  If no suitable block is    *
	* found, the routine returns NO_CLUSTER.                                 */
	
    int iblk, ext_inps, istart;
	
    istart = min (lut_size, inputs_avail);
	istart = lut_size + B_LUT_IN - B_CLK-1;

	//printf("get_free_block_with_most_ext_input\n");
	//printf("istart = %d \n", istart);

	for (ext_inps=istart;ext_inps>=0;ext_inps--) {
        iblk = get_block_by_num_ext_inputs (ext_inps, lut_size, clocks_avail,
                                            REMOVE_CLUSTERED);
        if (iblk != NO_CLUSTER)
            return (iblk);
    }
	
    return (NO_CLUSTER);   /* No suitable block found. */
}


static void reset_cluster (int *inputs_used, int *luts_used,
                           int *clocks_used, int* next_empty_location_in_cluster,
                           int *block_in_cluster, int cluster_size) {
	
    /* Call this routine when starting to fill up a new cluster.  It resets *
	* the gain vector, etc.                                                */
	
    int i;
	
    /* If statement below is for speed.  If nets are reasonably low-fanout,  *
	* only a relatively small number of blocks will be marked, and updating *
	* only those block structures will be fastest.  If almost all blocks    *
	* have been touched it should be faster to just run through them all    *
	* in order (less addressing and better cache locality).                 */
	
    *inputs_used = 0;
    *luts_used = 0;
    *clocks_used = 0;
    *next_empty_location_in_cluster=0;
	
    for (i=0;i<num_marked_blocks;i++){
        gain[marked_blocks[i]] = 0.0;
        lengthgain[marked_blocks[i]]=0.0;
        sharinggain[marked_blocks[i]]=NOT_VALID;
        hillgain[marked_blocks[i]]=NOT_VALID;
        connectiongain[marked_blocks[i]]=0;
        powergain[marked_blocks[i]]=0.0;
    }
	
	
    num_marked_blocks = 0;
	
    for (i=0;i<num_marked_nets;i++) {
        num_pins_of_net_in_cluster[marked_nets[i]] = 0;
        net_output_in_cluster[marked_nets[i]] = FALSE;
    }
	
    for (i=0; i<cluster_size;i++)
        block_in_cluster[i]=NO_CLUSTER;
	
    num_marked_nets = 0;
}


static void update_connection_gain_values (int inet, int clustered_block,
										   int pin_on_clustered_block,
										   boolean *is_clock) {
    /*This function is called when the connectiongain values on the net*
	*inet require updating.   */
	
    enum e_net_relation_to_clustered_block net_relation_to_clustered_block;
    int iblk, ipin;
	
    //if (pin_on_clustered_block==0){
	if (pin_on_clustered_block>=B_COUT && pin_on_clustered_block<=B_DIG)
	{
        /*these designations are only valid for non-clock nets*/
        net_relation_to_clustered_block=OUTPUT;
    }
    else if (pin_on_clustered_block<B_COUT)
	{
		//error
		printf("handling invalid pin in clustering, pin_on_clustered_block = %d \n", pin_on_clustered_block);
		exit(1);
	}else if (pin_on_clustered_block >=B_CLK)
	{
        net_relation_to_clustered_block=INPUT;
    }
	
    if (net_relation_to_clustered_block==OUTPUT && !is_clock[inet]){
        for (ipin=1;ipin<net[inet].num_pins;ipin++) {
            iblk = net[inet].pins[ipin];
            if (cluster_of_block[iblk] == NO_CLUSTER) {
                connectiongain[iblk] ++;
            }
        }
    }
	
    if(net_relation_to_clustered_block==INPUT && !is_clock[inet]){
        /*Calculate the connectiongain for the block which is driving *
		*the net that is an input to a block in the cluster */
		
        iblk=net[inet].pins[0];
        if (cluster_of_block[iblk] == NO_CLUSTER) {
            connectiongain[iblk] ++;
        }
    }
}


static void update_length_gain_values (int inet, int clustered_block,
                                       int pin_on_clustered_block,
                                       boolean *is_clock) {
	
    /*This function is called when the length_gain values on the net*
	*inet requires updating.   */
	
    enum e_net_relation_to_clustered_block net_relation_to_clustered_block;
    float lengain;
    int newblk, netpin, ifirst;
    int iblk, ipin;
	
	
    /* Check if this net lists its driving block twice.  If so, avoid  *
		* double counting this block by skipping the first (driving) pin. */
    if (net_output_feeds_driving_block_input[inet] == FALSE)
        ifirst = 0;
    else
        ifirst = 1;
	
    if (pin_on_clustered_block==0){
        /*these designations are only valid for non-clock nets*/
        net_relation_to_clustered_block=OUTPUT;
    }
    else{
        net_relation_to_clustered_block=INPUT;
    }
	
    if (net_relation_to_clustered_block==OUTPUT && !is_clock[inet]){
        for (ipin=ifirst;ipin<net[inet].num_pins;ipin++) {
            iblk = net[inet].pins[ipin];
            if (cluster_of_block[iblk] == NO_CLUSTER) {
                lengain=get_net_pin_backward_criticality(inet, ipin);
                if (lengain>lengthgain[iblk])
                    lengthgain[iblk]=lengain;
            }
        }
    }
	
    if(net_relation_to_clustered_block==INPUT && !is_clock[inet]){
        /*Calculate the length gain for the block which is driving *
		*the net that is an input to a block in the cluster */
		
        newblk=net[inet].pins[0];
        if (cluster_of_block[newblk] == NO_CLUSTER) {
            netpin= get_net_pin_number(clustered_block, pin_on_clustered_block);
            lengain=get_net_pin_forward_criticality(inet, netpin);
            if (lengain>lengthgain[newblk])
                lengthgain[newblk]=lengain;
        }
    }
}


static void mark_and_update_partial_gain (int inet,
										  enum e_gain_update gain_flag,
										  int lut_size, int clustered_block, int pin_on_clustered_block,
										  boolean* is_clock, int luts_available,
										  boolean timing_driven, boolean connection_driven,
										  boolean power_driven) {
	
    /* Updates the marked data structures, and if gain_flag is GAIN,  *
	* the gain when a logic block is added to a cluster.  The        *
	* sharinggain is the number of inputs that a block shares with   *
	* blocks that are already in the cluster. Hillgain is the        *
	* reduction in number of pins-required by adding a block to the  *
	* cluster. The lengthgain is the criticality of the most critical*
	* net between this block and a block in the cluster.             */
	
    int iblk, ipin, ifirst;
	
    /* Mark net as being visited, if necessary. */
	
    if (num_pins_of_net_in_cluster[inet] == 0) {
        marked_nets[num_marked_nets] = inet;
        num_marked_nets++;
    }
	
    /* Update gains of affected blocks. */
	
    if (gain_flag == GAIN) {
		
        /* Check if this net lists its driving block twice.  If so, avoid  *
		* double counting this block by skipping the first (driving) pin. */
		
        if (net_output_feeds_driving_block_input[inet] == FALSE)
            ifirst = 0;
        else
            ifirst = 1;
		
        if (num_pins_of_net_in_cluster[inet] == 0) {
            net[inet].num_clusters++;
            for (ipin=ifirst;ipin<net[inet].num_pins;ipin++) {
                iblk = net[inet].pins[ipin];
                if (cluster_of_block[iblk] == NO_CLUSTER) {
					
                    if (sharinggain[iblk] == NOT_VALID) {
                        marked_blocks[num_marked_blocks] = iblk;
                        num_marked_blocks++;
                        if ((net[inet].num_pins < PINS) &&
							(net[inet].num_clusters == 1))
                        {
                            powergain[iblk] = net[inet].density*ABSORB_GAIN;
                        }
                        else
                        {
       	                    powergain[iblk] = net[inet].density;
                        }
                        sharinggain[iblk]=1;
                        hillgain[iblk] = 1 - num_ext_inputs (iblk, lut_size);
                    }
                    else {
                        if ((net[inet].num_pins < PINS) &&
							(net[inet].num_clusters == 1))
                        {
                            powergain[iblk] += net[inet].density*ABSORB_GAIN;
                        }
                        else
                        {
                            powergain[iblk] += net[inet].density;
                        }
                        sharinggain[iblk]++;
                        hillgain[iblk]++;
                    }
                }
            }
        }
		
        if (connection_driven) {
            update_connection_gain_values(inet, clustered_block, pin_on_clustered_block,
                                          is_clock);
        }
        else if (timing_driven) {
            update_length_gain_values(inet, clustered_block, pin_on_clustered_block,
                                      is_clock);
        }
    }
	
    num_pins_of_net_in_cluster[inet]++;
}


static void  recompute_length_gain_values(int *block_in_cluster,
										  int next_empty_location_in_cluster,
										  int lut_size,
										  boolean global_clocks,
										  boolean *is_clock) {
	
    /*This function recomputes all of the length_gain values for any *
	*nets that are affected by blocks that have been added to       *
	*current cluster.                                               */
	
    int ipin, inet, iblk;
    int i,idx;
	
    for (i=0;i<num_marked_blocks;i++){
        iblk=marked_blocks[i];
        lengthgain[iblk] = 0.0;
    }
	
    for (idx=0; idx < next_empty_location_in_cluster; idx++) {
        iblk=block_in_cluster[idx];
		
        inet = block[iblk].nets[0];  /*output pin first */
        if (inet != OPEN) {
            if (!is_clock[inet] || !global_clocks)
                update_length_gain_values(inet, iblk, 0, is_clock);
        }
		
        for (ipin=1;ipin<=lut_size;ipin++) {   /*  LUT input pins. */
            inet = block[iblk].nets[ipin];
            if (inet != OPEN)
                update_length_gain_values(inet, iblk, ipin, is_clock);
        }
    }
}


static void update_total_gain(float alpha, float beta, boolean timing_driven, boolean
                              connection_driven, boolean power_driven){
	
    /*Updates the total  gain array to reflect the desired tradeoff between*
	*input sharing (sharinggain) and path_length minimization (lengthgain)*/
	
    int i, iblk;
	
    if (connection_driven) {
        /*try to absorb as many connections as possible*/
        for (i=0;i<num_marked_blocks;i++){
            iblk=marked_blocks[i];
            gain[iblk] = alpha*(float)connectiongain[iblk] + (1-alpha)*(float)sharinggain[iblk];
        }
    }
    else if (timing_driven && !power_driven) {
        for (i=0;i<num_marked_blocks;i++){
            iblk=marked_blocks[i];
            gain[iblk] = alpha*lengthgain[iblk]+
				gain_for_each_net_shared*(float)sharinggain[iblk]; 
        }
    }
    else if (timing_driven && power_driven) {
        for (i=0;i<num_marked_blocks;i++){
            iblk=marked_blocks[i];
            gain[iblk] = alpha*lengthgain[iblk]+
				gain_for_each_net_shared*(float)sharinggain[iblk]+
				power_gain_for_each_net_shared*powergain[iblk]/avg_dens;
        }
    }
    else if (power_driven) {
        for (i=0;i<num_marked_blocks;i++){
            iblk=marked_blocks[i];
            gain[iblk] = (1-beta)*((float)sharinggain[iblk]) + beta*powergain[iblk]/avg_dens;
        }
    }
    else { /*non timing_driven, minimize number of inputs used*/
        for (i=0;i<num_marked_blocks;i++){
            iblk=marked_blocks[i];
            gain[iblk] = (float)sharinggain[iblk];
        }
    }
}


static void add_to_cluster (int new_blk, int cluster_size, int cluster_index,
                            int lut_size, boolean *is_clock, boolean global_clocks, int *inputs_used,
                            int *luts_used, int *clocks_used, float alpha, float beta, boolean timing_driven,
                            boolean connection_driven, boolean power_driven) {
	
    /* Marks new_blk as belonging to cluster cluster_index and updates  *
	* all the gain, etc. structures.  Cluster_index should always      *
	* be the index of the currently open cluster.                      */
	
    int ipin, inet, luts_available;
	
    cluster_of_block[new_blk] = cluster_index;
//	printf("new_blk %d (%s), cluster_index %d\n", new_blk, block[new_blk].name, cluster_index);
	block[new_blk].cluster_order = *luts_used;
    (*luts_used)++;
	
    luts_available = cluster_size - (*luts_used);
	
	
    //inet = block[new_blk].nets[0];    /* Output pin first. */
	
    /* Output should never be open but I check anyway.  I don't change  *
		* the gain for clock outputs when clocks are globally distributed  *
		* because I assume there is no real need to pack similarly clocked *
		* FFs together then.  Note that by updating the gain when the      *
		* clock driver is placed in a cluster implies that the output of   *
		* LUTs can be connected to clock inputs internally.  Probably not  *
		* true, but it doesn't make much difference, since it will still   *
		* make local routing of this clock very short, and none of my      *
		* benchmarks actually generate local clocks (all come from pads).  */
	
	 /* Output pin first. */
	for (ipin = B_COUT; ipin <=B_DIG; ipin ++)
	{
		inet = block[new_blk].nets[ipin];   

		if (inet != OPEN) {
			if (!is_clock[inet] || !global_clocks)
				mark_and_update_partial_gain (inet, GAIN, lut_size, new_blk, ipin, is_clock,
											luts_available,
											timing_driven, connection_driven, power_driven);
			else
				mark_and_update_partial_gain (inet, NO_GAIN, lut_size, new_blk, ipin,
											is_clock, luts_available, timing_driven,
											connection_driven, power_driven);
			
			net_output_in_cluster[inet] = TRUE;
			
			if (num_pins_of_net_in_cluster[inet] > 1 && !is_clock[inet])
				(*inputs_used)--;
		}
	}
	
    //for (ipin=1;ipin<=lut_size;ipin++) {   
	/*  LUT input pins. */
	for (ipin=B_CIN;ipin<lut_size + B_LUT_IN;ipin++) {   
        inet = block[new_blk].nets[ipin];
        if (inet != OPEN) {
            mark_and_update_partial_gain (inet, GAIN, lut_size, new_blk, ipin,
                                          is_clock, luts_available, timing_driven,
                                          connection_driven, power_driven);
			
            /* If num_pins_of_net_in_cluster != 1, then either the output is *
			* in the cluster or an input for this net is already in the     *
			* cluster.  In either case we don't need a new pin.             */
			
            if (num_pins_of_net_in_cluster[inet] == 1)
                (*inputs_used)++;
        }
    }

/* Note:  The code below ONLY WORKS when nets that go to clock inputs *
* NEVER go to the input of a LUT.  It doesn't really make electrical *
* sense for that to happen, and I check this in the check_clocks     *
* function.  Don't disable that sanity check.                        */

//inet = block[new_blk].nets[lut_size+1];    /* Clock input pin. */
inet = block[new_blk].nets[B_CLK];    /* Clock input pin. */
if (inet != OPEN) {
	if (global_clocks)
		mark_and_update_partial_gain (inet, NO_GAIN, lut_size, new_blk,
									  B_CLK, is_clock, luts_available,
									  timing_driven,
									  connection_driven, power_driven);
	else
		mark_and_update_partial_gain (inet, GAIN, lut_size, new_blk,
									  B_CLK, is_clock, luts_available,
									  timing_driven,
									  connection_driven, power_driven);
	
	if (num_pins_of_net_in_cluster[inet] == 1) {
		(*clocks_used)++;
	}
	else if (num_pins_of_net_in_cluster[inet] == 2 &&
			 net_output_in_cluster[inet]) {
		(*clocks_used)++;
	}
	/* Note: unlike inputs, I'm currently assuming there is no internal *
		* connection in a cluster from LUT outputs to clock inputs.        */
}

update_total_gain(alpha, beta, timing_driven, connection_driven, power_driven);

}


static boolean inputs_and_clocks_feasible (int iblk, int inputs_avail,
										   int clocks_avail, int lut_size, boolean *is_clock) {
	
    /* Checks if adding iblk to the currently open cluster would violate *
	* the cluster input and clock pin limitations.  Returns TRUE if     *
	* iblk can be added to the cluster, FALSE otherwise.                */
	
    int ipin, inet, output_net;
	
	boolean all_output_open;

    /* Output first. */
	//at least one of the output is not open
	all_output_open = TRUE;

	for (ipin = B_COUT ; ipin <= B_DIG; ipin ++)
	{
	    //output_net = block[iblk].nets[0];
		output_net = block[iblk].nets[ipin];
		if (output_net !=  OPEN)		
		{
			if (num_pins_of_net_in_cluster[output_net] != 0 && !is_clock[output_net])
				all_output_open = FALSE;			
		}
	}

	if (all_output_open == FALSE)
		inputs_avail++;
	
    /* Inputs. */
	
    //for (ipin=1;ipin<=lut_size;ipin++) {
	for (ipin=B_CIN;ipin<lut_size +  B_LUT_IN;ipin++) {
        inet = block[iblk].nets[ipin];
        if (inet != OPEN) {
            if (num_pins_of_net_in_cluster[inet] == 0 && inet != output_net)
                inputs_avail--;
        }
    }

	if (block[current_blk].use_ff == 1)
	{
		//check the share pin of FF: CE, SR, CLK
		if (block[iblk].use_ff ==1)
		{
			if (block[iblk].nets[B_CE] != OPEN && block[current_blk].nets[B_CE] != OPEN)
			{
				if (block[iblk].nets[B_CE]  != block[current_blk].nets[B_CE])
				{
					return (FALSE);
				}
				else
				{
					if (block[iblk].use_inv_ce != block[current_blk].use_inv_ce)
					{
						return (FALSE);
					}
				}
			}

			if (block[iblk].nets[B_SR] != OPEN && block[current_blk].nets[B_SR] != OPEN)
			{
				if (block[iblk].nets[B_SR]  != block[current_blk].nets[B_SR])
				{
					return (FALSE);
				}
				else
				{
					if (block[iblk].use_inv_sr != block[current_blk].use_inv_sr)
					{
						return (FALSE);
					}
				}
			}

			if (block[iblk].nets[B_CLK] != OPEN && block[current_blk].nets[B_CLK] != OPEN)
			{
				if (block[iblk].nets[B_CLK]  != block[current_blk].nets[B_CLK])
				{
					return (FALSE);
				}
				else
				{
					if (block[iblk].use_inv_clk != block[current_blk].use_inv_clk)
					{
						return (FALSE);
					}
				}
			}
		}

	}
	
    if (clocks_feasible (iblk, inputs_avail, clocks_avail, lut_size,
                         is_clock) == FALSE)
        return (FALSE);
	
    if (inputs_avail >= 0)
        return (TRUE);
    else
        return (FALSE);
}


static int get_highest_gain_block (int inputs_avail, int clocks_avail,
                                   int lut_size, boolean *is_clock, boolean (*is_feasible) (
																							int iblk, int inputs_avail, int clocks_avail, int lut_size,
																							boolean *is_clock), enum e_gain_type gain_mode) {
	
    /* This routine finds the block with the highest gain that is   *
	* not currently in a cluster and satisfies the feasibility     *
	* function passed in as is_feasible.  If there are no feasible *
	* blocks it returns NO_CLUSTER.                                */
	
    int best_block, i, iblk;
    int best_hillgain;
    float best_gain;
	
    best_gain = (float)NOT_VALID + 1.0;
    best_hillgain=NOT_VALID+1;
	
    best_block = NO_CLUSTER;
	
    /* Divide into two cases for speed only. */
    /* Typical case:  not too many blocks have been marked. */
	//printf("Num_marked_block = %d\n", num_marked_blocks);
    if (num_marked_blocks < num_blocks / MARKED_FRAC) {
        for (i=0;i<num_marked_blocks;i++) {
            iblk = marked_blocks[i];
            if (cluster_of_block[iblk] == NO_CLUSTER) {
                if (gain_mode != HILL_CLIMBING){
                    if (gain[iblk] > best_gain) {
                        if (!is_on_chain[iblk] && !is_start_chain[iblk]) {
							if (is_feasible (iblk, inputs_avail, clocks_avail,
											 lut_size, is_clock)) {
								
								best_gain = gain[iblk];
								best_block = iblk;
							}
                        }
                    }
                }
                else{  /*hill climbing*/
                    if (hillgain[iblk] > best_hillgain) {
                        if (!is_on_chain[iblk] && !is_start_chain[iblk]) {
							if (is_feasible (iblk, inputs_avail, clocks_avail,
											 lut_size, is_clock)) {
								best_hillgain = hillgain[iblk];
								best_block = iblk;
							}
                        }
                    }
                }
            }
        }
    }

else {        /* Some high fanout nets marked lots of blocks. */
for (iblk=first_clusterable_block;iblk<num_blocks;iblk++) {
	if (cluster_of_block[iblk] == NO_CLUSTER) {
		if (gain_mode != HILL_CLIMBING){
			if (gain[iblk] > best_gain) {
				if (!is_on_chain[iblk] && !is_start_chain[iblk]) {
					if (is_feasible (iblk, inputs_avail, clocks_avail,
									 lut_size, is_clock)) {
						best_gain = gain[iblk];
						best_block = iblk;
					}
				}
			}
		}
		else{ /*hill climbing*/
			if (hillgain[iblk] > best_hillgain) {
				if (!is_on_chain[iblk] && !is_start_chain[iblk]) {
					if (is_feasible (iblk, inputs_avail, clocks_avail,
									 lut_size, is_clock)) {
						best_hillgain = hillgain[iblk];
						best_block = iblk;
					}
				}
			}
		}
	}
}
}

return (best_block);
}


static int get_lut_for_cluster (int inputs_avail, int clocks_avail,
                                int cluster_size, int lut_size, int luts_used, boolean *is_clock,
                                boolean allow_unrelated_clustering,
                                int in_carry_chain, int next_in_chain) {
	
    /* Finds the LUT with the the greatest gain that satisifies the      *
	* input, clock and capacity constraints of a cluster that are       *
	* passed in.  If no suitable block is found it returns NO_CLUSTER.  */
	
    int best_block;
	
    if (luts_used == cluster_size)
        return (NO_CLUSTER);
	
	
    if ((in_carry_chain) && (next_in_chain != OPEN)) {
		if (inputs_and_clocks_feasible( next_in_chain, inputs_avail, clocks_avail, lut_size, is_clock)) {
			//printf("next carry block %d (%s) \n", next_in_chain, block[next_in_chain]);
			best_block = next_in_chain;
			num_on_carry_chain--;
		} else {
			best_block = NO_CLUSTER;
		}
		return(best_block);
    }

	//printf("best_block %d \n", best_block);	
    best_block = get_highest_gain_block (inputs_avail, clocks_avail,
                                         lut_size, is_clock, inputs_and_clocks_feasible,
                                         NOT_HILL_CLIMBING);
	
	
    /* If no blocks have any gain to the current cluster, the code above *
		* will not find anything.  However, another block with no inputs in *
		* common with the cluster may still be inserted into the cluster.   */
	
    if (allow_unrelated_clustering)
        if (best_block == NO_CLUSTER)
            best_block = get_free_block_with_most_ext_inputs (lut_size,
															  inputs_avail, clocks_avail);
	
    return (best_block);
}


static int get_free_block_with_fewest_ext_inputs (int lut_size, int
												  clocks_avail) {
	
    /* Used by the hill climbing code.  Finds the LUT that has the     *
	* fewest used inputs and is compatible with the cluster clocks.   *
	* Returns NO_CLUSTER if no suitable block is found.               */
	
    int iblk, ext_inps;
	
    //for (ext_inps=0;ext_inps<=lut_size;ext_inps++) {
	for (ext_inps=0;ext_inps<lut_size + B_LUT_IN - B_CLK;ext_inps++) {
	 
        iblk = get_block_by_num_ext_inputs (ext_inps, lut_size, clocks_avail,
                                            LEAVE_CLUSTERED);
        if (iblk != NO_CLUSTER)
            return (iblk);
    }
	
    return (NO_CLUSTER);
}


static int get_most_feasible_block (int inputs_avail, int clocks_avail,
                                    int lut_size) {
	
    /* Finds the block that is closest to being feasible for the hill    *
	* climbing step.  If no block can ever become feasible (all blocks  *
															* already clustered or have incompatible clocking) the routine      *
	* returns NO_CLUSTER.  Otherwise, it returns the best block to add  *
	* to the cluster and passes back the new number of inputs available *
	* and clocks available through the pointers.                        */
	
    int best_connected_block, lowest_ext_input_block;
	
    best_connected_block = get_highest_gain_block (inputs_avail,
												   clocks_avail, lut_size, NULL, clocks_feasible,
												   HILL_CLIMBING);
	
    /* It could be that there are no clock feasible blocks with any  *
		* connection to the current cluster, or that there are blocks   *
		* that aren't connected to the cluster that have so few inputs  *
		* they are the most feasible blocks.  Hence code below.         */
	
    lowest_ext_input_block = get_free_block_with_fewest_ext_inputs (
																	lut_size, clocks_avail);
	
    if (best_connected_block == NO_CLUSTER)
        return (lowest_ext_input_block);
	
    else if (lowest_ext_input_block == NO_CLUSTER)
        return (best_connected_block);
	
    else {
        if (hillgain[best_connected_block] >= -num_ext_inputs(
															  lowest_ext_input_block, lut_size))
            return (best_connected_block);
        else
            return (lowest_ext_input_block);
    }
}


static void hill_climbing_add_to_cluster (int new_blk, int cluster_index,
										  int lut_size, boolean *is_clock, int *clocks_avail,
										  boolean timing_driven, boolean connection_driven,
										  boolean power_driven) {
	
    /* Adds new_blk to the currently open cluster.  New_blk will be clock *
	* feasible but may not be input-feasible.                            */
	
    int ipin, inet;
	
    cluster_of_block[new_blk] = cluster_index;
	 /* Output pin first. */
	for (ipin = B_COUT; ipin <= B_DIG; ipin ++)
	{
		//inet = block[new_blk].nets[0];   
		inet = block[new_blk].nets[ipin];   
		if (inet != OPEN)
		{
			if (!is_clock[inet])
				mark_and_update_partial_gain (inet, GAIN, lut_size, new_blk,
				ipin, is_clock, 0, timing_driven,
				connection_driven, power_driven);
			else
				mark_and_update_partial_gain (inet, NO_GAIN, lut_size, new_blk,
				ipin, is_clock, 0, timing_driven,
				connection_driven, power_driven);

			net_output_in_cluster[inet] = TRUE;
		}		
	}
	
	/*  LUT input pins. */
    //for (ipin=1;ipin<=lut_size;ipin++) {   
	for (ipin=B_CIN;ipin<B_LUT_IN+ lut_size;ipin++) {   
        inet = block[new_blk].nets[ipin];
        if (inet != OPEN)
            mark_and_update_partial_gain (inet, GAIN, lut_size, new_blk,
                                          ipin, is_clock, 0, timing_driven,
                                          connection_driven, power_driven);
    }

/* Note:  The code below ONLY WORKS when nets that go to clock inputs *
* NEVER go to the input of a LUT.  It doesn't really make electrical *
* sense for that to happen, and I check this in the check_clocks     *  
* function.  Don't disable that sanity check.                        */ 

//inet = block[new_blk].nets[lut_size+1];    /* Clock input pin. */
	inet = block[new_blk].nets[B_CLK];    /* Clock input pin. */
if (inet != OPEN) {
	mark_and_update_partial_gain (inet, NO_GAIN, lut_size, new_blk,
								  B_CLK, is_clock, 0, timing_driven,
								  connection_driven, power_driven);
	
	if (num_pins_of_net_in_cluster[inet] == 1) {
		(*clocks_avail)--;
	}
	else if (num_pins_of_net_in_cluster[inet] == 2 &&
			 net_output_in_cluster[inet]) {
		(*clocks_avail)--;
	}
	/* Note: unlike inputs, I'm currently assuming there is no internal *
		* connection in a cluster from LUT outputs to clock inputs.        */
}
}


static int  hill_climbing (int initial_inputs_avail, int clocks_avail,
                           int cluster_size, int lut_size, int initial_luts_used,
                           int cluster_index, boolean *is_clock, boolean global_clocks,
                           int *next_empty_location_in_cluster, int *block_in_cluster,
                           boolean timing_driven, boolean connection_driven,
                           boolean power_driven) {
	
    /* This routine is called when we find that no more luts can be packed *
	* into the open cluster.  If this is because the cluster is full,     *
	* we immediately exit since there's nothing to do.  If there is still *
	* room in the cluster, however, we may be able to pack more luts in.  *
	* This routine then looks for LUTs which meet the clocking            *
	* constraints of the open cluster which will produce the smallest     *
	* increase in the number of inputs used.  Because adding a LUT can    *
	* *reduce* the number of inputs required by a cluster (when all       *
	* inputs are already in the cluster, and the output of the lut        *
	* already is an input to the cluster), an infeasible cluster could    *
	* become feasible after more luts are added to it.  Hence the hill    *
	* climbing name.  Note also that the attraction function is different *
	* in this function than in the first pass clustering routine -- here  *
	* we're just looking for luts that will fit, not ones with the most   *
	* pins shared.  The routine keeps track after each move of whether or *
	* not the resulting cluster is feasible.  Once the cluster is full    *
	* the cluster state is rolled back to its last feasible configuration.*
	* If this routine didn't accomplish anything that configuration will  *
	* be the cluster config. when this routine was called.                */
	
    /* I have to keep track of the key cluster information after each *
	* block is added so that I can later "roll back" the cluster to  *
	* the last feasible configuration.                               */
	
    /*returns how many blocks added to the cluster*/
	
    static int *inputs_avail = NULL;    /* 0..cluster_size */
    static int *block_added = NULL;     /* Which block was added? */
    int luts_used, iblk, i;
    int num_blocks_added;
	
    num_blocks_added = 0;
	
    /* Only allocate once.  Ugly hack, but what can I do?  Can't free the *
		* memory easily when it's done this way either.                      */
    if (inputs_avail == NULL) {
        inputs_avail = (int *) my_malloc (cluster_size * sizeof(int));
        block_added = (int *) my_malloc (cluster_size * sizeof(int));
    }
	
    if (initial_luts_used == cluster_size)
        return num_blocks_added;
	
    luts_used = initial_luts_used;
    inputs_avail[luts_used-1] = initial_inputs_avail;
	
    while (luts_used != cluster_size) {
        iblk = get_most_feasible_block (inputs_avail[luts_used-1],
                                        clocks_avail, lut_size);
        if (iblk == NO_CLUSTER)
            break;
		
        luts_used++;
        inputs_avail[luts_used-1] = inputs_avail[luts_used-2] + hillgain[iblk];
        block_added[luts_used-1] = iblk;
		
        num_blocks_added++;
        block_in_cluster[*next_empty_location_in_cluster]=iblk;
        (*next_empty_location_in_cluster)++;
		
		printf("     node = %d (%s) [hill climbing]\n",iblk,block[iblk].name);
		
        hill_climbing_add_to_cluster (iblk, cluster_index, lut_size,
                                      is_clock, &clocks_avail, timing_driven, connection_driven,
                                      power_driven);
		
        /* Early exit check.  Each LUT added can reduce the number of inputs *
			* required by at most one, so check if it's hopeless.               */
		
        if (inputs_avail[luts_used-1] + cluster_size - luts_used < 0)
            break;
    }
	
    /* Now roll back to the last feasible clustering. */
    /* NB:  A future enhancement would be to try replicating blocks.  When *
		* a clustering with i blocks isn't feasible below, try finding a      *
		* block which if replicated would reduce the inputs used by one and   *
		* replace the i'th block with it and so on.                           */
	
    for (i=luts_used-1;i>=initial_luts_used;i--) {
        if (inputs_avail[i] >= 0){   /* Found feasible solution! */
            break;
        }
		
        /* Infeasible.  Back up one block.  */
        (*next_empty_location_in_cluster)--;
        num_blocks_added--;
        iblk = block_added[i];
        cluster_of_block[iblk] = NO_CLUSTER;
        block_in_cluster[*next_empty_location_in_cluster]=NO_CLUSTER;
    }
return num_blocks_added;
}


static void alloc_and_load_cluster_info (int ***cluster_contents_ptr,
										 int **cluster_occupancy_ptr,
										 int **cluster_carryouts_ptr, 
										 int *cluster_carryout_blocks,
										 int num_clusters, int cluster_size) {
	
    /* Allocates and loads the cluster_contents and cluster_occupancy    *
	* arrays.  Also checks that all logic blocks have been assigned to  *
	* a legal cluster, no clusters have more than cluster_size logic    *
	* blocks, and that no pads have been put into clusters.             */
	
    int **cluster_contents;  /* [0..num_clusters-1][0..cluster_size-1] */
    int *cluster_occupancy;  /* [0..num_clusters-1] */
    int *cluster_carryouts;  /* [0..num_clusters-1] */
    int iblk, icluster;
	
	printf("alloc_and_load_cluster_info \n");
	printf("num_clusters = %d  \n", num_clusters);
    cluster_contents = (int **) alloc_matrix (0,num_clusters-1,0,cluster_size-1,
											  sizeof(int));
    cluster_occupancy = (int *) my_calloc (num_clusters, sizeof (int));
    cluster_carryouts = (int *) my_calloc (num_clusters, sizeof (int));
	
    for (icluster=0;icluster<num_clusters;icluster++) {
		if (cluster_carryout_blocks[icluster] == -1) {
			cluster_carryouts[icluster] = -1;
		} else {
			cluster_carryouts[icluster] = cluster_of_block[cluster_carryout_blocks[icluster]];
			//printf("Cluster %d has carryout to cluster %d, block %d\n",icluster, cluster_carryouts[icluster], cluster_carryout_blocks[icluster]);
		}
    }
   
	for(iblk=0;iblk<num_blocks;iblk++)
	{
	    if (block[iblk].type == LUT || block[iblk].type == LATCH ||
			block[iblk].type == LUT_AND_LATCH) {
            icluster = cluster_of_block[iblk];
			//printf("Block %d(%s), icluster %d, cluster order %d \n", iblk, block[iblk].name, icluster, block[iblk].cluster_order );

		}
	}

//	exit(1); 

    for (iblk=0;iblk<num_blocks;iblk++) {
		
        if (block[iblk].type == LUT || block[iblk].type == LATCH ||
			block[iblk].type == LUT_AND_LATCH) {
            icluster = cluster_of_block[iblk];
            if (icluster < 0 || icluster > num_clusters-1) {
                printf("Error in alloc_and_load_cluster_info:  "
                       "cluster number (%d) for block\n"
                       "%d (%s) is out of range.\n", icluster, iblk, block[iblk].name);
                exit (1);
            }
			
            cluster_occupancy[icluster]++;

			//printf("Block %d(%s), icluster %d, cluster order %d, cluster occupancy %d \n", iblk, block[iblk].name, icluster, block[iblk].cluster_order, cluster_occupancy[icluster] );
            if (cluster_occupancy[icluster] > cluster_size) {
                printf("Error in alloc_and_load_cluster_info:  "
                       "cluster %d contains more than\n"
                       "%d blocks.\n", icluster, cluster_size);
                exit (1);
            }
            //cluster_contents[icluster][cluster_occupancy[icluster]-1] = iblk;
			cluster_contents[icluster][block[iblk].cluster_order] = iblk;

			//printf("cluster content = %d , iblk %d, cluster occupancy  %d\n", icluster, iblk, cluster_occupancy[icluster]);
        }
		
        else {    /* INPAD or OUTPAD */
            icluster = cluster_of_block[iblk];
            if (icluster != NEVER_CLUSTER) {
                printf("Error in alloc_and_load_cluster_info:  "
                       "block %d is a pad but has\n"
                       "been assigned to cluster %d, Never_CLUSTER %d.\n", iblk, icluster, NEVER_CLUSTER);
                exit (1);
            }
        }
    }

*cluster_occupancy_ptr = cluster_occupancy;
*cluster_contents_ptr = cluster_contents;
*cluster_carryouts_ptr = cluster_carryouts;
}


static void check_clustering (int num_clusters, int cluster_size,
                              int inputs_per_cluster, int clocks_per_cluster, int lut_size,
                              boolean *is_clock, int **cluster_contents, int *cluster_occupancy) {
	
    /* This routine checks that the clustering we have found is indeed a *
	* legal clustering.  It also outputs various statistics about the   *
	* clustering.                                                       */
	
    int iblk, inet, icluster, i, ipin;
    int inputs_used, clocks_used;
    int max_inputs_used, min_inputs_used, summ_inputs_used;
    int max_clocks_used, min_clocks_used, summ_clocks_used;
    int max_occupancy, min_occupancy, num_logic_blocks;
	
    /* Note:  some checking was already done in alloc_and_load_cluster_info. */
	
    /* Brute-force reset of data structures I will need during checking.  */
	
    for (inet=0;inet<num_nets;inet++) {
        num_pins_of_net_in_cluster[inet] = 0;
        net_output_in_cluster[inet] = FALSE;
    }
	
    /* Check that each cluster satisifies the input and clock pin  *
		* constraints and computes some statistics.                   */
	
    max_inputs_used = -1;
    max_clocks_used = -1;
    max_occupancy = -1;
    min_inputs_used = inputs_per_cluster + 1;
    min_clocks_used = clocks_per_cluster + 1;
    min_occupancy = cluster_size + 1;
    summ_inputs_used = 0;
    summ_clocks_used = 0;
/*
	for (icluster=0;icluster<num_clusters;icluster++) {
		printf ("cluster %d, cluster_occupancy = %d \n", icluster, cluster_occupancy[icluster]);
		for (i=0;i<cluster_occupancy[icluster];i++) 
		{
			iblk = cluster_contents[icluster][i];
//			printf ("cluster order %d = iblk %d (%s)\n", i, iblk, block[iblk].name);
			printf ("cluster order %d = iblk %d \n", i, iblk);


		}
	
	}
*/
	
    for (icluster=0;icluster<num_clusters;icluster++) {
		
        if (cluster_occupancy[icluster] <= 0) {
            printf("Error:  cluster %d contains %d logic blocks.\n", icluster, cluster_occupancy[icluster]);
            exit (1);
        }
		
        inputs_used = 0;
		
        clocks_used = 0;
		
		//printf("cluster_occupancy = %d \n", cluster_occupancy[icluster]);
        for (i=0;i<cluster_occupancy[icluster];i++) 
		{
            iblk = cluster_contents[icluster][i];
			
			//printf("iblk = %d\n", iblk);
			// Output 
			for (ipin= B_COUT; ipin <= B_DIG; ipin ++)
			{								
				inet = block[iblk].nets[ipin];              
								
				if (inet != OPEN)
				{
					if (num_pins_of_net_in_cluster[inet] > 0 && !is_clock[inet])
						inputs_used--;
					num_pins_of_net_in_cluster[inet]++;
					net_output_in_cluster[inet] = TRUE;
				}
				
				//printf("inet = %d, inputs_used = %d, num_pins_of_net_in_cluster= %d\n", inet, inputs_used, num_pins_of_net_in_cluster[inet]);
			}
		
            //for (ipin=1;ipin<=lut_size;ipin++) {  // LUT inputs 
			// LUT inputs 
			for (ipin=B_CIN;ipin<lut_size + B_LUT_IN ;ipin++) 
			{  
                inet = block[iblk].nets[ipin];
                if (inet != OPEN) {
                    if (num_pins_of_net_in_cluster[inet] == 0)
                        inputs_used++;
                    num_pins_of_net_in_cluster[inet]++;
                }
            }
			
            //inet = block[iblk].nets[lut_size+1];     // Clock 
			inet = block[iblk].nets[B_CLK];     // Clock 
            if (inet != OPEN) {
                if (num_pins_of_net_in_cluster[inet] == 0 ||
					(num_pins_of_net_in_cluster[inet] == 1 &&
					 net_output_in_cluster[inet]))
                    clocks_used++;
                num_pins_of_net_in_cluster[inet]++;
				
            }
		
        }
/*	
        if (inputs_used > inputs_per_cluster) {
            printf("Error in check_clustering:  cluster %d uses %d inputs.\n",
                   icluster, inputs_used);
            exit (1);
        }
*/
        if (clocks_used > clocks_per_cluster) {
            printf("Error in check_clustering:  cluster %d uses %d clocks.\n",
                   icluster, clocks_used);
            exit (1);
        }
	
        // Reset data structures for check of next cluster 
		
        for (i=0;i<cluster_occupancy[icluster];i++) {
            iblk = cluster_contents[icluster][i];
			
			for (ipin= B_COUT; ipin <= B_DIG; ipin ++)
			{
				//inet = block[iblk].nets[0];

				inet = block[iblk].nets[ipin];
				if (inet != OPEN)
				{
					num_pins_of_net_in_cluster[inet] = 0;
					net_output_in_cluster[inet] = FALSE;
				}
			}
			
            //for (ipin=1;ipin<=lut_size+1;ipin++) {
			for (ipin=B_CLK;ipin<lut_size + B_LUT_IN ;ipin++) 
			{  
                inet = block[iblk].nets[ipin];
                if (inet != OPEN)
                    num_pins_of_net_in_cluster[inet] = 0;
            }
        }
		
        // Compute statistical information. 

        min_inputs_used = min (min_inputs_used, inputs_used);
        max_inputs_used = max (max_inputs_used, inputs_used);
        summ_inputs_used += inputs_used;
		
        min_clocks_used = min (min_clocks_used, clocks_used);
        max_clocks_used = max (max_clocks_used, clocks_used);
        summ_clocks_used += clocks_used;
		
        min_occupancy = min (min_occupancy, cluster_occupancy[icluster]);
        max_occupancy = max (max_occupancy, cluster_occupancy[icluster]);
	
    }      // End for loop over all clusters. 
	
	
    printf("Completed clustering consistency check successfully.\n\n");
	
    printf("Clustering Statistics:\n\n");
    num_logic_blocks = num_blocks - num_p_inputs - num_p_outputs;
    printf("%d Logic Blocks packed into %d Clusters.\n", num_logic_blocks,
           num_clusters);
    printf("\n\t\t\tAverage\t\tMin\tMax\n");
    printf("Logic Blocks / Cluster\t%f\t%d\t%d\n", (float) num_logic_blocks /
           (float) num_clusters, min_occupancy, max_occupancy);
    printf("Used Inputs / Cluster\t%f\t%d\t%d\n", (float) summ_inputs_used /
           (float) num_clusters, min_inputs_used, max_inputs_used);
    printf("Used Clocks / Cluster\t%f\t%d\t%d\n", (float) summ_clocks_used /
           (float) num_clusters, min_clocks_used, max_clocks_used);
    printf("\n");
}


/*globally accessable function*/
void do_clustering (int cluster_size, int inputs_per_cluster,
                    int clocks_per_cluster, int lut_size, boolean global_clocks,
                    boolean muxes_to_cluster_output_pins,
                    boolean *is_clock, boolean hill_climbing_flag,
                    char *out_fname, boolean timing_driven,
                    enum e_cluster_seed cluster_seed_type, float alpha, float beta,
                    int recompute_timing_after, float block_delay,
                    float intra_cluster_net_delay, float inter_cluster_net_delay,
                    boolean allow_unrelated_clustering,
                    boolean allow_early_exit, boolean connection_driven, boolean power_driven,
                    char *activityout_filename, char *functionout_filename){
	
    /* Does the actual work of clustering multiple LUT+FF logic blocks *
	* into clusters.                                                  */
	
    /*note: I allow timing_driven and connection_driven to be simultaneously true*/
    /*in this case, connection_driven is responsible for all clustering decisions*/
    /*but timing analysis is still enabled (useful for viewing the constant delay*/
    /*results) */
	
    int i;
    int num_clusters, istart;
    int inputs_used, luts_used, clocks_used, next_blk;
    int *cluster_occupancy, **cluster_contents;
    int *cluster_carryouts, *cluster_carryout_blocks;
    int blocks_since_last_analysis;
    int farthest_block;
    int *block_in_cluster;
    int next_empty_location_in_cluster;
    int num_blocks_hill_added;
    int num_blocks_clustered;
    int in_carry_chain;
    int next_in_chain;
	int inet;
    boolean critical_path_minimized, dummy_bool;
    boolean early_exit;
	int temp_istart;

	printf("do_clustering\n");	
    check_clocks (is_clock, lut_size);
    //check_for_duplicate_inputs (lut_size);
	check_net_consistent(lut_size);

    init_is_start_chain();
	printf("alloc_and_init_clustering \n");
    alloc_and_init_clustering (lut_size, cluster_size, global_clocks, alpha, beta);
	printf("finish alloc_and_init_clustering \n");

    num_clusters = 0;
    next_empty_location_in_cluster = 0;
    blocks_since_last_analysis = 0;
    critical_path_minimized = FALSE;
    early_exit = FALSE;
    num_blocks_clustered = 0;
    num_blocks_hill_added = 0;
    in_carry_chain = 0;
	
    block_in_cluster = (int*) my_malloc (cluster_size * sizeof (int));
	
    cluster_carryout_blocks = (int *) my_malloc(num_blocks * sizeof(int));
    for(i=0;i<num_blocks;i++) cluster_carryout_blocks[i] = -1;   


    if (timing_driven)
    {
		
        alloc_and_init_path_length(lut_size, is_clock);
		
        calculate_timing_information(block_delay, inter_cluster_net_delay,
                                     intra_cluster_net_delay,
                                     num_clusters,
                                     num_blocks_clustered,
                                     &farthest_block);
		
        //print out initial critical path before clustering starts 
        dummy_bool = report_critical_path(
										  block_delay, inter_cluster_net_delay,
										  intra_cluster_net_delay, farthest_block,
										  cluster_size, TRUE);
		
        if (num_start_carry_chain > 0) {
            istart = get_carry_chain_seed_block(lut_size,inputs_per_cluster,clocks_per_cluster);
            in_carry_chain = 1;
            next_in_chain = block[istart].carryout_to;
		} else {
			in_carry_chain = 0;
			if (cluster_seed_type == TIMING)
			{
				istart=get_most_critical_unclustered_block();
			}
			else if (cluster_seed_type == POWER)
			{
				istart=get_highest_density_unclustered_block(lut_size,
															 inputs_per_cluster,
															 clocks_per_cluster);
			}
			else //max input seed
			{
				istart=get_free_block_with_most_ext_inputs(lut_size,
														   inputs_per_cluster,
														   clocks_per_cluster);
			}
		}

		
		//printf("no timing driven available now\n");
    }
    else //cluster seed is max input (since there is no timing information)
    {

		printf ("num_start_carry_chain %d \n", num_start_carry_chain);	
        if (num_start_carry_chain > 0) 
		{
            istart = get_carry_chain_seed_block(lut_size,inputs_per_cluster,clocks_per_cluster);
//			printf("Carry start %d \n", istart);
            in_carry_chain = 1;
            //next_in_chain = block[istart].carryout_to;
//			printf("COUT %d \n", block[istart].nets[B_COUT]);
//			printf("COUT (%s) num pins %d \n", net[block[istart].nets[B_COUT]].name, net[block[istart].nets[B_COUT]].num_pins);
			if (block[istart].nets[B_COUT] == OPEN)
			{
				next_in_chain = OPEN;
			}
			else
			{
		   		//next_in_chain = net[block[istart].nets[B_COUT]].pins[1];
				for (inet = 1; inet < net[block[istart].nets[B_COUT]].num_pins; inet ++)
				{
					//ignore the driver pin
					next_in_chain = net[block[istart].nets[B_COUT]].pins[inet];
					if (block[next_in_chain].nets[B_CIN] != OPEN)
					{
						if (block[next_in_chain].nets[B_CIN] == block[istart].nets[B_COUT])
						{
							//this is the target block 
							break;
						}
					}
				}
			}

		//	next_in_chain = net[block[istart].nets[B_COUT]].pins[1];
//			printf("next block %d (%s) \n", next_in_chain, block[next_in_chain].name);
			//printf("next block %d \n", next_in_chain);

	//		exit(1);
		
			//printf("Start carry chain istart %d(%s), next_in_chain %d(%s) \n",istart, block[istart].name, next_in_chain, block[next_in_chain].name);
	
		} else 
		{
			in_carry_chain = 0;
			if (cluster_seed_type == POWER)
			{
				istart=get_highest_density_unclustered_block(lut_size,
															 inputs_per_cluster,
															 clocks_per_cluster);
			}
			else
			{
				istart=get_free_block_with_most_ext_inputs(lut_size,
														   inputs_per_cluster,
														   clocks_per_cluster);
				//printf("seed node = %d \n",istart);
			}
		}	
    }

    while (istart != NO_CLUSTER) 
	{
	
        reset_cluster(&inputs_used, &luts_used, &clocks_used,
                      &next_empty_location_in_cluster, block_in_cluster,
                      cluster_size);
		
        num_clusters++;
		
		//printf("seed node = %d (%s)\n",istart,block[istart].name);
        block_in_cluster[next_empty_location_in_cluster]=istart;
        next_empty_location_in_cluster++;
        add_to_cluster(istart, cluster_size, num_clusters - 1, lut_size,
                       is_clock, global_clocks, &inputs_used, &luts_used, &clocks_used,
                       alpha, beta, timing_driven, connection_driven, power_driven);
		
		
		
        num_blocks_clustered ++;
		
        if (timing_driven && !early_exit) {
            blocks_since_last_analysis++;
            //it doesn't make sense to do a timing analysis here since there
			//is only one block clustered it would not change anything      
        }
				

		current_blk = istart;

//		printf(" inputs per cluster %d, inputs used %d, luts used %d, in_carry_chain %d, next in chain %d , current blk %d\n", inputs_per_cluster, inputs_used, luts_used, in_carry_chain, next_in_chain, current_blk);
       // next_blk = get_lut_for_cluster (inputs_per_cluster - inputs_used,
		if ((block[current_blk].nets[B_COUT] == OPEN) && (num_start_carry_chain > 0) )
		{
			//start new cluster for new carry chain 
			in_carry_chain = 0;
			next_blk = NO_CLUSTER;
			
		}
		else
		{
			 next_blk = get_lut_for_cluster ( (B_LUT_IN - B_CLK + lut_size) * cluster_size  - inputs_used,
										clocks_per_cluster - clocks_used, cluster_size, lut_size,
										luts_used, is_clock, allow_unrelated_clustering,
										in_carry_chain, next_in_chain);
		}
			
		
		//printf("next_blk %d\n", next_blk);
        while (next_blk != NO_CLUSTER)
        {
			
			//printf("0 next_blk %d\n", next_blk);
//			printf("next_blk %d, num_clusters %d, num_blocks_clustered %d \n", next_blk, num_clusters, num_blocks_clustered);
//			printf("     node = %d (%s)\n",next_blk,block[next_blk].name);
            block_in_cluster[next_empty_location_in_cluster]=next_blk;
            next_empty_location_in_cluster++;
						
            add_to_cluster(next_blk, cluster_size, num_clusters - 1, lut_size,
                           is_clock, global_clocks, &inputs_used, &luts_used, &clocks_used,
                           alpha, beta, timing_driven, connection_driven, power_driven);
			
			if (block[next_blk].nets[B_COUT] != OPEN){
				in_carry_chain = 0;				
				//printf("next_blk %d (%s), B_COUT %d (%s), num_pins %d \n", next_blk, block[next_blk].name, block[next_blk].nets[B_COUT], net[block[next_blk].nets[B_COUT]].name, net[block[next_blk].nets[B_COUT]].num_pins);
				for (inet = 1; inet < net[block[next_blk].nets[B_COUT]].num_pins; inet ++)
				{
					//ignore the driver pin
					next_in_chain = net[block[next_blk].nets[B_COUT]].pins[inet];
					//printf("Next carry chain -1:  %d, , B_CIN = %d , B_COUT = %d (%s) \n", next_in_chain,  block[next_in_chain].nets[B_CIN], block[next_blk].nets[B_COUT], net[block[next_blk].nets[B_COUT]].name);

					if (block[next_in_chain].nets[B_CIN] != OPEN)
					{
						if (block[next_in_chain].nets[B_CIN] == block[next_blk].nets[B_COUT])
						{
							//this is the target block 
							//printf("Next carry chain 0:  %d, , B_CIN = %d , B_COUT = %d (%s) \n", next_in_chain,  block[next_in_chain].nets[B_CIN], block[next_blk].nets[B_COUT], net[block[next_blk].nets[B_COUT]].name);
							in_carry_chain = 1;

							break;
						}
					}
				}
//				next_in_chain = net[block[next_blk].nets[B_COUT]].pins[1];
				//printf("Next carry chain 0 :%d \n", next_in_chain);				
				//printf ("B_COUT (%s) \n", net[block[next_blk].nets[B_COUT]].name);
			} else {
				in_carry_chain = 0;
			}
            num_blocks_clustered ++;
			
            if (timing_driven && !early_exit) 
			{
                blocks_since_last_analysis++;
                if (blocks_since_last_analysis >= recompute_timing_after) 
				{
                    calculate_timing_information(block_delay ,inter_cluster_net_delay,
                                                 intra_cluster_net_delay,
                                                 num_clusters,
                                                 num_blocks_clustered,
                                                 &farthest_block);
					
                    recompute_length_gain_values(block_in_cluster,
                                                 next_empty_location_in_cluster,
                                                 lut_size,
                                                 global_clocks, is_clock);
					
                    critical_path_minimized = report_critical_path(
																   block_delay, inter_cluster_net_delay,
																   intra_cluster_net_delay, farthest_block,
																   cluster_size, FALSE);
					
                    //once we have clustered every block on the most critical path*
						//no further timing gains can be made. 
					
                    if (critical_path_minimized) 
					{
                         //allow unrelateed clustering now, since we are not    
						//worried any more about inadvertantly absorbing blocks 
						//which might be on a critical path (current and future)
                        allow_unrelated_clustering=TRUE;
						
                        if (allow_early_exit) 
						{
                            // if the critical path is minimized, and we have set this option
                            // there is no need to to any more timing analysis               
                            early_exit = TRUE;
                        }
                    }
					
					
                    blocks_since_last_analysis=0;
                }
            }
			
			if ((block[current_blk].nets[B_COUT] == OPEN) && (num_start_carry_chain > 0) )
			{
				//start new cluster for new carry chain 
				in_carry_chain = 0;
				next_blk = NO_CLUSTER;
			}
			else
			{
				next_blk = get_lut_for_cluster ( (B_LUT_IN - B_CLK + lut_size) * cluster_size  - inputs_used,
                                            clocks_per_cluster - clocks_used, cluster_size,
                                            lut_size, luts_used, is_clock, allow_unrelated_clustering,
                                            in_carry_chain, next_in_chain);
			}

			//printf("1 next_blk %d\n", next_blk);

        } 
        if (hill_climbing_flag && allow_unrelated_clustering && !in_carry_chain)
        {
            num_blocks_hill_added=hill_climbing (inputs_per_cluster - inputs_used,
                                                 clocks_per_cluster - clocks_used, cluster_size, lut_size,
                                                 luts_used, num_clusters - 1, is_clock, global_clocks,
                                                 &next_empty_location_in_cluster, block_in_cluster,
                                                 timing_driven, connection_driven, power_driven);
            num_blocks_clustered += num_blocks_hill_added;
        }


        if (timing_driven)
        {
            if (num_blocks_hill_added > 0  && !early_exit)
            {
                blocks_since_last_analysis += num_blocks_hill_added;
                if (blocks_since_last_analysis >= recompute_timing_after)
                {
                    calculate_timing_information(block_delay, inter_cluster_net_delay,
                                                 intra_cluster_net_delay,
                                                 num_clusters,
                                                 num_blocks_clustered,
                                                 &farthest_block);
					
                    blocks_since_last_analysis=0;
                }
            }
			
			if (in_carry_chain) {
				istart = next_in_chain;
				next_in_chain = block[istart].carryout_to;
				if (next_in_chain == -1) {
					in_carry_chain = 0;
				} 
				cluster_carryout_blocks[num_clusters-1] = istart;
			}
			else if (num_start_carry_chain > 0) {
				istart = get_carry_chain_seed_block(lut_size,inputs_per_cluster,clocks_per_cluster);
				in_carry_chain = 1;
				next_in_chain = block[istart].carryout_to;
				if (next_in_chain == -1) {
					in_carry_chain = 0;
				} 
				
			} else {
				in_carry_chain = 0;
				
				if (cluster_seed_type == TIMING)
				{
					istart=get_most_critical_unclustered_block();
				}
				else if (cluster_seed_type == POWER)
				{
					istart=get_highest_density_unclustered_block(lut_size,
																 inputs_per_cluster,
																 clocks_per_cluster);
				}
				else  //max input seed
				{
					istart=get_free_block_with_most_ext_inputs(lut_size,
															   inputs_per_cluster,
															   clocks_per_cluster);
				}
			}
		}
       else //cluster seed is max input (since there is no timing information)
	   {
           if (in_carry_chain) 
		   {
               istart = next_in_chain;
               //next_in_chain = block[istart].carryout_to;
				if (block[istart].nets[B_COUT] == OPEN)
				{
					next_in_chain = OPEN;						
				}
				else
				{
					in_carry_chain = 0;
					for (inet = 1; inet < net[block[istart].nets[B_COUT]].num_pins; inet ++)
					{
						//ignore the driver pin
						next_in_chain = net[block[istart].nets[B_COUT]].pins[inet];
						if (block[next_in_chain].nets[B_CIN] != OPEN)
						{
							if (block[next_in_chain].nets[B_CIN] == block[istart].nets[B_COUT])
							{
								//printf("Next carry chain 2:  %d, istart %d, B_CIN = %d , B_COUT = %d (%s) \n", next_in_chain, istart, block[next_in_chain].nets[B_CIN], block[istart].nets[B_COUT], net[block[istart].nets[B_COUT]].name);
								//this is the target block 
								in_carry_chain = 1;
								break;
							}
						}
					}

			   	//	next_in_chain = net[block[istart].nets[B_COUT]].pins[1];
				}

				
				//printf("Next carry chain 2 : %d \n", next_in_chain);
				//if (block[istart].nets[B_COUT]  != OPEN)
				//{
				//	printf ("B_COUT (%s) \n", net[block[istart].nets[B_COUT]].name);
				//}
				

               if (next_in_chain == OPEN) 
			   {
				   in_carry_chain = 0;
			   }
               cluster_carryout_blocks[num_clusters-1] = istart;
			   
//			   printf("istart %d \n", istart);
		   }
           else if (num_start_carry_chain > 0) 
		   {
               istart = get_carry_chain_seed_block(lut_size,inputs_per_cluster,clocks_per_cluster);
               in_carry_chain = 1;               
				if (block[istart].nets[B_COUT] == OPEN)
				{
					next_in_chain = OPEN;
				}
				else
				{
			   		next_in_chain = net[block[istart].nets[B_COUT]].pins[1];					
				}
			   
			  // printf("Start carry chain istart %d(%s), next_in_chain %d(%s) \n",istart, block[istart].name, next_in_chain, block[next_in_chain].name);

		   } else {
               in_carry_chain = 0;
               if (cluster_seed_type == POWER)
               {
                   istart=get_highest_density_unclustered_block(lut_size,
																inputs_per_cluster,
																clocks_per_cluster);
               }
               else
               {
                   istart=get_free_block_with_most_ext_inputs(lut_size,
															  inputs_per_cluster,
															  clocks_per_cluster);
				 //  printf ("get_free_block_with_most_ext_inputs, istart %d \n", istart);
			   }
		   }
	   }

    } // while 

    if (timing_driven){
        calculate_timing_information(block_delay, inter_cluster_net_delay,
                                     intra_cluster_net_delay,
                                     num_clusters,
                                     num_blocks_clustered,
                                     &farthest_block);
		
        //print out critical path after circuit has been fully clustered
        dummy_bool = report_critical_path(
										  block_delay, inter_cluster_net_delay,
										  intra_cluster_net_delay, farthest_block,
										  cluster_size, TRUE);
    }

	
//	output_block(17941, 4);
//	output_block(17909, 4);
//	output_block(17910, 4);
	//output_block(4002, 4);

    alloc_and_load_cluster_info (&cluster_contents, &cluster_occupancy, 
                                 &cluster_carryouts, cluster_carryout_blocks,
                                 num_clusters, cluster_size);
	
    check_clustering (num_clusters, cluster_size, inputs_per_cluster,
                      clocks_per_cluster, lut_size, is_clock, cluster_contents,
                      cluster_occupancy);

    output_clustering (cluster_contents, cluster_occupancy, cluster_carryouts,
                       cluster_carryout_blocks, cluster_size,
                       inputs_per_cluster, clocks_per_cluster, num_clusters,
                       lut_size, global_clocks, muxes_to_cluster_output_pins,
                       is_clock, out_fname);
	/*
    output_activities (cluster_contents, cluster_occupancy, cluster_size,
                       inputs_per_cluster, clocks_per_cluster, num_clusters,
                       lut_size, global_clocks, muxes_to_cluster_output_pins,
                       is_clock, activityout_filename);
    output_functions (functionout_filename);

*/
	printf("finished output clustering \n");
    free (cluster_occupancy);
	
    free (block_in_cluster);
	printf("free cluster_contents\n");
    free_matrix (cluster_contents, 0, num_clusters-1, 0,
                 sizeof (int));
	printf("free clustering\n");
    free_clustering ();
	
    if (timing_driven)
        free_path_length_memory();
}

