1 files changed, 229 insertions, 49 deletions

diff --git a/apps/tagtree.c b/apps/tagtree.c
index ea2a756a46..1a49936f45 100644
--- a/apps/tagtree.c
+++ b/apps/tagtree.c
@@ -56,6 +56,8 @@
 #include "playback.h"
 #include "strnatcmp.h"
 #include "panic.h"
+#include "onplay.h"
+#include "plugin.h"
 
 #define str_or_empty(x) (x ? x : "(NULL)")
 
@@ -64,6 +66,10 @@
 
 static int tagtree_play_folder(struct tree_context* c);
 
+/* reuse of tagtree data after tagtree_play_folder() */
+static uint32_t loaded_entries_crc = 0;
+
+
 /* this needs to be same size as struct entry (tree.h) and name needs to be
  * the first; so that they're compatible enough to walk arrays of both
  * derefencing the name member*/
@@ -71,6 +77,7 @@ struct tagentry {
     char* name;
     int newtable;
     int extraseek;
+    int customaction;
 };
 
 static struct tagentry* tagtree_get_entry(struct tree_context *c, int id);
@@ -78,10 +85,10 @@ static struct tagentry* tagtree_get_entry(struct tree_context *c, int id);
 #define SEARCHSTR_SIZE 256
 
 enum table {
-    ROOT = 1,
-    NAVIBROWSE,
-    ALLSUBENTRIES,
-    PLAYTRACK,
+    TABLE_ROOT = 1,
+    TABLE_NAVIBROWSE,
+    TABLE_ALLSUBENTRIES,
+    TABLE_PLAYTRACK,
 };
 
 static const struct id3_to_search_mapping {
@@ -108,6 +115,7 @@ enum variables {
     menu_next,
     menu_load,
     menu_reload,
+    menu_shuffle_songs,
 };
 
 /* Capacity 10 000 entries (for example 10k different artists) */
@@ -276,6 +284,20 @@ static struct buflib_callbacks ops = {
     .shrink_callback = NULL,
 };
 
+static uint32_t tagtree_data_crc(struct tree_context* c)
+{
+    char* buf;
+    uint32_t crc;
+    buf = core_get_data(tagtree_handle); /* data for the search clauses etc */
+    crc = crc_32(buf, tagtree_buf_used, c->dirlength);
+    buf = core_get_data(c->cache.name_buffer_handle); /* names */
+    crc = crc_32(buf, c->cache.name_buffer_size, crc);
+    buf = core_get_data(c->cache.entries_handle); /* tagentries */
+    crc = crc_32(buf, c->cache.max_entries * sizeof(struct tagentry), crc);
+    logf("%s 0x%x", __func__, crc);
+    return crc;
+}
+
 static void* tagtree_alloc(size_t size)
 {
     size = ALIGN_UP(size, sizeof(void*));
@@ -338,6 +360,7 @@ static int get_tag(int *tag)
         TAG_MATCH("Pm", tag_virt_playtime_min),
         TAG_MATCH("Ps", tag_virt_playtime_sec),
         TAG_MATCH("->", menu_next),
+        TAG_MATCH("~>", menu_shuffle_songs),
 
         TAG_MATCH("==>", menu_load),
 
@@ -820,7 +843,7 @@ static bool parse_search(struct menu_entry *entry, const char *str)
         return true;
     }
 
-    if (entry->type != menu_next)
+    if (entry->type != menu_next && entry->type != menu_shuffle_songs)
         return false;
 
     while (inst->tagorder_count < MAX_TAGS)
@@ -847,7 +870,7 @@ static bool parse_search(struct menu_entry *entry, const char *str)
 
         inst->tagorder_count++;
 
-        if (get_tag(&type) <= 0 || type != menu_next)
+        if (get_tag(&type) <= 0 || (type != menu_next && type != menu_shuffle_songs))
             break;
     }
 
@@ -1245,6 +1268,7 @@ static void tagtree_unload(struct tree_context *c)
             dptr->name = NULL;
             dptr->newtable = 0;
             dptr->extraseek = 0;
+            dptr->customaction = ONPLAY_NO_CUSTOMACTION;
             dptr++;
         }
     }
@@ -1452,9 +1476,9 @@ static int retrieve_entries(struct tree_context *c, int offset, bool init)
 #else
         true
 #endif
-        , 0);
+        , 0, 0, 0);
 
-    if (c->currtable == ALLSUBENTRIES)
+    if (c->currtable == TABLE_ALLSUBENTRIES)
     {
         tag = tag_title;
         level--;
@@ -1544,17 +1568,19 @@ static int retrieve_entries(struct tree_context *c, int offset, bool init)
     {
         if (offset == 0)
         {
-            dptr->newtable = ALLSUBENTRIES;
+            dptr->newtable = TABLE_ALLSUBENTRIES;
             dptr->name = str(LANG_TAGNAVI_ALL_TRACKS);
+            dptr->customaction = ONPLAY_NO_CUSTOMACTION;
             dptr++;
             current_entry_count++;
             special_entry_count++;
         }
         if (offset <= 1)
         {
-            dptr->newtable = NAVIBROWSE;
+            dptr->newtable = TABLE_NAVIBROWSE;
             dptr->name = str(LANG_TAGNAVI_RANDOM);
             dptr->extraseek = -1;
+            dptr->customaction = ONPLAY_NO_CUSTOMACTION;
             dptr++;
             current_entry_count++;
             special_entry_count++;
@@ -1568,14 +1594,15 @@ static int retrieve_entries(struct tree_context *c, int offset, bool init)
         if (total_count++ < offset)
             continue;
 
-        dptr->newtable = NAVIBROWSE;
+        dptr->newtable = TABLE_NAVIBROWSE;
         if (tag == tag_title || tag == tag_filename)
         {
-            dptr->newtable = PLAYTRACK;
+            dptr->newtable = TABLE_PLAYTRACK;
             dptr->extraseek = tcs.idx_id;
         }
         else
             dptr->extraseek = tcs.result_seek;
+        dptr->customaction = ONPLAY_NO_CUSTOMACTION;
 
         fmt = NULL;
         /* Check the format */
@@ -1676,7 +1703,7 @@ entry_skip_formatter:
 
         if (init)
         {
-            if (!show_search_progress(false, total_count))
+            if (!show_search_progress(false, total_count, 0, 0))
             {   /* user aborted */
                 tagcache_search_finish(&tcs);
                 tree_unlock_cache(c);
@@ -1710,7 +1737,7 @@ entry_skip_formatter:
 
     while (tagcache_get_next(&tcs, tcs_buf, tcs_bufsz))
     {
-        if (!show_search_progress(false, total_count))
+        if (!show_search_progress(false, total_count, 0, 0))
             break;
         total_count++;
     }
@@ -1758,7 +1785,7 @@ static int load_root(struct tree_context *c)
     int i;
 
     tc = c;
-    c->currtable = ROOT;
+    c->currtable = TABLE_ROOT;
     if (c->dirlevel == 0)
         c->currextra = rootmenu;
 
@@ -1775,13 +1802,21 @@ static int load_root(struct tree_context *c)
         switch (menu->items[i]->type)
         {
             case menu_next:
-                dptr->newtable = NAVIBROWSE;
+                dptr->newtable = TABLE_NAVIBROWSE;
                 dptr->extraseek = i;
+                dptr->customaction = ONPLAY_NO_CUSTOMACTION;
                 break;
 
             case menu_load:
-                dptr->newtable = ROOT;
+                dptr->newtable = TABLE_ROOT;
                 dptr->extraseek = menu->items[i]->link;
+                dptr->customaction = ONPLAY_NO_CUSTOMACTION;
+                break;
+
+            case menu_shuffle_songs:
+                dptr->newtable = TABLE_NAVIBROWSE;
+                dptr->extraseek = i;
+                dptr->customaction = ONPLAY_CUSTOMACTION_SHUFFLE_SONGS;
                 break;
         }
 
@@ -1796,6 +1831,8 @@ static int load_root(struct tree_context *c)
 
 int tagtree_load(struct tree_context* c)
 {
+    logf( "%s", __func__);
+
     int count;
     int table = c->currtable;
 
@@ -1804,20 +1841,32 @@ int tagtree_load(struct tree_context* c)
     if (!table)
     {
         c->dirfull = false;
-        table = ROOT;
+        table = TABLE_ROOT;
         c->currtable = table;
         c->currextra = rootmenu;
     }
 
     switch (table)
     {
-        case ROOT:
+        case TABLE_ROOT:
+            logf( "root...");
             count = load_root(c);
             break;
 
-        case ALLSUBENTRIES:
-        case NAVIBROWSE:
+        case TABLE_ALLSUBENTRIES:
+        case TABLE_NAVIBROWSE:
             logf("navibrowse...");
+
+            if (loaded_entries_crc != 0)
+            {
+                if (loaded_entries_crc == tagtree_data_crc(c))
+                {
+                    count = c->dirlength;
+                    logf("Reusing %d entries", count);
+                    break;
+                }
+            }
+
             cpu_boost(true);
             count = retrieve_entries(c, 0, true);
             cpu_boost(false);
@@ -1828,6 +1877,8 @@ int tagtree_load(struct tree_context* c)
             return -1;
     }
 
+    loaded_entries_crc = 0;
+
     if (count < 0)
     {
         if (count != RELOAD_TAGTREE)
@@ -1860,6 +1911,8 @@ int tagtree_load(struct tree_context* c)
  */
 int tagtree_enter(struct tree_context* c, bool is_visible)
 {
+    logf( "%s", __func__);
+
     int rc = 0;
     struct tagentry *dptr;
     struct mp3entry *id3;
@@ -1921,16 +1974,16 @@ int tagtree_enter(struct tree_context* c, bool is_visible)
     core_pin(tagtree_handle);
 
     switch (c->currtable) {
-        case ROOT:
+        case TABLE_ROOT:
             c->currextra = newextra;
 
-            if (newextra == ROOT)
+            if (newextra == TABLE_ROOT)
             {
                 menu = menus[seek];
                 c->currextra = seek;
             }
 
-            else if (newextra == NAVIBROWSE)
+            else if (newextra == TABLE_NAVIBROWSE)
             {
                 int i, j;
 
@@ -2005,9 +2058,9 @@ int tagtree_enter(struct tree_context* c, bool is_visible)
 
             break;
 
-        case NAVIBROWSE:
-        case ALLSUBENTRIES:
-            if (newextra == PLAYTRACK)
+        case TABLE_NAVIBROWSE:
+        case TABLE_ALLSUBENTRIES:
+            if (newextra == TABLE_PLAYTRACK)
             {
                 adjust_selection = false;
 
@@ -2059,6 +2112,7 @@ int tagtree_enter(struct tree_context* c, bool is_visible)
 /* Exits current database menu or table */
 void tagtree_exit(struct tree_context* c, bool is_visible)
 {
+    logf( "%s", __func__);
     if (is_visible) /* update selection history only for user-selected items */
     {
         if (c->selected_item != selected_item_history[c->dirlevel])
@@ -2102,15 +2156,54 @@ int tagtree_get_filename(struct tree_context* c, char *buf, int buflen)
     return 0;
 }
 
+int tagtree_get_custom_action(struct tree_context* c)
+{
+    return tagtree_get_entry(c, c->selected_item)->customaction;
+}
+
+static void swap_array_bool(bool *a, bool *b)
+{
+    bool temp = *a;
+    *a = *b;
+    *b = temp;
+}
+
+/**
+ * Randomly shuffle an array using the Fisher-Yates algorithm :
+ *  https://en.wikipedia.org/wiki/Random_permutation
+ *  This algorithm has a linear complexity.
+ *  Don't forget to srand before call to use it with a relevant seed.
+ */
+static bool* fill_random_playlist_indexes(bool *bool_array, size_t arr_sz,
+                                         size_t track_count, size_t max_slots)
+{
+    size_t i;
+    if (track_count * sizeof(bool) > arr_sz || max_slots > track_count)
+        return NULL;
+
+    for (i = 0; i < arr_sz; i++) /* fill max_slots with TRUE */
+        bool_array[i] = i < max_slots;
+
+    /* shuffle bool array */
+    for (i = track_count - 1; i > 0; i--)
+    {
+        int j = rand() % (i + 1);
+        swap_array_bool(&bool_array[i], &bool_array[j]);
+    }
+    return bool_array;
+}
 
 static bool insert_all_playlist(struct tree_context *c,
                                 const char* playlist, bool new_playlist,
                                 int position, bool queue)
 {
     struct tagcache_search tcs;
-    int i, n;
+    int n;
     int fd = -1;
     unsigned long last_tick;
+    int slots_remaining = 0;
+    bool fill_randomly = false;
+    bool *rand_bool_array = NULL;
     char buf[MAX_PATH];
 
     cpu_boost(true);
@@ -2148,40 +2241,114 @@ static bool insert_all_playlist(struct tree_context *c,
     last_tick = current_tick + HZ/2; /* Show splash after 0.5 seconds have passed */
     splash_progress_set_delay(HZ / 2); /* wait 1/2 sec before progress */
     n = c->filesindir;
-    for (i = 0; i < n; i++)
+
+    if (playlist == NULL)
     {
+        int max_playlist_size = playlist_get_current()->max_playlist_size;
+        slots_remaining = max_playlist_size - playlist_get_current()->amount;
+        if (slots_remaining <= 0)
+        {
+            logf("Playlist has no space remaining");
+            cpu_boost(false);
+            return false;
+        }
 
-        splash_progress(i, n, "%s (%s)", str(LANG_WAIT), str(LANG_OFF_ABORT));
+        fill_randomly = n > slots_remaining;
+    
+        if (fill_randomly)
+        {
+            srand(current_tick);
+            size_t bufsize = 0;
+            bool *buffer = (bool *) plugin_get_buffer(&bufsize);
+            rand_bool_array = fill_random_playlist_indexes(buffer, bufsize,
+                                                           n, slots_remaining);
+
+            talk_id(LANG_RANDOM_SHUFFLE_RANDOM_SELECTIVE_SONGS_SUMMARY, true);
+            splashf(HZ * 2, str(LANG_RANDOM_SHUFFLE_RANDOM_SELECTIVE_SONGS_SUMMARY),
+                    slots_remaining);
+        }
+    }
+
+    bool exit_loop_now = false;
+    for (int i = 0; i < n; i++)
+    {
         if (TIME_AFTER(current_tick, last_tick + HZ/4))
         {
+            splash_progress(i, n, "%s (%s)", str(LANG_WAIT), str(LANG_OFF_ABORT));
             if (action_userabort(TIMEOUT_NOBLOCK))
+            {
+                exit_loop_now = true;
                 break;
+            }
             last_tick = current_tick;
         }
 
-        if (!tagcache_retrieve(&tcs, tagtree_get_entry(c, i)->extraseek,
-                               tcs.type, buf, sizeof buf))
+        if (playlist == NULL)
         {
-            continue;
+            if (fill_randomly)
+            {
+                int remaining_tracks = n - i;
+                if (remaining_tracks > slots_remaining)
+                {
+                    if (rand_bool_array)
+                    {
+                        /* Skip the track if rand_bool_array[i] is FALSE */
+                        if (!rand_bool_array[i])
+                            continue;
+                    }
+                    else
+                    {
+                        /* Generate random value between 0 and remaining_tracks - 1 */
+                        int selrange = RAND_MAX / remaining_tracks; /* Improve distribution */
+                        int random;
+
+                        for (int r = 0; r < 0x0FFF; r++) /* limit loops */
+                        {
+                            random = rand() / selrange;
+                            if (random < remaining_tracks)
+                                break;
+                            else
+                                random = 0;
+                        }
+                        /* Skip the track if random >= slots_remaining */
+                        if (random >= slots_remaining)
+                            continue;
+                    }
+                }
+            }
         }
 
+        if (!tagcache_retrieve(&tcs, tagtree_get_entry(c, i)->extraseek, tcs.type, buf, sizeof buf))
+            continue;
+
         if (playlist == NULL)
         {
-            if (playlist_insert_track(NULL, buf, position, queue, false) < 0)
+            if (fill_randomly)
             {
+                if (--slots_remaining <= 0)
+                {
+                    exit_loop_now = true;
+                    break;
+                }
+            }
+
+            if (playlist_insert_track(NULL, buf, position, queue, false) < 0) {
                 logf("playlist_insert_track failed");
+                exit_loop_now = true;
                 break;
             }
         }
         else if (fdprintf(fd, "%s\n", buf) <= 0)
-                break;
-
+        {
+            exit_loop_now = true;
+            break;
+        }
         yield();
-
         if (playlist == NULL && position == PLAYLIST_INSERT_FIRST)
-        {
             position = PLAYLIST_INSERT;
-        }
+
+        if (exit_loop_now)
+            break;
     }
     if (playlist == NULL)
         playlist_sync(NULL);
@@ -2196,14 +2363,14 @@ static bool insert_all_playlist(struct tree_context *c,
 static bool goto_allsubentries(int newtable)
 {
     int i = 0;
-    while (i < 2 && (newtable == NAVIBROWSE || newtable == ALLSUBENTRIES))
+    while (i < 2 && (newtable == TABLE_NAVIBROWSE || newtable == TABLE_ALLSUBENTRIES))
     {
         tagtree_enter(tc, false);
         tagtree_load(tc);
         newtable = tagtree_get_entry(tc, tc->selected_item)->newtable;
         i++;
     }
-    return (newtable == PLAYTRACK);
+    return (newtable == TABLE_PLAYTRACK);
 }
 
 static void reset_tc_to_prev(int dirlevel, int selected_item)
@@ -2229,11 +2396,11 @@ static bool tagtree_insert_selection(int position, bool queue,
 #else
         true
 #endif
-        , 0);
+        , 0, 0, 0);
 
     newtable = tagtree_get_entry(tc, tc->selected_item)->newtable;
 
-    if (newtable == PLAYTRACK) /* Insert a single track? */
+    if (newtable == TABLE_PLAYTRACK) /* Insert a single track? */
     {
         if (tagtree_get_filename(tc, buf, sizeof buf) < 0)
             return false;
@@ -2342,6 +2509,7 @@ int tagtree_add_to_playlist(const char* playlist, bool new_playlist)
 
 static int tagtree_play_folder(struct tree_context* c)
 {
+    logf( "%s", __func__);
     int start_index = c->selected_item;
 
     if (playlist_create(NULL, NULL) < 0)
@@ -2353,14 +2521,26 @@ static int tagtree_play_folder(struct tree_context* c)
     if (!insert_all_playlist(c, NULL, false, PLAYLIST_INSERT_LAST, false))
         return -2;
 
+    int n = c->filesindir;
+    bool has_playlist_been_randomized = n > playlist_get_current()->max_playlist_size;
+    if (has_playlist_been_randomized)
+    {
+        /* We need to recalculate the start index based on a percentage to put the user
+        around its desired start position and avoid out of bounds */
+
+        int percentage_start_index = 100 * start_index / n;
+        start_index = percentage_start_index * playlist_get_current()->amount / 100;
+    }
+
     if (global_settings.playlist_shuffle)
     {
-        start_index = playlist_shuffle(current_tick, c->selected_item);
+        start_index = playlist_shuffle(current_tick, start_index);
         if (!global_settings.play_selected)
             start_index = 0;
     }
 
     playlist_start(start_index, 0, 0);
+    loaded_entries_crc = tagtree_data_crc(c); /* save crc in case we return */
     return 0;
 }
 
@@ -2403,11 +2583,11 @@ char *tagtree_get_title(struct tree_context* c)
 {
     switch (c->currtable)
     {
-        case ROOT:
+        case TABLE_ROOT:
             return menu->title;
 
-        case NAVIBROWSE:
-        case ALLSUBENTRIES:
+        case TABLE_NAVIBROWSE:
+        case TABLE_ALLSUBENTRIES:
             return current_title[c->currextra];
     }
 
@@ -2419,7 +2599,7 @@ int tagtree_get_attr(struct tree_context* c)
     int attr = -1;
     switch (c->currtable)
     {
-        case NAVIBROWSE:
+        case TABLE_NAVIBROWSE:
             if (csi->tagorder[c->currextra] == tag_title
                 || csi->tagorder[c->currextra] == tag_virt_basename)
                 attr = FILE_ATTR_AUDIO;
@@ -2427,7 +2607,7 @@ int tagtree_get_attr(struct tree_context* c)
                 attr = ATTR_DIRECTORY;
             break;
 
-        case ALLSUBENTRIES:
+        case TABLE_ALLSUBENTRIES:
             attr = FILE_ATTR_AUDIO;
             break;