• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /**
2  * Copyright (c) 2021-2022 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 panda::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 TagShift = 0ULL;
39     static constexpr size_t TagBits = 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 TagShift = Base::Bits;
72     static constexpr size_t TagBits = T::Bits;
73 
GetTagShift()74     static constexpr auto GetTagShift()
75     {
76         return std::tuple_cat(std::tuple<size_t> {TagShift}, Base::GetTagShift());
77     }
GetTagBits()78     static constexpr auto GetTagBits()
79     {
80         return std::tuple_cat(std::tuple<size_t> {TagBits}, 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) << TagBits) - static_cast<UInt>(1)) << TagShift;
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 uint_val = static_cast<UInt>(val);
105         auto mask = GetMask<Int, Shift>();
106         uint_val &= ~mask;
107         auto tag_val = static_cast<UInt>(tag);
108         tag_val <<= TagShift + Shift;
109         tag_val &= mask;
110         uint_val |= tag_val;
111         val = static_cast<Int>(uint_val);
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 UIntBits = sizeof(UInt) * 8ULL;
124     static constexpr size_t AllTagBits = AllTags::Bits;
125     static constexpr size_t TagQuantity = AllTags::Quantity;
126     static constexpr size_t IntBits = UIntBits - AllTagBits - 1ULL;
127     static constexpr UInt ALL_TAG_MASK = ((static_cast<UInt>(1) << AllTagBits) - static_cast<UInt>(1)) << IntBits;
128     static constexpr UInt VALIDITY_BIT = (static_cast<UInt>(1) << (UIntBits - 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) << IntBits) - static_cast<UInt>(1);
131     static constexpr size_t VALUE_SIGN_BIT = (static_cast<UInt>(1) << (IntBits - 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 IntBits + 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, IntBits>());
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     TaggedIndexHelper0(typename Tags::type... tags, Int idx)
161     {
162         AllTags::template SetTags<UInt, IntBits>(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 < TagQuantity);
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     operator Index<Int>() const
246     {
247         return GetIndex();
248     }
249     template <const Int INV>
GetIndex()250     Index<Int, INV> GetIndex() const
251     {
252         ASSERT(static_cast<UInt>(INV) > MAX_VALUE);
253         if (IsValid()) {
254             return GetInt();
255         }
256         return {};
257     }
258     template <const Int INV>
259     operator Index<Int, INV>() const
260     {
261         return GetIndex<INV>();
262     }
Int()263     operator Int() const
264     {
265         ASSERT(IsValid());
266         return GetInt();
267     }
268     bool operator==(const TaggedIndexHelper0 rhs) const
269     {
270         ASSERT(IsValid());
271         ASSERT(rhs.IsValid());
272         return Value_ == rhs.Value_;
273     }
274     bool operator!=(const TaggedIndexHelper0 rhs) const
275     {
276         ASSERT(IsValid());
277         ASSERT(rhs.IsValid());
278         return Value_ != rhs.Value_;
279     }
280 
281 private:
282     UInt Value_ {INVALID};
283     template <typename T>
284     friend struct std::hash;
285 };
286 
287 struct First;
288 struct Second;
289 
290 template <typename...>
291 class TaggedIndexSelectorH;
292 
293 template <typename Int, typename... Tags>
294 class TaggedIndexSelectorH<First, Int, std::tuple<Tags...>> : public TaggedIndexHelper0<Int, TagPack<Tags...>> {
295     using Base = TaggedIndexHelper0<Int, TagPack<Tags...>>;
296 
297 public:
298     TaggedIndexSelectorH() = default;
TaggedIndexSelectorH(typename Tags::type...tags,Int & val)299     TaggedIndexSelectorH(typename Tags::type... tags, Int &val) : Base {std::forward<typename Tags::type>(tags)..., val}
300     {
301     }
302 
303     ~TaggedIndexSelectorH() = default;
304 };
305 
306 template <typename Int, typename... Tags>
307 class TaggedIndexSelectorH<Second, Int, std::tuple<Tags...>>
308     : public TaggedIndexHelper0<size_t, TagPack<Tags..., Int>> {
309     using Base = TaggedIndexHelper0<Int, TagPack<Tags..., Int>>;
310 
311 public:
312     TaggedIndexSelectorH() = default;
TaggedIndexSelectorH(typename Tags::type...tags,size_t & val)313     TaggedIndexSelectorH(typename Tags::type... tags, size_t &val)
314         : Base {std::forward<typename Tags::type>(tags)..., val}
315     {
316     }
317 
318     ~TaggedIndexSelectorH() = default;
319 };
320 
321 template <typename Int, typename... Tags>
322 class TaggedIndexSelector : public TaggedIndexSelectorH<std::conditional_t<std::is_integral_v<Int>, First, Second>, Int,
323                                                         std::tuple<Tags...>> {
324     using Base =
325         TaggedIndexSelectorH<std::conditional_t<std::is_integral_v<Int>, First, Second>, Int, std::tuple<Tags...>>;
326 
327 public:
328     TaggedIndexSelector() = default;
TaggedIndexSelector(typename Tags::type...tags,Int & val)329     TaggedIndexSelector(typename Tags::type... tags, Int &val) : Base {std::forward<typename Tags::type>(tags)..., val}
330     {
331     }
332 
333     ~TaggedIndexSelector() = default;
334 };
335 
336 template <typename...>
337 class TaggedIndexHelper2;
338 
339 template <typename... Tags, typename Int>
340 class TaggedIndexHelper2<std::tuple<Tags...>, std::tuple<Int>> {
341 public:
342     using TagsInTuple = std::tuple<Tags...>;
343     using IntType = Int;
344 };
345 
346 template <typename... Ls, typename R, typename... Rs>
347 class TaggedIndexHelper2<std::tuple<Ls...>, std::tuple<R, Rs...>>
348     : public TaggedIndexHelper2<std::tuple<Ls..., R>, std::tuple<Rs...>> {
349 };
350 
351 template <typename... TagsAndInt>
352 class TaggedIndex
353     : public TaggedIndexSelectorH<
354           std::conditional_t<
355               std::is_integral_v<typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::IntType>, First,
356               Second>,
357           typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::IntType,
358           typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::TagsInTuple> {
359     using Base = TaggedIndexSelectorH<
360         std::conditional_t<
361             std::is_integral_v<typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::IntType>, First,
362             Second>,
363         typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::IntType,
364         typename TaggedIndexHelper2<std::tuple<>, std::tuple<TagsAndInt...>>::TagsInTuple>;
365 
366 public:
367     TaggedIndex() = default;
368     template <typename... Args>
TaggedIndex(Args &&...args)369     TaggedIndex(Args &&... args) : Base {std::forward<Args>(args)...}
370     {
371     }
372 
373     ~TaggedIndex() = default;
374 };
375 
376 }  // namespace panda::verifier
377 
378 namespace std {
379 
380 template <typename... TagsAndInt>
381 struct hash<panda::verifier::TaggedIndex<TagsAndInt...>> {
382     size_t operator()(const panda::verifier::TaggedIndex<TagsAndInt...> &i) const noexcept
383     {
384         return panda::verifier::StdHash(i.Value_);
385     }
386 };
387 
388 }  // namespace std
389 
390 #endif  // !PANDA_VERIFIER_UTIL_TAGGED_INDEX_HPP_
391