/*
    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 */			\
	    movq_r2r(mm2, mm6);	/* dst -> mm6 */			\
	    movq_m2r((*srcp), mm1); /* src -> mm1 */			\
	    movq_r2r(mm1, mm5);	/* src -> mm5 */			\
	    pand_r2r(mm4, mm6);	/* dst & 0x00fefefe -> mm6 */		\
	    pand_r2r(mm4, mm5); /* src & 0x00fefefe -> mm5 */		\
	    paddd_r2r(mm6, mm5); /* (dst & 0x00fefefe) + (dst & 0x00fefefe) -> mm5 */	\
	    psrld_i2r(1, mm5);						\
	    pand_r2r(mm1, mm2);	/* s & d -> mm2 */			\
	    pand_r2r(mm3, mm2);	/* s & d & 0x00010101 -> mm2 */		\
	    paddd_r2r(mm5, mm2);					\
	    movq_r2m(mm2, (*dstp));					\
	    dstp += 2;							\
	    srcp += 2;							\
	    i--;							\
	}								\
	emms();								\
    } while(0)

#endif

/*
 * Special case: 50% alpha (alpha=128)
 * This is treated specially because it can be optimized very well, and
 * since it is good for many cases of semi-translucency.
 * The theory is to do all three components at the same time:
 * First zero the lowest bit of each component, which gives us room to
 * add them. Then shift right and add the sum of the lowest bits.
 */
#define ALPHA_BLIT32_888_50(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;						\
	    *dst++ = (((s & 0x00fefefe) + (d & 0x00fefefe)) >> 1)	\
		     + (s & d & 0x00010101);				\
	}								\
    } while(0)

/*
 * For 16bpp, we can actually blend two pixels in parallel, if we take
 * care to shift before we add, not after.
 */

/* helper: blend a single 16 bit pixel at 50% */
#define BLEND16_50(dst, src, mask)			\
    do {						\
	Uint32 s = *src++;				\
	Uint32 d = *dst;				\
	*dst++ = (Uint16)((((s & mask) + (d & mask)) >> 1) +	\
	                  (s & d & (~mask & 0xffff)));		\
    } while(0)

/* basic 16bpp blender. mask is the pixels to keep when adding. */
#define ALPHA_BLIT16_50(to, from, length, bpp, alpha, mask)		\
    do {								\
	unsigned n = (length);						\
	Uint16 *src = (Uint16 *)(from);					\
	Uint16 *dst = (Uint16 *)(to);					\
	if(((uintptr_t)src ^ (uintptr_t)dst) & 3) {			\
	    /* source and destination not in phase, blit one by one */	\
	    while(n--)							\
		BLEND16_50(dst, src, mask);				\
	} else {							\
	    if((uintptr_t)src & 3) {					\
		/* first odd pixel */					\
		BLEND16_50(dst, src, mask);				\
		n--;							\
	    }								\
	    for(; n > 1; n -= 2) {					\
		Uint32 s = *(Uint32 *)src;				\
		Uint32 d = *(Uint32 *)dst;				\
		*(Uint32 *)dst = ((s & (mask | mask << 16)) >> 1)	\
		               + ((d & (mask | mask << 16)) >> 1)	\
		               + (s & d & (~(mask | mask << 16)));	\
		src += 2;						\
		dst += 2;						\
	    }								\
	    if(n)							\
		BLEND16_50(dst, src, mask); /* last odd pixel */	\
	}								\
    } while(0)

#define ALPHA_BLIT16_565_50(to, from, length, bpp, alpha)	\
    ALPHA_BLIT16_50(to, from, length, bpp, alpha, 0xf7de)

#define ALPHA_BLIT16_555_50(to, from, length, bpp, alpha)	\
    ALPHA_BLIT16_50(to, from, length, bpp, alpha, 0xfbde)

#ifdef MMX_ASMBLIT

#define CHOOSE_BLIT(blitter, alpha, fmt)				\
    do {								\
        if(alpha == 255) {						\
	    switch(fmt->BytesPerPixel) {				\
	    case 1: blitter(1, Uint8, OPAQUE_BLIT); break;		\
	    case 2: blitter(2, Uint8, OPAQUE_BLIT); break;		\
	    case 3: blitter(3, Uint8, OPAQUE_BLIT); break;		\
	    case 4: blitter(4, Uint16, OPAQUE_BLIT); break;		\
	    }								\
	} else {							\
	    switch(fmt->BytesPerPixel) {				\
	    case 1:							\
		/* No 8bpp alpha blitting */				\
		break;							\
									\
	    case 2:							\
		switch(fmt->Rmask | fmt->Gmask | fmt->Bmask) {		\
		case 0xffff:						\
		    if(fmt->Gmask == 0x07e0				\
		       || fmt->Rmask == 0x07e0				\
		       || fmt->Bmask == 0x07e0) {			\
			if(alpha == 128)				\
			    blitter(2, Uint8, ALPHA_BLIT16_565_50);	\
			else {						\
			    if(SDL_HasMMX())				\
				blitter(2, Uint8, ALPHA_BLIT16_565MMX);	\
			    else					\
				blitter(2, Uint8, ALPHA_BLIT16_565);	\
			}						\
		    } else						\
			goto general16;					\
		    break;						\
									\
		case 0x7fff:						\
		    if(fmt->Gmask == 0x03e0				\
		       || fmt->Rmask == 0x03e0				\
		       || fmt->Bmask == 0x03e0) {			\
			if(alpha == 128)				\
			    blitter(2, Uint8, ALPHA_BLIT16_555_50);	\
			else {						\
			    if(SDL_HasMMX())				\
				blitter(2, Uint8, ALPHA_BLIT16_555MMX);	\
			    else					\
				blitter(2, Uint8, ALPHA_BLIT16_555);	\
			}						\
			break;						\
		    }							\
		    /* fallthrough */					\
									\
		default:						\
		general16:						\
		    blitter(2, Uint8, ALPHA_BLIT_ANY);			\
		}							\
		break;							\
									\
	    case 3:							\
		blitter(3, Uint8, ALPHA_BLIT_ANY);			\
		break;							\
									\
	    case 4:							\
		if((fmt->Rmask | fmt->Gmask | fmt->Bmask) == 0x00ffffff	\
		   && (fmt->Gmask == 0xff00 || fmt->Rmask == 0xff00	\
		       || fmt->Bmask == 0xff00)) {			\
		    if(alpha == 128)					\
		    {							\
			if(SDL_HasMMX())				\
				blitter(4, Uint16, ALPHA_BLIT32_888_50MMX);\
			else						\
				blitter(4, Uint16, ALPHA_BLIT32_888_50);\
		    }							\
		    else						\
		    {							\
			if(SDL_HasMMX())				\
				blitter(4, Uint16, ALPHA_BLIT32_888MMX);\
			else						\
				blitter(4, Uint16, ALPHA_BLIT32_888);	\
		    }							\
		} else							\
		    blitter(4, Uint16, ALPHA_BLIT_ANY);			\
		break;							\
	    }								\
	}								\
    } while(0)

#else

#define CHOOSE_BLIT(blitter, alpha, fmt)				\
    do {								\
        if(alpha == 255) {						\
	    switch(fmt->BytesPerPixel) {				\
	    case 1: blitter(1, Uint8, OPAQUE_BLIT); break;		\
	    case 2: blitter(2, Uint8, OPAQUE_BLIT); break;		\
	    case 3: blitter(3, Uint8, OPAQUE_BLIT); break;		\
	    case 4: blitter(4, Uint16, OPAQUE_BLIT); break;		\
	    }								\
	} else {							\
	    switch(fmt->BytesPerPixel) {				\
	    case 1:							\
		/* No 8bpp alpha blitting */				\
		break;							\
									\
	    case 2:							\
		switch(fmt->Rmask | fmt->Gmask | fmt->Bmask) {		\
		case 0xffff:						\
		    if(fmt->Gmask == 0x07e0				\
		       || fmt->Rmask == 0x07e0				\
		       || fmt->Bmask == 0x07e0) {			\
			if(alpha == 128)				\
			    blitter(2, Uint8, ALPHA_BLIT16_565_50);	\
			else {						\
			    blitter(2, Uint8, ALPHA_BLIT16_565);	\
			}						\
		    } else						\
			goto general16;					\
		    break;						\
									\
		case 0x7fff:						\
		    if(fmt->Gmask == 0x03e0				\
		       || fmt->Rmask == 0x03e0				\
		       || fmt->Bmask == 0x03e0) {			\
			if(alpha == 128)				\
			    blitter(2, Uint8, ALPHA_BLIT16_555_50);	\
			else {						\
			    blitter(2, Uint8, ALPHA_BLIT16_555);	\
			}						\
			break;						\
		    }							\
		    /* fallthrough */					\
									\
		default:						\
		general16:						\
		    blitter(2, Uint8, ALPHA_BLIT_ANY);			\
		}							\
		break;							\
									\
	    case 3:							\
		blitter(3, Uint8, ALPHA_BLIT_ANY);			\
		break;							\
									\
	    case 4:							\
		if((fmt->Rmask | fmt->Gmask | fmt->Bmask) == 0x00ffffff	\
		   && (fmt->Gmask == 0xff00 || fmt->Rmask == 0xff00	\
		       || fmt->Bmask == 0xff00)) {			\
		    if(alpha == 128)					\
			blitter(4, Uint16, ALPHA_BLIT32_888_50);	\
		    else						\
			blitter(4, Uint16, ALPHA_BLIT32_888);		\
		} else							\
		    blitter(4, Uint16, ALPHA_BLIT_ANY);			\
		break;							\
	    }								\
	}								\
    } while(0)

#endif

/*
 * This takes care of the case when the surface is clipped on the left and/or
 * right. Top clipping has already been taken care of.
 */
static void
RLEClipBlit(int w, Uint8 * srcbuf, SDL_Surface * dst,
            Uint8 * dstbuf, SDL_Rect * srcrect, unsigned alpha)
{
    SDL_PixelFormat *fmt = dst->format;

#define RLECLIPBLIT(bpp, Type, do_blit)					   \
    do {								   \
	int linecount = srcrect->h;					   \
	int ofs = 0;							   \
	int left = srcrect->x;						   \
	int right = left + srcrect->w;					   \
	dstbuf -= left * bpp;						   \
	for(;;) {							   \
	    int run;							   \
	    ofs += *(Type *)srcbuf;					   \
	    run = ((Type *)srcbuf)[1];					   \
	    srcbuf += 2 * sizeof(Type);					   \
	    if(run) {							   \
		/* clip to left and right borders */			   \
		if(ofs < right) {					   \
		    int start = 0;					   \
		    int len = run;					   \
		    int startcol;					   \
		    if(left - ofs > 0) {				   \
			start = left - ofs;				   \
			len -= start;					   \
			if(len <= 0)					   \
			    goto nocopy ## bpp ## do_blit;		   \
		    }							   \
		    startcol = ofs + start;				   \
		    if(len > right - startcol)				   \
			len = right - startcol;				   \
		    do_blit(dstbuf + startcol * bpp, srcbuf + start * bpp, \
			    len, bpp, alpha);				   \
		}							   \
	    nocopy ## bpp ## do_blit:					   \
		srcbuf += run * bpp;					   \
		ofs += run;						   \
	    } else if(!ofs)						   \
		break;							   \
	    if(ofs == w) {						   \
		ofs = 0;						   \
		dstbuf += dst->pitch;					   \
		if(!--linecount)					   \
		    break;						   \
	    }								   \
	}								   \
    } while(0)

    CHOOSE_BLIT(RLECLIPBLIT, alpha, fmt);

#undef RLECLIPBLIT

}


/* blit a colorkeyed RLE surface */
int
SDL_RLEBlit(SDL_Surface * src, SDL_Rect * srcrect,
            SDL_Surface * dst, SDL_Rect * dstrect)
{
    Uint8 *dstbuf;
    Uint8 *srcbuf;
    int x, y;
    int w = src->w;
    unsigned alpha;

    /* Lock the destination if necessary */
    if (SDL_MUSTLOCK(dst)) {
        if (SDL_LockSurface(dst) < 0) {
            return (-1);
        }
    }

    /* Set up the source and destination pointers */
    x = dstrect->x;
    y = dstrect->y;
    dstbuf = (Uint8 *) dst->pixels
        + y * dst->pitch + x * src->format->BytesPerPixel;
    srcbuf = (Uint8 *) src->map->data;

    {
        /* skip lines at the top if neccessary */
        int vskip = srcrect->y;
        int ofs = 0;
        if (vskip) {

#define RLESKIP(bpp, Type)			\
		for(;;) {			\
		    int run;			\
		    ofs += *(Type *)srcbuf;	\
		    run = ((Type *)srcbuf)[1];	\
		    srcbuf += sizeof(Type) * 2;	\
		    if(run) {			\
			srcbuf += run * bpp;	\
			ofs += run;		\
		    } else if(!ofs)		\
			goto done;		\
		    if(ofs == w) {		\
			ofs = 0;		\
			if(!--vskip)		\
			    break;		\
		    }				\
		}

            switch (src->format->BytesPerPixel) {
            case 1:
                RLESKIP(1, Uint8);
                break;
            case 2:
                RLESKIP(2, Uint8);
                break;
            case 3:
                RLESKIP(3, Uint8);
                break;
            case 4:
                RLESKIP(4, Uint16);
                break;
            }

#undef RLESKIP

        }
    }

    alpha = src->map->info.a;
    /* if left or right edge clipping needed, call clip blit */
    if (srcrect->x || srcrect->w != src->w) {
        RLEClipBlit(w, srcbuf, dst, dstbuf, srcrect, alpha);
    } else {
        SDL_PixelFormat *fmt = src->format;

#define RLEBLIT(bpp, Type, do_blit)					      \
	    do {							      \
		int linecount = srcrect->h;				      \
		int ofs = 0;						      \
		for(;;) {						      \
		    unsigned run;					      \
		    ofs += *(Type *)srcbuf;				      \
		    run = ((Type *)srcbuf)[1];				      \
		    srcbuf += 2 * sizeof(Type);				      \
		    if(run) {						      \
			do_blit(dstbuf + ofs * bpp, srcbuf, run, bpp, alpha); \
			srcbuf += run * bpp;				      \
			ofs += run;					      \
		    } else if(!ofs)					      \
			break;						      \
		    if(ofs == w) {					      \
			ofs = 0;					      \
			dstbuf += dst->pitch;				      \
			if(!--linecount)				      \
			    break;					      \
		    }							      \
		}							      \
	    } while(0)

        CHOOSE_BLIT(RLEBLIT, alpha, fmt);

#undef RLEBLIT
    }

  done:
    /* Unlock the destination if necessary */
    if (SDL_MUSTLOCK(dst)) {
        SDL_UnlockSurface(dst);
    }
    return (0);
}

#undef OPAQUE_BLIT

/*
 * Per-pixel blitting macros for translucent pixels:
 * These use the same techniques as the per-surface blitting macros
 */

/*
 * For 32bpp pixels, we have made sure the alpha is stored in the top
 * 8 bits, so proceed as usual
 */
#define BLIT_TRANSL_888(src, dst)				\
    do {							\
        Uint32 s = src;						\
	Uint32 d = dst;						\
	unsigned alpha = s >> 24;				\
	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 have stored the 5 most significant alpha bits in
 * bits 5-10. As before, we can process all 3 RGB components at the same time.
 */
#define BLIT_TRANSL_565(src, dst)		\
    do {					\
	Uint32 s = src;				\
	Uint32 d = dst;				\
	unsigned alpha = (s & 0x3e0) >> 5;	\
	s &= 0x07e0f81f;			\
	d = (d | d << 16) & 0x07e0f81f;		\
	d += (s - d) * alpha >> 5;		\
	d &= 0x07e0f81f;			\
	dst = (Uint16)(d | d >> 16);			\
    } while(0)

#define BLIT_TRANSL_555(src, dst)		\
    do {					\
	Uint32 s = src;				\
	Uint32 d = dst;				\
	unsigned alpha = (s & 0x3e0) >> 5;	\
	s &= 0x03e07c1f;			\
	d = (d | d << 16) & 0x03e07c1f;		\
	d += (s - d) * alpha >> 5;		\
	d &= 0x03e07c1f;			\
	dst = (Uint16)(d | d >> 16);			\
    } while(0)

/* used to save the destination format in the encoding. Designed to be
   macro-compatible with SDL_PixelFormat but without the unneeded fields */
typedef struct
{
    Uint8 BytesPerPixel;
    Uint8 Rloss;
    Uint8 Gloss;
    Uint8 Bloss;
    Uint8 Rshift;
    Uint8 Gshift;
    Uint8 Bshift;
    Uint8 Ashift;
    Uint32 Rmask;
    Uint32 Gmask;
    Uint32 Bmask;
    Uint32 Amask;
} RLEDestFormat;

/* blit a pixel-alpha RLE surface clipped at the right and/or left edges */
static void
RLEAlphaClipBlit(int w, Uint8 * srcbuf, SDL_Surface * dst,
                 Uint8 * dstbuf, SDL_Rect * srcrect)
{
    SDL_PixelFormat *df = dst->format;
    /*
     * clipped blitter: Ptype is the destination pixel type,
     * Ctype the translucent count type, and do_blend the macro
     * to blend one pixel.
     */
#define RLEALPHACLIPBLIT(Ptype, Ctype, do_blend)			  \
    do {								  \
	int linecount = srcrect->h;					  \
	int left = srcrect->x;						  \
	int right = left + srcrect->w;					  \
	dstbuf -= left * sizeof(Ptype);					  \
	do {								  \
	    int ofs = 0;						  \
	    /* blit opaque pixels on one line */			  \
	    do {							  \
		unsigned run;						  \
		ofs += ((Ctype *)srcbuf)[0];				  \
		run = ((Ctype *)srcbuf)[1];				  \
		srcbuf += 2 * sizeof(Ctype);				  \
		if(run) {						  \
		    /* clip to left and right borders */		  \
		    int cofs = ofs;					  \
		    int crun = run;					  \
		    if(left - cofs > 0) {				  \
			crun -= left - cofs;				  \
			cofs = left;					  \
		    }							  \
		    if(crun > right - cofs)				  \
			crun = right - cofs;				  \
		    if(crun > 0)					  \
			PIXEL_COPY(dstbuf + cofs * sizeof(Ptype),	  \
				   srcbuf + (cofs - ofs) * sizeof(Ptype), \
				   (unsigned)crun, sizeof(Ptype));	  \
		    srcbuf += run * sizeof(Ptype);			  \
		    ofs += run;						  \
		} else if(!ofs)						  \
		    return;						  \
	    } while(ofs < w);						  \
	    /* skip padding if necessary */				  \
	    if(sizeof(Ptype) == 2)					  \
		srcbuf += (uintptr_t)srcbuf & 2;			  \
	    /* blit translucent pixels on the same line */		  \
	    ofs = 0;							  \
	    do {							  \
		unsigned run;						  \
		ofs += ((Uint16 *)srcbuf)[0];				  \
		run = ((Uint16 *)srcbuf)[1];				  \
		srcbuf += 4;						  \
		if(run) {						  \
		    /* clip to left and right borders */		  \
		    int cofs = ofs;					  \
		    int crun = run;					  \
		    if(left - cofs > 0) {				  \
			crun -= left - cofs;				  \
			cofs = left;					  \
		    }							  \
		    if(crun > right - cofs)				  \
			crun = right - cofs;				  \
		    if(crun > 0) {					  \
			Ptype *dst = (Ptype *)dstbuf + cofs;		  \
			Uint32 *src = (Uint32 *)srcbuf + (cofs - ofs);	  \
			int i;						  \
			for(i = 0; i < crun; i++)			  \
			    do_blend(src[i], dst[i]);			  \
		    }							  \
		    srcbuf += run * 4;					  \
		    ofs += run;						  \
		}							  \
	    } while(ofs < w);						  \
	    dstbuf += dst->pitch;					  \
	} while(--linecount);						  \
    } while(0)

    switch (df->BytesPerPixel) {
    case 2:
        if (df->Gmask == 0x07e0 || df->Rmask == 0x07e0 || df->Bmask == 0x07e0)
            RLEALPHACLIPBLIT(Uint16, Uint8, BLIT_TRANSL_565);
        else
            RLEALPHACLIPBLIT(Uint16, Uint8, BLIT_TRANSL_555);
        break;
    case 4:
        RLEALPHACLIPBLIT(Uint32, Uint16, BLIT_TRANSL_888);
        break;
    }
}

/* blit a pixel-alpha RLE surface */
int
SDL_RLEAlphaBlit(SDL_Surface * src, SDL_Rect * srcrect,
                 SDL_Surface * dst, SDL_Rect * dstrect)
{
    int x, y;
    int w = src->w;
    Uint8 *srcbuf, *dstbuf;
    SDL_PixelFormat *df = dst->format;

    /* Lock the destination if necessary */
    if (SDL_MUSTLOCK(dst)) {
        if (SDL_LockSurface(dst) < 0) {
            return -1;
        }
    }

    x = dstrect->x;
    y = dstrect->y;
    dstbuf = (Uint8 *) dst->pixels + y * dst->pitch + x * df->BytesPerPixel;
    srcbuf = (Uint8 *) src->map->data + sizeof(RLEDestFormat);

    {
        /* skip lines at the top if necessary */
        int vskip = srcrect->y;
        if (vskip) {
            int ofs;
            if (df->BytesPerPixel == 2) {
                /* the 16/32 interleaved format */
                do {
                    /* skip opaque line */
                    ofs = 0;
                    do {
                        int run;
                        ofs += srcbuf[0];
                        run = srcbuf[1];
                        srcbuf += 2;
                        if (run) {
                            srcbuf += 2 * run;
                            ofs += run;
                        } else if (!ofs)
                            goto done;
                    }
                    while (ofs < w);

                    /* skip padding */
                    srcbuf += (uintptr_t) srcbuf & 2;

                    /* skip translucent line */
                    ofs = 0;
                    do {
                        int run;
                        ofs += ((Uint16 *) srcbuf)[0];
                        run = ((Uint16 *) srcbuf)[1];
                        srcbuf += 4 * (run + 1);
                        ofs += run;
                    }
                    while (ofs < w);
                }
                while (--vskip);
            } else {
                /* the 32/32 interleaved format */
                vskip <<= 1;    /* opaque and translucent have same format */
                do {
                    ofs = 0;
                    do {
                        int run;
                        ofs += ((Uint16 *) srcbuf)[0];
                        run = ((Uint16 *) srcbuf)[1];
                        srcbuf += 4;
                        if (run) {
                            srcbuf += 4 * run;
                            ofs += run;
                        } else if (!ofs)
                            goto done;
                    }
                    while (ofs < w);
                }
                while (--vskip);
            }
        }
    }

    /* if left or right edge clipping needed, call clip blit */
    if (srcrect->x || srcrect->w != src->w) {
        RLEAlphaClipBlit(w, srcbuf, dst, dstbuf, srcrect);
    } else {

        /*
         * non-clipped blitter. Ptype is the destination pixel type,
         * Ctype the translucent count type, and do_blend the
         * macro to blend one pixel.
         */
#define RLEALPHABLIT(Ptype, Ctype, do_blend)				 \
	do {								 \
	    int linecount = srcrect->h;					 \
	    do {							 \
		int ofs = 0;						 \
		/* blit opaque pixels on one line */			 \
		do {							 \
		    unsigned run;					 \
		    ofs += ((Ctype *)srcbuf)[0];			 \
		    run = ((Ctype *)srcbuf)[1];				 \
		    srcbuf += 2 * sizeof(Ctype);			 \
		    if(run) {						 \
			PIXEL_COPY(dstbuf + ofs * sizeof(Ptype), srcbuf, \
				   run, sizeof(Ptype));			 \
			srcbuf += run * sizeof(Ptype);			 \
			ofs += run;					 \
		    } else if(!ofs)					 \
			goto done;					 \
		} while(ofs < w);					 \
		/* skip padding if necessary */				 \
		if(sizeof(Ptype) == 2)					 \
		    srcbuf += (uintptr_t)srcbuf & 2;		 	 \
		/* blit translucent pixels on the same line */		 \
		ofs = 0;						 \
		do {							 \
		    unsigned run;					 \
		    ofs += ((Uint16 *)srcbuf)[0];			 \
		    run = ((Uint16 *)srcbuf)[1];			 \
		    srcbuf += 4;					 \
		    if(run) {						 \
			Ptype *dst = (Ptype *)dstbuf + ofs;		 \
			unsigned i;					 \
			for(i = 0; i < run; i++) {			 \
			    Uint32 src = *(Uint32 *)srcbuf;		 \
			    do_blend(src, *dst);			 \
			    srcbuf += 4;				 \
			    dst++;					 \
			}						 \
			ofs += run;					 \
		    }							 \
		} while(ofs < w);					 \
		dstbuf += dst->pitch;					 \
	    } while(--linecount);					 \
	} while(0)

        switch (df->BytesPerPixel) {
        case 2:
            if (df->Gmask == 0x07e0 || df->Rmask == 0x07e0
                || df->Bmask == 0x07e0)
                RLEALPHABLIT(Uint16, Uint8, BLIT_TRANSL_565);
            else
                RLEALPHABLIT(Uint16, Uint8, BLIT_TRANSL_555);
            break;
        case 4:
            RLEALPHABLIT(Uint32, Uint16, BLIT_TRANSL_888);
            break;
        }
    }

  done:
    /* Unlock the destination if necessary */
    if (SDL_MUSTLOCK(dst)) {
        SDL_UnlockSurface(dst);
    }
    return 0;
}

/*
 * Auxiliary functions:
 * The encoding functions take 32bpp rgb + a, and
 * return the number of bytes copied to the destination.
 * The decoding functions copy to 32bpp rgb + a, and
 * return the number of bytes copied from the source.
 * These are only used in the encoder and un-RLE code and are therefore not
 * highly optimised.
 */

/* encode 32bpp rgb + a into 16bpp rgb, losing alpha */
static int
copy_opaque_16(void *dst, Uint32 * src, int n,
               SDL_PixelFormat * sfmt, SDL_PixelFormat * dfmt)
{
    int i;
    Uint16 *d = dst;
    for (i = 0; i < n; i++) {
        unsigned r, g, b;
        RGB_FROM_PIXEL(*src, sfmt, r, g, b);
        PIXEL_FROM_RGB(*d, dfmt, r, g, b);
        src++;
        d++;
    }
    return n * 2;
}

/* decode opaque pixels from 16bpp to 32bpp rgb + a */
static int
uncopy_opaque_16(Uint32 * dst, void *src, int n,
                 RLEDestFormat * sfmt, SDL_PixelFormat * dfmt)
{
    int i;
    Uint16 *s = src;
    unsigned alpha = dfmt->Amask ? 255 : 0;
    for (i = 0; i < n; i++) {
        unsigned r, g, b;
        RGB_FROM_PIXEL(*s, sfmt, r, g, b);
        PIXEL_FROM_RGBA(*dst, dfmt, r, g, b, alpha);
        s++;
        dst++;
    }
    return n * 2;
}



/* encode 32bpp rgb + a into 32bpp G0RAB format for blitting into 565 */
static int
copy_transl_565(void *dst, Uint32 * src, int n,
                SDL_PixelFormat * sfmt, SDL_PixelFormat * dfmt)
{
    int i;
    Uint32 *d = dst;
    for (i = 0; i < n; i++) {
        unsigned r, g, b, a;
        Uint16 pix;
        RGBA_FROM_8888(*src, sfmt, r, g, b, a);
        PIXEL_FROM_RGB(pix, dfmt, r, g, b);
        *d = ((pix & 0x7e0) << 16) | (pix & 0xf81f) | ((a << 2) & 0x7e0);
        src++;
        d++;
    }
    return n * 4;
}

/* encode 32bpp rgb + a into 32bpp G0RAB format for blitting into 555 */
static int
copy_transl_555(void *dst, Uint32 * src, int n,
                SDL_PixelFormat * sfmt, SDL_PixelFormat * dfmt)
{
    int i;
    Uint32 *d = dst;
    for (i = 0; i < n; i++) {
        unsigned r, g, b, a;
        Uint16 pix;
        RGBA_FROM_8888(*src, sfmt, r, g, b, a);
        PIXEL_FROM_RGB(pix, dfmt, r, g, b);
        *d = ((pix & 0x3e0) << 16) | (pix & 0xfc1f) | ((a << 2) & 0x3e0);
        src++;
        d++;
    }
    return n * 4;
}

/* decode translucent pixels from 32bpp GORAB to 32bpp rgb + a */
static int
uncopy_transl_16(Uint32 * dst, void *src, int n,
                 RLEDestFormat * sfmt, SDL_PixelFormat * dfmt)
{
    int i;
    Uint32 *s = src;
    for (i = 0; i < n; i++) {
        unsigned r, g, b, a;
        Uint32 pix = *s++;
        a = (pix & 0x3e0) >> 2;
        pix = (pix & ~0x3e0) | pix >> 16;
        RGB_FROM_PIXEL(pix, sfmt, r, g, b);
        PIXEL_FROM_RGBA(*dst, dfmt, r, g, b, a);
        dst++;
    }
    return n * 4;
}

/* encode 32bpp rgba into 32bpp rgba, keeping alpha (dual purpose) */
static int
copy_32(void *dst, Uint32 * src, int n,
        SDL_PixelFormat * sfmt, SDL_PixelFormat * dfmt)
{
    int i;
    Uint32 *d = dst;
    for (i = 0; i < n; i++) {
        unsigned r, g, b, a;
        Uint32 pixel;
        RGBA_FROM_8888(*src, sfmt, r, g, b, a);
        PIXEL_FROM_RGB(pixel, dfmt, r, g, b);
        *d++ = pixel | a << 24;
        src++;
    }
    return n * 4;
}

/* decode 32bpp rgba into 32bpp rgba, keeping alpha (dual purpose) */
static int
uncopy_32(Uint32 * dst, void *src, int n,
          RLEDestFormat * sfmt, SDL_PixelFormat * dfmt)
{
    int i;
    Uint32 *s = src;
    for (i = 0; i < n; i++) {
        unsigned r, g, b, a;
        Uint32 pixel = *s++;
        RGB_FROM_PIXEL(pixel, sfmt, r, g, b);
        a = pixel >> 24;
        PIXEL_FROM_RGBA(*dst, dfmt, r, g, b, a);
        dst++;
    }
    return n * 4;
}

#define ISOPAQUE(pixel, fmt) ((((pixel) & fmt->Amask) >> fmt->Ashift) == 255)

#define ISTRANSL(pixel, fmt)	\
    ((unsigned)((((pixel) & fmt->Amask) >> fmt->Ashift) - 1U) < 254U)

/* convert surface to be quickly alpha-blittable onto dest, if possible */
static int
RLEAlphaSurface(SDL_Surface * surface)
{
    SDL_Surface *dest;
    SDL_PixelFormat *df;
    int maxsize = 0;
    int max_opaque_run;
    int max_transl_run = 65535;
    unsigned masksum;
    Uint8 *rlebuf, *dst;
    int (*copy_opaque) (void *, Uint32 *, int,
                        SDL_PixelFormat *, SDL_PixelFormat *);
    int (*copy_transl) (void *, Uint32 *, int,
                        SDL_PixelFormat *, SDL_PixelFormat *);

    dest = surface->map->dst;
    if (!dest)
        return -1;
    df = dest->format;
    if (surface->format->BitsPerPixel != 32)
        return -1;              /* only 32bpp source supported */

    /* find out whether the destination is one we support,
       and determine the max size of the encoded result */
    masksum = df->Rmask | df->Gmask | df->Bmask;
    switch (df->BytesPerPixel) {
    case 2:
        /* 16bpp: only support 565 and 555 formats */
        switch (masksum) {
        case 0xffff:
            if (df->Gmask == 0x07e0
                || df->Rmask == 0x07e0 || df->Bmask == 0x07e0) {
                copy_opaque = copy_opaque_16;
                copy_transl = copy_transl_565;
            } else
                return -1;
            break;
        case 0x7fff:
            if (df->Gmask == 0x03e0
                || df->Rmask == 0x03e0 || df->Bmask == 0x03e0) {
                copy_opaque = copy_opaque_16;
                copy_transl = copy_transl_555;
            } else
                return -1;
            break;
        default:
            return -1;
        }
        max_opaque_run = 255;   /* runs stored as bytes */

        /* worst case is alternating opaque and translucent pixels,
           with room for alignment padding between lines */
        maxsize = surface->h * (2 + (4 + 2) * (surface->w + 1)) + 2;
        break;
    case 4:
        if (masksum != 0x00ffffff)
            return -1;          /* requires unused high byte */
        copy_opaque = copy_32;
        copy_transl = copy_32;
        max_opaque_run = 255;   /* runs stored as short ints */

        /* worst case is alternating opaque and translucent pixels */
        maxsize = surface->h * 2 * 4 * (surface->w + 1) + 4;
        break;
    default:
        return -1;              /* anything else unsupported right now */
    }

    maxsize += sizeof(RLEDestFormat);
    rlebuf = (Uint8 *) SDL_malloc(maxsize);
    if (!rlebuf) {
        SDL_OutOfMemory();
        return -1;
    }
    {
        /* save the destination format so we can undo the encoding later */
        RLEDestFormat *r = (RLEDestFormat *) rlebuf;
        r->BytesPerPixel = df->BytesPerPixel;
        r->Rloss = df->Rloss;
        r->Gloss = df->Gloss;
        r->Bloss = df->Bloss;
        r->Rshift = df->Rshift;
        r->Gshift = df->Gshift;
        r->Bshift = df->Bshift;
        r->Ashift = df->Ashift;
        r->Rmask = df->Rmask;
        r->Gmask = df->Gmask;
        r->Bmask = df->Bmask;
        r->Amask = df->Amask;
    }
    dst = rlebuf + sizeof(RLEDestFormat);

    /* Do the actual encoding */
    {
        int x, y;
        int h = surface->h, w = surface->w;
        SDL_PixelFormat *sf = surface->format;
        Uint32 *src = (Uint32 *) surface->pixels;
        Uint8 *lastline = dst;  /* end of last non-blank line */

        /* opaque counts are 8 or 16 bits, depending on target depth */
#define ADD_OPAQUE_COUNTS(n, m)			\
	if(df->BytesPerPixel == 4) {		\
	    ((Uint16 *)dst)[0] = n;		\
	    ((Uint16 *)dst)[1] = m;		\
	    dst += 4;				\
	} else {				\
	    dst[0] = n;				\
	    dst[1] = m;				\
	    dst += 2;				\
	}

        /* translucent counts are always 16 bit */
#define ADD_TRANSL_COUNTS(n, m)		\
	(((Uint16 *)dst)[0] = n, ((Uint16 *)dst)[1] = m, dst += 4)

        for (y = 0; y < h; y++) {
            int runstart, skipstart;
            int blankline = 0;
            /* First encode all opaque pixels of a scan line */
            x = 0;
            do {
                int run, skip, len;
                skipstart = x;
                while (x < w && !ISOPAQUE(src[x], sf))
                    x++;
                runstart = x;
                while (x < w && ISOPAQUE(src[x], sf))
                    x++;
                skip = runstart - skipstart;
                if (skip == w)
                    blankline = 1;
                run = x - runstart;
                while (skip > max_opaque_run) {
                    ADD_OPAQUE_COUNTS(max_opaque_run, 0);
                    skip -= max_opaque_run;
                }
                len = MIN(run, max_opaque_run);
                ADD_OPAQUE_COUNTS(skip, len);
                dst += copy_opaque(dst, src + runstart, len, sf, df);
                runstart += len;
                run -= len;
                while (run) {
                    len = MIN(run, max_opaque_run);
                    ADD_OPAQUE_COUNTS(0, len);
                    dst += copy_opaque(dst, src + runstart, len, sf, df);
                    runstart += len;
                    run -= len;
                }
            }
            while (x < w);

            /* Make sure the next output address is 32-bit aligned */
            dst += (uintptr_t) dst & 2;

            /* Next, encode all translucent pixels of the same scan line */
            x = 0;
            do {
                int run, skip, len;
                skipstart = x;
                while (x < w && !ISTRANSL(src[x], sf))
                    x++;
                runstart = x;
                while (x < w && ISTRANSL(src[x], sf))
                    x++;
                skip = runstart - skipstart;
                blankline &= (skip == w);
                run = x - runstart;
                while (skip > max_transl_run) {
                    ADD_TRANSL_COUNTS(max_transl_run, 0);
                    skip -= max_transl_run;
                }
                len = MIN(run, max_transl_run);
                ADD_TRANSL_COUNTS(skip, len);
                dst += copy_transl(dst, src + runstart, len, sf, df);
                runstart += len;
                run -= len;
                while (run) {
                    len = MIN(run, max_transl_run);
                    ADD_TRANSL_COUNTS(0, len);
                    dst += copy_transl(dst, src + runstart, len, sf, df);
                    runstart += len;
                    run -= len;
                }
                if (!blankline)
                    lastline = dst;
            }
            while (x < w);

            src += surface->pitch >> 2;
        }
        dst = lastline;         /* back up past trailing blank lines */
        ADD_OPAQUE_COUNTS(0, 0);
    }

#undef ADD_OPAQUE_COUNTS
#undef ADD_TRANSL_COUNTS

    /* Now that we have it encoded, release the original pixels */
    if (!(surface->flags & SDL_PREALLOC)) {
        SDL_free(surface->pixels);
        surface->pixels = NULL;
    }

    /* realloc the buffer to release unused memory */
    {
        Uint8 *p = SDL_realloc(rlebuf, dst - rlebuf);
        if (!p)
            p = rlebuf;
        surface->map->data = p;
    }

    return 0;
}

static Uint32
getpix_8(Uint8 * srcbuf)
{
    return *srcbuf;
}

static Uint32
getpix_16(Uint8 * srcbuf)
{
    return *(Uint16 *) srcbuf;
}

static Uint32
getpix_24(Uint8 * srcbuf)
{
#if SDL_BYTEORDER == SDL_LIL_ENDIAN
    return srcbuf[0] + (srcbuf[1] << 8) + (srcbuf[2] << 16);
#else
    return (srcbuf[0] << 16) + (srcbuf[1] << 8) + srcbuf[2];
#endif
}

static Uint32
getpix_32(Uint8 * srcbuf)
{
    return *(Uint32 *) srcbuf;
}

typedef Uint32(*getpix_func) (Uint8 *);

static getpix_func getpixes[4] = {
    getpix_8, getpix_16, getpix_24, getpix_32
};

static int
RLEColorkeySurface(SDL_Surface * surface)
{
    Uint8 *rlebuf, *dst;
    int maxn;
    int y;
    Uint8 *srcbuf, *curbuf, *lastline;
    int maxsize = 0;
    int skip, run;
    int bpp = surface->format->BytesPerPixel;
    getpix_func getpix;
    Uint32 ckey, rgbmask;
    int w, h;

    /* calculate the worst case size for the compressed surface */
    switch (bpp) {
    case 1:
        /* worst case is alternating opaque and transparent pixels,
           starting with an opaque pixel */
        maxsize = surface->h * 3 * (surface->w / 2 + 1) + 2;
        break;
    case 2:
    case 3:
        /* worst case is solid runs, at most 255 pixels wide */
        maxsize = surface->h * (2 * (surface->w / 255 + 1)
                                + surface->w * bpp) + 2;
        break;
    case 4:
        /* worst case is solid runs, at most 65535 pixels wide */
        maxsize = surface->h * (4 * (surface->w / 65535 + 1)
                                + surface->w * 4) + 4;
        break;
    }

    rlebuf = (Uint8 *) SDL_malloc(maxsize);
    if (rlebuf == NULL) {
        SDL_OutOfMemory();
        return (-1);
    }

    /* Set up the conversion */
    srcbuf = (Uint8 *) surface->pixels;
    curbuf = srcbuf;
    maxn = bpp == 4 ? 65535 : 255;
    skip = run = 0;
    dst = rlebuf;
    rgbmask = ~surface->format->Amask;
    ckey = surface->map->info.colorkey & rgbmask;
    lastline = dst;
    getpix = getpixes[bpp - 1];
    w = surface->w;
    h = surface->h;

#define ADD_COUNTS(n, m)			\
	if(bpp == 4) {				\
	    ((Uint16 *)dst)[0] = n;		\
	    ((Uint16 *)dst)[1] = m;		\
	    dst += 4;				\
	} else {				\
	    dst[0] = n;				\
	    dst[1] = m;				\
	    dst += 2;				\
	}

    for (y = 0; y < h; y++) {
        int x = 0;
        int blankline = 0;
        do {
            int run, skip, len;
            int runstart;
            int skipstart = x;

            /* find run of transparent, then opaque pixels */
            while (x < w && (getpix(srcbuf + x * bpp) & rgbmask) == ckey)
                x++;
            runstart = x;
            while (x < w && (getpix(srcbuf + x * bpp) & rgbmask) != ckey)
                x++;
            skip = runstart - skipstart;
            if (skip == w)
                blankline = 1;
            run = x - runstart;

            /* encode segment */
            while (skip > maxn) {
                ADD_COUNTS(maxn, 0);
                skip -= maxn;
            }
            len = MIN(run, maxn);
            ADD_COUNTS(skip, len);
            SDL_memcpy(dst, srcbuf + runstart * bpp, len * bpp);
            dst += len * bpp;
            run -= len;
            runstart += len;
            while (run) {
                len = MIN(run, maxn);
                ADD_COUNTS(0, len);
                SDL_memcpy(dst, srcbuf + runstart * bpp, len * bpp);
                dst += len * bpp;
                runstart += len;
                run -= len;
            }
            if (!blankline)
                lastline = dst;
        }
        while (x < w);

        srcbuf += surface->pitch;
    }
    dst = lastline;             /* back up bast trailing blank lines */
    ADD_COUNTS(0, 0);

#undef ADD_COUNTS

    /* Now that we have it encoded, release the original pixels */
    if (!(surface->flags & SDL_PREALLOC)) {
        SDL_free(surface->pixels);
        surface->pixels = NULL;
    }

    /* realloc the buffer to release unused memory */
    {
        /* If realloc returns NULL, the original block is left intact */
        Uint8 *p = SDL_realloc(rlebuf, dst - rlebuf);
        if (!p)
            p = rlebuf;
        surface->map->data = p;
    }

    return (0);
}

int
SDL_RLESurface(SDL_Surface * surface)
{
    int flags;

    /* Clear any previous RLE conversion */
    if ((surface->flags & SDL_RLEACCEL) == SDL_RLEACCEL) {
        SDL_UnRLESurface(surface, 1);
    }

    /* We don't support RLE encoding of bitmaps */
    if (surface->format->BitsPerPixel < 8) {
        return -1;
    }

    /* Make sure the pixels are available */
    if (!surface->pixels) {
        return -1;
    }

    /* If we don't have colorkey or blending, nothing to do... */
    flags = surface->map->info.flags;
    if (!(flags & (SDL_COPY_COLORKEY | SDL_COPY_BLEND))) {
        return -1;
    }

    /* Pass on combinations not supported */
    if ((flags & SDL_COPY_MODULATE_COLOR) ||
        (flags & (SDL_COPY_ADD | SDL_COPY_MOD)) ||
        (flags & SDL_COPY_NEAREST)) {
        return -1;
    }

    /* Encode and set up the blit */
    if (!surface->format->Amask || !(flags & SDL_COPY_BLEND)) {
        if (!surface->map->identity) {
            return -1;
        }
        if (RLEColorkeySurface(surface) < 0) {
            return -1;
        }
        surface->map->blit = SDL_RLEBlit;
        surface->map->info.flags |= SDL_COPY_RLE_COLORKEY;
    } else {
        if (RLEAlphaSurface(surface) < 0) {
            return -1;
        }
        surface->map->blit = SDL_RLEAlphaBlit;
        surface->map->info.flags |= SDL_COPY_RLE_ALPHAKEY;
    }

    /* The surface is now accelerated */
    surface->flags |= SDL_RLEACCEL;

    return (0);
}

/*
 * Un-RLE a surface with pixel alpha
 * This may not give back exactly the image before RLE-encoding; all
 * completely transparent pixels will be lost, and colour and alpha depth
 * may have been reduced (when encoding for 16bpp targets).
 */
static SDL_bool
UnRLEAlpha(SDL_Surface * surface)
{
    Uint8 *srcbuf;
    Uint32 *dst;
    SDL_PixelFormat *sf = surface->format;
    RLEDestFormat *df = surface->map->data;
    int (*uncopy_opaque) (Uint32 *, void *, int,
                          RLEDestFormat *, SDL_PixelFormat *);
    int (*uncopy_transl) (Uint32 *, void *, int,
                          RLEDestFormat *, SDL_PixelFormat *);
    int w = surface->w;
    int bpp = df->BytesPerPixel;

    if (bpp == 2) {
        uncopy_opaque = uncopy_opaque_16;
        uncopy_transl = uncopy_transl_16;
    } else {
        uncopy_opaque = uncopy_transl = uncopy_32;
    }

    surface->pixels = SDL_malloc(surface->h * surface->pitch);
    if (!surface->pixels) {
        return (SDL_FALSE);
    }
    /* fill background with transparent pixels */
    SDL_memset(surface->pixels, 0, surface->h * surface->pitch);

    dst = surface->pixels;
    srcbuf = (Uint8 *) (df + 1);
    for (;;) {
        /* copy opaque pixels */
        int ofs = 0;
        do {
            unsigned run;
            if (bpp == 2) {
                ofs += srcbuf[0];
                run = srcbuf[1];
                srcbuf += 2;
            } else {
                ofs += ((Uint16 *) srcbuf)[0];
                run = ((Uint16 *) srcbuf)[1];
                srcbuf += 4;
            }
            if (run) {
                srcbuf += uncopy_opaque(dst + ofs, srcbuf, run, df, sf);
                ofs += run;
            } else if (!ofs)
                return (SDL_TRUE);
        }
        while (ofs < w);

        /* skip padding if needed */
        if (bpp == 2)
            srcbuf += (uintptr_t) srcbuf & 2;

        /* copy translucent pixels */
        ofs = 0;
        do {
            unsigned run;
            ofs += ((Uint16 *) srcbuf)[0];
            run = ((Uint16 *) srcbuf)[1];
            srcbuf += 4;
            if (run) {
                srcbuf += uncopy_transl(dst + ofs, srcbuf, run, df, sf);
                ofs += run;
            }
        }
        while (ofs < w);
        dst += surface->pitch >> 2;
    }
    /* Make the compiler happy */
    return (SDL_TRUE);
}

void
SDL_UnRLESurface(SDL_Surface * surface, int recode)
{
    if (surface->flags & SDL_RLEACCEL) {
        surface->flags &= ~SDL_RLEACCEL;

        if (recode && !(surface->flags & SDL_PREALLOC)) {
            if (surface->map->info.flags & SDL_COPY_RLE_COLORKEY) {
                SDL_Rect full;

                /* re-create the original surface */
                surface->pixels = SDL_malloc(surface->h * surface->pitch);
                if (!surface->pixels) {
                    /* Oh crap... */
                    surface->flags |= SDL_RLEACCEL;
                    return;
                }

                /* fill it with the background colour */
                SDL_FillRect(surface, NULL, surface->map->info.colorkey);

                /* now render the encoded surface */
                full.x = full.y = 0;
                full.w = surface->w;
                full.h = surface->h;
                SDL_RLEBlit(surface, &full, surface, &full);
            } else {
                if (!UnRLEAlpha(surface)) {
                    /* Oh crap... */
                    surface->flags |= SDL_RLEACCEL;
                    return;
                }
            }
        }
        surface->map->info.flags &=
            (SDL_COPY_RLE_COLORKEY | SDL_COPY_RLE_ALPHAKEY);
        surface->map->info.flags |= SDL_COPY_RLE_DESIRED;

        if (surface->map->data) {
            SDL_free(surface->map->data);
            surface->map->data = NULL;
        }
    }
}

/* vi: set ts=4 sw=4 expandtab: */