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 = std::upper_bound(InitializedBits.begin(), InitializedBits.end(), 95 Element); 96 InitializedBits.insert(It, Element); 97 } 98 99 #ifndef NDEBUG 100 // Ensure ranges are sorted and non-overlapping. 101 assert(llvm::is_sorted(InitializedBits)); 102 for (unsigned I = 1; I != InitializedBits.size(); ++I) { 103 [[maybe_unused]] auto Prev = InitializedBits[I - 1]; 104 [[maybe_unused]] auto Cur = InitializedBits[I]; 105 assert(Prev.End.N < Cur.Start.N); 106 } 107 #endif 108 } 109 110 bool BitcastBuffer::rangeInitialized(Bits Offset, Bits Length) const { 111 if (Length.isZero()) 112 return true; 113 114 BitRange Range(Offset, Offset + Length - Bits(1)); 115 Bits Sum; 116 bool FoundStart = false; 117 for (BitRange BR : InitializedBits) { 118 if (FoundStart) { 119 if (BR.contains(Range.End)) { 120 Sum += (Range.End - BR.Start + Bits(1)); 121 break; 122 } 123 124 // Else, BR is completely inside Range. 125 Sum += BR.size(); 126 } 127 if (BR.contains(Range.Start)) { 128 Sum += (BR.End - Range.Start + Bits(1)); 129 FoundStart = true; 130 } 131 } 132 133 // Note that Sum can be larger than Range, e.g. when Range is fully 134 // contained in one range. 135 return Sum >= Range.size(); 136 } 137 138 #if 0 139 template<typename T> 140 static std::string hex(T t) { 141 std::stringstream stream; 142 stream << std::hex << (int)t; 143 return std::string(stream.str()); 144 } 145 146 147 void BitcastBuffer::dump(bool AsHex = true) const { 148 llvm::errs() << "LSB\n "; 149 unsigned LineLength = 0; 150 for (unsigned I = 0; I != (FinalBitSize / 8); ++I) { 151 std::byte B = Data[I]; 152 if (AsHex) { 153 std::stringstream stream; 154 stream << std::hex << (int)B; 155 llvm::errs() << stream.str(); 156 LineLength += stream.str().size() + 1; 157 } else { 158 llvm::errs() << std::bitset<8>((int)B).to_string(); 159 LineLength += 8 + 1; 160 // llvm::errs() << (int)B; 161 } 162 llvm::errs() << ' '; 163 } 164 llvm::errs() << '\n'; 165 166 for (unsigned I = 0; I != LineLength; ++I) 167 llvm::errs() << ' '; 168 llvm::errs() << "MSB\n"; 169 } 170 #endif 171