processingt.cc

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

	    continue;

	const PortT &hf = conn[c].from(), &ht = conn[c].to();
	int fp = output_pidx(hf), tp = input_pidx(ht);

	if ((_processing[end_from][fp] & ppush) && output_used[fp] >= 0) {
	    errh->lerror(conn[c].decorated_landmark(),
			 "illegal reuse of %<%s%> push output %d",
			 hf.element->name_c_str(), hf.port);
	    errh->lmessage(conn[output_used[fp]].decorated_landmark(),
			   "  %<%s%> output %d previously used here",
			   hf.element->name_c_str(), hf.port);
	    _processing[end_from][fp] |= perror;
	} else
	    output_used[fp] = c;

	if ((_processing[end_to][tp] & ppull) && input_used[tp] >= 0) {
	    errh->lerror(conn[c].decorated_landmark(),
			 "illegal reuse of %<%s%> pull input %d",
			 ht.element->name_c_str(), ht.port);
	    errh->lmessage(conn[input_used[tp]].decorated_landmark(),
			   "  %<%s%> input %d previously used here",
			   ht.element->name_c_str(), ht.port);
	    _processing[end_to][tp] |= perror;
	} else
	    input_used[tp] = c;
    }

    // Check for unused inputs and outputs.
    for (int ei = 0; ei < _router->nelements(); ei++) {
	const ElementT *e = _router->element(ei);
	if (e->dead())
	    continue;
	int ipdx = _pidx[end_to][ei], opdx = _pidx[end_from][ei];
	check_nports(e, input_used.begin() + ipdx, output_used.begin() + opdx, errh);
	for (int i = 0; i < e->ninputs(); i++)
	    if (input_used[ipdx + i] < 0) {
		errh->lerror(e->decorated_landmark(),
			     "%<%s%> %s input %d not connected",
			     e->name_c_str(), processing_name(_processing[end_to][ipdx + i]), i);
		_processing[end_to][ipdx + i] |= perror;
	    }
	for (int i = 0; i < e->noutputs(); i++)
	    if (output_used[opdx + i] < 0) {
		errh->lerror(e->decorated_landmark(),
			     "%<%s%> %s output %d not connected",
			     e->name_c_str(), processing_name(_processing[end_from][opdx + i]), i);
		_processing[end_from][opdx + i] |= perror;
	    }
    }
}

void
ProcessingT::resolve_agnostics()
{
    for (int p = 0; p < 2; ++p)
	for (int *it = _processing[p].begin(); it != _processing[p].end(); ++it)
	    if ((*it & 7) == pagnostic)
		*it += ppush;
}

bool
ProcessingT::same_processing(int a, int b) const
{
    // NB ppush != pagnostic+ppush; this is ok
    int ai = _pidx[end_to][a], bi = _pidx[end_to][b];
    int ao = _pidx[end_from][a], bo = _pidx[end_from][b];
    int ani = _pidx[end_to][a+1] - ai, bni = _pidx[end_to][b+1] - bi;
    int ano = _pidx[end_from][a+1] - ao, bno = _pidx[end_from][b+1] - bo;
    if (ani != bni || ano != bno)
	return false;
    if (ani && memcmp(&_processing[end_to][ai], &_processing[end_to][bi], sizeof(int) * ani) != 0)
	return false;
    if (ano && memcmp(&_processing[end_from][ao], &_processing[end_from][bo], sizeof(int) * ano) != 0)
	return false;
    return true;
}

String
ProcessingT::processing_code(const ElementT *e) const
{
    assert(e->router() == _router);
    int ei = e->eindex();
    StringAccum sa;
    for (int i = _pidx[end_to][ei]; i < _pidx[end_to][ei+1]; i++)
	sa << processing_letters[_processing[end_to][i] & 7];
    sa << '/';
    for (int i = _pidx[end_from][ei]; i < _pidx[end_from][ei+1]; i++)
	sa << processing_letters[_processing[end_from][i] & 7];
    return sa.take_string();
}

String
ProcessingT::decorated_processing_code(const ElementT *e) const
{
    assert(e->router() == _router);
    int ei = e->eindex();
    int ipb = _pidx[end_to][ei], ipe = _pidx[end_to][ei+1];
    int opb = _pidx[end_from][ei], ope = _pidx[end_from][ei+1];

    // avoid memory allocation by returning an existing string
    // (premature optimization?)
    int pin = (ipb == ipe ? ppush : _processing[end_to][ipb]);
    int pout = (opb == ope ? ppush : _processing[end_from][opb]);
    for (int i = ipb + 1; i < ipe; ++i)
	if (_processing[end_to][i] != pin)
	    goto create_code;
    for (int i = opb + 1; i < ope; ++i)
	if (_processing[end_from][i] != pout)
	    goto create_code;
    if ((pin & perror) == 0 && (pout & perror) == 0) {
	if (pin == ppush && pout == ppush)
	    return dpcode_push;
	else if (pin == ppull && pout == ppull)
	    return dpcode_pull;
	else if (pin == pagnostic && pout == pagnostic)
	    return dpcode_agnostic;
	else if (pin == ppush + pagnostic && pout == ppush + pagnostic)
	    return dpcode_apush;
	else if (pin == ppull + pagnostic && pout == ppull + pagnostic)
	    return dpcode_apull;
	else if (pin == ppush && pout == ppull)
	    return dpcode_push_to_pull;
    }

    // no optimization possible; just return the whole code
  create_code:
    StringAccum sa;
    for (const int *it = _processing[end_to].begin() + ipb;
	 it != _processing[end_to].begin() + ipe; ++it) {
	sa << decorated_processing_letters[*it & 7];
	if (*it & perror)
	    sa << '@';
    }
    sa << '/';
    for (const int *it = _processing[end_from].begin() + opb;
	 it != _processing[end_from].begin() + ope; ++it) {
	sa << decorated_processing_letters[*it & 7];
	if (*it & perror)
	    sa << '@';
    }
    return sa.take_string();
}

// FLOW CODES

static void
skip_flow_code(const char *&p, const char *last)
{
    if (p != last && *p != '/') {
	if (*p == '[') {
	    for (p++; p != last && *p != ']'; p++)
		/* nada */;
	    if (p != last)
		p++;
	} else
	    p++;
    }
}

static int
next_flow_code(const char *&p, const char *last,
	       int port, Bitvector &code, ErrorHandler *errh)
{
    if (p == last || *p == '/') {
	// back up to last code character
	if (p[-1] == ']') {
	    for (p -= 2; *p != '['; p--)
		/* nada */;
	} else
	    p--;
    }

    code.assign(256, false);

    if (*p == '[') {
	bool negated = false;
	if (p[1] == '^')
	    negated = true, p++;
	for (p++; p != last && *p != ']'; p++) {
	    // avoid isalpha() to avoid locale/"signed char" dependencies
	    if ((*p >= 'A' && *p <= 'Z') || (*p >= 'a' && *p <= 'z'))
		code[*p] = true;
	    else if (*p == '#')
		code[port + 128] = true;
	    else if (errh)
		errh->error("flow code: invalid character %<%c%>", *p);
	}
	if (negated)
	    code.negate();
	if (p == last) {
	    if (errh)
		errh->error("flow code: missing %<]%>");
	    p--;		// don't skip over final '\0'
	}
    } else if ((*p >= 'A' && *p <= 'Z') || (*p >= 'a' && *p <= 'z'))
	code[*p] = true;
    else if (*p == '#')
	code[port + 128] = true;
    else {
	if (errh)
	    errh->error("flow code: invalid character %<%c%>", *p);
	p++;
	return -1;
    }

    p++;
    return 0;
}

int
ProcessingT::code_flow(const String &flow_code, int port, bool isoutput,
		       Bitvector *bv, int size, ErrorHandler *errh)
{
    if (port < 0 || size == 0) {
	bv->assign(size, false);
	return 0;
    } else if (!flow_code || flow_code.equals("x/x", 3)) {
	bv->assign(size, true);
	return 0;
    } else
	bv->assign(size, false);

    const char *fbegin[2], *fend[2], *slash = find(flow_code, '/');
    fbegin[end_to] = flow_code.begin();
    if (slash == flow_code.end()) {
	fbegin[end_from] = fbegin[end_to];
	fend[end_to] = fend[end_from] = flow_code.end();
    } else if (slash + 1 == flow_code.end() || slash[1] == '/')
	return (errh ? errh->error("flow code: bad %</%>") : -1);
    else {
	fend[end_to] = slash;
	fbegin[end_from] = slash + 1;
	fend[end_from] = flow_code.end();
    }

    Bitvector source_code, sink_code;

    for (int i = 0; i < port; ++i)
	skip_flow_code(fbegin[isoutput], fend[isoutput]);
    next_flow_code(fbegin[isoutput], fend[isoutput], port, source_code, errh);

    for (int i = 0; i < size; i++) {
	next_flow_code(fbegin[!isoutput], fend[!isoutput], i, sink_code, errh);
	if (source_code.nonzero_intersection(sink_code))
	    (*bv)[i] = true;
    }

    return 0;
}

void
ProcessingT::debug_print_pidxes(const Bitvector &ports, bool isoutput,
				const String &prefix, ErrorHandler *debug_errh) const
{
    if (debug_errh) {
	assert(ports.size() == npidx(isoutput));
	StringAccum sa;
	for (int i = 0; i < npidx(isoutput); i++)
	    if (ports[i]) {
		if (sa)
		    sa << ' ';
		sa << port(i, isoutput).unparse(isoutput);
	    }
	if (prefix && !sa)
	    sa << "(none)";
	if (prefix)
	    debug_errh->message("%s%s", prefix.c_str(), sa.c_str());
	else if (sa)
	    debug_errh->message("%s", sa.c_str());
    }
}

void
ProcessingT::follow_connections(const Bitvector &source, bool source_isoutput,
				Bitvector &sink) const
{
    assert(source.size() == npidx(source_isoutput)
	   && sink.size() == npidx(!source_isoutput));
    for (RouterT::conn_iterator it = _router->begin_connections();
	 it != _router->end_connections(); ++it)
	if (source[pidx(*it, source_isoutput)])
	    sink[pidx(*it, !source_isoutput)] = true;
}

void
ProcessingT::follow_connections(const PortT &source, bool source_isoutput,
				Bitvector &sink) const
{
    assert(sink.size() == npidx(!source_isoutput));
    for (RouterT::conn_iterator it = _router->begin_connections_touching(source, source_isoutput);
	 it != _router->end_connections(); ++it)
	sink[pidx(*it, !source_isoutput)] = true;
}

void
ProcessingT::follow_flow(const Bitvector &source, bool source_isoutput,
			 Bitvector &sink, ErrorHandler *errh) const
{
    assert(source.size() == npidx(source_isoutput)
	   && sink.size() == npidx(!source_isoutput));
    Bitvector bv;
    // for speed with sparse Bitvectors, look into the Bitvector implementation
    const uint32_t *source_words = source.data_words();
    const int wb = Bitvector::data_word_bits;
    for (int w = 0; w <= source.max_word(); ++w)
	if (source_words[w]) {
	    int m = std::min(source.size(), (w + 1) * wb);
	    for (int pidx = w * wb; pidx < m; ++pidx)
		if (source[pidx]) {
		    PortT p = port(pidx, source_isoutput);
		    (void) port_flow(p, source_isoutput, &bv, errh);
		    sink.offset_or(bv, _pidx[!source_isoutput][p.eindex()]);
		}
	}
}

void
ProcessingT::follow_reachable(Bitvector &ports, bool isoutput, bool forward, ErrorHandler *errh, ErrorHandler *debug_errh) const
{
    assert(ports.size() == npidx(isoutput));
    Bitvector other_ports(npidx(!isoutput), false);
    Bitvector new_ports(npidx(isoutput), false);
    Bitvector diff(ports);
    for (int round = 0; true; ++round) {
	if (debug_errh) {
	    debug_print_pidxes(diff, isoutput, (round ? "round " + String(round) : "initial") + String(": "), debug_errh);
	    other_ports.assign(npidx(!isoutput), false);
	}
	if (isoutput != forward) {
	    follow_flow(diff, isoutput, other_ports, errh);
	    follow_connections(other_ports, !isoutput, new_ports);
	} else {
	    follow_connections(diff, isoutput, other_ports);
	    follow_flow(other_ports, !isoutput, new_ports, errh);
	}
	ports.or_with_difference(new_ports, diff);
	if (!diff)
	    return;
    }
}

String
ProcessingT::compound_port_count_code() const
{
    ElementT *input = _router->element("input");
    ElementT *output = _router->element("output");
    assert(input && output && input->tunnel() && output->tunnel());
    if (input->noutputs() == 0 && output->ninputs() == 0)
	return String::make_stable("0/0", 3);
    else
	return String(input->noutputs()) + "/" + String(output->ninputs());
}

String
ProcessingT::compound_processing_code() const
{
    assert(_elt[end_to].size());
    ElementT *input = _router->element("input");
    ElementT *output = _router->element("output");
    assert(input && output && input->tunnel() && output->tunnel());

    // read input and output codes
    StringAccum icode, ocode;
    for (int i = 0; i < input->noutputs(); i++) {
	int p = output_processing(PortT(input, i));
	icode << processing_letters[p];
    }
    for (int i = 0; i < output->ninputs(); i++) {
	int p = input_processing(PortT(output, i));
	ocode << processing_letters[p];
    }

    // streamline codes, ensure at least one character per half
    while (icode.length() > 1 && icode[icode.length() - 2] == icode.back())
	icode.pop_back();
    while (ocode.length() > 1 && ocode[ocode.length() - 2] == ocode.back())
	ocode.pop_back();
    if (!icode.length())
	icode << 'a';
    if (!ocode.length())
	ocode << 'a';

    icode << '/' << ocode;
    return icode.take_string();
}

String
ProcessingT::compound_flow_code(ErrorHandler *errh) const
{
    assert(_elt[end_to].size());
    ElementT *input = _router->element("input");
    ElementT *output = _router->element("output");
    assert(input && output && input->tunnel() && output->tunnel());

    // skip calculation in common case
    int ninputs = input->noutputs(), noutputs = output->ninputs();
    if (ninputs == 0 || noutputs == 0)
	return "x/y";

    // read flow codes, create 'codes' array
    Bitvector *codes = new Bitvector[noutputs];
    for (int i = 0; i < noutputs; i++)
	codes[i].assign(ninputs, false);
    Bitvector input_vec(ninput_pidx(), false);
    int opidx = input_pidx(PortT(output, 0));
    for (int i = 0; i < ninputs; i++) {
	if (i)
	    input_vec.clear();
	follow_connections(PortT(input, i), true, input_vec);
	follow_reachable(input_vec, false, true, errh);
	for (int p = 0; p < noutputs; p++)
	    if (input_vec[opidx + p])
		codes[p][i] = true;
    }

    // combine flow codes
    Vector<int> codeid;
    const char *cur_code = "xyzabcdefghijklmnopqrstuvwXYZABCDEFGHIJKLMNOPQRSTUVW0123456789_";
    codeid.push_back(*cur_code++);
    for (int i = 1; i < ninputs; i++) {

	// look for flow codes common among all outputs with this code, and
	// flow codes present in any output without this code
	Bitvector common(ninputs, true);
	Bitvector disjoint(ninputs, false);
	int found = 0;
	for (int j = 0; j < noutputs; j++)
	    if (codes[j][i]) {
		common &= codes[j];
		found++;
	    } else
		disjoint |= codes[j];
	disjoint.negate();

	common &= disjoint;
	for (int j = 0; j < i; j++)
	    if (common[j]) {
		codeid.push_back(codeid[j]);
		// turn off reference
		for (int k = 0; k < noutputs; k++)
		    codes[k][i] = false;
		goto found;
	    }
	assert(*cur_code);
	codeid.push_back(*cur_code++);

      found: ;
    }

    // generate flow code
    assert(*cur_code);
    StringAccum sa;
    for (int i = 0; i < ninputs; i++)
	sa << (char)codeid[i];
    sa << '/';
    for (int i = 0; i < noutputs; i++)
	if (!codes[i])
	    sa << *cur_code;
	else {
	    int pos = sa.length();
	    sa << '[';
	    for (int j = 0; j < ninputs; j++)
		if (codes[i][j])
		    sa << (char)codeid[j];
	    if (sa.length() == pos + 2) {
		sa[pos] = sa[pos + 1];
		sa.pop_back();
	    } else
		sa << ']';
	}

    // return
    delete[] codes;
    return sa.take_string();
}