mood.c

   1 /* Copyright (C) 2007 Andre Noll <maan@tuebingen.mpg.de>, see file COPYING. */
   2
   3 /** \file mood.c Paraslash's mood handling functions. */
   4
   5 #include <regex.h>
   6 #include <osl.h>
   7 #include <lopsub.h>
   8
   9 #include "para.h"
  10 #include "error.h"
  11 #include "string.h"
  12 #include "afh.h"
  13 #include "afs.h"
  14 #include "list.h"
  15 #include "mood.h"
  16
  17 /*
  18  * Mood parser API. It's overkill to have an own header file for
  19  * these declarations as they are only needed in this .c file.
  20  */
  21 struct mp_context;
  22 int mp_init(const char *definition, int nbytes, struct mp_context **result,
  23                  char **errmsg);
  24 bool mp_eval_row(const struct osl_row *aft_row, struct mp_context *ctx);
  25 void mp_shutdown(struct mp_context *ctx);
  26
  27 /**
  28  * Contains statistical data of the currently admissible audio files.
  29  *
  30  * It is used to assign normalized score values to each admissible audio file.
  31  */
  32 struct afs_statistics {
  33         /** Sum of num played over all admissible files. */
  34         int64_t num_played_sum;
  35         /** Sum of last played times over all admissible files. */
  36         int64_t last_played_sum;
  37         /** Quadratic deviation of num played count. */
  38         int64_t num_played_qd;
  39         /** Quadratic deviation of last played time. */
  40         int64_t last_played_qd;
  41         /** Number of admissible files */
  42         unsigned num;
  43 };
  44 static struct afs_statistics statistics;
  45
  46 struct mood {
  47         /** The name of this mood. */
  48         char *name;
  49         /** Info for the bison parser. */
  50         struct mp_context *parser_context;
  51 };
  52
  53 /*
  54  * If current_mood is NULL then no mood is currently open. If
  55  * current_mood->name is NULL, the dummy mood is currently open.
  56  */
  57 static struct mood *current_mood;
  58
  59 /*
  60  * Find the position of the most-significant set bit.
  61  *
  62  * Copied and slightly adapted from the linux source tree, version 4.9.39
  63  * (2017-07).
  64  */
  65 __a_const static uint32_t fls64(uint64_t v)
  66 {
  67         int n = 63;
  68         const uint64_t ones = ~(uint64_t)0U;
  69
  70         if ((v & (ones << 32)) == 0) {
  71                 n -= 32;
  72                 v <<= 32;
  73         }
  74         if ((v & (ones << (64 - 16))) == 0) {
  75                 n -= 16;
  76                 v <<= 16;
  77         }
  78         if ((v & (ones << (64 - 8))) == 0) {
  79                 n -= 8;
  80                 v <<= 8;
  81         }
  82         if ((v & (ones << (64 - 4))) == 0) {
  83                 n -= 4;
  84                 v <<= 4;
  85         }
  86         if ((v & (ones << (64 - 2))) == 0) {
  87                 n -= 2;
  88                 v <<= 2;
  89         }
  90         if ((v & (ones << (64 - 1))) == 0)
  91                 n -= 1;
  92         return n;
  93 }
  94
  95 /*
  96  * Compute the integer square root floor(sqrt(x)).
  97  *
  98  * Taken 2007 from the linux source tree.
  99  */
 100 __a_const static uint64_t int_sqrt(uint64_t x)
 101 {
 102         uint64_t op = x, res = 0, one = 1;
 103
 104         one = one << (fls64(x) & ~one);
 105         while (one != 0) {
 106                 if (op >= res + one) {
 107                         op = op - (res + one);
 108                         res = res + 2 * one;
 109                 }
 110                 res /= 2;
 111                 one /= 4;
 112         }
 113         return res;
 114 }
 115
 116 /* returns 1 if row admissible, 0 if not, negative on errors */
 117 static int row_is_admissible(const struct osl_row *aft_row, struct mood *m)
 118 {
 119         if (!m)
 120                 return -E_NO_MOOD;
 121         return mp_eval_row(aft_row, m->parser_context);
 122 }
 123
 124 static void destroy_mood(struct mood *m)
 125 {
 126         if (!m)
 127                 return;
 128         mp_shutdown(m->parser_context);
 129         free(m->name);
 130         free(m);
 131 }
 132
 133 static struct mood *alloc_new_mood(const char *name)
 134 {
 135         struct mood *m = para_calloc(sizeof(struct mood));
 136         if (name)
 137                 m->name = para_strdup(name);
 138         return m;
 139 }
 140
 141 static int load_mood(const struct osl_row *mood_row, struct mood **m,
 142                 char **errmsg)
 143 {
 144         char *mood_name;
 145         struct osl_object mood_def;
 146         int ret;
 147
 148         ret = mood_get_name_and_def_by_row(mood_row, &mood_name, &mood_def);
 149         if (ret < 0) {
 150                 if (errmsg)
 151                         *errmsg = make_message(
 152                                 "could not read mood definition");
 153                 return ret;
 154         }
 155         assert(*mood_name);
 156         *m = alloc_new_mood(mood_name);
 157         PARA_INFO_LOG("opening mood %s\n", mood_name);
 158         ret = mp_init(mood_def.data, mood_def.size, &(*m)->parser_context, errmsg);
 159         osl_close_disk_object(&mood_def);
 160         return ret;
 161 }
 162
 163 static int check_mood(struct osl_row *mood_row, void *data)
 164 {
 165         struct para_buffer *pb = data;
 166         char *mood_name, *errmsg;
 167         struct osl_object mood_def;
 168         struct mood *m;
 169         int ret = mood_get_name_and_def_by_row(mood_row, &mood_name, &mood_def);
 170
 171         if (ret < 0) {
 172                 para_printf(pb, "cannot read mood\n");
 173                 return ret;
 174         }
 175         if (!*mood_name) /* ignore dummy row */
 176                 goto out;
 177         m = alloc_new_mood("check");
 178         ret = mp_init(mood_def.data, mood_def.size, &m->parser_context,
 179                 &errmsg);
 180         if (ret < 0) {
 181                 para_printf(pb, "%s: %s\n", mood_name, errmsg);
 182                 free(errmsg);
 183                 para_printf(pb, "%s\n", para_strerror(-ret));
 184         } else
 185                 destroy_mood(m);
 186         ret = 1; /* don't fail the loop on invalid mood definitions */
 187 out:
 188         osl_close_disk_object(&mood_def);
 189         return ret;
 190 }
 191
 192 /**
 193  * Check all moods for syntax errors.
 194  *
 195  * \param aca Only ->pbout is used for diagnostics.
 196  *
 197  * \return Negative on fatal errors. Inconsistent mood definitions are not
 198  * considered an error.
 199  */
 200 int mood_check_callback(struct afs_callback_arg *aca)
 201 {
 202         para_printf(&aca->pbout, "checking moods...\n");
 203         return osl(osl_rbtree_loop(moods_table, BLOBCOL_ID, &aca->pbout,
 204                 check_mood));
 205 }
 206
 207 static int64_t normalized_value(int64_t x, int64_t n, int64_t sum, int64_t qd)
 208 {
 209         if (!n || !qd)
 210                 return 0;
 211         return 100 * (n * x - sum) / (int64_t)int_sqrt(n) / (int64_t)int_sqrt(qd);
 212 }
 213
 214 static long compute_score(struct afs_info *afsi)
 215 {
 216         long score = -normalized_value(afsi->num_played, statistics.num,
 217                 statistics.num_played_sum, statistics.num_played_qd);
 218         score -= normalized_value(afsi->last_played, statistics.num,
 219                 statistics.last_played_sum, statistics.last_played_qd);
 220         return score / 2;
 221 }
 222
 223 static int add_afs_statistics(const struct osl_row *row)
 224 {
 225         uint64_t n, x, s, q;
 226         struct afs_info afsi;
 227         int ret;
 228
 229         ret = get_afsi_of_row(row, &afsi);
 230         if (ret < 0)
 231                 return ret;
 232         n = statistics.num;
 233         x = afsi.last_played;
 234         s = statistics.last_played_sum;
 235         if (n > 0) {
 236                 q = (x > s / n)? x - s / n : s / n - x;
 237                 statistics.last_played_qd += q * q * n / (n + 1);
 238         }
 239         statistics.last_played_sum += x;
 240
 241         x = afsi.num_played;
 242         s = statistics.num_played_sum;
 243         if (n > 0) {
 244                 q = (x > s / n)? x - s / n : s / n - x;
 245                 statistics.num_played_qd += q * q * n / (n + 1);
 246         }
 247         statistics.num_played_sum += x;
 248         statistics.num++;
 249         return 1;
 250 }
 251
 252 static int del_afs_statistics(const struct osl_row *row)
 253 {
 254         uint64_t n, s, q, a, new_s;
 255         struct afs_info afsi;
 256         int ret;
 257         ret = get_afsi_of_row(row, &afsi);
 258         if (ret < 0)
 259                 return ret;
 260         n = statistics.num;
 261         assert(n);
 262         if (n == 1) {
 263                 memset(&statistics, 0, sizeof(statistics));
 264                 return 1;
 265         }
 266
 267         s = statistics.last_played_sum;
 268         q = statistics.last_played_qd;
 269         a = afsi.last_played;
 270         new_s = s - a;
 271         statistics.last_played_sum = new_s;
 272         statistics.last_played_qd = q + s * s / n - a * a
 273                 - new_s * new_s / (n - 1);
 274
 275         s = statistics.num_played_sum;
 276         q = statistics.num_played_qd;
 277         a = afsi.num_played;
 278         new_s = s - a;
 279         statistics.num_played_sum = new_s;
 280         statistics.num_played_qd = q + s * s / n - a * a
 281                 - new_s * new_s / (n - 1);
 282
 283         statistics.num--;
 284         return 1;
 285 }
 286
 287 /*
 288  * At mood open time we determine the set of admissible files for the given
 289  * mood where each file is identified by a pointer to a row of the audio file
 290  * table. In the first pass the pointers are added to a temporary array and
 291  * statistics are computed. When all admissible files have been processed in
 292  * this way, the score of each admissible file is computed and the (row, score)
 293  * pair is added to the score table. This has to be done in a second pass
 294  * since the score depends on the statistics. Finally, the array is freed.
 295  */
 296 struct admissible_array {
 297         /** Files are admissible wrt. this mood. */
 298         struct mood *m;
 299         /** The size of the array */
 300         unsigned size;
 301         /** Pointer to the array of admissible files. */
 302         struct osl_row **array;
 303 };
 304
 305 /*
 306  * Check whether the given audio file is admissible. If it is, add it to array
 307  * of admissible files.
 308  */
 309 static int add_if_admissible(struct osl_row *aft_row, void *data)
 310 {
 311         struct admissible_array *aa = data;
 312         int ret;
 313
 314         ret = row_is_admissible(aft_row, aa->m);
 315         if (ret <= 0)
 316                 return ret;
 317         if (statistics.num >= aa->size) {
 318                 aa->size *= 2;
 319                 aa->size += 100;
 320                 aa->array = para_realloc(aa->array,
 321                         aa->size * sizeof(struct osl_row *));
 322         }
 323         aa->array[statistics.num] = aft_row;
 324         return add_afs_statistics(aft_row);
 325 }
 326
 327 /**
 328  * Compute the new quadratic deviation in case one element changes.
 329  *
 330  * \param n Number of elements.
 331  * \param old_qd The quadratic deviation before the change.
 332  * \param old_val The value that was replaced.
 333  * \param new_val The replacement value.
 334  * \param old_sum The sum of all elements before the update.
 335  *
 336  * \return The new quadratic deviation resulting from replacing old_val
 337  * by new_val.
 338  *
 339  * Given n real numbers a_1, ..., a_n, their sum S = a_1 + ... + a_n,
 340  * their quadratic deviation
 341  *
 342  * q = (a_1 - S/n)^2 + ... + (a_n - S/n)^2,
 343  *
 344  * and a real number b, the quadratic deviation q' of a_1,...a_{n-1}, b (ie.
 345  * the last number a_n was replaced by b) may be computed in O(1) time in terms
 346  * of n, q, a_n, b, and S as
 347  *
 348  *      q' = q + d * s - (2 * S + d) * d / n
 349  *         = q + d * (s - 2 * S / n - d /n),
 350  *
 351  * where d = b - a_n, and s = b + a_n.
 352  *
 353  * Example: n = 3, a_1 = 3, a_2 = 5, a_3 = 7, b = 10. Then S = 15, q = 8, d = 3,
 354  * s = 17, so
 355  *
 356  *      q + d * s - (2 * S + d) * d / n = 8 + 51 - 33 = 26,
 357  *
 358  * which equals q' = (3 - 6)^2 + (5 - 6)^2 + (10 - 6)^2.
 359  *
 360  */
 361 _static_inline_ int64_t update_quadratic_deviation(int64_t n, int64_t old_qd,
 362                 int64_t old_val, int64_t new_val, int64_t old_sum)
 363 {
 364         int64_t delta = new_val - old_val;
 365         int64_t sigma = new_val + old_val;
 366         return old_qd + delta * (sigma - 2 * old_sum / n - delta / n);
 367 }
 368
 369 static int update_afs_statistics(struct afs_info *old_afsi,
 370                 struct afs_info *new_afsi)
 371 {
 372         unsigned n;
 373         int ret = get_num_admissible_files(&n);
 374
 375         if (ret < 0)
 376                 return ret;
 377         assert(n);
 378
 379         statistics.last_played_qd = update_quadratic_deviation(n,
 380                 statistics.last_played_qd, old_afsi->last_played,
 381                 new_afsi->last_played, statistics.last_played_sum);
 382         statistics.last_played_sum += new_afsi->last_played - old_afsi->last_played;
 383
 384         statistics.num_played_qd = update_quadratic_deviation(n,
 385                 statistics.num_played_qd, old_afsi->num_played,
 386                 new_afsi->num_played, statistics.num_played_sum);
 387         statistics.num_played_sum += new_afsi->num_played - old_afsi->num_played;
 388         return 1;
 389 }
 390
 391 static int add_to_score_table(const struct osl_row *aft_row)
 392 {
 393         long score;
 394         struct afs_info afsi;
 395         int ret = get_afsi_of_row(aft_row, &afsi);
 396
 397         if (ret < 0)
 398                 return ret;
 399         score = compute_score(&afsi);
 400         return score_add(aft_row, score);
 401 }
 402
 403 static int delete_from_statistics_and_score_table(const struct osl_row *aft_row)
 404 {
 405         int ret = del_afs_statistics(aft_row);
 406         if (ret < 0)
 407                 return ret;
 408         return score_delete(aft_row);
 409 }
 410
 411 /**
 412  * Delete one entry from the statistics and from the score table.
 413  *
 414  * \param aft_row The audio file which is no longer admissible.
 415  *
 416  * \return Positive on success, negative on errors.
 417  *
 418  * \sa \ref score_delete().
 419  */
 420 static int mood_delete_audio_file(const struct osl_row *aft_row)
 421 {
 422         int ret;
 423
 424         ret = row_belongs_to_score_table(aft_row, NULL);
 425         if (ret < 0)
 426                 return ret;
 427         if (!ret) /* not admissible, nothing to do */
 428                 return 1;
 429         return delete_from_statistics_and_score_table(aft_row);
 430 }
 431
 432 /**
 433  * Compute the new score of an audio file wrt. the current mood.
 434  *
 435  * \param aft_row Determines the audio file.
 436  * \param old_afsi The audio file selector info before updating.
 437  *
 438  * The \a old_afsi argument may be \p NULL which indicates that no changes to
 439  * the audio file info were made.
 440  *
 441  * \return Positive on success, negative on errors.
 442  */
 443 static int mood_update_audio_file(const struct osl_row *aft_row,
 444                 struct afs_info *old_afsi)
 445 {
 446         long score, percent;
 447         int ret, is_admissible, was_admissible = 0;
 448         struct afs_info afsi;
 449         unsigned rank;
 450
 451         if (!current_mood)
 452                 return 1; /* nothing to do */
 453         ret = row_belongs_to_score_table(aft_row, &rank);
 454         if (ret < 0)
 455                 return ret;
 456         was_admissible = ret;
 457         ret = row_is_admissible(aft_row, current_mood);
 458         if (ret < 0)
 459                 return ret;
 460         is_admissible = (ret > 0);
 461         if (!was_admissible && !is_admissible)
 462                 return 1;
 463         if (was_admissible && !is_admissible)
 464                 return delete_from_statistics_and_score_table(aft_row);
 465         if (!was_admissible && is_admissible) {
 466                 ret = add_afs_statistics(aft_row);
 467                 if (ret < 0)
 468                         return ret;
 469                 return add_to_score_table(aft_row);
 470         }
 471         /* update score */
 472         ret = get_afsi_of_row(aft_row, &afsi);
 473         if (ret < 0)
 474                 return ret;
 475         if (old_afsi) {
 476                 ret = update_afs_statistics(old_afsi, &afsi);
 477                 if (ret < 0)
 478                         return ret;
 479         }
 480         score = compute_score(&afsi);
 481         PARA_DEBUG_LOG("score: %li\n", score);
 482         percent = (score + 100) / 3;
 483         if (percent > 100)
 484                 percent = 100;
 485         else if (percent < 0)
 486                 percent = 0;
 487         PARA_DEBUG_LOG("moving from rank %u to %li%%\n", rank, percent);
 488         return score_update(aft_row, percent);
 489 }
 490
 491 static void log_statistics(void)
 492 {
 493         unsigned n = statistics.num;
 494         int mean_days, sigma_days;
 495         /*
 496          * We can not use the "now" pointer from sched.c here because we are
 497          * called before schedule(), which initializes "now".
 498          */
 499         struct timeval rnow;
 500
 501         assert(current_mood);
 502         PARA_NOTICE_LOG("loaded mood %s\n", current_mood->name?
 503                 current_mood->name : "(dummy)");
 504         if (!n) {
 505                 PARA_WARNING_LOG("no admissible files\n");
 506                 return;
 507         }
 508         PARA_NOTICE_LOG("%u admissible files\n", statistics.num);
 509         clock_get_realtime(&rnow);
 510         mean_days = (rnow.tv_sec - statistics.last_played_sum / n) / 3600 / 24;
 511         sigma_days = int_sqrt(statistics.last_played_qd / n) / 3600 / 24;
 512         PARA_NOTICE_LOG("last_played mean/sigma: %d/%d days\n", mean_days, sigma_days);
 513         PARA_NOTICE_LOG("num_played mean/sigma: %llu/%llu\n",
 514                 (long long unsigned)statistics.num_played_sum / n,
 515                 (long long unsigned)int_sqrt(statistics.num_played_qd / n));
 516 }
 517
 518 /**
 519  * Close the current mood.
 520  *
 521  * Frees all resources of the current mood.
 522  */
 523 void close_current_mood(void)
 524 {
 525         destroy_mood(current_mood);
 526         current_mood = NULL;
 527         memset(&statistics, 0, sizeof(statistics));
 528 }
 529
 530 /**
 531  * Change the current mood.
 532  *
 533  * \param mood_name The name of the mood to open.
 534  * \param errmsg Error description is returned here.
 535  *
 536  * If \a mood_name is \a NULL, load the dummy mood that accepts every audio file
 537  * and uses a scoring method based only on the \a last_played information.
 538  *
 539  * The errmsg pointer may be NULL, in which case no error message will be
 540  * returned. If a non-NULL pointer is given, the caller must free *errmsg.
 541  *
 542  * If there is already an open mood, it will be closed first.
 543  *
 544  * \return Positive on success, negative on errors. Loading the dummy mood
 545  * always succeeds.
 546  *
 547  * \sa struct \ref afs_info::last_played, \ref mp_eval_row().
 548  */
 549 int change_current_mood(const char *mood_name, char **errmsg)
 550 {
 551         int i, ret;
 552         struct admissible_array aa = {
 553                 .size = 0,
 554                 .array = NULL
 555         };
 556
 557         if (mood_name) {
 558                 struct mood *m;
 559                 struct osl_row *row;
 560                 struct osl_object obj = {
 561                         .data = (char *)mood_name,
 562                         .size = strlen(mood_name) + 1
 563                 };
 564                 ret = osl(osl_get_row(moods_table, BLOBCOL_NAME, &obj, &row));
 565                 if (ret < 0) {
 566                         if (errmsg)
 567                                 *errmsg = make_message("no such mood: %s",
 568                                         mood_name);
 569                         return ret;
 570                 }
 571                 ret = load_mood(row, &m, errmsg);
 572                 if (ret < 0)
 573                         return ret;
 574                 close_current_mood();
 575                 current_mood = m;
 576         } else { /* load dummy mood */
 577                 close_current_mood();
 578                 current_mood = alloc_new_mood(NULL);
 579         }
 580         aa.m = current_mood;
 581         PARA_NOTICE_LOG("computing statistics of admissible files\n");
 582         ret = audio_file_loop(&aa, add_if_admissible);
 583         if (ret < 0) {
 584                 if (errmsg)
 585                         *errmsg = make_message("audio file loop failed");
 586                 return ret;
 587         }
 588         for (i = 0; i < statistics.num; i++) {
 589                 ret = add_to_score_table(aa.array[i]);
 590                 if (ret < 0) {
 591                         if (errmsg)
 592                                 *errmsg = make_message(
 593                                         "could not add row to score table");
 594                         goto out;
 595                 }
 596         }
 597         log_statistics();
 598         ret = statistics.num;
 599 out:
 600         free(aa.array);
 601         return ret;
 602 }
 603
 604 /*
 605  * Close and re-open the current mood.
 606  *
 607  * This function is called on events which render the current list of
 608  * admissible files useless, for example if an attribute is removed from the
 609  * attribute table.
 610  *
 611  * If no mood is currently open, the function returns success.
 612  */
 613 static int reload_current_mood(void)
 614 {
 615         int ret;
 616         char *mood_name = NULL;
 617
 618         ret = clear_score_table();
 619         if (ret < 0)
 620                 return ret;
 621         if (!current_mood)
 622                 return 1;
 623         PARA_NOTICE_LOG("reloading %s\n", current_mood->name?
 624                 current_mood->name : "(dummy)");
 625         if (current_mood->name)
 626                 mood_name = para_strdup(current_mood->name);
 627         close_current_mood();
 628         ret = change_current_mood(mood_name, NULL);
 629         free(mood_name);
 630         return ret;
 631 }
 632
 633 /**
 634  * Notification callback for the moods table.
 635  *
 636  * \param event Type of the event just occurred.
 637  * \param pb Unused.
 638  * \param data Its type depends on the event.
 639  *
 640  * This function performs actions required due to the occurrence of the given
 641  * event. Possible actions include reload of the current mood and update of the
 642  * score of an audio file.
 643  *
 644  * \return Standard.
 645  */
 646 int moods_event_handler(enum afs_events event, __a_unused struct para_buffer *pb,
 647                 void *data)
 648 {
 649         if (!current_mood)
 650                 return 0;
 651         switch (event) {
 652         /*
 653          * The three blob events might change the set of admissible files,
 654          * so we must reload the score list.
 655          */
 656         case BLOB_RENAME:
 657         case BLOB_REMOVE:
 658         case BLOB_ADD:
 659                 if (data == moods_table || data == playlists_table)
 660                         return 1; /* no reload necessary for these */
 661                 return reload_current_mood();
 662         /* these also require reload of the score table */
 663         case ATTRIBUTE_ADD:
 664         case ATTRIBUTE_REMOVE:
 665         case ATTRIBUTE_RENAME:
 666                 return reload_current_mood();
 667         /* changes to the aft only require to re-examine the audio file */
 668         case AFSI_CHANGE: {
 669                 struct afsi_change_event_data *aced = data;
 670                 return mood_update_audio_file(aced->aft_row, aced->old_afsi);
 671                 }
 672         case AFHI_CHANGE:
 673         case AUDIO_FILE_RENAME:
 674         case AUDIO_FILE_ADD:
 675                 return mood_update_audio_file(data, NULL);
 676         case AUDIO_FILE_REMOVE:
 677                 return mood_delete_audio_file(data);
 678         default:
 679                 return 1;
 680         }
 681 }