From c16dbbfd1fb7bf4bc268a4693bbed21497456b30 Mon Sep 17 00:00:00 2001 From: Paul Sauro Date: Wed, 28 Aug 2024 22:55:52 +0200 Subject: 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 --- apps/tagtree.c | 228 +++++++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 164 insertions(+), 64 deletions(-) (limited to 'apps/tagtree.c') 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; -- cgit v1.2.3