14 files changed, 146 insertions, 5 deletions
diff --git a/source/blender/blenlib/BLI_bitmap.h b/source/blender/blenlib/BLI_bitmap.h
index 19d8525311c..973cc5c3d1e 100644
--- a/source/blender/blenlib/BLI_bitmap.h
+++ b/source/blender/blenlib/BLI_bitmap.h
@@ -27,7 +27,7 @@ typedef unsigned int BLI_bitmap;
 /**
  * Number of blocks needed to hold '_num' bits.
  */
-#define _BITMAP_NUM_BLOCKS(_num) (((_num) >> _BITMAP_POWER) + 1)
+#define _BITMAP_NUM_BLOCKS(_num) (((_num) + _BITMAP_MASK) >> _BITMAP_POWER)
 
 /**
  * Size (in bytes) used to hold '_num' bits.
@@ -54,6 +54,11 @@ typedef unsigned int BLI_bitmap;
    ((BLI_bitmap *)BLI_memarena_calloc(_mem, BLI_BITMAP_SIZE(_num))))
 
 /**
+ * Declares a bitmap as a variable.
+ */
+#define BLI_BITMAP_DECLARE(_name, _num) BLI_bitmap _name[_BITMAP_NUM_BLOCKS(_num)] = {}
+
+/**
  * Get the value of a single bit at '_index'.
  */
 #define BLI_BITMAP_TEST(_bitmap, _index) \
@@ -137,6 +142,12 @@ void BLI_bitmap_and_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits);
  */
 void BLI_bitmap_or_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits);
 
+/**
+ * Find index of the lowest unset bit.
+ * Returns -1 if all the bits are set.
+ */
+int BLI_bitmap_find_first_unset(const BLI_bitmap *bitmap, size_t bits);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/blenlib/BLI_index_range.hh b/source/blender/blenlib/BLI_index_range.hh
index bd0a7e5bb7a..6fcc560d856 100644
--- a/source/blender/blenlib/BLI_index_range.hh
+++ b/source/blender/blenlib/BLI_index_range.hh
@@ -198,6 +198,16 @@ class IndexRange {
   }
 
   /**
+   * Get the element one before the beginning. The returned value is undefined when the range is
+   * empty, and the range must start after zero already.
+   */
+  constexpr int64_t one_before_start() const
+  {
+    BLI_assert(start_ > 0);
+    return start_ - 1;
+  }
+
+  /**
    * Get the element one after the end. The returned value is undefined when the range is empty.
    */
   constexpr int64_t one_after_last() const
diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h
index 2cd2a299d53..c2dafbe3a1a 100644
--- a/source/blender/blenlib/BLI_math_matrix.h
+++ b/source/blender/blenlib/BLI_math_matrix.h
@@ -238,6 +238,7 @@ bool invert_m3_ex(float m[3][3], float epsilon);
 bool invert_m3_m3_ex(float m1[3][3], const float m2[3][3], float epsilon);
 
 bool invert_m3(float R[3][3]);
+bool invert_m2_m2(float R[2][2], const float A[2][2]);
 bool invert_m3_m3(float R[3][3], const float A[3][3]);
 bool invert_m4(float R[4][4]);
 bool invert_m4_m4(float R[4][4], const float A[4][4]);
diff --git a/source/blender/blenlib/BLI_math_rotation.hh b/source/blender/blenlib/BLI_math_rotation.hh
index e8b746b34df..50a062162ad 100644
--- a/source/blender/blenlib/BLI_math_rotation.hh
+++ b/source/blender/blenlib/BLI_math_rotation.hh
@@ -15,4 +15,13 @@ namespace blender::math {
  */
 float3 rotate_direction_around_axis(const float3 &direction, const float3 &axis, float angle);
 
+/**
+ * Rotate any arbitrary \a vector around the \a center position, with a unit-length \a axis
+ * and the specified \a angle.
+ */
+float3 rotate_around_axis(const float3 &vector,
+                          const float3 &center,
+                          const float3 &axis,
+                          float angle);
+
 }  // namespace blender::math
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 95b4987596e..d39a586206f 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -424,6 +424,7 @@ if(WITH_GTESTS)
     tests/BLI_array_store_test.cc
     tests/BLI_array_test.cc
     tests/BLI_array_utils_test.cc
+    tests/BLI_bitmap_test.cc
     tests/BLI_bounds_test.cc
     tests/BLI_color_test.cc
     tests/BLI_cpp_type_test.cc
diff --git a/source/blender/blenlib/intern/bitmap.c b/source/blender/blenlib/intern/bitmap.c
index 7fcbc31c066..2cc2fbc3e2f 100644
--- a/source/blender/blenlib/intern/bitmap.c
+++ b/source/blender/blenlib/intern/bitmap.c
@@ -11,6 +11,7 @@
 #include <string.h>
 
 #include "BLI_bitmap.h"
+#include "BLI_math_bits.h"
 #include "BLI_utildefines.h"
 
 void BLI_bitmap_set_all(BLI_bitmap *bitmap, bool set, size_t bits)
@@ -46,3 +47,22 @@ void BLI_bitmap_or_all(BLI_bitmap *dst, const BLI_bitmap *src, size_t bits)
     dst[i] |= src[i];
   }
 }
+
+int BLI_bitmap_find_first_unset(const BLI_bitmap *bitmap, const size_t bits)
+{
+  const size_t blocks_num = _BITMAP_NUM_BLOCKS(bits);
+  int result = -1;
+  /* Skip over completely set blocks. */
+  int index = 0;
+  while (index < blocks_num && bitmap[index] == ~0u) {
+    index++;
+  }
+  if (index < blocks_num) {
+    /* Found a partially used block: find the lowest unused bit. */
+    const uint m = ~bitmap[index];
+    BLI_assert(m != 0);
+    const uint bit_index = bitscan_forward_uint(m);
+    result = bit_index + (index << _BITMAP_POWER);
+  }
+  return result;
+}
diff --git a/source/blender/blenlib/intern/filereader_zstd.c b/source/blender/blenlib/intern/filereader_zstd.c
index 5f114f24fb0..aeb000e9754 100644
--- a/source/blender/blenlib/intern/filereader_zstd.c
+++ b/source/blender/blenlib/intern/filereader_zstd.c
@@ -281,7 +281,10 @@ static void zstd_close(FileReader *reader)
   if (zstd->reader.seek) {
     MEM_freeN(zstd->seek.uncompressed_ofs);
     MEM_freeN(zstd->seek.compressed_ofs);
-    MEM_freeN(zstd->seek.cached_content);
+    /* When an error has occurred this may be NULL, see: T99744. */
+    if (zstd->seek.cached_content) {
+      MEM_freeN(zstd->seek.cached_content);
+    }
   }
   else {
     MEM_freeN((void *)zstd->in_buf.src);
diff --git a/source/blender/blenlib/intern/generic_virtual_array.cc b/source/blender/blenlib/intern/generic_virtual_array.cc
index 28bc66e8524..1e548d006b2 100644
--- a/source/blender/blenlib/intern/generic_virtual_array.cc
+++ b/source/blender/blenlib/intern/generic_virtual_array.cc
@@ -323,6 +323,7 @@ GVArraySpan::GVArraySpan(GVArraySpan &&other)
   else {
     data_ = owned_data_;
   }
+  other.owned_data_ = nullptr;
   other.data_ = nullptr;
   other.size_ = 0;
 }
@@ -393,6 +394,7 @@ GMutableVArraySpan::GMutableVArraySpan(GMutableVArraySpan &&other)
   else {
     data_ = owned_data_;
   }
+  other.owned_data_ = nullptr;
   other.data_ = nullptr;
   other.size_ = 0;
 }
diff --git a/source/blender/blenlib/intern/index_mask.cc b/source/blender/blenlib/intern/index_mask.cc
index f3590e4a41c..e9af183d60d 100644
--- a/source/blender/blenlib/intern/index_mask.cc
+++ b/source/blender/blenlib/intern/index_mask.cc
@@ -142,6 +142,7 @@ IndexMask find_indices_based_on_predicate__merge(
   int64_t result_mask_size = 0;
   for (Vector<Vector<int64_t>> &local_sub_masks : sub_masks) {
     for (Vector<int64_t> &sub_mask : local_sub_masks) {
+      BLI_assert(!sub_mask.is_empty());
       all_vectors.append(&sub_mask);
       result_mask_size += sub_mask.size();
     }
@@ -232,7 +233,9 @@ IndexMask find_indices_from_virtual_array(const IndexMask indices_to_check,
             }
           }
         });
-        sub_masks.local().append(std::move(masked_indices));
+        if (!masked_indices.is_empty()) {
+          sub_masks.local().append(std::move(masked_indices));
+        }
       });
 
   return detail::find_indices_based_on_predicate__merge(indices_to_check, sub_masks, r_indices);
diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c
index ce9abc36cad..fcd017b3082 100644
--- a/source/blender/blenlib/intern/math_matrix.c
+++ b/source/blender/blenlib/intern/math_matrix.c
@@ -1116,6 +1116,22 @@ double determinant_m3_array_db(const double m[3][3])
           m[2][0] * (m[0][1] * m[1][2] - m[0][2] * m[1][1]));
 }
 
+bool invert_m2_m2(float m1[2][2], const float m2[2][2])
+{
+  adjoint_m2_m2(m1, m2);
+  float det = determinant_m2(m2[0][0], m2[1][0], m2[0][1], m2[1][1]);
+
+  bool success = (det != 0.0f);
+  if (success) {
+    m1[0][0] /= det;
+    m1[1][0] /= det;
+    m1[0][1] /= det;
+    m1[1][1] /= det;
+  }
+
+  return success;
+}
+
 bool invert_m3_ex(float m[3][3], const float epsilon)
 {
   float tmp[3][3];
diff --git a/source/blender/blenlib/intern/math_rotation.cc b/source/blender/blenlib/intern/math_rotation.cc
index 74300d55954..091e8af85d9 100644
--- a/source/blender/blenlib/intern/math_rotation.cc
+++ b/source/blender/blenlib/intern/math_rotation.cc
@@ -23,4 +23,17 @@ float3 rotate_direction_around_axis(const float3 &direction, const float3 &axis,
   return axis_scaled + diff * std::cos(angle) + cross * std::sin(angle);
 }
 
+float3 rotate_around_axis(const float3 &vector,
+                          const float3 &center,
+                          const float3 &axis,
+                          const float angle)
+
+{
+  float3 result = vector - center;
+  float mat[3][3];
+  axis_angle_normalized_to_mat3(mat, axis, angle);
+  mul_m3_v3(mat, result);
+  return result + center;
+}
+
 }  // namespace blender::math
diff --git a/source/blender/blenlib/intern/rct.c b/source/blender/blenlib/intern/rct.c
index 0bb606c288e..7248db5b718 100644
--- a/source/blender/blenlib/intern/rct.c
+++ b/source/blender/blenlib/intern/rct.c
@@ -265,7 +265,7 @@ bool BLI_rcti_isect_segment(const rcti *rect, const int s1[2], const int s2[2])
   /* diagonal: [/] */
   tvec1[0] = rect->xmin;
   tvec1[1] = rect->ymin;
-  tvec2[0] = rect->xmin;
+  tvec2[0] = rect->xmax;
   tvec2[1] = rect->ymax;
   if (isect_segments_i(s1, s2, tvec1, tvec2)) {
     return true;
@@ -311,7 +311,7 @@ bool BLI_rctf_isect_segment(const rctf *rect, const float s1[2], const float s2[
   /* diagonal: [/] */
   tvec1[0] = rect->xmin;
   tvec1[1] = rect->ymin;
-  tvec2[0] = rect->xmin;
+  tvec2[0] = rect->xmax;
   tvec2[1] = rect->ymax;
   if (isect_segments_fl(s1, s2, tvec1, tvec2)) {
     return true;
diff --git a/source/blender/blenlib/tests/BLI_bitmap_test.cc b/source/blender/blenlib/tests/BLI_bitmap_test.cc
new file mode 100644
index 00000000000..fb9e03e3136
--- /dev/null
+++ b/source/blender/blenlib/tests/BLI_bitmap_test.cc
@@ -0,0 +1,46 @@
+/* SPDX-License-Identifier: Apache-2.0 */
+
+#include "BLI_bitmap.h"
+#include "testing/testing.h"
+
+namespace blender::tests {
+
+TEST(bitmap, empty_is_all_unset)
+{
+  BLI_BITMAP_DECLARE(bitmap, 10);
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_FALSE(BLI_BITMAP_TEST_BOOL(bitmap, i));
+  }
+}
+
+TEST(bitmap, find_first_unset_empty)
+{
+  BLI_BITMAP_DECLARE(bitmap, 10);
+  EXPECT_EQ(0, BLI_bitmap_find_first_unset(bitmap, 10));
+}
+
+TEST(bitmap, find_first_unset_full)
+{
+  BLI_BITMAP_DECLARE(bitmap, 10);
+  BLI_bitmap_flip_all(bitmap, 10);
+  EXPECT_EQ(-1, BLI_bitmap_find_first_unset(bitmap, 10));
+}
+
+TEST(bitmap, find_first_unset_middle)
+{
+  BLI_BITMAP_DECLARE(bitmap, 100);
+  BLI_bitmap_flip_all(bitmap, 100);
+  /* Turn some bits off */
+  BLI_BITMAP_DISABLE(bitmap, 53);
+  BLI_BITMAP_DISABLE(bitmap, 81);
+  BLI_BITMAP_DISABLE(bitmap, 85);
+  BLI_BITMAP_DISABLE(bitmap, 86);
+
+  /* Find lowest unset bit, and set it. */
+  EXPECT_EQ(53, BLI_bitmap_find_first_unset(bitmap, 100));
+  BLI_BITMAP_ENABLE(bitmap, 53);
+  /* Now should find the next lowest bit. */
+  EXPECT_EQ(81, BLI_bitmap_find_first_unset(bitmap, 100));
+}
+
+}  // namespace blender::tests
diff --git a/source/blender/blenlib/tests/BLI_index_range_test.cc b/source/blender/blenlib/tests/BLI_index_range_test.cc
index 10f6784cd44..f5b994d409a 100644
--- a/source/blender/blenlib/tests/BLI_index_range_test.cc
+++ b/source/blender/blenlib/tests/BLI_index_range_test.cc
@@ -105,6 +105,12 @@ TEST(index_range, OneAfterEnd)
   EXPECT_EQ(range.one_after_last(), 8);
 }
 
+TEST(index_range, OneBeforeStart)
+{
+  IndexRange range = IndexRange(5, 3);
+  EXPECT_EQ(range.one_before_start(), 4);
+}
+
 TEST(index_range, Start)
 {
   IndexRange range = IndexRange(6, 2);