/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * See the COPYING file for license information.
 *
 * Guillaume Chazarain <guichaz@gmail.com>
 */

/**********************************************
 * Compute the tiling for a texture dimension *
 **********************************************/

/*
 * To test the tiling algorithm:
 * $ cc -DSTANDALONE $(pkg-config --libs --cflags gtk+-2.0) \
 *      -Iinclude tiling.c -o tiling
 * $ ./tiling 1025
 */
#ifndef STANDALONE
#define STANDALONE 0
#endif

#if STANDALONE
#include <glib.h>
#include <stdio.h>              /* printf() */
#include <stdlib.h>             /* atoi() */
#else

#include "gliv.h"
#include "options.h"
#endif

#include "tiling.h"

#if STANDALONE
#define MAX_TEXTURE_SIZE 2048
#else
extern rt_struct *rt;
#define MAX_TEXTURE_SIZE (rt->max_texture_size)
#endif

/*
 * glTexImage2D(3G): All implementations support texture images
 * that are at least 64 texels (wide|high).
 */
#define MIN_TEXTURE_SIZE 64

#define ARRAY_LENGTH (order(MAX_TEXTURE_SIZE) + 1)


/* ln2(p) */
static G_GNUC_CONST gint order(gint p)
{
    gint power = 1;
    gint ord = 0;

    while (power < p) {
        power += power;
        ord++;
    }

    return ord;
}

/* Smallest power of two bigger than p */
static G_GNUC_CONST gint p2(gint p)
{
    return 1 << order(p);
}

static struct tiles *new_tiles(void)
{
    struct tiles *tiles = g_new0(struct tiles, 1);
    tiles->array = g_new0(gint, ARRAY_LENGTH);
    return tiles;
}

void destroy_tiles(struct tiles *tiles)
{
    if (tiles != NULL) {
        g_free(tiles->array);
        g_free(tiles);
    }
}

#define MORE_WASTE_THAN(a, b) ((a) - (b) > MIN_TEXTURE_SIZE)

static G_GNUC_CONST gint try_single_texture(gint dim)
{
    gint low, high;

    if (dim <= MIN_TEXTURE_SIZE)
        return MIN_TEXTURE_SIZE;

    if (dim > MAX_TEXTURE_SIZE)
        return 0;

    high = p2(dim);
    low = high / 2;

    if (MORE_WASTE_THAN(dim - low, high - dim))
        return high;

    return 0;
}

#define ADD_TILES(nb, size) (dim -= add_tiles(tiles, (nb), (size)))
#define ADD_TILE(size) ADD_TILES(1, (size))

static gint add_tiles(struct tiles *tiles, gint nb, gint size)
{
    tiles->array[order(size)] += nb;
    tiles->nb_tiles += nb;
    return nb * (size - 1);
}

static struct tiles *make_tiles_rec(gint dim, gboolean can_be_single)
{
    gint low, high;
    struct tiles *tiles_low, *tiles_high;
    struct tiles *tiles = new_tiles();

    if (dim > 0 && can_be_single) {
        gint single = try_single_texture(dim);
        if (single)
            ADD_TILE(single);
    }

    while (dim > 1) {
        if (dim >= MAX_TEXTURE_SIZE) {
            ADD_TILES(dim / MAX_TEXTURE_SIZE, MAX_TEXTURE_SIZE);
            continue;
        }

        if (dim <= MIN_TEXTURE_SIZE) {
            ADD_TILE(MIN_TEXTURE_SIZE);
            continue;
        }

        high = p2(dim);
        low = high / 2;

        tiles_low = make_tiles_rec(dim - low + 1, FALSE);
        tiles_high = make_tiles_rec(dim - high + 1, FALSE);

        if (MORE_WASTE_THAN(tiles_high->waste, tiles_low->waste))
            ADD_TILE(low);
        else
            ADD_TILE(high);

        destroy_tiles(tiles_low);
        destroy_tiles(tiles_high);
    }

    tiles->waste = -dim + 1;
    return tiles;
}

struct tiles *make_tiles(gint dim)
{
    return make_tiles_rec(dim, TRUE);
}

static gboolean array_pos_empty(struct tiles_iterator *iter, gint i)
{
    gint number = iter->tiles->array[i];

    if (iter->first_pass)
        number += i % 2;
    else
        number += 1 - (i % 2);

    return number <= 1;
}

struct tiles_iterator *tiles_iterator_new(struct tiles *tiles)
{
    struct tiles_iterator *iter = g_new(struct tiles_iterator, 1);

    iter->tiles = tiles;
    iter->first_pass = TRUE;
    iter->current_array_pos = -1;
    iter->remaining_in_pos = 0;

    return iter;
}

gint tiles_iterator_next(struct tiles_iterator * iter)
{
    gint i, length = ARRAY_LENGTH;

    if (iter->current_array_pos >= length)
        return -1;

    if (iter->remaining_in_pos != 0) {
        iter->remaining_in_pos--;
        return 1 << iter->current_array_pos;
    }

    if (iter->first_pass) {
        for (i = iter->current_array_pos + 1; i < length; i++) {
            if (!array_pos_empty(iter, i)) {
                iter->current_array_pos = i;
                iter->remaining_in_pos = iter->tiles->array[i] / 2;
                if (iter->tiles->array[i] % 2 == 1)
                    iter->remaining_in_pos += i % 2;

                if (iter->remaining_in_pos != 0) {
                    iter->remaining_in_pos--;
                    return 1 << i;
                }
            }
        }

        iter->first_pass = FALSE;
        iter->current_array_pos = length;
    }

    for (i = iter->current_array_pos - 1; i >= 0; i--) {
        if (!array_pos_empty(iter, i)) {
            iter->current_array_pos = i;
            iter->remaining_in_pos = iter->tiles->array[i] / 2;
            if (iter->tiles->array[i] % 2 == 1)
                iter->remaining_in_pos += 1 - (i % 2);

            if (iter->remaining_in_pos != 0) {
                iter->remaining_in_pos--;
                return 1 << i;
            }
        }
    }

    iter->current_array_pos = length;
    return -1;
}

#if STANDALONE
static gint print_tiles(struct tiles *tiles)
{
    struct tiles_iterator *iter = tiles_iterator_new(tiles);
    gint tile;

    printf("%d tiles:\n", tiles->nb_tiles);
    while ((tile = tiles_iterator_next(iter)) > 0)
        printf("%d ", tile);

    g_free(iter);
    return tiles->waste;
}

static void test_tile(gint size)
{
    struct tiles *tiles = make_tiles(size);
    struct tiles_iterator *iter;
    gint count = 0, tile_size = 0;
    gint length = ARRAY_LENGTH;
    gint i;

    for (i = 0; i < length; i++) {
        if ((1 << i) != MAX_TEXTURE_SIZE && tiles->array[i] > 1) {
            printf("Error with %d\n", size);
            break;
        }

        count += tiles->array[i];
        tile_size += tiles->array[i] * 1 << i;
    }

    tile_size -= tiles->nb_tiles - 1;

    if (tile_size - size != tiles->waste || tiles->nb_tiles != count)
        printf("Error with %d\n", size);

    iter = tiles_iterator_new(tiles);
    count = 0;
    tile_size = 0;
    while ((i = tiles_iterator_next(iter)) > 0) {
        count++;
        tile_size += i;
    }

    tile_size -= tiles->nb_tiles - 1;

    if (tile_size - size != tiles->waste || tiles->nb_tiles != count)
        printf("Error with %d\n", size);

    g_free(iter);
    destroy_tiles(tiles);
}

gint main(gint argc, char **argv)
{
    if (argc > 1) {
        struct tiles *tiles = make_tiles(atoi(argv[1]));
        gint waste = print_tiles(tiles);
        printf("=> waste: %d\n", waste);
        destroy_tiles(tiles);
    } else {
        for (;;)
            test_tile(g_random_int_range(1, MAX_TEXTURE_SIZE * 10));
    }

    return 0;
}
#endif