1/*
2    SDL - Simple DirectMedia Layer
3    Copyright (C) 1997-2006 Sam Lantinga
4
5    This library is free software; you can redistribute it and/or
6    modify it under the terms of the GNU Lesser General Public
7    License as published by the Free Software Foundation; either
8    version 2.1 of the License, or (at your option) any later version.
9
10    This library is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    Lesser General Public License for more details.
14
15    You should have received a copy of the GNU Lesser General Public
16    License along with this library; if not, write to the Free Software
17    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18
19    Sam Lantinga
20    slouken@libsdl.org
21*/
22#include "SDL_config.h"
23
24/* General (mostly internal) pixel/color manipulation routines for SDL */
25
26#include "SDL_endian.h"
27#include "SDL_video.h"
28#include "SDL_sysvideo.h"
29#include "SDL_blit.h"
30#include "SDL_pixels_c.h"
31#include "SDL_RLEaccel_c.h"
32
33/* Helper functions */
34/*
35 * Allocate a pixel format structure and fill it according to the given info.
36 */
37SDL_PixelFormat *SDL_AllocFormat(int bpp,
38			Uint32 Rmask, Uint32 Gmask, Uint32 Bmask, Uint32 Amask)
39{
40	SDL_PixelFormat *format;
41	Uint32 mask;
42
43	/* Allocate an empty pixel format structure */
44	format = SDL_malloc(sizeof(*format));
45	if ( format == NULL ) {
46		SDL_OutOfMemory();
47		return(NULL);
48	}
49	SDL_memset(format, 0, sizeof(*format));
50	format->alpha = SDL_ALPHA_OPAQUE;
51
52	/* Set up the format */
53	format->BitsPerPixel = bpp;
54	format->BytesPerPixel = (bpp+7)/8;
55	if ( Rmask || Bmask || Gmask ) { /* Packed pixels with custom mask */
56		format->palette = NULL;
57		format->Rshift = 0;
58		format->Rloss = 8;
59		if ( Rmask ) {
60			for ( mask = Rmask; !(mask&0x01); mask >>= 1 )
61				++format->Rshift;
62			for ( ; (mask&0x01); mask >>= 1 )
63				--format->Rloss;
64		}
65		format->Gshift = 0;
66		format->Gloss = 8;
67		if ( Gmask ) {
68			for ( mask = Gmask; !(mask&0x01); mask >>= 1 )
69				++format->Gshift;
70			for ( ; (mask&0x01); mask >>= 1 )
71				--format->Gloss;
72		}
73		format->Bshift = 0;
74		format->Bloss = 8;
75		if ( Bmask ) {
76			for ( mask = Bmask; !(mask&0x01); mask >>= 1 )
77				++format->Bshift;
78			for ( ; (mask&0x01); mask >>= 1 )
79				--format->Bloss;
80		}
81		format->Ashift = 0;
82		format->Aloss = 8;
83		if ( Amask ) {
84			for ( mask = Amask; !(mask&0x01); mask >>= 1 )
85				++format->Ashift;
86			for ( ; (mask&0x01); mask >>= 1 )
87				--format->Aloss;
88		}
89		format->Rmask = Rmask;
90		format->Gmask = Gmask;
91		format->Bmask = Bmask;
92		format->Amask = Amask;
93	} else if ( bpp > 8 ) {		/* Packed pixels with standard mask */
94		/* R-G-B */
95		if ( bpp > 24 )
96			bpp = 24;
97		format->Rloss = 8-(bpp/3);
98		format->Gloss = 8-(bpp/3)-(bpp%3);
99		format->Bloss = 8-(bpp/3);
100		format->Rshift = ((bpp/3)+(bpp%3))+(bpp/3);
101		format->Gshift = (bpp/3);
102		format->Bshift = 0;
103		format->Rmask = ((0xFF>>format->Rloss)<<format->Rshift);
104		format->Gmask = ((0xFF>>format->Gloss)<<format->Gshift);
105		format->Bmask = ((0xFF>>format->Bloss)<<format->Bshift);
106	} else {
107		/* Palettized formats have no mask info */
108		format->Rloss = 8;
109		format->Gloss = 8;
110		format->Bloss = 8;
111		format->Aloss = 8;
112		format->Rshift = 0;
113		format->Gshift = 0;
114		format->Bshift = 0;
115		format->Ashift = 0;
116		format->Rmask = 0;
117		format->Gmask = 0;
118		format->Bmask = 0;
119		format->Amask = 0;
120	}
121	if ( bpp <= 8 ) {			/* Palettized mode */
122		int ncolors = 1<<bpp;
123#ifdef DEBUG_PALETTE
124		fprintf(stderr,"bpp=%d ncolors=%d\n",bpp,ncolors);
125#endif
126		format->palette = (SDL_Palette *)SDL_malloc(sizeof(SDL_Palette));
127		if ( format->palette == NULL ) {
128			SDL_FreeFormat(format);
129			SDL_OutOfMemory();
130			return(NULL);
131		}
132		(format->palette)->ncolors = ncolors;
133		(format->palette)->colors = (SDL_Color *)SDL_malloc(
134				(format->palette)->ncolors*sizeof(SDL_Color));
135		if ( (format->palette)->colors == NULL ) {
136			SDL_FreeFormat(format);
137			SDL_OutOfMemory();
138			return(NULL);
139		}
140		if ( Rmask || Bmask || Gmask ) {
141			/* create palette according to masks */
142			int i;
143			int Rm=0,Gm=0,Bm=0;
144			int Rw=0,Gw=0,Bw=0;
145#ifdef ENABLE_PALETTE_ALPHA
146			int Am=0,Aw=0;
147#endif
148			if(Rmask)
149			{
150				Rw=8-format->Rloss;
151				for(i=format->Rloss;i>0;i-=Rw)
152					Rm|=1<<i;
153			}
154#ifdef DEBUG_PALETTE
155			fprintf(stderr,"Rw=%d Rm=0x%02X\n",Rw,Rm);
156#endif
157			if(Gmask)
158			{
159				Gw=8-format->Gloss;
160				for(i=format->Gloss;i>0;i-=Gw)
161					Gm|=1<<i;
162			}
163#ifdef DEBUG_PALETTE
164			fprintf(stderr,"Gw=%d Gm=0x%02X\n",Gw,Gm);
165#endif
166			if(Bmask)
167			{
168				Bw=8-format->Bloss;
169				for(i=format->Bloss;i>0;i-=Bw)
170					Bm|=1<<i;
171			}
172#ifdef DEBUG_PALETTE
173			fprintf(stderr,"Bw=%d Bm=0x%02X\n",Bw,Bm);
174#endif
175#ifdef ENABLE_PALETTE_ALPHA
176			if(Amask)
177			{
178				Aw=8-format->Aloss;
179				for(i=format->Aloss;i>0;i-=Aw)
180					Am|=1<<i;
181			}
182# ifdef DEBUG_PALETTE
183			fprintf(stderr,"Aw=%d Am=0x%02X\n",Aw,Am);
184# endif
185#endif
186			for(i=0; i < ncolors; ++i) {
187				int r,g,b;
188				r=(i&Rmask)>>format->Rshift;
189				r=(r<<format->Rloss)|((r*Rm)>>Rw);
190				format->palette->colors[i].r=r;
191
192				g=(i&Gmask)>>format->Gshift;
193				g=(g<<format->Gloss)|((g*Gm)>>Gw);
194				format->palette->colors[i].g=g;
195
196				b=(i&Bmask)>>format->Bshift;
197				b=(b<<format->Bloss)|((b*Bm)>>Bw);
198				format->palette->colors[i].b=b;
199
200#ifdef ENABLE_PALETTE_ALPHA
201				a=(i&Amask)>>format->Ashift;
202				a=(a<<format->Aloss)|((a*Am)>>Aw);
203				format->palette->colors[i].unused=a;
204#else
205				format->palette->colors[i].unused=0;
206#endif
207			}
208		} else if ( ncolors == 2 ) {
209			/* Create a black and white bitmap palette */
210			format->palette->colors[0].r = 0xFF;
211			format->palette->colors[0].g = 0xFF;
212			format->palette->colors[0].b = 0xFF;
213			format->palette->colors[1].r = 0x00;
214			format->palette->colors[1].g = 0x00;
215			format->palette->colors[1].b = 0x00;
216		} else {
217			/* Create an empty palette */
218			SDL_memset((format->palette)->colors, 0,
219				(format->palette)->ncolors*sizeof(SDL_Color));
220		}
221	}
222	return(format);
223}
224SDL_PixelFormat *SDL_ReallocFormat(SDL_Surface *surface, int bpp,
225			Uint32 Rmask, Uint32 Gmask, Uint32 Bmask, Uint32 Amask)
226{
227	if ( surface->format ) {
228		SDL_FreeFormat(surface->format);
229		SDL_FormatChanged(surface);
230	}
231	surface->format = SDL_AllocFormat(bpp, Rmask, Gmask, Bmask, Amask);
232	return surface->format;
233}
234
235/*
236 * Change any previous mappings from/to the new surface format
237 */
238void SDL_FormatChanged(SDL_Surface *surface)
239{
240	static int format_version = 0;
241	++format_version;
242	if ( format_version < 0 ) { /* It wrapped... */
243		format_version = 1;
244	}
245	surface->format_version = format_version;
246	SDL_InvalidateMap(surface->map);
247}
248/*
249 * Free a previously allocated format structure
250 */
251void SDL_FreeFormat(SDL_PixelFormat *format)
252{
253	if ( format ) {
254		if ( format->palette ) {
255			if ( format->palette->colors ) {
256				SDL_free(format->palette->colors);
257			}
258			SDL_free(format->palette);
259		}
260		SDL_free(format);
261	}
262}
263/*
264 * Calculate an 8-bit (3 red, 3 green, 2 blue) dithered palette of colors
265 */
266void SDL_DitherColors(SDL_Color *colors, int bpp)
267{
268	int i;
269	if(bpp != 8)
270		return;		/* only 8bpp supported right now */
271
272	for(i = 0; i < 256; i++) {
273		int r, g, b;
274		/* map each bit field to the full [0, 255] interval,
275		   so 0 is mapped to (0, 0, 0) and 255 to (255, 255, 255) */
276		r = i & 0xe0;
277		r |= r >> 3 | r >> 6;
278		colors[i].r = r;
279		g = (i << 3) & 0xe0;
280		g |= g >> 3 | g >> 6;
281		colors[i].g = g;
282		b = i & 0x3;
283		b |= b << 2;
284		b |= b << 4;
285		colors[i].b = b;
286	}
287}
288/*
289 * Calculate the pad-aligned scanline width of a surface
290 */
291Uint16 SDL_CalculatePitch(SDL_Surface *surface)
292{
293	Uint16 pitch;
294
295	/* Surface should be 4-byte aligned for speed */
296	pitch = surface->w*surface->format->BytesPerPixel;
297	switch (surface->format->BitsPerPixel) {
298		case 1:
299			pitch = (pitch+7)/8;
300			break;
301		case 4:
302			pitch = (pitch+1)/2;
303			break;
304		default:
305			break;
306	}
307	pitch = (pitch + 3) & ~3;	/* 4-byte aligning */
308	return(pitch);
309}
310/*
311 * Match an RGB value to a particular palette index
312 */
313Uint8 SDL_FindColor(SDL_Palette *pal, Uint8 r, Uint8 g, Uint8 b)
314{
315	/* Do colorspace distance matching */
316	unsigned int smallest;
317	unsigned int distance;
318	int rd, gd, bd;
319	int i;
320	Uint8 pixel=0;
321
322	smallest = ~0;
323	for ( i=0; i<pal->ncolors; ++i ) {
324		rd = pal->colors[i].r - r;
325		gd = pal->colors[i].g - g;
326		bd = pal->colors[i].b - b;
327		distance = (rd*rd)+(gd*gd)+(bd*bd);
328		if ( distance < smallest ) {
329			pixel = i;
330			if ( distance == 0 ) { /* Perfect match! */
331				break;
332			}
333			smallest = distance;
334		}
335	}
336	return(pixel);
337}
338
339/* Find the opaque pixel value corresponding to an RGB triple */
340Uint32 SDL_MapRGB
341(const SDL_PixelFormat * const format,
342 const Uint8 r, const Uint8 g, const Uint8 b)
343{
344	if ( format->palette == NULL ) {
345		return (r >> format->Rloss) << format->Rshift
346		       | (g >> format->Gloss) << format->Gshift
347		       | (b >> format->Bloss) << format->Bshift
348		       | format->Amask;
349	} else {
350		return SDL_FindColor(format->palette, r, g, b);
351	}
352}
353
354/* Find the pixel value corresponding to an RGBA quadruple */
355Uint32 SDL_MapRGBA
356(const SDL_PixelFormat * const format,
357 const Uint8 r, const Uint8 g, const Uint8 b, const Uint8 a)
358{
359	if ( format->palette == NULL ) {
360	        return (r >> format->Rloss) << format->Rshift
361		    | (g >> format->Gloss) << format->Gshift
362		    | (b >> format->Bloss) << format->Bshift
363		    | ((a >> format->Aloss) << format->Ashift & format->Amask);
364	} else {
365		return SDL_FindColor(format->palette, r, g, b);
366	}
367}
368
369void SDL_GetRGBA(Uint32 pixel, SDL_PixelFormat *fmt,
370		 Uint8 *r, Uint8 *g, Uint8 *b, Uint8 *a)
371{
372	if ( fmt->palette == NULL ) {
373	        /*
374		 * This makes sure that the result is mapped to the
375		 * interval [0..255], and the maximum value for each
376		 * component is 255. This is important to make sure
377		 * that white is indeed reported as (255, 255, 255),
378		 * and that opaque alpha is 255.
379		 * This only works for RGB bit fields at least 4 bit
380		 * wide, which is almost always the case.
381		 */
382	        unsigned v;
383		v = (pixel & fmt->Rmask) >> fmt->Rshift;
384		*r = (v << fmt->Rloss) + (v >> (8 - (fmt->Rloss << 1)));
385		v = (pixel & fmt->Gmask) >> fmt->Gshift;
386		*g = (v << fmt->Gloss) + (v >> (8 - (fmt->Gloss << 1)));
387		v = (pixel & fmt->Bmask) >> fmt->Bshift;
388		*b = (v << fmt->Bloss) + (v >> (8 - (fmt->Bloss << 1)));
389		if(fmt->Amask) {
390		        v = (pixel & fmt->Amask) >> fmt->Ashift;
391			*a = (v << fmt->Aloss) + (v >> (8 - (fmt->Aloss << 1)));
392		} else {
393		        *a = SDL_ALPHA_OPAQUE;
394                }
395	} else {
396		*r = fmt->palette->colors[pixel].r;
397		*g = fmt->palette->colors[pixel].g;
398		*b = fmt->palette->colors[pixel].b;
399		*a = SDL_ALPHA_OPAQUE;
400	}
401}
402
403void SDL_GetRGB(Uint32 pixel, SDL_PixelFormat *fmt, Uint8 *r,Uint8 *g,Uint8 *b)
404{
405	if ( fmt->palette == NULL ) {
406	        /* the note for SDL_GetRGBA above applies here too */
407	        unsigned v;
408		v = (pixel & fmt->Rmask) >> fmt->Rshift;
409		*r = (v << fmt->Rloss) + (v >> (8 - (fmt->Rloss << 1)));
410		v = (pixel & fmt->Gmask) >> fmt->Gshift;
411		*g = (v << fmt->Gloss) + (v >> (8 - (fmt->Gloss << 1)));
412		v = (pixel & fmt->Bmask) >> fmt->Bshift;
413		*b = (v << fmt->Bloss) + (v >> (8 - (fmt->Bloss << 1)));
414	} else {
415		*r = fmt->palette->colors[pixel].r;
416		*g = fmt->palette->colors[pixel].g;
417		*b = fmt->palette->colors[pixel].b;
418	}
419}
420
421/* Apply gamma to a set of colors - this is easy. :) */
422void SDL_ApplyGamma(Uint16 *gamma, SDL_Color *colors, SDL_Color *output,
423							int ncolors)
424{
425	int i;
426
427	for ( i=0; i<ncolors; ++i ) {
428		output[i].r = gamma[0*256 + colors[i].r] >> 8;
429		output[i].g = gamma[1*256 + colors[i].g] >> 8;
430		output[i].b = gamma[2*256 + colors[i].b] >> 8;
431	}
432}
433
434/* Map from Palette to Palette */
435static Uint8 *Map1to1(SDL_Palette *src, SDL_Palette *dst, int *identical)
436{
437	Uint8 *map;
438	int i;
439
440	if ( identical ) {
441		if ( src->ncolors <= dst->ncolors ) {
442			/* If an identical palette, no need to map */
443			if ( SDL_memcmp(src->colors, dst->colors, src->ncolors*
444						sizeof(SDL_Color)) == 0 ) {
445				*identical = 1;
446				return(NULL);
447			}
448		}
449		*identical = 0;
450	}
451	map = (Uint8 *)SDL_malloc(src->ncolors);
452	if ( map == NULL ) {
453		SDL_OutOfMemory();
454		return(NULL);
455	}
456	for ( i=0; i<src->ncolors; ++i ) {
457		map[i] = SDL_FindColor(dst,
458			src->colors[i].r, src->colors[i].g, src->colors[i].b);
459	}
460	return(map);
461}
462/* Map from Palette to BitField */
463static Uint8 *Map1toN(SDL_PixelFormat *src, SDL_PixelFormat *dst)
464{
465	Uint8 *map;
466	int i;
467	int  bpp;
468	unsigned alpha;
469	SDL_Palette *pal = src->palette;
470
471	bpp = ((dst->BytesPerPixel == 3) ? 4 : dst->BytesPerPixel);
472	map = (Uint8 *)SDL_malloc(pal->ncolors*bpp);
473	if ( map == NULL ) {
474		SDL_OutOfMemory();
475		return(NULL);
476	}
477
478	alpha = dst->Amask ? src->alpha : 0;
479	/* We memory copy to the pixel map so the endianness is preserved */
480	for ( i=0; i<pal->ncolors; ++i ) {
481		ASSEMBLE_RGBA(&map[i*bpp], dst->BytesPerPixel, dst,
482			      pal->colors[i].r, pal->colors[i].g,
483			      pal->colors[i].b, alpha);
484	}
485	return(map);
486}
487/* Map from BitField to Dithered-Palette to Palette */
488static Uint8 *MapNto1(SDL_PixelFormat *src, SDL_PixelFormat *dst, int *identical)
489{
490	/* Generate a 256 color dither palette */
491	SDL_Palette dithered;
492	SDL_Color colors[256];
493	SDL_Palette *pal = dst->palette;
494
495	/* SDL_DitherColors does not initialize the 'unused' component of colors,
496	   but Map1to1 compares it against pal, so we should initialize it. */
497	SDL_memset(colors, 0, sizeof(colors));
498
499	dithered.ncolors = 256;
500	SDL_DitherColors(colors, 8);
501	dithered.colors = colors;
502	return(Map1to1(&dithered, pal, identical));
503}
504
505SDL_BlitMap *SDL_AllocBlitMap(void)
506{
507	SDL_BlitMap *map;
508
509	/* Allocate the empty map */
510	map = (SDL_BlitMap *)SDL_malloc(sizeof(*map));
511	if ( map == NULL ) {
512		SDL_OutOfMemory();
513		return(NULL);
514	}
515	SDL_memset(map, 0, sizeof(*map));
516
517	/* Allocate the software blit data */
518	map->sw_data = (struct private_swaccel *)SDL_malloc(sizeof(*map->sw_data));
519	if ( map->sw_data == NULL ) {
520		SDL_FreeBlitMap(map);
521		SDL_OutOfMemory();
522		return(NULL);
523	}
524	SDL_memset(map->sw_data, 0, sizeof(*map->sw_data));
525
526	/* It's ready to go */
527	return(map);
528}
529void SDL_InvalidateMap(SDL_BlitMap *map)
530{
531	if ( ! map ) {
532		return;
533	}
534	map->dst = NULL;
535	map->format_version = (unsigned int)-1;
536	if ( map->table ) {
537		SDL_free(map->table);
538		map->table = NULL;
539	}
540}
541int SDL_MapSurface (SDL_Surface *src, SDL_Surface *dst)
542{
543	SDL_PixelFormat *srcfmt;
544	SDL_PixelFormat *dstfmt;
545	SDL_BlitMap *map;
546
547	/* Clear out any previous mapping */
548	map = src->map;
549	if ( (src->flags & SDL_RLEACCEL) == SDL_RLEACCEL ) {
550		SDL_UnRLESurface(src, 1);
551	}
552	SDL_InvalidateMap(map);
553
554	/* Figure out what kind of mapping we're doing */
555	map->identity = 0;
556	srcfmt = src->format;
557	dstfmt = dst->format;
558	switch (srcfmt->BytesPerPixel) {
559	    case 1:
560		switch (dstfmt->BytesPerPixel) {
561		    case 1:
562			/* Palette --> Palette */
563			/* If both SDL_HWSURFACE, assume have same palette */
564			if ( ((src->flags & SDL_HWSURFACE) == SDL_HWSURFACE) &&
565			     ((dst->flags & SDL_HWSURFACE) == SDL_HWSURFACE) ) {
566				map->identity = 1;
567			} else {
568				map->table = Map1to1(srcfmt->palette,
569					dstfmt->palette, &map->identity);
570			}
571			if ( ! map->identity ) {
572				if ( map->table == NULL ) {
573					return(-1);
574				}
575			}
576			if (srcfmt->BitsPerPixel!=dstfmt->BitsPerPixel)
577				map->identity = 0;
578			break;
579
580		    default:
581			/* Palette --> BitField */
582			map->table = Map1toN(srcfmt, dstfmt);
583			if ( map->table == NULL ) {
584				return(-1);
585			}
586			break;
587		}
588		break;
589	default:
590		switch (dstfmt->BytesPerPixel) {
591		    case 1:
592			/* BitField --> Palette */
593			map->table = MapNto1(srcfmt, dstfmt, &map->identity);
594			if ( ! map->identity ) {
595				if ( map->table == NULL ) {
596					return(-1);
597				}
598			}
599			map->identity = 0;	/* Don't optimize to copy */
600			break;
601		    default:
602			/* BitField --> BitField */
603			if ( FORMAT_EQUAL(srcfmt, dstfmt) )
604				map->identity = 1;
605			break;
606		}
607		break;
608	}
609
610	map->dst = dst;
611	map->format_version = dst->format_version;
612
613	/* Choose your blitters wisely */
614	return(SDL_CalculateBlit(src));
615}
616void SDL_FreeBlitMap(SDL_BlitMap *map)
617{
618	if ( map ) {
619		SDL_InvalidateMap(map);
620		if ( map->sw_data != NULL ) {
621			SDL_free(map->sw_data);
622		}
623		SDL_free(map);
624	}
625}
626