classifier.cc

COPE the first practical network coding scheme which is developped on click

  assert(start.size() == end.size() && start.size() > 1);
  if (in[end[0] - 1] <= 0) {
    int s = in[end[0] - 1];
    for (int j = 1; j < start.size(); j++)
      if (in[end[j] - 1] != s)
	goto not_end;
    return s;
  }
 not_end:
  Vector<int> intersection;
  intersect_lists(in, start, end, 0, start.size(), intersection);
  return intersection.back();
}

void
Classifier::DominatorOptimizer::shift_branch(int brno)
{
  // shift a branch by examining its dominators
  
  int s = stateno(brno);
  int &to_state = (br(brno) ? expr(s).yes : expr(s).no);
  if (to_state <= 0)
    return;

  if (_domlist_start[s] + 1 == _domlist_start[s+1]) {
    // single domlist; faster algorithm
    int d = _domlist_start[s];
    to_state = dom_shift_branch(brno, to_state, _dom_start[d], _dom_start[d+1], 0);
  } else {
    Vector<int> vals, start, end;
    for (int d = _domlist_start[s]; d < _domlist_start[s+1]; d++) {
      start.push_back(vals.size());
      (void) dom_shift_branch(brno, to_state, _dom_start[d], _dom_start[d+1], &vals);
      end.push_back(vals.size());
    }
    to_state = last_common_state_in_lists(vals, start, end);
  }
}

void
Classifier::DominatorOptimizer::run(int state)
{
  assert(_domlist_start.size() == state + 1);
  calculate_dom(state);
  shift_branch(brno(state, true));
  shift_branch(brno(state, false));
}


// OPTIMIZATION

bool
Classifier::remove_unused_states()
{
  // Remove uninteresting exprs
  int first = 0;
  for (int i = 0; _output_everything < 0 && i < _exprs.size(); i++) {
    Expr &e = _exprs[i];
    int next = e.yes;
    if (e.yes == e.no || e.mask.u == 0) {
      if (i == first && next <= 0)
	_output_everything = e.yes;
      else {
	for (int j = 0; j < i; j++) {
	  Expr &ee = _exprs[j];
	  if (ee.yes == i) ee.yes = next;
	  if (ee.no == i) ee.no = next;
	}
	if (i == 0) first = next;
      }
    }
  }
  if (_output_everything < 0 && first > 0)
    _exprs[0] = _exprs[first];

  // Remove unreachable states
  for (int i = 1; i < _exprs.size(); i++) {
    for (int j = 0; j < i; j++)	// all branches are forward
      if (_exprs[j].yes == i || _exprs[j].no == i)
	goto done;
    // if we get here, the state is unused
    for (int j = i+1; j < _exprs.size(); j++)
      _exprs[j-1] = _exprs[j];
    _exprs.pop_back();
    for (int j = 0; j < _exprs.size(); j++) {
      if (_exprs[j].yes >= i) _exprs[j].yes--;
      if (_exprs[j].no >= i) _exprs[j].no--;
    }
    i--;			// shifted downward, so must reconsider `i'
   done: ;
  }

  // Get rid of bad branches
  Vector<int> failure_states(_exprs.size(), FAILURE);
  bool changed = false;
  for (int i = _exprs.size() - 1; i >= 0; i--) {
    Expr &e = _exprs[i];
    if (e.yes > 0 && failure_states[e.yes] != FAILURE) {
      e.yes = failure_states[e.yes];
      changed = true;
    }
    if (e.no > 0 && failure_states[e.no] != FAILURE) {
      e.no = failure_states[e.no];
      changed = true;
    }
    if (e.yes == FAILURE)
      failure_states[i] = e.no;
    else if (e.no == FAILURE)
      failure_states[i] = e.yes;
  }
  return changed;
}

void
Classifier::combine_compatible_states()
{
  for (int i = 0; i < _exprs.size(); i++) {
    Expr &e = _exprs[i];
    if (e.no > 0 && _exprs[e.no].compatible(e) && e.flippable())
      e.flip();
    if (e.yes <= 0)
      continue;
    Expr &ee = _exprs[e.yes];
    if (e.no == ee.yes && ee.flippable())
      ee.flip();
    if (e.no == ee.no && ee.compatible(e)) {
      e.yes = ee.yes;
      if (!e.mask.u)		// but probably ee.mask.u is always != 0...
	e.offset = ee.offset;
      e.value.u = (e.value.u & e.mask.u) | (ee.value.u & ee.mask.u);
      e.mask.u |= ee.mask.u;
      i--;
    }
  }
}

void
Classifier::bubble_sort_and_exprs(int sort_stopper)
{
  // count inbranches
  Vector<int> inbranch(_exprs.size(), -1);
  for (int i = 0; i < _exprs.size(); i++) {
    Expr &e = _exprs[i];
    if (e.yes > 0)
      inbranch[e.yes] = (inbranch[e.yes] >= 0 ? 0 : i);
    if (e.no > 0)
      inbranch[e.no] = (inbranch[e.no] >= 0 ? 0 : i);
  }

  // do bubblesort
  for (int i = 0; i < _exprs.size(); i++)
    if (_exprs[i].yes > 0) {
      int j = _exprs[i].yes;
      Expr &e1 = _exprs[i], &e2 = _exprs[j];
      if (e1.no == e2.no && e1.offset > e2.offset && e1.offset < sort_stopper
	  && inbranch[j] > 0) {
	Expr temp(e2);
	e2 = e1;
	e2.yes = temp.yes;
	e1 = temp;
	e1.yes = j;
	// step backwards to continue the sort
	i = (inbranch[i] > 0 ? inbranch[i] - 1 : i - 1);
      }
    }
}

void
Classifier::optimize_exprs(ErrorHandler *errh, int sort_stopper)
{
  // sort 'and' expressions
  bubble_sort_and_exprs(sort_stopper);
  
  //{ String sxxx = program_string(this, 0); click_chatter("%s", sxxx.cc()); }

  // optimize using dominators
  {
    DominatorOptimizer dom(this);
    for (int i = 0; i < _exprs.size(); i++)
      dom.run(i);
    //dom.print();
    combine_compatible_states();
    (void) remove_unused_states();
  }
  
  //{ String sxxx = program_string(this, 0); click_chatter("%s", sxxx.cc()); }
  
  // Check for case where all patterns have conflicts: _exprs will be empty
  // but _output_everything will still be < 0. We require that, when _exprs
  // is empty, _output_everything is >= 0.
  if (_exprs.size() == 0 && _output_everything < 0)
    _output_everything = noutputs();
  else if (_output_everything >= 0)
    _exprs.clear();

  // Calculate _safe_length
  _safe_length = 0;
  for (int i = 0; i < _exprs.size(); i++) {
    unsigned off = _exprs[i].offset + UBYTES;
    for (int j = 3; j >= 0; j--, off--)
      if (_exprs[i].mask.c[j])
	break;
    if (off > _safe_length)
      _safe_length = off;
  }
  _safe_length -= _align_offset;

  // Warn on patterns that can't match anything
  Vector<int> used_patterns(noutputs() + 1, 0);
  if (_output_everything >= 0)
    used_patterns[_output_everything] = 1;
  else
    for (int i = 0; i < _exprs.size(); i++) {
      if (_exprs[i].yes <= 0) used_patterns[-_exprs[i].yes] = 1;
      if (_exprs[i].no <= 0) used_patterns[-_exprs[i].no] = 1;
    }
  for (int i = 0; i < noutputs(); i++)
    if (!used_patterns[i])
      errh->warning("pattern %d matches no packets", i);

  //{ String sxxx = program_string(this, 0); click_chatter("%s", sxxx.cc()); }
}

//
// CONFIGURATION
//

void
Classifier::init_expr_subtree(Vector<int> &tree)
{
  assert(!tree.size());
  tree.push_back(0);
}

void
Classifier::add_expr(Vector<int> &tree, const Expr &e)
{
  _exprs.push_back(e);
  Expr &ee = _exprs.back();
  ee.yes = SUCCESS;
  ee.no = FAILURE;
  int level = tree[0];
  tree.push_back(level);
}

void
Classifier::add_expr(Vector<int> &tree, int offset, uint32_t value, uint32_t mask)
{
  Expr e;
  e.offset = offset;
  e.value.u = value & mask;
  e.mask.u = mask;
  add_expr(tree, e);
}

void
Classifier::start_expr_subtree(Vector<int> &tree)
{
  tree[0]++;
}

void
Classifier::redirect_expr_subtree(int first, int last, int success, int failure)
{
  for (int i = first; i < last; i++) {
    Expr &e = _exprs[i];
    if (e.yes == SUCCESS)
      e.yes = success;
    else if (e.yes == FAILURE)
      e.yes = failure;
    if (e.no == SUCCESS)
      e.no = success;
    else if (e.no == FAILURE)
      e.no = failure;
  }
}

void
Classifier::finish_expr_subtree(Vector<int> &tree, Combiner combiner,
				int success, int failure)
{
  int level = tree[0];

  // 'subtrees' contains pointers to trees at level 'level'
  Vector<int> subtrees;
  {
    // move backward to parent subtree
    int ptr = _exprs.size();
    while (ptr > 0 && (tree[ptr] < 0 || tree[ptr] >= level))
      ptr--;
    // collect child subtrees
    for (ptr++; ptr <= _exprs.size(); ptr++)
      if (tree[ptr] == level)
	subtrees.push_back(ptr - 1);
  }

  if (subtrees.size()) {

    // combine subtrees

    // first mark all subtrees as next higher level
    tree[subtrees[0] + 1] = level - 1;
    for (int e = subtrees[0] + 2; e <= _exprs.size(); e++)
      tree[e] = -1;

    // loop over expressions
    int t;
    for (t = 0; t < subtrees.size() - 1; t++) {
      int first = subtrees[t];
      int next = subtrees[t+1];

      if (combiner == C_AND)
	redirect_expr_subtree(first, next, next, failure);
      else if (combiner == C_OR)
	redirect_expr_subtree(first, next, success, next);
      else if (combiner == C_TERNARY) {
	if (t < subtrees.size() - 2) {
	  int next2 = subtrees[t+2];
	  redirect_expr_subtree(first, next, next, next2);
	  redirect_expr_subtree(next, next2, success, failure);
	  t++;
	} else			// like C_AND
	  redirect_expr_subtree(first, next, next, failure);
      } else
	redirect_expr_subtree(first, next, success, failure);
    }

    if (t < subtrees.size()) {
      assert(t == subtrees.size() - 1);
      redirect_expr_subtree(subtrees[t], _exprs.size(), success, failure);
    }
  }

  tree[0]--;
}

void
Classifier::negate_expr_subtree(Vector<int> &tree)
{
  // swap 'SUCCESS' and 'FAILURE' within the last subtree
  int level = tree[0];
  int first = _exprs.size() - 1;
  while (first >= 0 && tree[first+1] != level)
    first--;

  for (int i = first; i < _exprs.size(); i++) {
    Expr &e = _exprs[i];
    if (e.yes == FAILURE)
      e.yes = SUCCESS;
    else if (e.yes == SUCCESS)
      e.yes = FAILURE;
    if (e.no == FAILURE)
      e.no = SUCCESS;
    else if (e.no == SUCCESS)
      e.no = FAILURE;
  }
}

static void
update_value_mask(int c, int shift, int &value, int &mask)
{
  int v = 0, m = 0xF;
  if (c == '?')
    v = m = 0;
  else if (c >= '0' && c <= '9')
    v = c - '0';
  else if (c >= 'A' && c <= 'F')
    v = c - 'A' + 10;
  else if (c >= 'a' && c <= 'f')
    v = c - 'a' + 10;
  value |= (v << shift);
  mask |= (m << shift);
}

int
Classifier::configure(Vector<String> &conf, ErrorHandler *errh)
{
  set_noutputs(conf.size());
  
  int before = errh->nerrors();

  // set align offset
  {
    int c, o;
    if (AlignmentInfo::query(this, 0, c, o) && c >= 4)
      // want `data - _align_offset' aligned at 4/(o%4)
      _align_offset = (4 - (o % 4)) % 4;
    else {
#ifndef __i386__
      errh->error("no AlignmentInfo available: you may experience unaligned accesses");
#endif
      _align_offset = 0;
    }
  }
  
  Vector<int> tree;
  init_expr_subtree(tree);
  start_expr_subtree(tree);
  
  for (int slot = 0; slot < conf.size(); slot++) {
    int i = 0;
    int len = conf[slot].length();
    const char *s = conf[slot].data();

    int slot_branch = _exprs.size();
    Vector<Expr> slot_exprs;

    start_expr_subtree(tree);

    if (s[0] == '-' && len == 1)
      // slot accepting everything
      i = 1;
    
    while (i < len) {
      
      while (i < len && isspace(s[i]))
	i++;
      if (i >= len) break;

      start_expr_subtree(tree);
      
      // negated?
      bool negated = false;
      if (s[i] == '!') {
	negated = true;