1 /*
2  *
3  * Copyright 2019, The Android Open Source Project
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  *     http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 #ifndef TEEUI_LIBTEEUI_UTILS_H_
19 #define TEEUI_LIBTEEUI_UTILS_H_
20 
21 #include <math.h>
22 #include <stddef.h>
23 #include <stdint.h>
24 #include <sys/types.h>
25 
26 #include <algorithm>
27 #include <initializer_list>
28 #include <optional>
29 #include <tuple>
30 #include <type_traits>
31 
32 #include <teeui/error.h>
33 #include <teeui/log.h>
34 
35 namespace teeui {
36 
37 using std::optional;
38 
39 template <typename T, size_t elements> class Array {
40     using array_type = T[elements];
41 
42   public:
Array()43     constexpr Array() : data_{} {}
Array(const T (& data)[elements])44     constexpr Array(const T (&data)[elements]) { std::copy(data, data + elements, data_); }
Array(const std::initializer_list<uint8_t> & li)45     constexpr Array(const std::initializer_list<uint8_t>& li) {
46         size_t i = 0;
47         for (auto& item : li) {
48             data_[i] = item;
49             ++i;
50             if (i == elements) break;
51         }
52         for (; i < elements; ++i) {
53             data_[i] = {};
54         }
55     }
56 
data()57     T* data() { return data_; }
data()58     const T* data() const { return data_; }
size()59     constexpr size_t size() const { return elements; }
60 
begin()61     T* begin() { return data_; }
end()62     T* end() { return data_ + elements; }
begin()63     const T* begin() const { return data_; }
end()64     const T* end() const { return data_ + elements; }
65 
fill(const T & v)66     static constexpr Array fill(const T& v) {
67         Array result;
68         for (size_t i = 0; i < elements; ++i) {
69             result.data_[i] = v;
70         }
71         return result;
72     }
73 
74   private:
75     array_type data_;
76 };
77 
78 template <typename T> auto bytesCast(const T& v) -> const uint8_t (&)[sizeof(T)] {
79     return *reinterpret_cast<const uint8_t(*)[sizeof(T)]>(&v);
80 }
81 template <typename T> auto bytesCast(T& v) -> uint8_t (&)[sizeof(T)] {
82     return *reinterpret_cast<uint8_t(*)[sizeof(T)]>(&v);
83 }
84 
85 class ByteBufferProxy {
86     template <typename T> struct has_data {
fhas_data87         template <typename U> static int f(const U*, const void*) { return 0; }
88         template <typename U> static int* f(const U* u, decltype(u->data())) { return nullptr; }
89         static constexpr bool value = std::is_pointer<decltype(f((T*)nullptr, ""))>::value;
90     };
91 
92   public:
93     template <typename T>
94     ByteBufferProxy(const T& buffer, decltype(buffer.data()) = nullptr)
95         : data_(reinterpret_cast<const uint8_t*>(buffer.data())), size_(buffer.size()) {
96         static_assert(sizeof(decltype(*buffer.data())) == 1, "elements to large");
97     }
98 
99     template <size_t size>
ByteBufferProxy(const char (& buffer)[size])100     ByteBufferProxy(const char (&buffer)[size])
101         : data_(reinterpret_cast<const uint8_t*>(buffer)), size_(size - 1) {
102         static_assert(size > 0, "even an empty string must be 0-terminated");
103     }
104 
105     template <size_t size>
ByteBufferProxy(const uint8_t (& buffer)[size])106     ByteBufferProxy(const uint8_t (&buffer)[size]) : data_(buffer), size_(size) {}
107 
ByteBufferProxy()108     ByteBufferProxy() : data_(nullptr), size_(0) {}
109 
data()110     const uint8_t* data() const { return data_; }
size()111     size_t size() const { return size_; }
112 
begin()113     const uint8_t* begin() const { return data_; }
end()114     const uint8_t* end() const { return data_ + size_; }
115 
116   private:
117     const uint8_t* data_;
118     size_t size_;
119 };
120 
121 constexpr const uint8_t kAuthTokenKeySize = 32;
122 constexpr const uint8_t kHmacKeySize = kAuthTokenKeySize;
123 using AuthTokenKey = Array<uint8_t, kAuthTokenKeySize>;
124 using Hmac = AuthTokenKey;
125 
126 /**
127  * Implementer are expected to provide an implementation with the following prototype:
128  *  static optional<array<uint8_t, 32>> hmac256(const uint8_t key[32],
129  *                                     std::initializer_list<ByteBufferProxy> buffers);
130  */
131 template <typename Impl> class HMac {
132   public:
133     template <typename... Data>
hmac256(const AuthTokenKey & key,const Data &...data)134     static optional<Hmac> hmac256(const AuthTokenKey& key, const Data&... data) {
135         return Impl::hmac256(key, {data...});
136     }
137 };
138 
139 bool operator==(const ByteBufferProxy& lhs, const ByteBufferProxy& rhs);
140 
141 template <typename IntType, uint32_t byteOrder> struct choose_hton;
142 
143 template <typename IntType> struct choose_hton<IntType, __ORDER_LITTLE_ENDIAN__> {
144     inline static IntType hton(const IntType& value) {
145         IntType result = {};
146         const unsigned char* inbytes = reinterpret_cast<const unsigned char*>(&value);
147         unsigned char* outbytes = reinterpret_cast<unsigned char*>(&result);
148         for (int i = sizeof(IntType) - 1; i >= 0; --i) {
149             *(outbytes++) = inbytes[i];
150         }
151         return result;
152     }
153 };
154 
155 template <typename IntType> struct choose_hton<IntType, __ORDER_BIG_ENDIAN__> {
156     inline static IntType hton(const IntType& value) { return value; }
157 };
158 
159 template <typename IntType> inline IntType hton(const IntType& value) {
160     return choose_hton<IntType, __BYTE_ORDER__>::hton(value);
161 }
162 
163 template <typename IntType> inline IntType ntoh(const IntType& value) {
164     // same operation as hton
165     return choose_hton<IntType, __BYTE_ORDER__>::hton(value);
166 }
167 
168 enum class Unit : uint8_t {
169     PX,
170     DP,
171     MM,
172 };
173 
174 template <Unit unit> struct UnitT { constexpr static const Unit value = unit; };
175 
176 using px = UnitT<Unit::PX>;
177 using dp = UnitT<Unit::DP>;
178 using mm = UnitT<Unit::MM>;
179 
180 template <typename Unit> static constexpr const char* str = "N/A";
181 
182 template <> static constexpr const char* str<px> = "px";
183 template <> static constexpr const char* str<dp> = "dp";
184 template <> static constexpr const char* str<mm> = "mm";
185 
186 using DefaultNumericType = float;
187 
188 namespace bits {
189 
190 inline long double abs(long double v) {
191     return ::fabsl(v);
192 }
193 inline double abs(double v) {
194     return ::fabs(v);
195 }
196 
197 inline long double ceil(long double v) {
198     return ::ceill(v);
199 }
200 
201 inline double ceil(double v) {
202     return ::ceil(v);
203 }
204 
205 inline long double floor(long double v) {
206     return ::floorl(v);
207 }
208 
209 inline double floor(double v) {
210     return ::floor(v);
211 }
212 
213 inline long double sqrt(long double v) {
214     return ::sqrtl(v);
215 }
216 
217 inline double sqrt(double v) {
218     return ::sqrt(v);
219 }
220 
221 inline float round(float v) {
222     return ::roundf(v);
223 }
224 
225 inline long double round(long double v) {
226     return ::roundl(v);
227 }
228 
229 inline double round(double v) {
230     return ::round(v);
231 }
232 
233 }  // namespace bits
234 
235 template <typename Unit, typename Numeric = DefaultNumericType> class Coordinate;
236 
237 template <typename Numeric> struct Add {
238     constexpr static Coordinate<px, Numeric> eval(const Coordinate<px, Numeric>& v1,
239                                                   const Coordinate<px, Numeric>& v2) {
240         return v1 + v2;
241     }
242 };
243 template <typename Numeric> struct Sub {
244     constexpr static Coordinate<px, Numeric> eval(const Coordinate<px, Numeric>& v1,
245                                                   const Coordinate<px, Numeric>& v2) {
246         return v1 - v2;
247     }
248 };
249 template <typename Numeric> struct Mul {
250     constexpr static Coordinate<px, Numeric> eval(const Coordinate<px, Numeric>& v1,
251                                                   const Coordinate<px, Numeric>& v2) {
252         return v1 * v2;
253     }
254 };
255 template <typename Numeric> struct Div {
256     constexpr static Coordinate<px, Numeric> eval(const Coordinate<px, Numeric>& v1,
257                                                   const Coordinate<px, Numeric>& v2) {
258         return v1 / v2;
259     }
260 };
261 
262 template <typename T1, typename T2, typename Numeric, template <typename> class Op> struct BinOp;
263 
264 template <typename T1, typename T2, typename Numeric> using add = BinOp<T1, T2, Numeric, Add>;
265 template <typename T1, typename T2, typename Numeric> using sub = BinOp<T1, T2, Numeric, Sub>;
266 template <typename T1, typename T2, typename Numeric> using mul = BinOp<T1, T2, Numeric, Mul>;
267 template <typename T1, typename T2, typename Numeric> using div = BinOp<T1, T2, Numeric, Div>;
268 
269 template <typename T1, typename T2, typename Numeric, template <typename> class Op> struct BinOp {
270   private:
271     T1 v1_;
272     T2 v2_;
273 
274   public:
275     constexpr BinOp(const T1& v1, const T2& v2) : v1_(v1), v2_(v2) {}
276     BinOp(const BinOp&) = default;
277     BinOp(BinOp&&) = default;
278 
279     template <typename Context> Coordinate<px, Numeric> eval(const Context& ctx) const {
280         Coordinate<px, Numeric> v1 = ctx = v1_;
281         Coordinate<px, Numeric> v2 = ctx = v2_;
282         return Op<Numeric>::eval(v1, v2);
283     }
284     template <typename T> constexpr add<BinOp, T, Numeric> operator+(const T& v) const {
285         return {*this, v};
286     }
287     template <typename T> constexpr sub<BinOp, T, Numeric> operator-(const T& v) const {
288         return {*this, v};
289     }
290     template <typename T> constexpr mul<BinOp, T, Numeric> operator*(const T& v) const {
291         return {*this, v};
292     }
293     template <typename T> constexpr div<BinOp, T, Numeric> operator/(const T& v) const {
294         return {*this, v};
295     }
296 };
297 
298 template <typename Name, typename ParamType> struct MetaParam {};
299 
300 template <typename Name, typename Unit, typename Numeric>
301 struct MetaParam<Name, Coordinate<Unit, Numeric>> {
302     template <typename T> constexpr add<MetaParam, T, Numeric> operator+(const T& v) const {
303         return {*this, v};
304     }
305     template <typename T> constexpr sub<MetaParam, T, Numeric> operator-(const T& v) const {
306         return {*this, v};
307     }
308     template <typename T> constexpr mul<MetaParam, T, Numeric> operator*(const T& v) const {
309         return {*this, v};
310     }
311     template <typename T> constexpr div<MetaParam, T, Numeric> operator/(const T& v) const {
312         return {*this, v};
313     }
314 };
315 
316 template <typename Name, typename ParamType> class Param {
317   private:
318     ParamType param_;
319 
320   public:
321     Param() : param_{} {}
322     Param(const Param&) = default;
323     Param(Param&&) = default;
324     Param& operator=(const Param&) = default;
325     Param& operator=(Param&&) = default;
326     inline const ParamType& operator*() const { return param_; }
327     inline ParamType& operator*() { return param_; }
328     inline const ParamType* operator->() const { return &param_; }
329     inline ParamType* operator->() { return &param_; }
330 };
331 
332 template <typename Unit, typename Numeric> class Coordinate {
333     Numeric value_;
334 
335   public:
336     using unit_t = Unit;
337     constexpr Coordinate() : value_{} {}
338     constexpr Coordinate(Numeric value) : value_(value) {}
339     Coordinate(const Coordinate&) = default;
340     Coordinate(Coordinate&&) = default;
341     template <typename N> Coordinate(const Coordinate<Unit, N>& other) {
342         if constexpr (std::is_floating_point<N>::value && std::is_integral<Numeric>::value) {
343             value_ = bits::round(other.count());
344         } else {
345             value_ = other.count();
346         }
347     }
348     Coordinate& operator=(const Coordinate& rhs) = default;
349     Coordinate& operator=(Coordinate&& rhs) = default;
350 
351     constexpr Coordinate operator-(const Coordinate& v) const { return value_ - v.value_; }
352     constexpr Coordinate operator+(const Coordinate& v) const { return value_ + v.value_; }
353     constexpr Coordinate& operator-=(const Coordinate& v) {
354         value_ -= v.value_;
355         return *this;
356     }
357     constexpr Coordinate& operator+=(const Coordinate& v) {
358         value_ += v.value_;
359         return *this;
360     }
361     constexpr Coordinate operator*(const Coordinate& v) const { return value_ * v.value_; }
362     constexpr Coordinate& operator*=(const Coordinate& v) {
363         value_ *= v.value_;
364         return *this;
365     }
366     constexpr Coordinate operator/(const Coordinate& v) const { return value_ / v.value_; }
367     constexpr Coordinate& operator/=(const Coordinate& v) {
368         value_ /= v.value_;
369         return *this;
370     }
371     constexpr Coordinate operator-() const { return -value_; }
372 
373     Coordinate abs() const { return bits::abs(value_); }
374     Coordinate ceil() const { return bits::ceil(value_); }
375     Coordinate floor() const { return bits::floor(value_); }
376     Coordinate sqrt() const { return bits::sqrt(value_); }
377 
378     constexpr bool operator==(const Coordinate& v) const { return value_ == v.value_; }
379     constexpr bool operator!=(const Coordinate& v) const { return !(*this == v); }
380     constexpr bool operator<(const Coordinate& v) const { return value_ < v.value_; }
381     constexpr bool operator>(const Coordinate& v) const { return v < *this; }
382     constexpr bool operator<=(const Coordinate& v) const { return !(v < *this); }
383     constexpr bool operator>=(const Coordinate& v) const { return !(*this < v); }
384 
385     template <typename T> constexpr add<Coordinate, T, Numeric> operator+(const T& v) const {
386         return {*this, v};
387     }
388     template <typename T> constexpr sub<Coordinate, T, Numeric> operator-(const T& v) const {
389         return {*this, v};
390     }
391     template <typename T> constexpr mul<Coordinate, T, Numeric> operator*(const T& v) const {
392         return {*this, v};
393     }
394     template <typename T> constexpr div<Coordinate, T, Numeric> operator/(const T& v) const {
395         return {*this, v};
396     }
397 
398     Numeric count() const { return value_; }
399 };
400 
401 template <typename... T> struct MetaList {};
402 
403 template <typename MetaParam> struct metaParam2Param;
404 
405 template <typename ParamName, typename ParamType>
406 struct metaParam2Param<MetaParam<ParamName, ParamType>> {
407     using type = Param<ParamName, ParamType>;
408 };
409 
410 template <typename MetaParam> struct metaParam2ParamType;
411 
412 template <typename ParamName, typename ParamType>
413 struct metaParam2ParamType<MetaParam<ParamName, ParamType>> {
414     using type = ParamType;
415 };
416 
417 template <typename T> struct isCoordinateType { constexpr static const bool value = false; };
418 
419 template <typename Unit, typename Numeric> struct isCoordinateType<Coordinate<Unit, Numeric>> {
420     constexpr static const bool value = true;
421 };
422 
423 template <typename MetaParam> struct isCoordinateParam;
424 
425 template <typename ParamName, typename ParamType>
426 struct isCoordinateParam<MetaParam<ParamName, ParamType>> {
427     constexpr static const bool value = isCoordinateType<ParamType>::value;
428 };
429 
430 template <typename T> struct isMetaParam { constexpr static const bool value = false; };
431 
432 template <typename ParamName, typename ParamType>
433 struct isMetaParam<MetaParam<ParamName, ParamType>> {
434     constexpr static const bool value = true;
435 };
436 
437 template <typename Param, typename Numeric = DefaultNumericType> class context;
438 
439 template <typename... ParamsNames, typename... ParamTypes, typename Numeric>
440 class context<MetaList<MetaParam<ParamsNames, ParamTypes>...>, Numeric> {
441     Numeric mm2px_;
442     Numeric dp2px_;
443     std::tuple<Param<ParamsNames, ParamTypes>...> params_;
444 
445     class Proxy {
446         Numeric valuepx_;
447         Numeric mm2px_, dp2px_;
448 
449       public:
450         Proxy(Numeric valuepx, Numeric mm2px, Numeric dp2px)
451             : valuepx_(valuepx), mm2px_(mm2px), dp2px_(dp2px) {}
452         Proxy(const Proxy&) = default;
453         Proxy(Proxy&&) = default;
454 
455         operator Coordinate<px, Numeric>() const { return valuepx_; }
456         operator Coordinate<mm, Numeric>() const { return valuepx_ / mm2px_; }
457         operator Coordinate<dp, Numeric>() const { return valuepx_ / dp2px_; }
458     };
459 
460   public:
461     context(Numeric mm2px, Numeric dp2px) : mm2px_(mm2px), dp2px_(dp2px) {}
462 
463     context(const context&) = default;
464     context(context&&) = default;
465     context& operator=(const context&) = default;
466     context& operator=(context&&) = default;
467 
468     template <typename MetaParam> auto& getParam() {
469         return std::get<typename metaParam2Param<MetaParam>::type>(params_);
470     }
471     template <typename MetaParam> const auto& getParam() const {
472         return std::get<typename metaParam2Param<MetaParam>::type>(params_);
473     }
474 
475     template <typename MetaParam, typename = std::enable_if_t<isCoordinateParam<MetaParam>::value>>
476     void setParam(const Coordinate<px, Numeric>& v) {
477         *getParam<MetaParam>() = v;
478     }
479 
480     template <typename MetaParam, typename Unit, typename N,
481               typename = std::enable_if_t<isCoordinateParam<MetaParam>::value>>
482     void setParam(const Coordinate<Unit, N>& v) {
483         *getParam<MetaParam>() = *this = v;
484     }
485 
486     template <typename MetaParam>
487     void setParam(std::enable_if_t<!isCoordinateParam<MetaParam>::value,
488                                    const typename metaParam2ParamType<MetaParam>::type>& v) {
489         *getParam<MetaParam>() = v;
490     }
491 
492     Proxy operator=(const Coordinate<px, Numeric>& rhs) const {
493         return {rhs.count(), mm2px_, dp2px_};
494     }
495     Proxy operator=(const Coordinate<mm, Numeric>& rhs) const {
496         return {rhs.count() * mm2px_, mm2px_, dp2px_};
497     }
498     Proxy operator=(const Coordinate<dp, Numeric>& rhs) const {
499         return {rhs.count() * dp2px_, mm2px_, dp2px_};
500     }
501     template <typename T1, typename T2, template <typename> class Op>
502     Proxy operator=(const BinOp<T1, T2, Numeric, Op>& rhs) const {
503         return {rhs.eval(*this).count(), mm2px_, dp2px_};
504     }
505     template <typename ParamName, typename ParamType>
506     std::enable_if_t<isCoordinateParam<MetaParam<ParamName, ParamType>>::value, Proxy>
507     operator=(const MetaParam<ParamName, ParamType>&) const {
508         return {getParam<MetaParam<ParamName, ParamType>>()->count(), mm2px_, dp2px_};
509     }
510     template <typename ParamName, typename ParamType>
511     std::enable_if_t<!isCoordinateParam<MetaParam<ParamName, ParamType>>::value, const ParamType&>
512     operator=(const MetaParam<ParamName, ParamType>&) const {
513         return *getParam<MetaParam<ParamName, ParamType>>();
514     }
515     template <typename T,
516               typename = std::enable_if_t<!(isMetaParam<T>::value || isCoordinateType<T>::value)>>
517     inline T&& operator=(T&& v) const {
518         return std::forward<T>(v);
519     }
520 };
521 
522 using dps = Coordinate<dp>;
523 using mms = Coordinate<mm>;
524 using pxs = Coordinate<px>;
525 
526 constexpr dps operator""_dp(long double dp) {
527     return dps(dp);
528 }
529 constexpr mms operator""_mm(long double mm) {
530     return mms(mm);
531 }
532 constexpr pxs operator""_px(long double px) {
533     return pxs(px);
534 }
535 constexpr dps operator""_dp(unsigned long long dp) {
536     return dps(dp);
537 }
538 constexpr mms operator""_mm(unsigned long long mm) {
539     return mms(mm);
540 }
541 constexpr pxs operator""_px(unsigned long long px) {
542     return pxs(px);
543 }
544 
545 template <typename Coord> class Vec2d {
546     Coord x_, y_;
547 
548   public:
549     constexpr Vec2d() : x_{}, y_{} {}
550     constexpr Vec2d(Coord x, Coord y) : x_(x), y_(y) {}
551     Vec2d(const Vec2d&) = default;
552     Vec2d(Vec2d&&) = default;
553     template <typename N>
554     Vec2d(const Vec2d<Coordinate<typename Coord::unit_t, N>>& other)
555         : x_(other.x()), y_(other.y()) {}
556 
557     Vec2d& operator=(const Vec2d& rhs) = default;
558     Vec2d& operator=(Vec2d&& rhs) = default;
559 
560     Vec2d operator-(const Vec2d& rhs) const { return Vec2d(*this) -= rhs; }
561     Vec2d operator+(const Vec2d& rhs) const { return Vec2d(*this) += rhs; }
562     Vec2d& operator-=(const Vec2d& rhs) {
563         x_ -= rhs.x_;
564         y_ -= rhs.y_;
565         return *this;
566     }
567     Vec2d& operator+=(const Vec2d& rhs) {
568         x_ += rhs.x_;
569         y_ += rhs.y_;
570         return *this;
571     }
572     Coord operator*(const Vec2d& rhs) const { return (x_ * rhs.x_ + y_ * rhs.y_).count(); }
573     Vec2d operator*(const Coord& f) const { return Vec2d(*this) *= f; }
574     Vec2d& operator*=(const Coord& f) {
575         x_ *= f;
576         y_ *= f;
577         return *this;
578     }
579     Vec2d operator/(const Coord& f) { return Vec2d(*this) /= f; }
580     Vec2d& operator/=(const Coord& f) {
581         x_ /= f;
582         y_ /= f;
583         return *this;
584     }
585     bool operator==(const Vec2d& rhs) const { return x_ == rhs.x() && y_ == rhs.y(); }
586     Coord length() const {
587         Coord factor = *this * *this;
588         return bits::sqrt(factor.count());
589     }
590     Vec2d unit() const { return Vec2d(*this) /= length(); }
591     Coord x() const { return x_; }
592     Coord y() const { return y_; }
593 };
594 
595 #ifdef TEEUI_DO_LOG_DEBUG
596 template <typename Unit, typename Numeric>
597 std::ostream& operator<<(std::ostream& out, const Coordinate<Unit, Numeric>& p) {
598     out << std::setprecision(10) << p.count() << str<Unit>;
599     return out;
600 }
601 
602 template <typename Coord> std::ostream& operator<<(std::ostream& out, const Vec2d<Coord>& p) {
603     out << "Vec2d(" << p.x() << ", " << p.y() << ")";
604     return out;
605 }
606 #endif
607 
608 using Color = uint32_t;
609 
610 template <typename Coord> using Point = Vec2d<Coord>;
611 
612 Color drawLinePoint(Point<pxs> a, Point<pxs> b, Point<pxs> px_origin, Color c,
613                     pxs width = pxs(1.0));
614 
615 Color drawCirclePoint(Point<pxs> center, pxs r, Point<pxs> px_origin, Color c);
616 
617 using PxPoint = Point<pxs>;
618 using PxVec = Vec2d<pxs>;
619 
620 /*
621  * Computes the intersection of the lines given by ax + b and cy + d.
622  * The result may be empty if there is no solution.
623  */
624 optional<PxPoint> intersect(const PxVec& a, const PxPoint& b, const PxVec& c, const PxPoint& d);
625 
626 namespace bits {
627 
628 static constexpr const ssize_t kIntersectEmpty = -1;
629 /**
630  * Returned by the intersect if the object is in the positive half plane of the given line.
631  */
632 static constexpr const ssize_t kIntersectAllPositive = -2;
633 
634 ssize_t intersect(const PxPoint* oBegin, const PxPoint* oEnd, const PxPoint& lineA,
635                   const PxPoint& lineB, PxPoint* nBegin, PxPoint* nEnd);
636 
637 pxs area(const PxPoint* begin, const PxPoint* end);
638 
639 }  // namespace bits
640 
641 /**
642  * A ConvexObject is given by a list of 2D vertexes. Each vertex must lie on the positive half-plane
643  * of the line denoted by its two predecessors. A point is considered inside of the convex object
644  * if it is on the positive half-plane of all lines given by any two subsequent vertexes.
645  *
646  * ConvexObjects have fixed size given by the capacity template argument. The geometric object
647  * that they describe may have any number of vertexes between 3 and capacity.
648  */
649 template <size_t capacity> class ConvexObject {
650     template <size_t other_cap> friend class ConvexObject;
651 
652   protected:
653     PxPoint points_[capacity];
654     size_t fill_;
655 
656   public:
657     ConvexObject() : fill_(0) {}
658     explicit constexpr ConvexObject(std::initializer_list<PxPoint> l) : fill_(0) {
659         if (l.size() > capacity) return;
660         for (const auto& p : l) {
661             points_[fill_++] = p;
662         }
663     }
664     ConvexObject(const ConvexObject& other) = default;
665     ConvexObject(ConvexObject&& other) = default;
666     ConvexObject& operator=(const ConvexObject& other) = default;
667     ConvexObject& operator=(ConvexObject&& other) = default;
668 
669     constexpr size_t size() const { return fill_; }
670 
671     constexpr const PxPoint* begin() const { return &points_[0]; }
672     constexpr const PxPoint* end() const { return &points_[fill_]; }
673 
674     template <size_t result_cap>
675     optional<ConvexObject<result_cap>> intersect(const PxPoint& A, const PxPoint& B) const {
676         static_assert(result_cap >= capacity,
677                       "resulting capacity must be at least as large as the original");
678         ConvexObject<result_cap> result;
679         ssize_t vCount =
680             bits::intersect(begin(), end(), A, B, &result.points_[0], &result.points_[result_cap]);
681         if (vCount == bits::kIntersectEmpty) return {};
682         // -2 is returned if the object is in the positive half plane of the line (may be tangent)
683         if (vCount == bits::kIntersectAllPositive) {
684             std::copy(begin(), end(), &result.points_[0]);
685             vCount = fill_;
686         }
687         result.fill_ = vCount;
688         return result;
689     }
690 
691     template <size_t result_cap, size_t arg_cap>
692     optional<ConvexObject<result_cap>> intersect(const ConvexObject<arg_cap>& other) const {
693         return intersect<result_cap>(other.begin(), other.end());
694     }
695 
696     template <size_t result_cap>
697     optional<ConvexObject<result_cap>> intersect(const PxPoint* begin, const PxPoint* end) const {
698         if (end - begin < 3) return {};
699         auto b = begin;
700         auto a = end - 1;
701         auto result = intersect<result_cap>(*a, *b);
702         a = b++;
703         while (result && b != end) {
704             result = result->template intersect<result_cap>(*a, *b);
705             a = b++;
706         }
707         return result;
708     }
709 
710     pxs area() const { return bits::area(begin(), end()); }
711 
712     void push_back(const PxPoint& p) {
713         if (fill_ < capacity) {
714             points_[fill_++] = p;
715         }
716     }
717 };
718 
719 #ifdef TEEUI_DO_LOG_DEBUG
720 template <size_t capacity>
721 std::ostream& operator<<(std::ostream& out, const ConvexObject<capacity>& o) {
722     out << "ConvexObject(";
723     bool first = true;
724     for (const auto& p : o) {
725         if (first)
726             first = false;
727         else
728             out << ", ";
729         out << p;
730     }
731     out << ")";
732     return out;
733 }
734 #endif
735 
736 template <typename Coord> class Box {
737     Point<Coord> topLeft_;
738     Vec2d<Coord> extend_;
739 
740   public:
741     Box() {}
742     template <typename N>
743     Box(const Box<Coordinate<typename Coord::unit_t, N>>& other)
744         : topLeft_(other.topLeft()), extend_(other.extend()) {}
745     Box(const Coord& x, const Coord& y, const Coord& w, const Coord& h)
746         : topLeft_(x, y), extend_(w, h) {}
747     Box(const Point<Coord>& topLeft, const Vec2d<Coord>& extend)
748         : topLeft_(topLeft), extend_(extend) {}
749     bool contains(Point<Coord> p) const {
750         p -= topLeft_;
751         return p.y().count() >= 0 && p.y().count() <= extend_.y().count() && p.x().count() >= 0 &&
752                p.x().count() <= extend_.x().count();
753     }
754     bool contains(const Box& other) const {
755         auto br = bottomRight();
756         auto obr = other.bottomRight();
757         return topLeft_.x() <= other.topLeft_.x() && br.x() >= obr.x() &&
758                topLeft_.y() <= other.topLeft_.y() && br.y() >= obr.y();
759     }
760     bool overlaps(const Box& other) const {
761         auto br = bottomRight();
762         auto obr = other.bottomRight();
763         return topLeft_.x() < obr.x() && other.topLeft_.x() < br.x() && topLeft_.y() < obr.y() &&
764                other.topLeft_.y() < obr.y();
765     }
766 
767     /**
768      * fitsInside only compares the extend of the boxes. It returns true if this box would fit
769      * inside the other box regardless of their absolute positions.
770      */
771     bool fitsInside(const Box& other) const { return w() <= other.w() && h() <= other.w(); }
772     Point<Coord> bottomRight() const { return topLeft_ + extend_; }
773     Point<Coord> topLeft() const { return topLeft_; }
774     Vec2d<Coord> extend() const { return extend_; }
775     Coord x() const { return topLeft_.x(); }
776     Coord y() const { return topLeft_.y(); }
777     Coord w() const { return extend_.x(); }
778     Coord h() const { return extend_.y(); }
779 
780     Box merge(const Box& other) const {
781         Coord x = std::min(topLeft_.x(), other.topLeft_.x());
782         Coord y = std::min(topLeft_.y(), other.topLeft_.y());
783         auto br = bottomRight();
784         auto obr = other.bottomRight();
785         Coord w = std::max(br.x(), obr.x()) - x;
786         Coord h = std::max(br.y(), obr.y()) - y;
787         return {x, y, w, h};
788     }
789 
790     /**
791      * Returns a box that contains the this box and the given point.
792      */
793     Box merge(const Point<Coord>& p) const {
794         auto br = bottomRight();
795         TEEUI_LOG << "A tl: " << topLeft_ << " br: " << br << " new: " << p << ENDL;
796         Coord x = std::min(topLeft_.x(), p.x());
797         Coord y = std::min(topLeft_.y(), p.y());
798         Coord w = std::max(br.x(), p.x()) - x;
799         Coord h = std::max(br.y(), p.y()) - y;
800         TEEUI_LOG << "B x: " << x << " y: " << y << " w: " << w << " h: " << h << ENDL;
801         return {x, y, w, h};
802     }
803 
804     /**
805      * Returns a box that contains this box and all of the given points.
806      */
807     Box merge(const Point<Coord>* begin, const Point<Coord>* end) const {
808         auto tl = topLeft();
809         auto br = bottomRight();
810         while (begin != end) {
811             TEEUI_LOG << "A tl: " << tl << " br: " << br << " new: " << *begin << ENDL;
812             tl = {std::min(tl.x(), begin->x()), std::min(tl.y(), begin->y())};
813             br = {std::max(br.x(), begin->x()), std::max(br.y(), begin->y())};
814             TEEUI_LOG << "B tl: " << tl << " br: " << br << " new: " << *begin << ENDL;
815             ++begin;
816         }
817         return {tl, br - tl};
818     }
819 
820     /**
821      * Creates a box that contains all of the given points.
822      */
823     static Box boundingBox(const Point<Coord>* begin, const Point<Coord>* end) {
824         if (begin == end) return {};
825         Box result(*begin, {0, 0});
826         result.merge(begin + 1, end);
827         return result;
828     }
829 
830     /*
831      * Translates the Box by the given offset. And returns a reference to itself
832      */
833     Box& translateSelf(const Point<Coord>& offset) {
834         topLeft_ += offset;
835         return *this;
836     }
837     /*
838      * Returns copy of this box translated by offset.
839      */
840     Box translate(const Point<Coord>& offset) const& {
841         Box result = *this;
842         result.topLeft_ += offset;
843         return result;
844     }
845     /*
846      * When called on a temporary just reuse this box.
847      */
848     Box translate(const Point<Coord>& offset) && {
849         topLeft_ += offset;
850         return *this;
851     }
852 };
853 
854 #ifdef TEEUI_DO_LOG_DEBUG
855 template <typename Coord> std::ostream& operator<<(std::ostream& out, const Box<Coord>& p) {
856     out << "Box(x: " << p.x().count() << " y: " << p.y().count() << " w: " << p.w().count()
857         << " h: " << p.h().count() << ")";
858     return out;
859 }
860 #endif
861 
862 enum class EventType : uint8_t {
863     KeyDown,
864     KeyUp,
865     KeyMoved,
866 };
867 
868 struct Event {
869     uint32_t x_;
870     uint32_t y_;
871     EventType event_;
872 };
873 
874 template <typename Fn> struct Callback;
875 
876 template <typename Ret, typename... Args> struct Callback<Ret(Args...)> {
877     Ret (*callback_)(Args... args, void* priv_data);
878     void* priv_data_;
879     Ret operator()(Args... args) const { return callback_(args..., priv_data_); }
880 };
881 
882 template <typename Ret, typename... Args>
883 Callback<Ret(Args...)> makeCallback(Ret (*fn)(Args..., void*), void* priv_data) {
884     return {fn, priv_data};
885 }
886 
887 template <typename Fn, typename Ret, typename... Args> struct CallbackHelper {
888     Fn fn_;
889     operator Callback<Ret(Args...)>() {
890         return makeCallback<Ret, Args...>(
891             [](Args... args, void* priv_data) -> Ret {
892                 return reinterpret_cast<CallbackHelper*>(priv_data)->fn_(args...);
893             },
894             this);
895     }
896 };
897 
898 using CallbackEvent = Callback<Error(Event)>;
899 using PixelDrawer = Callback<Error(uint32_t, uint32_t, Color)>;
900 
901 template <typename Fn>
902 using PixelDrawerHelper = CallbackHelper<Fn, Error, uint32_t, uint32_t, Color>;
903 
904 template <typename Fn> PixelDrawerHelper<Fn> makePixelDrawer(Fn fn) {
905     return PixelDrawerHelper<Fn>{fn};
906 }
907 
908 template <typename Derived> struct LayoutElement {
909     Box<pxs> bounds_;
910     LayoutElement() = default;
911     template <typename Context>
912     LayoutElement(const Context& context)
913         : bounds_{context = Derived::pos_x, context = Derived::pos_y, context = Derived::dim_w,
914                   context = Derived::dim_h} {}
915 
916     Error draw(const PixelDrawer&) { return Error::OK; }
917     Error hit(const Event&) { return Error::OK; }
918 };
919 
920 template <typename... Elements, typename Context>
921 std::tuple<Elements...> instantiateLayout(MetaList<Elements...>, const Context& context) {
922     std::tuple<Elements...> result{Elements(context)...};
923     return result;
924 }
925 
926 template <typename T> struct MetaList2Layout;
927 
928 template <typename... Elements> struct MetaList2Layout<MetaList<Elements...>> {
929     using type = std::tuple<Elements...>;
930 };
931 
932 template <typename T> using layout_t = typename MetaList2Layout<T>::type;
933 
934 template <typename... Coords>
935 constexpr inline std::tuple<Vec2d<Coords>...> makeConvexObject(const Vec2d<Coords>&... points) {
936     return {points...};
937 }
938 
939 template <size_t capacity, typename Tuple, typename Context, size_t... I>
940 constexpr inline ConvexObject<capacity>
941 initConvexObject(const Context& context, const Tuple& outline, std::index_sequence<I...>) {
942     return ConvexObject<capacity>(
943         {PxVec(context = std::get<I>(outline).x(), context = std::get<I>(outline).y())...});
944 }
945 
946 template <size_t capacity, typename... Points, typename Context>
947 constexpr inline ConvexObject<capacity> initConvexObject(const Context& context,
948                                                          const std::tuple<Points...>& outline) {
949     return initConvexObject<capacity>(context, outline, std::index_sequence_for<Points...>{});
950 }
951 
952 template <size_t capacity, typename Tuple, typename Context, size_t... I, size_t size>
953 constexpr inline void initConvexObjectArray(const Context& context,
954                                             ConvexObject<capacity> (&out)[size], const Tuple& t,
955                                             std::index_sequence<I...>) {
956     static_assert(sizeof...(I) <= size,
957                   "Array to initialize must be big enough to hold all tuple elements");
958     [](auto...) {}((out[I] = initConvexObject<capacity>(context, std::get<I>(t)))...);
959 }
960 
961 template <size_t capacity, typename... COs, typename Context, size_t size>
962 constexpr inline void initConvexObjectArray(const Context& context,
963                                             ConvexObject<capacity> (&out)[size],
964                                             const std::tuple<COs...>& t) {
965     initConvexObjectArray(context, out, t, std::index_sequence_for<COs...>());
966 }
967 
968 template <typename Iterator> class Range {
969     Iterator begin_;
970     Iterator end_;
971 
972   public:
973     Range(Iterator begin, Iterator end) : begin_(begin), end_(end) {}
974     const Iterator begin() const { return begin_; }
975     const Iterator end() const { return end_; }
976 };
977 
978 template <typename Iterator> Range<Iterator> makeRange(Iterator begin, Iterator end) {
979     return {begin, end};
980 }
981 
982 }  // namespace teeui
983 
984 #define Position(x, y)                                                                             \
985     static const constexpr auto pos_x = x;                                                         \
986     static const constexpr auto pos_y = y
987 
988 #define Dimension(w, h)                                                                            \
989     static const constexpr auto dim_w = w;                                                         \
990     static const constexpr auto dim_h = h
991 
992 #define BEGIN_ELEMENT(name, type, ...)                                                             \
993     struct name : public type<name, ##__VA_ARGS__> {                                               \
994         name() = default;                                                                          \
995         template <typename Context>                                                                \
996         name(const Context& context) : type<name, ##__VA_ARGS__>(context) {}
997 
998 #define END_ELEMENT() }
999 
1000 #define DECLARE_TYPED_PARAMETER(name, type)                                                        \
1001     struct Param_##name {};                                                                        \
1002     using name = ::teeui::MetaParam<Param_##name, type>
1003 
1004 #define DECLARE_PARAMETER(name) DECLARE_TYPED_PARAMETER(name, ::teeui::pxs)
1005 
1006 #define CONSTANT(name, value) static constexpr const auto name = value
1007 
1008 #define BOTTOM_EDGE_OF(name) (name::pos_y + name::dim_h)
1009 
1010 #define CONVEX_OBJECT(...) makeConvexObject(__VA_ARGS__)
1011 
1012 #define CONVEX_OBJECTS(...) std::make_tuple(__VA_ARGS__)
1013 
1014 /**
1015  * Creates a new Layout with the name "name" followed by a list of Layout elements as defined with
1016  * BEGIN_ELEMENT(name).
1017  */
1018 #define NEW_LAYOUT(name, ...) using name = ::teeui::MetaList<__VA_ARGS__>
1019 
1020 #define NEW_PARAMETER_SET(name, ...) using name = ::teeui::MetaList<__VA_ARGS__>
1021 
1022 #define LABELS(name, ...) using ::teeui::MetaList<__VA_ARGS__>
1023 
1024 #define TEXT_ID(textId) static_cast<uint32_t>(textId)
1025 #endif  // TEEUI_LIBTEEUI_UTILS_H_
1026