git.cworth.org Git - mnemon/blob - mnemon.c

   1 /*
   2  * Copyright © 2006 Carl Worth
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2, or (at your option)
   7  * any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
  17  */
  18
  19 /* for asprintf */
  20 #define _GNU_SOURCE
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <stdarg.h>
  24 #include <stdint.h>
  25 #include <math.h>
  26
  27 #include <sys/types.h>
  28 #include <sys/time.h>
  29 #include <sys/stat.h>
  30 #include <unistd.h>
  31 #include <dirent.h>
  32 #include <errno.h>
  33 #include <string.h>
  34 #include <assert.h>
  35
  36 #include <readline/readline.h>
  37 #include <readline/history.h>
  38
  39 #define ASSERT_NOT_REACHED              \
  40 do {                                    \
  41     static const int NOT_REACHED = 0;   \
  42     assert (NOT_REACHED);               \
  43 } while (0)
  44
  45 #define unused(foo) foo __attribute__((unused))
  46
  47 typedef int bool_t;
  48
  49 typedef struct _item {
  50     int score;
  51     char *challenge;
  52     char *response;
  53 } item_t;
  54
  55 typedef struct _bin {
  56     int score;
  57     int items_size;
  58     int num_items;
  59     item_t **items;
  60 } bin_t;
  61
  62 typedef enum {
  63     CATEGORY_ORDER_RANDOM,
  64     CATEGORY_ORDER_SEQUENTIAL
  65 } category_order_t;
  66
  67 typedef enum {
  68     CHALLENGE_TYPE_TEXT,
  69     CHALLENGE_TYPE_IMAGE,
  70     CHALLENGE_TYPE_AUDIO,
  71     CHALLENGE_TYPE_MIDI,
  72     CHALLENGE_TYPE_TEXT_TO_SPEECH
  73 } challenge_type_t;
  74
  75 typedef struct _category {
  76     char *name;
  77     int items_size;
  78     int num_items;
  79     item_t *items;
  80
  81     /* Support sequential introduction of items from bin 0 */
  82     category_order_t order;
  83     /* Support categories where responses are timed (0.0 == disable). */
  84     double time_limit;
  85     int bin_zero_head;
  86     /* Support challenges of non-text types (image, audio, etc.) */
  87     challenge_type_t challenge_type;
  88     /* Whether to repeat afterwards (for a little extra reinforcement) */
  89     bool_t repeat;
  90 } category_t;
  91
  92 typedef struct _mnemon {
  93     char *dir_name;
  94
  95     int categories_size;
  96     int num_categories;
  97     category_t *categories;
  98
  99     int bins_size;
 100     int num_bins;
 101     bin_t *bins;
 102
 103     int to_introduce;
 104     int to_master;
 105     int unlearned;
 106     int mastered;
 107 } mnemon_t;
 108
 109 static void *
 110 xmalloc (size_t size)
 111 {
 112     void *ret;
 113
 114     ret = malloc (size);
 115     if (ret == NULL) {
 116         fprintf (stderr, "Error: out of memory\n");
 117         exit (1);
 118     }
 119
 120     return ret;
 121 }
 122
 123 static void *
 124 xrealloc (void *ptr, size_t size)
 125 {
 126     void *ret;
 127
 128     ret = realloc (ptr, size);
 129     if (ret == NULL) {
 130         fprintf (stderr, "Error: out of memory\n");
 131         exit (1);
 132     }
 133
 134     return ret;
 135 }
 136
 137 static char *
 138 xstrdup (const char *s)
 139 {
 140     char *ret;
 141
 142     ret = strdup (s);
 143     if (ret == NULL) {
 144         fprintf (stderr, "Error: out of memory\n");
 145         exit (1);
 146     }
 147
 148     return ret;
 149 }
 150
 151 static char *
 152 xstrndup (const char *s, size_t n)
 153 {
 154     char *ret;
 155
 156     ret = strndup (s, n);
 157     if (ret == NULL) {
 158         fprintf (stderr, "Error: out of memory\n");
 159         exit (1);
 160     }
 161
 162     return ret;
 163 }
 164
 165 static void
 166 xasprintf (char **strp, const char *fmt, ...)
 167 {
 168     va_list ap;
 169     int ret;
 170
 171     va_start (ap, fmt);
 172     ret = vasprintf (strp, fmt, ap);
 173     va_end (ap);
 174
 175     if (ret < 0) {
 176         fprintf (stderr, "Error: out of memory\n");
 177         exit (1);
 178     }
 179 }
 180
 181 static void
 182 item_init (item_t       *item,
 183            int           score,
 184            const char   *challenge,
 185            const char   *response)
 186 {
 187     item->score = score;
 188
 189     item->challenge = xmalloc (strlen (challenge) + 1 +
 190                                strlen (response) + 1);
 191     item->response = item->challenge + strlen (challenge) + 1;
 192
 193     strcpy (item->challenge, challenge);
 194     strcpy (item->response, response);
 195 }
 196
 197 static void
 198 item_fini (item_t *item)
 199 {
 200     /* item->response shares allocation with item->challenge, so
 201      * doesn't require a separate call to free */
 202     free (item->challenge);
 203 }
 204
 205 static void
 206 category_init (category_t *category,
 207                const char *name)
 208 {
 209     category->name = xstrdup (name);
 210
 211     category->items_size = 0;
 212     category->num_items = 0;
 213     category->items = NULL;
 214     category->order = CATEGORY_ORDER_RANDOM;
 215     category->time_limit = 0.0;
 216     category->bin_zero_head = 0;
 217     category->challenge_type = CHALLENGE_TYPE_TEXT;
 218     category->repeat = 0;
 219 }
 220
 221 static void
 222 category_fini (category_t *category)
 223 {
 224     int i;
 225
 226     for (i = 0; i < category->num_items; i++)
 227         item_fini (&category->items[i]);
 228
 229     free (category->items);
 230
 231     free (category->name);
 232 }
 233
 234 static void
 235 category_grow (category_t *category)
 236 {
 237     if (category->items_size)
 238         category->items_size *= 2;
 239     else
 240         category->items_size = 1;
 241
 242     category->items = xrealloc (category->items,
 243                                 category->items_size * sizeof (item_t));
 244 }
 245
 246 static item_t *
 247 category_add_item (category_t   *category,
 248                    int           score,
 249                    const char   *challenge,
 250                    const char   *response)
 251 {
 252     item_t *item;
 253
 254     if (category->num_items == category->items_size)
 255         category_grow (category);
 256
 257     item = &category->items[category->num_items++];
 258
 259     item_init (item, score, challenge, response);
 260
 261     return item;
 262 }
 263
 264 static item_t *
 265 category_next_bin_zero_item (category_t *category)
 266 {
 267     int *i = &category->bin_zero_head;
 268
 269     for ( ; *i < category->num_items; *i = *i + 1)
 270         if (category->items[*i].score == 0)
 271             return &category->items[*i];
 272
 273     return NULL;
 274 }
 275
 276 static void
 277 category_print (category_t      *category,
 278                 FILE            *file)
 279 {
 280     int i;
 281     item_t *item;
 282
 283     fprintf (file, "order = %s\n\n",
 284             category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
 285     fprintf (file, "time = %f\n\n",
 286              category->time_limit);
 287
 288     fprintf (file, "challenge = ");
 289     switch (category->challenge_type) {
 290     case CHALLENGE_TYPE_TEXT:
 291         fprintf (file, "text");
 292         break;
 293     case CHALLENGE_TYPE_IMAGE:
 294         fprintf (file, "image");
 295         break;
 296     case CHALLENGE_TYPE_AUDIO:
 297         fprintf (file, "audio");
 298         break;
 299     case CHALLENGE_TYPE_MIDI:
 300         fprintf (file, "midi");
 301         break;
 302     case CHALLENGE_TYPE_TEXT_TO_SPEECH:
 303         fprintf (file, "text-to-speech");
 304         break;
 305     }
 306     fprintf (file, "\n\n");
 307
 308     fprintf (file, "repeat = %d\n\n", category->repeat);
 309
 310     for (i = 0; i < category->num_items; i++) {
 311         item = &category->items[i];
 312         if (i != 0)
 313             fprintf (file, "\n");
 314         fprintf (file, "%d\n%s\n%s\n",
 315                  item->score,
 316                  item->challenge,
 317                  item->response);
 318     }
 319 }
 320
 321 static void
 322 bin_init (bin_t *bin,
 323           int    score)
 324 {
 325     bin->score = score;
 326
 327     bin->items_size = 0;
 328     bin->num_items = 0;
 329     bin->items = NULL;
 330 }
 331
 332 static void
 333 bin_fini (bin_t *bin)
 334 {
 335     free (bin->items);
 336 }
 337
 338 static void
 339 bin_grow (bin_t *bin)
 340 {
 341     if (bin->items_size)
 342         bin->items_size *= 2;
 343     else
 344         bin->items_size = 1;
 345
 346     bin->items = xrealloc (bin->items,
 347                            bin->items_size * sizeof (item_t*));
 348 }
 349
 350 static void
 351 bin_add_item (bin_t     *bin,
 352               item_t    *item)
 353 {
 354     assert (item->score == bin->score);
 355
 356     if (bin->num_items == bin->items_size)
 357         bin_grow (bin);
 358
 359     bin->items[bin->num_items++] = item;
 360 }
 361
 362 static void
 363 bin_remove_item (bin_t  *bin,
 364                  int     item_index)
 365 {
 366     /* Replace the current item with the last item, (no need to shift
 367      * any more than that since we don't care about the order of the
 368      * items within a bin). */
 369     bin->num_items--;
 370     if (bin->num_items)
 371         bin->items[item_index] = bin->items[bin->num_items];
 372 }
 373
 374 /* Find the index for an item within a bin.
 375  *
 376  * XXX: This is currently a linear search, so is a potential
 377  * performance problem.
 378  */
 379 static int
 380 bin_item_index (bin_t   *bin,
 381                 item_t  *item)
 382 {
 383     int i;
 384
 385     for (i = 0; i < bin->num_items; i++)
 386         if (bin->items[i] == item)
 387             return i;
 388
 389     assert (0);
 390 }
 391
 392 typedef int (item_match_predicate_t) (void *closure, item_t *item);
 393
 394 /* Return the number of items in the bin from the given category (or
 395  * from all categories if category == NULL) */
 396 static int
 397 bin_num_items_matching (bin_t                   *bin,
 398                         item_match_predicate_t  *predicate,
 399                         void                    *closure)
 400 {
 401     int i, num_items = 0;
 402
 403     if (predicate == NULL)
 404         return bin->num_items;
 405
 406     for (i = 0; i < bin->num_items; i++)
 407         if ((predicate) (closure, bin->items[i]))
 408             num_items++;
 409
 410     return num_items;
 411 }
 412
 413 static void
 414 mnemon_init (mnemon_t *mnemon)
 415 {
 416     char *home;
 417
 418     home = getenv ("HOME");
 419     if (home == NULL)
 420         home = "";
 421
 422     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
 423
 424     mnemon->categories_size = 0;
 425     mnemon->num_categories = 0;
 426     mnemon->categories = NULL;
 427
 428     mnemon->bins_size = 0;
 429     mnemon->num_bins = 0;
 430     mnemon->bins = NULL;
 431
 432     mnemon->to_introduce = 10;
 433     mnemon->to_master = 10;
 434     mnemon->unlearned = 0;
 435     mnemon->mastered = -1;
 436 }
 437
 438 static void
 439 mnemon_fini (mnemon_t *mnemon)
 440 {
 441     int i;
 442
 443     for (i = 0; i < mnemon->num_bins; i++)
 444         bin_fini (&mnemon->bins[i]);
 445     free (mnemon->bins);
 446
 447     for (i = 0; i < mnemon->num_categories; i++)
 448         category_fini (&mnemon->categories[i]);
 449     free (mnemon->categories);
 450
 451     free (mnemon->dir_name);
 452 }
 453
 454 static void
 455 mnemon_categories_grow (mnemon_t *mnemon)
 456 {
 457     if (mnemon->categories_size)
 458         mnemon->categories_size *= 2;
 459     else
 460         mnemon->categories_size = 1;
 461
 462     mnemon->categories = xrealloc (mnemon->categories,
 463                                    mnemon->categories_size * sizeof (category_t));
 464 }
 465
 466 /* Get a category by name if it exists */
 467 static category_t *
 468 mnemon_get_category_if_exists (mnemon_t     *mnemon,
 469                                const char   *name)
 470 {
 471     int i;
 472
 473     for (i = 0; i < mnemon->num_categories; i++)
 474         if (strcmp (mnemon->categories[i].name, name) == 0)
 475             return &mnemon->categories[i];
 476
 477     return NULL;
 478 }
 479
 480 /* Get a category by name, creating new one if necessary. */
 481 static category_t *
 482 mnemon_get_category (mnemon_t   *mnemon,
 483                      const char *name)
 484 {
 485     category_t *category;
 486
 487     category = mnemon_get_category_if_exists (mnemon, name);
 488     if (category)
 489         return category;
 490
 491     mnemon_categories_grow (mnemon);
 492
 493     category = &mnemon->categories[mnemon->num_categories++];
 494
 495     category_init (category, name);
 496
 497     return category;
 498 }
 499
 500 static void
 501 mnemon_bins_grow (mnemon_t *mnemon)
 502 {
 503     if (mnemon->bins_size)
 504         mnemon->bins_size *= 2;
 505     else
 506         mnemon->bins_size = 1;
 507
 508     mnemon->bins = xrealloc (mnemon->bins,
 509                              mnemon->bins_size * sizeof (bin_t));
 510 }
 511
 512 static bin_t *
 513 mnemon_get_bin (mnemon_t        *mnemon,
 514                 int              score)
 515 {
 516     int i;
 517     bin_t *bin;
 518
 519     for (i = 0; i < mnemon->num_bins; i++)
 520         if (mnemon->bins[i].score == score)
 521             return &mnemon->bins[i];
 522         else if (mnemon->bins[i].score > score)
 523             break;
 524
 525     if (mnemon->num_bins == mnemon->bins_size)
 526         mnemon_bins_grow (mnemon);
 527
 528     bin = &mnemon->bins[i];
 529
 530     /* Make room to insert new bin at its sorted location. */
 531     if (i < mnemon->num_bins)
 532         memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
 533     mnemon->num_bins++;
 534
 535     bin_init (bin, score);
 536
 537     return bin;
 538 }
 539
 540 static void
 541 mnemon_remove_bin (mnemon_t     *mnemon,
 542                    bin_t        *bin)
 543 {
 544     int i = bin - mnemon->bins;
 545
 546     bin_fini (bin);
 547
 548     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
 549     mnemon->num_bins--;
 550 }
 551
 552 static void
 553 chomp (char *s)
 554 {
 555     int len = strlen (s);
 556     if (len == 0)
 557         return;
 558     if (s[len - 1] == '\n')
 559         s[len - 1] = '\0';
 560 }
 561
 562 static char *
 563 trim_space (char *string)
 564 {
 565     char *s;
 566
 567     s = string;
 568     while (*s && isspace (*s))
 569         s++;
 570
 571     string = s;
 572
 573     s = string + strlen (string) - 1;
 574     while (s > string && isspace (*s)) {
 575         *s = '\0';
 576         s--;
 577     }
 578
 579     return string;
 580 }
 581
 582 static void
 583 mnemon_load_category (mnemon_t          *mnemon,
 584                       const char        *name)
 585 {
 586     FILE *file;
 587     char *line = NULL, *end;
 588     size_t line_size = 0;
 589     ssize_t bytes_read;
 590     int line_count = 0;
 591     char *path;
 592     category_t *category;
 593     int i;
 594     struct stat st;
 595
 596     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
 597     sprintf (path, "%s/%s", mnemon->dir_name, name);
 598
 599     file = fopen (path, "r");
 600     if (file == NULL) {
 601         fprintf (stderr, "Error: Failed to open %s: %s\n",
 602                  path, strerror (errno));
 603         exit (1);
 604     }
 605
 606     fstat (fileno(file), &st);
 607     if (! S_ISREG(st.st_mode)) {
 608         fprintf (stderr, "Error: File %s is not a regular file.\n", path);
 609         exit (1);
 610     }
 611
 612     category = mnemon_get_category (mnemon, name);
 613
 614 #define READ_LINE do {                                  \
 615     bytes_read = getline (&line, &line_size, file);     \
 616     if (bytes_read == -1)                               \
 617         goto END_OF_FILE;                               \
 618     line_count++;                                       \
 619     chomp (line);                                       \
 620 } while (0)
 621
 622     /* Parse options */
 623     while (1) {
 624         char *name, *equal, *value;
 625
 626         /* Ignore blank lines */
 627         READ_LINE;
 628         if (*line == '\0')
 629             continue;
 630
 631         /* An initial digit means we hit an item. Trigger the
 632          * spaghetti machine. */
 633         if ((*line >= '0' && *line <= '9') || *line == '-')
 634             goto PARSE_BIN;
 635
 636         equal = strchr (line, '=');
 637         if (equal == NULL) {
 638             fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
 639                      line, path, line_count);
 640             exit (1);
 641         }
 642
 643         value = equal + 1;
 644         name = line;
 645         *equal = '\0';
 646
 647         name = trim_space (name);
 648         value = trim_space (value);
 649
 650         if (strcmp (name, "order") == 0) {
 651             if (strcmp (value, "sequential") == 0) {
 652                 category->order = CATEGORY_ORDER_SEQUENTIAL;
 653             } else if (strcmp (value, "random") == 0) {
 654                 category->order = CATEGORY_ORDER_RANDOM;
 655             } else {
 656                 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
 657                          value, path, line_count);
 658                 exit (1);
 659             }
 660         } else if (strcmp (name, "time") == 0) {
 661             double limit;
 662             char *end;
 663             limit = strtod (value, &end);
 664             while (isspace (*end))
 665                 end++;
 666             if (*end == '\0') {
 667                 category->time_limit = limit;
 668             } else {
 669                 fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
 670                          value, path, line_count);
 671                 exit (1);
 672             }
 673         } else if (strcmp (name, "challenge") == 0) {
 674             if (strcmp (value, "text") == 0) {
 675                 category->challenge_type = CHALLENGE_TYPE_TEXT;
 676             } else if (strcmp (value, "image") == 0) {
 677                 category->challenge_type = CHALLENGE_TYPE_IMAGE;
 678             } else if (strcmp (value, "audio") == 0) {
 679                 category->challenge_type = CHALLENGE_TYPE_AUDIO;
 680             } else if (strcmp (value, "midi") == 0) {
 681                 category->challenge_type = CHALLENGE_TYPE_MIDI;
 682             } else if (strcmp (value, "text-to-speech") == 0) {
 683                 category->challenge_type = CHALLENGE_TYPE_TEXT_TO_SPEECH;
 684             } else {
 685                 fprintf (stderr, "Unknown value for \"challenge\" option \"%s\" at %s:%d\n",
 686                          value, path, line_count);
 687                 exit (1);
 688             }
 689         } else if (strcmp (name, "repeat") == 0) {
 690             if (strcmp (value, "0") == 0)
 691                 category->repeat = 0;
 692             else
 693                 category->repeat = 1;
 694         } else {
 695             fprintf (stderr, "Unknown option %s at %s:%d\n",
 696                      name, path, line_count);
 697             exit (1);
 698         }
 699     }
 700
 701     /* Parse items */
 702     while (1) {
 703         int score;
 704         char *challenge, *response;
 705
 706         /* Ignore blank lines */
 707         READ_LINE;
 708         if (*line == '\0')
 709             continue;
 710
 711         /* Read bin number */
 712       PARSE_BIN:
 713         score = strtol (line, &end, 10);
 714         if (*end != '\0') {
 715             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
 716                      line, path, line_count);
 717             exit (1);
 718         }
 719
 720         /* Read challenge */
 721         READ_LINE;
 722         challenge = strdup (line);
 723
 724         /* Read response */
 725         READ_LINE;
 726         response = line;
 727
 728         category_add_item (category, score, challenge, response);
 729
 730         free (challenge);
 731     }
 732   END_OF_FILE:
 733
 734     free (line);
 735     fclose (file);
 736     free (path);
 737
 738     /* Resize category items to fit exactly. */
 739     category->items_size = category->num_items;
 740     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
 741
 742     /* Now that the category is completely loaded, with stable
 743      * pointers to every item, we can add each item to its appropriate
 744      * bin. */
 745     for (i = 0; i < category->num_items; i++) {
 746         item_t *item = &category->items[i];
 747         bin_t *bin = mnemon_get_bin (mnemon, item->score);
 748
 749         bin_add_item (bin, item);
 750     }
 751 }
 752
 753 static void
 754 mnemon_load (mnemon_t *mnemon)
 755 {
 756     DIR *dir;
 757     struct dirent *dirent;
 758
 759     dir = opendir (mnemon->dir_name);
 760     if (dir == NULL) {
 761         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
 762                  mnemon->dir_name, strerror (errno));
 763         exit (1);
 764     }
 765
 766     while (1) {
 767         dirent = readdir (dir);
 768         if (dirent == NULL)
 769             break;
 770
 771         if (dirent->d_type == DT_REG) {
 772             /* Ignore files matching *~, (yes, this shouldn't be
 773              * hard-coded in such an ad-hoc way, but there you go. */
 774             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
 775                 mnemon_load_category (mnemon, dirent->d_name);
 776         }
 777     }
 778
 779     closedir (dir);
 780 }
 781
 782 static void
 783 mnemon_save (mnemon_t *mnemon)
 784 {
 785     int i, err;
 786     char *filename, *lock_filename;
 787     FILE *file;
 788     category_t *category;
 789
 790     for (i = 0; i < mnemon->num_categories; i++) {
 791         category = &mnemon->categories[i];
 792
 793         xasprintf (&filename, "%s/%s",
 794                    mnemon->dir_name, category->name);
 795         xasprintf (&lock_filename, "%s/.#%s",
 796                    mnemon->dir_name, category->name);
 797
 798         file = fopen (lock_filename, "w");
 799         if (file == NULL) {
 800             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
 801                      lock_filename, strerror (errno));
 802             continue;
 803         }
 804
 805         category_print (category, file);
 806
 807         fsync (fileno (file));
 808         fclose (file);
 809
 810         err = rename (lock_filename, filename);
 811         if (err < 0) {
 812             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
 813                      lock_filename, filename, strerror (errno));
 814             continue;
 815         }
 816
 817         free (filename);
 818         free (lock_filename);
 819     }
 820 }
 821
 822 /* Return a uniformly-distributed pseudo-random integer within the
 823  * range:
 824  *
 825  *      0 <= result < num_values
 826  */
 827 static int
 828 rand_within (int num_values)
 829 {
 830     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
 831 }
 832
 833 /* Return an exponentially-distributed pseudo-random integer within
 834  * the range:
 835  *
 836  *      0 <= result < num_values
 837  *
 838  * The distribution is such that each successively larger value will
 839  * occur with a probability of half of the previous value.
 840  */
 841 static int
 842 rand_within_exponential (int num_values)
 843 {
 844     static int r;
 845     static uint32_t mask = 0;
 846     int ones;
 847     int bit;
 848
 849     /* Optimize the constant case. */
 850     if (num_values == 1)
 851         return 0;
 852
 853     ones = 0;
 854
 855     do {
 856         if (mask == 0) {
 857             r = rand ();
 858             mask = 1 << 31;
 859             while (mask > RAND_MAX)
 860                 mask >>= 1;
 861         }
 862         bit = r & mask;
 863         mask >>= 1;
 864         if (bit) {
 865             ones++;
 866             if (ones == num_values)
 867                 ones = 0;
 868         }
 869     } while (bit);
 870
 871     return ones;
 872 }
 873
 874 /* Find the category to which an item belongs. */
 875 static category_t *
 876 mnemon_item_category (mnemon_t  *mnemon,
 877                       item_t    *item)
 878 {
 879     category_t *category;
 880     int i, item_index;
 881
 882     for (i = 0; i < mnemon->num_categories; i++) {
 883         category = &mnemon->categories[i];
 884         item_index = item - category->items;
 885         if (item_index >= 0 && item_index < category->num_items)
 886             return category;
 887     }
 888
 889     assert (0);
 890 }
 891
 892 typedef struct _item_in_category_closure
 893 {
 894     mnemon_t *mnemon;
 895     category_t *category;
 896 } item_in_category_closure_t;
 897
 898 static int
 899 mnemon_item_in_category (void *closure, item_t *item)
 900 {
 901     item_in_category_closure_t *iicc = closure;
 902     mnemon_t *mnemon = iicc->mnemon;
 903     category_t *category = iicc->category;
 904
 905     return (mnemon_item_category (mnemon, item) == category);
 906 }
 907
 908 typedef struct _item_in_category_of_length_closure
 909 {
 910     mnemon_t *mnemon;
 911     category_t *category;
 912     int length;
 913 } item_in_category_of_length_closure_t;
 914
 915 static int
 916 mnemon_item_in_category_of_length (void *closure, item_t *item)
 917 {
 918     item_in_category_of_length_closure_t *iicolc = closure;
 919     mnemon_t *mnemon = iicolc->mnemon;
 920     category_t *category = iicolc->category;
 921     unsigned int length = iicolc->length;
 922
 923     if (mnemon_item_category (mnemon, item) != category)
 924         return 0;
 925
 926     return strlen (item->challenge) == length;
 927 }
 928
 929 static void
 930 mnemon_select_item (mnemon_t     *mnemon,
 931                     bin_t       **bin_ret,
 932                     int          *item_index_ret,
 933                     category_t  **category_ret)
 934 {
 935     int bin_index, item_index;
 936     bin_t *bin;
 937     item_t *item;
 938     category_t *category;
 939
 940     bin_index = rand_within_exponential (mnemon->num_bins);
 941     bin = &mnemon->bins[bin_index];
 942
 943     /* The most intuitive understanding of the to_introduce counter is
 944      * that it's tracking never-before-learned items as they are
 945      * pulled from the bin with score 0. But that bin can become
 946      * empty. So the refined rule is that we decrement to_introduce
 947      * whenever we pull from the lowest-indexed bin with a
 948      * non-negative score. */
 949     if (mnemon->to_introduce && bin->score >=0 &&
 950         (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
 951     {
 952         mnemon->to_introduce--;
 953     }
 954
 955     item_index = rand_within (bin->num_items);
 956
 957     item = bin->items[item_index];
 958     category = mnemon_item_category (mnemon, item);
 959
 960     if (bin->score == 0) {
 961         if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
 962             item = category_next_bin_zero_item (category);
 963             if (item)
 964                 item_index = bin_item_index (bin, item);
 965         }
 966     }
 967
 968     *bin_ret = bin;
 969     *item_index_ret = item_index;
 970     *category_ret = category;
 971 }
 972
 973
 974 #define HISTOGRAM_ROW_FORMAT "%3d: %3d"
 975 #define HISTOGRAM_BAR_WIDTH  63
 976
 977 static void
 978 print_histogram_bar (double     size,
 979                      double     max)
 980 {
 981     int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
 982     static char const *boxes[8] = {
 983         "█", "▉", "▊", "▋",
 984         "▌", "▍", "▎", "▏"
 985     };
 986
 987     while (size > units_per_cell) {
 988         printf(boxes[0]);
 989         size -= units_per_cell;
 990     }
 991
 992     size /= units_per_cell;
 993
 994     if (size > 7.5/8.0)
 995         printf(boxes[0]);
 996     else if (size > 6.5/8.0)
 997         printf(boxes[1]);
 998     else if (size > 5.5/8.0)
 999         printf(boxes[2]);
1000     else if (size > 4.5/8.0)
1001         printf(boxes[3]);
1002     else if (size > 3.5/8.0)
1003         printf(boxes[4]);
1004     else if (size > 2.5/8.0)
1005         printf(boxes[5]);
1006     else if (size > 1.5/8.0)
1007         printf(boxes[6]);
1008     else if (size > 0.5/8.0)
1009         printf(boxes[7]);
1010
1011     printf ("\n");
1012 }
1013
1014 static void
1015 mnemon_print_histogram (mnemon_t    *mnemon,
1016                         const char  *category_name,
1017                         int          length)
1018 {
1019     int i, last_score, max;
1020     category_t *category = NULL;
1021     bin_t *bin;
1022     int num_items;
1023     item_match_predicate_t *predicate = NULL;
1024     void *closure = NULL;
1025     item_in_category_closure_t item_in_category;
1026     item_in_category_of_length_closure_t item_in_category_of_length;
1027
1028     if (mnemon->num_bins == 0)
1029         return;
1030
1031     if (category_name) {
1032         category = mnemon_get_category_if_exists (mnemon, category_name);
1033         if (category) {
1034             if (length) {
1035                 predicate = mnemon_item_in_category_of_length;
1036                 item_in_category_of_length.mnemon = mnemon;
1037                 item_in_category_of_length.category = category;
1038                 item_in_category_of_length.length = length;
1039                 closure = &item_in_category_of_length;
1040             } else {
1041                 predicate = mnemon_item_in_category;
1042                 item_in_category.mnemon = mnemon;
1043                 item_in_category.category = category;
1044                 closure = &item_in_category;
1045             }
1046         }
1047     }
1048
1049     for (i = 0; i < mnemon->num_bins; i++) {
1050         num_items = bin_num_items_matching (&mnemon->bins[i],
1051                                             predicate, closure);
1052         if (i == 0 || num_items > max)
1053             max = num_items;
1054     }
1055
1056     for (i = 0; i < mnemon->num_bins; i++) {
1057         bin = &mnemon->bins[i];
1058         if (i != 0)
1059             while (bin->score - last_score > 1)
1060                 printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
1061         num_items = bin_num_items_matching (bin,
1062                                             predicate, closure);
1063         printf (HISTOGRAM_ROW_FORMAT " ", bin->score, num_items);
1064         print_histogram_bar (num_items, max);
1065         last_score = bin->score;
1066     }
1067 }
1068
1069 static void
1070 mnemon_handle_command (mnemon_t         *mnemon,
1071                        const char       *command)
1072 {
1073     const char *arg;
1074     int len;
1075     switch (command[0]) {
1076         /* 'h' for histogram */
1077         case 'h':
1078         {
1079             char *category = NULL;
1080             int length = 0;
1081
1082             arg = command + 1;
1083             arg += strspn (arg, " \t");
1084             len = strcspn (arg, " \t");
1085             if (len) {
1086                 category = xstrndup (arg, len);
1087                 arg += len;
1088                 arg += strspn (arg, " \t");
1089                 if (*arg)
1090                     length = atoi (arg);
1091             }
1092             mnemon_print_histogram (mnemon, category, length);
1093         }
1094         break;
1095         /* 'r' for repeat */
1096         case 'r':
1097         {
1098             /* Nothing necessary for repeating. */
1099         }
1100         break;
1101         default:
1102             printf ("Unknown command: %s\n", command);
1103             break;
1104     }
1105 }
1106
1107 static void
1108 mnemon_handle_response (mnemon_t        *mnemon,
1109                         bin_t           *bin,
1110                         int              item_index,
1111                         item_t          *item,
1112                         const char      *response,
1113                         double           response_time,
1114                         double           time_limit)
1115 {
1116     bool_t correct;
1117
1118     correct = (strcmp (response, item->response) == 0);
1119
1120     bin_remove_item (bin, item_index);
1121
1122     /* If the bin is now empty, we must remove it. Also if we just
1123      * picked the last word we'll ever pick from the bin with
1124      * score 0, then we can remove that as well. */
1125     if (bin->num_items == 0 ||
1126         (bin->score == 0 && mnemon->to_introduce == 0))
1127     {
1128         mnemon_remove_bin (mnemon, bin);
1129     }
1130
1131     if (correct &&
1132         (time_limit == 0.0 || response_time < time_limit))
1133     {
1134         item->score++;
1135         /* We reserve an item score of 0 for an item that has
1136          * never been asked. */
1137         if (item->score == 0) {
1138             item->score = 1;
1139             mnemon->unlearned--;
1140             printf ("You got it!");
1141         } else if (item->score < 0) {
1142             printf ("Yes---just give me %d more.",
1143                     - item->score);
1144         } else if (item->score == 1) {
1145             printf ("On your first try, no less!");
1146         } else {
1147             printf ("Masterful (%dx).", item->score);
1148             if (mnemon->to_master)
1149                 mnemon->to_master--;
1150         }
1151     } else {
1152         if (! correct)
1153             printf ("  %s is the correct answer.",
1154                     item->response);
1155         else
1156             printf ("Correct, but not quite quick enough (%0.2f seconds---needed %0.2f seconds)\n",
1157                     response_time, time_limit);
1158         /* Penalize an incorrect response by forcing the score
1159          * negative. */
1160         if (item->score >= 0) {
1161             if (item->score > 0)
1162                 printf (" Oops, you knew that, right? (%dx)\n ",
1163                         item->score);
1164             mnemon->unlearned++;
1165             /* We increase to_master here as an extra penalty. If the
1166              * user is forgetting stuff learned previously, then more
1167              * time should be spent on mastering than learning new
1168              * items. Note that we only do this during the initial
1169              * phase while new items are still being introduced. */
1170             if (mnemon->to_introduce)
1171                 mnemon->to_master++;
1172             /* We go to -2 to force a little extra reinforcement
1173              * when re-learning an item, (otherwise, it will often
1174              * get asked again immediately where it is easy to get
1175              * a correct response without any learning). */
1176             item->score = -2;
1177         } else {
1178             item->score--;
1179         }
1180     }
1181
1182     printf (" ");
1183     if (mnemon->to_introduce)
1184         printf ("%d to come. ", mnemon->to_introduce);
1185     if (mnemon->unlearned)
1186         printf ("%d still unlearned. ", mnemon->unlearned);
1187     if (mnemon->to_introduce == 0 && mnemon->to_master > 0)
1188         printf ("%d items to master", mnemon->to_master);
1189     printf ("\n\n");
1190
1191     bin = mnemon_get_bin (mnemon, item->score);
1192
1193     bin_add_item (bin, item);
1194 }
1195
1196 static void
1197 mnemon_show_challenge (mnemon_t *mnemon,
1198                        challenge_type_t challenge_type,
1199                        const char *challenge)
1200 {
1201     const char *program;
1202     char *command;
1203
1204     if (challenge_type == CHALLENGE_TYPE_TEXT) {
1205         printf ("%s\n", challenge);
1206         return;
1207     }
1208
1209     /* XXX: Yes, shelling out to system is total cheese. The planned
1210      * fix here is to bring graphical display in process, (or at least
1211      * have a custom external program that accepts image filenames on
1212      * stdin.
1213      */
1214     switch (challenge_type) {
1215     case CHALLENGE_TYPE_TEXT:
1216         ASSERT_NOT_REACHED;
1217         break;
1218     case CHALLENGE_TYPE_IMAGE:
1219         program = "xli -gamma 2.2";
1220         break;
1221     case CHALLENGE_TYPE_AUDIO:
1222         program = "play";
1223         break;
1224     case CHALLENGE_TYPE_MIDI:
1225         program = "timidity -Os";
1226         break;
1227     case CHALLENGE_TYPE_TEXT_TO_SPEECH:
1228         program = "mnemon-tts";
1229         break;
1230     }
1231
1232     xasprintf (&command, "%s %s/%s >/dev/null 2>&1 &",
1233                program,
1234                mnemon->dir_name,
1235                challenge);
1236     system (command);
1237     free (command);
1238 }
1239
1240 static void
1241 mnemon_hide_challenge (unused (mnemon_t *mnemon),
1242                        challenge_type_t challenge_type)
1243 {
1244     char * command;
1245
1246     if (challenge_type != CHALLENGE_TYPE_IMAGE)
1247         return;
1248
1249     /* XXX: And this is just embarrassing (obviously wrong in several
1250      * ways). Hopefully I'll amend away any commit that includes this.
1251      */
1252     xasprintf (&command, "killall xli");
1253     system (command);
1254     free (command);
1255 }
1256
1257 static void
1258 mnemon_do_challenges (mnemon_t *mnemon)
1259 {
1260     bin_t *bin;
1261     int item_index;
1262     item_t *item;
1263     category_t *category;
1264     char *response;
1265     int i;
1266
1267     /* Count the number of items with negative scores. */
1268     mnemon->unlearned = 0;
1269     for (i = 0; i < mnemon->num_bins; i++) {
1270         bin = &mnemon->bins[i];
1271         if (bin->score >= 0)
1272             break;
1273         mnemon->unlearned += bin->num_items;
1274     }
1275
1276     mnemon->to_introduce -= mnemon->unlearned;
1277     if (mnemon->to_introduce < 0)
1278         mnemon->to_introduce = 0;
1279
1280     /* Get rid of bin with score of 0 if we aren't going to be
1281      * introducing anything from it. */
1282     if (mnemon->to_introduce == 0) {
1283         bin = mnemon_get_bin (mnemon, 0);
1284         mnemon_remove_bin (mnemon, bin);
1285     }
1286
1287     if (mnemon->unlearned) {
1288         printf ("You've got %d items to learn already. ", mnemon->unlearned);
1289         if (mnemon->to_introduce)
1290             printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
1291         printf ("\n");
1292     } else {
1293         printf ("Introducing %d new items.\n", mnemon->to_introduce);
1294     }
1295     printf ("\n");
1296
1297     do {
1298         struct timeval start, end;
1299
1300         mnemon_select_item (mnemon, &bin, &item_index, &category);
1301         item = bin->items[item_index];
1302
1303         while (1) {
1304             if (category->time_limit > 0.0) {
1305                 response = readline ("The next one is timed. Press enter when ready:");
1306                 free (response);
1307             }
1308
1309             mnemon_show_challenge (mnemon, category->challenge_type,
1310                                    item->challenge);
1311
1312             gettimeofday (&start, NULL);
1313             response = readline ("> ");
1314             gettimeofday (&end, NULL);
1315
1316             mnemon_hide_challenge (mnemon, category->challenge_type);
1317
1318             /* Terminate on EOF */
1319             if (response == NULL) {
1320                 printf ("\n");
1321                 return;
1322             }
1323
1324             if (response[0] == '/') {
1325                 mnemon_handle_command (mnemon, response + 1);
1326                 free (response);
1327             } else {
1328                 break;
1329             }
1330         }
1331
1332         mnemon_handle_response (mnemon, bin, item_index,
1333                                 item, response,
1334                                 (end.tv_sec + end.tv_usec / 1e6) -
1335                                 (start.tv_sec + start.tv_usec / 1e6),
1336                                 category->time_limit);
1337         free (response);
1338
1339         /* Replay audio challenges for reinforcement. */
1340         if (category->repeat)
1341         {
1342             mnemon_show_challenge (mnemon, category->challenge_type,
1343                                    item->challenge);
1344             printf ("%s\n", item->challenge);
1345             sleep (2);
1346         }
1347     } while (mnemon->to_introduce ||
1348              mnemon->unlearned ||
1349              mnemon->to_master > 0);
1350 }
1351
1352 int
1353 main (int argc, char *argv[])
1354 {
1355     mnemon_t mnemon;
1356     char *response;
1357
1358     void _load_categories()
1359     {
1360         if (argc > 1) {
1361             int i;
1362             for (i = 1; i < argc; i++)
1363                 mnemon_load_category (&mnemon, argv[i]);
1364         } else {
1365             mnemon_load (&mnemon);
1366         }
1367     }
1368
1369     srand (time (NULL));
1370
1371     mnemon_init (&mnemon);
1372
1373     _load_categories ();
1374
1375     mnemon_do_challenges (&mnemon);
1376
1377     mnemon_save (&mnemon);
1378
1379     mnemon_fini (&mnemon);
1380
1381     mnemon_init (&mnemon);
1382
1383     _load_categories ();
1384
1385     printf ("Great job.\nHere are your current results:\n");
1386     mnemon_print_histogram (&mnemon, NULL, 0);
1387     response = readline ("Press enter to quit.\n");
1388     free (response);
1389
1390     mnemon_fini (&mnemon);
1391
1392     return 0;
1393 }