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_SEPERATE_RECTS_H_
18#define DRM_HWCOMPOSER_SEPERATE_RECTS_H_
19
20#include <stdint.h>
21
22#include <sstream>
23#include <vector>
24
25namespace seperate_rects {
26
27template <typename TFloat>
28struct 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
41  Rect() {
42  }
43
44  Rect(TFloat xx1, TFloat yy1, TFloat xx2, TFloat yy2)
45      : x1(xx1), y1(yy1), x2(xx2), y2(yy2) {
46  }
47
48  template <typename T>
49  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
70  TFloat width() const {
71    return bounds[2] - bounds[0];
72  }
73
74  TFloat height() const {
75    return bounds[3] - bounds[1];
76  }
77
78  TFloat area() const {
79    return width() * height();
80  }
81
82  void Dump(std::ostringstream *out) const {
83    *out << "[x/y/w/h]=" << left << "/" << top << "/" << width() << "/"
84         << height();
85  }
86};
87
88template <typename TUInt>
89struct IdSet {
90 public:
91  typedef TUInt TId;
92
93  IdSet() : bitset(0) {
94  }
95
96  IdSet(TId id) : bitset(0) {
97    add(id);
98  }
99
100  void add(TId id) {
101    bitset |= ((TUInt)1) << id;
102  }
103
104  void subtract(TId id) {
105    bitset &= ~(((TUInt)1) << id);
106  }
107
108  bool isEmpty() const {
109    return bitset == 0;
110  }
111
112  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
143template <typename TId, typename TNum>
144struct RectSet {
145  IdSet<TId> id_set;
146  Rect<TNum> rect;
147
148  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// Seperates 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.
162void seperate_frects_64(const std::vector<Rect<float>> &in,
163                        std::vector<RectSet<uint64_t, float>> *out);
164void seperate_rects_64(const std::vector<Rect<int>> &in,
165                       std::vector<RectSet<uint64_t, int>> *out);
166
167}  // namespace seperate_rects
168
169#endif
170