From ab31c2432225f9e82fbfe6a15cef14e8f65d3f05 Mon Sep 17 00:00:00 2001
From: Piotr Makal <pmakal>
Date: Mon, 28 Jun 2021 19:25:40 +1000
Subject: BLI_rand: support for randomizing bitmaps

Add utility functions:

- BLI_bitmap_randomize
- BLI_rng_shuffle_bitmap

Part of D11685
---
 source/blender/blenlib/BLI_rand.h     |  6 ++++++
 source/blender/blenlib/intern/rand.cc | 37 +++++++++++++++++++++++++++++------
 2 files changed, 37 insertions(+), 6 deletions(-)

(limited to 'source/blender/blenlib')

diff --git a/source/blender/blenlib/BLI_rand.h b/source/blender/blenlib/BLI_rand.h
index ec74cef9311..f8627952628 100644
--- a/source/blender/blenlib/BLI_rand.h
+++ b/source/blender/blenlib/BLI_rand.h
@@ -71,6 +71,9 @@ void BLI_rng_shuffle_array(struct RNG *rng,
                            unsigned int elem_size_i,
                            unsigned int elem_tot) ATTR_NONNULL(1, 2);
 
+void BLI_rng_shuffle_bitmap(struct RNG *rng, unsigned int *bitmap, unsigned int bits_tot)
+    ATTR_NONNULL(1, 2);
+
 /** Note that skipping is as slow as generating n numbers! */
 void BLI_rng_skip(struct RNG *rng, int n) ATTR_NONNULL(1);
 
@@ -89,6 +92,9 @@ void BLI_array_randomize(void *data,
                          unsigned int elem_tot,
                          unsigned int seed);
 
+void BLI_bitmap_randomize(unsigned int *bitmap, unsigned int bits_tot, unsigned int seed)
+    ATTR_NONNULL(1);
+
 /** Better seed for the random number generator, using noise.c hash[] */
 /** Allows up to BLENDER_MAX_THREADS threads to address */
 void BLI_thread_srandom(int thread, unsigned int seed);
diff --git a/source/blender/blenlib/intern/rand.cc b/source/blender/blenlib/intern/rand.cc
index 8dbfffbad20..db5e08d37ce 100644
--- a/source/blender/blenlib/intern/rand.cc
+++ b/source/blender/blenlib/intern/rand.cc
@@ -28,6 +28,7 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_bitmap.h"
 #include "BLI_math.h"
 #include "BLI_rand.h"
 #include "BLI_rand.hh"
@@ -149,18 +150,16 @@ void BLI_rng_get_tri_sample_float_v3(
 
 void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_tot)
 {
-  const uint elem_size = elem_size_i;
-  unsigned int i = elem_tot;
-  void *temp;
-
   if (elem_tot <= 1) {
     return;
   }
 
-  temp = malloc(elem_size);
+  const uint elem_size = elem_size_i;
+  unsigned int i = elem_tot;
+  void *temp = malloc(elem_size);
 
   while (i--) {
-    unsigned int j = BLI_rng_get_uint(rng) % elem_tot;
+    const unsigned int j = BLI_rng_get_uint(rng) % elem_tot;
     if (i != j) {
       void *iElem = (unsigned char *)data + i * elem_size_i;
       void *jElem = (unsigned char *)data + j * elem_size_i;
@@ -173,6 +172,24 @@ void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsig
   free(temp);
 }
 
+void BLI_rng_shuffle_bitmap(struct RNG *rng, BLI_bitmap *bitmap, unsigned int bits_tot)
+{
+  if (bits_tot <= 1) {
+    return;
+  }
+
+  unsigned int i = bits_tot;
+  while (i--) {
+    const unsigned int j = BLI_rng_get_uint(rng) % bits_tot;
+    if (i != j) {
+      const bool i_bit = BLI_BITMAP_TEST(bitmap, i);
+      const bool j_bit = BLI_BITMAP_TEST(bitmap, j);
+      BLI_BITMAP_SET(bitmap, i, j_bit);
+      BLI_BITMAP_SET(bitmap, j, i_bit);
+    }
+  }
+}
+
 /**
  * Simulate getting \a n random values.
  *
@@ -216,6 +233,14 @@ void BLI_array_randomize(void *data,
   BLI_rng_shuffle_array(&rng, data, elem_size, elem_tot);
 }
 
+void BLI_bitmap_randomize(BLI_bitmap *bitmap, unsigned int bits_tot, unsigned int seed)
+{
+  RNG rng;
+
+  BLI_rng_seed(&rng, seed);
+  BLI_rng_shuffle_bitmap(&rng, bitmap, bits_tot);
+}
+
 /* ********* for threaded random ************** */
 
 static RNG rng_tab[BLENDER_MAX_THREADS];
-- 
cgit v1.2.3