/*
 *   This library is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU Lesser General Public
 *   License as published by the Free Software Foundation; either
 *   version 2.1 of the License, or (at your option) any later version.
 *
 *   This library is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *   Lesser General Public License for more details.
 *
 *   You should have received a copy of the GNU Lesser General Public
 *   License along with this library; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */

/** Functions to manipulate DNS labels
 *
 * @file src/lib/util/dns.c
 *
 * @copyright 2019 The FreeRADIUS server project
 * @copyright 2019 Network RADIUS SAS (legal@networkradius.com)
 */
RCSID("$Id: 8138fc337defc4e396d92e52302e38bc0325225e $")

#include <freeradius-devel/util/misc.h>
#include <freeradius-devel/util/strerror.h>
#include <freeradius-devel/util/value.h>
#include <freeradius-devel/util/dns.h>
#include <freeradius-devel/util/proto.h>

#define MAX_OFFSET (1 << 14)

static int dns_label_add(fr_dns_labels_t *lb, uint8_t const *start, uint8_t const *end)
{
	size_t offset, size = end - start;
	fr_dns_block_t *block;

	/*
	 *	If we don't care about tracking the blocks, then don't
	 *	do anything.
	 */
	if (!lb) return 0;

	fr_assert(start >= lb->start);
	fr_assert(end >= start);

	offset = start - lb->start;

	/*
	 *	DNS packets can be up to 64K in size, but the
	 *	compressed pointers can only be up to 2^14 in size.
	 *	So we just ignore offsets which are greater than 2^14.
	 */
	if ((offset + size) >= MAX_OFFSET) return 0;

	/*
	 *	We're not tracking labels, so don't do anything.
	 */
	if (lb->max == 1) return 0;

	FR_PROTO_TRACE("adding label at offset %zu", offset);

	/*
	 *	We add blocks append-only.  No adding new blocks in
	 *	the middle of a packet.
	 */
	block = &lb->blocks[lb->num - 1];
	fr_assert(block->start <= offset);
	fr_assert(offset);

	FR_PROTO_TRACE("Last block (%d) is %u..%u", lb->num - 1, block->start, block->end);

	/*
	 *	Fits within an existing block.
	 */
	if (block->end == offset) {
		block->end += size;
		FR_PROTO_TRACE("Expanding last block (%d) to %u..%u", lb->num - 1, block->start, block->end);
		return 0;
	}

	/*
	 *	It's full, die.
	 */
	if (lb->num == lb->max) return -1;

	lb->num++;
	block++;

	block->start = offset;
	block->end = offset + size;
	FR_PROTO_TRACE("Appending block (%d) to %u..%u", lb->num - 1, block->start, block->end);

	return 0;
}

static void dns_label_mark(fr_dns_labels_t *lb, uint8_t const *p)
{
	if (!lb || !lb->mark) return;

	fr_assert(p >= (lb->start + 12)); /* can't point to the packet header */
	fr_assert(!lb->end || (p < lb->end));

	lb->mark[p - lb->start] = 1;
}


static bool dns_pointer_valid(fr_dns_labels_t *lb, uint16_t offset)
{
	int i;

	if (!lb) return true;	/* we have no idea, so allow it */

	if (lb->mark) return (lb->mark[offset] != 0);

	/*
	 *	Brute-force searching.
	 *
	 *	@todo - manually walk through the pointers for the block?
	 */
	for (i = 0; i < lb->num; i++) {
		FR_PROTO_TRACE("Checking block %d %u..%u against %u",
			       i, lb->blocks[i].start, lb->blocks[i].end, offset);

		if (offset < lb->blocks[i].start) return false;

		if (offset < lb->blocks[i].end) return true;
	}

	return false;
}

/** Compare two labels in a case-insensitive fashion.
 *
 *  This function requires that the input is valid, i.e. all
 *  characters are within [-0-9A-Za-z].  If any other input is given,
 *  it will break.
 */
static bool labelcmp(uint8_t const *a, uint8_t const *b, size_t len)
{
	for (/* nothing */; len > 0; len--) {
		if (*a == *b) {
			a++;
			b++;
			continue;
		}

		/*
		 *	If one or the other isn't a letter, we can't
		 *	do case insensitive comparisons of them, so
		 *	they can't match.
		 */
		if (!(((*a >= 'a') && (*a <= 'z')) || ((*a >= 'A') && (*a <= 'Z')))) return false;
		if (!(((*b >= 'a') && (*b <= 'z')) || ((*b >= 'A') && (*b <= 'Z')))) return false;

		/*
		 *	If they're equal but different case, then the
		 *	only bit that's different is 0x20.
		 */
		if (((*a)^(*b)) != 0x20) {
			return false;
		}

		a++;
		b++;
	}

	return true;
}

/** Compress "label" by looking at the label recursively.
 *
 *  For "ftp.example.com", it searches the input buffer for a matching
 *  "com".  It only does string compares if it finds bytes "03 xx xx
 *  xx 00".  This means that the scan is quick, because most bytes are
 *  skipped.
 *
 *  If a matching string is found, the label is updated to replace
 *  "com" with a 2-byte pointer P1.  The process then proceeds
 *  recursively, with "exampleP1".
 *
 *  The input buffer is the scanned again for labels of matching
 *  length (7 here), AND which either end in the value of "P1", or end
 *  *at* P1.  If we find a match, we replace "exampleP1" with "P2".
 *  The process then proceeds recursively with "ftpP2".
 *
 *  Since the algorithm replaces known suffixes with pointers, we
 *  *never* have to compare full names.  Instead, we only ever compare
 *  one label to one other label.  And then only if the labels have
 *  the same lengths AND the same suffixes (00 byte, or a pointer P).
 *
 *  As an extra optimization, we track the start of the label where we
 *  found the compressed pointer.  e.g. "www.example.com" when
 *  compressing "com".  We know that the "com" string CANNOT appear
 *  before this label.  Because if it did, then the "www.example.com"
 *  name would have instead been compressed, as in "www.exampleP1".
 *
 *  This optimization ensures that we scan as little of the buffer as
 *  possible, by moving the search start ahead in the buffer.  This
 *  optimization also means that in many cases, the suffix we're
 *  looking for (e.g. "example.com") is in the first label we search.
 *  Which means that we end up ignoring most of the buffer.
 *
 *  This algorithm is O(N * B), where N is the number of labels in a
 *  name (e.g. 3 for "ftp.example.com"), and "B" is the size of the
 *  buffer.  It also does linear scans of the buffer, which are good
 *  for read-ahead.  Each input label is compared to labels in the
 *  buffer only when very limited situations apply.  And we never
 *  compare the full input name to full names in the buffer.
 *
 *  In the case where we are adding many names from the same zone to
 *  the input buffer, the input buffer will start with the zone name.
 *  So any searches will match that.  The only reason to continue
 *  scanning the buffer is to see if the name prefix already exists.
 *  If we assume that the records do not contain duplicates, then we
 *  can likely skip that scan, too.
 *
 *  Adding that optimization, however, requires tracking the maximum
 *  size of a name across multiple invocations of the function.  For
 *  example, if the maximum length name in the buffer is 3 labels, and
 *  we're adding a 3 label name, then we can stop scanning the buffer
 *  as soon as we compressed the 2 suffix labels.  Since we are
 *  guaranteed that there are no duplicates, we are sure that there is
 *  no existing 3-label name which matches a 3-label name in the
 *  buffer.
 *
 *  Note that this function does NOT follow pointers in the input
 *  buffer!
 *
 *
 *  A different and more straightforward approach is to loop over all
 *  labels in the name from longest to shortest, and comparing them to
 *  each name in the buffer in turn.  That algorithm ends up being
 *  O(L1 * T * L2), where L1 is the length of the input name, T is the
 *  total number of names in the buffer, and L2 is the average length
 *  of names in the buffer.  This algorithm can result in the buffer
 *  being scanned many, many, times.  The scan is also done forwards
 *  (due to comparing names one after the other), but also backwards
 *  (due to following pointers).  Which makes for poor locality of
 *  reference.
 *
 *  i.e. that approach *has* to scan the entire input buffer, because
 *  that's where all of the names are.  Further, it has to scan it at
 *  least "N" times, because there are N labels in the input name.  So
 *  O(N * B) is the *lower* bound for this algorithm.
 *
 *  It gets worse when the straightforward algorithm does pointer
 *  following instead of pointer comparisons.  It ends up scanning
 *  portions of the input buffer many, many, times.  i.e. it can
 *  compare an input "com" name to "org" once for every "org" name in
 *  the input buffer.  In contrast, because our algorithm does not do
 *  pointer following, it only compares "com" to "org" once.
 *
 * @param[in] packet	  where the packet starts
 * @param[in] start	  input buffer holding one or more labels
 * @param[in] end	  end of the input buffer
 * @param[out] new_search Where the parent call to dns_label_compress()
 *			  should start searching from, instead of from "start".
 * @param[in] label	  label to add to the buffer.
 * @param[out] label_end  updated end of the input label after compression.
 * @return
 *	- false, we didn't compress the input
 *	- true, we did compress the input.
 */
static bool dns_label_compress(uint8_t const *packet, uint8_t const *start, uint8_t const *end, uint8_t const **new_search,
			       uint8_t *label, uint8_t **label_end)
{
	uint8_t *next;
	uint8_t const *q, *ptr, *suffix, *search;
	uint16_t offset;
	bool compressed = false;

	/*
	 *	Don't compress "end of label" byte or pointers.
	 */
	if (!*label || (*label > 63)) {
		return false;
	}

	/*
	 *	Check the next label.  Note that this is *after*
	 *	"end".  It also MUST be a valid, uncompressed label.
	 */
	next = label + *label + 1;

	/*
	 *	Note that by design, next > end.  We don't care about
	 *	the size of the buffer we put "label" into.  We only
	 *	care that all bytes of "label" are valid, and we don't
	 *	access memory after "label".
	 */

	/*
	 *	On the first call, begin searching from the start of
	 *	the buffer.
	 *
	 *	For subsequent calls, begin from where we started
	 *	searching before.
	 */
	if (!new_search) {
		search = start;
	} else {
		search = *new_search;
	}

	/*
	 *	We're at the last uncompressed label, scan the input
	 *	buffer to see if there's a match.
	 *
	 *	The scan skips ahead until it find both a label length
	 *	that matches, AND "next" label which is 0x00.  Only
	 *	then does it do the string compare of the label
	 *	values.
	 *
	 *	We speed this up slightly by tracking the previous
	 *	uncompressed pointer.  If we do compress the current
	 *	label, then we should also tell the caller where the
	 *	previous uncompressed label started.  That way the
	 *	caller can start looking there for the next piece to
	 *	compress.  There's no need to search from the
	 *	beginning of the input buffer, as we're sure that
	 *	there is no earlier instance of the suffix we found.
	 *
	 *	i.e. as we compress the current name, we start
	 *	searching not at the beginning of the input buffer/
	 *	Instead, we start searching at the name which contains
	 *	the label that we just compressed.  The previous
	 *	sarching guarantees that no name *before* that one
	 *	will match the suffix we're looking for.  So we can
	 *	skip all of the previous names in subsequent searches,
	 */
	if (*next == 0x00) {
		q = search;
		while (q < end) {
			if (*q == 0x00) {
				q++;

				/*
				 *	None of the previous names
				 *	matched, so we tell the caller
				 *	to start searching from the
				 *	next name in the buffer.
				 */
				search = q;
				continue;
			}

			/*
			 *	Our label is a terminal one.  Which
			 *	can't point to a pointer.
			 */
			if (*q > 63) {
				q += 2;

				/*
				 *	None of the previous
				 *	uncompressed names matched,
				 *	and this pointer refers to a
				 *	compressed name.  So it
				 *	doesn't match, either.
				 */
				search = q;
				continue;
			}

			/*
			 *	We now have a label which MIGHT match.
			 *	We have to walk down it until it does
			 *	match.  But we don't update "search"
			 *	here, because there may be a suffix
			 *	which matches.
			 */
			ptr = q + *q + 1;
			if (ptr > end) return false;

			/*
			 *	Label lengths aren't the same, skip
			 *	it.
			 */
			if (*q != *label) {
				q = ptr;
				continue;
			}

			/*
			 *	Our input label ends with 0x00.  If
			 *	this label doesn't end with 0x00, skip
			 *	it.
			 */
			if (*ptr != 0x00) {
				q = ptr;
				continue;
			}

			/*
			 *	The pointer is too far away.  Don't
			 *	point to it.  This check is mainly for
			 *	static analyzers.
			 */
			if ((q - packet) > (1 << 14)) return false;

			/*
			 *	Only now do case-insensitive
			 *	comparisons.
			 */
			if (!labelcmp(q + 1, label + 1, *label)) {
				q = ptr;
				continue;
			}

			/*
			 *	We have a match.  Replace the input
			 *	label with a compressed pointer.  Tell
			 *	the caller the start of the found
			 *	name, so subsequent searches can start
			 *	from there.  Then return to the caller
			 *	that we managed to compress this
			 *	label.
			 */
			offset = (q - packet);
			label[0] = (offset >> 8) | 0xc0;
			label[1] = offset & 0xff;
			*label_end = label + 2;
			if (new_search) *new_search = search;
			return true;
		}

		return false;
	}

	/*
	 *	The next label is still uncompressed, so we call
	 *	ourselves recursively in order to compress it.
	 */
	if (*next < 63) {
		if (!dns_label_compress(packet, start, end, &search, next, label_end)) return false;

		/*
		 *	Else it WAS compressed.
		 */
		compressed = true;
	}

	/*
	 *	The next label wasn't compressed, OR it is invalid,
	 *	skip it.  This check is here only to shut up the
	 *	static analysis tools.
	 */
	if (*next < 0xc0) {
		return compressed;
	}

	/*
	 *	Remember where our suffix points to.
	 */
	suffix = packet + ((next[0] & ~0xc0) << 8) + next[1];

	/*
	 *	Our label now ends with a compressed pointer.  Scan
	 *	the input until we find either an uncompressed label
	 *	which ends with the same compressed pointer, OR we
	 *	find an uncompressed label which ends AT our
	 *	compressed pointer.
	 *
	 *	Note that we start searching from the beginning of the
	 *	label which resulted in us finding the compressed
	 *	pointer!
	 *
	 *	We're guaranteed that any label BEFORE that one
	 *	doesn't end with a matching compressed pointer.
	 */
	q = search;
	while (q < end) {
		if (*q == 0x00) {
			q++;

			/*
			 *	None of the previous stuff matched, so
			 *	we tell the caller to start searching
			 *	from the next name.
			 */
			search = q;
			continue;
		}

		/*
		 *	Skip compressed pointers.  We can't point to
		 *	compressed pointers.
		 */
		if (*q > 63) {
			q += 2;

			/*
			 *	None of the previous uncompressed
			 *	names matched, and this pointer refers
			 *	to a compressed name.  So it doesn't
			 *	match, either.
			 */
			search = q;
			continue;
		}

		/*
		 *	We now have an uncompressed label in the input
		 *	buffer.  Check for a match.
		 */
		ptr = q + *q + 1;
		if (ptr > end) return compressed;

		/*
		 *	Label lengths aren't the same, skip it.
		 */
		if (*q != *label) {
			q = ptr;
			continue;
		}

		/*
		 *	If the NEXT label is uncompressed, then skip
		 *	it unless it's the suffix we're pointing to.
		 */
		if (*ptr < 63) {
			if (ptr != suffix) {
				q = ptr;
				continue;
			}

			goto check_label;
		}

		/*
		 *	The next label is a compressed pointer.  If
		 *	the compressed pointers are different, then
		 *	skip both this label and the compressed
		 *	pointer after it.
		 */
		if ((ptr[0] != next[0]) ||
		    (ptr[1] != next[1])) {
			q = ptr + 2;

			/*
			 *	None of the previous uncompressed
			 *	names matched, and this pointer refers
			 *	to a compressed name.  So it doesn't
			 *	match, either.
			 */
			search = q;
			continue;
		}

	check_label:
		/*
		 *	Pointer is too far away.  Don't point
		 *	to it.
		 */
		if ((q - packet) > (1 << 14)) return compressed;

		/*
		 *	Only now do case-insensitive
		 *	comparisons.
		 */
		if (!labelcmp(q + 1, label + 1, *label)) {
			q = ptr;
			continue;
		}

		/*
		 *	We have a match.  Replace the input
		 *	label with a compressed pointer.  Tell
		 *	the caller the start of the found
		 *	name, so subsequent searches can start
		 *	from there.  Then return to the caller
		 *	that we managed to compress this
		 *	label.
		 */
		offset = (q - packet);
		label[0] = (offset >> 8) | 0xc0;
		label[1] = offset & 0xff;
		*label_end = label + 2;
		if (new_search) *new_search = search;
		return true;
	}

	/*
	 *	Who knows what it is, we couldn't compress it.
	 */
	return compressed;
}


/** Encode a single value box of type string, serializing its contents to a dns label
 *  in a dbuff
 *
 * @param[in] dbuff	Buffer where labels are written
 * @param[in] compression Whether or not to do DNS label compression.
 * @param[in] value	to encode.
 * @param[in] lb	label tracking data structure.
 * @return
 *	- >0 the number of bytes written to the dbuff
 *	- 0 could not encode anything, an error has occurred.
 *	- <0 the number of bytes the dbuff should have had, instead of "remaining".
 */
ssize_t fr_dns_label_from_value_box_dbuff(fr_dbuff_t *dbuff, bool compression, fr_value_box_t const *value, fr_dns_labels_t *lb)
{
	ssize_t			slen;
	size_t			need = 0;

	slen = fr_dns_label_from_value_box(&need, dbuff->p, fr_dbuff_remaining(dbuff), dbuff->p, compression, value, lb);
	if (slen < 0) return 0;

	if (slen == 0) return -need;

	fr_dbuff_advance(dbuff, (size_t)slen);
	return slen;
}

/** Encode a single value box of type string, serializing its contents to a dns label
 *
 * This functions takes a large buffer and encodes the label in part
 * of the buffer.  This API is necessary in order to allow DNS label
 * compression.
 *
 * @param[out] need	if not NULL, how long "buf_len" should be to
 *			serialize the rest of the data.
 *			Note: Only variable length types will be partially
 *			encoded. Fixed length types will not be partially encoded.
 * @param[out] buf	Buffer where labels are stored
 * @param[in] buf_len	The length of the output buffer
 * @param[out] where	Where to write this label
 * @param[in] compression Whether or not to do DNS label compression.
 * @param[in] value	to encode.
 * @param[in] lb	label tracking data structure
 * @return
 *	- 0 no bytes were written, see need value to determine
 *	- >0 the number of bytes written to "where", NOT "buf + where + outlen"
 *	- <0 on error.
 */
ssize_t fr_dns_label_from_value_box(size_t *need, uint8_t *buf, size_t buf_len, uint8_t *where, bool compression,
				    fr_value_box_t const *value, fr_dns_labels_t *lb)
{
	uint8_t *label;
	uint8_t const *end = buf + buf_len;
	uint8_t const *q, *strend, *last;
	uint8_t *data;
	bool underscore = true;

	if (!buf || !buf_len || !where || !value) {
		fr_strerror_const("Invalid input");
		return -1;
	}

	/*
	 *	Don't allow stupidities
	 */
	if (!((where >= buf) && (where < (buf + buf_len)))) {
		fr_strerror_const("Label to write is outside of buffer");
		return -1;
	}

	/*
	 *	We can only encode strings.
	 */
	if (value->type != FR_TYPE_STRING) {
		fr_strerror_const("Asked to encode non-string type");
		return -1;
	}

	/*
	 *	'.' or empty string is special, and is encoded as a
	 *	plain zero byte.
	 *
	 *	Since "where < end", we can always write 1 byte to it.
	 */
	if ((value->vb_length == 0) ||
	    ((value->vb_length == 1) && (value->vb_strvalue[0] == '.'))) {
		*where = 0x00;
		return 1;
	}

	/*
	 *	Sanity check the name before writing anything to the
	 *	buffer.
	 *
	 *	Only encode [-0-9a-zA-Z].  Anything else is forbidden.
	 *	Dots at the start are forbidden.  Double dots are
	 *	forbidden.
	 */
	q = (uint8_t const *) value->vb_strvalue;
	strend = q + value->vb_length;
	last = q;

	if (*q == '.') {
		fr_strerror_const("Empty labels are invalid");
		return -1;
	}

	/*
	 *	Convert it piece by piece.
	 */
	while (q < strend) {
		/*
		 *	Allow underscore at the start of a label.
		 */
		if (underscore) {
			underscore = false;

			if (*q == '_') goto next;
		}

		if (*q == '.') {
			/*
			 *	Don't count final dot as an
			 *	intermediate dot, and don't bother
			 *	encoding it.
			 */
			if ((q + 1) == strend) {
				strend--;
				break;
			}

			if (q[1] == '.') {
				fr_strerror_const("Double dots '..' are forbidden");
				return -1;
			}
			last = q;

			/*
			 *	We had a dot, allow underscore as the
			 *	first character of the next label.
			 */
			underscore = true;

		} else if (!((*q == '-') || ((*q >= '0') && (*q <= '9')) ||
			     ((*q >= 'A') && (*q <= 'Z')) || ((*q >= 'a') && (*q <= 'z')))) {
			fr_strerror_printf("Invalid character 0x%02x in label", *q);
			return -1;
		}

	next:
		q++;

		if ((q - last) > 63) {
			fr_strerror_const("Label is larger than 63 characters");
			return -1;
		}
	}

	q = (uint8_t const *) value->vb_strvalue;

	/*
	 *	For now, just encode the value as-is.  We do
	 *	compression as a second step.
	 *
	 *	We need a minimum length of string + beginning length
	 *	+ trailing zero.  Intermediate '.' are converted to
	 *	length bytes.
	 */
	if ((where + (strend - q) + 2) > end) {
		if (need) *need = (where + (strend - q) + 2) - buf;
		return 0;
	}

	label = where;
	*label = 0;
	data = label + 1;

	/*
	 *	@todo - encode into a local buffer, and then try to
	 *	compress that into the output buffer.  This means that
	 *	the output buffer can be a little bit smaller.
	 */
	while (q < strend) {
		fr_assert(data < end);
		fr_assert((data - where) < 255);

		/*
		 *	'.' is a label delimiter.
		 *
		 *	We've already checked above for '.' at the
		 *	start, for double dots, and have already
		 *	suppressed '.' at the end of the string.
		 *
		 *	Start a new label.
		 */
		if (*q == '.') {
			label = data;
			*label = 0;
			data = label + 1;

			q++;
			continue;
		}

		*(data++) = *(q++);
		(*label)++;
		fr_assert(*label <= 63);
	}

	*(data++) = 0;		/* end of label */

	/*
	 *	If we're compressing it, and we have data to compress,
	 *	then do it.
	 */
	if (compression && ((data - where) > 2)) {
		if (lb) {
			int i;

			/*
			 *	Loop over the parts of the packet which have DNS labels.
			 *
			 *	Note that the dns_label_compress() function does NOT follow pointers in the
			 *	start/end block which it's searching!  It just tries to compress the *input*,
			 *	and assumes that the input is compressed last label to first label.
			 *
			 *	In addition, dns_label_compress() tracks where in the block it started
			 *	searching.  So it only scans the block once, even if we pass a NULL search
			 *	parameter to it.
			 *
			 *	We could start compression from the *last* block.  When we add
			 *	"www.example.com" and then "ftp.example.com", we could point "ftp" to the
			 *	"example.com" portion. which is already in the packet.  However, doing that
			 *	would require that dns_label_compress() follows pointers in the block it's
			 *	searching. Which would greatly increase the complexity of the algorithm.
			 *
			 *
			 *	We could still optimize this algorithm a bit, by tracking which parts of the
			 *	buffer have DNS names of label length 1, 2, etc.  Doing that would mean more
			 *	complex data structures, but fewer passes over the packet.
			 */
			for (i = 0; i < lb->num; i++) {
				bool compressed;

				FR_PROTO_TRACE("Trying to compress %s in block %d of %u..%u",
					       value->vb_strvalue, i,
					       lb->blocks[i].start, lb->blocks[i].end);

				compressed = dns_label_compress(lb->start, lb->start + lb->blocks[i].start,
								lb->start + lb->blocks[i].end,
								NULL, where, &data);
				if (compressed) {
					FR_PROTO_TRACE("Compressed label in block %d", i);
					if (*(where + *where + 1) >= 0xc0) {
						FR_PROTO_TRACE("Next label is compressed, stopping");
					}
				}
			}

			dns_label_add(lb, where, data);

		} else if (buf != where) {
			if (dns_label_compress(buf, buf, where, NULL, where, &data)) {
				FR_PROTO_TRACE("Compressed single label %s to %zu bytes",
					       value->vb_strvalue, (size_t) (data - where));
			} else {
				FR_PROTO_TRACE("Did not compress single label");
			}
		}
	} else {
		FR_PROTO_TRACE("Not compressing label");
	}

	fr_assert(data > where);
	return data - where;
}

/** Get the *uncompressed* length of a DNS label in a network buffer.
 *
 *  i.e. how bytes are required to store the uncompressed version of
 *  the label.
 *
 *  Note that a bare 0x00 byte has length 1, to account for '.'
 *
 * @param[in] packet	  where the packet starts
 * @param[in] buf	buffer holding one or more DNS labels
 * @param[in] buf_len	total length of the buffer
 * @param[in,out] next	the DNS label to check, updated to point to the next label
 * @param[in] lb	label tracking data structure
 * @return
 *	- <=0 on error, offset from buf where the invalid label is located.
 *	- > 0 decoded size of this particular DNS label
 */
ssize_t fr_dns_label_uncompressed_length(uint8_t const *packet, uint8_t const *buf, size_t buf_len, uint8_t const **next, fr_dns_labels_t *lb)
{
	uint8_t const *p, *q, *end, *label_end;
	uint8_t const *current, *start;
	size_t length;
	bool at_first_label, already_set_next;

	if (!packet || !buf || (buf_len == 0) || !next) {
		fr_strerror_printf("Invalid argument");
		return 0;
	}

	start = *next;

	/*
	 *	Don't allow stupidities
	 */
	if (!((start >= packet) && (start < (buf + buf_len)))) {
		fr_strerror_printf("Label is not within the buffer");
		return 0;
	}

	end = buf + buf_len;
	p = current = start;
	length = 0;
	at_first_label = true;
	already_set_next = false;

	/*
	 *	We silently accept labels *without* a trailing 0x00,
	 *	so long as they end at the end of the input buffer.
	 */
	while (p < end) {
		/*
		 *	End of label byte.  Skip it.
		 *
		 *	Empty labels are length 1, to account for the
		 *	'.'.  The caller has to take care of this
		 *	manually.
		 */
		if (*p == 0x00) {
			p++;
			if (at_first_label) length++;

			/*
			 *	We're still processing the first
			 *	label, tell the caller where the next
			 *	one is located.
			 */
			if (current == start) {
				*next = p;
				already_set_next = true;
			}

			break;
		}

		/*
		 *	If there's only one byte in the packet, then
		 *	it MUST be 0x00.  If it's not, then the label
		 *	overflows the buffer.
		 */
		if ((p + 1) >= end) goto overflow;

		/*
		 *	0b10 and 0b10 are forbidden
		 */
		if ((*p > 63) && (*p < 0xc0)) {
			fr_strerror_const("Data with invalid high bits");
			return -(p - packet);
		}

		/*
		 *	Maybe it's a compressed pointer.
		 */
		if (*p > 63) {
			uint16_t offset;

			if ((p + 2) > end) {
			overflow:
				fr_strerror_const("Label overflows buffer");
				return -(p - packet);
			}

			offset = p[1];
			offset += ((*p & ~0xc0) << 8);

			/*
			 *	Forward references are forbidden,
			 *	including self-references.
			 *
			 *	This requirement follows RFC 1035
			 *	Section 4.1.4, which says:
			 *
			 *	... an entire domain name or a list of
			 *	labels at the end of a domain name is
			 *	replaced with a pointer to a prior
			 *	occurrence of the same name.
			 *	...
			 *
			 *	Note the key word PRIOR.  If we
			 *	enforce that the pointer is backwards,
			 *	and do various other enforcements,
			 *	then it is very difficult for
			 *	attackers to create malicious DNS
			 *	packets which will cause the decoder
			 *	to do bad things.
			 */
			if (offset >= (p - packet)) {
				fr_strerror_printf("Pointer %04x at offset %04x is an invalid forward reference",
						   offset, (unsigned int) (p - packet));
				return -(p - packet);
			}

			q = packet + offset;

			/*
			 *	As an additional sanity check, the
			 *	pointer MUST NOT point to something
			 *	within the label we're parsing.  If
			 *	that happens, we have a loop.
			 *
			 *	i.e. the pointer must point backwards
			 *	to *before* our current label.  When
			 *	that limitation is enforced, pointer
			 *	loops are impossible.
			 */
			if (q >= current) {
				fr_strerror_printf("Pointer %04x at offset %04x creates a loop within a label",
						   offset, (unsigned int) (p - packet));
				return -(p - packet);
			}

			/*
			 *	If we're tracking which labels are
			 *	valid, then check the pointer, too.
			 */
			if (!dns_pointer_valid(lb, offset)) {
				fr_strerror_printf("Pointer %04x at offset %04x does not point to a DNS label",
						   offset, (unsigned int) (p - packet));
				return -(p - packet);
			}

			/*
			 *	The pointer MUST point to a valid
			 *	length field, and not to another
			 *	pointer.
			 */
			if (*q > 63) {
				fr_strerror_printf("Pointer %04x at offset %04x does not point to the start of a label",
						   offset, (unsigned int) (p - packet));
				return -(p - packet);
			}

			/*
			 *	The pointer MUST NOT point to an end of label field.
			 */
			if (!*q) {
				fr_strerror_printf("Pointer %04x at offset %04x refers to an invalid field", offset,
						   (unsigned int) (p - packet));
				return -(p - packet);
			}

			/*
			 *	If we're jumping away from the label
			 *	we started with, tell the caller where
			 *	the next label is in the network
			 *	buffer.
			 */
			if (current == start) {
				*next = p + 2;
				already_set_next = true;
			}

			p = current = q;
			continue;
		}

		/*
		 *	Else it's an uncompressed label
		 */
		if ((p + *p + 1) > end) goto overflow;

		/*
		 *	It's a valid label.  Mark it as such.
		 */
		dns_label_mark(lb, p);

		/*
		 *	Account for the '.' on every label after the
		 *	first one.
		 */
		if (!at_first_label) length++;
		at_first_label = false;
		length += *p;

		/*
		 *	DNS names can be no more than 255 octets.
		 */
		if (length > 255) {
			fr_strerror_const("Total length of labels is > 255");
			return -(p - packet);
		}

		q = p + 1;
		label_end = q + *p;

		/*
		 *	Allow for underscore at the beginning of a
		 *	label.
		 */
		if (*q == '_') q++;

		/*
		 *	Verify that the contents of the label are OK.
		 */
		while (q < label_end) {
			if (!((*q == '-') || ((*q >= '0') && (*q <= '9')) ||
			      ((*q >= 'A') && (*q <= 'Z')) || ((*q >= 'a') && (*q <= 'z')))) {
				fr_strerror_printf("Invalid character 0x%02x in label", *q);
				return -(q - packet);
			}

			q++;
		}

		p += *p + 1;
	}

	/*
	 *	Return the length of this label.
	 */
	if (!already_set_next) *next = p; /* should be <='end' */

	/*
	 *	Add the label, only if we're not using the markup field.
	 */
	if (lb && !lb->mark) (void) dns_label_add(lb, start, *next);

	return length;
}

/** Verify that a network buffer contains valid DNS labels.
 *
 * @param[in] packet	  where the packet starts
 * @param[in] buf	buffer holding one or more DNS labels
 * @param[in] buf_len	total length of the buffer
 * @param[in] start	where to start looking
 * @param[in] lb	label tracking data structure
 * @return
 *	- <=0 on error, where in the buffer the invalid label is located.
 *	- > 0 total size of the encoded label(s).  Will be <= buf_len
 */
ssize_t fr_dns_labels_network_verify(uint8_t const *packet, uint8_t const *buf, size_t buf_len, uint8_t const *start, fr_dns_labels_t *lb)
{
	ssize_t slen;
	uint8_t const *label = start;
	uint8_t const *end = buf + buf_len;

	while (label < end) {
		if (*label == 0x00) {
			label++;
			break;
		}

		slen = fr_dns_label_uncompressed_length(packet, buf, buf_len, &label, lb);
		if (slen <= 0) return slen; /* already is offset from 'buf' and not 'label' */
	}

	return label - buf;
}

static ssize_t dns_label_decode(uint8_t const *packet, uint8_t const *end, uint8_t const **start, uint8_t const **next)
{
	uint8_t const *p, *q;

	p = *start;

	if (end == packet) return -1;

	if (*p == 0x00) {
		*next = p + 1;
		return 0;
	}

	/*
	 *	Pointer, which points somewhere in the packet.
	 */
	if (*p >= 0xc0) {
		uint16_t offset;

		if ((end - packet) < 2) {
			return -(p - packet);
		}

		offset = p[1];
		offset += ((*p & ~0xc0) << 8);

		q = packet + offset;
		if (q >= p) {
			return -(p - packet);
		}
		p = q;
	}

	/*
	 *	0b10 and 0b10 are forbidden, and pointers can't point to other pointers.
	 */
	if (*p > 63) return -(p - packet);

	if ((p + *p + 1) > end) {
		return -(p - packet);
	}

	/*
	 *	Tell the caller where the actual label is located.
	 */
	*start = p;
	*next = p + *p + 1;
	return *p;
}


/** Decode a #fr_value_box_t from one DNS label
 *
 * The output type is always FR_TYPE_STRING
 *
 * Note that the caller MUST call fr_dns_labels_network_verify(src, len, start)
 * before calling this function.  Otherwise bad things will happen.
 *
 * @param[in] ctx	Where to allocate any talloc buffers required.
 * @param[out] dst	value_box to write the result to.
 * @param[in] src	Start of the buffer containing DNS labels
 * @param[in] len	Length of the buffer to decode
 * @param[in] label	This particular label
 * @param[in] tainted	Whether the value came from a trusted source.
 * @param[in] lb	label tracking data structure
 * @return
 *	- >= 0 The number of network bytes consumed.
 *	- <0 on error.
 */
ssize_t fr_dns_label_to_value_box(TALLOC_CTX *ctx, fr_value_box_t *dst,
				  uint8_t const *src, size_t len, uint8_t const *label,
				  bool tainted, fr_dns_labels_t *lb)
{
	ssize_t slen;
	uint8_t const *after = label;
	uint8_t const *current, *next = NULL;
	uint8_t const *packet = src;
	uint8_t const *end = packet + len;
	uint8_t *p;
	char *q;

	if (!len) return -1;

	/*
	 *	The label must be within the current buffer we're
	 *	passed.
	 */
	if ((label < src) || (label >= end)) return -1;

	/*
	 *	The actual packet might start earlier than the buffer,
	 *	so reset it if necessary.
	 */
	if (lb) packet = lb->start;

	/*
	 *	Get the uncompressed length of the label, and the
	 *	label after this one.
	 */
	slen = fr_dns_label_uncompressed_length(packet, src, len, &after, lb);
	if (slen <= 0) {
		FR_PROTO_TRACE("dns_label_to_value_box - Failed getting length");
		return slen;
	}

	fr_value_box_init_null(dst);

	/*
	 *	An empty label is a 0x00 byte.  Just create an empty
	 *	string.
	 */
	if (slen == 1) {
		if (fr_value_box_bstr_alloc(ctx, &q, dst, NULL, 1, tainted) < 0) return -1;
		q[0] = '.';
		return after - label;
	}

	/*
	 *	Allocate the string and set up the value_box
	 */
	if (fr_value_box_bstr_alloc(ctx, &q, dst, NULL, slen, tainted) < 0) return -1;

	current = label;
	p = (uint8_t *) q;
	q += slen;

	while (current && (current < after) && (*current != 0x00)) {
		/*
		 *	Get how many bytes this label has, and where
		 *	we will go to obtain the next label.
		 */
		slen = dns_label_decode(packet, end, &current, &next);
		if (slen < 0) return slen;

		/*
		 *	As a sanity check, ensure we don't have a
		 *	buffer overflow.
		 */
		if ((p + slen) > (uint8_t *) q) {
			FR_PROTO_TRACE("dns_label_to_value_box - length %zd Failed at %d", slen, __LINE__);

		fail:
			fr_value_box_clear(dst);
			return -1;
		}

		/*
		 *	Add '.' before the label, but only for the
		 *	second and subsequent labels.
		 */
		if (p != (uint8_t const *) dst->vb_strvalue) {
			*(p++) = '.';
		}

		/*
		 *	Copy the raw bytes from the network.
		 */
		memcpy(p, current + 1, slen);

		/*
		 *	Go ahead in the output string, and go to the
		 *	next label for decoding.
		 */
		p += slen;
		current = next;
	}

	/*
	 *	As a last sanity check, ensure that we've filled the
	 *	buffer exactly.
	 */
	if (p != (uint8_t *) q) {
		FR_PROTO_TRACE("dns_label_to_value_box - Failed at %d", __LINE__);
		goto fail;
	}

	*p = '\0';

	/*
	 *	Return the number of network bytes used to parse this
	 *	part of the label.
	 */
	return after - label;
}
