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
11using namespace clang;
12using namespace clang::interp;
13
14/// Returns the value of the bit in the given sequence of bytes.
15static 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
20void 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(B: In, BitIndex: 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
38std::unique_ptr<std::byte[]>
39BitcastBuffer::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[]>(num: 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(B: 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
64bool BitcastBuffer::allInitialized() const {
65 return rangeInitialized(Offset: Bits::zero(), Length: FinalBitSize);
66}
67
68void 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(Elt: 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(Elt: Element);
92 } else {
93 // Insert sorted.
94 auto It = llvm::upper_bound(Range&: InitializedBits, Value&: Element);
95 InitializedBits.insert(I: It, Elt: 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
109bool 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(B: 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(B: 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