Bug 1586975 - Part 2: Add TwoEntriesHuffmanTable. r=Yoric
☠☠ backed out by 31f16b9b5863 ☠ ☠
authorTooru Fujisawa <arai_a@mac.com>
Mon, 21 Oct 2019 14:31:30 +0000
changeset 498377 fbf2c90da04c85d8253ce146c0b229ef8b4a228f
parent 498376 aa843177070ed83477a9559a9d7eb5bc2f84eaab
child 498378 7f0b3124697b07eff7ba29046f691c27a7009491
push id36717
push usernbeleuzu@mozilla.com
push dateMon, 21 Oct 2019 21:51:55 +0000
treeherdermozilla-central@563f437f24b9 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersYoric
bugs1586975
milestone71.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1586975 - Part 2: Add TwoEntriesHuffmanTable. r=Yoric Differential Revision: https://phabricator.services.mozilla.com/D49561
js/src/frontend/BinASTTokenReaderContext.cpp
js/src/frontend/BinASTTokenReaderContext.h
--- a/js/src/frontend/BinASTTokenReaderContext.cpp
+++ b/js/src/frontend/BinASTTokenReaderContext.cpp
@@ -1598,32 +1598,39 @@ HuffmanKey::HuffmanKey(const uint32_t bi
 
 // ---- Implementation of Huffman Tables
 
 GenericHuffmanTable::Iterator::Iterator(
     typename SingleEntryHuffmanTable::Iterator&& iterator)
     : implementation_(std::move(iterator)) {}
 
 GenericHuffmanTable::Iterator::Iterator(
+    typename TwoEntriesHuffmanTable::Iterator&& iterator)
+    : implementation_(std::move(iterator)) {}
+
+GenericHuffmanTable::Iterator::Iterator(
     typename SingleLookupHuffmanTable::Iterator&& iterator)
     : implementation_(std::move(iterator)) {}
 
 GenericHuffmanTable::Iterator::Iterator(
     typename TwoLookupsHuffmanTable::Iterator&& iterator)
     : implementation_(std::move(iterator)) {}
 
 GenericHuffmanTable::Iterator::Iterator(
     typename ThreeLookupsHuffmanTable::Iterator&& iterator)
     : implementation_(std::move(iterator)) {}
 
 void GenericHuffmanTable::Iterator::operator++() {
   implementation_.match(
       [](typename SingleEntryHuffmanTable::Iterator& iterator) {
         iterator.operator++();
       },
+      [](typename TwoEntriesHuffmanTable::Iterator& iterator) {
+        iterator.operator++();
+      },
       [](typename SingleLookupHuffmanTable::Iterator& iterator) {
         iterator.operator++();
       },
       [](typename TwoLookupsHuffmanTable::Iterator& iterator) {
         iterator.operator++();
       },
       [](typename ThreeLookupsHuffmanTable::Iterator& iterator) {
         iterator.operator++();
@@ -1633,16 +1640,21 @@ void GenericHuffmanTable::Iterator::oper
 bool GenericHuffmanTable::Iterator::operator==(
     const GenericHuffmanTable::Iterator& other) const {
   return implementation_.match(
       [other](const typename SingleEntryHuffmanTable::Iterator& iterator) {
         return iterator ==
                other.implementation_
                    .template as<typename SingleEntryHuffmanTable::Iterator>();
       },
+      [other](const typename TwoEntriesHuffmanTable::Iterator& iterator) {
+        return iterator ==
+               other.implementation_
+                   .template as<typename TwoEntriesHuffmanTable::Iterator>();
+      },
       [other](const typename SingleLookupHuffmanTable::Iterator& iterator) {
         return iterator ==
                other.implementation_
                    .template as<typename SingleLookupHuffmanTable::Iterator>();
       },
       [other](const typename TwoLookupsHuffmanTable::Iterator& iterator) {
         return iterator ==
                other.implementation_
@@ -1658,16 +1670,21 @@ bool GenericHuffmanTable::Iterator::oper
 bool GenericHuffmanTable::Iterator::operator!=(
     const GenericHuffmanTable::Iterator& other) const {
   return implementation_.match(
       [other](const typename SingleEntryHuffmanTable::Iterator& iterator) {
         return iterator !=
                other.implementation_
                    .template as<typename SingleEntryHuffmanTable::Iterator>();
       },
+      [other](const typename TwoEntriesHuffmanTable::Iterator& iterator) {
+        return iterator !=
+               other.implementation_
+                   .template as<typename TwoEntriesHuffmanTable::Iterator>();
+      },
       [other](const typename SingleLookupHuffmanTable::Iterator& iterator) {
         return iterator !=
                other.implementation_
                    .template as<typename SingleLookupHuffmanTable::Iterator>();
       },
       [other](const typename TwoLookupsHuffmanTable::Iterator& iterator) {
         return iterator !=
                other.implementation_
@@ -1680,32 +1697,38 @@ bool GenericHuffmanTable::Iterator::oper
       });
 }
 
 const BinASTSymbol* GenericHuffmanTable::Iterator::operator*() const {
   return implementation_.match(
       [](const typename SingleEntryHuffmanTable::Iterator& iterator) {
         return iterator.operator*();
       },
+      [](const typename TwoEntriesHuffmanTable::Iterator& iterator) {
+        return iterator.operator*();
+      },
       [](const typename SingleLookupHuffmanTable::Iterator& iterator) {
         return iterator.operator*();
       },
       [](const typename TwoLookupsHuffmanTable::Iterator& iterator) {
         return iterator.operator*();
       },
       [](const typename ThreeLookupsHuffmanTable::Iterator& iterator) {
         return iterator.operator*();
       });
 }
 
 const BinASTSymbol* GenericHuffmanTable::Iterator::operator->() const {
   return implementation_.match(
       [](const typename SingleEntryHuffmanTable::Iterator& iterator) {
         return iterator.operator->();
       },
+      [](const typename TwoEntriesHuffmanTable::Iterator& iterator) {
+        return iterator.operator->();
+      },
       [](const typename SingleLookupHuffmanTable::Iterator& iterator) {
         return iterator.operator->();
       },
       [](const typename TwoLookupsHuffmanTable::Iterator& iterator) {
         return iterator.operator->();
       },
       [](const typename ThreeLookupsHuffmanTable::Iterator& iterator) {
         return iterator.operator->();
@@ -1715,16 +1738,19 @@ const BinASTSymbol* GenericHuffmanTable:
 GenericHuffmanTable::GenericHuffmanTable(JSContext*)
     : implementation_(HuffmanTableUnreachable{}) {}
 
 JS::Result<Ok> GenericHuffmanTable::initComplete() {
   return implementation_.match(
       [](SingleEntryHuffmanTable& implementation) -> JS::Result<Ok> {
         MOZ_CRASH("SingleEntryHuffmanTable shouldn't have multiple entries!");
       },
+      [](TwoEntriesHuffmanTable& implementation) -> JS::Result<Ok> {
+        return implementation.initComplete();
+      },
       [](SingleLookupHuffmanTable& implementation) -> JS::Result<Ok> {
         return implementation.initComplete();
       },
       [](TwoLookupsHuffmanTable& implementation) -> JS::Result<Ok> {
         return implementation.initComplete();
       },
       [](ThreeLookupsHuffmanTable& implementation) -> JS::Result<Ok> {
         return implementation.initComplete();
@@ -1735,16 +1761,20 @@ JS::Result<Ok> GenericHuffmanTable::init
 }
 
 typename GenericHuffmanTable::Iterator GenericHuffmanTable::begin() const {
   return implementation_.match(
       [](const SingleEntryHuffmanTable& implementation)
           -> GenericHuffmanTable::Iterator {
         return Iterator(implementation.begin());
       },
+      [](const TwoEntriesHuffmanTable& implementation)
+          -> GenericHuffmanTable::Iterator {
+        return Iterator(implementation.begin());
+      },
       [](const SingleLookupHuffmanTable& implementation)
           -> GenericHuffmanTable::Iterator {
         return Iterator(implementation.begin());
       },
       [](const TwoLookupsHuffmanTable& implementation)
           -> GenericHuffmanTable::Iterator {
         return Iterator(implementation.begin());
       },
@@ -1758,16 +1788,20 @@ typename GenericHuffmanTable::Iterator G
 }
 
 typename GenericHuffmanTable::Iterator GenericHuffmanTable::end() const {
   return implementation_.match(
       [](const SingleEntryHuffmanTable& implementation)
           -> GenericHuffmanTable::Iterator {
         return Iterator(implementation.end());
       },
+      [](const TwoEntriesHuffmanTable& implementation)
+          -> GenericHuffmanTable::Iterator {
+        return Iterator(implementation.end());
+      },
       [](const SingleLookupHuffmanTable& implementation)
           -> GenericHuffmanTable::Iterator {
         return Iterator(implementation.end());
       },
       [](const TwoLookupsHuffmanTable& implementation)
           -> GenericHuffmanTable::Iterator {
         return Iterator(implementation.end());
       },
@@ -1799,16 +1833,22 @@ JS::Result<Ok> GenericHuffmanTable::init
 
   // Make sure that we're initializing.
   MOZ_ASSERT(implementation_.template is<HuffmanTableUnreachable>());
 
   // Make sure we don't accidentally end up with only one symbol.
   MOZ_ASSERT(numberOfSymbols != 1,
              "Should have used `initWithSingleValue` instead");
 
+  if (numberOfSymbols == 2) {
+    implementation_ = {mozilla::VariantType<TwoEntriesHuffmanTable>{}};
+    return implementation_.template as<TwoEntriesHuffmanTable>().initStart(
+        cx, numberOfSymbols, largestBitLength);
+  }
+
   // Find the (hopefully) fastest implementation of HuffmanTable for
   // `largestBitLength`.
   // ...hopefully, only one lookup.
   if (largestBitLength <= SingleLookupHuffmanTable::MAX_BIT_LENGTH) {
     implementation_ = {mozilla::VariantType<SingleLookupHuffmanTable>{}, cx,
                        SingleLookupHuffmanTable::Use::ToplevelTable};
     return implementation_.template as<SingleLookupHuffmanTable>().initStart(
         cx, numberOfSymbols, largestBitLength);
@@ -1831,16 +1871,22 @@ JS::Result<Ok> GenericHuffmanTable::init
 JS::Result<Ok> GenericHuffmanTable::addSymbol(uint32_t bits, uint8_t bitLength,
                                               const BinASTSymbol& value) {
   return implementation_.match(
       [](SingleEntryHuffmanTable&) -> JS::Result<Ok> {
         MOZ_CRASH("SingleEntryHuffmanTable shouldn't have multiple entries!");
         return Ok();
       },
       [bits, bitLength,
+       value](TwoEntriesHuffmanTable&
+                  implementation) mutable /* discard implicit const */
+      -> JS::Result<Ok> {
+        return implementation.addSymbol(bits, bitLength, value);
+      },
+      [bits, bitLength,
        value](SingleLookupHuffmanTable&
                   implementation) mutable /* discard implicit const */
       -> JS::Result<Ok> {
         return implementation.addSymbol(bits, bitLength, value);
       },
       [bits, bitLength,
        value](TwoLookupsHuffmanTable&
                   implementation) mutable /* discard implicit const */
@@ -1858,16 +1904,18 @@ JS::Result<Ok> GenericHuffmanTable::addS
         return Ok();
       });
 }
 
 HuffmanLookupResult GenericHuffmanTable::lookup(HuffmanLookup key) const {
   return implementation_.match(
       [key](const SingleEntryHuffmanTable& implementation)
           -> HuffmanLookupResult { return implementation.lookup(key); },
+      [key](const TwoEntriesHuffmanTable& implementation)
+          -> HuffmanLookupResult { return implementation.lookup(key); },
       [key](const SingleLookupHuffmanTable& implementation)
           -> HuffmanLookupResult { return implementation.lookup(key); },
       [key](const TwoLookupsHuffmanTable& implementation)
           -> HuffmanLookupResult { return implementation.lookup(key); },
       [key](const ThreeLookupsHuffmanTable& implementation)
           -> HuffmanLookupResult { return implementation.lookup(key); },
       [](const HuffmanTableUnreachable&) -> HuffmanLookupResult {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
@@ -1960,16 +2008,78 @@ bool SingleEntryHuffmanTable::Iterator::
     const Iterator& other) const {
   return position_ != other.position_;
 }
 
 HuffmanLookupResult SingleEntryHuffmanTable::lookup(HuffmanLookup key) const {
   return HuffmanLookupResult::found(0, &value_);
 }
 
+TwoEntriesHuffmanTable::Iterator::Iterator(const BinASTSymbol* position)
+    : position_(position) {}
+
+void TwoEntriesHuffmanTable::Iterator::operator++() { position_++; }
+
+const BinASTSymbol* TwoEntriesHuffmanTable::Iterator::operator*() const {
+  return position_;
+}
+
+const BinASTSymbol* TwoEntriesHuffmanTable::Iterator::operator->() const {
+  return position_;
+}
+
+bool TwoEntriesHuffmanTable::Iterator::operator==(const Iterator& other) const {
+  return position_ == other.position_;
+}
+
+bool TwoEntriesHuffmanTable::Iterator::operator!=(const Iterator& other) const {
+  return position_ != other.position_;
+}
+
+JS::Result<Ok> TwoEntriesHuffmanTable::initStart(JSContext* cx,
+                                                 size_t numberOfSymbols,
+                                                 uint8_t largestBitLength) {
+  // Make sure that we're initializing.
+  MOZ_ASSERT(length_ == 0);
+  MOZ_ASSERT(numberOfSymbols == 2);
+  MOZ_ASSERT(largestBitLength == 1);
+  return Ok();
+}
+
+JS::Result<Ok> TwoEntriesHuffmanTable::initComplete() {
+  MOZ_ASSERT(length_ == 2);
+  return Ok();
+}
+
+JS::Result<Ok> TwoEntriesHuffmanTable::addSymbol(uint32_t bits,
+                                                 uint8_t bitLength,
+                                                 const BinASTSymbol& value,
+                                                 reporter) {
+  MOZ_ASSERT(length_ < 2);
+  // Symbols must be ranked by increasing bits length
+  MOZ_ASSERT_IF(length_ == 0, bits == 0);
+  MOZ_ASSERT_IF(length_ == 1, bits == 1);
+
+  // FIXME: Throw soft error instead of assert.
+  MOZ_ASSERT(bitLength == 1);
+
+  values_[length_] = value;
+
+  ++length_;
+  return Ok();
+}
+
+HuffmanLookupResult TwoEntriesHuffmanTable::lookup(HuffmanLookup key) const {
+  MOZ_ASSERT(length_ == 2);
+  // By invariant, bit lengths are 1.
+  const auto index = key.leadingBits(1);
+  MOZ_ASSERT(index < length_);
+  return HuffmanLookupResult::found(1, &values_[index]);
+}
+
 SingleLookupHuffmanTable::Iterator::Iterator(const HuffmanEntry* position)
     : position_(position) {}
 
 void SingleLookupHuffmanTable::Iterator::operator++() { position_++; }
 
 const BinASTSymbol* SingleLookupHuffmanTable::Iterator::operator*() const {
   return &position_->value();
 }
--- a/js/src/frontend/BinASTTokenReaderContext.h
+++ b/js/src/frontend/BinASTTokenReaderContext.h
@@ -349,16 +349,90 @@ class SingleEntryHuffmanTable {
   Iterator end() const { return Iterator(nullptr); }
 
  private:
   BinASTSymbol value_;
 
   friend class HuffmanPreludeReader;
 };
 
+// An implementation of Huffman Tables for two-entry table.
+class TwoEntriesHuffmanTable {
+ public:
+  TwoEntriesHuffmanTable() : length_(0) {}
+  TwoEntriesHuffmanTable(TwoEntriesHuffmanTable&& other) noexcept = default;
+
+  // Initialize a Huffman table containing `numberOfSymbols`.
+  // Symbols must be added with `addSymbol`.
+  // If you initialize with `initStart`, you MUST call `initComplete()`
+  // at the end of initialization.
+  JS::Result<Ok> initStart(JSContext* cx, size_t numberOfSymbols,
+                           uint8_t maxBitLength);
+
+  JS::Result<Ok> initComplete();
+
+  // Add a symbol to a value.
+  JS::Result<Ok> addSymbol(uint32_t bits, uint8_t bitLength,
+                           const BinASTSymbol& value);
+
+  TwoEntriesHuffmanTable(TwoEntriesHuffmanTable&) = delete;
+
+  // Lookup a value in the table.
+  //
+  // The return of this method contains:
+  //
+  // - the resulting value (`nullptr` if the value is not in the table);
+  // - the number of bits in the entry associated to this value.
+  //
+  // Note that entries inside a single table are typically associated to
+  // distinct bit lengths. The caller is responsible for checking
+  // the result of this method and advancing the bitstream by
+  // `result.key().bitLength_` bits.
+  HuffmanLookupResult lookup(HuffmanLookup key) const;
+
+  struct Iterator {
+    explicit Iterator(const BinASTSymbol* position);
+    void operator++();
+    const BinASTSymbol* operator*() const;
+    const BinASTSymbol* operator->() const;
+    bool operator==(const Iterator& other) const;
+    bool operator!=(const Iterator& other) const;
+
+   private:
+    const BinASTSymbol* position_;
+  };
+  Iterator begin() const { return Iterator(std::begin(values_)); }
+  Iterator end() const {
+    MOZ_ASSERT(length_ == 2);
+    return Iterator(std::end(values_));
+  }
+
+  // The number of values in the table.
+  size_t length() const {
+    MOZ_ASSERT(length_ == 2);
+    return 2;
+  }
+
+ private:
+  // A buffer for the values added to this table.
+  //
+  // Only the interval 0..length_ is considered
+  // initialized memory.
+  BinASTSymbol values_[2] = {BinASTSymbol::fromBool(false),
+                             BinASTSymbol::fromBool(false)};
+
+  // The number of elements added to the table.
+  // Invariants:
+  // - during initialization, 0 <= length_ <= 2;
+  // - after initialization, length_ == 2;
+  uint8_t length_;
+
+  friend class HuffmanPreludeReader;
+};
+
 // An implementation of Huffman Tables as a vector designed to allow
 // constant-time lookups at the expense of high space complexity.
 //
 // # Time complexity
 //
 // Lookups take constant time, which essentially consists in two
 // simple vector lookups.
 //
@@ -811,29 +885,31 @@ struct GenericHuffmanTable {
 
   JS::Result<Ok> initComplete();
 
   // The number of values in the table.
   size_t length() const;
 
   struct Iterator {
     explicit Iterator(typename SingleEntryHuffmanTable::Iterator&&);
+    explicit Iterator(typename TwoEntriesHuffmanTable::Iterator&&);
     explicit Iterator(typename SingleLookupHuffmanTable::Iterator&&);
     explicit Iterator(typename TwoLookupsHuffmanTable::Iterator&&);
     explicit Iterator(typename ThreeLookupsHuffmanTable::Iterator&&);
     Iterator(Iterator&&) = default;
     Iterator(const Iterator&) = default;
     void operator++();
     const BinASTSymbol* operator*() const;
     const BinASTSymbol* operator->() const;
     bool operator==(const Iterator& other) const;
     bool operator!=(const Iterator& other) const;
 
    private:
     mozilla::Variant<typename SingleEntryHuffmanTable::Iterator,
+                     typename TwoEntriesHuffmanTable::Iterator,
                      typename SingleLookupHuffmanTable::Iterator,
                      typename TwoLookupsHuffmanTable::Iterator,
                      typename ThreeLookupsHuffmanTable::Iterator>
         implementation_;
   };
 
   // Iterating in the order of insertion.
   Iterator begin() const;
@@ -848,19 +924,19 @@ struct GenericHuffmanTable {
   //
   // Note that entries inside a single table are typically associated to
   // distinct bit lengths. The caller is responsible for checking
   // the result of this method and advancing the bitstream by
   // `result.key().bitLength_` bits.
   HuffmanLookupResult lookup(HuffmanLookup key) const;
 
  private:
-  mozilla::Variant<SingleEntryHuffmanTable, SingleLookupHuffmanTable,
-                   TwoLookupsHuffmanTable, ThreeLookupsHuffmanTable,
-                   HuffmanTableUnreachable>
+  mozilla::Variant<SingleEntryHuffmanTable, TwoEntriesHuffmanTable,
+                   SingleLookupHuffmanTable, TwoLookupsHuffmanTable,
+                   ThreeLookupsHuffmanTable, HuffmanTableUnreachable>
       implementation_;
 };
 
 // While reading the Huffman prelude, whenever we first encounter a
 // `HuffmanTableUnreachable`, we replace it with a `HuffmanTableInitializing`
 // to mark that we should not attempt to read/initialize it again.
 //
 // Attempting to get a value from this table is an internal error.