[ruby/yarp] require constant pool capacity to be a power of 2

https://github.com/ruby/yarp/commit/dea8d3f29f

1 files changed, 42 insertions, 4 deletions

diff --git a/yarp/util/yp_constant_pool.c b/yarp/util/yp_constant_pool.c
index 7ae5ea1f10..b8dc5772e7 100644
--- a/yarp/util/yp_constant_pool.c
+++ b/yarp/util/yp_constant_pool.c
@@ -59,10 +59,42 @@ yp_constant_pool_hash(const uint8_t *start, size_t length) {
     return value;
 }
 
+// https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
+static size_t
+next_power_of_two(size_t v) {
+    // Avoid underflow in subtraction on next line.
+    if (v == 0) {
+        // 1 is the nearest power of 2 to 0 (2^0)
+        return 1;
+    }
+    v--;
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+#if defined(__LP64__) || defined(_WIN64)
+    v |= v >> 32;
+#endif
+    v++;
+    return v;
+}
+
+#ifndef NDEBUG
+static bool
+is_power_of_two(size_t size) {
+    return (size & (size - 1)) == 0;
+}
+#endif
+
 // Resize a constant pool to a given capacity.
 static inline bool
 yp_constant_pool_resize(yp_constant_pool_t *pool) {
+    assert(is_power_of_two(pool->capacity));
     size_t next_capacity = pool->capacity * 2;
+    if (next_capacity < pool->capacity) return false;
+
+    const size_t mask = next_capacity - 1;
     yp_constant_t *next_constants = calloc(next_capacity, sizeof(yp_constant_t));
     if (next_constants == NULL) return false;
 
@@ -74,13 +106,13 @@ yp_constant_pool_resize(yp_constant_pool_t *pool) {
         // If an id is set on this constant, then we know we have content here.
         // In this case we need to insert it into the next constant pool.
         if (constant->id != 0) {
-            size_t next_index = constant->hash % next_capacity;
+            size_t next_index = constant->hash & mask;
 
             // This implements linear scanning to find the next available slot
             // in case this index is already taken. We don't need to bother
             // comparing the values since we know that the hash is unique.
             while (next_constants[next_index].id != 0) {
-                next_index = (next_index + 1) % next_capacity;
+                next_index = (next_index + 1) & mask;
             }
 
             // Here we copy over the entire constant, which includes the id so
@@ -98,6 +130,10 @@ yp_constant_pool_resize(yp_constant_pool_t *pool) {
 // Initialize a new constant pool with a given capacity.
 bool
 yp_constant_pool_init(yp_constant_pool_t *pool, size_t capacity) {
+    const size_t size_t_max = (~((size_t) 0));
+    if (capacity >= ((size_t_max / 2) + 1)) return false;
+
+    capacity = next_power_of_two(capacity);
     pool->constants = calloc(capacity, sizeof(yp_constant_t));
     if (pool->constants == NULL) return false;
 
@@ -113,8 +149,10 @@ yp_constant_pool_insert(yp_constant_pool_t *pool, const uint8_t *start, size_t l
         if (!yp_constant_pool_resize(pool)) return 0;
     }
 
+    assert(is_power_of_two(pool->capacity));
+    const size_t mask = pool->capacity - 1;
     size_t hash = yp_constant_pool_hash(start, length);
-    size_t index = hash % pool->capacity;
+    size_t index = hash & mask;
     yp_constant_t *constant;
 
     while (constant = &pool->constants[index], constant->id != 0) {
@@ -143,7 +181,7 @@ yp_constant_pool_insert(yp_constant_pool_t *pool, const uint8_t *start, size_t l
             return constant->id;
         }
 
-        index = (index + 1) % pool->capacity;
+        index = (index + 1) & mask;
     }
 
     pool->size++;