path: root/mood.c

/* SPDX-License-Identifier: GPL-2.0 */

/** \file mood.c Paraslash's mood handling functions. */

#include <osl.h>
#include <lopsub.h>

#include "para.h"
#include "error.h"
#include "string.h"
#include "afh.h"
#include "afs.h"

/*
 * Mood parser API. It's overkill to have an own header file for
 * these declarations as they are only needed in this .c file.
 */
struct mp_context;
int mp_init(const char *definition, int nbytes, struct mp_context **result,
		 char **errmsg);
bool mp_eval_row(const struct osl_row *aft_row, struct mp_context *ctx);
void mp_shutdown(struct mp_context *ctx);

/*
 * Statistics about the set of admissible audio files. Computed at mood
 * load time. The values are used to assign normalized score values to
 * each admissible audio file. The statistics of the current mood are
 * also accessed when the score of an audio file needs to be recomputed,
 * for example because it was streamed or because the file's metadata got
 * modified via the touch subcommand.
 */
struct afs_statistics {
	/* Sum of the num_played counts of the admissible files. */
	int64_t num_played_sum;
	/* Same, but with the last_played values. */
	int64_t last_played_sum;
	/* Quadratic deviation of num_played count. */
	int64_t num_played_qd;
	/* Same but with last played time. */
	int64_t last_played_qd;
	/* Correction factor for the num played score. */
	int64_t num_played_correction;
	/* Correction factor for the last played score. */
	int64_t last_played_correction;
	/* Common divisor of the correction factors. */
	int64_t normalization_divisor;
	/* Number of admissible files */
	unsigned num;
};

/*
 * Represents a loaded mood. Contains the context of the bison mood parser
 * and the statistics. Allocated and initialized at mood load time.
 */
struct selector_instance {
	/* NULL means that this is the "dummy" mood. */
	char *name;
	/* Bison's abstract syntax tree, used to determine admissibility. */
	struct mp_context *parser_context;
	/* To compute the score. */
	struct afs_statistics stats;
	/* NULL means to operate on the global score table. */
	struct osl_table *score_table;
};

/*
 * Find the position of the most-significant set bit.
 *
 * Copied and slightly adapted from the linux source tree, version 4.9.39
 * (2017-07).
 */
__a_const static uint32_t fls64(uint64_t v)
{
	int n = 63;
	const uint64_t ones = ~(uint64_t)0U;

	if ((v & (ones << 32)) == 0) {
		n -= 32;
		v <<= 32;
	}
	if ((v & (ones << (64 - 16))) == 0) {
		n -= 16;
		v <<= 16;
	}
	if ((v & (ones << (64 - 8))) == 0) {
		n -= 8;
		v <<= 8;
	}
	if ((v & (ones << (64 - 4))) == 0) {
		n -= 4;
		v <<= 4;
	}
	if ((v & (ones << (64 - 2))) == 0) {
		n -= 2;
		v <<= 2;
	}
	if ((v & (ones << (64 - 1))) == 0)
		n -= 1;
	return n;
}

/*
 * Compute the integer square root floor(sqrt(x)).
 *
 * Taken 2007 from the linux source tree.
 */
__a_const static uint64_t int_sqrt(uint64_t x)
{
	uint64_t op = x, res = 0, one = 1;

	one = one << (fls64(x) & ~one);
	while (one != 0) {
		if (op >= res + one) {
			op = op - (res + one);
			res = res + 2 * one;
		}
		res /= 2;
		one /= 4;
	}
	return res;
}

/* Free all resources of a mood instance. It's OK to pass NULL. */
static void mood_unload(struct selector_instance *si)
{
	if (!si)
		return;
	mp_shutdown(si->parser_context);
	score_close(si->score_table);
	free(si->name);
	free(si);
}

static struct selector_instance *new_mood_instance(const char *name)
{
	struct selector_instance *si = zalloc(sizeof(*si));

	if (name)
		si->name = para_strdup(name);
	si->stats.normalization_divisor = 1;
	return si;
}

static int init_mood_parser(const char *mood_name, struct afs_callback_arg *aca,
		struct selector_instance **si)
{
	struct osl_object mood_def;
	int ret;
	char *err;

	if (!*mood_name) {
		afs_error(aca, "empty mood name\n");
		return -ERRNO_TO_PARA_ERROR(EINVAL);
	}
	ret = mood_get_def_by_name(mood_name, &mood_def);
	if (ret < 0) {
		afs_error(aca, "could not read mood definition\n");
		return ret;
	}
	*si = new_mood_instance(mood_name);
	PARA_INFO_LOG("loading mood %s\n", mood_name);
	ret = mp_init(mood_def.data, mood_def.size, &(*si)->parser_context, &err);
	osl_close_disk_object(&mood_def);
	if (ret < 0) {
		afs_error(aca, "cannot init mood %s: %s\n", mood_name, err);
		free(err);
		mood_unload(*si);
	}
	return ret;
}

static int check_mood(struct osl_row *mood_row, void *data)
{
	struct afs_callback_arg *aca = data;
	char *mood_name, *errmsg;
	struct osl_object mood_def;
	struct selector_instance *si;
	int ret = mood_get_name_and_def_by_row(mood_row, &mood_name, &mood_def);

	if (ret < 0) {
		if (ret == osl(-E_OSL_EMPTY)) {
			para_printf(&aca->pbout, "not checking empty mood %s\n",
				mood_name);
			return 0;
		}
		para_printf(&aca->pbout, "cannot read mood: %s\n",
			para_strerror(-ret));
		return ret;
	}
	if (!*mood_name) /* ignore dummy row */
		goto out;
	para_printf(&aca->pbout, "checking mood %s\n", mood_name);
	si = new_mood_instance("check");
	ret = mp_init(mood_def.data, mood_def.size, &si->parser_context,
		&errmsg);
	if (ret < 0) {
		para_printf(&aca->pbout, "%s: %s\n%s\n", mood_name, errmsg,
			para_strerror(-ret));
		free(errmsg);
	} else
		mood_unload(si);
	ret = 1; /* don't fail the loop on invalid mood definitions */
out:
	osl_close_disk_object(&mood_def);
	return ret;
}

/*
 * Check all moods for syntax errors. Inconsistent mood definitions are
 * not considered an error.
 */
static int mood_check(struct afs_callback_arg *aca)
{
	para_printf(&aca->pbout, "checking moods...\n");
	return osl(osl_rbtree_loop(moods_table, BLOBCOL_ID, aca, check_mood));
}

/*
 * The normalized num_played and last_played values are defined as
 *
 *	nn := -(np - mean_n) / sigma_n and nl := -(lp - mean_l) / sigma_l
 *
 *  For a (hypothetical) file with np = 0 and lp = now we thus have
 *
 *	nn =  mean_n / sigma_n =: hn > 0
 *	nl = -(now - mean_l) / sigma_l =: hl < 0
 *
 * We design the score function so that for this hypothetical file both
 * contributions get the same weight. Define the np and lp score of an
 * arbitrary file as
 *
 *	sn := nn * -hl and sl := nl * hn
 *
 * The total score s := sn + sl has the representation
 *
 *	s = -cn * (np - mean_n) - cl * (lp - mean_l)
 *
 * with positive correction factors
 *
 *	cn = (now - mean_l) / (sqrt(ql) * sqrt(qn) / n)
 *	cl = mean_n / (sqrt(ql) * sqrt(qn) / n)
 *
 * where ql and qn are the quadratic deviations stored in the statistics
 * structure and n is the number of admissible files. To avoid integer
 * overflows and rounding errors we store the common divisor of the
 * correction factors separately.
 */
static long compute_score(struct afs_info *afsi,
		const struct afs_statistics *stats)
{
	int64_t mean_n, mean_l, score_n, score_l;

	if (stats->num == 0)
		return 0;
	assert(stats->normalization_divisor > 0);
	mean_n = stats->num_played_sum / stats->num;
	mean_l = stats->last_played_sum / stats->num;

	score_n = -((int64_t)afsi->num_played - mean_n)
		* stats->num_played_correction
		/ stats->normalization_divisor;
	score_l = -((int64_t)afsi->last_played - mean_l)
		* stats->last_played_correction
		/ stats->normalization_divisor;
	return (score_n + score_l) / 2;
}

/*
 * Given values a_1,...,a_n and a, their sum s=a_1+...+a_n, and the quadratic
 * deviation q=(a_1-s/n)^2+...+(a_n-s/n)^2, the quadratic deviation of the
 * extended sequence a_1,,,a_n,a is given by q + (s-n*a)^2/n/(n+1).
 */
static int add_afs_statistics(const struct osl_row *row,
		struct afs_statistics *stats)
{
	int64_t n, s, a;
	struct afs_info afsi;
	int ret;

	ret = get_afsi_of_row(row, &afsi);
	if (ret < 0)
		return ret;
	n = stats->num;

	/*
	 * We use a slightly different (but equivalent) variant of the above
	 * formula to avoid integer overflows.
	 */
	s = stats->last_played_sum;
	a = afsi.last_played;
	stats->last_played_qd += (n == 0)? 0 :
		(s / n - a) * (s / (n + 1) - a * n / (n + 1));
	stats->last_played_sum += a;

	s = stats->num_played_sum;
	a = afsi.num_played;
	stats->num_played_qd += (n == 0)? 0 :
		(s / n - a) * (s / (n + 1) - a * n / (n + 1));
	stats->num_played_sum += a;

	stats->num++;
	return 1;
}

/*
 * At mood load time we determine the set of admissible files for the given
 * mood where each file is identified by a pointer to a row of the audio file
 * table. In the first pass the pointers are added to a temporary array and
 * statistics are computed. When all admissible files have been processed in
 * this way, the score of each admissible file is computed and the (row, score)
 * pair is added to the score table. This has to be done in a second pass
 * since the score depends on the statistics. Finally, the array is freed.
 */
struct admissible_array {
	/* Files are admissible wrt. this mood. */
	struct selector_instance *si;
	/* The size of the array */
	unsigned size;
	/* Pointer to the array of admissible files. */
	struct osl_row **array;
};

/*
 * Check whether the given audio file is admissible. If it is, add it to array
 * of admissible files.
 */
static int add_if_admissible(struct osl_row *aft_row, void *data)
{
	struct admissible_array *aa = data;
	struct afs_statistics *stats = &aa->si->stats;

	if (!mp_eval_row(aft_row, aa->si->parser_context))
		return 0;
	if (stats->num >= aa->size) {
		aa->size *= 2;
		aa->size += 100;
		aa->array = arr_realloc(aa->array, aa->size,
			sizeof(struct osl_row *));
	}
	aa->array[stats->num] = aft_row;
	return add_afs_statistics(aft_row, stats);
}

static int update_audio_file(struct osl_row *aft_row)
{
	struct selector_instance *si = current_selector_instance;
	int ret;
	struct afs_info afsi;
	long score;

	if (!mp_eval_row(aft_row, si->parser_context))
		/* file is not admissible */
		return score_delete(aft_row, si->score_table);
	ret = score_move_to_end(aft_row, si->score_table);
	if (ret > 0) /* file was admissible and has been moved to the end */
		return 1;
	ret = get_afsi_of_row(aft_row, &afsi);
	if (ret < 0)
		return ret;
	score = compute_score(&afsi, &si->stats);
	return score_add(aft_row, score, si->score_table);
}

/* sse: seconds since epoch. */
static void print_statistics(struct selector_instance *si, int64_t sse,
		struct para_buffer *pb)
{
	unsigned n = si->stats.num;
	int mean_days, sigma_days;

	if (!pb)
		return;
	if (n == 0) {
		para_printf(pb, "no admissible files\n");
		return;
	}
	mean_days = (sse - si->stats.last_played_sum / n) / 3600 / 24;
	sigma_days = int_sqrt(si->stats.last_played_qd / n) / 3600 / 24;
	para_printf(pb,
		"loaded mood %s (%u files)\n"
		"last_played mean/sigma: %d/%d days\n"
		"num_played mean/sigma: %" PRId64 "/%" PRIu64 "\n"
		"correction factor ratio: %.2lf\n"
	,
		si->name? si->name : "(dummy)",
		n,
		mean_days, sigma_days,
		si->stats.num_played_sum / n,
		int_sqrt(si->stats.num_played_qd / n),
		86400.0 * si->stats.last_played_correction /
			si->stats.num_played_correction
	);
}

static void compute_correction_factors(int64_t sse, struct afs_statistics *s)
{
	if (s->num > 0) {
		s->normalization_divisor = int_sqrt(s->last_played_qd)
			* int_sqrt(s->num_played_qd) / s->num / 100;
		s->num_played_correction = sse - s->last_played_sum / s->num;
		s->last_played_correction = s->num_played_sum / s->num;
	}
	if (s->num_played_correction == 0)
		s->num_played_correction = 1;
	if (s->normalization_divisor == 0)
		s->normalization_divisor = 1;
	if (s->last_played_correction == 0)
		s->last_played_correction = 1;
}

/*
 * Populate a score table with admissible files for the given mood.
 *
 * This consults the mood table to initialize the mood parser with the mood
 * expression stored in the blob object which corresponds to the given name.
 *
 * A score table is allocated and populated with references to those entries
 * of the audio file table which evaluate as admissible with respect to the
 * mood expression. For each audio file a score value is computed and stored
 * along with the file reference.
 *
 * It is not considered an error if no files are admissible.
 */
static int mood_load(const char *mood_name, struct para_buffer *pbout,
		struct afs_callback_arg *aca, struct selector_instance **result)
{
	int ret;
	struct admissible_array aa = {.size = 0};
	/*
	 * We can not use the "now" pointer from sched.c here because we are
	 * called before schedule(), which initializes "now".
	 */
	struct timeval rnow;

	assert(result);
	if (mood_name) {
		ret = init_mood_parser(mood_name, aca, &aa.si);
		if (ret < 0)
			return ret;
	} else /* load dummy mood */
		aa.si = new_mood_instance(NULL);
	PARA_NOTICE_LOG("loading %s\n", mood_name? mood_name : "dummy");
	ret = audio_file_loop(&aa, add_if_admissible);
	if (ret < 0) {
		afs_error(aca, "audio file loop failed\n");
		goto out;
	}
	clock_get_realtime(&rnow);
	compute_correction_factors(rnow.tv_sec, &aa.si->stats);
	score_open(&aa.si->score_table);
	for (int i = 0; i < aa.si->stats.num; i++) {
		struct afs_info afsi;
		ret = get_afsi_of_row(aa.array[i], &afsi);
		if (ret < 0) {
			afs_error(aca, "could not load afsi\n");
			goto out;
		}
		ret = score_add(aa.array[i], compute_score(&afsi, &aa.si->stats),
			aa.si->score_table);
		if (ret < 0) {
			afs_error(aca, "could not add row to score table\n");
			goto out;
		}
	}
	/* success */
	print_statistics(aa.si, rnow.tv_sec, pbout);
	*result = aa.si;
	ret = 1;
out:
	free(aa.array);
	if (ret <= 0) /* error, or no admissible files */
		mood_unload(aa.si);
	return ret;
}


static int mood_loop(int (*cb)(struct osl_row *aft_row, long score, void *data),
		struct selector_instance *si, void *data)
{
	return score_loop(cb, si->score_table, data);
}

/*
 * Empty the score table and start over.
 *
 * This function is called on events which render the current set of admissible
 * files invalid, for example if an attribute is removed from the attribute
 * table.
 */
static int reload_current_mood(void)
{
	int ret;
	const char *name = current_selector_instance->name;
	struct selector_instance *si = new_mood_instance(name);

	PARA_NOTICE_LOG("reloading %s\n", name? name : "(dummy)");
	ret = mood_load(name, NULL, NULL, &si);
	if (ret < 0)
		return ret;
	mood_unload(current_selector_instance);
	current_selector_instance = si;
	return 1;
}

/**
 * Notification callback for the moods table.
 *
 * \param event Type of the event just occurred.
 * \param data Its type depends on the event.
 *
 * This function updates the score table according to the event that has
 * occurred. Two actions are possible: (a) reload the current mood, or (b)
 * add/remove/update the row of the score table which corresponds to the audio
 * file that has been modified or whose afs info has been changed. It depends
 * on the type of the event which action (if any) is performed.
 *
 * The callbacks of command handlers such as com_add() or com_touch() which
 * modify the audio file table call this function. The virtual streaming system
 * also calls this after it has updated the afs info of the file it is about to
 * stream (the one with the highest score). If the file stays admissible, its
 * score is recomputed so that a different file is picked next time.
 *
 * \return Standard.
 */
int moods_event_handler(enum afs_events event, void *data)
{
	if (!current_selector_instance || current_selector_id != SEL_MOOD)
		return 0;
	switch (event) {
	/*
	 * The three blob events might change the set of admissible files,
	 * so we must reload the score list.
	 */
	case BLOB_RENAME:
	case BLOB_REMOVE:
	case BLOB_ADD:
		if (data == moods_table || data == playlists_table)
			return 1; /* no reload necessary for these */
		return reload_current_mood();
	/* these also require reload of the score table */
	case ATTRIBUTE_ADD:
	case ATTRIBUTE_REMOVE:
	case ATTRIBUTE_RENAME:
		return reload_current_mood();
	/* changes to the aft only require to re-examine the audio file */
	case VSS_NEW_AUDIO_FILE:
	case AFSI_CHANGE:
	case AFHI_CHANGE:
	case AUDIO_FILE_RENAME:
	case AUDIO_FILE_ADD:
		return update_audio_file(data);
	case AUDIO_FILE_REMOVE:
		return score_delete(data, current_selector_instance->score_table);
	default:
		return 1;
	}
}

static int mood_get_best(struct osl_row **aft_row, long *score,
		struct selector_instance *si)
{
	return score_get_best(aft_row, score, si->score_table);
}

static int mood_invalidate(struct osl_row *aft_row, struct selector_instance *si)
{
	return score_delete(aft_row, si->score_table);
}

/**
 * Functions for mood handling.
 *
 * To activate a mood the mood selector reads a mood definition stored in the
 * mood blob table. An audio file is regarded as amissible if the resulting
 * mood expression evaluates as true.
 *
 * \sa \ref playlist_selector_operations.
 */
const struct selector_operations mood_selector_operations = {
	.load = mood_load,
	.loop = mood_loop,
	.unload = mood_unload,
	.check = mood_check,
	.get_best = mood_get_best,
	.invalidate = mood_invalidate,
};