1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software
14 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
15 *
16 * See the COPYING file for license information.
17 *
18 * Guillaume Chazarain <guichaz@gmail.com>
19 */
20
21 /**********************************************
22 * Compute the tiling for a texture dimension *
23 **********************************************/
24
25 /*
26 * To test the tiling algorithm:
27 * $ cc -DSTANDALONE $(pkg-config --libs --cflags gtk+-2.0) \
28 * -Iinclude tiling.c -o tiling
29 * $ ./tiling 1025
30 */
31 #ifndef STANDALONE
32 #define STANDALONE 0
33 #endif
34
35 #if STANDALONE
36 #include <glib.h>
37 #include <stdio.h> /* printf() */
38 #include <stdlib.h> /* atoi() */
39 #else
40
41 #include "gliv.h"
42 #include "options.h"
43 #endif
44
45 #include "tiling.h"
46
47 #if STANDALONE
48 #define MAX_TEXTURE_SIZE 2048
49 #else
50 extern rt_struct *rt;
51 #define MAX_TEXTURE_SIZE (rt->max_texture_size)
52 #endif
53
54 /*
55 * glTexImage2D(3G): All implementations support texture images
56 * that are at least 64 texels (wide|high).
57 */
58 #define MIN_TEXTURE_SIZE 64
59
60 #define ARRAY_LENGTH (order(MAX_TEXTURE_SIZE) + 1)
61
62
63 /* ln2(p) */
order(gint p)64 static G_GNUC_CONST gint order(gint p)
65 {
66 gint power = 1;
67 gint ord = 0;
68
69 while (power < p) {
70 power += power;
71 ord++;
72 }
73
74 return ord;
75 }
76
77 /* Smallest power of two bigger than p */
p2(gint p)78 static G_GNUC_CONST gint p2(gint p)
79 {
80 return 1 << order(p);
81 }
82
new_tiles(void)83 static struct tiles *new_tiles(void)
84 {
85 struct tiles *tiles = g_new0(struct tiles, 1);
86 tiles->array = g_new0(gint, ARRAY_LENGTH);
87 return tiles;
88 }
89
destroy_tiles(struct tiles * tiles)90 void destroy_tiles(struct tiles *tiles)
91 {
92 if (tiles != NULL) {
93 g_free(tiles->array);
94 g_free(tiles);
95 }
96 }
97
98 #define MORE_WASTE_THAN(a, b) ((a) - (b) > MIN_TEXTURE_SIZE)
99
try_single_texture(gint dim)100 static G_GNUC_CONST gint try_single_texture(gint dim)
101 {
102 gint low, high;
103
104 if (dim <= MIN_TEXTURE_SIZE)
105 return MIN_TEXTURE_SIZE;
106
107 if (dim > MAX_TEXTURE_SIZE)
108 return 0;
109
110 high = p2(dim);
111 low = high / 2;
112
113 if (MORE_WASTE_THAN(dim - low, high - dim))
114 return high;
115
116 return 0;
117 }
118
119 #define ADD_TILES(nb, size) (dim -= add_tiles(tiles, (nb), (size)))
120 #define ADD_TILE(size) ADD_TILES(1, (size))
121
add_tiles(struct tiles * tiles,gint nb,gint size)122 static gint add_tiles(struct tiles *tiles, gint nb, gint size)
123 {
124 tiles->array[order(size)] += nb;
125 tiles->nb_tiles += nb;
126 return nb * (size - 1);
127 }
128
make_tiles_rec(gint dim,gboolean can_be_single)129 static struct tiles *make_tiles_rec(gint dim, gboolean can_be_single)
130 {
131 gint low, high;
132 struct tiles *tiles_low, *tiles_high;
133 struct tiles *tiles = new_tiles();
134
135 if (dim > 0 && can_be_single) {
136 gint single = try_single_texture(dim);
137 if (single)
138 ADD_TILE(single);
139 }
140
141 while (dim > 1) {
142 if (dim >= MAX_TEXTURE_SIZE) {
143 ADD_TILES(dim / MAX_TEXTURE_SIZE, MAX_TEXTURE_SIZE);
144 continue;
145 }
146
147 if (dim <= MIN_TEXTURE_SIZE) {
148 ADD_TILE(MIN_TEXTURE_SIZE);
149 continue;
150 }
151
152 high = p2(dim);
153 low = high / 2;
154
155 tiles_low = make_tiles_rec(dim - low + 1, FALSE);
156 tiles_high = make_tiles_rec(dim - high + 1, FALSE);
157
158 if (MORE_WASTE_THAN(tiles_high->waste, tiles_low->waste))
159 ADD_TILE(low);
160 else
161 ADD_TILE(high);
162
163 destroy_tiles(tiles_low);
164 destroy_tiles(tiles_high);
165 }
166
167 tiles->waste = -dim + 1;
168 return tiles;
169 }
170
make_tiles(gint dim)171 struct tiles *make_tiles(gint dim)
172 {
173 return make_tiles_rec(dim, TRUE);
174 }
175
array_pos_empty(struct tiles_iterator * iter,gint i)176 static gboolean array_pos_empty(struct tiles_iterator *iter, gint i)
177 {
178 gint number = iter->tiles->array[i];
179
180 if (iter->first_pass)
181 number += i % 2;
182 else
183 number += 1 - (i % 2);
184
185 return number <= 1;
186 }
187
tiles_iterator_new(struct tiles * tiles)188 struct tiles_iterator *tiles_iterator_new(struct tiles *tiles)
189 {
190 struct tiles_iterator *iter = g_new(struct tiles_iterator, 1);
191
192 iter->tiles = tiles;
193 iter->first_pass = TRUE;
194 iter->current_array_pos = -1;
195 iter->remaining_in_pos = 0;
196
197 return iter;
198 }
199
tiles_iterator_next(struct tiles_iterator * iter)200 gint tiles_iterator_next(struct tiles_iterator * iter)
201 {
202 gint i, length = ARRAY_LENGTH;
203
204 if (iter->current_array_pos >= length)
205 return -1;
206
207 if (iter->remaining_in_pos != 0) {
208 iter->remaining_in_pos--;
209 return 1 << iter->current_array_pos;
210 }
211
212 if (iter->first_pass) {
213 for (i = iter->current_array_pos + 1; i < length; i++) {
214 if (!array_pos_empty(iter, i)) {
215 iter->current_array_pos = i;
216 iter->remaining_in_pos = iter->tiles->array[i] / 2;
217 if (iter->tiles->array[i] % 2 == 1)
218 iter->remaining_in_pos += i % 2;
219
220 if (iter->remaining_in_pos != 0) {
221 iter->remaining_in_pos--;
222 return 1 << i;
223 }
224 }
225 }
226
227 iter->first_pass = FALSE;
228 iter->current_array_pos = length;
229 }
230
231 for (i = iter->current_array_pos - 1; i >= 0; i--) {
232 if (!array_pos_empty(iter, i)) {
233 iter->current_array_pos = i;
234 iter->remaining_in_pos = iter->tiles->array[i] / 2;
235 if (iter->tiles->array[i] % 2 == 1)
236 iter->remaining_in_pos += 1 - (i % 2);
237
238 if (iter->remaining_in_pos != 0) {
239 iter->remaining_in_pos--;
240 return 1 << i;
241 }
242 }
243 }
244
245 iter->current_array_pos = length;
246 return -1;
247 }
248
249 #if STANDALONE
print_tiles(struct tiles * tiles)250 static gint print_tiles(struct tiles *tiles)
251 {
252 struct tiles_iterator *iter = tiles_iterator_new(tiles);
253 gint tile;
254
255 printf("%d tiles:\n", tiles->nb_tiles);
256 while ((tile = tiles_iterator_next(iter)) > 0)
257 printf("%d ", tile);
258
259 g_free(iter);
260 return tiles->waste;
261 }
262
test_tile(gint size)263 static void test_tile(gint size)
264 {
265 struct tiles *tiles = make_tiles(size);
266 struct tiles_iterator *iter;
267 gint count = 0, tile_size = 0;
268 gint length = ARRAY_LENGTH;
269 gint i;
270
271 for (i = 0; i < length; i++) {
272 if ((1 << i) != MAX_TEXTURE_SIZE && tiles->array[i] > 1) {
273 printf("Error with %d\n", size);
274 break;
275 }
276
277 count += tiles->array[i];
278 tile_size += tiles->array[i] * 1 << i;
279 }
280
281 tile_size -= tiles->nb_tiles - 1;
282
283 if (tile_size - size != tiles->waste || tiles->nb_tiles != count)
284 printf("Error with %d\n", size);
285
286 iter = tiles_iterator_new(tiles);
287 count = 0;
288 tile_size = 0;
289 while ((i = tiles_iterator_next(iter)) > 0) {
290 count++;
291 tile_size += i;
292 }
293
294 tile_size -= tiles->nb_tiles - 1;
295
296 if (tile_size - size != tiles->waste || tiles->nb_tiles != count)
297 printf("Error with %d\n", size);
298
299 g_free(iter);
300 destroy_tiles(tiles);
301 }
302
main(gint argc,char ** argv)303 gint main(gint argc, char **argv)
304 {
305 if (argc > 1) {
306 struct tiles *tiles = make_tiles(atoi(argv[1]));
307 gint waste = print_tiles(tiles);
308 printf("=> waste: %d\n", waste);
309 destroy_tiles(tiles);
310 } else {
311 for (;;)
312 test_tile(g_random_int_range(1, MAX_TEXTURE_SIZE * 10));
313 }
314
315 return 0;
316 }
317 #endif
318