Reworks to the shuffle system to improve performance and allow fast shuffling from a big library (but this work for all database views)

This improvement brings a huge performance improvement to start a random mix of your library. Previously, the only way to do this was to increase the size of a playlist with absurd sizes number. Now it will respect the limitation but will insert random songs from the current view.

Database: Add true random songs in playlist if it is gonna exceed its maximum capacity

More context is available here : https://www.reddit.com/r/rockbox/comments/1ez0mq4/i_developped_true_full_library_shuffle_for/

Also :
- Improved layout in the DB browser
- New default max playlists capacity is now 2000 on old PortalPlayer targets to give a better user experience and not having to wait dozens of seconds while creating a playlist
- "Show insert shuffled" option is now true by default
- Add a new shortcut to play all songs shuffled in the DB browser
- Now the feature is fully optional and enabled only on targets that have more than 2MB of RAM
- Add entries about this feature in the manual to explain it to the users
Change-Id: I1aebaf7ebcff2bf907080f1861027d530619097c

Change-Id: I3354923b148eeef1975171990e814a1a505d1df0

13 files changed, 263 insertions, 88 deletions

diff --git a/apps/gui/wps.c b/apps/gui/wps.c
index 0de805bd02..82b0394a53 100644
--- a/apps/gui/wps.c
+++ b/apps/gui/wps.c
@@ -806,7 +806,7 @@ long gui_wps_show(void)
                     theme_enabled = false;
                     gwps_leave_wps(theme_enabled);
                     onplay(state->id3->path,
-                           FILE_ATTR_AUDIO, CONTEXT_WPS, hotkey);
+                           FILE_ATTR_AUDIO, CONTEXT_WPS, hotkey, ONPLAY_NO_CUSTOMACTION);
                     if (!audio_status())
                     {
                         /* re-enable theme since we're returning to SBS */
@@ -823,7 +823,7 @@ long gui_wps_show(void)
             {
                 gwps_leave_wps(true);
                 int retval = onplay(state->id3->path,
-                       FILE_ATTR_AUDIO, CONTEXT_WPS, hotkey);
+                       FILE_ATTR_AUDIO, CONTEXT_WPS, hotkey, ONPLAY_NO_CUSTOMACTION);
                 /* if music is stopped in the context menu we want to exit the wps */
                 if (retval == ONPLAY_MAINMENU
                     || !audio_status())
diff --git a/apps/lang/english.lang b/apps/lang/english.lang
index b0c7aed8f7..348f339239 100644
--- a/apps/lang/english.lang
+++ b/apps/lang/english.lang
@@ -2054,6 +2054,20 @@
   </voice>
 </phrase>
 <phrase>
+  id: LANG_RANDOM_SHUFFLE_RANDOM_SELECTIVE_SONGS_SUMMARY
+  desc: a summary splash screen that appear on the database browser when you try to create a playlist from the database browser that exceeds your system limit
+  user: core
+  <source>
+    *: "Selection too big, %d random tracks will be picked from it"
+  </source>
+  <dest>
+    *: "Selection too big, %d random tracks will be picked from it"
+  </dest>
+  <voice>
+    *: "Selection too big, fewer random tracks will be picked from it"
+  </voice>
+</phrase>
+<phrase>
   id: LANG_TAGCACHE_RAM
   desc: in tag cache settings
   user: core
diff --git a/apps/lang/francais.lang b/apps/lang/francais.lang
index ce907372b0..518b48fb96 100644
--- a/apps/lang/francais.lang
+++ b/apps/lang/francais.lang
@@ -2028,6 +2028,20 @@
   </voice>
 </phrase>
 <phrase>
+  id: LANG_RANDOM_SHUFFLE_RANDOM_SELECTIVE_SONGS_SUMMARY
+  desc: a summary splash screen that appear on the database browser when you try to create a playlist from the database browser that exceeds your system limit
+  user: core
+  <source>
+    *: "Selection too big, %d random tracks will be picked from it"
+  </source>
+  <dest>
+    *: "Selection trop grande, %d pistes seront sélectionnées aléatoirement depuis celle-ci"
+  </dest>
+  <voice>
+    *: "Selection trop grande, donc des pistes seront sélectionnées aléatoirement depuis celle-ci"
+  </voice>
+</phrase>
+<phrase>
   id: LANG_TAGCACHE_RAM
   desc: in tag cache settings
   user: core
diff --git a/apps/onplay.c b/apps/onplay.c
index 4f748204df..045af275bc 100644
--- a/apps/onplay.c
+++ b/apps/onplay.c
@@ -302,7 +302,7 @@ static int add_to_playlist(void* arg)
 
     /* warn if replacing the playlist */
     if (new_playlist && !warn_on_pl_erase())
-        return 0;
+        return 1;
 
     splash(0, ID2P(LANG_WAIT));
 
@@ -340,7 +340,7 @@ static int add_to_playlist(void* arg)
     }
 
     playlist_set_modified(NULL, true);
-    return false;
+    return 0;
 }
 
 static bool view_playlist(void)
@@ -1255,7 +1255,7 @@ static int execute_hotkey(bool is_wps)
 }
 #endif /* HOTKEY */
 
-int onplay(char* file, int attr, int from_context, bool hotkey)
+int onplay(char* file, int attr, int from_context, bool hotkey, int customaction)
 {
     const struct menu_item_ex *menu;
     onplay_result = ONPLAY_OK;
@@ -1294,6 +1294,13 @@ int onplay(char* file, int attr, int from_context, bool hotkey)
 #else
     (void)hotkey;
 #endif
+    if (customaction == ONPLAY_CUSTOMACTION_SHUFFLE_SONGS) {
+        int returnCode = add_to_playlist(&addtopl_replace_shuffled);
+        if (returnCode == 1)
+            // User did not want to erase his current playlist, so let's show again the database main menu
+            return ONPLAY_RELOAD_DIR;
+        return ONPLAY_START_PLAY;
+    }
 
     push_current_activity(ACTIVITY_CONTEXTMENU);
     if (from_context == CONTEXT_WPS)
diff --git a/apps/onplay.h b/apps/onplay.h
index 74dc045db3..03861e9cf6 100644
--- a/apps/onplay.h
+++ b/apps/onplay.h
@@ -25,7 +25,12 @@
 #include "menu.h"
 #endif
 
-int onplay(char* file, int attr, int from_context, bool hotkey);
+enum {
+    ONPLAY_NO_CUSTOMACTION,
+    ONPLAY_CUSTOMACTION_SHUFFLE_SONGS,
+};
+
+int onplay(char* file, int attr, int from_context, bool hotkey, int customaction);
 int get_onplay_context(void);
 
 enum {
diff --git a/apps/playlist_viewer.c b/apps/playlist_viewer.c
index 70072f59f5..5bf547a3fc 100644
--- a/apps/playlist_viewer.c
+++ b/apps/playlist_viewer.c
@@ -1107,7 +1107,7 @@ enum playlist_viewer_result playlist_viewer_ex(const char* filename,
                     }
                 }
                 else
-                    onplay(current_track->name, FILE_ATTR_AUDIO, CONTEXT_STD, true);
+                    onplay(current_track->name, FILE_ATTR_AUDIO, CONTEXT_STD, true, ONPLAY_NO_CUSTOMACTION);
                 break;
             }
 #endif /* HAVE_HOTKEY */
diff --git a/apps/settings_list.c b/apps/settings_list.c
index 8ec434bd9b..3b29703fe9 100644
--- a/apps/settings_list.c
+++ b/apps/settings_list.c
@@ -1120,7 +1120,11 @@ const struct settings_list settings[] = {
     SYSTEM_SETTING(NVRAM(4), topruntime, 0),
     INT_SETTING(F_BANFROMQS, max_files_in_playlist,
                 LANG_MAX_FILES_IN_PLAYLIST,
-#if MEMORYSIZE > 1
+#if CONFIG_CPU == PP5002 || CONFIG_CPU == PP5020 || CONFIG_CPU == PP5022
+                  /** Slow CPU benefits greatly from building smaller playlists 
+                  On the iPod Mini 2nd gen, creating a playlist of 2000 entries takes around 10 seconds */
+                  2000,
+#elif MEMORYSIZE > 1
                   10000,
 #else
                   400,
@@ -1854,7 +1858,7 @@ const struct settings_list settings[] = {
                   true, "warn when erasing dynamic playlist",NULL),
     OFFON_SETTING(0, keep_current_track_on_replace_playlist, LANG_KEEP_CURRENT_TRACK_ON_REPLACE,
                   true, "keep current track when replacing playlist",NULL),
-    OFFON_SETTING(0, show_shuffled_adding_options, LANG_SHOW_SHUFFLED_ADDING_OPTIONS, false,
+    OFFON_SETTING(0, show_shuffled_adding_options, LANG_SHOW_SHUFFLED_ADDING_OPTIONS, true,
                       "show shuffled adding options", NULL),
     CHOICE_SETTING(0, show_queue_options, LANG_SHOW_QUEUE_OPTIONS, 0,
                       "show queue options", "off,on,in submenu",
diff --git a/apps/tagnavi.config b/apps/tagnavi.config
index 6eda05ec44..6baa6e1328 100644
--- a/apps/tagnavi.config
+++ b/apps/tagnavi.config
@@ -176,20 +176,21 @@
 
 # Define the title of the main menu
 %menu_start "main" "Database"
-"Artist"   -> canonicalartist   -> album  -> title = "fmt_title"
 "Album Artist" -> albumartist   -> album  -> title = "fmt_title"
+"Artist"   -> canonicalartist   -> album  -> title = "fmt_title"
 "Album"    -> album    -> title = "fmt_title"
 "Genre"    -> genre    -> canonicalartist -> album -> title = "fmt_title"
+"Year"     -> year ? year > "0" -> canonicalartist -> album -> title = "fmt_title"
 "Composer" -> composer -> album -> title = "fmt_title"
+"A to Z" ==> "a2z"
 "Track"   ==> "track"
-"Year"     -> year ? year > "0" -> canonicalartist -> album -> title = "fmt_title"
+"Shuffle Songs" ~> title = "fmt_title"
+"Search" ==> "search"
 "User Rating" -> rating -> title = "fmt_title"
 "Recently Added" -> album ? entryage < "4" & commitid > "0" -> title = "fmt_title"
-"A to Z..." ==> "a2z"
-"History..." ==> "runtime"
-"Same as current..." ==> "same"
-"Search..." ==> "search"
-"Custom view..."  ==> "custom"
+"History" ==> "runtime"
+"Same as current" ==> "same"
+"Custom view"  ==> "custom"
 
 # And finally set main menu as our root menu
 %root_menu "main"
diff --git a/apps/tagtree.c b/apps/tagtree.c
index d2e27a3e58..4a0bff32bd 100644
--- a/apps/tagtree.c
+++ b/apps/tagtree.c
@@ -56,6 +56,7 @@
 #include "playback.h"
 #include "strnatcmp.h"
 #include "panic.h"
+#include "onplay.h"
 
 #define str_or_empty(x) (x ? x : "(NULL)")
 
@@ -71,6 +72,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 +80,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,12 +110,21 @@ enum variables {
     menu_next,
     menu_load,
     menu_reload,
+    menu_shuffle_songs,
 };
 
 /* Capacity 10 000 entries (for example 10k different artists) */
 #define UNIQBUF_SIZE (64*1024)
 static uint32_t uniqbuf[UNIQBUF_SIZE / sizeof(uint32_t)];
 
+#if MEMORYSIZE > 2
+    #define INSERT_ALL_PLAYLIST_MAX_SEGMENT_SIZE (1024)
+#else
+    /* Lower quality randomness for low-ram devices using smaller segments */
+    #define INSERT_ALL_PLAYLIST_MAX_SEGMENT_SIZE (128)
+#endif
+static bool selective_random_playlist_indexes[INSERT_ALL_PLAYLIST_MAX_SEGMENT_SIZE];
+
 #define MAX_TAGS 5
 #define MAX_MENU_ID_SIZE 32
 
@@ -338,6 +349,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 +832,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 +859,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 +1257,7 @@ static void tagtree_unload(struct tree_context *c)
             dptr->name = NULL;
             dptr->newtable = 0;
             dptr->extraseek = 0;
+            dptr->customaction = ONPLAY_NO_CUSTOMACTION;
             dptr++;
         }
     }
@@ -1454,7 +1467,7 @@ static int retrieve_entries(struct tree_context *c, int offset, bool init)
 #endif
         , 0, 0, 0);
 
-    if (c->currtable == ALLSUBENTRIES)
+    if (c->currtable == TABLE_ALLSUBENTRIES)
     {
         tag = tag_title;
         level--;
@@ -1544,17 +1557,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 +1583,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 */
@@ -1758,7 +1774,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 +1791,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;
         }
 
@@ -1804,19 +1828,19 @@ 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:
             count = load_root(c);
             break;
 
-        case ALLSUBENTRIES:
-        case NAVIBROWSE:
+        case TABLE_ALLSUBENTRIES:
+        case TABLE_NAVIBROWSE:
             logf("navibrowse...");
             cpu_boost(true);
             count = retrieve_entries(c, 0, true);
@@ -1921,16 +1945,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 +2029,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;
 
@@ -2102,13 +2126,46 @@ 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 void shuffle_bool_array(bool array[], int size) {
+    for (int i = size - 1; i > 0; i--) {
+        int j = rand() % (i + 1);
+        swap_array_bool(&array[i], &array[j]);
+    }
+}
+
+static bool fill_selective_random_playlist_indexes(int current_segment_n, int current_segment_max_available_space) {
+    if (current_segment_n == 0 || current_segment_max_available_space == 0)
+        return false;
+    if (current_segment_max_available_space > current_segment_n)
+        current_segment_max_available_space = current_segment_n;
+    for (int i = 0; i < current_segment_n; i++)
+        selective_random_playlist_indexes[i] = i < current_segment_max_available_space;
+    srand(current_tick);
+    shuffle_bool_array(selective_random_playlist_indexes, current_segment_n);
+    return true;
+}
 
 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;
     char buf[MAX_PATH];
@@ -2144,44 +2201,77 @@ static bool insert_all_playlist(struct tree_context *c,
             return false;
         }
     }
-
     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++)
-    {
-
-        splash_progress(i, n, "%s (%s)", str(LANG_WAIT), str(LANG_OFF_ABORT));
-        if (TIME_AFTER(current_tick, last_tick + HZ/4))
-        {
-            if (action_userabort(TIMEOUT_NOBLOCK))
-                break;
-            last_tick = current_tick;
+    int segment_size = INSERT_ALL_PLAYLIST_MAX_SEGMENT_SIZE;
+    int segments_count = n / segment_size;
+    int leftovers_segment_size = n % segment_size;
+    bool fill_randomly = false;
+    if (playlist == NULL) {
+        bool will_exceed = n > playlist_get_current()->max_playlist_size;
+        fill_randomly = will_exceed;
+    }
+    if (leftovers_segment_size > 0 && fill_randomly) {
+        // We need to re-balance the segments so the randomness will be coherent and balanced the same through all segments
+        while (leftovers_segment_size + segments_count < segment_size) {
+            segment_size--; // -1 to all other segments
+            leftovers_segment_size += segments_count;
         }
-
-        if (!tagcache_retrieve(&tcs, tagtree_get_entry(c, i)->extraseek,
-                               tcs.type, buf, sizeof buf))
-        {
-            continue;
+    }
+    if (leftovers_segment_size > 0)
+        segments_count += 1;
+    int max_available_space = playlist_get_current()->max_playlist_size - playlist_get_current()->amount;
+    int max_available_space_per_segment = max_available_space / segments_count;
+    if (fill_randomly) {
+        talk_id(LANG_RANDOM_SHUFFLE_RANDOM_SELECTIVE_SONGS_SUMMARY, true);
+        splashf(HZ * 3, str(LANG_RANDOM_SHUFFLE_RANDOM_SELECTIVE_SONGS_SUMMARY), max_available_space_per_segment * segments_count);
+        //splashf(HZ * 5, "sz=%d lsz=%d sc=%d rcps=%d", segment_size, leftovers_segment_size, segments_count, max_available_space_per_segment);
+    }
+    for (int i = 0; i < segments_count; i++) {
+        bool is_leftovers_segment = leftovers_segment_size > 0 && i + 1 >= segments_count;
+        if (fill_randomly) {
+            if (is_leftovers_segment)
+                fill_randomly = fill_selective_random_playlist_indexes(leftovers_segment_size, max_available_space_per_segment);
+            else
+                fill_randomly = fill_selective_random_playlist_indexes(segment_size, max_available_space_per_segment);
         }
-
-        if (playlist == NULL)
-        {
-            if (playlist_insert_track(NULL, buf, position, queue, false) < 0)
-            {
-                logf("playlist_insert_track failed");
-                break;
+        bool exit_loop_now = false;
+        int cur_segment_start = i * segment_size;
+        int cur_segment_end;
+        if (is_leftovers_segment)
+            cur_segment_end = cur_segment_start + leftovers_segment_size;
+        else
+            cur_segment_end = cur_segment_start + segment_size;
+        for (int j = cur_segment_start; j < cur_segment_end && !exit_loop_now; j++) {
+            if (fill_randomly && !selective_random_playlist_indexes[j % segment_size])
+                continue;
+            splash_progress(j, n, "%s (%s)", str(LANG_WAIT), str(LANG_OFF_ABORT));
+            if (TIME_AFTER(current_tick, last_tick + HZ/4)) {
+                if (action_userabort(TIMEOUT_NOBLOCK)) {
+                    exit_loop_now = true;
+                    break;
+                }
+                last_tick = current_tick;
             }
-        }
-        else if (fdprintf(fd, "%s\n", buf) <= 0)
+            if (!tagcache_retrieve(&tcs, tagtree_get_entry(c, j)->extraseek, tcs.type, buf, sizeof buf))
+                continue;
+            if (playlist == NULL) {
+                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) {
+                exit_loop_now = true;
                 break;
-
-        yield();
-
-        if (playlist == NULL && position == PLAYLIST_INSERT_FIRST)
-        {
-            position = PLAYLIST_INSERT;
+            }
+            yield();
+            if (playlist == NULL && position == PLAYLIST_INSERT_FIRST)
+                position = PLAYLIST_INSERT;
         }
+        if (exit_loop_now)
+            break;
     }
     if (playlist == NULL)
         playlist_sync(NULL);
@@ -2196,14 +2286,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)
@@ -2233,7 +2323,7 @@ static bool tagtree_insert_selection(int position, bool queue,
 
     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;
@@ -2353,9 +2443,19 @@ 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;
     }
@@ -2403,11 +2503,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 +2519,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 +2527,7 @@ int tagtree_get_attr(struct tree_context* c)
                 attr = ATTR_DIRECTORY;
             break;
 
-        case ALLSUBENTRIES:
+        case TABLE_ALLSUBENTRIES:
             attr = FILE_ATTR_AUDIO;
             break;
 
diff --git a/apps/tagtree.h b/apps/tagtree.h
index 39ab545bd0..a57a5c2f80 100644
--- a/apps/tagtree.h
+++ b/apps/tagtree.h
@@ -45,6 +45,7 @@ char *tagtree_get_title(struct tree_context* c);
 int tagtree_get_attr(struct tree_context* c);
 int tagtree_get_icon(struct tree_context* c);
 int tagtree_get_filename(struct tree_context* c, char *buf, int buflen);
+int tagtree_get_custom_action(struct tree_context* c);
 bool tagtree_get_subentry_filename(char *buf, size_t bufsize);
 bool tagtree_subentries_do_action(bool (*action_cb)(const char *file_name));
 
diff --git a/apps/tree.c b/apps/tree.c
index 71a7ee3f62..b4cd9d77b0 100644
--- a/apps/tree.c
+++ b/apps/tree.c
@@ -735,6 +735,17 @@ static int dirbrowse(void)
         oldbutton = button;
         gui_synclist_do_button(&tree_lists, &button);
         tc.selected_item = gui_synclist_get_sel_pos(&tree_lists);
+        int customaction = ONPLAY_NO_CUSTOMACTION;
+        bool do_restore_display = true;
+        #ifdef HAVE_TAGCACHE
+            if (id3db && (button == ACTION_STD_OK || button == ACTION_STD_CONTEXT)) {
+                customaction = tagtree_get_custom_action(&tc);
+                if (customaction == ONPLAY_CUSTOMACTION_SHUFFLE_SONGS) {
+                    button = ACTION_STD_CONTEXT; /** The code to insert shuffled is on the context branch of the switch so we always go here */
+                    do_restore_display = false;
+                }
+            }
+        #endif
         switch ( button ) {
             case ACTION_STD_OK:
                 /* nothing to do if no files to display */
@@ -773,7 +784,7 @@ static int dirbrowse(void)
                     default:
                         break;
                 }
-                restore = true;
+                restore = do_restore_display;
                 break;
 
             case ACTION_STD_CANCEL:
@@ -798,12 +809,12 @@ static int dirbrowse(void)
                     if (ft_exit(&tc) == 3)
                         exit_func = true;
 
-                restore = true;
+                restore = do_restore_display;
                 break;
 
             case ACTION_TREE_STOP:
                 if (list_stop_handler())
-                    restore = true;
+                    restore = do_restore_display;
                 break;
 
             case ACTION_STD_MENU:
@@ -851,7 +862,7 @@ static int dirbrowse(void)
                         skin_update(CUSTOM_STATUSBAR, i, SKIN_REFRESH_ALL);
                 }
 
-                restore = true;
+                restore = do_restore_display;
                 break;
             }
 #endif
@@ -872,7 +883,7 @@ static int dirbrowse(void)
                     break;
 
                 if(!numentries)
-                    onplay_result = onplay(NULL, 0, curr_context, hotkey);
+                    onplay_result = onplay(NULL, 0, curr_context, hotkey, customaction);
                 else {
 #ifdef HAVE_TAGCACHE
                     if (id3db)
@@ -902,7 +913,7 @@ static int dirbrowse(void)
                         ft_assemble_path(buf, sizeof(buf), currdir, entry->name);
 
                     }
-                    onplay_result = onplay(buf, attr, curr_context, hotkey);
+                    onplay_result = onplay(buf, attr, curr_context, hotkey, customaction);
                 }
                 switch (onplay_result)
                 {
@@ -911,7 +922,7 @@ static int dirbrowse(void)
                         break;
 
                     case ONPLAY_OK:
-                        restore = true;
+                        restore = do_restore_display;
                         break;
 
                     case ONPLAY_RELOAD_DIR:
@@ -988,7 +999,7 @@ static int dirbrowse(void)
 
             lastfilter = *tc.dirfilter;
             lastsortcase = global_settings.sort_case;
-            restore = true;
+            restore = do_restore_display;
         }
 
         if (exit_func)
diff --git a/apps/tree.h b/apps/tree.h
index d13c75d434..e958bbf109 100644
--- a/apps/tree.h
+++ b/apps/tree.h
@@ -33,6 +33,9 @@ struct entry {
     char *name;
     int attr; /* FAT attributes + file type flags */
     unsigned time_write; /* Last write time */
+    #ifdef HAVE_TAGCACHE
+    int customaction; /* db use */
+    #endif
 };
 
 #define BROWSE_SELECTONLY       0x0001  /* exit on selecting a file */
diff --git a/manual/rockbox_interface/tagcache.tex b/manual/rockbox_interface/tagcache.tex
index 3c3e6d2df8..ea34b5ba9e 100644
--- a/manual/rockbox_interface/tagcache.tex
+++ b/manual/rockbox_interface/tagcache.tex
@@ -137,6 +137,21 @@ There is no option to turn off database completely. If you do not want
 to use it just do not do the initial build of the database and do not load it
 to RAM.}%
 
+If your total amount of music tracks exceeds the value of the
+\setting{Max Playlist Size} setting (\setting{Settings $\rightarrow$ General
+Settings $\rightarrow$ System $\rightarrow$ Limits}), using the database
+will be your only way to shuffle between all songs from your music library.
+Any view on the database browser that exceeds the maximum value of this option
+will be automatically adjusted and randomized to fit into the available space
+when you will create a dynamic playlist from the view.
+Using the database browser is recommended if you shuffle regularly between a lot of
+songs rather than increasing your limit, so you will get the best possible performance
+on this action.
+
+\note{For your convenience, a shortcut button "Shuffle Songs" is available directly
+from the \setting{Database} menu to create and start a mix with all of your
+existing music tracks.}
+
 \begin{table}
   \begin{rbtabular}{.75\textwidth}{XXX}%
   {\textbf{Tag}   & \textbf{Type}  & \textbf{Origin}}{}{}