1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef DRM_HWCOMPOSER_SEPARATE_RECTS_H_
18 #define DRM_HWCOMPOSER_SEPARATE_RECTS_H_
19 
20 #include <stdint.h>
21 
22 #include <sstream>
23 #include <vector>
24 
25 namespace separate_rects {
26 
27 template <typename TFloat>
28 struct Rect {
29   union {
30     struct {
31       TFloat left, top, right, bottom;
32     };
33     struct {
34       TFloat x1, y1, x2, y2;
35     };
36     TFloat bounds[4];
37   };
38 
39   typedef TFloat TNum;
40 
RectRect41   Rect() {
42   }
43 
RectRect44   Rect(TFloat xx1, TFloat yy1, TFloat xx2, TFloat yy2)
45       : x1(xx1), y1(yy1), x2(xx2), y2(yy2) {
46   }
47 
48   template <typename T>
RectRect49   Rect(const Rect<T> &rhs) {
50     for (int i = 0; i < 4; i++)
51       bounds[i] = rhs.bounds[i];
52   }
53 
54   template <typename T>
55   Rect<TFloat> &operator=(const Rect<T> &rhs) {
56     for (int i = 0; i < 4; i++)
57       bounds[i] = rhs.bounds[i];
58     return *this;
59   }
60 
61   bool operator==(const Rect &rhs) const {
62     for (int i = 0; i < 4; i++) {
63       if (bounds[i] != rhs.bounds[i])
64         return false;
65     }
66 
67     return true;
68   }
69 
widthRect70   TFloat width() const {
71     return bounds[2] - bounds[0];
72   }
73 
heightRect74   TFloat height() const {
75     return bounds[3] - bounds[1];
76   }
77 
areaRect78   TFloat area() const {
79     return width() * height();
80   }
81 
DumpRect82   void Dump(std::ostringstream *out) const {
83     *out << "[x/y/w/h]=" << left << "/" << top << "/" << width() << "/"
84          << height();
85   }
86 };
87 
88 template <typename TUInt>
89 struct IdSet {
90  public:
91   typedef TUInt TId;
92 
IdSetIdSet93   IdSet() : bitset(0) {
94   }
95 
IdSetIdSet96   IdSet(TId id) : bitset(0) {
97     add(id);
98   }
99 
addIdSet100   void add(TId id) {
101     bitset |= ((TUInt)1) << id;
102   }
103 
subtractIdSet104   void subtract(TId id) {
105     bitset &= ~(((TUInt)1) << id);
106   }
107 
isEmptyIdSet108   bool isEmpty() const {
109     return bitset == 0;
110   }
111 
getBitsIdSet112   TUInt getBits() const {
113     return bitset;
114   }
115 
116   bool operator==(const IdSet<TId> &rhs) const {
117     return bitset == rhs.bitset;
118   }
119 
120   bool operator<(const IdSet<TId> &rhs) const {
121     return bitset < rhs.bitset;
122   }
123 
124   IdSet<TId> operator|(const IdSet<TId> &rhs) const {
125     IdSet ret;
126     ret.bitset = bitset | rhs.bitset;
127     return ret;
128   }
129 
130   IdSet<TId> operator|(TId id) const {
131     IdSet<TId> ret;
132     ret.bitset = bitset;
133     ret.add(id);
134     return ret;
135   }
136 
137   static const int max_elements = sizeof(TId) * 8;
138 
139  private:
140   TUInt bitset;
141 };
142 
143 template <typename TId, typename TNum>
144 struct RectSet {
145   IdSet<TId> id_set;
146   Rect<TNum> rect;
147 
RectSetRectSet148   RectSet(const IdSet<TId> &i, const Rect<TNum> &r) : id_set(i), rect(r) {
149   }
150 
151   bool operator==(const RectSet<TId, TNum> &rhs) const {
152     return id_set == rhs.id_set && rect == rhs.rect;
153   }
154 };
155 
156 // Separates up to a maximum of 64 input rectangles into mutually non-
157 // overlapping rectangles that cover the exact same area and outputs those non-
158 // overlapping rectangles. Each output rectangle also includes the set of input
159 // rectangle indices that overlap the output rectangle encoded in a bitset. For
160 // example, an output rectangle that overlaps input rectangles in[0], in[1], and
161 // in[4], the bitset would be (ommitting leading zeroes) 10011.
162 void separate_frects_64(const std::vector<Rect<float>> &in,
163                         std::vector<RectSet<uint64_t, float>> *out);
164 void separate_rects_64(const std::vector<Rect<int>> &in,
165                        std::vector<RectSet<uint64_t, int>> *out);
166 
167 }  // namespace separate_rects
168 
169 #endif
170