Line data Source code
1 : /**
2 : Copyright (c) 2024 Stappler LLC <admin@stappler.dev>
3 :
4 : Permission is hereby granted, free of charge, to any person obtaining a copy
5 : of this software and associated documentation files (the "Software"), to deal
6 : in the Software without restriction, including without limitation the rights
7 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 : copies of the Software, and to permit persons to whom the Software is
9 : furnished to do so, subject to the following conditions:
10 :
11 : The above copyright notice and this permission notice shall be included in
12 : all copies or substantial portions of the Software.
13 :
14 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 : THE SOFTWARE.
21 : **/
22 :
23 : #include "SPFontEmplace.h"
24 : #include "SPGeometry.h"
25 :
26 : namespace STAPPLER_VERSIONIZED stappler::font {
27 :
28 : namespace {
29 :
30 : constexpr uint32_t LAYOUT_PADDING = 1;
31 :
32 : struct LayoutNodeMemory;
33 :
34 : struct LayoutNodeMemoryStorage {
35 : const EmplaceCharInterface *interface = nullptr;
36 : LayoutNodeMemory *free = nullptr;
37 : memory::pool_t *pool = nullptr;
38 :
39 : LayoutNodeMemoryStorage(const EmplaceCharInterface *, memory::pool_t *);
40 :
41 : LayoutNodeMemory *alloc(const geom::URect &rect);
42 : LayoutNodeMemory *alloc(const geom::UVec2 &origin, void *c);
43 : void release(LayoutNodeMemory *node);
44 : };
45 :
46 : struct LayoutNodeMemory : memory::AllocPool {
47 : LayoutNodeMemory* _child[2];
48 : geom::URect _rc;
49 : void * _char = nullptr;
50 :
51 : LayoutNodeMemory(const geom::URect &rect);
52 : LayoutNodeMemory(const LayoutNodeMemoryStorage &, const geom::UVec2 &origin, void *c);
53 :
54 : bool insert(LayoutNodeMemoryStorage &, void *c);
55 : size_t nodes() const;
56 : void finalize(LayoutNodeMemoryStorage &, uint8_t tex);
57 : };
58 :
59 1268 : LayoutNodeMemoryStorage::LayoutNodeMemoryStorage(const EmplaceCharInterface *i, memory::pool_t *p)
60 1268 : : interface(i), pool(p) { }
61 :
62 454550 : LayoutNodeMemory *LayoutNodeMemoryStorage::alloc(const geom::URect &rect) {
63 454550 : if (free) {
64 168 : auto node = free;
65 168 : free = node->_child[0];
66 168 : return new (node) LayoutNodeMemory(rect);
67 : }
68 454382 : return new (pool) LayoutNodeMemory(rect);
69 : }
70 :
71 208814 : LayoutNodeMemory *LayoutNodeMemoryStorage::alloc(const geom::UVec2 &origin, void *c) {
72 208814 : if (free) {
73 0 : auto node = free;
74 0 : free = node->_child[0];
75 0 : return new (node) LayoutNodeMemory(*this, origin, c);
76 : }
77 208814 : return new (pool) LayoutNodeMemory(*this, origin, c);
78 : }
79 :
80 606134 : void LayoutNodeMemoryStorage::release(LayoutNodeMemory *node) {
81 606134 : node->_child[0] = nullptr;
82 606134 : node->_child[1] = nullptr;
83 606134 : node->_rc = geom::URect({0, 0, 0, 0});
84 606134 : node->_char = nullptr;
85 606134 : if (free) {
86 604698 : node->_child[0] = free;
87 : }
88 606134 : free = node;
89 606134 : }
90 :
91 454550 : LayoutNodeMemory::LayoutNodeMemory(const geom::URect &rect) {
92 454550 : _rc = rect;
93 454550 : _child[0] = nullptr;
94 454550 : _child[1] = nullptr;
95 454550 : }
96 :
97 208814 : LayoutNodeMemory::LayoutNodeMemory(const LayoutNodeMemoryStorage &storage, const geom::UVec2 &origin, void *c) {
98 208814 : _child[0] = nullptr;
99 208814 : _child[1] = nullptr;
100 208814 : _char = c;
101 208814 : _rc = geom::URect{origin.x, origin.y, storage.interface->getWidth(c), storage.interface->getHeight(c)};
102 208814 : }
103 :
104 41162368 : bool LayoutNodeMemory::insert(LayoutNodeMemoryStorage &storage, void *c) {
105 41162368 : if (_child[0] && _child[1]) {
106 20540712 : return _child[0]->insert(storage, c) || _child[1]->insert(storage, c);
107 : } else {
108 20621656 : if (_char) {
109 12400217 : return false;
110 : }
111 :
112 8221439 : const auto iwidth = storage.interface->getWidth(c);
113 8221439 : const auto iheight = storage.interface->getHeight(c);
114 :
115 8221439 : if (_rc.width < iwidth || _rc.height < iheight) {
116 7890475 : return false;
117 : }
118 :
119 330964 : if (_rc.width == iwidth || _rc.height == iheight) {
120 208814 : if (_rc.height == iheight) {
121 126963 : _child[0] = storage.alloc(_rc.origin(), c); // new (pool) LayoutNode(_rc.origin(), c);
122 126963 : _child[1] = storage.alloc(geom::URect{uint32_t(_rc.x + iwidth + LAYOUT_PADDING), _rc.y,
123 126963 : (_rc.width > iwidth + LAYOUT_PADDING)?uint32_t(_rc.width - iwidth - LAYOUT_PADDING):uint32_t(0), _rc.height});
124 81851 : } else if (_rc.width == iwidth) {
125 81851 : _child[0] = storage.alloc(_rc.origin(), c); // new (pool) LayoutNode(_rc.origin(), c);
126 81851 : _child[1] = storage.alloc(geom::URect{_rc.x, uint32_t(_rc.y + iheight + LAYOUT_PADDING),
127 81851 : _rc.width, (_rc.height > iheight + LAYOUT_PADDING)?uint32_t(_rc.height - iheight - LAYOUT_PADDING):uint32_t(0)});
128 : }
129 208814 : return true;
130 : }
131 :
132 : //(decide which way to split)
133 122150 : int16_t dw = _rc.width - iwidth;
134 122150 : int16_t dh = _rc.height - iheight;
135 :
136 122150 : if (dw > dh) {
137 46097 : _child[0] = storage.alloc(geom::URect{_rc.x, _rc.y, iwidth, _rc.height});
138 46097 : _child[1] = storage.alloc(geom::URect{uint32_t(_rc.x + iwidth + LAYOUT_PADDING), _rc.y, uint32_t(dw - LAYOUT_PADDING), _rc.height});
139 : } else {
140 76053 : _child[0] = storage.alloc(geom::URect{_rc.x, _rc.y, _rc.width, iheight});
141 76053 : _child[1] = storage.alloc(geom::URect{_rc.x, uint32_t(_rc.y + iheight + LAYOUT_PADDING), _rc.width, uint32_t(dh - LAYOUT_PADDING)});
142 : }
143 :
144 122150 : _child[0]->insert(storage, c);
145 :
146 122150 : return true;
147 : }
148 : }
149 :
150 663364 : size_t LayoutNodeMemory::nodes() const {
151 663364 : if (_char) {
152 208814 : return 1;
153 454550 : } else if (_child[0] && _child[1]) {
154 330964 : return _child[0]->nodes() + _child[1]->nodes();
155 : } else {
156 123586 : return 0;
157 : }
158 : }
159 :
160 604698 : void LayoutNodeMemory::finalize(LayoutNodeMemoryStorage &storage, uint8_t tex) {
161 604698 : if (_char) {
162 190510 : storage.interface->setX(_char, _rc.x);
163 190510 : storage.interface->setY(_char, _rc.y);
164 190510 : storage.interface->setTex(_char, tex);
165 : } else {
166 414188 : if (_child[0]) { _child[0]->finalize(storage, tex); }
167 414188 : if (_child[1]) { _child[1]->finalize(storage, tex); }
168 : }
169 604698 : storage.release(this);
170 604698 : }
171 :
172 : } // unnamed
173 :
174 1268 : geom::Extent2 emplaceChars(const EmplaceCharInterface &iface, const SpanView<void *> &layoutData, float totalSquare) {
175 1268 : if (std::isnan(totalSquare)) {
176 0 : totalSquare = 0.0f;
177 0 : for (auto &it : layoutData) {
178 0 : totalSquare += iface.getWidth(it) * iface.getHeight(it);
179 : }
180 : }
181 :
182 : // find potential best match square
183 1268 : bool s = true;
184 1268 : uint32_t h = 128, w = 128; uint32_t sq2 = h * w;
185 4610 : for (; sq2 < totalSquare; sq2 *= 2, s = !s) {
186 3342 : if (s) { w *= 2; } else { h *= 2; }
187 : }
188 :
189 1268 : LayoutNodeMemoryStorage storage(&iface, memory::pool::acquire());
190 :
191 : while (true) {
192 1436 : auto l = storage.alloc(geom::URect{0, 0, w, h});
193 210250 : for (auto &it : layoutData) {
194 208982 : if (!l->insert(storage, it)) {
195 168 : break;
196 : }
197 : }
198 :
199 1436 : auto nodes = l->nodes();
200 1436 : if (nodes == layoutData.size()) {
201 1268 : l->finalize(storage, 0);
202 1268 : storage.release(l);
203 1268 : break;
204 : } else {
205 168 : if (s) { w *= 2; } else { h *= 2; }
206 168 : sq2 *= 2; s = !s;
207 : }
208 168 : storage.release(l);
209 168 : }
210 :
211 1268 : return geom::Extent2(w, h);
212 : }
213 :
214 : }
|
