1 //===-------------------- Bitcastbuffer.cpp ---------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 #include "BitcastBuffer.h" 9 #include "llvm/ADT/STLExtras.h" 10 11 using namespace clang; 12 using namespace clang::interp; 13 14 /// Returns the value of the bit in the given sequence of bytes. 15 static inline bool bitof(const std::byte *B, Bits BitIndex) { 16 return (B[BitIndex.roundToBytes()] & 17 (std::byte{1} << BitIndex.getOffsetInByte())) != std::byte{0}; 18 } 19 20 void BitcastBuffer::pushData(const std::byte *In, Bits BitOffset, Bits BitWidth, 21 Endian TargetEndianness) { 22 for (unsigned It = 0; It != BitWidth.getQuantity(); ++It) { 23 bool BitValue = bitof(In, Bits(It)); 24 if (!BitValue) 25 continue; 26 27 Bits DstBit; 28 if (TargetEndianness == Endian::Little) 29 DstBit = BitOffset + Bits(It); 30 else 31 DstBit = size() - BitOffset - BitWidth + Bits(It); 32 33 size_t DstByte = DstBit.roundToBytes(); 34 Data[DstByte] |= std::byte{1} << DstBit.getOffsetInByte(); 35 } 36 } 37 38 std::unique_ptr<std::byte[]> 39 BitcastBuffer::copyBits(Bits BitOffset, Bits BitWidth, Bits FullBitWidth, 40 Endian TargetEndianness) const { 41 assert(BitWidth.getQuantity() <= FullBitWidth.getQuantity()); 42 assert(FullBitWidth.isFullByte()); 43 auto Out = std::make_unique<std::byte[]>(FullBitWidth.roundToBytes()); 44 45 for (unsigned It = 0; It != BitWidth.getQuantity(); ++It) { 46 Bits BitIndex; 47 if (TargetEndianness == Endian::Little) 48 BitIndex = BitOffset + Bits(It); 49 else 50 BitIndex = size() - BitWidth - BitOffset + Bits(It); 51 52 bool BitValue = bitof(Data.get(), BitIndex); 53 if (!BitValue) 54 continue; 55 56 Bits DstBit = Bits(It); 57 size_t DstByte = DstBit.roundToBytes(); 58 Out[DstByte] |= std::byte{1} << DstBit.getOffsetInByte(); 59 } 60 61 return Out; 62 } 63 64 bool BitcastBuffer::allInitialized() const { 65 return rangeInitialized(Bits::zero(), FinalBitSize); 66 } 67 68 void BitcastBuffer::markInitialized(Bits Offset, Bits Length) { 69 if (Length.isZero()) 70 return; 71 72 BitRange Element(Offset, Offset + Length - Bits(1)); 73 if (InitializedBits.empty()) { 74 InitializedBits.push_back(Element); 75 return; 76 } 77 78 assert(InitializedBits.size() >= 1); 79 // Common case of just appending. 80 Bits End = InitializedBits.back().End; 81 if (End <= Offset) { 82 // Merge this range with the last one. 83 // In the best-case scenario, this means we only ever have 84 // one single bit range covering all bits. 85 if (End == (Offset - Bits(1))) { 86 InitializedBits.back().End = Element.End; 87 return; 88 } 89 90 // Otherwise, we can simply append. 91 InitializedBits.push_back(Element); 92 } else { 93 // Insert sorted. 94 auto It = llvm::upper_bound(InitializedBits, Element); 95 InitializedBits.insert(It, Element); 96 } 97 98 #ifndef NDEBUG 99 // Ensure ranges are sorted and non-overlapping. 100 assert(llvm::is_sorted(InitializedBits)); 101 for (unsigned I = 1; I != InitializedBits.size(); ++I) { 102 [[maybe_unused]] auto Prev = InitializedBits[I - 1]; 103 [[maybe_unused]] auto Cur = InitializedBits[I]; 104 assert(Prev.End.N < Cur.Start.N); 105 } 106 #endif 107 } 108 109 bool BitcastBuffer::rangeInitialized(Bits Offset, Bits Length) const { 110 if (Length.isZero()) 111 return true; 112 113 BitRange Range(Offset, Offset + Length - Bits(1)); 114 Bits Sum; 115 bool FoundStart = false; 116 for (BitRange BR : InitializedBits) { 117 if (FoundStart) { 118 if (BR.contains(Range.End)) { 119 Sum += (Range.End - BR.Start + Bits(1)); 120 break; 121 } 122 123 // Else, BR is completely inside Range. 124 Sum += BR.size(); 125 } 126 if (BR.contains(Range.Start)) { 127 Sum += (BR.End - Range.Start + Bits(1)); 128 FoundStart = true; 129 } 130 } 131 132 // Note that Sum can be larger than Range, e.g. when Range is fully 133 // contained in one range. 134 return Sum >= Range.size(); 135 } 136 137 #if 0 138 template<typename T> 139 static std::string hex(T t) { 140 std::stringstream stream; 141 stream << std::hex << (int)t; 142 return std::string(stream.str()); 143 } 144 145 146 void BitcastBuffer::dump(bool AsHex = true) const { 147 llvm::errs() << "LSB\n "; 148 unsigned LineLength = 0; 149 for (unsigned I = 0; I != (FinalBitSize / 8); ++I) { 150 std::byte B = Data[I]; 151 if (AsHex) { 152 std::stringstream stream; 153 stream << std::hex << (int)B; 154 llvm::errs() << stream.str(); 155 LineLength += stream.str().size() + 1; 156 } else { 157 llvm::errs() << std::bitset<8>((int)B).to_string(); 158 LineLength += 8 + 1; 159 // llvm::errs() << (int)B; 160 } 161 llvm::errs() << ' '; 162 } 163 llvm::errs() << '\n'; 164 165 for (unsigned I = 0; I != LineLength; ++I) 166 llvm::errs() << ' '; 167 llvm::errs() << "MSB\n"; 168 } 169 #endif 170