path: root/src/bencoding.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

/**
 * enum of all possible bencoding types and some options to use
 * to check a type, use ORing, not direct comparison, as bdecoded structs inherit opts from bdecode function in their ->types
 */

enum benc {
	string = 1 << 0,
	num = 1 << 1,
	list = 1 << 2,
	dict = 1 << 3,
	replace = 1 << 4, /**< replace existing element with same key when using binsert() instead of prepending the new element before the old. see binsert() docs. */
	nonascii2dot = 1 << 5 /**< see b2json() */
};

/**
 * structure representation of bencoded data
 * the structure copies strings
 */

struct bencoding {
	struct bencoding * next; /**< NULL if element is not member of a list or dict */
	struct bencoding * prev;
	struct bencoding * child; /**< NULL if element is not a list or dict or if it has 0 children */
	struct bencoding * parent;
	enum benc type; /**< type | opts of this element */
	struct bencoding * key; /**< the key element, string according to the spec, applicable for dict */
	char * value; /**< set to the content of the element. \0 terminated. NULL for dict and list. */
	size_t valuelen; /**< length of string value. */
	long int intvalue;
	int index;
	unsigned seqnr; /**< sequential number for bdecode_safe element counting */
	const char * after; /**< internal, set to character after this bencoded element in input string, used by recursive bdecode */
};

/**
 * frees the passed bencoding struct or performs no action if NULL was passed. caller should NULL the pointer to prevent reuse.
 *
 * possible stack overflow: freeing large lists, those with either a lot of elements or very deep nesting causes a stack overflow due to the deep recursion of this funtion. bdecode wrapper makes sure that the number of elements does not exceed a certain hardcoded number.
 */

void free_bencoding (struct bencoding * b) {
	if (!b)
		return;
	free_bencoding(b->child); /* we free the child should it exist. it can be NULL. */
	free_bencoding(b->key); /* should this be an element of a dict, free the key */
	free_bencoding(b->next);
	free(b->value);
	free(b);
	return;
}

/**
 * compares two bencoding elements. used in binsert. elements with different types are always different.
 *
 * @param a	[in] if this one is higher, -1 is returned
 * @param b	[in] if this one is higher, 1 is returned
 * @return -1 if a is higher, 1 if b is higher, 0 if they are the same
 */

int bcompare (struct bencoding * a, struct bencoding * b) {
	if (!a && !b)
		return 0;
	if (!a && b)
		return -1;
	if (a && !b)
		return 1;
	if ((a->type & (num | string | list | dict)) < (b->type & (num | string | list | dict)))
		return -1;
	if ((a->type & (num | string | list | dict)) > (b->type & (num | string | list | dict)))
		return 1;
	int ret = bcompare(a->key, b->key);
	if (ret)
		return ret;
	if (a->type & num) {
		if (a->intvalue != b->intvalue)
			return a->intvalue < b->intvalue ? -1 : 1;
		else
			return 0;
	}
	if (a->type & string) {
		if (a->valuelen != b->valuelen)
			return a->valuelen < b->valuelen ? -1 : 1;
		else
			return memcmp(a->value, b->value, a->valuelen);
	}
	if (!a->child && b->child)
		return -1;
	if (a->child && !b->child)
		return 1;
	if (a->type & (list | dict)) {
		a = a->child;
		b = b->child;
		while (1) {
			if (!a && !b)
				return 0;
			int ret = bcompare(a, b);
			if (ret)
				return ret;
			a = a->next;
			b = b->next;
		}
	}
	return 0;
}

/**
 * returns a bencoding element that represents a string. the resulting element is allocated on heap and must be bencoding_free()d.
 *
 * the string ownership is transfered, so for static strings, do strdup() before pass
 *
 * @param str	[in]	the string to be converted to a bencoding element
 */

struct bencoding * bstr (char * str) {
	if (!str)
		return NULL;
	struct bencoding * b = calloc(1, sizeof *b);
	if (!b)
		return NULL;
	b->type = string;
	b->valuelen = strlen(str);
	b->value = str;
	return b;
}

/**
 * returns a bencoding element that represents a string. the string ownership is not transfered and the element is allocated on the stack, so no cleanup is required. ideal for bval(), DO NOT USE ON binsert() and similar.
 *
 * implemented as a macro that edits the current function's stack.
 *
 * @param str	[in]	the string to be converted to a bencoding element
 */

#define bstrs(x) bstrs_set(alloca(sizeof(struct bencoding)), x)

struct bencoding * bstrs_set (struct bencoding * b, char * s) {
	memset(b, '\0', sizeof *b);
	b->value = s;
	b->valuelen = strlen(s);
	b->type = string;
	return b;
}

/**
 * returns a bencoding element that represents a number. the resulting element is allocated on heap and must be bencoding_free()d.
 *
 * @param num	[in]	the number to be converted to a bencoding number
 */

struct bencoding * bnum (long int nr) {
	struct bencoding * b = calloc(1, sizeof *b);
	if (!b)
		return NULL;
	b->type = num;
	b->valuelen = 0;
	b->intvalue = nr;
	return b;
}

/**
 * returns a bencoding element that represents a number. the element is allocated on the stack, so no cleanup is required. ideal for bval(), DO NOT USE ON binsert() and similar.
 *
 * implemented as a macro that edits the current function's stack.
 *
 * @param num	[in]	the number to be converted to a bencoding number
 */

#define bnums(x) bnums_set(alloca(sizeof(struct bencoding)), x)

struct bencoding * bnums_set (struct bencoding * b, long int num) {
	memset(b, '\0', sizeof *b);
	b->type = num;
	b->valuelen = 0;
	b->intvalue = num;
	return b;
}

/**
 * return how much space a character in a string uses
 *
 * @param a	[in]	the character in question
 */

int b2json_charsize (unsigned char a) {
	if (a == '"')
		return 2;
	if (a == '\\')
		return 2;
	if (a == '\b')
		return 2;
	if (a == '\f')
		return 2;
	if (a == '\n')
		return 2;
	if (a == '\r')
		return 2;
	if (a == '\t')
		return 2;
	if (a < ' ')
		return 6;
	return 1;
}

/**
 * write a string representation of a character in a JSON string
 *
 * @param dest	[out]	destination
 * @param a	[in]	the character in question
 * @param na2d	[in]	true if you want to convert non-ascii characters to . or false to output them literally (the latter is non-standard)
 * @return the destination pointer, incremented for the number of bytes written
 */

char * b2json_charrepr (char * dest, unsigned char a, bool na2d) {
	switch (a) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wstringop-truncation"
		case '"':
			strncpy(dest, "\\\"", 2);
			return dest+2;
		case '\\':
			strncpy(dest, "\\\\", 2);
			return dest+2;
		case '\b':
			strncpy(dest, "\\b", 2);
			return dest+2;
		case '\f':
			strncpy(dest, "\\f", 2);
			return dest+2;
		case '\n':
			strncpy(dest, "\\n", 2);
			return dest+2;
		case '\r':
			strncpy(dest, "\\r", 2);
			return dest+2;
		case '\t':
			strncpy(dest, "\\t", 2);
			return dest+2;
		default:
			if (a < ' ') {
				char buf[7];
				sprintf(buf, "\\u00%02x", a);
				strncpy(dest, buf, 6);
				return dest+6;
			} else if (a > 127 && na2d) {
				*dest++ = '.';
				return dest;
			} else {
				*dest++ = a;
				return dest;
			}
#pragma GCC diagnostic pop
	}
}


/**
 * get size required for JSON representation of a bencoding struct. terminating NULL byte is not counted, because b2json does not write it. write it yourself.
 *
 * @param b	[in]	bencoding structure of a bdecoded element
 */

int b2json_length (struct bencoding * b) {
	int add = 0;
	if (!b)
		return 4;
	if (b->key)
		add += 1 + b2json_length(b->key);
	if (b->type & string) {
		int size = 2;
		for (size_t i = 0; i < b->valuelen; i++)
			size += b2json_charsize(b->value[i]);
		return size+add;
	}
	if (b->type & num) {
		char buf[512];
		sprintf(buf, "%ld", b->intvalue);
		return strlen(buf)+add;
	}
	if (b->type & (list | dict)) {
		if (!b->child)
			return 2+add;
		struct bencoding * t = b->child;
		int size = 2 + b2json_length(t);
		while (t->next) {
			t = t->next;
			size += b2json_length(t) + 1;
		}
		return size+add;
	}
	return 5;
}

/**
 * write json representation of a bencoding struct. does not write terminating nullbyte, b2json_length does not include it in count. add it yourself. should write exactly b2json_length bytes.
 *
 * writes false when struct has an incorrect type and null when NULL pointer is passed, this is in ordnung with b2json_length.
 *
 * you can set bencoding opt nonascii2dot to convert values above 127 to '.'
 *
 * @param dest	[in]	destination
 * @param b	[in]	bencoding structure of a bdecoded element
 * @return the destination pointer, incremented for the number of bytes written
 */

char * b2json (char * dest, struct bencoding * b) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wstringop-truncation"
	if (!b) {
		strncpy(dest, "null", 4);
		return dest+4;
	}
	if (b->key) {
		dest = b2json(dest, b->key);
		*dest++ = ':';
	}
	if (b->type & string) {
		*dest++ = '"';
		for (size_t i = 0; i < b->valuelen; i++)
			dest = b2json_charrepr(dest, b->value[i], b->type & nonascii2dot);
		*dest++ = '"';
		return dest;
	}
	if (b->type & num) {
		char buf[512];
		sprintf(buf, "%ld", b->intvalue);
		strcpy(dest, buf);
		return dest+strlen(buf);
	}
	if (b->type & (list | dict)) {
		if (!b->child) {
			strncpy(dest, b->type & list ? "[]" : "{}", 2);
			return dest+2;
		}
		*dest++ = b->type & list ? '[' : '{';
		struct bencoding * t = b->child;
		dest = b2json(dest, t);
		while (t->next) {
			t = t->next;
			*dest++ = ',';
			dest = b2json(dest, t);
		}
		*dest++ = b->type & list ? ']' : '}';
		return dest;
	}
	strncpy(dest, "false", 4);
	return dest+4;
#pragma GCC diagnostic pop
}

/**
 * print bstructure to a FILE *. used for debugging. in JSON
 *
 * @param benc [in]	the structure to be printed
 * @param benc [in]	the FILE * to which to print to
 */

void bprint (FILE * out, struct bencoding * benc) {
	char o[1+b2json_length(benc)];
	b2json(o, benc);
	o[b2json_length(benc)] = '\0';
	fprintf(out, "%s\n", o);
}

/**
 * insert into bencoding dict or list. if key already exists, it's prepended to the already existing key, unless opts has replace set.
 *
 * the memory pointed to by elem is considered ownership and responsibility of the dict now, so it shouldn't be freed by the caller. it can still be modified, however.
 *
 * if elem or benc is NULL, function does nothing.
 *
 * default (without replace), new element will be inserted into the dict, but before the old element, with the aim that finders, such as bpath(), would return the new element instead of the old.
 * replace option frees the old element and inserts this one instead if the key already exists in the dict. this is not the default, because it frees objects that may be used elsewhere.
 *
 * for lists, binsert adds the new element to the start of the list
 *
 * @param benc	[in]	the structure to which elem will be inserted into
 * @param elem	[in]	the element that will be inserted into the structure
 */

void binsert (struct bencoding * benc, struct bencoding * elem) {
	if (!benc || !elem)
		return;
	elem->parent = benc;
	struct bencoding ** place = &benc->child;
	while (1) {
		if (!*place) {
			*place = elem;
			elem->next = NULL;
			elem->prev = NULL;
			return;
		}
		if (bcompare((*place)->key, elem->key) >= 0) {
			elem->prev = (*place)->prev;
			elem->next = *place;
			(*place)->prev = elem;
			if (((benc->type & replace) || (elem->type & replace)) && !bcompare((*place)->key, elem->key)) {
				elem->next = (*place)->next;
				if ((*place)->next)
					(*place)->next->prev = elem;
				free_bencoding(*place);
			}
			*place = elem;
			return;
		}
		place = &(*place)->next;
	}
}

/**
 * detaches an element from a bencoding list or dict, does not free it.
 *
 * @param elem	[in]	the element to be detached but not freed
 */

void bdetach (struct bencoding * elem) {
	if (!elem)
		return;
	if (elem->prev)
		elem->prev->next = elem->next;
	if (elem->next)
		elem->next->prev = elem->prev;
	elem->next = NULL;
	elem->prev = NULL;
	// elem->parent = NULL; // we could also do that, no issue with me 20221123
}

/**
 * element count limited bdecode, see bdecode wrapper function for full description. additional params are described here though
 *
 * @param seqnr	[in]	sequential count of this invocation
 * @param max	[in]	max invocation count that can be achieved (max nr. of elems)
 */

struct bencoding * bdecode_safe (const char * s, int len, enum benc opts, unsigned seqnr, unsigned max) {
	if (seqnr >= max)
		return NULL;
	if (!s || len < -2 || (len >= 0 && len < 2 /* 2 being the smallest bencoding string */))
		return NULL;
	if (len == -2)
		len = strlen(s);
	struct bencoding * b = calloc(1, sizeof(struct bencoding)); /* SEGV if OOM */
	b->seqnr = seqnr;
	char * ch = NULL;
	switch (s[0]) {
		case 'i': /* num */
			b->type = num;
			if (len == -1 || memchr(s, 'e', len)) { /* correct string or end found */
				b->intvalue = strtol(s+1, &ch, 10);
				b->valuelen = ch-(s+1);
				b->value = malloc(b->valuelen+1);
				if (!b->value) {
					free(b);
					return NULL;
				}
				strncpy(b->value, s+1, b->valuelen);
				b->value[b->valuelen] = '\0';
				b->after = s+2+b->valuelen;
			} else {
				free(b);
				return NULL;
			}
			break;
		case 'd': /* dict */
			b->type = dict;
			__attribute__((fallthrough));
		case 'l': /* list */
			if (!b->type)
				b->type = list;
			const char * cp = s+1;
			struct bencoding * arbeit = NULL;
			struct bencoding * oldarbeit = NULL;
			struct bencoding * oldoldarbeit = NULL; /* for dicts, holds previous value */
			int index = 0;
			while (len == -1 || cp <= s+len) {  /* s+len is max we are allowed to read */
				arbeit = bdecode_safe(cp, len == -1 ? -1 : len-(cp-s), opts, ++b->seqnr, max);
				if (arbeit) {
					arbeit->parent = b;
					b->seqnr = arbeit->seqnr;
				} else
					break;
				if (b->seqnr >= max) {
					free_bencoding(arbeit);
					break;
				}
#define ISDICT (b->type & dict)
#define ISLIST !ISDICT
#define ISVAL (index % 2)
#define ISKEY !ISVAL
				if (ISDICT && ISVAL)
					arbeit->key = oldarbeit;
				cp = arbeit->after;
				arbeit->prev = ISDICT ? ISVAL ? oldoldarbeit : oldarbeit : oldarbeit;
				arbeit->index = ISDICT ? index/2 : index;
				if (ISLIST) {
					if (index)
						oldarbeit->next = arbeit;
					else
						b->child = arbeit;
				}
				if (ISDICT) {
					if (index == 1)
						b->child = arbeit;
					else if (ISVAL)
						oldoldarbeit->next = arbeit;
				}
				oldoldarbeit = oldarbeit;
				oldarbeit = arbeit;
				index++;
			}
			b->after = cp+1;
			b->type = b->type | opts;
			if (ISDICT && ISVAL) // e je torej value, če je prej samoten key
				free_bencoding(oldarbeit); // this key would be otherwise leaked
			return b;
		case 'e': /* end of list/dict */
			free(b);
			return NULL;
		default:
			if (!(s[0] >= '0' && s[0] <= '9')) { /* not a string. not checking this would allow DoS for parsing "lx" */
				// fprintf(stderr, "bencoding: unknown type %d - %c\n", s[0], s[0]);
				free(b);
				return NULL;
			}
			b->type = string;
			if (len == -1 || (b->value = memchr(s, ':', len))) {
				b->valuelen = strtol(s, &ch, 10);
				if (len != -1 && (unsigned)len < b->valuelen + (ch+1 - s) /* len minus prefix; strlen & colon */)
					b->valuelen = len - (ch+1 - s); /* malformed bencoded data, truncating string */
				b->value = malloc(b->valuelen+1);
				memcpy(b->value, ch+1, b->valuelen); // ofc not strncpy - binary strs
				b->value[b->valuelen] = '\0';
				b->after = ch+1+b->valuelen;
			} else {
				free(b);
				return NULL;
			}
			break;
	}
	b->type = b->type | opts;
	return b;
}

/**
 * bdecodes a bencoded structure from a string into a bencoding structure that must be free_bencodinged by the caller.
 * 
 * nonstandard things: this parser allows for dict keys to be of any type, valuekey
 *
 * this is a wrapper function, the implementation is in bdecode_safe that was made as an afterthought to prevent stack overflows and limits the number of elements bdecoded.
 *
 * @param len	[in]	* if set to -1, string is assumed to be correct and not NULL terminated, NULLs may be in strings.
 * 				- malicious strings may trigger reads past the end of the buffer, which may lead to undefined
 *				behaviour, crashes (DoS) or leaks of content, stored in memory.
 *				- if opts&terminate, another character will be written after the bencoded structure in memory if
 *				that structure is a string. beware and have space allocated for it!
 * 			* if set to -2, string is assumed to be NULL terminated and no further reading will be done after the NULL.
 * 				- if such terminator breaks an incomplete element, the resulting structure may be incomplete, but
 * 				will be correct - for example valuelen of a misterminated string will correctly be shortened.
 * 			* if set to a positive number, reading will only be allowed up to that many characters.
 * 				- if the input string reads the end and the structure is incomplete, same thing as with -2 happens.
 * 				- if the structure ends cleanly (string length satisfied or end of list, dict or num found),
 * 				processing stops, no mather how many characters of len are left.
 * @param opts	[in]	sets options. do not set the type bits here, this is the same enum as the ->type enum of returned struct.
 * 			opts will be reflected in the ->type of the returning struct. opts will apply to childs of lists&dicts too.
 */

struct bencoding * bdecode (const char * s, int len, enum benc opts) {
	return bdecode_safe(s, len, opts, 0, 1 << 21);
}

/**
 * returns a pointer to bencoding struct matching bencoding path or NULL if not found.
 *
 * path key/key2/key3 will given object {"key":{"key2":{"key3":val}}} return val
 * 
 * @param benc	[in]	the bencoding dict to look in
 * @param key	[in]	the path
 */

struct bencoding * bpath (const struct bencoding * benc, const char * key) {
	if (!benc)
		return NULL;
	if (!benc->child)
		return NULL;
	benc = benc->child;
	if (key[0] == '/')
		key++;
	size_t len = strlen(key);
	char * c = strchr(key, '/');
	if (c)
		len = c - key;
	while (benc) {
		if (benc->key && benc->key->type & num) {
			char buf[512];
			sprintf(buf, "%ld", benc->key->intvalue);
			if (len == strlen(buf) && !strncmp(buf, key, len)) {
				if (!c) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdiscarded-qualifiers"
					return benc;
#pragma GCC diagnostic pop
				} else
					return bpath(benc, key+len);
			}
		}
		if (benc->key && benc->key->type & string) {
			if (len == benc->key->valuelen && !strncmp(key, benc->key->value, len)) {
				if (!c) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdiscarded-qualifiers"
					return benc;
#pragma GCC diagnostic pop
				} else
					return bpath(benc, key+len);
			}
		}
		benc = benc->next;
	}
	return NULL;
}

/**
 * macro that loops following code body across a list or values of dict
 *
 * @param list	[in]	list/dict of values
 * @param elem	[out]	name of element that will be used for value while looping
 */

#define bforeach(list, elem) \
	for (struct bencoding * elem = list ? list->child : NULL; elem; elem = elem->next)

/**
 * find a value in a list. returns NULL if not found.
 *
 * to easily check if a number or string is present in a list or dict as a value:
 *
 * if (bval(benc, bnums(123)) || bval(benc, bstrs("some string")));
 *
 * @param benc	[in]	the bencoding list or dict to look in
 * @param val	[in]	the value
 */

struct bencoding * bval (struct bencoding * benc, struct bencoding * val) {
	if (!benc)
		return NULL;
	if (!benc->child)
		return NULL;
	benc = benc->child;
	while (benc) {
		if (!bcompare(benc, val))
			return benc;
		benc = benc->next;
	}
	return NULL;
}

/**
 * returns the size required to store a bencoded object, without the terminating NULL byte.
 *
 * @param b	[in]	the bencoding object
 */

int bencode_length (struct bencoding * b) {
	if (!b)
		return 0;
	char buf[512];
	if (b->type & num) {
		sprintf(buf, "%ld", b->intvalue);
		return strlen(buf)+bencode_length(b->key)+2;
	}
	if (b->type & string) {
		sprintf(buf, "%zu", b->valuelen);
		return strlen(buf)+1+b->valuelen+bencode_length(b->key);
	}
	if (b->type & (list | dict)) {
		struct bencoding * t = b->child;
		int size = 2;
		while (t) {
			size += bencode_length(t);
			t = t->next;
		}
		return size+bencode_length(b->key);
	}
	return 0;
}

/**
 * encode a bencoding object with bencoding and store it into memory pointed to by dest with at least bencode_length(b) space.
 *
 * does not write a terminating NULL byte.
 *
 * @param dest	[in]	the destination to which to write to
 * @param b	[in]	the bencoding object
 * @return the pointer to the byte after the last written byte
 */

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wstringop-truncation"
char * bencode (char * dest, struct bencoding * b) {
	if (!b)
		return dest;
	char buf[512];
	if (b->key)
		dest = bencode(dest, b->key);
	if (b->type & num) {
		sprintf(buf, "i%ld", b->intvalue);
		strcpy(dest, buf);
		dest += strlen(buf);
		*dest++ = 'e';
	}
	if (b->type & string) {
		sprintf(buf, "%zu:", b->valuelen);
		strcpy(dest, buf);
		dest += strlen(buf);
		memcpy(dest, b->value, b->valuelen);
		dest += b->valuelen;
	}
	if (b->type & (list | dict)) {
		if (b->type & list)
			*dest++ = 'l';
		else
			*dest++ = 'd';
		struct bencoding * t = b->child;
		while (t) {
			dest = bencode(dest, t);
			t = t->next;
		}
		*dest++ = 'e';
	}
	return dest;
}
#pragma GCC diagnostic pop

/**
 * clones a bencoding object including all of it's children
 *
 * @param b	[in]	the source object
 * @return the new object, allocated on heap
 */

struct bencoding * bclone (struct bencoding * b) {
	if (!b)
		return NULL;
	struct bencoding * c = calloc(1, sizeof(*c));
	if (b->key) {
		c->key = bclone(b->key);
		c->key->parent = c;
	}
	if (b->child) {
		c->child = bclone(b->child);
		c->child->parent = c;
	}
	if (b->next && (c->next = bclone(b->child)) && (c->next->parent = c))
		{}
	c->valuelen = b->valuelen;
	if (b->value) {
		c->value = malloc(c->valuelen+1);
		memcpy(c->value, b->value, c->valuelen+1);
	}
	c->intvalue = b->intvalue;
	c->type = b->type;
	c->index = b->index;
	return c;
}