/*
 * classifier.{cc,h} -- element is a generic classifier
 * Eddie Kohler
 *
 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
 * Copyright (c) 2000 Mazu Networks, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "classifier.h"

//
// CLASSIFIER::EXPR OPERATIONS
//

bool
Classifier::Expr::implies(const Expr &e) const
  /* Returns true iff a packet that matches `*this' must match `e'. */
{
  if (!e.mask.u)
    return true;
  else if (e.offset != offset)
    return false;
  uint32_t both_mask = mask.u & e.mask.u;
  return both_mask == e.mask.u
    && (value.u & both_mask) == e.value.u;
}

bool
Classifier::Expr::not_implies(const Expr &e) const
  /* Returns true iff a packet that DOES NOT match `*this' must match `e'. */
  /* This happens when (1) 'e' matches everything, or (2) 'e' and '*this'
     both match against the same single bit, and they have different values. */
{
  if (!e.mask.u)
    return true;
  else if (e.offset != offset || (mask.u & (mask.u - 1)) != 0
	   || mask.u != e.mask.u || value.u == e.value.u)
    return false;
  else
    return true;
}

bool
Classifier::Expr::implies_not(const Expr &e) const
  /* Returns true iff a packet that matches `*this' CANNOT match `e'. */
{
  if (!e.mask.u || e.offset != offset)
    return false;
  uint32_t both_mask = mask.u & e.mask.u;
  return both_mask == e.mask.u
    && (value.u & both_mask) != (e.value.u & both_mask);
}

bool
Classifier::Expr::not_implies_not(const Expr &e) const
  /* Returns true iff a packet that DOES NOT match `*this' CANNOT match `e'. */
{
  if (!mask.u)
    return true;
  else if (e.offset != offset)
    return false;
  uint32_t both_mask = mask.u & e.mask.u;
  return both_mask == mask.u
    && (value.u & both_mask) == (e.value.u & both_mask);
}

bool
Classifier::Expr::compatible(const Expr &e) const
{
  if (!mask.u || !e.mask.u)
    return true;
  else if (e.offset != offset)
    return false;
  uint32_t both_mask = mask.u & e.mask.u;
  return (value.u & both_mask) == (e.value.u & both_mask);
}

bool
Classifier::Expr::flippable() const
{
  if (!mask.u)
    return false;
  else
    return ((mask.u & (mask.u - 1)) == 0);
}

void
Classifier::Expr::flip()
{
  assert(flippable());
  value.u ^= mask.u;
  int tmp = j[0];
  j[0] = j[1];
  j[1] = tmp;
}

std::string
Classifier::Expr::s() const
{
  std::string s;
  char buf[20];
  int offset = this->offset;

  sprintf(buf, "%3d/", offset);
  s = buf;
  for (int i = 0; i < 4; i++)
    sprintf(buf + 2*i, "%02x", value.c[i]);
  sprintf(buf + 8, "%%");
  for (int i = 0; i < 4; i++)
    sprintf(buf + 9 + 2*i, "%02x", mask.c[i]);
  s += buf;

  s += "  yes->";
  if (yes() <= 0)
      sprintf(buf, "[%d]   ", -yes());
  else
      sprintf(buf, "step %d", yes());
  s += buf;

  s += "  no->";
  if (no() <= 0)
      sprintf(buf, "[%d]", -no());
  else
      sprintf(buf, "step %d", no());
  s += buf;
 
  return s;
}

//
// CLASSIFIER ITSELF
//

Classifier::Classifier()
    : _output_everything(-1)
{
}

Classifier::~Classifier()
{
}

//
// COMPILATION
//

// DOMINATOR OPTIMIZER

/* Optimize Classifier decision trees by removing useless branches. If we have
   a path like:

   0: x>=5?  ---Y-->  1: y==2?  ---Y-->  2: x>=6?  ---Y-->  3: ...
       \
        --N-->...

   and every path to #1 leads from #0, then we can move #1's "Y" branch to
   point at state #3, since we know that the test at state #2 will always
   succeed.

   There's an obvious exponential-time algorithm to check this. Namely, given
   a state, enumerate all paths that could lead you to that state; then check
   the test against all tests on those paths. This terminates -- the
   classifier structure is a DAG -- but clearly in exptime.

   We reduce the algorithm to polynomial time by storing a bounded number of
   paths per state. For every state S, we maintain a set of up to
   MAX_DOMLIST==4 path subsets D1...D4, so *every* path to state S is a
   superset of at least one Di. (There is no requirement that S contains Di as
   a contiguous subpath. Rather, Di might leave out edges.) We can then shift
   edges as follows. Given an edge S.x-->T, check whether T is resolved (to
   the same answer) by every one of the path subsets D1...D4 corresponding to
   S. If so, then the edge S.x-->T is redundant; shift it to destination
   corresponding to the answer to T. (In the example above, we shift #1.Y to
   point to #3, since that is the destination of the #2.Y edge.)

   _dom holds all the Di sets for all states.
   _dom_start[k] says where, in _dom, a given Di begins.
   _domlist_start[S] says where, in _dom_start, the list of dominator sets
   for state S begins.
*/


Classifier::DominatorOptimizer::DominatorOptimizer(Classifier *c)
  : _c(c)
{
  _dom_start.push_back(0);
  _domlist_start.push_back(0);
}

inline Classifier::Expr &
Classifier::DominatorOptimizer::expr(int state) const
{
  return _c->_exprs[state];
}

inline int
Classifier::DominatorOptimizer::nexprs() const
{
  return _c->_exprs.size();
}

inline bool
Classifier::DominatorOptimizer::br_implies(int brno, int state) const
{
  assert(state > 0);
  if (br(brno))
    return expr(stateno(brno)).implies(expr(state));
  else
    return expr(stateno(brno)).not_implies(expr(state));
}

inline bool
Classifier::DominatorOptimizer::br_implies_not(int brno, int state) const
{
  assert(state > 0);
  if (br(brno))
    return expr(stateno(brno)).implies_not(expr(state));
  else
    return expr(stateno(brno)).not_implies_not(expr(state));
}

void
Classifier::DominatorOptimizer::find_predecessors(int state, Vector<int> &v) const
{
  for (int i = 0; i < state; i++) {
    Expr &e = expr(i);
    if (e.yes() == state)
      v.push_back(brno(i, true));
    if (e.no() == state)
      v.push_back(brno(i, false));
  }
}

void
Classifier::DominatorOptimizer::print()
{
  std::string s = _c->program_string();
  fprintf(stderr, "%s\n", s.c_str());
  for (Vector<int>::size_type i = 0; i < _domlist_start.size() - 1; i++) {
    if (_domlist_start[i] == _domlist_start[i+1])
      fprintf(stderr, "S-%zd   NO DOMINATORS\n", i);
    else {
      fprintf(stderr, "S-%zd : ", i);
      for (int j = _domlist_start[i]; j < _domlist_start[i+1]; j++) {
	if (j > _domlist_start[i])
	  fprintf(stderr, "    : ");
	for (int k = _dom_start[j]; k < _dom_start[j+1]; k++)
	  fprintf(stderr, " %d.%c", stateno(_dom[k]), br(_dom[k]) ? 'Y' : 'N');
	fprintf(stderr, "\n");
      }
    }
  }
}

void
Classifier::DominatorOptimizer::calculate_dom(int state)
{
  assert((int)_domlist_start.size() == state + 1);
  assert((int)_dom_start.size() - 1 == _domlist_start.back());
  assert((int)_dom.size() == _dom_start.back());
  
  // find predecessors
  Vector<int> predecessors;
  find_predecessors(state, predecessors);
  
  // if no predecessors, kill this expr
  if (predecessors.size() == 0) {
    if (state > 0)
	expr(state).j[0] = expr(state).j[1] = -_c->noutputs();
    else {
	assert(state == 0);
	_dom.push_back(brno(state, false));
	_dom_start.push_back(_dom.size());
    }
    _domlist_start.push_back(_dom_start.size() - 1);
    return;
  }

  // collect dominator lists from predecessors
  Vector<int> pdom, pdom_end;
  for (int i = 0; i < (int)predecessors.size(); i++) {
    int p = predecessors[i], s = stateno(p);
    
    // if both branches point at same place, remove predecessor state from
    // tree
    if (i > 0 && stateno(predecessors[i-1]) == s) {
      assert(i == (int)predecessors.size() - 1 || stateno(predecessors[i+1]) != s);
      assert(pdom_end.back() > pdom.back());
      assert(stateno(_dom[pdom_end.back() - 1]) == s);
      pdom_end.back()--;
      continue;
    }

    // append all dom lists to pdom and pdom_end; modify dom array to end with
    // branch 'p'
    for (int j = _domlist_start[s]; j < _domlist_start[s+1]; j++) {
      pdom.push_back(_dom_start[j]);
      pdom_end.push_back(_dom_start[j+1]);
      assert(stateno(_dom[pdom_end.back() - 1]) == s);
      _dom[pdom_end.back() - 1] = p;
    }
  }

  // We now have pdom and pdom_end arrays pointing at predecessors'
  // dominators.

  // If we have too many arrays, combine some of them.
  int pdom_pos = 0;
  if (pdom.size() > MAX_DOMLIST) {
    intersect_lists(_dom, pdom, pdom_end, 0, pdom.size(), _dom);
    _dom.push_back(brno(state, false));
    _dom_start.push_back(_dom.size());
    pdom_pos = pdom.size();	// skip loop
  }

  // Our dominators equal predecessors' dominators.
  for (vec_size_t p = pdom_pos; p < pdom.size(); p++) {
    for (int i = pdom[p]; i < pdom_end[p]; i++) {
      int x = _dom[i];
      _dom.push_back(x);
    }
    _dom.push_back(brno(state, false));
    _dom_start.push_back(_dom.size());
  }

  _domlist_start.push_back(_dom_start.size() - 1);
}


void
Classifier::DominatorOptimizer::intersect_lists(const Vector<int> &in, const Vector<int> &start, const Vector<int> &end, int pos1, int pos2, Vector<int> &out)
  /* Define subvectors V1...Vk as in[start[i] ... end[i]-1] for each pos1 <= i
     < pos2. This code places an intersection of V1...Vk in 'out'. */
{
  assert(pos1 <= pos2 && pos2 <= (int)start.size() && pos2 <= (int)end.size());
  if (pos1 == pos2)
    return;
  else if (pos2 - pos1 == 1) {
    for (int i = start[pos1]; i < end[pos1]; i++)
      out.push_back(in[i]);
  } else {
    Vector<int> pos(start);
    
    // Be careful about lists that end with something <= 0.
    int x = -1;			// 'x' describes the intersection path.
    
    while (1) {
      int p = pos1, k = 0;
      // Search for an 'x' that is on all of V1...Vk. We step through V1...Vk
      // in parallel, using the 'pos' array (initialized to 'start'). On
      // reaching the end of any of the arrays, exit.
      while (k < pos2 - pos1) {
	while (pos[p] < end[p] && in[pos[p]] < x)
	  pos[p]++;
	if (pos[p] >= end[p])
	  goto done;
	// Stepped past 'x'; current value is a new candidate
	if (in[pos[p]] > x)
	  x = in[pos[p]], k = 0;
	p++;
	if (p == pos2)
	  p = pos1;
	k++;
      }
      // Went through all of V1...Vk without changing x, so it's on all lists
      // (0 will definitely be the first such); add it to 'out' and step
      // through again
      out.push_back(x);
      x++;
    }
   done: ;
  }
}

int
Classifier::DominatorOptimizer::dom_shift_branch(int brno, int to_state, int dom, int dom_end, Vector<int> *collector)
{
  // shift the branch from `brno' to `to_state' as far down as you can, using
  // information from `brno's dominators
  assert(dom_end > dom && stateno(_dom[dom_end - 1]) == stateno(brno));
  _dom[dom_end - 1] = brno;
  if (collector)
    collector->push_back(to_state);

  while (to_state > 0) {
    for (int j = dom_end - 1; j >= dom; j--)
      if (br_implies(_dom[j], to_state)) {
	  to_state = expr(to_state).yes();
	  goto found;
      } else if (br_implies_not(_dom[j], to_state)) {
	  to_state = expr(to_state).no();
	  goto found;
      }
    // not found
    break;
   found:
    if (collector)
      collector->push_back(to_state);
  }

  return to_state;
}

int
Classifier::DominatorOptimizer::last_common_state_in_lists(const Vector<int> &in, const Vector<int> &start, const Vector<int> &end)
{
  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 < (int)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);
  int32_t &to_state = expr(s).j[br(brno)];
  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((int)_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 < (int)_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++)
	    for (int k = 0; k < 2; k++)
		if (_exprs[j].j[k] == i)
		    _exprs[j].j[k] = next;
	if (i == 0)
	    first = next;
      }
    }
  }
  if (_output_everything < 0 && first > 0)
    _exprs[0] = _exprs[first];

  // Remove unreachable states
  for (int i = 1; i < (int)_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 < (int)_exprs.size(); j++)
      _exprs[j-1] = _exprs[j];
    _exprs.pop_back();
    for (int j = 0; j < (int)_exprs.size(); j++)
	for (int k = 0; k < 2; k++)
	    if (_exprs[j].j[k] >= i)
		_exprs[j].j[k]--;
    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];
    for (int k = 0; k < 2; k++)
	if (e.j[k] > 0 && failure_states[e.j[k]] != FAILURE) {
	    e.j[k] = failure_states[e.j[k]];
	    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 < (int)_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::count_inbranches(Vector<int> &inbranch) const
{
    inbranch.assign(_exprs.size(), -1);
    for (int i = 0; i < (int)_exprs.size(); i++) {
	const Expr &e = _exprs[i];
	for (int k = 0; k < 2; k++)
	    if (e.j[k] > 0)
		inbranch[e.j[k]] = (inbranch[e.j[k]] >= 0 ? 0 : i);
    }
}

void
Classifier::bubble_sort_and_exprs(int sort_stopper)
{
    Vector<int> inbranch;
    count_inbranches(inbranch);
    
    // do bubblesort
    for (int i = 0; i < (int)_exprs.size(); i++) {
	Expr &e1 = _exprs[i];
	for (int k = 0; k < 2; k++)
	    if (e1.j[k] > 0) {
		int j = e1.j[k];
		Expr &e2 = _exprs[j];
		if (e1.j[!k] == e2.j[!k]
		    && (e1.offset > e2.offset
			|| (e1.offset == e2.offset && e1.mask.u > e2.mask.u))
		    && e1.offset < sort_stopper && inbranch[j] > 0) {
		    Expr temp(e2);
		    e2 = e1;
		    e2.j[k] = temp.j[k];
		    e1 = temp;
		    e1.j[k] = j;
		    // step backwards to continue the sort
		    i = (inbranch[i] > 0 ? inbranch[i] - 1 : i - 1);
		    break;
		}
	    }
    }
}

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

  // optimize using dominators
  {
    DominatorOptimizer dom(this);
    for (vec_size_t i = 0; i < _exprs.size(); i++)
      dom.run(i);
    //dom.print();
    combine_compatible_states();
    (void) remove_unused_states();
  }

  //{ String sxx = program_string(this, 0); click_chatter("%s", sxx.c_str()); }
  
  // 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();

  // 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 (vec_size_t i = 0; i < _exprs.size(); i++)
	for (int k = 0; k < 2; k++)
	    if (_exprs[i].j[k] <= 0)
		used_patterns[-_exprs[i].j[k]] = 1;
  for (int i = 0; i < noutputs(); i++)
    if (!used_patterns[i])
      errh->warning("pattern %d matches no packets", i);
}

//
// 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)
{
    if (_exprs.size() < 0x7FFF) {
	_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 <= (int)_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 <= (int)_exprs.size(); e++)
      tree[e] = -1;

    // loop over expressions
    int t;
    for (t = 0; t < (int)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 < (int)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 < (int)subtrees.size()) {
      assert(t == (int)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 (vec_size_t 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;
  }
}

void
Classifier::compress_exprs(Vector<uint32_t> &prog, bool perform_binary_search,
			   unsigned min_binary_search) const
{
    // Compress the program into "prog."

    // The compressed program groups related Exprs together and sorts large
    // sequences of common primitives ("port 80 or port 90 or port 92 or ..."),
    // allowing the use of binary search.

    // The compressed program is a sequence of tests.  Each test consists of
    // five or more 32-bit words, as follows.
    //
    // +--------+--------+--------+--------+--------+-------
    // |nval|off|   no   |   yes  |  mask  |  value | value...
    // +--------+--------+--------+--------+--------+-------
    // nval (16 bits)  - number of values in the test
    // off (16 bits)   - offset of word into the data packet
    // no (32 bits)    - jump if test fails
    // yes (32 bits)   - jump if test succeeds
    // mask (32 bits)  - masked with packet data before comparing with values
    // value (32 bits) - comparison data (nval values).  The values are sorted
    //                   in numerical order if 'nval >= MIN_BINARY_SEARCH.'
    //
    // The test succeeds if the 32 bits of packet data starting at 'off,'
    // bitwise anded with 'mask,' equal any one of the 'value's.  If a 'jump'
    // value is <= 0, it is the negative of the relevant IPFilter output port.
    // A positive 'jump' value equals the number of 32-bit words to move the
    // instruction pointer.

    assert(prog.size() == 0);

    Vector<int> wanted(_exprs.size() + 1, 0);
    wanted[0] = 1;
    for (vec_size_t i = 0; i < _exprs.size(); i++) {
	const Expr *ex = &_exprs[i];

	if (wanted[i])
	    for (int j = 0; j < 2; j++)
		if (ex->j[j] > 0)
		    wanted[ex->j[j]]++;
    }

    Vector<int> offsets;
    for (vec_size_t i = 0; i < _exprs.size(); i++) {
	int off = prog.size();
	offsets.push_back(off);
	if (wanted[i] == 0)
	    continue;
	assert(_exprs[i].offset >= 0);
	prog.push_back(_exprs[i].offset + 0x10000);
	prog.push_back(_exprs[i].no());
	prog.push_back(_exprs[i].yes());
	prog.push_back(_exprs[i].mask.u);
	prog.push_back(_exprs[i].value.u);
	int no;
	while ((no = (int32_t) prog[off+1]) > 0 && wanted[no] == 1
		&& _exprs[no].yes() == _exprs[i].yes()
		&& _exprs[no].offset == _exprs[i].offset
		&& _exprs[no].mask.u == _exprs[i].mask.u) {
	    prog[off] += 0x10000;
	    prog[off+1] = _exprs[no].no();
	    prog.push_back(_exprs[no].value.u);
	    wanted[no]--;
	}
#if NOT_YET
	if (perform_binary_search && (prog[off] >> 16) >= min_binary_search)
	    click_qsort(&prog[off+4], prog[off] >> 16);
#endif
    }
    offsets.push_back(prog.size());

    for (vec_size_t i = 0; i < _exprs.size(); i++)
	if ((vec_size_t)offsets[i] < prog.size() && offsets[i] < offsets[i+1]) {
	    int off = offsets[i];
	    if ((int32_t) prog[off+1] > 0)
		prog[off+1] = offsets[prog[off+1]] - off;
	    if ((int32_t) prog[off+2] > 0)
		prog[off+2] = offsets[prog[off+2]] - off;
	}
}

std::string Classifier::program_string(void)
{
    std::string s("");
    char buf[256];

    for (vec_size_t i = 0; i < _exprs.size(); i++) {
	sprintf(buf, "%4zd  ", i);
	s += buf;
	s += _exprs[i].s();
	s += '\n';
    }
    if (_exprs.size() == 0) {
	sprintf(buf, "all->[%d]\n", _output_everything);
	s += buf;
    }
    return s;
}

void Classifier::dump_program(FILE *out)
{
    fprintf(out, "classifier program:\n%s", program_string().c_str());
}

int Classifier::match(const OffloadReq &req) const
{
    if (_output_everything >= 0)
	return _output_everything;

    const uint32_t *p = (const uint32_t *)&req;
    const Expr *ex = &_exprs[0];	// avoid bounds checking
    int pos = 0;

    do {
	const Expr *curr = &ex[pos];
	uint32_t data = p[curr->offset] & curr->mask.u;
	pos = curr->j[data == curr->value.u];
    } while (pos > 0);

    return -pos;
}

#ifndef USE_STD_VECTOR
# include "vector.cc"
#endif