Tagtree selective random playlist -- rewrite

this is a bit cleaner without so much ram (or code) used

Credit to goes to Paul Sauro (OlsroFR) as this was his idea

if available space exists in the pluginbuf it uses fisher yates
shuffle to get good probability
and falls back to random permutation if not

Change-Id: I413078a48314ce4c6f3722c78e0858a407b7b46e

1 files changed, 94 insertions, 104 deletions

diff --git a/apps/tagtree.c b/apps/tagtree.c
index 562ad44863..126fb04678 100644
--- a/apps/tagtree.c
+++ b/apps/tagtree.c
@@ -57,6 +57,7 @@
 #include "strnatcmp.h"
 #include "panic.h"
 #include "onplay.h"
+#include "plugin.h"
 
 #define str_or_empty(x) (x ? x : "(NULL)")
 
@@ -117,14 +118,6 @@ enum variables {
 #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
 
@@ -2141,30 +2134,26 @@ static void swap_array_bool(bool *a, bool *b)
 /**
  * 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.
+ *  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)
+static bool* fill_random_playlist_indexes(bool *bool_array, size_t arr_sz,
+                                         size_t track_count, size_t max_slots)
 {
-    for (int i = size - 1; i > 0; i--)
+    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(&array[i], &array[j]);
+        swap_array_bool(&bool_array[i], &bool_array[j]);
     }
-}
-
-static bool fill_random_playlist_indexes(int current_segment_n,
-                                         int current_segment_max_space)
-{
-    if (current_segment_n == 0 || current_segment_max_space == 0)
-        return false;
-    if (current_segment_max_space > current_segment_n)
-        current_segment_max_space = current_segment_n;
-    for (int i = 0; i < current_segment_n; i++)
-        selective_random_playlist_indexes[i] = i < current_segment_max_space;
-    srand(current_tick);
-    shuffle_bool_array(selective_random_playlist_indexes, current_segment_n);
-    return true;
+    return bool_array;
 }
 
 static bool insert_all_playlist(struct tree_context *c,
@@ -2175,6 +2164,9 @@ static bool insert_all_playlist(struct tree_context *c,
     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);
@@ -2213,113 +2205,111 @@ static bool insert_all_playlist(struct tree_context *c,
     splash_progress_set_delay(HZ / 2); /* wait 1/2 sec before progress */
     n = c->filesindir;
 
-    int max_playlist_size = playlist_get_current()->max_playlist_size;
-    int playlist_amount = playlist_get_current()->amount;
-    int segment_size = INSERT_ALL_PLAYLIST_MAX_SEGMENT_SIZE;
-    int segments_count = n / segment_size;
-    int leftovers_segment_size = n - (segments_count * segment_size);
-    bool fill_randomly = false;
-
     if (playlist == NULL)
     {
-        bool will_exceed = n > 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)
+        int max_playlist_size = playlist_get_current()->max_playlist_size;
+        slots_remaining = max_playlist_size - playlist_get_current()->amount;
+        if (slots_remaining <= 0)
         {
-            segment_size--; // -1 to all other segments
-            leftovers_segment_size += segments_count;
+            logf("Playlist has no space remaining");
+            cpu_boost(false);
+            return false;
         }
-    }
-    if (leftovers_segment_size > 0)
-        segments_count += 1;
-
-    int max_available_space = max_playlist_size - playlist_amount;
-    int max_space_per_segment = max_available_space / segments_count;
-
-    int remaining_space =
-       max_available_space - (max_space_per_segment * 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_space_per_segment * segments_count + remaining_space);
-        /* logf("sz=%d lsz=%d sc=%d rcps=%d", segment_size, leftovers_segment_size,
-                segments_count, max_available_space_per_segment); */
+        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 < segments_count; i++)
+    for (int i = 0; i < n; i++)
     {
-        int cur_segment_size = segment_size;
-        int cur_segment_start = i * segment_size;
-        int cur_segment_end;
-        int space_per_segment = max_space_per_segment;
-
-        if (i + 1 >= segments_count && leftovers_segment_size > 0)
-        {
-            /* add any remaining tracks to the last segment */
-            space_per_segment += remaining_space;
-            cur_segment_size = leftovers_segment_size;
-        }
-        else if (fill_randomly)
+        if (TIME_AFTER(current_tick, last_tick + HZ/4))
         {
-            /* add an extra track to some of the segments */
-            if (remaining_space > 0 && (i & 7) != 7)
+            splash_progress(i, n, "%s (%s)", str(LANG_WAIT), str(LANG_OFF_ABORT));
+            if (action_userabort(TIMEOUT_NOBLOCK))
             {
-                space_per_segment++;
-                remaining_space--;
+                exit_loop_now = true;
+                break;
             }
+            last_tick = current_tick;
         }
-        if (fill_randomly)
-        {
-            fill_randomly = fill_random_playlist_indexes(cur_segment_size,
-                                                         space_per_segment);
-        }
-
-        cur_segment_end = cur_segment_start + cur_segment_size;
 
-        for (int j = cur_segment_start; j < cur_segment_end && !exit_loop_now; j++)
+        if (playlist == NULL)
         {
-            if (TIME_AFTER(current_tick, last_tick + HZ/4))
+            if (fill_randomly)
             {
-                splash_progress(j, n, "%s (%s)", str(LANG_WAIT), str(LANG_OFF_ABORT));
-                if (action_userabort(TIMEOUT_NOBLOCK))
+                int remaining_tracks = n - i;
+                if (remaining_tracks > slots_remaining)
                 {
-                    exit_loop_now = true;
-                    break;
+                    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;
+                    }
                 }
-                last_tick = current_tick;
             }
+        }
 
-            if (fill_randomly && !selective_random_playlist_indexes[j % segment_size])
-                continue;
-
-            if (!tagcache_retrieve(&tcs, tagtree_get_entry(c, j)->extraseek, tcs.type, buf, sizeof buf))
-                continue;
+        if (!tagcache_retrieve(&tcs, tagtree_get_entry(c, i)->extraseek, tcs.type, buf, sizeof buf))
+            continue;
 
-            if (playlist == NULL)
+        if (playlist == NULL)
+        {
+            if (fill_randomly)
             {
-                if (playlist_insert_track(NULL, buf, position, queue, false) < 0) {
-                    logf("playlist_insert_track failed");
+                if (--slots_remaining <= 0)
+                {
                     exit_loop_now = true;
                     break;
                 }
             }
-            else if (fdprintf(fd, "%s\n", buf) <= 0)
-            {
+
+            if (playlist_insert_track(NULL, buf, position, queue, false) < 0) {
+                logf("playlist_insert_track failed");
                 exit_loop_now = true;
                 break;
             }
-            yield();
-            if (playlist == NULL && position == PLAYLIST_INSERT_FIRST)
-                position = PLAYLIST_INSERT;
         }
+        else if (fdprintf(fd, "%s\n", buf) <= 0)
+        {
+            exit_loop_now = true;
+            break;
+        }
+        yield();
+        if (playlist == NULL && position == PLAYLIST_INSERT_FIRST)
+            position = PLAYLIST_INSERT;
+
         if (exit_loop_now)
             break;
     }