classifier.cc

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

	i++;
	while (i < len && isspace(s[i]))
	  i++;
      }
      
      if (i >= len || !isdigit(s[i]))
	return errh->error("pattern %d: expected a digit", slot);

      // read offset
      int offset = 0;
      while (i < len && isdigit(s[i])) {
	offset *= 10;
	offset += s[i] - '0';
	i++;
      }
      
      if (i >= len || s[i] != '/')
	return errh->error("pattern %d: expected `/'", slot);
      i++;

      // scan past value
      int value_pos = i;
      while (i < len && (isxdigit(s[i]) || s[i] == '?'))
	i++;
      int value_end = i;

      // scan past mask
      int mask_pos = -1;
      int mask_end = -1;
      if (i < len && s[i] == '%') {
	i++;
	mask_pos = i;
	while (i < len && (isxdigit(s[i]) || s[i] == '?'))
	  i++;
	mask_end = i;
      }

      // check lengths
      if (value_end - value_pos < 2) {
	errh->error("pattern %d: value has less than 2 hex digits", slot);
	value_end = value_pos;
	mask_end = mask_pos;
      }
      if ((value_end - value_pos) % 2 != 0) {
	errh->error("pattern %d: value has odd number of hex digits", slot);
	value_end--;
	mask_end--;
      }
      if (mask_pos >= 0 && (mask_end - mask_pos) != (value_end - value_pos)) {
	bool too_many = (mask_end - mask_pos) > (value_end - value_pos);
	errh->error("pattern %d: mask has too %s hex digits", slot,
		    (too_many ? "many" : "few"));
	if (too_many)
	  mask_end = mask_pos + value_end - value_pos;
	else
	  value_end = value_pos + mask_end - mask_pos;
      }

      // add values to exprs
      bool first = true;
      offset += _align_offset;
      while (value_pos < value_end) {
	int v = 0, m = 0;
	update_value_mask(s[value_pos], 4, v, m);
	update_value_mask(s[value_pos+1], 0, v, m);
	value_pos += 2;
	if (mask_pos >= 0) {
	  int mv = 0, mm = 0;
	  update_value_mask(s[mask_pos], 4, mv, mm);
	  update_value_mask(s[mask_pos+1], 0, mv, mm);
	  mask_pos += 2;
	  m = m & mv & mm;
	}
	if (first || offset % 4 == 0) {
	  add_expr(tree, (offset / 4) * 4, 0, 0);
	  first = false;
	}
	_exprs.back().mask.c[offset % 4] = m;
	_exprs.back().value.c[offset % 4] = v & m;
	offset++;
      }

      // combine with "and"
      finish_expr_subtree(tree, C_AND);

      if (negated)
	negate_expr_subtree(tree);
    }

    // add fake expr if required
    if (_exprs.size() == slot_branch)
      add_expr(tree, 0, 0, 0);

    finish_expr_subtree(tree, C_AND, -slot);
  }

  finish_expr_subtree(tree, C_OR, -noutputs(), -noutputs());

  //{ String sxxx = program_string(this, 0); click_chatter("%s", sxxx.cc()); }
  optimize_exprs(errh);
  //{ String sxxx = program_string(this, 0); click_chatter("%s", sxxx.cc()); }
  return (errh->nerrors() == before ? 0 : -1);
}

String
Classifier::program_string(Element *element, void *)
{
  Classifier *c = (Classifier *)element;
  StringAccum sa;
  for (int i = 0; i < c->_exprs.size(); i++) {
    Expr e = c->_exprs[i];
    e.offset -= c->_align_offset;
    sa << (i < 10 ? " " : "") << i << ' ' << e << '\n';
  }
  if (c->_exprs.size() == 0)
    sa << "all->[" << c->_output_everything << "]\n";
  sa << "safe length " << c->_safe_length << "\n";
  sa << "alignment offset " << c->_align_offset << "\n";
  return sa.take_string();
}

void
Classifier::add_handlers()
{
  add_read_handler("program", Classifier::program_string, 0);
}

//
// RUNNING
//

void
Classifier::length_checked_push(Packet *p)
{
  const unsigned char *packet_data = p->data() - _align_offset;
  int packet_length = p->length() + _align_offset; // XXX >= MAXINT?
  Expr *ex = &_exprs[0];	// avoid bounds checking
  int pos = 0;
  
  do {
    if (ex[pos].offset+UBYTES > packet_length)
      goto check_length;
    
   length_ok:
    if ((*((uint32_t *)(packet_data + ex[pos].offset)) & ex[pos].mask.u)
	== ex[pos].value.u)
      pos = ex[pos].yes;
    else
      pos = ex[pos].no;
    continue;
    
   check_length:
    if (ex[pos].offset < packet_length) {
      unsigned available = packet_length - ex[pos].offset;
      if (!(ex[pos].mask.c[3]
	    || (ex[pos].mask.c[2] && available <= 2)
	    || (ex[pos].mask.c[1] && available == 1)))
	goto length_ok;
    }
    pos = ex[pos].no;
  } while (pos > 0);
  
  checked_output_push(-pos, p);
}

void
Classifier::push(int, Packet *p)
{
  const unsigned char *packet_data = p->data() - _align_offset;
  Expr *ex = &_exprs[0];	// avoid bounds checking
  int pos = 0;
  
  if (_output_everything >= 0) {
    // must use checked_output_push because the output number might be
    // out of range
    pos = -_output_everything;
    goto found;
  } else if (p->length() < _safe_length) {
    // common case never checks packet length
    length_checked_push(p);
    return;
  }
  
  do {
    if ((*((uint32_t *)(packet_data + ex[pos].offset)) & ex[pos].mask.u)
	== ex[pos].value.u)
      pos = ex[pos].yes;
    else
      pos = ex[pos].no;
  } while (pos > 0);
  
 found:
  checked_output_push(-pos, p);
}



#if 0
// optimization detritus

int
Classifier::check_path(const Vector<int> &path,
		       int ei, int interested, int eventual,
		       bool first, bool yet) const
{
  if (ei > interested && ei != eventual && !yet)
    return FAILURE;
  if (ei < 0 || (ei == 0 && !first))
    return (!yet ? FAILURE : ei);

  const Expr &e = _exprs[ei];
  Vector<int> new_path(path);
  new_path.push_back(ei);
  
  int yes_answer = 0;
  for (int i = 0; i < new_path.size() - 1 && !yes_answer; i++) {
    const Expr &old = _exprs[new_path[i]];
    bool yes = (old.yes == new_path[i+1]);
    if ((yes && old.implies_not(e)) || (!yes && old.not_implies_not(e)))
      yes_answer = FAILURE;
  }
  if (!yes_answer)
    yes_answer = check_path(new_path, e.yes, interested, eventual, false,
			    yet || (ei == interested && e.yes == eventual));
  
  int no_answer = 0;
  for (int i = 0; i < new_path.size() - 1 && !no_answer; i++) {
    const Expr &old = _exprs[new_path[i]];
    bool yes = (old.yes == new_path[i+1]);
    if ((yes && old.implies(e)) || (!yes && old.not_implies(e)))
      no_answer = FAILURE;
  }
  if (!no_answer)
    no_answer = check_path(new_path, e.no, interested, eventual, false,
			   yet || (ei == interested && e.no == eventual));

  //fprintf(stderr, "      ");
  //for (int i=0; i<new_path.size(); i++) fprintf(stderr, " %d", new_path[i]);
  //fprintf(stderr, "%s -> [%d, %d]\n", (yet?"*":""), yes_answer, no_answer);
  
  if (ei == interested)
    return (e.yes == eventual ? yes_answer : no_answer);
  else if (yes_answer != FAILURE && no_answer != FAILURE && yes_answer != no_answer)
    return (ei > eventual ? ei : eventual);
  else
    return (yes_answer != FAILURE ? yes_answer : no_answer);
}

int
Classifier::count_occurrences(const Expr &what, int state, bool first) const
{
  if (state < 0 || (state == 0 && !first))
    return 0;
  const Expr &e = _exprs[state];
  int nyes = count_occurrences(what, e.yes, false);
  int nno = count_occurrences(what, e.no, false);
  return (nyes > nno ? nyes : nno) + (what.implies(e) ? 1 : 0);
}

bool
Classifier::remove_duplicate_states()
{
  // look for duplicate states
  Vector<int> init_duplicates;
  for (int i = 0; i < _exprs.size(); i++) {
    const Expr &e = _exprs[i];
    int dupcount = 0;
    for (int j = i + 1; j < _exprs.size(); j++)
      if (e.implies(_exprs[j]))
	dupcount++;
    if (dupcount)
      init_duplicates.push_back(i);
  }

  // check for real duplicates
  Vector<int> duplicates;
  for (int i = 0; i < init_duplicates.size(); i++)
    if (count_occurrences(_exprs[init_duplicates[i]], 0, true) > 1)
      duplicates.push_back(init_duplicates[i]);
  
  if (!duplicates.size())
    return false;
  
  // expand first duplicate
  int splitter = duplicates[0];
  Expr &splite = _exprs[splitter];
  assert(splite.no > 0 && splite.yes > 0);
  //click_chatter("%s", program_string(this, 0).cc());
  //click_chatter("******** %s", splite.s().cc());
  int orig_nexprs = _exprs.size();
  int orig_no_branch = splite.no;
  splite.no = orig_nexprs;
  for (int i = orig_no_branch; i < orig_nexprs; i++) {
    Expr e = _exprs[i];
    if (e.yes > 0) e.yes += orig_nexprs - orig_no_branch;
    if (e.no > 0) e.no += orig_nexprs - orig_no_branch;
    _exprs.push_back(e);
  }
  click_chatter("%s", program_string(this, 0).cc());
  return true;
}

void
Classifier::unaligned_optimize()
{
  // A simple optimization to catch the common case that two adjacent
  // expressions have one of the forms:
  //   OFF/??XXXXXX    OFF/????XXXX    OFF/??????XX
  // OFF+4/XX??????  OFF+4/XXXX????  OFF+4/XXXXXX??
  // Change this into a single expression like:
  // OFF+1/XXXXXXXX  OFF+2/XXXXXXXX  OFF+3/XXXXXXXX
  // It's a pretty weak optimization, but often effective.
  for (int i = 0; i < _exprs.size() - 1; i++) {
    if (_exprs[i].yes != i+1 || _exprs[i].no != _exprs[i+1].no
	|| _exprs[i].offset + UBYTES != _exprs[i+1].offset)
      continue;
    
    // check to see that masks don't conflict
    int shift = 0;
    while (!_exprs[i].mask.c[shift])
      shift++;
    if (shift == 0)
      continue;
    for (int j = shift; j < 4; j++)
      if (_exprs[i+1].mask.c[j])
	goto done;
    
    // combine expressions
    _exprs[i].offset += shift;
    for (int j = 0; j < 4-shift; j++) {
      _exprs[i].mask.c[j] = _exprs[i].mask.c[j+shift];
      _exprs[i].value.c[j] = _exprs[i].value.c[j+shift];
    }
    for (int j = 4-shift; j < 4; j++) {
      _exprs[i].mask.c[j] = _exprs[i+1].mask.c[j-4+shift];
      _exprs[i].value.c[j] = _exprs[i+1].value.c[j-4+shift];
    }
    _exprs[i].yes = _exprs[i+1].yes;
    
   done: ;
  }
}

#endif
#if 0
#define CLASSIFIER_ITERATIVE 1

#if CLASSIFIER_ITERATIVE

#define BEFORE_YES		0x00000000
#define BEFORE_NO		0x00000001
#define BEFORE_COMBINE		0x00000002
#define STATE_FLAG		0x00000003
#define SET_STATE(x, s)		((x) = ((x) & ~STATE_FLAG) | (s))
#define YET_FLAG		0x00000004
#define YES_OK_FLAG		0x00000008
#define YES_OUTPUT(s)		((s >> 8)  & 0x00000FFF)
#define NO_OUTPUT(s)		((s >> 20) & 0x00000FFF)
#define MK_YES_OUTPUT(i)	((i << 8)  & 0x000FFF00)
#define MK_NO_OUTPUT(i)		((i << 20) & 0xFFF00000)

static void
common_paths(Vector<int> &output, int yes_pos, int no_pos)
{
  assert(yes_pos <= no_pos && no_pos <= output.size());
  Vector<int> result;
  
  int yi = yes_pos, ni = no_pos;
  while (yi < no_pos && ni < output.size()) {
    if (output[yi] == output[ni]) {
      result.push_back(output[ni]);
      yi++;
      ni++;
    }
    // cast to unsigned so that outputs and FAILURE are bigger than
    // internal nodes
    while (yi < no_pos && ni < output.size() && (unsigned)output[yi] < (unsigned)output[ni])
      yi++;
    while (yi < no_pos && ni < output.size() && (unsigned)output[yi] > (unsigned)output[ni])
      ni++;
  }

  if (result.size())
    memcpy(&output[yes_pos], &result[0], sizeof(int) * result.size());
  output.resize(yes_pos + result.size());
}

static void
move_path(Vector<int> &output, int to_pos, int start_pos, int end_pos)
{
  assert(to_pos <= start_pos && start_pos <= end_pos && end_pos <= output.size());
  if (to_pos == start_pos)
    output.resize(end_pos);
  else {
    int len = end_pos - start_pos;
    if (len)
      memmove(&output[to_pos], &output[start_pos], sizeof(int) * len);
    output.resize(to_pos + len);
  }
}

/* The recursive check_path function below is easier to understand than this,
 * but unfortunately, it seems to cause kernel crashes b/c of stack overflows.
 * (Deep recursion.) This iterative version, based on the recursive version,
 * should avoid such problems.
 *
 * The iterative transformation is pretty conventional. To transofrm a
 * recursive function to iterative version, you explicitly store the required
 * persistent state from each activation record.
 *
 * The check_path function walks over a path through the _exprs array. Since
 * _exprs is noncircular -- every branch points forward (or to an output) --
 * each path has a maximum length: _exprs.size() + 1. Since only one path is
 * active at a time, the recursion has a maximum depth of _exprs.size(), and
 * we can reserve _exprs.size() state words.
 *
 * What state do we need to keep? The list of current activations, obviously.
 * And for each activation, the state it is in; whether 'yet' is true; whether
 * the recursive call for the 'yes' branch succeeded; and the 'yes_output' and
 * 'no_output' arrays. We store them as follows:
 *
 * - List of prior activations: Each activation corresponds to a single
 *   expression number. Expression numbers are stored in 'path'. When 'path'
 *   is empty the recursion is done. Making a recursive call == adding an
 *   expr# to the end of 'path'. Returning from an activation == removing the