#include "c4d_general.h"
#include "c4d_shader.h"
#include "c4d_memory.h"
#include "c4d_bitmapfilter.h"

#define	DEBUG	0
#define	USE_TILE_CACHE	1
#define	MAX_COMPONENTS	8																		// maximum number of components per pixel

#include "pixelfetchutil.h"

struct TILE_LRU
{
	TILE_LRU	*prev;
	TILE_LRU	*next;

	LONG			grid_x;
	LONG			grid_y;
	TILE_LRU	**grid_entry;

	BM_TILE		*data;																					// data
};

struct	PIXEL_ROOT
{
	BM_REF		bm;																							// needed for accessing tiles
	LONG			color_space;
	ULONG			px_format;
	LONG			pixel_size;																			// bytes per pixel
	LONG			tile_flags;																			// flags for clipping/texture wrapping

#if	USE_TILE_CACHE
#if DEBUG
	LONG			no_tile_unloads;																// # of times tiles had to be kicked out of the cache
#endif

	TILE_LRU	dummy_first;
	TILE_LRU	dummy_last;

	LONG			tile_shifts;
	LONG			tile_mask;
	LONG			tile_wh;

	LONG			no_tiles;																				// number of currently cached tiles
	LONG			no_max_tiles;																		// maximum number of tiles that should be cached

	ULONG			grid_width;																			// # of tiles along the x axis (must be ULONG!)
	ULONG			grid_height;																		// # of tiles along the y axis (must be ULONG!)
	TILE_LRU	*tile_grid[VARIABLE_ARRAY_SIZE];

#else

	BM_TILE		*tile;

#endif
};

//----------------------------------------------------------------------------------------
// Create a new pixel fetcher object
// Function result:		pixel fetcher reference
// bm:								bitmap reference
// tile_flags:				TILE_REPEAT_BORDER or TILE_REPEAT_TILING
// no_cached_tiles:		0: use default settings > 0: maximum number of cached tiles
//----------------------------------------------------------------------------------------
PIXEL_REF	new_pixel_fetcher( BM_REF bm, LONG tile_flags, LONG no_cached_tiles )
{
	LONG	tile_shifts;
	LONG	tile_wh;
	LONG	grid_w;
	LONG	grid_h;
	LONG	grid_size;
	PIXEL_REF pf;

	tile_shifts = 7;																					// tile size is 128 * 128
	tile_wh = 128;

	grid_w = ( bm->image_rect.x2 + tile_wh - 1 ) / tile_wh;		// width of the lookup table in tiles
	grid_h = ( bm->image_rect.y2 + tile_wh - 1 ) / tile_wh;		// height of the lookup table in tiles
	grid_size = grid_w * grid_h * sizeof( TILE_LRU *);

	pf = (PIXEL_REF) GeAlloc( sizeof( PIXEL_ROOT ) + grid_size );
	if ( pf )
	{
		pf->bm = bm;
		pf->color_space = bm->image_color_space;
		pf->px_format = bm->image_px_format;
		pf->pixel_size = get_PX_BITS( bm->image_px_format ) >> 3;
		pf->tile_flags = tile_flags;

#if USE_TILE_CACHE
#if DEBUG
		pf->no_tile_unloads = 0;
#endif

		pf->dummy_first.prev = 0;																// indicates that this ist first dummy entry
		pf->dummy_first.next = &pf->dummy_last;
		pf->dummy_first.grid_x = MINLONG;
		pf->dummy_first.grid_y = MINLONG;
		pf->dummy_first.grid_entry = 0;
		pf->dummy_first.data = 0;

		pf->dummy_last.prev = &pf->dummy_first;
		pf->dummy_last.next = 0;																// indicates that this is the final dummy entry
		pf->dummy_last.grid_x = MINLONG;
		pf->dummy_last.grid_y = MINLONG;
		pf->dummy_last.grid_entry = 0;
		pf->dummy_last.data = 0;
	
		pf->tile_shifts = tile_shifts;													// tile size is 128 * 128
		pf->tile_wh = tile_wh;
		pf->tile_mask = tile_wh - 1;
	
		pf->no_tiles = 0;																				// currently no tiles allocated
		pf->no_max_tiles = ( bm->image_rect.x2 - bm->image_rect.x1 + tile_wh - 1 ) >> tile_shifts;
		pf->no_max_tiles <<= 1;
		if ( no_cached_tiles > 0 )
			pf->no_max_tiles = no_cached_tiles;
	
		pf->grid_width = grid_w;
		pf->grid_height = grid_h;
		ClearMem( pf->tile_grid, grid_size, 0 );								// empty lookup table
#else
		pf->tile = NULL;
#endif
	}
	return( pf );
}

//----------------------------------------------------------------------------------------
// Delete a pixel fetcher object
// Function result:		-
// pf:								pixel fetcher object
//----------------------------------------------------------------------------------------
void	delete_pixel_fetcher( PIXEL_REF pf )
{
	if ( pf )
	{
#if USE_TILE_CACHE
		TILE_LRU	*lru_tile;

		lru_tile = pf->dummy_first.next;
		while ( lru_tile->next )																// loop till the last dummy entry is reached
		{
			TILE_LRU	*tmp;
			
			tmp = lru_tile;
			lru_tile = lru_tile->next;
			
			BfBitmapTileDetach( pf->bm, tmp->data, FALSE );				// free the tile data
			GeFree( tmp );																				// free lru entry
		}
#else
		if ( pf->tile )
			BfBitmapTileDetach( pf->bm, pf->tile, FALSE );
#endif
		GeFree( pf );
	}
}

#if USE_TILE_CACHE

//----------------------------------------------------------------------------------------
// Return a pixel's address
// Function result:		pixel address or 0
// pf:								pixel fetcher object
// x, y:							coordinates in the image's coordinate space
//----------------------------------------------------------------------------------------
inline static UCHAR	*get_pixel_addr( PIXEL_REF pf, LONG x, LONG y )
{
	ULONG	grid_x;
	ULONG	grid_y;
	TILE_LRU	*lru_tile;
	BM_TILE	*tile;

	grid_x = ((ULONG) x ) >> pf->tile_shifts;	
	grid_y = ((ULONG) y ) >> pf->tile_shifts;	
	lru_tile = pf->dummy_first.next;													// the last recently used tile

	if (( grid_x != (ULONG) lru_tile->grid_x ) || ( grid_y != (ULONG) lru_tile->grid_y ))	// are we not accessing the last recently used tile?
	{
		if (( grid_x >= pf->grid_width ) || ( grid_y >= pf->grid_height ))
		{
			RECT32	*r;
			
			r = &pf->bm->image_rect;
			if ( pf->tile_flags & TILE_REPEAT_TILING )						// wrap around at the border
			{
				x -= r->x1;
				y -= r->y1;
	
				x %= r->x2 - r->x1;																	// note: the modulo result is negative, if x was < 0
				y %= r->y2 - r->y1;
	
				if ( x < 0 )
					x += r->x2;
				else
					x += r->x1;
	
				if ( y < 0 )
					y += r->y2;
				else
					y += r->y1;
			}
			else																									// TILE_REPEAT_BORDER
			{
				if ( x < pf->bm->image_rect.x1 )
					x = pf->bm->image_rect.x1;
		
				if ( x >= pf->bm->image_rect.x2 )
					x = pf->bm->image_rect.x2 - 1;
		
				if ( y < pf->bm->image_rect.y1 )
					y = pf->bm->image_rect.y1;
		
				if ( y >= pf->bm->image_rect.y2 )
					y = pf->bm->image_rect.y2 - 1;
			}
			grid_x = ((ULONG) x ) >> pf->tile_shifts;	
			grid_y = ((ULONG) y ) >> pf->tile_shifts;	
		}
	
		lru_tile = pf->tile_grid[( grid_y * pf->grid_width ) + grid_x];
		if ( lru_tile == 0 )																		// no tile for this area?
		{
			RECT32	tile_rect;
	
			tile_rect.x1 = grid_x << pf->tile_shifts;
			tile_rect.y1 = grid_y << pf->tile_shifts;
			tile_rect.x2 = ( grid_x + 1 ) << pf->tile_shifts;
			tile_rect.y2 = ( grid_y + 1 ) << pf->tile_shifts;
	
			if ( pf->no_tiles >= pf->no_max_tiles )								// free the least important tile?
			{
				pf->no_tiles--;
				lru_tile = pf->dummy_last.prev;
				lru_tile->prev->next = lru_tile->next;							// unlink
				lru_tile->next->prev = lru_tile->prev;
	
				*lru_tile->grid_entry = 0;													// delete the entry in the lookup grid
	
				BfBitmapTileDetach( pf->bm, lru_tile->data, FALSE );	// free the tile data
	
#if DEBUG
				pf->no_tile_unloads++;
#endif
			}
			else																									// add a new lru entry
			{
				lru_tile = (TILE_LRU *) GeAlloc( sizeof( TILE_LRU ));
				if ( lru_tile == 0 )
					return( 0 );		
			}
	
			lru_tile->data = BfBitmapTileGet( pf->bm, &tile_rect, 0, 0, TILE_BM_READ_ONLY, pf->tile_flags );
	
			if ( lru_tile->data == 0 )														// unable to access the tile?
			{
				GeFree( lru_tile );
				return( 0 );																				// Houston, we have a problem
			}
	
			pf->no_tiles++;
	
			lru_tile->next = pf->dummy_first.next;								// insert in the chain as the first
			lru_tile->prev = &pf->dummy_first;
			lru_tile->prev->next = lru_tile;
			lru_tile->next->prev = lru_tile;
	
			lru_tile->grid_x = grid_x;														// save that grid position for a quick lru check at the top of the function
			lru_tile->grid_y = grid_y;
			lru_tile->grid_entry = &pf->tile_grid[( grid_y * pf->grid_width ) + grid_x];
			*lru_tile->grid_entry = lru_tile;											// add entry in the lookup grid
		}
	
		if ( lru_tile != pf->dummy_first.next )									// change the lru order?
		{
			lru_tile->next->prev = lru_tile->prev;								// unlink from the chain
			lru_tile->prev->next = lru_tile->next;
		
			pf->dummy_first.next->prev = lru_tile;								// link with the previously used tile
			lru_tile->next = pf->dummy_first.next;
	
			lru_tile->prev = &pf->dummy_first;										// link with the dummy root
			pf->dummy_first.next = lru_tile;
		}
	}

	tile = lru_tile->data;
	x -= tile->xmin;
	y -= tile->ymin;
	return((UCHAR *) tile->addr + ( tile->width * y ) + ( pf->pixel_size * x ));
}

//----------------------------------------------------------------------------------------
// Return a pixel
// Function result:		TRUE: everything is fine FALSE: can't access the pixel
// pf:								pixel fetcher object
// x:									discrete x coordinate
// y:									discrete y coordinate
// dst:								used to return the pixel
//----------------------------------------------------------------------------------------
Bool	pf_get_pixel( PIXEL_REF pf, LONG x, LONG y, UCHAR *dst )
{
	UCHAR	*p;
	
	p = get_pixel_addr( pf, x, y );
	if ( p )
	{
		LONG	i;
	
		for ( i = pf->pixel_size; i; i--)
			*dst++ = *p++;
		
		return( TRUE );
	}
	return( FALSE );
}

//----------------------------------------------------------------------------------------
// Return a pixel's address
// Function result:		pixel address or 0
// pf:								pixel fetcher object
// x:									discrete x coordinate
// y:									discrete y coordinate
//----------------------------------------------------------------------------------------
UCHAR	*pf_get_pixel_addr( PIXEL_REF pf, LONG x, LONG y )
{
	return( get_pixel_addr( pf, x, y ));
}

#else

Bool	pf_get_pixel( PIXEL_REF pf, LONG x, LONG y, UCHAR *pixel )
{
	UCHAR *p;
	LONG		 i;
	BM_TILE	*tile;

	tile = pf->tile;
	
	if (( tile == 0 ) || ( x < tile->xmin ) || ( x >= tile->xmax ) || ( y < tile->ymin ) || ( y >= tile->ymax ))
	{
		BM_REF	bm;
		RECT32	tile_rect;
		LONG	col;
		LONG	row;

		bm = pf->bm;

		if ( x < bm->image_rect.x1 )
			x = bm->image_rect.x1;
		
		if ( x >= bm->image_rect.x2 )
			x = bm->image_rect.x2 - 1;

		if ( y < bm->image_rect.y1 )
			y = bm->image_rect.y1;
		
		if ( y >= bm->image_rect.y2 )
			y = bm->image_rect.y2 - 1;

		if (( tile == 0 ) || ( x < tile->xmin ) || ( x >= tile->xmax ) || ( y < tile->ymin ) || ( y >= tile->ymax ))
		{
			col = x / bm->preferred_tile_width;
			row	= y / bm->preferred_tile_height;
	
			if ( pf->tile )
				BfBitmapTileDetach( bm, pf->tile, FALSE );
	
			tile_rect = bm->image_rect;
			tile = BfBitmapTileGet( bm, &tile_rect, 0, 0, TILE_BM_READ_ONLY, 0 );
		
			if ( tile == 0 )
				return( FALSE );
	
			pf->tile = tile;
		}
	}

	p = (UCHAR *) tile->addr;
	p += tile->width * ( y - tile->ymin );
	p += pf->pixel_size * ( x - tile->xmin );

	for (i = pf->pixel_size; i; i--)
		*pixel++ = *p++;

	return( TRUE );
}

UCHAR	*pf_get_pixel_addr( PIXEL_REF pf, LONG x, LONG y )
{
	UCHAR *p;
	BM_TILE	*tile;

	tile = pf->tile;
	
	if (( tile == 0 ) || ( x < tile->xmin ) || ( x >= tile->xmax ) || ( y < tile->ymin ) || ( y >= tile->ymax ))
	{
		BM_REF	bm;
		RECT32	tile_rect;
		LONG	col;
		LONG	row;

		bm = pf->bm;

		if ( x < bm->image_rect.x1 )
			x = bm->image_rect.x1;
		
		if ( x >= bm->image_rect.x2 )
			x = bm->image_rect.x2 - 1;

		if ( y < bm->image_rect.y1 )
			y = bm->image_rect.y1;
		
		if ( y >= bm->image_rect.y2 )
			y = bm->image_rect.y2 - 1;

		if (( tile == 0 ) || ( x < tile->xmin ) || ( x >= tile->xmax ) || ( y < tile->ymin ) || ( y >= tile->ymax ))
		{
			col = x / bm->preferred_tile_width;
			row	= y / bm->preferred_tile_height;
	
			if ( pf->tile )
				BfBitmapTileDetach( bm, pf->tile, FALSE );
	
			tile_rect = bm->image_rect;
			tile = BfBitmapTileGet( bm, &tile_rect, 0, 0, TILE_BM_READ_ONLY, 0 );
		
			if ( tile == 0 )
				return( 0 );
	
			pf->tile = tile;
		}
	}

	p = (UCHAR *) tile->addr;
	p += tile->width * ( y - tile->ymin );
	p += pf->pixel_size * ( x - tile->xmin );
	return( p );
}
#endif

//----------------------------------------------------------------------------------------
// Return a bilinear filtered pixel
// Function result:		TRUE: everything is fine FALSE: can't access the pixel
// pf:								pixel fetcher object
// fx:								continous x coordinate (.5 is pixel center)
// fy:								continous y coordinate (.5 is pixel center)
// dst:								used to return the pixel
//----------------------------------------------------------------------------------------
Bool	pf_get_pixel_bilinear( PIXEL_REF pf, LReal fx, LReal fy, UCHAR *dst )
{
  UCHAR	pbuf[4][MAX_COMPONENTS];
  LONG	ix;
  LONG	iy;

	fx -= 0.5;
	fy -= 0.5;

	ix = (LONG) floor( fx );
	iy = (LONG) floor( fy );
	
	if ( pf_get_pixel( pf, ix, iy, pbuf[0] ))
	{
		if ( pf_get_pixel( pf, ix + 1, iy, pbuf[1] ))
		{
			if ( pf_get_pixel( pf, ix, iy + 1, pbuf[2] ))
			{
				if ( pf_get_pixel( pf, ix + 1, iy + 1, pbuf[3] ))
				{
				  LReal	values[4];
					LONG	i;
	
					if ( pf->color_space & CSPACE_ALPHA_FLAG )
					{
						LReal	alpha[4];
						LReal	new_alpha;

						values[0] = (LReal) pbuf[0][0];
						values[1] = (LReal) pbuf[1][0];
						values[2] = (LReal) pbuf[2][0];
						values[3] = (LReal) pbuf[3][0];
						alpha[0] = values[0] / 255.0;
						alpha[1] = values[1] / 255.0;
						alpha[2] = values[2] / 255.0;
						alpha[3] = values[3] / 255.0;

						new_alpha = bilinear_double( fx, fy, values );
						*dst++ = (UCHAR) ( new_alpha + 0.5 );
						new_alpha /= 255.0;
						if ( new_alpha == 0.0 )
							new_alpha = 1.0;
						
						for ( i = 1; i < pf->pixel_size; i++ )
						{
							LReal	v;

							values[0] = (LReal) pbuf[0][i] * alpha[0];
							values[1] = (LReal) pbuf[1][i] * alpha[1];
							values[2] = (LReal) pbuf[2][i] * alpha[2];
							values[3] = (LReal) pbuf[3][i] * alpha[3];
						
							v = bilinear_double( fx, fy, values );
							v /= new_alpha;
							if ( v < 0.0 )
								v = 0.0;
							if ( v > 255.0 )
								v = 255.0;
							*dst++ = (UCHAR) ( v + 0.5 );
						}
					}
					else
					{
						for ( i = 0; i < pf->pixel_size; i++ )
						{
							values[0] = (LReal) pbuf[0][i];
							values[1] = (LReal) pbuf[1][i];
							values[2] = (LReal) pbuf[2][i];
							values[3] = (LReal) pbuf[3][i];
						
							*dst++ = (UCHAR) ( bilinear_double( fx, fy, values ) + 0.5 );
						}
					}
					return( TRUE );
				}
			}
		}
	}
	return( FALSE );
}

UCHAR	bilinear8( LReal x, LReal y, UCHAR *values )
{
  LReal m0, m1;

  x -= floor( x );
  y -= floor( y );

// the following line ist just another way of writing m0 = ( values[0] * ( 1 - x )) + ( values[1] * x )
  m0 = (LReal) values[0] + ( x * ((LReal) values[1] - values[0] ));
  m1 = (LReal) values[2] + ( x * ((LReal) values[3] - values[2] ));

  return((UCHAR) ( m0 + ( y * ( m1 - m0 ))));
}

UWORD	bilinear16( LReal x, LReal y, UWORD *values )
{
  LReal m0, m1;

  x -= floor( x );
  y -= floor( y );

  m0 = (LReal) values[0] + ( x * ((LReal) values[1] - values[0] ));
  m1 = (LReal) values[2] + ( x * ((LReal) values[3] - values[2] ));

  return((UWORD) ( m0 + ( y * ( m1 - m0 ))));
}

LReal	bilinear_double( LReal x, LReal y, LReal *values )
{
  LReal m0, m1;

  x -= floor( x );
  y -= floor( y );

// the following line ist just another way of writing m0 = ( values[0] * ( 1 - x )) + ( values[1] * x )
  m0 = values[0] + ( x * ( values[1] - values[0] ));
  m1 = values[2] + ( x * ( values[3] - values[2] ));

  return( m0 + ( y * ( m1 - m0 )));
}
