1  /*
  2  * Copyright (C) 2019 Apple Inc. All rights reserved.
  3  *
  4  * Redistribution and use in source and binary forms, with or without
  5  * modification, are permitted provided that the following conditions
  6  * are met:
  7  * 1. Redistributions of source code must retain the above copyright
  8  *    notice, this list of conditions and the following disclaimer.
  9  * 2. Redistributions in binary form must reproduce the above copyright
 10  *    notice, this list of conditions and the following disclaimer in the
 11  *    documentation and/or other materials provided with the distribution.
 12  *
 13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 24  */
 25  
 26  #pragma once
 27  
 28  #include <wtf/HashTraits.h>
 29  #include <wtf/MathExtras.h>
 30  
 31  namespace WTF {
 32  class PrintStream;
 33  }
 34  
 35  namespace JSC {
 36  
 37  using Checkpoint = uint8_t;
 38  static constexpr Checkpoint noCheckpoints = 0;
 39  
 40  class BytecodeIndex {
 41  public:
 42      BytecodeIndex() = default;
 43      BytecodeIndex(WTF::HashTableDeletedValueType)
 44          : m_packedBits(deletedValue().asBits())
 45      {
 46      }
 47  
 48      explicit BytecodeIndex(uint32_t bytecodeOffset, Checkpoint checkpoint = noCheckpoints)
 49          : m_packedBits(pack(bytecodeOffset, checkpoint))
 50      {
 51          ASSERT(*this);
 52      }
 53  
 54      static constexpr uint32_t numberOfCheckpoints = 4;
 55      static_assert(hasOneBitSet(numberOfCheckpoints), "numberOfCheckpoints should be a power of 2");
 56      static constexpr uint32_t checkpointMask = numberOfCheckpoints - 1;
 57      static constexpr uint32_t checkpointShift = WTF::getMSBSetConstexpr(numberOfCheckpoints);
 58  
 59      uint32_t offset() const { return m_packedBits >> checkpointShift; }
 60      Checkpoint checkpoint() const { return m_packedBits & checkpointMask; }
 61      uint32_t asBits() const { return m_packedBits; }
 62  
 63      unsigned hash() const { return WTF::intHash(m_packedBits); }
 64      static BytecodeIndex deletedValue() { return fromBits(invalidOffset - 1); }
 65      bool isHashTableDeletedValue() const { return *this == deletedValue(); }
 66  
 67      static BytecodeIndex fromBits(uint32_t bits);
 68      BytecodeIndex withCheckpoint(Checkpoint checkpoint) const { return BytecodeIndex(offset(), checkpoint); }
 69  
 70      // Comparison operators.
 71      explicit operator bool() const { return m_packedBits != invalidOffset && m_packedBits != deletedValue().offset(); }
 72      bool operator ==(const BytecodeIndex& other) const { return asBits() == other.asBits(); }
 73      bool operator !=(const BytecodeIndex& other) const { return !(*this == other); }
 74  
 75      bool operator <(const BytecodeIndex& other) const { return asBits() < other.asBits(); }
 76      bool operator >(const BytecodeIndex& other) const { return asBits() > other.asBits(); }
 77      bool operator <=(const BytecodeIndex& other) const { return asBits() <= other.asBits(); }
 78      bool operator >=(const BytecodeIndex& other) const { return asBits() >= other.asBits(); }
 79  
 80  
 81      void dump(WTF::PrintStream&) const;
 82  
 83  private:
 84      static constexpr uint32_t invalidOffset = std::numeric_limits<uint32_t>::max();
 85  
 86      static uint32_t pack(uint32_t bytecodeIndex, Checkpoint);
 87  
 88      uint32_t m_packedBits { invalidOffset };
 89  };
 90  
 91  inline uint32_t BytecodeIndex::pack(uint32_t bytecodeIndex, Checkpoint checkpoint)
 92  {
 93      ASSERT(checkpoint < numberOfCheckpoints);
 94      ASSERT((bytecodeIndex << checkpointShift) >> checkpointShift == bytecodeIndex);
 95      return bytecodeIndex << checkpointShift | checkpoint;
 96  }
 97  
 98  inline BytecodeIndex BytecodeIndex::fromBits(uint32_t bits)
 99  {
100      BytecodeIndex result;
101      result.m_packedBits = bits;
102      return result;
103  }
104  
105  struct BytecodeIndexHash {
106      static unsigned hash(const BytecodeIndex& key) { return key.hash(); }
107      static bool equal(const BytecodeIndex& a, const BytecodeIndex& b) { return a == b; }
108      static constexpr bool safeToCompareToEmptyOrDeleted = true;
109  };
110  
111  } // namespace JSC
112  
113  namespace WTF {
114  
115  template<typename T> struct DefaultHash;
116  template<> struct DefaultHash<JSC::BytecodeIndex> : JSC::BytecodeIndexHash { };
117  
118  template<typename T> struct HashTraits;
119  template<> struct HashTraits<JSC::BytecodeIndex> : SimpleClassHashTraits<JSC::BytecodeIndex> {
120      static constexpr bool emptyValueIsZero = false;
121  };
122  
123  } // namespace WTF