1/*!
2 * \file colorstop_atlas.cpp
3 * \brief file colorstop_atlas.cpp
4 *
5 * Copyright 2016 by Intel.
6 *
7 * Contact: kevin.rogovin@gmail.com
8 *
9 * This Source Code Form is subject to the
10 * terms of the Mozilla Public License, v. 2.0.
11 * If a copy of the MPL was not distributed with
12 * this file, You can obtain one at
13 * http://mozilla.org/MPL/2.0/.
14 *
15 * \author Kevin Rogovin <kevin.rogovin@gmail.com>
16 *
17 */
18
19
20#include <vector>
21#include <algorithm>
22#include <mutex>
23#include <fastuidraw/colorstop_atlas.hpp>
24#include <fastuidraw/util/math.hpp>
25#include <private/interval_allocator.hpp>
26#include <private/util_private.hpp>
27
28namespace
29{
30 class ColorInterpolator
31 {
32 public:
33 ColorInterpolator(const fastuidraw::ColorStop &begin,
34 const fastuidraw::ColorStop &end):
35 m_start(begin.m_place),
36 m_coeff(1.0f / (end.m_place - begin.m_place)),
37 m_startColor(begin.m_color),
38 m_deltaColor(fastuidraw::vec4(end.m_color) - fastuidraw::vec4(begin.m_color))
39 {}
40
41 fastuidraw::u8vec4
42 interpolate(float t)
43 {
44 float s;
45 fastuidraw::vec4 value;
46
47 s = (t - m_start) * m_coeff;
48 s = std::min(1.0f, std::max(0.0f, s));
49 value = m_startColor + s * m_deltaColor;
50
51 return fastuidraw::u8vec4(value);
52 };
53
54 private:
55 float m_start, m_coeff;
56 fastuidraw::vec4 m_startColor, m_deltaColor;
57 };
58
59 typedef std::pair<fastuidraw::ivec2, int> delayed_free_entry;
60
61 class ColorStopAtlasPrivate
62 {
63 public:
64 explicit
65 ColorStopAtlasPrivate(fastuidraw::reference_counted_ptr<fastuidraw::ColorStopBackingStore> pbacking_store);
66
67 void
68 remove_entry_from_available_layers(std::map<int, std::set<int> >::iterator, int y);
69
70 void
71 add_bookkeeping(int new_size);
72
73 void
74 deallocate_implement(fastuidraw::ivec2 location, int width);
75
76 mutable std::mutex m_mutex;
77 int m_delayed_interval_freeing_counter;
78 std::vector<delayed_free_entry> m_delayed_freed_intervals;
79
80 fastuidraw::reference_counted_ptr<fastuidraw::ColorStopBackingStore> m_backing_store;
81 int m_allocated;
82
83 /* Each layer has an interval allocator to allocate
84 * and free "color stop arrays"
85 */
86 std::vector<fastuidraw::interval_allocator*> m_layer_allocator;
87
88 /* m_available_layers[key] gives indices into m_layer_allocator
89 * for those layers for which largest_free_interval() returns
90 * key.
91 */
92 std::map<int, std::set<int> > m_available_layers;
93 };
94
95 class ColorStopBackingStorePrivate
96 {
97 public:
98 ColorStopBackingStorePrivate(int w, int num_layers):
99 m_dimensions(w, num_layers),
100 m_width_times_height(m_dimensions.x() * m_dimensions.y())
101 {}
102
103 fastuidraw::ivec2 m_dimensions;
104 int m_width_times_height;
105 };
106
107 class ColorStopSequencePrivate
108 {
109 public:
110 fastuidraw::reference_counted_ptr<fastuidraw::ColorStopAtlas> m_atlas;
111 fastuidraw::ivec2 m_texel_location;
112 int m_width;
113 int m_start_slack, m_end_slack;
114 };
115}
116
117////////////////////////////////////////
118// ColorStopAtlasPrivate methods
119ColorStopAtlasPrivate::
120ColorStopAtlasPrivate(fastuidraw::reference_counted_ptr<fastuidraw::ColorStopBackingStore> pbacking_store):
121 m_delayed_interval_freeing_counter(0),
122 m_backing_store(pbacking_store),
123 m_allocated(0)
124{
125 FASTUIDRAWassert(m_backing_store);
126 if (m_backing_store->dimensions().y() > 0)
127 {
128 add_bookkeeping(m_backing_store->dimensions().y());
129 }
130}
131
132void
133ColorStopAtlasPrivate::
134remove_entry_from_available_layers(std::map<int, std::set<int> >::iterator iter, int y)
135{
136 FASTUIDRAWassert(iter != m_available_layers.end());
137 FASTUIDRAWassert(iter->second.find(y) != iter->second.end());
138 iter->second.erase(y);
139 if (iter->second.empty())
140 {
141 m_available_layers.erase(iter);
142 }
143}
144
145void
146ColorStopAtlasPrivate::
147add_bookkeeping(int new_size)
148{
149 int width(m_backing_store->dimensions().x());
150 int old_size(m_layer_allocator.size());
151 std::set<int> &S(m_available_layers[width]);
152
153 FASTUIDRAWassert(new_size > old_size);
154 m_layer_allocator.resize(new_size, nullptr);
155 for(int y = old_size; y < new_size; ++y)
156 {
157 m_layer_allocator[y] = FASTUIDRAWnew fastuidraw::interval_allocator(width);
158 S.insert(y);
159 }
160}
161
162void
163ColorStopAtlasPrivate::
164deallocate_implement(fastuidraw::ivec2 location, int width)
165{
166 int y(location.y());
167 FASTUIDRAWassert(m_layer_allocator[y]);
168 FASTUIDRAWassert(m_delayed_interval_freeing_counter == 0);
169
170 int old_max, new_max;
171
172 old_max = m_layer_allocator[y]->largest_free_interval();
173 m_layer_allocator[y]->free_interval(location.x(), width);
174 new_max = m_layer_allocator[y]->largest_free_interval();
175
176 if (old_max != new_max)
177 {
178 std::map<int, std::set<int> >::iterator iter;
179
180 iter = m_available_layers.find(old_max);
181 remove_entry_from_available_layers(iter, y);
182 m_available_layers[new_max].insert(y);
183 }
184 m_allocated -= width;
185}
186
187/////////////////////////////////////
188// fastuidraw::ColorStopBackingStore methods
189fastuidraw::ColorStopBackingStore::
190ColorStopBackingStore(int w, int num_layers)
191{
192 m_d = FASTUIDRAWnew ColorStopBackingStorePrivate(w, num_layers);
193}
194
195fastuidraw::ColorStopBackingStore::
196ColorStopBackingStore(ivec2 wl)
197{
198 m_d = FASTUIDRAWnew ColorStopBackingStorePrivate(wl.x(), wl.y());
199}
200
201fastuidraw::ColorStopBackingStore::
202~ColorStopBackingStore()
203{
204 ColorStopBackingStorePrivate *d;
205 d = static_cast<ColorStopBackingStorePrivate*>(m_d);
206 FASTUIDRAWdelete(d);
207 m_d = nullptr;
208}
209
210fastuidraw::ivec2
211fastuidraw::ColorStopBackingStore::
212dimensions(void) const
213{
214 ColorStopBackingStorePrivate *d;
215 d = static_cast<ColorStopBackingStorePrivate*>(m_d);
216 return d->m_dimensions;
217}
218
219int
220fastuidraw::ColorStopBackingStore::
221width_times_height(void) const
222{
223 ColorStopBackingStorePrivate *d;
224 d = static_cast<ColorStopBackingStorePrivate*>(m_d);
225 return d->m_width_times_height;
226}
227
228void
229fastuidraw::ColorStopBackingStore::
230resize(int new_num_layers)
231{
232 ColorStopBackingStorePrivate *d;
233 d = static_cast<ColorStopBackingStorePrivate*>(m_d);
234 FASTUIDRAWassert(new_num_layers > d->m_dimensions.y());
235 resize_implement(new_num_layers);
236 d->m_dimensions.y() = new_num_layers;
237 d->m_width_times_height = d->m_dimensions.x() * d->m_dimensions.y();
238}
239
240///////////////////////////////////////
241// fastuidraw::ColorStopAtlas methods
242fastuidraw::ColorStopAtlas::
243ColorStopAtlas(reference_counted_ptr<ColorStopBackingStore> pbacking_store)
244{
245 m_d = FASTUIDRAWnew ColorStopAtlasPrivate(pbacking_store);
246}
247
248fastuidraw::ColorStopAtlas::
249~ColorStopAtlas()
250{
251 ColorStopAtlasPrivate *d;
252 d = static_cast<ColorStopAtlasPrivate*>(m_d);
253
254 FASTUIDRAWassert(d->m_delayed_interval_freeing_counter == 0);
255 FASTUIDRAWassert(d->m_allocated == 0);
256 for(interval_allocator *q : d->m_layer_allocator)
257 {
258 FASTUIDRAWdelete(q);
259 }
260 FASTUIDRAWdelete(d);
261 m_d = nullptr;
262}
263
264fastuidraw::reference_counted_ptr<fastuidraw::ColorStopSequence>
265fastuidraw::ColorStopAtlas::
266create(const ColorStopArray &color_stops, unsigned int pwidth)
267{
268 pwidth = t_min(pwidth, max_width());
269 if (pwidth == 0)
270 {
271 return nullptr;
272 }
273 return FASTUIDRAWnew ColorStopSequence(color_stops, *this, pwidth);
274}
275
276void
277fastuidraw::ColorStopAtlas::
278lock_resources(void)
279{
280 ColorStopAtlasPrivate *d;
281 d = static_cast<ColorStopAtlasPrivate*>(m_d);
282
283 std::lock_guard<std::mutex> m(d->m_mutex);
284 ++d->m_delayed_interval_freeing_counter;
285}
286
287void
288fastuidraw::ColorStopAtlas::
289unlock_resources(void)
290{
291 ColorStopAtlasPrivate *d;
292 d = static_cast<ColorStopAtlasPrivate*>(m_d);
293
294 std::lock_guard<std::mutex> m(d->m_mutex);
295 FASTUIDRAWassert(d->m_delayed_interval_freeing_counter >= 1);
296 --d->m_delayed_interval_freeing_counter;
297 if (d->m_delayed_interval_freeing_counter == 0)
298 {
299 for(unsigned int i = 0, endi = d->m_delayed_freed_intervals.size(); i < endi; ++i)
300 {
301 d->deallocate_implement(d->m_delayed_freed_intervals[i].first,
302 d->m_delayed_freed_intervals[i].second);
303 }
304 d->m_delayed_freed_intervals.clear();
305 }
306}
307
308void
309fastuidraw::ColorStopAtlas::
310deallocate(ivec2 location, int width)
311{
312 ColorStopAtlasPrivate *d;
313 d = static_cast<ColorStopAtlasPrivate*>(m_d);
314
315 std::lock_guard<std::mutex> m(d->m_mutex);
316 if (d->m_delayed_interval_freeing_counter == 0)
317 {
318 d->deallocate_implement(location, width);
319 }
320 else
321 {
322 d->m_delayed_freed_intervals.push_back(delayed_free_entry(location, width));
323 }
324}
325
326void
327fastuidraw::ColorStopAtlas::
328flush(void) const
329{
330 ColorStopAtlasPrivate *d;
331 d = static_cast<ColorStopAtlasPrivate*>(m_d);
332
333 std::lock_guard<std::mutex> m(d->m_mutex);
334 d->m_backing_store->flush();
335}
336
337int
338fastuidraw::ColorStopAtlas::
339total_available(void) const
340{
341 ColorStopAtlasPrivate *d;
342 d = static_cast<ColorStopAtlasPrivate*>(m_d);
343
344 std::lock_guard<std::mutex> m(d->m_mutex);
345 return d->m_backing_store->width_times_height() - d->m_allocated;
346}
347
348fastuidraw::ivec2
349fastuidraw::ColorStopAtlas::
350allocate(c_array<const u8vec4> data)
351{
352 ColorStopAtlasPrivate *d;
353 d = static_cast<ColorStopAtlasPrivate*>(m_d);
354
355 std::lock_guard<std::mutex> m(d->m_mutex);
356
357 std::map<int, std::set<int> >::iterator iter;
358 ivec2 return_value;
359 unsigned int width(data.size());
360
361 FASTUIDRAWassert(width > 0);
362 FASTUIDRAWassert(width <= max_width());
363
364 iter = d->m_available_layers.lower_bound(width);
365 if (iter == d->m_available_layers.end())
366 {
367 /* TODO: what should the resize algorithm be?
368 * Right now we double the size, but that might
369 * be excessive.
370 */
371 int new_size, old_size;
372 old_size = d->m_backing_store->dimensions().y();
373 new_size = std::max(1, old_size * 2);
374 d->m_backing_store->resize(new_size);
375 d->add_bookkeeping(new_size);
376
377 iter = d->m_available_layers.lower_bound(width);
378 FASTUIDRAWassert(iter != d->m_available_layers.end());
379 }
380
381 FASTUIDRAWassert(!iter->second.empty());
382
383 int y(*iter->second.begin());
384 int old_max, new_max;
385
386 old_max = d->m_layer_allocator[y]->largest_free_interval();
387 return_value.x() = d->m_layer_allocator[y]->allocate_interval(width);
388 FASTUIDRAWassert(return_value.x() >= 0);
389 new_max = d->m_layer_allocator[y]->largest_free_interval();
390
391 if (old_max != new_max)
392 {
393 d->remove_entry_from_available_layers(iter, y);
394 d->m_available_layers[new_max].insert(y);
395 }
396 return_value.y() = y;
397
398 d->m_backing_store->set_data(return_value.x(), return_value.y(),
399 width, data);
400 d->m_allocated += width;
401 return return_value;
402}
403
404unsigned int
405fastuidraw::ColorStopAtlas::
406max_width(void) const
407{
408 ColorStopAtlasPrivate *d;
409 d = static_cast<ColorStopAtlasPrivate*>(m_d);
410 return d->m_backing_store->dimensions().x();
411}
412
413fastuidraw::reference_counted_ptr<const fastuidraw::ColorStopBackingStore>
414fastuidraw::ColorStopAtlas::
415backing_store(void) const
416{
417 ColorStopAtlasPrivate *d;
418 d = static_cast<ColorStopAtlasPrivate*>(m_d);
419 return d->m_backing_store;
420}
421
422///////////////////////////////////////////
423// fastuidraw::ColorStopSequence methods
424fastuidraw::ColorStopSequence::
425ColorStopSequence(const ColorStopArray &pcolor_stops,
426 ColorStopAtlas &atlas, unsigned int pwidth)
427{
428 ColorStopSequencePrivate *d;
429 d = FASTUIDRAWnew ColorStopSequencePrivate();
430 m_d = d;
431
432 d->m_atlas = &atlas;
433 d->m_width = pwidth;
434
435 c_array<const ColorStop> color_stops(pcolor_stops.values());
436 FASTUIDRAWassert(d->m_atlas);
437 FASTUIDRAWassert(pwidth>0);
438
439 if (pwidth >= d->m_atlas->max_width())
440 {
441 d->m_width = d->m_atlas->max_width();
442 d->m_start_slack = 0;
443 d->m_end_slack = 0;
444 }
445 else if (pwidth == d->m_atlas->max_width() - 1)
446 {
447 d->m_start_slack = 0;
448 d->m_end_slack = 1;
449 }
450 else
451 {
452 d->m_start_slack = 1;
453 d->m_end_slack = 1;
454 }
455
456 std::vector<u8vec4> data(d->m_width + d->m_start_slack + d->m_end_slack);
457
458 /* Discretize and interpolate color_stops into data */
459 {
460 unsigned int data_i, color_stops_i;
461 float current_t, delta_t;
462
463 delta_t = 1.0f / static_cast<float>(d->m_width);
464 current_t = static_cast<float>(-d->m_start_slack) * delta_t;
465
466 for(data_i = 0; current_t <= color_stops[0].m_place; ++data_i, current_t += delta_t)
467 {
468 data[data_i] = color_stops[0].m_color;
469 }
470
471 for(color_stops_i = 1; color_stops_i < color_stops.size(); ++color_stops_i)
472 {
473 ColorStop prev_color(color_stops[color_stops_i-1]);
474 ColorStop next_color(color_stops[color_stops_i]);
475
476 /* There are cases where an application might
477 * add two color stops with the same stop location;
478 * these are for the purpose of changing color
479 * immediately at the named location. Adding the
480 * check avoids a divide error. The next texel
481 * in the gradient will observe the dramatic change.
482 * However, passing an interpolate between the
483 * immediate change and the texel after it will
484 * have the gradient interpolate from before the
485 * change to after the change sadly.
486 *
487 * The only way to really handle "fast immediate"
488 * changes is to make an array of (stop, color)
489 * pair values packed into an array readable from
490 * the shader and the fragment shader does the
491 * search. This means that rather than a single
492 * texture() command we would have multiple buffer
493 * look up value in the frag shader to get the
494 * interpolate. We can optimize it some where we
495 * increase the array size to the nearest power of 2
496 * so that within a triangle there is no branching
497 * in the hunt, but that would mean log2(N) buffer
498 * reads per pixel. ICK.
499 */
500 if (current_t < next_color.m_place)
501 {
502 ColorInterpolator color_interpolate(prev_color, next_color);
503
504 for(; current_t < next_color.m_place && data_i < data.size();
505 ++data_i, current_t += delta_t)
506 {
507 data[data_i] = color_interpolate.interpolate(current_t);
508 }
509 }
510 }
511
512 for(;data_i < data.size(); ++data_i)
513 {
514 data[data_i] = color_stops.back().m_color;
515 }
516 }
517
518
519 d->m_texel_location = d->m_atlas->allocate(make_c_array(data));
520
521 /* Adjust m_texel_location to remove the start slack
522 */
523 d->m_texel_location.x() += d->m_start_slack;
524}
525
526fastuidraw::ColorStopSequence::
527~ColorStopSequence(void)
528{
529 ColorStopSequencePrivate *d;
530 d = static_cast<ColorStopSequencePrivate*>(m_d);
531
532 ivec2 loc(d->m_texel_location);
533
534 loc.x() -= d->m_start_slack;
535 d->m_atlas->deallocate(loc, d->m_width + d->m_start_slack + d->m_end_slack);
536 FASTUIDRAWdelete(d);
537 m_d = nullptr;
538}
539
540fastuidraw::ivec2
541fastuidraw::ColorStopSequence::
542texel_location(void) const
543{
544 ColorStopSequencePrivate *d;
545 d = static_cast<ColorStopSequencePrivate*>(m_d);
546 return d->m_texel_location;
547}
548
549int
550fastuidraw::ColorStopSequence::
551width(void) const
552{
553 ColorStopSequencePrivate *d;
554 d = static_cast<ColorStopSequencePrivate*>(m_d);
555 return d->m_width;
556}
557
558fastuidraw::ColorStopAtlas&
559fastuidraw::ColorStopSequence::
560atlas(void) const
561{
562 ColorStopSequencePrivate *d;
563 d = static_cast<ColorStopSequencePrivate*>(m_d);
564 return *d->m_atlas;
565}
566