Bug - Allow sparse bitmap range operations to span sparse blocks draft
authorJon Coppeard <jcoppeard@mozilla.com>
Thu, 16 Jan 2020 18:21:02 +0000
changeset 2598867 2cb5bf731794e716bff635b3d693effb43c7225c
parent 2597305 e35e78857fe0e081e5c2c875dc6f76f600080e2b
child 2598868 2ea66637e60a83c94ba7bad1ff95b71ec0223f44
push id476910
push userjcoppeard@mozilla.com
push dateThu, 16 Jan 2020 18:31:49 +0000
treeherdertry@7ee4b4a50a4e [default view] [failures only]
milestone74.0a1
Bug - Allow sparse bitmap range operations to span sparse blocks
js/src/ds/Bitmap.cpp
js/src/ds/Bitmap.h
js/src/jsapi-tests/moz.build
js/src/jsapi-tests/testBitmap.cpp
--- a/js/src/ds/Bitmap.cpp
+++ b/js/src/ds/Bitmap.cpp
@@ -99,21 +99,24 @@ void SparseBitmap::bitwiseOrInto(DenseBi
     for (size_t i = 0; i < numWords; i++) {
       other.word(blockWord + i) |= block[i];
     }
   }
 }
 
 void SparseBitmap::bitwiseOrRangeInto(size_t wordStart, size_t numWords,
                                       uintptr_t* target) const {
-  size_t blockWord = blockStartWord(wordStart);
+  size_t i = 0;
+  while (i < numWords) {
+    size_t blockWord = blockStartWord(wordStart + i);
+    BitBlock* block = getBlock(blockWord / WordsInBlock);
 
-  // We only support using a single bit block in this API.
-  MOZ_ASSERT(numWords &&
-             (blockWord == blockStartWord(wordStart + numWords - 1)));
-
-  BitBlock* block = getBlock(blockWord / WordsInBlock);
-  if (block) {
-    for (size_t i = 0; i < numWords; i++) {
-      target[i] |= (*block)[wordStart - blockWord + i];
+    size_t blockWordEnd = blockWord + WordsInBlock;
+    size_t runEnd = std::min(numWords, blockWordEnd - wordStart);
+    if (block) {
+      for (; i < runEnd; i++) {
+        target[i] |= (*block)[wordStart - blockWord + i];
+      }
+    } else {
+      i += runEnd;
     }
   }
 }
--- a/js/src/ds/Bitmap.h
+++ b/js/src/ds/Bitmap.h
@@ -142,17 +142,15 @@ class SparseBitmap {
   }
 
   bool getBit(size_t bit) const;
 
   void bitwiseAndWith(const DenseBitmap& other);
   void bitwiseOrWith(const SparseBitmap& other);
   void bitwiseOrInto(DenseBitmap& other) const;
 
-  // Currently, this API only supports a range of words that is in a single bit
-  // block.
   void bitwiseOrRangeInto(size_t wordStart, size_t numWords,
                           uintptr_t* target) const;
 };
 
 }  // namespace js
 
 #endif  // ds_Bitmap_h
--- a/js/src/jsapi-tests/moz.build
+++ b/js/src/jsapi-tests/moz.build
@@ -13,16 +13,17 @@ UNIFIED_SOURCES += [
     'selfTest.cpp',
     'testAddPropertyPropcache.cpp',
     'testArgumentsObject.cpp',
     'testArrayBuffer.cpp',
     'testArrayBufferView.cpp',
     'testArrayBufferWithUserOwnedContents.cpp',
     'testAtomicOperations.cpp',
     'testAtomizeUtf8NonAsciiLatin1CodePoint.cpp',
+    'testBitmap.cpp',
     'testBoundFunction.cpp',
     'testBug604087.cpp',
     'testCallArgs.cpp',
     'testCallNonGenericMethodOnProxy.cpp',
     'testChromeBuffer.cpp',
     'testCompileNonSyntactic.cpp',
     'testCompileUtf8.cpp',
     'testDateToLocaleString.cpp',
new file mode 100644
--- /dev/null
+++ b/js/src/jsapi-tests/testBitmap.cpp
@@ -0,0 +1,133 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/PodOperations.h"
+
+#include "ds/Bitmap.h"
+
+#include "jsapi-tests/tests.h"
+
+BEGIN_TEST(testSparseBitmapBasics) {
+  SparseBitmap bitmap;
+
+  // Test bits in first block are initially zero.
+  for (size_t i = 0; i < 100; i++) {
+    CHECK(!bitmap.getBit(i));
+  }
+
+  // Test bits in different blocks are initially zero.
+  for (size_t i = 0; i < 100; i++) {
+    CHECK(!bitmap.getBit(i * 1000));
+  }
+
+  // Set some bits in the first block and check they are set.
+  for (size_t i = 0; i < 100; i += 2) {
+    bitmap.setBit(i);
+  }
+  for (size_t i = 0; i < 100; i++) {
+    CHECK(bitmap.getBit(i) == ((i % 2) == 0));
+  }
+
+  // Set some bits in different blocks and check they are set.
+  for (size_t i = 0; i < 100; i += 2) {
+    bitmap.setBit(i * 1000);
+  }
+  for (size_t i = 0; i < 100; i++) {
+    CHECK(bitmap.getBit(i * 1000) == ((i % 2) == 0));
+  }
+
+  // Create another bitmap with different bits set.
+  SparseBitmap other;
+  for (size_t i = 1; i < 100; i += 2) {
+    other.setBit(i * 1000);
+  }
+  for (size_t i = 0; i < 100; i++) {
+    CHECK(other.getBit(i * 1000) == ((i % 2) != 0));
+  }
+
+  // OR some bits into this bitmap and check the result.
+  bitmap.bitwiseOrWith(other);
+  for (size_t i = 0; i < 100; i++) {
+    CHECK(bitmap.getBit(i * 1000));
+  }
+
+  // AND some bits into this bitmap and check the result.
+  DenseBitmap dense;
+  size_t wordCount = (100 * 1000) / JS_BITS_PER_WORD + 1;
+  CHECK(dense.ensureSpace(wordCount));
+  other.bitwiseOrInto(dense);
+  bitmap.bitwiseAndWith(dense);
+  for (size_t i = 0; i < 100; i++) {
+    CHECK(bitmap.getBit(i * 1000) == ((i % 2) != 0));
+  }
+
+  return true;
+}
+END_TEST(testSparseBitmapBasics)
+
+BEGIN_TEST(testSparseBitmapExternal) {
+  // Testing ORing data into an external array.
+
+  // Must match definition of SparseBitmap::Woodblock.
+  size_t wordsInBlock = 4096 / sizeof(uintptr_t);
+
+  // Populate bitmap with test data.
+  size_t bitsInBlock = wordsInBlock * JS_BITS_PER_WORD;
+  size_t bitCount = bitsInBlock * 3;
+  size_t wordCount = bitCount / sizeof(uintptr_t);
+  SparseBitmap bitmap;
+  for (size_t i = 0; i < wordCount; i++) {
+    setBitsToValue(bitmap, i * JS_BITS_PER_WORD, i + 1);
+  }
+
+  // Copy a single word.
+  uintptr_t target[wordCount];
+  mozilla::PodZero(target, wordCount);
+  bitmap.bitwiseOrRangeInto(0, 1, target);
+  CHECK(checkValue(target, 0, 1));
+  CHECK(checkValue(target, 1, 0));
+
+  // Copy a word at an offset.
+  mozilla::PodZero(target, wordCount);
+  bitmap.bitwiseOrRangeInto(1, 1, target);
+  CHECK(checkValue(target, 0, 2));
+  CHECK(checkValue(target, 1, 0));
+
+  // Copy two words spanning a block boundary.
+  mozilla::PodZero(target, wordCount);
+  size_t i = wordsInBlock - 1;
+  bitmap.bitwiseOrRangeInto(i, 2, target);
+  CHECK(checkValue(target, 0, i + 1));
+  CHECK(checkValue(target, 1, i + 2));
+  CHECK(checkValue(target, 2, 0));
+
+  // Copy a region spanning three blocks.
+  mozilla::PodZero(target, wordCount);
+  bitmap.bitwiseOrRangeInto(i, wordsInBlock + 2, target);
+  for (size_t j = 0; j < wordsInBlock + 2; j++) {
+    CHECK(checkValue(target, j, j + i + 1));
+  }
+  CHECK(checkValue(target, wordsInBlock + 3, 0));
+
+  return true;
+}
+
+void setBitsToValue(SparseBitmap& bitmap, size_t bitOffset, uint32_t value) {
+  const size_t maxBit = 16;
+  MOZ_ASSERT(value < (1 << maxBit));
+  for (size_t i = 0; i < maxBit; i++) {
+    if (value & (1 << i)) {
+      bitmap.setBit(bitOffset + i);
+    }
+  }
+}
+
+bool checkValue(uintptr_t* data, size_t index, int32_t value) {
+  return data[index] == value;
+}
+
+END_TEST(testSparseBitmapExternal)