• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /**
2  * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef PANDA_VERIFIER_UTIL_TAGGED_INDEX_HPP_
17 #define PANDA_VERIFIER_UTIL_TAGGED_INDEX_HPP_
18 
19 #include "libpandabase/macros.h"
20 #include "libpandabase/utils/bit_utils.h"
21 
22 #include "verification/util/index.h"
23 #include "verification/util/hash.h"
24 
25 #include <limits>
26 #include <tuple>
27 #include <type_traits>
28 
29 #include <iostream>
30 
31 namespace ark::verifier {
32 
33 template <typename... Tag>
34 class TagPack {
35 public:
36     static constexpr size_t BITS = 0ULL;
37     static constexpr size_t QUANTITY = 0ULL;
38     static constexpr size_t TAG_SHIFT = 0ULL;
39     static constexpr size_t TAG_BITS = 0ULL;
40 
GetTagShift()41     static constexpr auto GetTagShift()
42     {
43         return std::tuple<> {};
44     }
GetTagBits()45     static constexpr auto GetTagBits()
46     {
47         return std::tuple<> {};
48     }
49     template <typename, size_t>
GetTagMask()50     static constexpr auto GetTagMask()
51     {
52         return std::tuple<> {};
53     }
GetTagHandler()54     static constexpr auto GetTagHandler()
55     {
56         return std::tuple<> {};
57     }
58     template <typename Int, const size_t SHIFT>
SetTags(Int & val)59     static constexpr void SetTags([[maybe_unused]] Int &val)
60     {
61     }
62 };
63 
64 template <typename T, typename... Tag>
65 class TagPack<T, Tag...> : private TagPack<Tag...> {
66     using Base = TagPack<Tag...>;
67 
68 public:
69     static constexpr size_t BITS = Base::BITS + T::BITS;
70     static constexpr size_t QUANTITY = Base::QUANTITY + 1ULL;
71     static constexpr size_t TAG_SHIFT = Base::BITS;
72     static constexpr size_t TAG_BITS = T::BITS;
73 
GetTagShift()74     static constexpr auto GetTagShift()
75     {
76         return std::tuple_cat(std::tuple<size_t> {TAG_SHIFT}, Base::GetTagShift());
77     }
GetTagBits()78     static constexpr auto GetTagBits()
79     {
80         return std::tuple_cat(std::tuple<size_t> {TAG_BITS}, Base::GetTagBits());
81     }
82     template <typename Int, const size_t SHIFT>
GetMask()83     static constexpr auto GetMask()
84     {
85         using UInt = std::make_unsigned_t<Int>;
86         UInt mask = ((static_cast<UInt>(1) << TAG_BITS) - static_cast<UInt>(1)) << TAG_SHIFT;
87         return mask << SHIFT;
88     }
89     template <typename Int, const size_t SHIFT>
GetTagMask()90     static constexpr auto GetTagMask()
91     {
92         using UInt = std::make_unsigned_t<Int>;
93         return std::tuple_cat(std::tuple<UInt> {GetMask<Int, SHIFT>()}, Base::template GetTagMask<Int, SHIFT>());
94     }
GetTagHandler()95     static constexpr auto GetTagHandler()
96     {
97         return std::tuple_cat(std::tuple<T> {}, Base::GetTagHandler());
98     }
99 
100     template <typename Int, const size_t SHIFT>
SetTags(const typename T::Type & tag,const typename Tag::Type &...tags,Int & val)101     static constexpr void SetTags(const typename T::Type &tag, const typename Tag::Type &...tags, Int &val)
102     {
103         using UInt = std::make_unsigned_t<Int>;
104         auto uintVal = static_cast<UInt>(val);
105         auto mask = GetMask<Int, SHIFT>();
106         uintVal &= ~mask;
107         auto tagVal = static_cast<UInt>(tag);
108         tagVal <<= TAG_SHIFT + SHIFT;
109         tagVal &= mask;
110         uintVal |= tagVal;
111         val = static_cast<Int>(uintVal);
112         Base::template SetTags<Int, SHIFT>(std::forward<const typename Tag::Type>(tags)..., val);
113     }
114 };
115 
116 template <typename...>
117 class TaggedIndexHelper0;
118 
119 template <typename... Tags, typename Int>
120 class TaggedIndexHelper0<Int, TagPack<Tags...>> {
121     using AllTags = TagPack<Tags...>;
122     using UInt = std::make_unsigned_t<Int>;
123     static constexpr size_t U_INT_BITS = sizeof(UInt) * 8ULL;
124     static constexpr size_t ALL_TAG_BITS = AllTags::BITS;
125     static constexpr size_t TAG_QUANTITY = AllTags::QUANTITY;
126     static constexpr size_t INT_BITS = U_INT_BITS - ALL_TAG_BITS - 1ULL;
127     static constexpr UInt ALL_TAG_MASK = ((static_cast<UInt>(1) << ALL_TAG_BITS) - static_cast<UInt>(1)) << INT_BITS;
128     static constexpr UInt VALIDITY_BIT = (static_cast<UInt>(1) << (U_INT_BITS - static_cast<size_t>(1)));
129     static constexpr UInt ALL_TAG_AND_VALIDITY_MASK = ALL_TAG_MASK & VALIDITY_BIT;
130     static constexpr UInt VALUE_MASK = (static_cast<UInt>(1) << INT_BITS) - static_cast<UInt>(1);
131     static constexpr size_t VALUE_SIGN_BIT = (static_cast<UInt>(1) << (INT_BITS - static_cast<size_t>(1)));
132     static constexpr UInt MAX_VALUE = VALUE_MASK;
133     static constexpr UInt INVALID = static_cast<UInt>(0);
134 
135     template <size_t TAGNUM>
TagShift()136     static constexpr size_t TagShift()
137     {
138         return INT_BITS + std::get<TAGNUM>(AllTags::GetTagShift());
139     }
140     template <size_t TAGNUM>
TagBits()141     static constexpr size_t TagBits()
142     {
143         return std::get<TAGNUM>(AllTags::GetTagBits());
144     }
145     template <size_t TAGNUM>
TagMask()146     static constexpr UInt TagMask()
147     {
148         return std::get<TAGNUM>(AllTags::template GetTagMask<UInt, INT_BITS>());
149     }
150     template <size_t TAGNUM>
151     using TagHandler = std::tuple_element_t<TAGNUM, decltype(AllTags::GetTagHandler())>;
152 
SetValid()153     void SetValid()
154     {
155         value_ |= VALIDITY_BIT;
156     }
157 
158 public:
159     TaggedIndexHelper0() = default;
TaggedIndexHelper0(typename Tags::Type...tags,Int idx)160     explicit TaggedIndexHelper0(typename Tags::Type... tags, Int idx)
161     {
162         AllTags::template SetTags<UInt, INT_BITS>(std::forward<typename Tags::Type>(tags)..., value_);
163         SetValid();
164         SetInt(idx);
165     }
SetInt(Int val)166     void SetInt(Int val)
167     {
168         ASSERT(IsValid());  // tag should be set before value
169         if constexpr (std::is_signed_v<Int>) {
170             if (val < 0) {
171                 ASSERT(static_cast<UInt>(-val) <= MAX_VALUE >> static_cast<UInt>(1));
172             } else {
173                 ASSERT(static_cast<UInt>(val) <= MAX_VALUE >> static_cast<UInt>(1));
174             }
175         } else {
176             ASSERT(static_cast<UInt>(val) <= MAX_VALUE);
177         }
178         value_ &= ~VALUE_MASK;
179         value_ |= (static_cast<UInt>(val) & VALUE_MASK);
180     }
181     TaggedIndexHelper0 &operator=(Int val)
182     {
183         SetInt(val);
184         return *this;
185     }
186     template <size_t N, typename Tag>
SetTag(Tag tag)187     void SetTag(Tag tag)
188     {
189         ASSERT(N < TAG_QUANTITY);
190         SetValid();
191         value_ &= ~TagMask<N>();
192         value_ |= static_cast<UInt>(TagHandler<N>::GetIndexFor(tag)) << TagShift<N>();
193     }
194     TaggedIndexHelper0(const TaggedIndexHelper0 &) = default;
TaggedIndexHelper0(TaggedIndexHelper0 && idx)195     TaggedIndexHelper0(TaggedIndexHelper0 &&idx) : value_ {idx.value_}
196     {
197         idx.Invalidate();
198     }
199     TaggedIndexHelper0 &operator=(const TaggedIndexHelper0 &) = default;
200     TaggedIndexHelper0 &operator=(TaggedIndexHelper0 &&idx)
201     {
202         value_ = idx.value_;
203         idx.Invalidate();
204         return *this;
205     }
206     ~TaggedIndexHelper0() = default;
Invalidate()207     void Invalidate()
208     {
209         value_ = INVALID;
210     }
IsValid()211     bool IsValid() const
212     {
213         return (value_ & VALIDITY_BIT) != 0;
214     }
215     template <size_t N>
GetTag()216     auto GetTag() const
217     {
218         ASSERT(IsValid());
219         return TagHandler<N>::GetValueFor((value_ & TagMask<N>()) >> TagShift<N>());
220     }
GetInt()221     Int GetInt() const
222     {
223         ASSERT(IsValid());
224         UInt val = value_ & VALUE_MASK;
225         Int ival;
226         if constexpr (std::is_signed_v<Int>) {
227             if (val & VALUE_SIGN_BIT) {
228                 val |= ALL_TAG_AND_VALIDITY_MASK;  // sign-extend
229                 ival = static_cast<Int>(val);
230             } else {
231                 ival = static_cast<Int>(val);
232             }
233         } else {
234             ival = static_cast<Int>(val);
235         }
236         return ival;
237     }
GetIndex()238     Index<Int> GetIndex() const
239     {
240         if (IsValid()) {
241             return GetInt();
242         }
243         return {};
244     }
245     // NOLINTNEXTLINE(google-explicit-constructor)
246     operator Index<Int>() const
247     {
248         return GetIndex();
249     }
250     template <const Int INV>
GetIndex()251     Index<Int, INV> GetIndex() const
252     {
253         ASSERT(static_cast<UInt>(INV) > MAX_VALUE);
254         if (IsValid()) {
255             return GetInt();
256         }
257         return {};
258     }
259     template <const Int INV>
260     // NOLINTNEXTLINE(google-explicit-constructor)
261     operator Index<Int, INV>() const
262     {
263         return GetIndex<INV>();
264     }
265     // NOLINTNEXTLINE(google-explicit-constructor)
Int()266     operator Int() const
267     {
268         ASSERT(IsValid());
269         return GetInt();
270     }
271     bool operator==(const TaggedIndexHelper0 rhs) const
272     {
273         ASSERT(IsValid());
274         ASSERT(rhs.IsValid());
275         return value_ == rhs.value_;
276     }
277     bool operator!=(const TaggedIndexHelper0 rhs) const
278     {
279         ASSERT(IsValid());
280         ASSERT(rhs.IsValid());
281         return value_ != rhs.value_;
282     }
283 
284 private:
285     UInt value_ {INVALID};
286     template <typename T>
287     friend struct std::hash;
288 };
289 
290 struct First;
291 struct Second;
292 
293 template <typename...>
294 class TaggedIndexSelectorH;
295 
296 template <typename Int, typename... Tags>
297 // NOLINTNEXTLINE(cppcoreguidelines-special-member-functions)
298 class TaggedIndexSelectorH<First, Int, std::tuple<Tags...>> : public TaggedIndexHelper0<Int, TagPack<Tags...>> {
299     using Base = TaggedIndexHelper0<Int, TagPack<Tags...>>;
300 
301 public:
302     TaggedIndexSelectorH() = default;
TaggedIndexSelectorH(typename Tags::Type...tags,Int & val)303     explicit TaggedIndexSelectorH(typename Tags::Type... tags, Int &val)
304         : Base {std::forward<typename Tags::Type>(tags)..., val}
305     {
306     }
307 
308     ~TaggedIndexSelectorH() = default;
309 };
310 
311 template <typename Int, typename... Tags>
312 // NOLINTNEXTLINE(cppcoreguidelines-special-member-functions)
313 class TaggedIndexSelectorH<Second, Int, std::tuple<Tags...>>
314     : public TaggedIndexHelper0<size_t, TagPack<Tags..., Int>> {
315     using Base = TaggedIndexHelper0<Int, TagPack<Tags..., Int>>;
316 
317 public:
318     TaggedIndexSelectorH() = default;
TaggedIndexSelectorH(typename Tags::Type...tags,size_t & val)319     explicit TaggedIndexSelectorH(typename Tags::Type... tags, size_t &val)
320         : Base {std::forward<typename Tags::Type>(tags)..., val}
321     {
322     }
323 
324     ~TaggedIndexSelectorH() = default;
325 };
326 
327 template <typename Int, typename... Tags>
328 // NOLINTNEXTLINE(cppcoreguidelines-special-member-functions)
329 class TaggedIndexSelector : public TaggedIndexSelectorH<std::conditional_t<std::is_integral_v<Int>, First, Second>, Int,
330                                                         std::tuple<Tags...>> {
331     using Base =
332         TaggedIndexSelectorH<std::conditional_t<std::is_integral_v<Int>, First, Second>, Int, std::tuple<Tags...>>;
333 
334 public:
335     TaggedIndexSelector() = default;
TaggedIndexSelector(typename Tags::Type...tags,Int & val)336     explicit TaggedIndexSelector(typename Tags::Type... tags, Int &val)
337         : Base {std::forward<typename Tags::Type>(tags)..., val}
338     {
339     }
340 
341     ~TaggedIndexSelector() = default;
342 };
343 
344 template <typename...>
345 class TaggedIndexHelper2;
346 
347 template <typename... Tags, typename Int>
348 class TaggedIndexHelper2<std::tuple<Tags...>, std::tuple<Int>> {
349 public:
350     using TagsInTuple = std::tuple<Tags...>;
351     using IntType = Int;
352 };
353 
354 template <typename... Ls, typename R, typename... Rs>
355 class TaggedIndexHelper2<std::tuple<Ls...>, std::tuple<R, Rs...>>
356     : public TaggedIndexHelper2<std::tuple<Ls..., R>, std::tuple<Rs...>> {
357 };
358 
359 template <typename... TagsAndInt>
360 // NOLINTNEXTLINE(cppcoreguidelines-special-member-functions)
361 class TaggedIndex
362     : public TaggedIndexSelectorH<
363           std::conditional_t<
364               std::is_integral_v<typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::IntType>, First,
365               Second>,
366           typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::IntType,
367           typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::TagsInTuple> {
368     using Base = TaggedIndexSelectorH<
369         std::conditional_t<
370             std::is_integral_v<typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::IntType>, First,
371             Second>,
372         typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::IntType,
373         typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::TagsInTuple>;
374 
375 public:
376     TaggedIndex() = default;
377     template <typename... Args>
TaggedIndex(Args &&...args)378     explicit TaggedIndex(Args &&...args) : Base {std::forward<Args>(args)...}
379     {
380     }
381 
382     ~TaggedIndex() = default;
383 };
384 
385 }  // namespace ark::verifier
386 
387 namespace std {
388 
389 template <typename... TagsAndInt>
390 struct hash<ark::verifier::TaggedIndex<TagsAndInt...>> {
391     size_t operator()(const ark::verifier::TaggedIndex<TagsAndInt...> &i) const noexcept
392     {
393         return ark::verifier::StdHash(i.value_);
394     }
395 };
396 
397 }  // namespace std
398 
399 #endif  // !PANDA_VERIFIER_UTIL_TAGGED_INDEX_HPP_
400