8 /** \file mood.c Paraslash's mood handling functions. */
11 * Contains statistical data of the currently admissible audio files.
13 * It is used to assign normalized score values to each admissbile audio file.
15 struct afs_statistics {
16 /** sum of num played over all admissible files */
17 int64_t num_played_sum;
18 /** sum of last played times over all admissible files */
19 int64_t last_played_sum;
20 /** quadratic deviation of num played time */
21 int64_t num_played_qd;
22 /** quadratic deviation of last played time */
23 int64_t last_played_qd;
24 /** number of admissible files */
27 struct afs_statistics statistics;
30 * Assign scores according to a mood_method.
32 * Each mood_method has its own mood_score_function. The first parameter passed
33 * to that function is a pointer to a row of the audio file table. It
34 * determines the audio file for which a score is to be assigned. The second
35 * argument depends on the mood method this function is used for. It usually is
36 * the argument given at the end of a mood line.
38 * Mood score functions must return values between -100 and +100 inclisively.
39 * Boolean score functions should always return either -100 or +100.
41 * \sa struct mood_method, mood_parser.
43 typedef int mood_score_function(const struct osl_row*, void *);
46 * Preprocess a mood line.
48 * The mood_parser of a mood_method is called once at mood open time for each
49 * line of the current mood definition that contains the mood_method's name as
50 * a keyword. The line is passed to the mood_parser as the first argument. The
51 * mood_parser must determine whether the line is syntactically correct and
52 * return a positive value if so and a negative value otherwise.
54 * Some mood parsers preprocess the data given in the mood line to compute a
55 * structure which depends of the particular mood_method and which is used
56 * later in the mood_score_function of the mood_method. The mood_parser may
57 * store a pointer to its structure via the second argument.
59 * \sa mood_open(), mood_cleanup_function, mood_score_function.
61 typedef int mood_parser(const char *, void **);
64 * Deallocate resources which were allocated by the mood_parser.
66 * This optional function of a mood_method is used to free any resources
67 * allocated in mood_open() by the mood_parser. The argument passed is a
68 * pointer to the mood_method specific data structure that was returned by the
73 typedef void mood_cleanup_function(void *);
76 * Used for scoring and to determine whether a file is admissible.
79 /* The name of the method. */
81 /** Pointer to the mood parser. */
83 /** Pointer to the score function */
84 mood_score_function *score_function;
85 /** Optional cleanup function. */
86 mood_cleanup_function *cleanup;
90 * Each line of the current mood corresponds to a mood_item.
93 /** The method this line is referring to. */
94 const struct mood_method *method;
95 /** The data structure computed by the mood parser. */
97 /** The given score value, or zero if none was given. */
99 /** Non-zero if random scoring was requested. */
101 /** Whether the "not" keyword was given in the mood line. */
103 /** The position in the list of items. */
104 struct list_head mood_item_node;
108 * Created from the mood definition by mood_open().
110 * When a mood is opened, each line of its definition is investigated, and a
111 * corresponding mood item is produced. Each mood line starts with \p accept,
112 * \p deny, or \p score which determins the type of the mood line. For each
113 * such type a linked list is maintained whose entries are the mood items.
115 * \sa mood_item, mood_open().
118 /** the name of this mood */
120 /** The list of mood items of type \p accept. */
121 struct list_head accept_list;
122 /** The list of mood items of type \p deny. */
123 struct list_head deny_list;
124 /** The list of mood items of type \p score. */
125 struct list_head score_list;
128 static struct mood *current_mood;
131 * Rough approximation to sqrt.
133 * \param x Integer of which to calculate the sqrt.
135 * \return An integer res with res * res <= x.
137 static uint64_t int_sqrt(uint64_t x)
139 uint64_t op, res, one = 1;
148 if (op >= res + one) {
149 op = op - (res + one);
155 // PARA_NOTICE_LOG("sqrt(%llu) = %llu\n", x, res);
159 static int mm_played_rarely_score_function(const struct osl_row *row,
160 __a_unused void *ignored)
162 struct afs_info afsi;
164 int ret = get_afsi_of_row(row, &afsi);
168 ret = get_num_admissible_files(&num);
171 if (statistics.num_played_sum - num * afsi.num_played
172 > int_sqrt(statistics.num_played_qd * num))
177 static int mm_played_rarely_parser(const char *arg, __a_unused void **ignored)
180 PARA_WARNING_LOG("ignored junk at eol: %s\n", arg);
184 static int mm_name_like_score_function(const struct osl_row *row, void *preg)
187 int ret = get_audio_file_path_of_row(row, &path);
191 ret = regexec((regex_t *)preg, path, 42, NULL, 0);
192 return (ret == REG_NOMATCH)? -100 : 100;
195 static int mm_name_like_parser(const char *arg, void **regex)
197 regex_t *preg = para_malloc(sizeof(*preg));
198 int ret = regcomp(preg, arg, REG_NOSUB);
202 return -E_MOOD_REGEX;
208 static void mm_name_like_cleanup(void *preg)
214 static int mm_is_set_parser(const char *arg, void **bitnum)
216 unsigned char *c = para_malloc(1);
217 int ret = get_attribute_bitnum_by_name(arg, c);
226 static int mm_is_set_score_function(const struct osl_row *row, void *bitnum)
228 unsigned char *bn = bitnum;
229 struct afs_info afsi;
230 int ret = get_afsi_of_row(row, &afsi);
234 if (afsi.attributes & (1ULL << *bn))
239 /* returns 1 if row matches score item, -1 otherwise */
240 static int add_item_score(const void *row, struct mood_item *item, long *score,
245 *score_arg_sum += item->random_score? 100 : PARA_ABS(item->score_arg);
247 ret = item->method->score_function(row, item->parser_data);
248 if ((ret < 0 && !item->logical_not) || (ret >= 0 && item->logical_not))
249 return -1; /* no match */
251 if (item->random_score)
252 *score += PARA_ABS(ret) * para_random(100);
254 *score += PARA_ABS(ret) * item->score_arg;
258 static int compute_mood_score(const void *row, long *result)
260 struct mood_item *item;
262 long score_arg_sum = 0, score = 0;
266 /* reject audio file if it matches any entry in the deny list */
267 list_for_each_entry(item, ¤t_mood->deny_list, mood_item_node)
268 if (add_item_score(row, item, &score, &score_arg_sum) > 0)
269 return -E_NOT_ADMISSIBLE;
270 list_for_each_entry(item, ¤t_mood->accept_list, mood_item_node)
271 if (add_item_score(row, item, &score, &score_arg_sum) > 0)
273 /* reject if there is no matching entry in the accept list */
274 if (!match && !list_empty(¤t_mood->accept_list))
275 return -E_NOT_ADMISSIBLE;
276 list_for_each_entry(item, ¤t_mood->score_list, mood_item_node)
277 add_item_score(row, item, &score, &score_arg_sum);
279 score /= score_arg_sum;
284 static const struct mood_method mood_methods[] = {
286 .parser = mm_played_rarely_parser,
287 .score_function = mm_played_rarely_score_function,
288 .name = "played_rarely"
291 .parser = mm_is_set_parser,
292 .score_function = mm_is_set_score_function,
296 .parser = mm_name_like_parser,
297 .score_function = mm_name_like_score_function,
298 .cleanup = mm_name_like_cleanup,
306 static void cleanup_list_entry(struct mood_item *item)
308 if (item->method && item->method->cleanup)
309 item->method->cleanup(item->parser_data);
311 free(item->parser_data);
312 list_del(&item->mood_item_node);
316 static void destroy_mood(struct mood *m)
318 struct mood_item *tmp, *item;
322 list_for_each_entry_safe(item, tmp, &m->accept_list, mood_item_node)
323 cleanup_list_entry(item);
324 list_for_each_entry_safe(item, tmp, &m->deny_list, mood_item_node)
325 cleanup_list_entry(item);
326 list_for_each_entry_safe(item, tmp, &m->score_list, mood_item_node)
327 cleanup_list_entry(item);
332 static struct mood *alloc_new_mood(const char *name)
334 struct mood *m = para_calloc(sizeof(struct mood));
335 m->name = para_strdup(name);
336 INIT_LIST_HEAD(&m->accept_list);
337 INIT_LIST_HEAD(&m->deny_list);
338 INIT_LIST_HEAD(&m->score_list);
342 /** The different types of a mood line. */
343 enum mood_line_type {
355 * <accept [with score <score>] | deny [with score <score>] | score <score>>
356 * [if] [not] <mood_method> [options]
357 * <score> is either an integer or "random" which assigns a random score to
361 /* TODO: Use current_mood as private_data*/
362 static int parse_mood_line(char *mood_line, __a_unused void *private_data)
369 enum mood_line_type mlt = ML_INVALID;
370 struct mood_item *mi = NULL;
371 struct mood *m = current_mood;
372 char *buf = para_strdup(mood_line);
374 num_words = split_args(buf, &argv, delim);
376 if (!num_words) /* empty line */
379 if (**w == '#') /* comment */
381 if (!strcmp(*w, "accept"))
383 else if (!strcmp(*w, "deny"))
385 else if (!strcmp(*w, "score"))
387 ret = -E_MOOD_SYNTAX;
388 if (mlt == ML_INVALID)
390 mi = para_calloc(sizeof(struct mood_item));
391 if (mlt != ML_SCORE) {
392 ret = -E_MOOD_SYNTAX;
396 if (!strcmp(*w, "with")) {
402 if (mlt == ML_SCORE || !strcmp(*w, "score")) {
403 ret = -E_MOOD_SYNTAX;
407 if (strcmp(*w, "random")) {
408 mi->random_score = 0;
409 ret = para_atol(*w, &mi->score_arg);
413 mi->random_score = 1;
415 goto success; /* the line "score random" is valid */
419 ret = -E_MOOD_SYNTAX;
423 if (!strcmp(*w, "if")) {
424 ret = -E_MOOD_SYNTAX;
429 if (!strcmp(*w, "not")) {
430 ret = -E_MOOD_SYNTAX;
437 for (i = 0; mood_methods[i].parser; i++) {
438 if (strcmp(*w, mood_methods[i].name))
442 ret = -E_MOOD_SYNTAX;
443 if (!mood_methods[i].parser)
446 ret = mood_methods[i].parser(*w, &mi->parser_data);
449 mi->method = &mood_methods[i];
451 if (mlt == ML_ACCEPT)
452 para_list_add(&mi->mood_item_node, &m->accept_list);
453 else if (mlt == ML_DENY)
454 para_list_add(&mi->mood_item_node, &m->deny_list);
456 para_list_add(&mi->mood_item_node, &m->score_list);
457 PARA_DEBUG_LOG("%s entry added, method: %p\n", mlt == ML_ACCEPT? "accept" :
458 (mlt == ML_DENY? "deny" : "score"), mi->method);
466 free(mi->parser_data);
472 static int load_mood(const void *row)
475 struct mood *new_mood, *old_mood = current_mood;
476 struct osl_object objs[NUM_BLOB_COLUMNS];
478 ret = osl_get_object(moods_table, row, BLOBCOL_NAME, &objs[BLOBCOL_NAME]);
481 if (objs[BLOBCOL_NAME].size <= 1)
483 ret = osl_open_disk_object(moods_table, row, BLOBCOL_DEF, &objs[BLOBCOL_DEF]);
486 new_mood = alloc_new_mood((char*)objs[BLOBCOL_NAME].data);
487 current_mood = new_mood;
488 ret = for_each_line_ro(objs[BLOBCOL_DEF].data, objs[BLOBCOL_DEF].size,
489 parse_mood_line, NULL);
490 osl_close_disk_object(&objs[BLOBCOL_DEF]);
492 PARA_ERROR_LOG("unable to load mood %s: %d\n",
493 (char *)objs[BLOBCOL_NAME].data, ret);
494 destroy_mood(new_mood);
495 current_mood = old_mood;
498 destroy_mood(old_mood);
499 current_mood = new_mood;
500 PARA_INFO_LOG("loaded mood %s\n", current_mood->name);
504 /* returns -E_MOOD_LOADED on _success_ to terminate the loop */
505 static int mood_loop(struct osl_row *row, __a_unused void *private_data)
507 int ret = load_mood(row);
509 if (ret != -E_DUMMY_ROW)
510 PARA_NOTICE_LOG("invalid mood (%d), trying next mood\n", ret);
513 return -E_MOOD_LOADED;
516 static int load_first_available_mood(void)
518 int ret = osl_rbtree_loop(moods_table, BLOBCOL_NAME, NULL,
520 if (ret == -E_MOOD_LOADED) /* success */
523 return ret; /* error */
524 PARA_NOTICE_LOG("no valid mood found\n");
529 static unsigned int_log2(uint64_t x)
541 static int64_t normalized_value(int64_t x, int64_t n, int64_t sum, int64_t qd)
545 return 100 * (n * x - sum) / (int64_t)int_sqrt(n * qd);
548 static long compute_num_played_score(struct afs_info *afsi)
550 return -normalized_value(afsi->num_played, statistics.num,
551 statistics.num_played_sum, statistics.num_played_qd);
554 static long compute_last_played_score(struct afs_info *afsi)
556 return -normalized_value(afsi->last_played, statistics.num,
557 statistics.last_played_sum, statistics.last_played_qd);
560 static long compute_dynamic_score(const struct osl_row *aft_row)
562 struct afs_info afsi;
563 int64_t score, nscore = 0, lscore = 0;
566 ret = get_afsi_of_row(aft_row, &afsi);
569 nscore = compute_num_played_score(&afsi);
570 lscore = compute_last_played_score(&afsi);
571 score = nscore + lscore;
575 static int add_afs_statistics(const struct osl_row *row)
578 struct afs_info afsi;
581 ret = get_afsi_of_row(row, &afsi);
585 x = afsi.last_played;
586 s = statistics.last_played_sum;
588 statistics.last_played_qd += (x - s / n) * (x - s / n) * n / (n + 1);
589 statistics.last_played_sum += x;
592 s = statistics.num_played_sum;
594 statistics.num_played_qd += (x - s / n) * (x - s / n) * n / (n + 1);
595 statistics.num_played_sum += x;
600 static int del_afs_statistics(const struct osl_row *row)
602 uint64_t n, s, q, a, new_s;
603 struct afs_info afsi;
605 ret = get_afsi_of_row(row, &afsi);
611 memset(&statistics, 0, sizeof(statistics));
615 s = statistics.last_played_sum;
616 q = statistics.last_played_qd;
617 a = afsi.last_played;
619 statistics.last_played_sum = new_s;
620 statistics.last_played_qd = q + s * s / n - a * a
621 - new_s * new_s / (n - 1);
623 s = statistics.num_played_sum;
624 q = statistics.num_played_qd;
627 statistics.num_played_sum = new_s;
628 statistics.num_played_qd = q + s * s / n - a * a
629 - new_s * new_s / (n - 1);
636 * Structure used during mood_open().
638 * At mood open time, we look at each file in the audio file table in order to
639 * determine whether it is admissible. If a file happens to be admissible, its
640 * mood score is computed by calling each relevant mood_score_function. Next,
641 * we update the afs_statistics and add a struct admissible_file_info to a
644 * If all files have been processed that way, the final score of each
645 * admissible file is computed by adding the dynamic score (which depends on
646 * the afs_statistics) to the mood score. Finally, all audio files in the
647 * array are added to the score table and the admissible array is freed.
649 * \sa mood_method, admissible_array.
651 struct admissible_file_info
653 /** The admissible audio file. */
659 /** The temporary array of admissible files. */
660 struct admissible_array {
661 /** The size of the array */
663 /** Pointer to the array of admissible files. */
664 struct admissible_file_info *array;
668 * Add an entry to the array of admissible files.
670 * \param aft_row The audio file to be added.
671 * \param private_data Pointer to a struct admissible_file_info.
673 * \return Negative on errors, positive on success.
675 static int add_if_admissible(struct osl_row *aft_row, void *private_data)
678 struct admissible_array *aa = private_data;
682 ret = compute_mood_score(aft_row, &score);
684 return (ret == -E_NOT_ADMISSIBLE)? 1 : ret;
685 if (statistics.num >= aa->size) {
688 aa->array = para_realloc(aa->array,
689 aa->size * sizeof(struct admissible_file_info));
691 aa->array[statistics.num].aft_row = aft_row;
692 aa->array[statistics.num].score = score;
693 ret = add_afs_statistics(aft_row);
700 * Compute the new quadratic deviation in case one element changes.
702 * \param n Number of elements.
703 * \param old_qd The quadratic deviation before the change.
704 * \param old_val The value that was repaced.
705 * \param new_val The replacement value.
706 * \param old_sum The sum of all elements before the update.
708 * \return The new quadratic deviation resulting from replacing old_val
711 * Given n real numbers a_1, ..., a_n, their sum S = a_1 + ... + a_n,
712 * their quadratic deviation
714 * q = (a_1 - S/n)^2 + ... + (a_n - S/n)^2,
716 * and a real number b, the quadratic deviation q' of a_1,...a_{n-1}, b (ie.
717 * the last number a_n was replaced by b) may be computed in O(1) time in terms
718 * of n, q, a_n, b, and S as
720 * q' = q + d * s - (2 * S + d) * d / n,
722 * where d = b - a_n, and s = b + a_n.
724 * Example: n = 3, a_1 = 3, a_2 = 5, a_3 = 7, b = 10. Then S = 15, q = 8, d = 3,
727 * q + d * s - (2 * S + d) * d / n = 8 + 51 - 33 = 26,
729 * which equals q' = (3 - 6)^2 + (5 - 6)^2 + (10 - 6)^2.
732 _static_inline_ int64_t update_quadratic_deviation(int64_t n, int64_t old_qd,
733 int64_t old_val, int64_t new_val, int64_t old_sum)
735 int64_t delta = new_val - old_val;
736 int64_t sigma = new_val + old_val;
737 return old_qd + delta * sigma - (2 * old_sum + delta) * delta / n;
740 static int update_afs_statistics(struct afs_info *old_afsi, struct afs_info *new_afsi)
743 int ret = get_num_admissible_files(&n);
749 statistics.last_played_qd = update_quadratic_deviation(n,
750 statistics.last_played_qd, old_afsi->last_played,
751 new_afsi->last_played, statistics.last_played_sum);
752 statistics.last_played_sum += new_afsi->last_played - old_afsi->last_played;
754 statistics.num_played_qd = update_quadratic_deviation(n,
755 statistics.num_played_qd, old_afsi->num_played,
756 new_afsi->num_played, statistics.num_played_sum);
757 statistics.num_played_sum += new_afsi->num_played - old_afsi->num_played;
761 static int add_to_score_table(const struct osl_row *aft_row, long mood_score)
763 long score = (compute_dynamic_score(aft_row) + mood_score) / 3;
764 return score_add(aft_row, score);
767 static int delete_from_statistics_and_score_table(const struct osl_row *aft_row)
769 int ret = del_afs_statistics(aft_row);
772 return score_delete(aft_row);
776 * Delete one entry from the statitics and from the score table.
778 * \param aft_row The audio file which is no longer admissible.
780 * \return Positive on success, negative on errors.
782 * \sa score_delete(), mood_update_audio_file().
784 int mood_delete_audio_file(const struct osl_row *aft_row)
788 ret = row_belongs_to_score_table(aft_row);
791 if (!ret) /* not admissible, nothing to do */
793 return delete_from_statistics_and_score_table(aft_row);
797 * Compute the new score of an audio file.
799 * \param aft_row Determines the audio file.
800 * \param old_afsi The audio file selector info before updating.
802 * The \a old_afsi argument may be \p NULL which indicates that no changes to
803 * the audio file info were made.
805 * \return Positive on success, negative on errors.
807 int mood_update_audio_file(const struct osl_row *aft_row, struct afs_info *old_afsi)
810 int ret, is_admissible, was_admissible = 0;
811 struct afs_info afsi;
814 return 1; /* nothing to do */
815 ret = row_belongs_to_score_table(aft_row);
818 was_admissible = ret;
819 ret = compute_mood_score(aft_row, &score);
820 is_admissible = (ret > 0);
821 if (!was_admissible && !is_admissible)
823 if (was_admissible && !is_admissible)
824 return delete_from_statistics_and_score_table(aft_row);
825 if (!was_admissible && is_admissible) {
826 ret = add_afs_statistics(aft_row);
829 return add_to_score_table(aft_row, score);
832 ret = get_afsi_of_row(aft_row, &afsi);
836 ret = update_afs_statistics(old_afsi, &afsi);
840 score += compute_num_played_score(&afsi);
841 score += compute_last_played_score(&afsi);
843 PARA_NOTICE_LOG("score: %li\n", score);
844 percent = (score + 100) / 3;
847 else if (percent < 0)
849 PARA_NOTICE_LOG("re-inserting at %lu%%\n", percent);
850 return score_update(aft_row, percent);
853 static void log_statistics(void)
855 unsigned n = statistics.num;
858 PARA_NOTICE_LOG("no admissible files\n");
861 PARA_NOTICE_LOG("last_played mean: %lli, last_played sigma: %llu\n",
862 (long long int)(statistics.last_played_sum / n),
863 (long long unsigned)int_sqrt(statistics.last_played_qd / n));
864 PARA_NOTICE_LOG("num_played mean: %lli, num_played sigma: %llu\n",
865 (long long int)statistics.num_played_sum / n,
866 (long long unsigned)int_sqrt(statistics.num_played_qd / n));
870 * Open the given mood.
872 * \param mood_name The name of the mood to open.
874 * There are two special cases: If \a mood_name is \a NULL, load the
875 * first available mood. If \a mood_name is the empty string "", load
876 * the dummy mood that accepts every audio file and uses a scoring method
877 * based only on the \a last_played information.
879 * \return Positive on success, negative on errors. Loading the dummy mood
882 * \sa struct admissible_file_info, struct admissible_array, struct
883 * afs_info::last_played, mood_close().
885 int mood_open(char *mood_name)
888 struct admissible_array aa = {
894 ret = load_first_available_mood();
897 } else if (*mood_name) {
899 struct osl_object obj = {
901 .size = strlen(mood_name) + 1
903 ret = osl_get_row(moods_table, BLOBCOL_NAME, &obj, &row);
905 PARA_NOTICE_LOG("no such mood: %s\n", mood_name);
908 ret = load_mood(row);
912 destroy_mood(current_mood);
913 current_mood = alloc_new_mood("dummy");
915 PARA_NOTICE_LOG("loaded mood %s\n", current_mood->name);
916 PARA_INFO_LOG("%s\n", "computing statistics of admissible files");
917 ret = audio_file_loop(&aa, add_if_admissible);
921 PARA_NOTICE_LOG("%d admissible files \n", statistics.num);
922 for (i = 0; i < statistics.num; i++) {
923 struct admissible_file_info *a = aa.array + i;
924 ret = add_to_score_table(a->aft_row, a->score);
928 PARA_NOTICE_LOG("score add complete\n");
936 * Close the current mood.
938 * Free all resources of the current mood which were allocated during
941 void mood_close(void)
943 destroy_mood(current_mood);
945 memset(&statistics, 0, sizeof(statistics));
949 * Close and re-open the current mood.
951 * This function is used if changes to the audio file table or the
952 * attribute table were made that render the current list of admissible
953 * files useless. For example, if an attribute is removed from the
954 * attribute table, this function is called.
956 * \return Positive on success, negative on errors. If no mood is currently
957 * open, the function returns success.
959 * \sa mood_open(), mood_close().
961 int mood_reload(void)
969 mood_name = para_strdup(current_mood->name);
971 ret = mood_open(mood_name);