/****************************************************************************
    Copyright (C) 1987-2005 by Jeffery P. Hansen

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
****************************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/time.h>
#include <unistd.h>
#include <stdarg.h>
#include <string.h>
#include <assert.h>
#include "gsim.h"
#include "ycmalloc.h"

int loops_detected = 0;

//#define PORT_ISCUT(P) ((P->p_type->flags & PF_CUT) || (P->p_gate->g_flags & GF_CPCUT))
int PORT_ISCUT(SPort *P)
{
  int c1 = (P->p_type->flags & PF_CUT);
  int c2 = (P->p_gate->g_flags & GF_CPCUT);

  if (c2)
    printf("gate cut\n");

  return c1 || c2;
}

void uninit_CPath(List *L)
{
  ListElem *E;

  for (E = List_first(L);E;E = List_next(L,E)) {
    CPathHop *ph = (CPathHop*) ListElem_obj(E);
    free(ph);
  }

  List_uninit(L);
}

CPathHop *new_CPathHop(SPort *f,SNet *n,SPort *t)
{
  CPathHop *h = (CPathHop*) malloc(sizeof(CPathHop));

  h->from = f; 
  h->net  = n;
  h->to   = t; 

  return h;
}

CPathHop *copy_CPathHop(CPathHop *ph)
{
  CPathHop *h = (CPathHop*) malloc(sizeof(CPathHop));

  *h = *ph;

  return h;
}

/*
 * Return non-zero if any ports opposite to P are marked with 
 * the loop flag (e.g., if P is an adder input, then it will
 * return non-zero if either the sum output or carry output
 * are marked).
 */
int cpath_anyLPCheck(SPort *P)
{
  SGate *g = P->p_gate;
  int j;

  for (j = 0; j < g->g_ports.num;j++) {
    SPort *P2 = g->g_ports.port[j];
    simTime d = g->g_type->gi_delay ? (*g->g_type->gi_delay)(P,P2) : NO_TIME;
    SNet *n = g->g_ports.port[j]->p_net;
    n = SNet_canonical(n);

    if (d == NO_TIME) continue;

    if ((n->n_flags & NF_LPCHECK))
      return 1;
  }
  return 0;
}

void SNet_propBackDelay(SNet *n,simTime t)
{
  int i;

  n = SNet_canonical(n);

  if ((n->n_flags & NF_LPCHECK)) {
    sendMsg("cpath_loop %s",n->n_name);
    loops_detected = 1;
    return;
  }

  if (t <= n->n_backDelay) return;
  n->n_backDelay = t;
  n->n_flags |= NF_LPCHECK;

  for (i = 0;i < n->n_ports.num; i++) {
    SPort *P = n->n_ports.port[i];
    SGate *g = P->p_gate;
    SGateInfo *gi = g->g_type;

    if (SPort_effectiveType(P) != GIO_OUT || PORT_ISCUT(P)) continue;

    if (gi->gi_propBackDelay) 
      (*gi->gi_propBackDelay)(P,t);
  }

  n->n_flags &= ~NF_LPCHECK;
}

void SNet_propFrwdDelay(SNet *n,simTime t)
{
  int i;

  n = SNet_canonical(n);

  if ((n->n_flags & NF_LPCHECK)) {
    sendMsg("cpath_loop %s",n->n_name);
    loops_detected = 1;
    return;
  }

  if (t <= n->n_frwdDelay) return;
  n->n_frwdDelay = t;

  n->n_flags |= NF_LPCHECK;

  for (i = 0;i < n->n_ports.num; i++) {
    SPort *P = n->n_ports.port[i];
    SGate *g = P->p_gate;
    SGateInfo *gi = g->g_type;

    if (SPort_effectiveType(P) != GIO_IN || PORT_ISCUT(P)) continue;

    if (gi->gi_propFrwdDelay) 
      (*gi->gi_propFrwdDelay)(P,t);
  }

  n->n_flags &= ~NF_LPCHECK;
}

void cpath_clearDPathMark(EvQueue *Q)
{
  HashElem *E;

  for (E = Hash_first(&Q->mod->m_nets);E; E = Hash_next(&Q->mod->m_nets,E)) {
    SNet *n = (SNet*) HashElem_obj(E);
    n->n_flags &= ~NF_DPATH;
  }
}


void clearDelays(EvQueue *Q)
{
  HashElem *E;
  int i;

  for (E = Hash_first(&Q->mod->m_gates);E; E = Hash_next(&Q->mod->m_gates,E)) {
    SGate *g = (SGate*) HashElem_obj(E);

    for (i = 0;i < g->g_ports.num;i++) {
      SPort *P = g->g_ports.port[i];
      P->p_frwdDelay = -1;
      P->p_backDelay = -1;
    }
  }

  for (E = Hash_first(&Q->mod->m_nets);E; E = Hash_next(&Q->mod->m_nets,E)) {
    SNet *n = (SNet*) HashElem_obj(E);

    n->n_frwdDelay = -1;
    n->n_backDelay = -1;
  }
}

void propForward(EvQueue *Q)
{
  HashElem *E;
  int i;

  for (E = Hash_first(&Q->mod->m_gates);E; E = Hash_next(&Q->mod->m_gates,E)) {
    SGate *g = (SGate*) HashElem_obj(E);
    SGateInfo *gi = g->g_type;

    for (i = 0;i < g->g_ports.num;i++) {
      SPort *P = g->g_ports.port[i];
      if (SPort_effectiveType(P) == GIO_OUT && PORT_ISCUT(P)) {
	P->p_frwdDelay = gi->gi_delay ? (*gi->gi_delay)(P,0) : 0;
	SNet_propFrwdDelay(P->p_net,P->p_frwdDelay);
      }
    }
  }
}

void propBackward(EvQueue *Q)
{
  HashElem *E;
  int i;

  /*
    First prop back from input gates with PF_CUT mark
   */
  for (E = Hash_first(&Q->mod->m_gates);E; E = Hash_next(&Q->mod->m_gates,E)) {
    SGate *g = (SGate*) HashElem_obj(E);
    SGateInfo *gi = g->g_type;

    for (i = 0;i < g->g_ports.num;i++) {
      SPort *P = g->g_ports.port[i];
      if (SPort_effectiveType(P) == GIO_IN && PORT_ISCUT(P)) {
	P->p_backDelay = gi->gi_delay ? (*gi->gi_delay)(P,0) : 0;
	SNet_propBackDelay(P->p_net,P->p_backDelay);
      }
    }
  }

  /*
   * Propogate back from any nets with no input ports attacheted to them
   */
  for (E = Hash_first(&Q->mod->m_nets);E; E = Hash_next(&Q->mod->m_nets,E)) {
    SNet *n = (SNet*) HashElem_obj(E);
    int has_in = 0;

    for (i = 0;i < n->n_ports.num;i++) {
      SPort *P = n->n_ports.port[i];
      if (SPort_effectiveType(P) == GIO_IN)
	has_in = 1;
    }

    if (!has_in)
      SNet_propBackDelay(n,0);
  }

  /*
   * Propogate back from remaining nets
   */
  for (E = Hash_first(&Q->mod->m_nets);E; E = Hash_next(&Q->mod->m_nets,E)) {
    SNet *n = (SNet*) HashElem_obj(E);
    SNet_propBackDelay(n,0);
  }
}

static int net_delay_compare(const void *vA,const void *vB)
{
  SNet *A = *(SNet**)vA;
  SNet *B = *(SNet**)vB;
  simTime ad = A->n_frwdDelay + A->n_backDelay;
  simTime bd = B->n_frwdDelay + B->n_backDelay;

  return bd-ad;
}

SNet **getDList(EvQueue *Q,int *d_len)
{
  SNet **d_list;	/* Vector of nets in reverse delay order */ 
  HashElem *E;
  int i;

  *d_len = Hash_numElems(&Q->mod->m_nets);
  d_list = (SNet**) malloc(sizeof(SNet*) * (*d_len + 1));

  i = 0;
  for (E = Hash_first(&Q->mod->m_nets);E; E = Hash_next(&Q->mod->m_nets,E)) {
    SNet *n = (SNet*) HashElem_obj(E);

    if (n != SNet_canonical(n)) continue;

    //    if (!n->n_source)
    d_list[i++] = n;
  }

  *d_len = i;
  d_list[i++] = 0;

  if (*d_len > 1) 
    qsort(d_list,*d_len,sizeof(SNet*),net_delay_compare);

  return d_list;
}

/*
 * Starting at net N, add nets to the end of list L to
 * form the longest path to an output.  A unique path will
 * be selected for each value of pidx.  If pidx is higher than
 * the number of paths through N, then -1 is returned.
 */
int makeForwardPath(List *L,SNet *N,unsigned pidx)
{
  simTime maxDelay = NO_TIME;
  List nextNodes;
  CPathHop *cp,*end_cp;
  int num,sel;
  int i,j;
  int r_value;
  int any_next;

#if 0
  sendMsg("echo makeForwardPath(%s, %d) flags=%x\n",N->n_name,pidx,N->n_flags);
#endif

  /*
   * If the loop flag is set, count this is the end of a path.
   */
  if ((N->n_flags & NF_LPCHECK)) {
    if (pidx == 0)
      return 0;
    else {
      return -1;
    }
  }
  N->n_flags |= NF_LPCHECK;

  List_init(&nextNodes);
  any_next = 0;

  for (i = 0;i < N->n_ports.num; i++) {
    SPort *P = N->n_ports.port[i];
    if (SPort_effectiveType(P) == GIO_IN && !PORT_ISCUT(P)) {
      SGate *g = P->p_gate;

      if (cpath_anyLPCheck(P)) {
	continue;
      }

      for (j = 0; j < g->g_ports.num;j++) {
	SPort *P2 = g->g_ports.port[j];
	simTime d = g->g_type->gi_delay ? (*g->g_type->gi_delay)(P,P2) : NO_TIME;
	SNet *n = g->g_ports.port[j]->p_net;
	n = SNet_canonical(n);

	if (d == NO_TIME) continue;

	any_next = 1;
	d += n->n_backDelay;

	if (d > maxDelay) {
	  List_flush(&nextNodes);
	  maxDelay = d;
	}

	if ((n->n_flags & NF_DPATH))
	  continue;

	if (d == maxDelay) {
	  List_addToTail(&nextNodes,new_CPathHop(P,n,g->g_ports.port[j]));
	}
      }
    }
  }

  num = List_numElems(&nextNodes);
  if (num <= 0) {
    uninit_CPath(&nextNodes);
    N->n_flags &= ~NF_LPCHECK;
    if (pidx == 0 && !any_next)  {
      return 0;
    } else {
      return -1;
    }
  }

  sel = pidx % num;
  pidx /= num;
  cp = List_nth(&nextNodes,sel);

  end_cp = (CPathHop*) ListElem_obj(List_last(L));
  end_cp->to = cp->from;
  List_addToTail(L,new_CPathHop(cp->to,cp->net,0));

  r_value = makeForwardPath(L,cp->net,pidx);

  uninit_CPath(&nextNodes);

  N->n_flags &= ~NF_LPCHECK;

  return r_value;
}

int makeBackwardPath(List *L,SNet *N,unsigned pidx)
{
  simTime maxDelay = NO_TIME;
  List nextNodes;
  CPathHop *cp,*end_cp;
  int num,sel,r_value;
  int i,j;
  int any_next;

  /*
   * If the loop flag is set, count this is the end of a path.
   */
  if ((N->n_flags & NF_LPCHECK)) {
    if (pidx == 0)
      return 0;
    else {
      return -1;
    }
  }
  N->n_flags |= NF_LPCHECK;

  List_init(&nextNodes);
  any_next = 0;

  for (i = 0;i < N->n_ports.num; i++) {
    SPort *P = N->n_ports.port[i];
    if (SPort_effectiveType(P) == GIO_OUT && !PORT_ISCUT(P)) {
      SGate *g = P->p_gate;

      if (cpath_anyLPCheck(P)) {
	continue;
      }

      for (j = 0; j < g->g_ports.num;j++) {
	SPort *P2 = g->g_ports.port[j];
	simTime d = g->g_type->gi_delay ? (*g->g_type->gi_delay)(P,P2) : NO_TIME;
	SNet *n = g->g_ports.port[j]->p_net;
	n = SNet_canonical(n);

	if (d == NO_TIME || (n->n_flags & NF_LPCHECK)) continue;
	any_next = 1;

	d += n->n_frwdDelay;

	if (d > maxDelay) {
	  List_flush(&nextNodes);
	  maxDelay = d;
	}

	if ((n->n_flags & NF_DPATH))
	  continue;

	if (d == maxDelay) {
	    List_addToTail(&nextNodes,new_CPathHop(P,n,P2));
	}
      }
    }
  }

  num = List_numElems(&nextNodes);
  if (num <= 0) {
    N->n_flags &= ~NF_LPCHECK;
    uninit_CPath(&nextNodes);
    if (pidx == 0 && !any_next)
      return 0;
    else {
      return -1;
    }
  }

  sel = pidx % num;
  pidx /= num;
  cp = List_nth(&nextNodes,sel);

 
  end_cp = (CPathHop*) ListElem_obj(List_first(L));
  end_cp->from = cp->from;
  List_addToHead(L,new_CPathHop(0,cp->net,cp->to));

  r_value = makeBackwardPath(L,cp->net,pidx);

  uninit_CPath(&nextNodes);

  N->n_flags &= ~NF_LPCHECK;

  return r_value;
}

/*
  Flag a net as "done" with respect to delay calculations and
  propegate the "done" property.
 */
void cpath_flagDoneNet(SNet *n)
{
  int i,j;

  n = SNet_canonical(n);

  if ((n->n_flags & NF_DPATH)) return;

  n->n_flags |= NF_DPATH;

  for (i = 0;i < n->n_ports.num; i++) {
    SPort *P = n->n_ports.port[i];
    SGate *g = P->p_gate;
    int p_type = SPort_effectiveType(P);

    for (j = 0; j < g->g_ports.num;j++) {
      SPort *P2 = g->g_ports.port[j];
      if (SPort_effectiveType(P2) == p_type && !(P2->p_net->n_flags & NF_DPATH))
	break;
    }

    if (j != g->g_ports.num) continue;	/* There was an unmarked net */

    for (j = 0; j < g->g_ports.num;j++) {
      SPort *P2 = g->g_ports.port[j];
      if (SPort_effectiveType(P2) != p_type)
	cpath_flagDoneNet(P2->p_net);
    }
  }
}

void chooseEndPorts(List *L)
{
  CPathHop *first_cp,*last_cp;
  int i;

  first_cp = (CPathHop*) ListElem_obj(List_first(L));
  last_cp = (CPathHop*) ListElem_obj(List_last(L));

  for (i = 0;i < last_cp->net->n_ports.num; i++) {
    SPort *P = last_cp->net->n_ports.port[i];

    if (SPort_effectiveType(P) != GIO_IN) continue;

    last_cp->to = P;
  }

  for (i = 0;i < first_cp->net->n_ports.num; i++) {
    SPort *P = first_cp->net->n_ports.port[i];

    if (SPort_effectiveType(P) != GIO_OUT) continue;

    first_cp->from = P;
  }
}

void makePathString(char *q,List *L)
{
  ListElem *E;

  *q = 0;

  for (E = List_first(L);E;E = List_next(L,E)) {
    CPathHop *ph = (CPathHop*) ListElem_obj(E);
    SNet *pn = ph->net;

    q += sprintf(q," ");
    if (ph->from) {
      q += sprintf(q,"{<%s[%s]>",ph->from->p_gate->g_name,ph->from->p_name);
    } else
      q += sprintf(q,"{<>");

    q += sprintf(q,":%s:",pn->n_name);

    if (ph->to) {
      q += sprintf(q,"<%s[%s]>}",ph->to->p_gate->g_name,ph->to->p_name);
    } else
      q += sprintf(q,"<>}");
  }
}

void cpath_LPCheck_mark(List *L,int markp)
{
  ListElem *E;

  for (E = List_first(L);E;E = List_next(L,E)) {
    CPathHop *ph = (CPathHop*) ListElem_obj(E);
    SNet *n = ph->net;
    
    if (markp)
      n->n_flags |= NF_LPCHECK;
    else
      n->n_flags &= ~NF_LPCHECK;
  }
}

void reportCriticalPaths(EvQueue *Q,SNet **d_list,int max_path)
{
  int i,j,k,l;
  simTime cur_t = NO_TIME;

#if 0
  sendMsg("echo reportCriticalPaths: %d",max_path);
#endif

  for (i = 0;d_list[i];i++) {
    SNet *n = d_list[i];
    simTime t = n->n_frwdDelay + n->n_backDelay;

    if (t != cur_t) {
      cpath_clearDPathMark(Q);
      cur_t = t;
    }


    l = 0;
    k = 0;
    for (j = 0;;j++, l++) {
      List L;
      char buf[STRMAX];

      List_init(&L);
      List_addToTail(&L,new_CPathHop(0,n,0));

      if (makeForwardPath(&L,n,j) == -1) {
	int xx; 
	k++;
	j = 0;
	List_flush(&L);
	List_addToTail(&L,new_CPathHop(0,n,0));
	xx = makeForwardPath(&L,n,j);
      }

      cpath_LPCheck_mark(&L,1);
      n->n_flags &= ~NF_LPCHECK;

      if (makeBackwardPath(&L,n,k) == -1) {
	break;
      }

      cpath_LPCheck_mark(&L,0);

#if 0
      sendMsg("echo %s (%d,%d) --- frwd:%d back:%d",n->n_name,j,k,n->n_frwdDelay,n->n_backDelay);
#endif

      chooseEndPorts(&L);

      makePathString(buf,&L);

#if 0
      sendMsg("echo %d: [%d %d %s] %s",l,n->n_frwdDelay,n->n_backDelay,n->n_name,buf);
#endif
      sendMsg("cpath %d %s",n->n_frwdDelay+n->n_backDelay,buf);

      uninit_CPath(&L);

      if (--max_path <= 0) {
	cpath_flagDoneNet(n);
	return;
      }
    }
    cpath_flagDoneNet(n);
  }
}

void cpath_reportNetDelays(EvQueue *Q)
{
  HashElem *E;

  for (E = Hash_first(&Q->mod->m_nets);E; E = Hash_next(&Q->mod->m_nets,E)) {
    SNet *n = (SNet*) HashElem_obj(E);
    SNet *cn = SNet_canonical(n);

    sendMsg("netdelay %s %d %d",n->n_name,cn->n_frwdDelay, cn->n_backDelay);
    if (n != cn)
      sendMsg("netalias %s %s",n->n_name,cn->n_name);
  }
}

void findCriticalPaths(EvQueue *Q,int n)
{
  SNet **d_list;	/* Vector of nets in reverse delay order */ 
  int d_len;

  loops_detected = 0;
  clearDelays(Q);
  propForward(Q);
  propBackward(Q);

  if (!loops_detected) {
    d_list = getDList(Q,&d_len);

    reportCriticalPaths(Q,d_list,n);
    free(d_list);

    cpath_reportNetDelays(Q);
  }

  sendMsg("cdone");
}