/*
    SDL - Simple DirectMedia Layer
    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002  Sam Lantinga

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library 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
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    Sam Lantinga
    slouken@libsdl.org
*/

#ifdef SAVE_RCSID
static char rcsid =
 "@(#) $Id$";
#endif

/* General (mostly internal) pixel/color manipulation routines for SDL */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "SDL_error.h"
#include "SDL_endian.h"
#include "SDL_video.h"
#include "SDL_sysvideo.h"
#include "SDL_blit.h"
#include "SDL_pixels_c.h"
#include "SDL_RLEaccel_c.h"

/* Helper functions */
/*
 * Allocate a pixel format structure and fill it according to the given info.
 */
SDL_PixelFormat *SDL_AllocFormat(int bpp,
			Uint32 Rmask, Uint32 Gmask, Uint32 Bmask, Uint32 Amask)
{
	SDL_PixelFormat *format;
	Uint32 mask;

	/* Allocate an empty pixel format structure */
	format = malloc(sizeof(*format));
	if ( format == NULL ) {
		SDL_OutOfMemory();
		return(NULL);
	}
	memset(format, 0, sizeof(*format));
	format->alpha = SDL_ALPHA_OPAQUE;

	/* Set up the format */
	format->BitsPerPixel = bpp;
	format->BytesPerPixel = (bpp+7)/8;
	switch (bpp) {
		case 1:
			/* Create the 2 color black-white palette */
			format->palette = (SDL_Palette *)malloc(
							sizeof(SDL_Palette));
			if ( format->palette == NULL ) {
				SDL_FreeFormat(format);
				SDL_OutOfMemory();
				return(NULL);
			}
			(format->palette)->ncolors = 2;
			(format->palette)->colors = (SDL_Color *)malloc(
				(format->palette)->ncolors*sizeof(SDL_Color));
			if ( (format->palette)->colors == NULL ) {
				SDL_FreeFormat(format);
				SDL_OutOfMemory();
				return(NULL);
			}
			format->palette->colors[0].r = 0xFF;
			format->palette->colors[0].g = 0xFF;
			format->palette->colors[0].b = 0xFF;
			format->palette->colors[1].r = 0x00;
			format->palette->colors[1].g = 0x00;
			format->palette->colors[1].b = 0x00;
			format->Rloss = 8;
			format->Gloss = 8;
			format->Bloss = 8;
			format->Aloss = 8;
			format->Rshift = 0;
			format->Gshift = 0;
			format->Bshift = 0;
			format->Ashift = 0;
			format->Rmask = 0;
			format->Gmask = 0;
			format->Bmask = 0;
			format->Amask = 0;
			break;

		case 4:
			/* Create the 16 color VGA palette */
			format->palette = (SDL_Palette *)malloc(
							sizeof(SDL_Palette));
			if ( format->palette == NULL ) {
				SDL_FreeFormat(format);
				SDL_OutOfMemory();
				return(NULL);
			}
			(format->palette)->ncolors = 16;
			(format->palette)->colors = (SDL_Color *)malloc(
				(format->palette)->ncolors*sizeof(SDL_Color));
			if ( (format->palette)->colors == NULL ) {
				SDL_FreeFormat(format);
				SDL_OutOfMemory();
				return(NULL);
			}
			/* Punt for now, will this ever be used? */
			memset((format->palette)->colors, 0,
				(format->palette)->ncolors*sizeof(SDL_Color));

			/* Palettized formats have no mask info */
			format->Rloss = 8;
			format->Gloss = 8;
			format->Bloss = 8;
			format->Aloss = 8;
			format->Rshift = 0;
			format->Gshift = 0;
			format->Bshift = 0;
			format->Ashift = 0;
			format->Rmask = 0;
			format->Gmask = 0;
			format->Bmask = 0;
			format->Amask = 0;
			break;

		case 8:
			/* Create an empty 256 color palette */
			format->palette = (SDL_Palette *)malloc(
							sizeof(SDL_Palette));
			if ( format->palette == NULL ) {
				SDL_FreeFormat(format);
				SDL_OutOfMemory();
				return(NULL);
			}
			(format->palette)->ncolors = 256;
			(format->palette)->colors = (SDL_Color *)malloc(
				(format->palette)->ncolors*sizeof(SDL_Color));
			if ( (format->palette)->colors == NULL ) {
				SDL_FreeFormat(format);
				SDL_OutOfMemory();
				return(NULL);
			}
			memset((format->palette)->colors, 0,
				(format->palette)->ncolors*sizeof(SDL_Color));

			/* Palettized formats have no mask info */
			format->Rloss = 8;
			format->Gloss = 8;
			format->Bloss = 8;
			format->Aloss = 8;
			format->Rshift = 0;
			format->Gshift = 0;
			format->Bshift = 0;
			format->Ashift = 0;
			format->Rmask = 0;
			format->Gmask = 0;
			format->Bmask = 0;
			format->Amask = 0;
			break;

		default:
			/* No palette, just packed pixel info */
			format->palette = NULL;
			format->Rshift = 0;
			format->Rloss = 8;
			if ( Rmask ) {
				for ( mask = Rmask; !(mask&0x01); mask >>= 1 )
					++format->Rshift;
				for ( ; (mask&0x01); mask >>= 1 )
					--format->Rloss;
			}
			format->Gshift = 0;
			format->Gloss = 8;
			if ( Gmask ) {
				for ( mask = Gmask; !(mask&0x01); mask >>= 1 )
					++format->Gshift;
				for ( ; (mask&0x01); mask >>= 1 )
					--format->Gloss;
			}
			format->Bshift = 0;
			format->Bloss = 8;
			if ( Bmask ) {
				for ( mask = Bmask; !(mask&0x01); mask >>= 1 )
					++format->Bshift;
				for ( ; (mask&0x01); mask >>= 1 )
					--format->Bloss;
			}
			format->Ashift = 0;
			format->Aloss = 8;
			if ( Amask ) {
				for ( mask = Amask; !(mask&0x01); mask >>= 1 )
					++format->Ashift;
				for ( ; (mask&0x01); mask >>= 1 )
					--format->Aloss;
			}
			format->Rmask = Rmask;
			format->Gmask = Gmask;
			format->Bmask = Bmask;
			format->Amask = Amask;
			break;
	}
	/* Calculate some standard bitmasks, if necessary 
	 * Note:  This could conflict with an alpha mask, if given.
	 */
	if ( (bpp > 8) && !format->Rmask && !format->Gmask && !format->Bmask ) {
		/* R-G-B */
		if ( bpp > 24 )
			bpp = 24;
		format->Rloss = 8-(bpp/3);
		format->Gloss = 8-(bpp/3)-(bpp%3);
		format->Bloss = 8-(bpp/3);
		format->Rshift = ((bpp/3)+(bpp%3))+(bpp/3);
		format->Gshift = (bpp/3);
		format->Bshift = 0;
		format->Rmask = ((0xFF>>format->Rloss)<<format->Rshift);
		format->Gmask = ((0xFF>>format->Gloss)<<format->Gshift);
		format->Bmask = ((0xFF>>format->Bloss)<<format->Bshift);
	}
	return(format);
}
SDL_PixelFormat *SDL_ReallocFormat(SDL_Surface *surface, int bpp,
			Uint32 Rmask, Uint32 Gmask, Uint32 Bmask, Uint32 Amask)
{
	if ( surface->format ) {
		SDL_FreeFormat(surface->format);
		SDL_FormatChanged(surface);
	}
	surface->format = SDL_AllocFormat(bpp, Rmask, Gmask, Bmask, Amask);
	return surface->format;
}

/*
 * Change any previous mappings from/to the new surface format
 */
void SDL_FormatChanged(SDL_Surface *surface)
{
	surface->format_version++;
	SDL_InvalidateMap(surface->map);
}
/*
 * Free a previously allocated format structure
 */
void SDL_FreeFormat(SDL_PixelFormat *format)
{
	if ( format ) {
		if ( format->palette ) {
			if ( format->palette->colors ) {
				free(format->palette->colors);
			}
			free(format->palette);
		}
		free(format);
	}
}
/*
 * Calculate an 8-bit (3 red, 3 green, 2 blue) dithered palette of colors
 */
void SDL_DitherColors(SDL_Color *colors, int bpp)
{
	int i;
	if(bpp != 8)
		return;		/* only 8bpp supported right now */

	for(i = 0; i < 256; i++) {
		int r, g, b;
		/* map each bit field to the full [0, 255] interval,
		   so 0 is mapped to (0, 0, 0) and 255 to (255, 255, 255) */
		r = i & 0xe0;
		r |= r >> 3 | r >> 6;
		colors[i].r = r;
		g = (i << 3) & 0xe0;
		g |= g >> 3 | g >> 6;
		colors[i].g = g;
		b = i & 0x3;
		b |= b << 2;
		b |= b << 4;
		colors[i].b = b;
	}
}
/* 
 * Calculate the pad-aligned scanline width of a surface
 */
Uint16 SDL_CalculatePitch(SDL_Surface *surface)
{
	Uint16 pitch;

	/* Surface should be 4-byte aligned for speed */
	pitch = surface->w*surface->format->BytesPerPixel;
	switch (surface->format->BitsPerPixel) {
		case 1:
			pitch = (pitch+7)/8;
			break;
		case 4:
			pitch = (pitch+1)/2;
			break;
		default:
			break;
	}
	pitch = (pitch + 3) & ~3;	/* 4-byte aligning */
	return(pitch);
}
/*
 * Match an RGB value to a particular palette index
 */
Uint8 SDL_FindColor(SDL_Palette *pal, Uint8 r, Uint8 g, Uint8 b)
{
	/* Do colorspace distance matching */
	unsigned int smallest;
	unsigned int distance;
	int rd, gd, bd;
	int i;
	Uint8 pixel=0;
		
	smallest = ~0;
	for ( i=0; i<pal->ncolors; ++i ) {
		rd = pal->colors[i].r - r;
		gd = pal->colors[i].g - g;
		bd = pal->colors[i].b - b;
		distance = (rd*rd)+(gd*gd)+(bd*bd);
		if ( distance < smallest ) {
			pixel = i;
			if ( distance == 0 ) { /* Perfect match! */
				break;
			}
			smallest = distance;
		}
	}
	return(pixel);
}

/* Find the opaque pixel value corresponding to an RGB triple */
Uint32 SDL_MapRGB(SDL_PixelFormat *format, Uint8 r, Uint8 g, Uint8 b)
{
	if ( format->palette == NULL ) {
		return (r >> format->Rloss) << format->Rshift
		       | (g >> format->Gloss) << format->Gshift
		       | (b >> format->Bloss) << format->Bshift
		       | format->Amask;
	} else {
		return SDL_FindColor(format->palette, r, g, b);
	}
}

/* Find the pixel value corresponding to an RGBA quadruple */
Uint32 SDL_MapRGBA(SDL_PixelFormat *format, Uint8 r, Uint8 g, Uint8 b, Uint8 a)
{
	if ( format->palette == NULL ) {
	        return (r >> format->Rloss) << format->Rshift
		    | (g >> format->Gloss) << format->Gshift
		    | (b >> format->Bloss) << format->Bshift
		    | ((a >> format->Aloss) << format->Ashift & format->Amask);
	} else {
		return SDL_FindColor(format->palette, r, g, b);
	}
}

void SDL_GetRGBA(Uint32 pixel, SDL_PixelFormat *fmt,
		 Uint8 *r, Uint8 *g, Uint8 *b, Uint8 *a)
{
	if ( fmt->palette == NULL ) {
	        /*
		 * This makes sure that the result is mapped to the
		 * interval [0..255], and the maximum value for each
		 * component is 255. This is important to make sure
		 * that white is indeed reported as (255, 255, 255),
		 * and that opaque alpha is 255.
		 * This only works for RGB bit fields at least 4 bit
		 * wide, which is almost always the case.
		 */
	        unsigned v;
		v = (pixel & fmt->Rmask) >> fmt->Rshift;
		*r = (v << fmt->Rloss) + (v >> (8 - (fmt->Rloss << 1)));
		v = (pixel & fmt->Gmask) >> fmt->Gshift;
		*g = (v << fmt->Gloss) + (v >> (8 - (fmt->Gloss << 1)));
		v = (pixel & fmt->Bmask) >> fmt->Bshift;
		*b = (v << fmt->Bloss) + (v >> (8 - (fmt->Bloss << 1)));
		if(fmt->Amask) {
		        v = (pixel & fmt->Amask) >> fmt->Ashift;
			*a = (v << fmt->Aloss) + (v >> (8 - (fmt->Aloss << 1)));
		} else {
		        *a = SDL_ALPHA_OPAQUE;
                }
	} else {
		*r = fmt->palette->colors[pixel].r;
		*g = fmt->palette->colors[pixel].g;
		*b = fmt->palette->colors[pixel].b;
		*a = SDL_ALPHA_OPAQUE;
	}
}

void SDL_GetRGB(Uint32 pixel, SDL_PixelFormat *fmt, Uint8 *r,Uint8 *g,Uint8 *b)
{
	if ( fmt->palette == NULL ) {
	        /* the note for SDL_GetRGBA above applies here too */
	        unsigned v;
		v = (pixel & fmt->Rmask) >> fmt->Rshift;
		*r = (v << fmt->Rloss) + (v >> (8 - (fmt->Rloss << 1)));
		v = (pixel & fmt->Gmask) >> fmt->Gshift;
		*g = (v << fmt->Gloss) + (v >> (8 - (fmt->Gloss << 1)));
		v = (pixel & fmt->Bmask) >> fmt->Bshift;
		*b = (v << fmt->Bloss) + (v >> (8 - (fmt->Bloss << 1)));
	} else {
		*r = fmt->palette->colors[pixel].r;
		*g = fmt->palette->colors[pixel].g;
		*b = fmt->palette->colors[pixel].b;
	}
}

/* Apply gamma to a set of colors - this is easy. :) */
void SDL_ApplyGamma(Uint16 *gamma, SDL_Color *colors, SDL_Color *output,
							int ncolors)
{
	int i;

	for ( i=0; i<ncolors; ++i ) {
		output[i].r = gamma[0*256 + colors[i].r] >> 8;
		output[i].g = gamma[1*256 + colors[i].g] >> 8;
		output[i].b = gamma[2*256 + colors[i].b] >> 8;
	}
}

/* Map from Palette to Palette */
static Uint8 *Map1to1(SDL_Palette *src, SDL_Palette *dst, int *identical)
{
	Uint8 *map;
	int i;

	if ( identical ) {
		if ( src->ncolors <= dst->ncolors ) {
			/* If an identical palette, no need to map */
			if ( memcmp(src->colors, dst->colors, src->ncolors*
						sizeof(SDL_Color)) == 0 ) {
				*identical = 1;
				return(NULL);
			}
		}
		*identical = 0;
	}
	map = (Uint8 *)malloc(src->ncolors);
	if ( map == NULL ) {
		SDL_OutOfMemory();
		return(NULL);
	}
	for ( i=0; i<src->ncolors; ++i ) {
		map[i] = SDL_FindColor(dst,
			src->colors[i].r, src->colors[i].g, src->colors[i].b);
	}
	return(map);
}
/* Map from Palette to BitField */
static Uint8 *Map1toN(SDL_Palette *src, SDL_PixelFormat *dst)
{
	Uint8 *map;
	int i;
	int  bpp;
	unsigned alpha;

	bpp = ((dst->BytesPerPixel == 3) ? 4 : dst->BytesPerPixel);
	map = (Uint8 *)malloc(src->ncolors*bpp);
	if ( map == NULL ) {
		SDL_OutOfMemory();
		return(NULL);
	}

	alpha = dst->Amask ? SDL_ALPHA_OPAQUE : 0;
	/* We memory copy to the pixel map so the endianness is preserved */
	for ( i=0; i<src->ncolors; ++i ) {
		ASSEMBLE_RGBA(&map[i*bpp], dst->BytesPerPixel, dst,
			      src->colors[i].r, src->colors[i].g,
			      src->colors[i].b, alpha);
	}
	return(map);
}
/* Map from BitField to Dithered-Palette to Palette */
static Uint8 *MapNto1(SDL_PixelFormat *src, SDL_Palette *dst, int *identical)
{
	/* Generate a 256 color dither palette */
	SDL_Palette dithered;
	SDL_Color colors[256];

	dithered.ncolors = 256;
	SDL_DitherColors(colors, 8);
	dithered.colors = colors;
	return(Map1to1(&dithered, dst, identical));
}

SDL_BlitMap *SDL_AllocBlitMap(void)
{
	SDL_BlitMap *map;

	/* Allocate the empty map */
	map = (SDL_BlitMap *)malloc(sizeof(*map));
	if ( map == NULL ) {
		SDL_OutOfMemory();
		return(NULL);
	}
	memset(map, 0, sizeof(*map));

	/* Allocate the software blit data */
	map->sw_data = (struct private_swaccel *)malloc(sizeof(*map->sw_data));
	if ( map->sw_data == NULL ) {
		SDL_FreeBlitMap(map);
		SDL_OutOfMemory();
		return(NULL);
	}
	memset(map->sw_data, 0, sizeof(*map->sw_data));

	/* It's ready to go */
	return(map);
}
void SDL_InvalidateMap(SDL_BlitMap *map)
{
	if ( ! map ) {
		return;
	}
	map->dst = NULL;
	map->format_version = (unsigned int)-1;
	if ( map->table ) {
		free(map->table);
		map->table = NULL;
	}
}
int SDL_MapSurface (SDL_Surface *src, SDL_Surface *dst)
{
	SDL_PixelFormat *srcfmt;
	SDL_PixelFormat *dstfmt;
	SDL_BlitMap *map;

	/* Clear out any previous mapping */
	map = src->map;
	if ( (src->flags & SDL_RLEACCEL) == SDL_RLEACCEL ) {
		SDL_UnRLESurface(src, 1);
	}
	SDL_InvalidateMap(map);

	/* Figure out what kind of mapping we're doing */
	map->identity = 0;
	srcfmt = src->format;
	dstfmt = dst->format;
	switch (srcfmt->BytesPerPixel) {
	    case 1:
		switch (dstfmt->BytesPerPixel) {
		    case 1:
			/* Palette --> Palette */
			/* If both SDL_HWSURFACE, assume have same palette */
			if ( ((src->flags & SDL_HWSURFACE) == SDL_HWSURFACE) &&
			     ((dst->flags & SDL_HWSURFACE) == SDL_HWSURFACE) ) {
				map->identity = 1;
			} else {
				map->table = Map1to1(srcfmt->palette,
					dstfmt->palette, &map->identity);
			}
			if ( ! map->identity ) {
				if ( map->table == NULL ) {
					return(-1);
				}
			}
			if (srcfmt->BitsPerPixel!=dstfmt->BitsPerPixel)
				map->identity = 0;
			break;

		    default:
			/* Palette --> BitField */
			map->table = Map1toN(srcfmt->palette, dstfmt);
			if ( map->table == NULL ) {
				return(-1);
			}
			break;
		}
		break;
	default:
		switch (dstfmt->BytesPerPixel) {
		    case 1:
			/* BitField --> Palette */
			map->table = MapNto1(srcfmt,
					dstfmt->palette, &map->identity);
			if ( ! map->identity ) {
				if ( map->table == NULL ) {
					return(-1);
				}
			}
			map->identity = 0;	/* Don't optimize to copy */
			break;
		    default:
			/* BitField --> BitField */
			if ( FORMAT_EQUAL(srcfmt, dstfmt) )
				map->identity = 1;
			break;
		}
		break;
	}

	map->dst = dst;
	map->format_version = dst->format_version;

	/* Choose your blitters wisely */
	return(SDL_CalculateBlit(src));
}
void SDL_FreeBlitMap(SDL_BlitMap *map)
{
	if ( map ) {
		SDL_InvalidateMap(map);
		if ( map->sw_data != NULL ) {
			free(map->sw_data);
		}
		free(map);
	}
}