src/tiling.c

   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@yahoo.fr>
  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) */
  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 */
  78 static G_GNUC_CONST gint p2(gint p)
  79 {
  80     return 1 << order(p);
  81 }
  82
  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
  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
 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
 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
 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
 171 struct tiles *make_tiles(gint dim)
 172 {
 173     return make_tiles_rec(dim, TRUE);
 174 }
 175
 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
 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
 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
 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
 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
 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