/*

    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.

		 */

		if(fmt->Amask) {

		} 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 */

	} 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;

	}