/*
 +--------------------------------------------------------------------------+
 | FlowMap: LUT-Based FPGA Technology Mapping Package (Release B 0.2)       |
 +--------------------------------------------------------------------------+
 | Copyright (C) 1991-1994 the Regents of University of California          |
 +--------------------------------------------------------------------------+
 | Restricted distribution only -- see "release.statement"                  |
 +--------------------------------------------------------------------------+
 | Author: Eugene Ding, VLSI CAD Lab, UCLA  CS Dept. <eugene@cs.ucla.edu>   |
 +--------------------------------------------------------------------------+
 | File Name:   dfmap.c                                                     |
 | Description: duplication-free optimal mapping routine                    |
 +--------------------------------------------------------------------------+
*/

#include "flowmap.h"

#define MAX_BRANCH 256
#define MFFCOUT 0x0
#define MFFCIN 0x1
#define MFFCBDR 0x2
#define MFFCLUT 0x4
#define LUTPKBDR 0x4
#define NETWKIN 0x0
#define NETWKOUT 0x1
#define ROOTCKD 0x2
#define ROOTIMPD 0x4
#define CUTNODE 0x8
#define LUTROOT 0x8
#define LUTBDR 0x8
#define LUTCTNT 0x8

#define MarkLOW(v,m) (Mark(v) = ((Mark(v) & ~0xF) | m))
#define ClearLOW(v,m) (Mark(v) = (Mark(v) & ~m))
#define FlushLOW(v) (Mark(v) = (Mark(v) & ~0xF))
#define MarkedLOW(v,m) (((Mark(v)) & 0xF) == m)
#define MarkHIGH(v,m) (Mark(v) = (Mark(v) | (m << 4)))
#define ClearHIGH(v,m) (Mark(v) = (Mark(v) & ~(m << 4)))
#define FlushHIGH(v) (Mark(v) = (Mark(v) & ~0xF0))
#define MarkedHIGH(v,m) (((((Mark(v)) & 0xF0) >> 4) & m) == m)
#define MFFCout(n) ((flow_aux_t *)(n->undef1))->undef.array_u

#define array_delete_last(type,a) \
(((a)->num <= 0)?array_abort((a),0):((a)->num --))
#define array_delete_gen(type,a,i) \
((a)->index = (i),\
(a)->index < 0 ? array_abort((a),0) : 0,\
(a)->index >= (a)->n_size ? array_abort((a),0) : 0,\
*((type *) ((a)->space + (a)->index * (a)->obj_size)) = \
array_fetch_last(type,a),\
array_delete_last(type,a),\
(a)->index = -(int)sizeof(type) )

#define array_delete(type,a,i) \
(((i)>=array_n(a))?array_abort((a),4):\
(((i)==array_n(a)-1)?array_delete_last(type,a)\
:array_delete_gen(type,a,i)))

struct sptree4cut
{
  Dag tree;
  int ***cuts;
};

typedef struct sptree4cut SPtree;

static int
df_min_cut(node, mffcb, k, bcosta, bcostd)
node_t *node;
array_t *mffcb;
int k, *bcosta, *bcostd;
{
  return (-1);
}

static int
dfs_mark(v, T)
node_t *v;
SPtree *T;
{
  node_t *t, *t0;
  lsGen gen;
  int m, tm = 1;

  if (MarkedLOW(v, MFFCBDR))
  {
    T->tree[Gindex(v)].mark = SINK_MARK;
    T->tree[Gindex(v)].node = v;
    return (tm);
  }
  T->tree[Gindex(v)].mark = -PASSED_MARK;
  T->tree[Gindex(v)].node = v;
  foreach_fanin(v, m, t)
  {
    if (tm && (node_num_fanout(t) > 1))
    {
      if (MarkedLOW(t, MFFCIN))
	tm = 0;
      else
      {
	tm = 2;
	foreach_fanout(t, gen, t0)
	{
	  if (MarkedHIGH(t0, NETWKOUT))
	    continue;
	  if (!MarkedLOW(t0, MFFCOUT))
	    tm--;
	}
	if (tm < 0)
	  tm = 0;
      }
    }
    if (T->tree[Gindex(t)].mark != NON_MARK)
      continue;
    AddArc(T->tree, T->tree + Gindex(v), T->tree + Gindex(t), 1);
    tm *= dfs_mark(t, T);
  }
  if (tm)
    T->tree[Gindex(v)].mark = PASSED_MARK;
  return (tm);
}

#define LinkT(n,v) (Gindex(n)=v)

static SPtree *
make_spanning_tree(n, tfi, k)
node_t *n;
array_t *tfi;
int k;
{
  SPtree *T;
  int i, j;
  node_t *t;

  LinkT(n, 1);
  i = 1;
  for (j = array_n(tfi) - 1; j >= 0; j--)
  {
    t = array_fetch(node_t *, tfi, j);
    LinkT(t, ++i);
  }
  T = ALLOC(SPtree, 1);
  T->tree = NewDag(i);
  (void) dfs_mark(n, T);
  T->cuts = ALLOC(int **, i + 1);
  for (; i > 0; i--)
  {
    T->cuts[i] = ALLOC(int *, k + 1);
    for (j = 0; j <= k; T->cuts[i][j++] = NULL);
  }
  return (T);
}

static int
free_spanning_tree(T, k)
SPtree *T;
int k;
{
  int j, m;

  for (j = 0; j <= k; j++)
    if (T->cuts[1][j] != NULL)
      FREE(T->cuts[1][j]);
  FREE(T->cuts[1]);
  FREE(T->cuts);
  FreeDag(T->tree);
  FREE(T);
  T = NULL;
}

static int
K_from_n(comb, k, n)
int comb[];
int k, n;
{
  int i = 0;

  if (n < 0)
  {
    while (k > 0 && i < -n)
    {
      comb[i++] = 1;
      k--;
    }
    if (k == 0)
      while (i < -n)
	comb[i++] = 0;
    else
      comb[0] += k;
    return (1);
  }
  while (comb[i] == 0)
    i++;
  if (i == n - 1)
    return (0);
  k = i;
  while (i < n - 1 && comb[i] == 1)
    i++;
  if (i == n - 1 && comb[i] != 0)
  {
    k = n - k - 1;
    comb[0] = comb[i] + 1;
    for (i = 1; i < k; comb[i++] = 1);
    for (; i < n; comb[i++] = 0);
  }
  else
  {
    if (i == k)
    {
      if (comb[i + 1] == 0)
      {
	comb[i + 1] = comb[i];
	comb[i] = 0;
      }
      else
      {
	comb[i + 1]++;
	comb[0] = comb[i] - 1;
	if (i != 0)
	  comb[i] = 0;
      }
    }
    else
    {
      if (comb[i] == 0)
      {
	comb[i--] = 1;
	comb[i--] = 0;
      }
      else if (comb[i + 1] != 0)
      {
	comb[i + 1]++;
	comb[i]--;
      }
      else
      {
	comb[i + 1] = comb[i - 1];
	comb[i - 1] = comb[i];
	comb[i--] = 0;
      }
      for (k = 0; i > k && comb[k] < comb[i]; k++, i--)
      {
	n = comb[i];
	comb[i] = comb[k];
	comb[k] = n;
      }
    }
  }
  return (1);
}

static int
K_from_n_4_tree(comb, k, n)
int comb[];
int k, n;
{
  int i = 0;

  if (n > k)
    return (0);
  if (n < 0)
  {
    while (i < -n)
      comb[i++] = 1;
    comb[0] = k - ((-n) - 1);
    return (1);
  }
  while (comb[i] == 1)
    i++;
  if (i >= n - 1)
    return (0);
  comb[i + 1]++;
  comb[i]--;
  if (i != 0)
  {
    comb[0] = comb[i];
    comb[i] = 1;
  }
  return (1);
}

#define TrNode(T,v) (T->tree[v].node)
#define foreach_arc(S,A,T) \
for (A=S.out_list;((A==NULL)?0:(T=A->this->id));A=A->next)

static int
dfs_check_4_root(t)
node_t *t;
{
  int i, ret = 1;
  node_t *v;

  foreach_fanin(t, i, v)
  {
    if (ret == 0)
      return (0);
    if (MarkedHIGH(v, CUTNODE))
      CNT(v)++;
    else if (MarkedLOW(v, MFFCBDR))
    {
      return (0);
    }
    else
      ret = dfs_check_4_root(v);
  }
  return (ret);
}

static int
dfs_check_4_nonroot(T, t)
SPtree *T;
int t;
{
  int ret = 1;
  int v;
  Arc arc;

  foreach_arc(T->tree[t], arc, v)
  {
    if (ret == 0)
      return (0);
    if (MarkedHIGH(TrNode(T, v), CUTNODE))
      CNT(TrNode(T, v))++;
    else if (MarkedLOW(TrNode(T, v), MFFCBDR))
    {
      return (0);
    }
    else
      ret = dfs_check_4_nonroot(T, v);
  }
  return (ret);
}

static int
is_cut(T, v, k, omffcet)
SPtree *T;
int v, k, omffcet;
{
  int i, bd, ret = 1;
  node_t *t;

  bd = 1 + omffcet * k;
  for (i = bd - k; ret && i < bd; i++)
  {
    if (MarkedHIGH(TrNode(T, T->cuts[v][k][i]), CUTNODE))
      ret = 0;
    else
    {
      MarkHIGH(TrNode(T, T->cuts[v][k][i]), CUTNODE);
      CNT(TrNode(T, T->cuts[v][k][i])) = 0;
    }
  }
  t = TrNode(T, v);
  if (ret && !MarkedHIGH(TrNode(T, 1), CUTNODE))
  {
    if (v == 1)
      ret = dfs_check_4_root(t);
    else
      ret = dfs_check_4_nonroot(T, v);
  }
  else
    ret = 0;
  for (i = bd - k; i < bd; i++)
  {
    if (CNT(TrNode(T, T->cuts[v][k][i])) == 0)
      if (node_num_fanout(TrNode(T, T->cuts[v][k][i])) <= 1 || v == 1)
	ret = 0;
    CNT(TrNode(T, T->cuts[v][k][i])) = 0;
    ClearHIGH(TrNode(T, T->cuts[v][k][i]), CUTNODE);
  }
  return (ret);
}

static void
dfs_sub_spt(T, w, mk)
SPtree *T;
int w;
int *mk;
{
  Arc arc;
  int v;

  foreach_arc(T->tree[w], arc, v)
  {
    mk[v] = 1;
    if (T->tree[v].mark == SINK_MARK)
      continue;
    dfs_sub_spt(T, v, mk);
  }
}

static int
non_esc(T, w, m, j)
SPtree *T;
int w, m, j;
{
  lsGen gen;
  node_t *n, *t;
  int *prvtmk;
  int i, ret = 0;

  prvtmk = ALLOC(int, T->tree[0].id + 1);
  for (i = 0; i <= T->tree[0].id; prvtmk[i++] = 0);
  prvtmk[w] = 1;
  dfs_sub_spt(T, w, prvtmk);
  for (i = 0; ret == 0 && i < m - 1; i++)
  {
    n = TrNode(T, T->cuts[w][m][1 + j * m + i]);
    ret = 1;
    foreach_fanout(n, gen, t)
    {
      if (MarkedHIGH(t, NETWKOUT))
	continue;
      if (MarkedLOW(t, MFFCOUT))
	continue;
      if (prvtmk[Gindex(t)])
	continue;
      ret = 0;
      break;
    }
  }
  FREE(prvtmk);
  return (ret);
}

static int
gencut(T, v, areaopt, k, mffcb, threshold, nogen, mb)
SPtree *T;
int v, areaopt, k;
array_t *mffcb;
int threshold, nogen, mb;
{
  int comb[MAX_BRANCH];
  Arc arc;
  int i, j, l, m, w, ba, bd, bb, dg, omffcet;
  int *lgct, *tmp, *chdrn;
  int ***redun;
  node_t *t0, *t1;
  lsGen gen;
  int skip = 0, th = threshold;

  redun = NULL;
  if (T->tree[v].mark == SINK_MARK)
  {
    T->cuts[v][0] = NULL;
    T->cuts[v][1] = ALLOC(int, 2);
    T->cuts[v][1][0] = 1;
    T->cuts[v][1][1] = v;
    return (1);
  }
  if (T->tree[v].out_list == NULL)
  {
    T->cuts[v][0] = ALLOC(int, 1);
    T->cuts[v][0][0] = 0;
    T->cuts[v][1] = ALLOC(int, 2);
    T->cuts[v][1][0] = 1;
    T->cuts[v][1][1] = v;
    return (0);
  }
  dg = T->tree[v].degree;
  chdrn = ALLOC(int, dg);
  l = 0;
  foreach_arc(T->tree[v], arc, m)
      chdrn[l++] = m;
  l = 0;
  for (m = 0; m < dg; m++)
  {
    if (T->tree[chdrn[m]].mark > 0)
      l += gencut4tree(T, chdrn[m], k);
    else
      l += gencut(T, chdrn[m], areaopt, k, mffcb, threshold, nogen, mb);
  }
  if (l == 0)
  {
    T->cuts[v][0] = ALLOC(int, 1);
    T->cuts[v][0][0] = 0;
  }
  if (v != 1 && !nogen)
  {
    redun = ALLOC(int **, dg);
    for (l = 0; l < dg; l++)
    {
      redun[l] = ALLOC(int *, k + 1);
      redun[l][0] = redun[l][k] = NULL;
      for (m = 1; m < k; m++)
      {
	redun[l][m] = ALLOC(int, 1);
	redun[l][m][0] = 0;
      }
    }
    for (l = 0; l < dg; l++)
    {
      w = chdrn[l];
      for (m = 1; m < k; m++)
      {
	if (T->cuts[w][m + 1] != NULL)
	{
	  for (j = T->cuts[w][m + 1][0] - 1; j >= 0; j--)
	    if (T->cuts[w][m + 1][(j + 1) * (m + 1)] != w)
	      break;
	  for (j++; j <= T->cuts[w][m + 1][0] - 1; j++)
	  {
	    if (non_esc(T, w, m + 1, j))
	      continue;
	    redun[l][m] = REALLOC(int, redun[l][m], 1 + m * (redun[l][m][0] + 1));
	    for (i = 0; i < m; i++)
	      redun[l][m][1 + m * redun[l][m][0] + i] = T->cuts[w][m + 1][1 + j * (m + 1) + i];
	    redun[l][m][0]++;
	  }
	}
	if (T->cuts[w][m] != NULL && node_num_fanout(TrNode(T, w)) > 1)
	{
	  for (j = T->cuts[w][m][0] - 1; j >= 0; j--)
	    if (T->cuts[w][m][(j + 1) * m] != w)
	      break;
	  for (j++; j <= T->cuts[w][m][0] - 1; j++)
	  {
	    redun[l][m] = REALLOC(int, redun[l][m], 1 + m * (redun[l][m][0] + 1));
	    for (i = 0; i < m; i++)
	      redun[l][m][1 + m * redun[l][m][0] + i] = T->cuts[w][m][1 + j * m + i];
	    redun[l][m][0]++;
	  }
	}
	if (redun[l][m][0] == 0)
	{
	  FREE(redun[l][m]);
	  redun[l][m] = NULL;
	}
      }
    }
  }
  else
    redun = NULL;
  lgct = ALLOC(int, dg);
  tmp = ALLOC(int, dg);
  if (T->cuts[v][1] == NULL)
  {
    T->cuts[v][1] = ALLOC(int, 2);
    T->cuts[v][1][0] = 1;
    T->cuts[v][1][1] = v;
  }
  else
  {
    T->cuts[v][1] = REALLOC(int, T->cuts[v][1], T->cuts[v][1][0] + 2);
    T->cuts[v][1][0]++;
    T->cuts[v][1][T->cuts[v][1][0]] = v;
  }
  for (l = 1; l <= k; l++)
  {
    (void) K_from_n(comb, l, -dg);
    do
    {
      for (m = 0; m < dg; m++)
	if (T->cuts[chdrn[m]][comb[m]] == NULL)
	  break;
      if (m < dg)
      {
	continue;
      }
      for (m = 0; m < dg; m++)
	if (comb[m] == 0)
	  lgct[m] = -1;
	else
	  lgct[m] = 0;
      do
      {
	if (T->cuts[v][l] == NULL)
	{
	  omffcet = 1;
	  T->cuts[v][l] = ALLOC(int, 1 + l);
	  T->cuts[v][l][0] = 0;
	  if (v == 1)
	    ba = bb = bd = T->tree[0].id + 1;
	}
	else
	{
	  omffcet = 1 + (T->cuts[v][l][0]) * l;
	  T->cuts[v][l] = REALLOC(int, T->cuts[v][l], omffcet + l);
	}
	for (m = 0; m < dg; m++)
	{
	  if (lgct[m] == -1)
	    continue;
	  w = lgct[m] * comb[m] + 1;
	  for (i = w; i < w + comb[m]; i++)
	    T->cuts[v][l][omffcet + i - w] = T->cuts[chdrn[m]][comb[m]][i];
	  omffcet += comb[m];
	}
	if ((--threshold) == 0)
	{
	  skip = 1;
	  continue;
	}
	if (is_cut(T, v, l, T->cuts[v][l][0] + 1))
	{
	  T->cuts[v][l][0]++;
	  if (v == 1)
	  {
	    for (i = (T->cuts[v][l][0]) * l, m = i - l + 1; m <= i; m++)
	      MarkHIGH(T->tree[T->cuts[v][l][m]].node, LUTROOT);
	    if (MarkedHIGH(T->tree[1].node, LUTROOT))
	    {
	      for (m = i - l + 1; m <= i; m++)
		ClearHIGH(T->tree[T->cuts[v][l][m]].node, LUTROOT);
	      T->cuts[v][l][0]--;
	    }
	    else
	    {
	      CNT(T->tree[1].node) = -1;
	      for (j = array_n(mffcb) - 1; j >= 0; j--)
	      {
		t0 = array_fetch(node_t *, mffcb, j);
		m = w = 0;
		foreach_fanout(t0, gen, t1)
		{
		  if (MarkedHIGH(t1, NETWKOUT))
		    continue;
		  if (CNT(t1) >= 0)
		    m++;
		  else
		    w++;
		}
		if (w == 0 || MarkedHIGH(t0, LUTROOT))
		  CNT(t0) = 0;
		else if (m == 0)
		  CNT(t0) = -1;
		else
		{
		  for (m = i - l + 1; m <= i; m++)
		    ClearHIGH(T->tree[T->cuts[v][l][m]].node, LUTROOT);
		  T->cuts[v][l][0]--;
		  break;
		}
	      }
	      CNT(T->tree[1].node) = 0;
	      for (m = array_n(mffcb) - 1; m >= 0; m--)
		CNT(array_fetch(node_t *, mffcb, m)) = 0;
	      if (j < 0)
	      {
		w = 1;
		j = 0;
		for (i = array_n(mffcb) - 1; i >= 0; i--)
		{
		  t0 = array_fetch(node_t *, mffcb, i);
		  if (!MarkedHIGH(t0, LUTROOT))
		    continue;
		  if (MarkedLOW(t0, MFFCBDR))
		    continue;
		  w += (int) array_fetch(int *, Cluster(t0), 0);
		  for (m = array_n(Frontier(t0)) - 1; m >= 0; m--)
		  {
		    t1 = array_fetch(node_t *, Frontier(t0), m);
		    MarkHIGH(t1, LUTROOT);
		  }
		}
		for (i = 0; i < array_n(mffcb); i++)
		{
		  t0 = array_fetch(node_t *, mffcb, i);
		  Label(t0) = 0;
		  if (!MarkedHIGH(t0, LUTROOT))
		    continue;
		  ClearHIGH(t0, LUTROOT);
		  if (MarkedLOW(t0, MFFCBDR))
		    continue;
		  for (m = array_n(Frontier(t0)) - 1; m >= 0; m--)
		  {
		    t1 = array_fetch(node_t *, Frontier(t0), m);
		    if (Label(t1) > Label(t0))
		      Label(t0) = Label(t1);
		  }
		  Label(t0) += (int) array_fetch(int *, Cluster(t0), 1);
		  if (Label(t0) > j)
		    j = Label(t0);
		}
		j++;
		m = ((areaopt) ? ((w < ba) || (w == ba && (mb ? (l < bb) : (j < bd))))
		   : ((j < bd) || (j == bd && (mb ? (l < bb) : (w < ba)))));
		if (m)
		{
		  ba = w;
		  bb = l;
		  bd = j;
		  if (T->cuts[v][l][0] > 1)
		  {
		    for (i = (T->cuts[v][l][0]) * l, m = i - l + 1; m <= i; m++)
		      T->cuts[v][l][m - l] = T->cuts[v][l][m];
		    T->cuts[v][l][0]--;
		  }
		}
		else
		  T->cuts[v][l][0]--;
	      }
	    }
	  }
	}
	for (m = 0; m < dg; m++)
	{
	  if (lgct[m] == -1)
	    continue;
	  if ((++lgct[m]) >= T->cuts[chdrn[m]][comb[m]][0])
	    lgct[m] = 0;
	  else
	    break;
	}
      } while (m < dg && !skip);
    } while (K_from_n(comb, l, dg) && !skip);
    if (v != 1 && l > 1 && !nogen && !skip)
    {
      (void) K_from_n(comb, l - 1, -dg);
      do
      {
	for (m = 0; m < dg; m++)
	{
	  if (comb[m] == 0)
	    continue;
	  if (redun[m][comb[m]] == NULL)
	    break;
	}
	if (m < dg)
	  continue;
	for (m = 0; m < dg; m++)
	  if (comb[m] == 0)
	    lgct[m] = -1;
	  else
	    lgct[m] = 0;
	do
	{
	  if (T->cuts[v][l] == NULL)
	  {
	    omffcet = 1;
	    T->cuts[v][l] = ALLOC(int, 1 + l);
	    T->cuts[v][l][0] = 0;
	  }
	  else
	  {
	    omffcet = 1 + (T->cuts[v][l][0]) * l;
	    T->cuts[v][l] = REALLOC(int, T->cuts[v][l], omffcet + l);
	  }
	  for (m = 0; m < dg; m++)
	  {
	    if (lgct[m] == -1)
	      continue;
	    w = lgct[m] * comb[m] + 1;
	    for (i = w; i < w + comb[m]; i++)
	      T->cuts[v][l][omffcet + i - w] = redun[m][comb[m]][i];
	    omffcet += comb[m];
	  }
	  T->cuts[v][l][omffcet++] = v;
	  T->cuts[v][l][0]++;
	  for (m = 0; m < dg; m++)
	  {
	    if (lgct[m] == -1)
	      continue;
	    if ((++lgct[m]) >= redun[m][comb[m]][0])
	      lgct[m] = 0;
	    else
	      break;
	  }
	} while (m < dg);
      } while (K_from_n(comb, l - 1, dg));
    }
    if (T->cuts[v][l] != NULL)
      if (T->cuts[v][l][0] == 0)
      {
	FREE(T->cuts[v][l]);
	T->cuts[v][l] = NULL;
      }
    if (skip)
      if (v == 1)
      {
	threshold = th;
	skip = 0;
      }
      else
	break;
  }
  for (l = 0; l < dg; l++)
  {
    for (m = 0; m <= k; m++)
    {
      if (T->cuts[chdrn[l]][m] != NULL)
      {
	FREE(T->cuts[chdrn[l]][m]);
	T->cuts[chdrn[l]][m] = NULL;
      }
      if (redun != NULL)
	if (redun[l][m] != NULL)
	{
	  FREE(redun[l][m]);
	  redun[l][m] = NULL;
	}
    }
    FREE(T->cuts[chdrn[l]]);
    T->cuts[chdrn[l]] = NULL;
    if (redun != NULL)
    {
      FREE(redun[l]);
      redun[l] = NULL;
    }
  }
  FREE(lgct);
  FREE(chdrn);
  FREE(tmp);
  if (redun != NULL)
    FREE(redun);
  if (T->cuts[v][0] != NULL)
    return (0);
  for (l = k; l >= 0; l--)
    if (T->cuts[v][l] != NULL)
      break;
  {
    int count = 0;

    for (i = 2; i <= k; i++)
    {
      if (T->cuts[v][i] == NULL)
	continue;
      count += T->cuts[v][i][0];
    }
  }
  return (l);
}

static int
gencut4tree(T, v, k)
SPtree *T;
int v, k;
{
  static int comb[MAX_BRANCH];
  Arc arc;
  int i, l, m, w, dg, omffcet;
  int *lgct, *chdrn;

  dg = T->tree[v].degree;
  T->cuts[v][1] = ALLOC(int, 2);
  T->cuts[v][1][0] = 1;
  T->cuts[v][1][1] = v;
  if (T->tree[v].mark == SINK_MARK || k < dg)
    return (1);
  chdrn = ALLOC(int, dg);
  l = 0;
  foreach_arc(T->tree[v], arc, m)
      chdrn[l++] = m;
  for (m = 0; m < dg; m++)
    gencut4tree(T, chdrn[m], k - dg + 1);
  lgct = ALLOC(int, dg);
  for (l = dg; l <= k; l++)
  {
    (void) K_from_n_4_tree(comb, l, -dg);
    do
    {
      for (m = 0; m < dg; m++)
	if (T->cuts[chdrn[m]][comb[m]] == NULL)
	  break;
      if (m < dg)
	continue;
      for (m = 0; m < dg; m++)
	lgct[m] = 0;
      do
      {
	if (T->cuts[v][l] == NULL)
	{
	  omffcet = 1;
	  T->cuts[v][l] = ALLOC(int, 1 + l);
	  T->cuts[v][l][0] = 0;
	}
	else
	{
	  omffcet = 1 + (T->cuts[v][l][0]) * l;
	  T->cuts[v][l] = REALLOC(int, T->cuts[v][l], omffcet + l);
	}
	for (m = 0; m < dg; m++)
	{
	  w = lgct[m] * comb[m] + 1;
	  for (i = w; i < w + comb[m]; i++)
	    T->cuts[v][l][omffcet + i - w] = T->cuts[chdrn[m]][comb[m]][i];
	  omffcet += comb[m];
	}
	T->cuts[v][l][0]++;
	for (m = 0; m < dg; m++)
	{
	  if ((++lgct[m]) >= T->cuts[chdrn[m]][comb[m]][0])
	    lgct[m] = 0;
	  else
	    break;
	}
      } while (m < dg);
    } while (K_from_n_4_tree(comb, l, dg));
  }
  for (l = 0; l < dg; l++)
  {
    for (m = 1; m <= k; m++)
      if (T->cuts[chdrn[l]][m] != NULL)
      {
	FREE(T->cuts[chdrn[l]][m]);
	T->cuts[chdrn[l]][m] = NULL;
      }
    FREE(T->cuts[chdrn[l]]);
    T->cuts[chdrn[l]] = NULL;
  }
  FREE(lgct);
  FREE(chdrn);
  for (l = k; l > 0; l--)
    if (T->cuts[v][l] != NULL)
      break;
  return (l);
}

static void
mark_lut(node)
node_t *node;
{
  int i;
  node_t *t;

  foreach_fanin(node, i, t)
  {
    if (MarkedHIGH(t, LUTBDR) || MarkedLOW(t, MFFCLUT))
      continue;
    MarkLOW(t, MFFCLUT);
    mark_lut(t);
  }
}

static int
map4mffc(node, areaopt, k, threshold, nogen, mb)
node_t *node;
int areaopt, k, threshold, nogen, mb;
{
  int i, j, l, m, tm, tn, bcosta, bcostb, bcostd, bcut, bsize;
  int *lut, *lut0;
  node_t *t0, *t1;
  array_t *tfi;
  SPtree *T;
  lsGen gen;
  array_t *mffcb;

  tfi = network_tfi(node, MAX_LEVEL);
  for (i = 0; i < array_n(tfi); i++)
  {
    t0 = array_fetch(node_t *, tfi, i);
    foreach_fanin(t0, j, t1)
    {
      MarkLOW(t1, MFFCOUT);
      CNT(t1) = 0;
    }
    foreach_fanout(t0, gen, t1)
    {
      MarkLOW(t1, MFFCOUT);
      CNT(t1) = 0;
    }
    MarkLOW(t0, MFFCOUT);
    CNT(t0) = 0;
  }
  MarkLOW(node, MFFCIN);
  foreach_fanin(node, i, t0)
      MarkLOW(t0, MFFCBDR);
  for (i = array_n(tfi) - 1; i >= 0; i--)
  {
    t0 = array_fetch(node_t *, tfi, i);
    if (MarkedLOW(t0, MFFCOUT))
      continue;
    if (MarkedHIGH(t0, NETWKOUT))
      continue;
    if (t0->type == PRIMARY_INPUT)
      continue;
    j = 0;
    foreach_fanout(t0, gen, t1)
    {
      if (MarkedHIGH(t1, NETWKOUT))
	continue;
      if (!MarkedLOW(t1, MFFCIN))
      {
	j = 1;
	break;
      }
    }
    if (j)
      continue;
    MarkLOW(t0, MFFCIN);
    foreach_fanin(t0, j, t1)
	MarkLOW(t1, MFFCBDR);
  }
  Frontier(node) = array_alloc(node_t *, 0);
  for (i = array_n(tfi) - 1; i >= 0; i--)
  {
    t0 = array_fetch(node_t *, tfi, i);
    if (MarkedLOW(t0, MFFCBDR))
    {
      array_insert_last(node_t *, Frontier(node), t0);
    }
  }
  mffcb = array_alloc(node_t *, 0);
  for (i = 0; i < array_n(tfi); i++)
  {
    t0 = array_fetch(node_t *, tfi, i);
    if (MarkedLOW(t0, MFFCOUT))
      continue;
    array_insert_last(node_t *, mffcb, t0);
  }
  array_free(tfi);
  T = make_spanning_tree(node, mffcb, k);
  tm = (T->tree[1].mark > 0);
  if (tm)
    (void) gencut4tree(T, 1, k);
  else
    (void) gencut(T, 1, areaopt, k, mffcb, threshold, nogen, mb);
  bsize = 0;
  bcut = 0;
  bcosta = bcostb = bcostd = array_n(mffcb) + 1;
  for (i = 1; i <= k; i++)
  {
    if (T->cuts[1][i] == NULL)
      continue;
    for (j = 0; j < T->cuts[1][i][0]; j++)
    {
      for (l = 0; l < i; l++)
	MarkHIGH(T->tree[T->cuts[1][i][1 + j * i + l]].node, LUTROOT);
      if (MarkedHIGH(node, LUTROOT))
      {
	for (l = 0; l < i; l++)
	  ClearHIGH(T->tree[T->cuts[1][i][1 + j * i + l]].node, LUTROOT);
	continue;
      }
      tm = 1;
      tn = 0;
      for (l = array_n(mffcb) - 1; l >= 0; l--)
      {
	t0 = array_fetch(node_t *, mffcb, l);
	if (!MarkedHIGH(t0, LUTROOT))
	  continue;
	if (MarkedLOW(t0, MFFCBDR))
	  continue;
	tm += (int) array_fetch(int *, Cluster(t0), 0);
	for (m = array_n(Frontier(t0)) - 1; m >= 0; m--)
	{
	  t1 = array_fetch(node_t *, Frontier(t0), m);
	  MarkHIGH(t1, LUTROOT);
	}
      }
      for (l = 0; l < array_n(mffcb); l++)
      {
	t0 = array_fetch(node_t *, mffcb, l);
	Label(t0) = 0;
	if (!MarkedHIGH(t0, LUTROOT))
	  continue;
	ClearHIGH(t0, LUTROOT);
	if (MarkedLOW(t0, MFFCBDR))
	  continue;
	for (m = array_n(Frontier(t0)) - 1; m >= 0; m--)
	{
	  t1 = array_fetch(node_t *, Frontier(t0), m);
	  if (Label(t1) > Label(t0))
	    Label(t0) = Label(t1);
	}
	Label(t0) += (int) array_fetch(int *, Cluster(t0), 1);
	if (Label(t0) > tn)
	  tn = Label(t0);
      }
      tn++;
      m = ((areaopt) ? ((tm < bcosta) || (tm == bcosta && (mb ? (i < bsize) : (tn < bcostd))))
	   : ((tn < bcostd) || (tn == bcostd && (mb ? (i < bsize) : (tm < bcosta)))));
      if (m)
      {
	bcosta = tm;
	bcostd = tn;
	bcut = j;
	bsize = i;
      }
    }
  }
  if (bsize <= 0)
  {
    bsize = df_min_cut(node, mffcb, k, &bcosta, &bcostd);
    if (bsize <= 0)
    {
      fprintf(siserr, "Error: Cannot map %s.\n", node->name);
      free_spanning_tree(T, k);
      array_free(mffcb);
      return (-1);
    }
  }
  for (i = 0; i < bsize; i++)
    MarkHIGH(T->tree[T->cuts[1][bsize][1 + bcut * bsize + i]].node, LUTBDR);
  mark_lut(node);
  for (i = 0; i < bsize; i++)
    ClearHIGH(T->tree[T->cuts[1][bsize][1 + bcut * bsize + i]].node, LUTBDR);
  lut = ALLOC(int, 2);
  lut[0] = 1;
  lut[1] = Index(node);
  for (i = array_n(mffcb) - 1; i >= 0; i--)
  {
    t0 = array_fetch(node_t *, mffcb, i);
    if (!MarkedLOW(t0, MFFCLUT))
      continue;
    lut = REALLOC(int, lut, lut[0] + 2);
    lut[++lut[0]] = Index(t0);
    MarkLOW(t0, MFFCIN);
  }
  Cluster(node) = array_alloc(int *, 0);
  array_insert_last(int *, Cluster(node), (int *) bcosta);
  array_insert_last(int *, Cluster(node), (int *) bcostd);
  array_insert_last(int *, Cluster(node), lut);
  free_spanning_tree(T, k);
  array_free(mffcb);
  return ((int) array_fetch(int *, Cluster(node), 0));
}

int
df_map(network, areaopt, k, thrshd, nogen, mb, pk)
network_t **network;
int areaopt, k, thrshd, nogen, mb, pk;
{
  int *lut;
  int i, j, m;
  node_t *node, *root, *membr;
  flow_aux_t *info;
  array_t *nv;

  nv = network_dfs(*network);
  info = ALLOC(flow_aux_t, array_n(nv));
  for (i = 0; i < array_n(nv); i++)
  {
    node = array_fetch(node_t *, nv, i);
    m = (int) (node->undef1);
    node->undef1 = (char *) (info + i);
    Label(node) = 0;
    Index(node) = i;
    Mark(node) = 0;
    Cluster(node) = NULL;
    Frontier(node) = NULL;
    ResynCluster(node) = NULL;
    ResynFrontier(node) = NULL;
    Undef(node) = NULL;
    Old(node) = (char *) m;
  }
  for (i = 0; i < array_n(nv); i++)
  {
    node = array_fetch(node_t *, nv, i);
    if (node->type == PRIMARY_INPUT || node->type == PRIMARY_OUTPUT)
      continue;
    if (node_function(node) == NODE_0 || node_function(node) == NODE_1)
      continue;
    Label(node) = map4mffc(node, areaopt, k, thrshd, nogen, mb);
  }
  if (areaopt)
    dfmap_improve(nv, k, thrshd, nogen, pk);
  for (i = array_n(nv) - 1; i >= 0; i--)
  {
    node = array_fetch(node_t *, nv, i);
    if (Frontier(node) != NULL)
    {
      array_free(Frontier(node));
      Frontier(node) = NULL;
    }
    if (node->type == PRIMARY_INPUT || node->type == PRIMARY_OUTPUT)
      continue;
    if (node_function(node) == NODE_0 || node_function(node) == NODE_1)
      continue;
    if (node_num_fanout(node) <= 0)
    {
      node_replace(node, node_constant(0));
      if (Cluster(node) != NULL)
      {
	lut = array_fetch(int *, Cluster(node), 2);
	if (lut != NULL)
	{
	  FREE(lut);
	  lut = NULL;
	}
	array_free(Cluster(node));
	Cluster(node) = NULL;
      }
      continue;
    }
    lut = array_fetch(int *, Cluster(node), 2);
    root = array_fetch(node_t *, nv, lut[1]);
    for (m = 2; m <= lut[0]; m++)
    {
      membr = array_fetch(node_t *, nv, lut[m]);
      j = node_collapse(root, membr);
    }
    lut = array_fetch(int *, Cluster(node), 2);
    if (lut != NULL)
    {
      FREE(lut);
      lut = NULL;
    }
    array_free(Cluster(node));
    Cluster(node) = NULL;
  }
  flow_aux_free(nv, info, array_n(nv));
  network_sweep(*network);
  return (0);
}

static void
mark_ext_mffc(n)
node_t *n;
{
  int i;
  lsGen gen;
  node_t *t0, *t1;

  ClearHIGH(n, NETWKOUT);
  MarkHIGH(n, LUTCTNT);
  foreach_fanin(n, i, t0)
  {
    if (t0->type == PRIMARY_INPUT)
      continue;
    if (MarkedLOW(t0, LUTPKBDR))
    {
      ClearLOW(t0, LUTPKBDR);
      MarkHIGH(t0, NETWKOUT);
      continue;
    }
    if (MFFCout(t0) != NULL)
    {
      MarkHIGH(t0, NETWKOUT);
      continue;
    }
    if (MarkedHIGH(t0, LUTCTNT))
      continue;
    mark_ext_mffc(t0);
    foreach_fanout(t0, gen, t1)
	if (!MarkedHIGH(t1, LUTCTNT))
      MarkHIGH(t1, NETWKOUT);
  }
}

int
dfmap_improve(nv, k, thrshd, nogen, pk)
array_t *nv;
int k, thrshd, nogen, pk;
{
  int count = 0, cur, curv, i, j, m, num_po, tmpv, oldarea, newarea, *lut;
  node_t *n, *t0, *t1;
  lsGen gen;
  array_t *tmparray, *roots, *lut_bdr, *lut_mffcout, *lut_mffcfront, **mffc_nodes,
  **mffc_clusters, **mffc_frontiers;

  if (pk <= 1)
    return (0);
  roots = array_alloc(node_t *, 0);
  for (i = array_n(nv) - 1; i >= 0; i--)
  {
    n = array_fetch(node_t *, nv, i);
    ClearHIGH(n, LUTCTNT);
    ClearLOW(n, LUTPKBDR);
    if (n->type == PRIMARY_OUTPUT)
    {
      if (MFFCout(n->fanin[0]) == NULL)
      {
	array_insert_last(node_t *, roots, n->fanin[0]);
	MFFCout(n->fanin[0]) = array_alloc(node_t *, 0);
      }
      array_insert_last(node_t *, MFFCout(n->fanin[0]), n);
      MarkHIGH(n->fanin[0], ROOTIMPD);
      continue;
    }
    if (n->type == PRIMARY_INPUT)
      continue;
    if (MFFCout(n) == NULL)
      continue;
    for (j = array_n(Frontier(n)) - 1; j >= 0; j--)
    {
      t0 = array_fetch(node_t *, Frontier(n), j);
      if (t0->type == PRIMARY_INPUT)
	continue;
      if (MFFCout(t0) == NULL)
      {
	array_insert_last(node_t *, roots, t0);
	MFFCout(t0) = array_alloc(node_t *, 0);
      }
      array_insert_last(node_t *, MFFCout(t0), n);
    }
  }
  num_po = network_num_po(node_network(n));
  while (1)
  {
    cur = -1;
    curv = num_po * array_n(roots);
    for (i = 0; i < array_n(roots); i++)
    {
      n = array_fetch(node_t *, roots, i);
      if (MarkedHIGH(n, ROOTCKD) || MarkedHIGH(n, ROOTIMPD))
	continue;
      if (array_n(MFFCout(n)) > pk)
	continue;
      tmpv = 0;
      for (j = 0; j < array_n(MFFCout(n)); j++)
      {
	t0 = array_fetch(node_t *, MFFCout(n), j);
	if (MarkedHIGH(t0, ROOTIMPD))
	  tmpv += 1;
	else
	  tmpv += num_po;
      }
      if (tmpv < curv)
      {
	cur = i;
	curv = tmpv;
      }
    }
    if (cur == -1)
      break;
    n = array_fetch(node_t *, roots, cur);
    lut = array_fetch(int *, Cluster(n), 2);
    lut_bdr = array_alloc(node_t *, 0);
    for (i = lut[0]; i >= 1; i--)
    {
      t0 = array_fetch(node_t *, nv, lut[i]);
      MarkHIGH(t0, LUTCTNT);
      foreach_fanin(t0, j, t1)
	  if (!MarkedHIGH(t1, LUTCTNT))
	array_insert_last(node_t *, lut_bdr, t1);
    }
    for (i = lut[0]; i >= 1; i--)
    {
      t0 = array_fetch(node_t *, nv, lut[i]);
      ClearHIGH(t0, LUTCTNT);
    }
    lut_mffcfront = Frontier(n);
    Frontier(n) = NULL;
    lut_mffcout = MFFCout(n);
    MFFCout(n) = NULL;
    mffc_frontiers = ALLOC(array_t *, array_n(lut_mffcout));
    mffc_clusters = ALLOC(array_t *, array_n(lut_mffcout));
    mffc_nodes = ALLOC(array_t *, array_n(lut_mffcout));
    for (i = 0; i < array_n(lut_mffcout); i++)
    {
      t0 = array_fetch(node_t *, lut_mffcout, i);
      for (j = 0; j < array_n(lut_bdr); j++)
      {
	t1 = array_fetch(node_t *, lut_bdr, j);
	MarkLOW(t1, LUTPKBDR);
      }
      mark_ext_mffc(t0);
      mffc_nodes[i] = array_alloc(node_t *, 0);
      mffc_clusters[i] = array_alloc(array_t *, 0);
      mffc_frontiers[i] = array_alloc(array_t *, 0);
      oldarea = (int) array_fetch(int *, Cluster(t0), 0);
      ClearHIGH(t0, LUTCTNT);
      array_insert_last(node_t *, mffc_nodes[i], t0);
      array_insert_last(array_t *, mffc_clusters[i], Cluster(t0));
      array_insert_last(array_t *, mffc_frontiers[i], Frontier(t0));
      Cluster(t0) = NULL;
      Frontier(t0) = NULL;
      tmparray = network_tfi(t0, MAX_LEVEL);
      for (j = array_n(tmparray) - 1; j >= 0; j--)
      {
	t1 = array_fetch(node_t *, tmparray, j);
	if (MarkedHIGH(t1, LUTCTNT))
	{
	  ClearHIGH(t1, LUTCTNT);
	  array_insert_last(node_t *, mffc_nodes[i], t1);
	  array_insert_last(array_t *, mffc_clusters[i], Cluster(t1));
	  array_insert_last(array_t *, mffc_frontiers[i], Frontier(t1));
	  Cluster(t1) = NULL;
	  Frontier(t1) = NULL;
	}
      }
      array_free(tmparray);
      for (j = array_n(mffc_nodes[i]) - 1; j >= 0; j--)
	map4mffc(array_fetch(node_t *, mffc_nodes[i], j),
		 1, k, thrshd, nogen, 1);
      newarea = (int) array_fetch(int *, Cluster(t0), 0);
      for (j = array_n(mffc_nodes[i]) - 1; j >= 0; j--)
      {
	t0 = array_fetch(node_t *, mffc_nodes[i], j);
	foreach_fanin(t0, m, t1)
	    if (MarkedHIGH(t1, NETWKOUT))
	  ClearHIGH(t1, NETWKOUT);
	foreach_fanout(t0, gen, t1)
	    if (MarkedHIGH(t1, NETWKOUT))
	  ClearHIGH(t1, NETWKOUT);
      }
      if (newarea <= oldarea)
	continue;
      else
	break;
    }
    if (i >= array_n(lut_mffcout))
    {
      for (i = 0; i < array_n(lut_mffcout); i++)
      {
	t0 = array_fetch(node_t *, lut_mffcout, i);
	ClearHIGH(t0, ROOTCKD);
	for (j = 0; j < array_n(Frontier(t0)); j++)
	{
	  t1 = array_fetch(node_t *, Frontier(t0), j);
	  ClearHIGH(t1, ROOTCKD);
	}
      }
      array_delete(node_t *, roots, cur);
      for (i = 0; i < array_n(lut_mffcfront); i++)
      {
	t0 = array_fetch(node_t *, lut_mffcfront, i);
	if (t0->type == PRIMARY_INPUT)
	  continue;
	for (j = 0; j < array_n(MFFCout(t0)); j++)
	  if (array_fetch(node_t *, MFFCout(t0), j) == n)
	    break;
	array_delete(node_t *, MFFCout(t0), j);
	ClearHIGH(t0, ROOTCKD);
      }
      curv = array_n(roots);
      for (i = 0; i < array_n(lut_bdr); i++)
      {
	t0 = array_fetch(node_t *, lut_bdr, i);
	if (t0->type == PRIMARY_INPUT)
	  continue;
	if (MFFCout(t0) == NULL)
	{
	  ClearHIGH(t0, ROOTCKD);
	  array_insert_last(node_t *, roots, t0);
	  MFFCout(t0) = array_dup(lut_mffcout);
	}
	else
	{
	  tmpv = array_n(MFFCout(t0));
	  for (j = 0; j < array_n(lut_mffcout); j++)
	  {
	    t1 = array_fetch(node_t *, lut_mffcout, j);
	    for (m = 0; m < tmpv; m++)
	      if (array_fetch(node_t *, MFFCout(t0), m) == t1)
		break;
	    if (m < tmpv)
	      continue;
	    array_insert_last(node_t *, MFFCout(t0), t1);
	  }
	}
      }
      for (i = curv; i < array_n(roots); i++)
      {
	t0 = array_fetch(node_t *, roots, i);
	for (j = 0; j < array_n(Frontier(t0)); j++)
	{
	  t1 = array_fetch(node_t *, Frontier(t0), j);
	  if (t1->type == PRIMARY_INPUT)
	    continue;
	  if (MFFCout(t1) == NULL)
	  {
	    ClearHIGH(t1, ROOTCKD);
	    array_insert_last(node_t *, roots, t1);
	    MFFCout(t1) = array_alloc(node_t *, 1);
	    array_insert(node_t *, MFFCout(t1), 0, t0);
	  }
	  else
	    array_insert_last(node_t *, MFFCout(t1), t0);
	}
      }
      for (i = 0; i < array_n(lut_mffcout); i++)
      {
	array_free(mffc_nodes[i]);
	for (j = 0; j < array_n(mffc_clusters[i]); j++)
	{
	  tmparray = array_fetch(array_t *, mffc_clusters[i], j);
	  lut = array_fetch(int *, tmparray, 2);
	  if (lut != NULL)
	    FREE(lut);
	  array_free(tmparray);
	}
	array_free(mffc_clusters[i]);
	for (j = 0; j < array_n(mffc_frontiers[i]); j++)
	{
	  tmparray = array_fetch(array_t *, mffc_frontiers[i], j);
	  if (tmparray != NULL)
	    array_free(tmparray);
	}
	array_free(mffc_frontiers[i]);
      }
      FREE(mffc_nodes);
      FREE(mffc_clusters);
      FREE(mffc_frontiers);
      array_free(lut_bdr);
      array_free(lut_mffcfront);
      array_free(lut_mffcout);
    }
    else
    {
      array_free(lut_bdr);
      for (; i >= 0; i--)
      {
	for (j = 0; j < array_n(mffc_nodes[i]); j++)
	{
	  t0 = array_fetch(node_t *, mffc_nodes[i], j);
	  if (Cluster(t0) != NULL)
	    array_free(Cluster(t0));
	  Cluster(t0) = array_fetch(array_t *, mffc_clusters[i], j);
	  if (Frontier(t0) != NULL)
	    array_free(Frontier(t0));
	  Frontier(t0) = array_fetch(array_t *, mffc_frontiers[i], j);
	}
	array_free(mffc_nodes[i]);
	array_free(mffc_clusters[i]);
	array_free(mffc_frontiers[i]);
      }
      FREE(mffc_nodes);
      FREE(mffc_clusters);
      FREE(mffc_frontiers);
      MFFCout(n) = lut_mffcout;
      Frontier(n) = lut_mffcfront;
      MarkHIGH(n, ROOTCKD);
    }
  }
  for (i = 0; i < array_n(roots); i++)
  {
    n = array_fetch(node_t *, roots, i);
    if (MFFCout(n) != NULL)
    {
      array_free(MFFCout(n));
      MFFCout(n) = NULL;
    }
  }
  array_free(roots);
  return (count);
}