115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner/* 215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * Copyright (C) 2015 The Android Open Source Project 315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * 415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * Licensed under the Apache License, Version 2.0 (the "License"); 515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * you may not use this file except in compliance with the License. 615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * You may obtain a copy of the License at 715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * 815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * http://www.apache.org/licenses/LICENSE-2.0 915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * 1015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * Unless required by applicable law or agreed to in writing, software 1115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * distributed under the License is distributed on an "AS IS" BASIS, 1215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * See the License for the specific language governing permissions and 1415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner * limitations under the License. 1515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner */ 1615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 1715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner#ifndef DRM_HWCOMPOSER_SEPERATE_RECTS_H_ 1815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner#define DRM_HWCOMPOSER_SEPERATE_RECTS_H_ 1915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 2015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner#include <stdint.h> 21fd6dc339551e5aa041daec7abffc3ff8eaeca138Zach Reizner 22fd6dc339551e5aa041daec7abffc3ff8eaeca138Zach Reizner#include <sstream> 2315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner#include <vector> 2415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 2515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reiznernamespace seperate_rects { 2615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 2715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reiznertemplate <typename TFloat> 2815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reiznerstruct Rect { 2915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner union { 3015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner struct { 3115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner TFloat left, top, right, bottom; 3215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner }; 3315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner struct { 3415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner TFloat x1, y1, x2, y2; 3515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner }; 3615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner TFloat bounds[4]; 3715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner }; 3815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 3915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner typedef TFloat TNum; 4015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 4115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner Rect() { 4215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 4315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 4415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner Rect(TFloat xx1, TFloat yy1, TFloat xx2, TFloat yy2) 4515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner : x1(xx1), y1(yy1), x2(xx2), y2(yy2) { 4615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 4715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 484a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner template <typename T> 494a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner Rect(const Rect<T> &rhs) { 5015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner for (int i = 0; i < 4; i++) 5115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner bounds[i] = rhs.bounds[i]; 5215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 5315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 544a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner template <typename T> 554a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner Rect<TFloat> &operator=(const Rect<T> &rhs) { 564a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner for (int i = 0; i < 4; i++) 574a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner bounds[i] = rhs.bounds[i]; 584a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner return *this; 594a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner } 604a253659cef3d82bfb0b25b3ff4c7b073d7a0460Zach Reizner 6115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner bool operator==(const Rect &rhs) const { 6215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner for (int i = 0; i < 4; i++) { 6315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner if (bounds[i] != rhs.bounds[i]) 6415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return false; 6515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 6615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 6715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return true; 6815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 69a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner 70a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner TFloat width() const { 71a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner return bounds[2] - bounds[0]; 72a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner } 73a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner 74a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner TFloat height() const { 75a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner return bounds[3] - bounds[1]; 76a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner } 77a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner 78a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner TFloat area() const { 79a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner return width() * height(); 80a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner } 81fd6dc339551e5aa041daec7abffc3ff8eaeca138Zach Reizner 82fd6dc339551e5aa041daec7abffc3ff8eaeca138Zach Reizner void Dump(std::ostringstream *out) const { 83fd6dc339551e5aa041daec7abffc3ff8eaeca138Zach Reizner *out << "[x/y/w/h]=" << left << "/" << top << "/" << width() << "/" 84fd6dc339551e5aa041daec7abffc3ff8eaeca138Zach Reizner << height(); 85fd6dc339551e5aa041daec7abffc3ff8eaeca138Zach Reizner } 8615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner}; 8715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 8815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reiznertemplate <typename TUInt> 8915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reiznerstruct IdSet { 9015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner public: 9115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner typedef TUInt TId; 9215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 9315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner IdSet() : bitset(0) { 9415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 9515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 9615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner IdSet(TId id) : bitset(0) { 9715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner add(id); 9815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 9915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 10015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner void add(TId id) { 10115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner bitset |= ((TUInt)1) << id; 10215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 10315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 10415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner void subtract(TId id) { 10515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner bitset &= ~(((TUInt)1) << id); 10615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 10715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 10815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner bool isEmpty() const { 10915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return bitset == 0; 11015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 11115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 11215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner TUInt getBits() const { 11315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return bitset; 11415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 11515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 11615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner bool operator==(const IdSet<TId> &rhs) const { 11715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return bitset == rhs.bitset; 11815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 11915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 12015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner bool operator<(const IdSet<TId> &rhs) const { 12115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return bitset < rhs.bitset; 12215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 12315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 12415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner IdSet<TId> operator|(const IdSet<TId> &rhs) const { 12515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner IdSet ret; 12615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner ret.bitset = bitset | rhs.bitset; 12715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return ret; 12815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 12915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 13015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner IdSet<TId> operator|(TId id) const { 13115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner IdSet<TId> ret; 13215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner ret.bitset = bitset; 13315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner ret.add(id); 13415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return ret; 13515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 13615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 13715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner static const int max_elements = sizeof(TId) * 8; 13815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 13915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner private: 14015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner TUInt bitset; 14115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner}; 14215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 14315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reiznertemplate <typename TId, typename TNum> 14415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reiznerstruct RectSet { 14515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner IdSet<TId> id_set; 14615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner Rect<TNum> rect; 14715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 14815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner RectSet(const IdSet<TId> &i, const Rect<TNum> &r) : id_set(i), rect(r) { 14915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 15015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 15115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner bool operator==(const RectSet<TId, TNum> &rhs) const { 15215c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner return id_set == rhs.id_set && rect == rhs.rect; 15315c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner } 15415c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner}; 15515c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 15615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner// Seperates up to a maximum of 64 input rectangles into mutually non- 15715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner// overlapping rectangles that cover the exact same area and outputs those non- 15815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner// overlapping rectangles. Each output rectangle also includes the set of input 15915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner// rectangle indices that overlap the output rectangle encoded in a bitset. For 16015c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner// example, an output rectangle that overlaps input rectangles in[0], in[1], and 16115c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner// in[4], the bitset would be (ommitting leading zeroes) 10011. 162a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reiznervoid seperate_frects_64(const std::vector<Rect<float>> &in, 163a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner std::vector<RectSet<uint64_t, float>> *out); 164a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reiznervoid seperate_rects_64(const std::vector<Rect<int>> &in, 165a281f8fce9fd2c6b9b1e539ffed18b71586a7bc5Zach Reizner std::vector<RectSet<uint64_t, int>> *out); 16615c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 16715c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner} // namespace seperate_rects 16815c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner 16915c9ffa2a0d662a3400a5d31a94faf7517a1d815Zach Reizner#endif 170