/*

    SDL - Simple DirectMedia Layer

    Copyright (C) 1997-2006 Sam Lantinga

    This library is free software; you can redistribute it and/or

    modify it under the terms of the GNU Lesser General Public

    License as published by the Free Software Foundation; either

    version 2.1 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

    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public

    License along with this library; if not, write to the Free Software

    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    Sam Lantinga

    slouken@libsdl.org

*/

#include "SDL_config.h"

/*

 * RLE encoding for software colorkey and alpha-channel acceleration

 *

 * Original version by Sam Lantinga

 *

 * Mattias Engdegård (Yorick): Rewrite. New encoding format, encoder and

 * decoder. Added per-surface alpha blitter. Added per-pixel alpha

 * format, encoder and blitter.

 *

 * Many thanks to Xark and johns for hints, benchmarks and useful comments

 * leading to this code.

 *

 * Welcome to Macro Mayhem.

 */

/*

 * The encoding translates the image data to a stream of segments of the form

 *

 * <skip> <run> <data>

 *

 * where <skip> is the number of transparent pixels to skip,

 *       <run>  is the number of opaque pixels to blit,

 * and   <data> are the pixels themselves.

 *

 * This basic structure is used both for colorkeyed surfaces, used for simple

 * binary transparency and for per-surface alpha blending, and for surfaces

 * with per-pixel alpha. The details differ, however:

 *

 * Encoding of colorkeyed surfaces:

 *

 *   Encoded pixels always have the same format as the target surface.

 *   <skip> and <run> are unsigned 8 bit integers, except for 32 bit depth

 *   where they are 16 bit. This makes the pixel data aligned at all times.

 *   Segments never wrap around from one scan line to the next.

 *

 *   The end of the sequence is marked by a zero <skip>,<run> pair at the *

 *   beginning of a line.

 *

 * Encoding of surfaces with per-pixel alpha:

 *

 *   The sequence begins with a struct RLEDestFormat describing the target

 *   pixel format, to provide reliable un-encoding.

 *

 *   Each scan line is encoded twice: First all completely opaque pixels,

 *   encoded in the target format as described above, and then all

 *   partially transparent (translucent) pixels (where 1 <= alpha <= 254),

 *   in the following 32-bit format:

 *

 *   For 32-bit targets, each pixel has the target RGB format but with

 *   the alpha value occupying the highest 8 bits. The <skip> and <run>

 *   counts are 16 bit.

 * 

 *   For 16-bit targets, each pixel has the target RGB format, but with

 *   the middle component (usually green) shifted 16 steps to the left,

 *   and the hole filled with the 5 most significant bits of the alpha value.

 *   i.e. if the target has the format         rrrrrggggggbbbbb,

 *   the encoded pixel will be 00000gggggg00000rrrrr0aaaaabbbbb.

 *   The <skip> and <run> counts are 8 bit for the opaque lines, 16 bit

 *   for the translucent lines. Two padding bytes may be inserted

 *   before each translucent line to keep them 32-bit aligned.

 *

 *   The end of the sequence is marked by a zero <skip>,<run> pair at the

 *   beginning of an opaque line.

 */

#include "SDL_video.h"

#include "SDL_sysvideo.h"

#include "SDL_blit.h"

#include "SDL_RLEaccel_c.h"

#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)) && SDL_ASSEMBLY_ROUTINES

#define MMX_ASMBLIT

#endif

#ifdef MMX_ASMBLIT

#include "mmx.h"

#include "SDL_cpuinfo.h"

#endif

#ifndef MAX

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#endif

#ifndef MIN

#define MIN(a, b) ((a) < (b) ? (a) : (b))

#endif

#define PIXEL_COPY(to, from, len, bpp)			\

do {							\

    if(bpp == 4) {					\

	SDL_memcpy4(to, from, (size_t)(len));		\

    } else {						\

	SDL_memcpy(to, from, (size_t)(len) * (bpp));	\

    }							\

} while(0)

/*

 * Various colorkey blit methods, for opaque and per-surface alpha

 */

#define OPAQUE_BLIT(to, from, length, bpp, alpha)	\

    PIXEL_COPY(to, from, length, bpp)

#ifdef MMX_ASMBLIT

#define ALPHA_BLIT32_888MMX(to, from, length, bpp, alpha)	\

    do {							\

	Uint32 *srcp = (Uint32 *)(from);			\

	Uint32 *dstp = (Uint32 *)(to);				\

        int i = 0x00FF00FF;					\

        movd_m2r(*(&i), mm3);					\

        punpckldq_r2r(mm3, mm3);				\

        i = 0xFF000000;						\

        movd_m2r(*(&i), mm7);					\

        punpckldq_r2r(mm7, mm7);				\

        i = alpha | alpha << 16;				\

        movd_m2r(*(&i), mm4);					\

        punpckldq_r2r(mm4, mm4);				\

	pcmpeqd_r2r(mm5,mm5); /* set mm5 to "1" */		\

	pxor_r2r(mm7, mm5); /* make clear alpha mask */		\

        i = length;						\

	if(i & 1) {						\

          movd_m2r((*srcp), mm1); /* src -> mm1 */		\

          punpcklbw_r2r(mm1, mm1);				\

          pand_r2r(mm3, mm1);					\

	  movd_m2r((*dstp), mm2); /* dst -> mm2 */		\

          punpcklbw_r2r(mm2, mm2);				\

          pand_r2r(mm3, mm2);					\

	  psubw_r2r(mm2, mm1);					\

	  pmullw_r2r(mm4, mm1);					\

	  psrlw_i2r(8, mm1);					\

	  paddw_r2r(mm1, mm2);					\

	  pand_r2r(mm3, mm2);					\

	  packuswb_r2r(mm2, mm2);				\

	  pand_r2r(mm5, mm2); /* 00000RGB -> mm2 */		\

	  movd_r2m(mm2, *dstp);					\

	  ++srcp;						\

	  ++dstp;						\

	  i--;							\

	}							\

	for(; i > 0; --i) {					\

          movq_m2r((*srcp), mm0);				\

	  movq_r2r(mm0, mm1);					\

          punpcklbw_r2r(mm0, mm0);				\

	  movq_m2r((*dstp), mm2);				\

	  punpckhbw_r2r(mm1, mm1);				\

	  movq_r2r(mm2, mm6);					\

          pand_r2r(mm3, mm0);					\

          punpcklbw_r2r(mm2, mm2);				\

	  pand_r2r(mm3, mm1);					\

	  punpckhbw_r2r(mm6, mm6);				\

          pand_r2r(mm3, mm2);					\

	  psubw_r2r(mm2, mm0);					\

	  pmullw_r2r(mm4, mm0);					\

	  pand_r2r(mm3, mm6);					\

	  psubw_r2r(mm6, mm1);					\

	  pmullw_r2r(mm4, mm1);					\

	  psrlw_i2r(8, mm0);					\

	  paddw_r2r(mm0, mm2);					\

	  psrlw_i2r(8, mm1);					\

	  paddw_r2r(mm1, mm6);					\

	  pand_r2r(mm3, mm2);					\

	  pand_r2r(mm3, mm6);					\

	  packuswb_r2r(mm2, mm2);				\

	  packuswb_r2r(mm6, mm6);				\

	  psrlq_i2r(32, mm2);					\

	  psllq_i2r(32, mm6);					\

	  por_r2r(mm6, mm2);					\

	  pand_r2r(mm5, mm2); /* 00000RGB -> mm2 */		\

         movq_r2m(mm2, *dstp);					\

	  srcp += 2;						\

	  dstp += 2;						\

	  i--;							\

	}							\

	emms();							\

    } while(0)

#define ALPHA_BLIT16_565MMX(to, from, length, bpp, alpha)	\

    do {						\

        int i, n = 0;					\

	Uint16 *srcp = (Uint16 *)(from);		\

	Uint16 *dstp = (Uint16 *)(to);			\

        Uint32 ALPHA = 0xF800;				\

	movd_m2r(*(&ALPHA), mm1);			\

        punpcklwd_r2r(mm1, mm1);			\

        punpcklwd_r2r(mm1, mm1);			\

	ALPHA = 0x07E0;					\

	movd_m2r(*(&ALPHA), mm4);			\

        punpcklwd_r2r(mm4, mm4);			\

        punpcklwd_r2r(mm4, mm4);			\

	ALPHA = 0x001F;					\

	movd_m2r(*(&ALPHA), mm7);			\

        punpcklwd_r2r(mm7, mm7);			\

        punpcklwd_r2r(mm7, mm7);			\

	alpha &= ~(1+2+4);				\

        i = (Uint32)alpha | (Uint32)alpha << 16;	\

        movd_m2r(*(&i), mm0);				\

        punpckldq_r2r(mm0, mm0);			\

        ALPHA = alpha >> 3;				\

        i = ((int)(length) & 3);			\

	for(; i > 0; --i) {				\

	    Uint32 s = *srcp++;				\

	    Uint32 d = *dstp;				\

	    s = (s | s << 16) & 0x07e0f81f;		\

	    d = (d | d << 16) & 0x07e0f81f;		\

	    d += (s - d) * ALPHA >> 5;			\

	    d &= 0x07e0f81f;				\

	    *dstp++ = d | d >> 16;			\

	    n++;					\

	}						\

	i = (int)(length) - n;				\

	for(; i > 0; --i) {				\

	  movq_m2r((*dstp), mm3);			\

	  movq_m2r((*srcp), mm2);			\

	  movq_r2r(mm2, mm5);				\

	  pand_r2r(mm1 , mm5);				\

	  psrlq_i2r(11, mm5);				\

	  movq_r2r(mm3, mm6);				\

	  pand_r2r(mm1 , mm6);				\

	  psrlq_i2r(11, mm6);				\

	  psubw_r2r(mm6, mm5);				\

	  pmullw_r2r(mm0, mm5);				\

	  psrlw_i2r(8, mm5);				\

	  paddw_r2r(mm5, mm6);				\

	  psllq_i2r(11, mm6);				\

	  pand_r2r(mm1, mm6);				\

	  movq_r2r(mm4, mm5);				\

	  por_r2r(mm7, mm5);				\

	  pand_r2r(mm5, mm3);				\

	  por_r2r(mm6, mm3);				\

	  movq_r2r(mm2, mm5);				\

	  pand_r2r(mm4 , mm5);				\

	  psrlq_i2r(5, mm5);				\

	  movq_r2r(mm3, mm6);				\

	  pand_r2r(mm4 , mm6);				\

	  psrlq_i2r(5, mm6);				\

	  psubw_r2r(mm6, mm5);				\

	  pmullw_r2r(mm0, mm5);				\

	  psrlw_i2r(8, mm5);				\

	  paddw_r2r(mm5, mm6);				\

	  psllq_i2r(5, mm6);				\

	  pand_r2r(mm4, mm6);				\

	  movq_r2r(mm1, mm5);				\

	  por_r2r(mm7, mm5);				\

	  pand_r2r(mm5, mm3);				\

	  por_r2r(mm6, mm3);				\

	  movq_r2r(mm2, mm5);				\

	  pand_r2r(mm7 , mm5);				\

          movq_r2r(mm3, mm6);				\

	  pand_r2r(mm7 , mm6);				\

	  psubw_r2r(mm6, mm5);				\

	  pmullw_r2r(mm0, mm5);				\

	  psrlw_i2r(8, mm5);				\

	  paddw_r2r(mm5, mm6);				\

	  pand_r2r(mm7, mm6);				\

	  movq_r2r(mm1, mm5);				\

	  por_r2r(mm4, mm5);				\

	  pand_r2r(mm5, mm3);				\

	  por_r2r(mm6, mm3);				\

	  movq_r2m(mm3, *dstp);				\

	  srcp += 4;					\

	  dstp += 4;					\

	  i -= 3;					\

	}						\

	emms();						\

    } while(0)

#define ALPHA_BLIT16_555MMX(to, from, length, bpp, alpha)	\

    do {						\

        int i, n = 0;					\

	Uint16 *srcp = (Uint16 *)(from);		\

	Uint16 *dstp = (Uint16 *)(to);			\

        Uint32 ALPHA = 0x7C00;				\

	movd_m2r(*(&ALPHA), mm1);			\

        punpcklwd_r2r(mm1, mm1);			\

        punpcklwd_r2r(mm1, mm1);			\

	ALPHA = 0x03E0;					\

        movd_m2r(*(&ALPHA), mm4);			\

        punpcklwd_r2r(mm4, mm4);			\

        punpcklwd_r2r(mm4, mm4);			\

	ALPHA = 0x001F;					\

	movd_m2r(*(&ALPHA), mm7);			\

        punpcklwd_r2r(mm7, mm7);			\

        punpcklwd_r2r(mm7, mm7);			\

	alpha &= ~(1+2+4);				\

        i = (Uint32)alpha | (Uint32)alpha << 16;	\

        movd_m2r(*(&i), mm0);				\

        punpckldq_r2r(mm0, mm0);			\

        i = ((int)(length) & 3);				\

        ALPHA = alpha >> 3;				\

	for(; i > 0; --i) {				\

	    Uint32 s = *srcp++;				\

	    Uint32 d = *dstp;				\

	    s = (s | s << 16) & 0x03e07c1f;		\

	    d = (d | d << 16) & 0x03e07c1f;		\

	    d += (s - d) * ALPHA >> 5;			\

	    d &= 0x03e07c1f;				\

	    *dstp++ = d | d >> 16;			\

	    n++;					\

	}						\

	i = (int)(length) - n;				\

	for(; i > 0; --i) {				\

	  movq_m2r((*dstp), mm3);			\

	  movq_m2r((*srcp), mm2);			\

	  movq_r2r(mm2, mm5);				\

	  pand_r2r(mm1 , mm5);				\

	  psrlq_i2r(10, mm5);				\

	  movq_r2r(mm3, mm6);				\

	  pand_r2r(mm1 , mm6);				\

	  psrlq_i2r(10, mm6);				\

	  psubw_r2r(mm6, mm5);				\

	  pmullw_r2r(mm0, mm5);				\

	  psrlw_i2r(8, mm5);				\

	  paddw_r2r(mm5, mm6);				\

	  psllq_i2r(10, mm6);				\

	  pand_r2r(mm1, mm6);				\

	  movq_r2r(mm4, mm5);				\

	  por_r2r(mm7, mm5);				\

	  pand_r2r(mm5, mm3);				\

	  por_r2r(mm6, mm3);				\

	  movq_r2r(mm2, mm5);				\

	  pand_r2r(mm4 , mm5);				\

	  psrlq_i2r(5, mm5);				\

	  movq_r2r(mm3, mm6);				\

	  pand_r2r(mm4 , mm6);				\

	  psrlq_i2r(5, mm6);				\

	  psubw_r2r(mm6, mm5);				\

	  pmullw_r2r(mm0, mm5);				\

	  psrlw_i2r(8, mm5);				\

	  paddw_r2r(mm5, mm6);				\

	  psllq_i2r(5, mm6);				\

	  pand_r2r(mm4, mm6);				\

	  movq_r2r(mm1, mm5);				\

	  por_r2r(mm7, mm5);				\

	  pand_r2r(mm5, mm3);				\

	  por_r2r(mm6, mm3);				\

	  movq_r2r(mm2, mm5);				\

	  pand_r2r(mm7 , mm5);				\

          movq_r2r(mm3, mm6);				\

	  pand_r2r(mm7 , mm6);				\

	  psubw_r2r(mm6, mm5);				\

	  pmullw_r2r(mm0, mm5);				\

	  psrlw_i2r(8, mm5);				\

	  paddw_r2r(mm5, mm6);				\

	  pand_r2r(mm7, mm6);				\

	  movq_r2r(mm1, mm5);				\

	  por_r2r(mm4, mm5);				\

	  pand_r2r(mm5, mm3);				\

	  por_r2r(mm6, mm3);				\

	  movq_r2m(mm3, *dstp);				\

	  srcp += 4;					\

	  dstp += 4;					\

	  i -= 3;					\

	}						\

	emms();						\

    } while(0)

#endif

/*

 * For 32bpp pixels on the form 0x00rrggbb:

 * If we treat the middle component separately, we can process the two

 * remaining in parallel. This is safe to do because of the gap to the left

 * of each component, so the bits from the multiplication don't collide.

 * This can be used for any RGB permutation of course.

 */

#define ALPHA_BLIT32_888(to, from, length, bpp, alpha)		\

    do {							\

        int i;							\

	Uint32 *src = (Uint32 *)(from);				\

	Uint32 *dst = (Uint32 *)(to);				\

	for(i = 0; i < (int)(length); i++) {			\

	    Uint32 s = *src++;					\

	    Uint32 d = *dst;					\

	    Uint32 s1 = s & 0xff00ff;				\

	    Uint32 d1 = d & 0xff00ff;				\

	    d1 = (d1 + ((s1 - d1) * alpha >> 8)) & 0xff00ff;	\

	    s &= 0xff00;					\

	    d &= 0xff00;					\

	    d = (d + ((s - d) * alpha >> 8)) & 0xff00;		\

	    *dst++ = d1 | d;					\

	}							\

    } while(0)

/*

 * For 16bpp pixels we can go a step further: put the middle component

 * in the high 16 bits of a 32 bit word, and process all three RGB

 * components at the same time. Since the smallest gap is here just

 * 5 bits, we have to scale alpha down to 5 bits as well.

 */

#define ALPHA_BLIT16_565(to, from, length, bpp, alpha)	\

    do {						\

        int i;						\

	Uint16 *src = (Uint16 *)(from);			\

	Uint16 *dst = (Uint16 *)(to);			\

	Uint32 ALPHA = alpha >> 3;			\

	for(i = 0; i < (int)(length); i++) {		\

	    Uint32 s = *src++;				\

	    Uint32 d = *dst;				\

	    s = (s | s << 16) & 0x07e0f81f;		\

	    d = (d | d << 16) & 0x07e0f81f;		\

	    d += (s - d) * ALPHA >> 5;			\

	    d &= 0x07e0f81f;				\

	    *dst++ = (Uint16)(d | d >> 16);			\

	}						\

    } while(0)

#define ALPHA_BLIT16_555(to, from, length, bpp, alpha)	\

    do {						\

        int i;						\

	Uint16 *src = (Uint16 *)(from);			\

	Uint16 *dst = (Uint16 *)(to);			\

	Uint32 ALPHA = alpha >> 3;			\

	for(i = 0; i < (int)(length); i++) {		\

	    Uint32 s = *src++;				\

	    Uint32 d = *dst;				\

	    s = (s | s << 16) & 0x03e07c1f;		\

	    d = (d | d << 16) & 0x03e07c1f;		\

	    d += (s - d) * ALPHA >> 5;			\

	    d &= 0x03e07c1f;				\

	    *dst++ = (Uint16)(d | d >> 16);			\

	}						\

    } while(0)

/*

 * The general slow catch-all function, for remaining depths and formats

 */

#define ALPHA_BLIT_ANY(to, from, length, bpp, alpha)			\

    do {								\

        int i;								\

	Uint8 *src = from;						\

	Uint8 *dst = to;						\

	for(i = 0; i < (int)(length); i++) {				\

	    Uint32 s, d;						\

	    unsigned rs, gs, bs, rd, gd, bd;				\

	    switch(bpp) {						\

	    case 2:							\

		s = *(Uint16 *)src;					\

		d = *(Uint16 *)dst;					\

		break;							\

	    case 3:							\

		if(SDL_BYTEORDER == SDL_BIG_ENDIAN) {			\

		    s = (src[0] << 16) | (src[1] << 8) | src[2];	\

		    d = (dst[0] << 16) | (dst[1] << 8) | dst[2];	\

		} else {						\

		    s = (src[2] << 16) | (src[1] << 8) | src[0];	\

		    d = (dst[2] << 16) | (dst[1] << 8) | dst[0];	\

		}							\

		break;							\

	    case 4:							\

		s = *(Uint32 *)src;					\

		d = *(Uint32 *)dst;					\

		break;							\

	    }								\

	    RGB_FROM_PIXEL(s, fmt, rs, gs, bs);				\

	    RGB_FROM_PIXEL(d, fmt, rd, gd, bd);				\

	    rd += (rs - rd) * alpha >> 8;				\

	    gd += (gs - gd) * alpha >> 8;				\

	    bd += (bs - bd) * alpha >> 8;				\

	    PIXEL_FROM_RGB(d, fmt, rd, gd, bd);				\

	    switch(bpp) {						\

	    case 2:							\

		*(Uint16 *)dst = (Uint16)d;					\

		break;							\

	    case 3:							\

		if(SDL_BYTEORDER == SDL_BIG_ENDIAN) {			\

		    dst[0] = (Uint8)(d >> 16);					\

		    dst[1] = (Uint8)(d >> 8);					\

		    dst[2] = (Uint8)(d);						\

		} else {						\

		    dst[0] = (Uint8)d;						\

		    dst[1] = (Uint8)(d >> 8);					\

		    dst[2] = (Uint8)(d >> 16);					\

		}							\

		break;							\

	    case 4:							\

		*(Uint32 *)dst = d;					\

		break;							\

	    }								\

	    src += bpp;							\

	    dst += bpp;							\

	}								\

    } while(0)

#ifdef MMX_ASMBLIT

#define ALPHA_BLIT32_888_50MMX(to, from, length, bpp, alpha)		\

    do {								\

	Uint32 *srcp = (Uint32 *)(from);				\

	Uint32 *dstp = (Uint32 *)(to);					\

        int i = 0x00fefefe;						\

        movd_m2r(*(&i), mm4);						\

        punpckldq_r2r(mm4, mm4);					\

        i = 0x00010101;							\

        movd_m2r(*(&i), mm3);						\

        punpckldq_r2r(mm3, mm3);					\

        i = (int)(length);						\

        if( i & 1 ) {							\

	  Uint32 s = *srcp++;						\

	  Uint32 d = *dstp;						\

	  *dstp++ = (((s & 0x00fefefe) + (d & 0x00fefefe)) >> 1)	\

		     + (s & d & 0x00010101);				\

	  i--;								\

	}								\

	for(; i > 0; --i) {						\

	    movq_m2r((*dstp), mm2); /* dst -> mm2 */			\