src/video/SDL_RLEaccel.c
author Sam Lantinga <slouken@libsdl.org>
Fri, 14 Dec 2001 12:38:15 +0000
changeset 252 e8157fcb3114
parent 1 cf2af46e9e2a
child 297 f6ffac90895c
permissions -rw-r--r--
Updated the source with the correct e-mail address
     1 /*
     2     SDL - Simple DirectMedia Layer
     3     Copyright (C) 1997, 1998, 1999, 2000, 2001  Sam Lantinga
     4 
     5     This library is free software; you can redistribute it and/or
     6     modify it under the terms of the GNU Library General Public
     7     License as published by the Free Software Foundation; either
     8     version 2 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     Library General Public License for more details.
    14 
    15     You should have received a copy of the GNU Library General Public
    16     License along with this library; if not, write to the Free
    17     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    18 
    19     Sam Lantinga
    20     slouken@libsdl.org
    21 */
    22 
    23 #ifdef SAVE_RCSID
    24 static char rcsid =
    25  "@(#) $Id$";
    26 #endif
    27 
    28 /*
    29  * RLE encoding for software colorkey and alpha-channel acceleration
    30  *
    31  * Original version by Sam Lantinga
    32  *
    33  * Mattias Engdegård (Yorick): Rewrite. New encoding format, encoder and
    34  * decoder. Added per-surface alpha blitter. Added per-pixel alpha
    35  * format, encoder and blitter.
    36  *
    37  * Many thanks to Xark and johns for hints, benchmarks and useful comments
    38  * leading to this code.
    39  *
    40  * Welcome to Macro Mayhem.
    41  */
    42 
    43 /*
    44  * The encoding translates the image data to a stream of segments of the form
    45  *
    46  * <skip> <run> <data>
    47  *
    48  * where <skip> is the number of transparent pixels to skip,
    49  *       <run>  is the number of opaque pixels to blit,
    50  * and   <data> are the pixels themselves.
    51  *
    52  * This basic structure is used both for colorkeyed surfaces, used for simple
    53  * binary transparency and for per-surface alpha blending, and for surfaces
    54  * with per-pixel alpha. The details differ, however:
    55  *
    56  * Encoding of colorkeyed surfaces:
    57  *
    58  *   Encoded pixels always have the same format as the target surface.
    59  *   <skip> and <run> are unsigned 8 bit integers, except for 32 bit depth
    60  *   where they are 16 bit. This makes the pixel data aligned at all times.
    61  *   Segments never wrap around from one scan line to the next.
    62  *
    63  *   The end of the sequence is marked by a zero <skip>,<run> pair at the *
    64  *   beginning of a line.
    65  *
    66  * Encoding of surfaces with per-pixel alpha:
    67  *
    68  *   The sequence begins with a struct RLEDestFormat describing the target
    69  *   pixel format, to provide reliable un-encoding.
    70  *
    71  *   Each scan line is encoded twice: First all completely opaque pixels,
    72  *   encoded in the target format as described above, and then all
    73  *   partially transparent (translucent) pixels (where 1 <= alpha <= 254),
    74  *   in the following 32-bit format:
    75  *
    76  *   For 32-bit targets, each pixel has the target RGB format but with
    77  *   the alpha value occupying the highest 8 bits. The <skip> and <run>
    78  *   counts are 16 bit.
    79  * 
    80  *   For 16-bit targets, each pixel has the target RGB format, but with
    81  *   the middle component (usually green) shifted 16 steps to the left,
    82  *   and the hole filled with the 5 most significant bits of the alpha value.
    83  *   i.e. if the target has the format         rrrrrggggggbbbbb,
    84  *   the encoded pixel will be 00000gggggg00000rrrrr0aaaaabbbbb.
    85  *   The <skip> and <run> counts are 8 bit for the opaque lines, 16 bit
    86  *   for the translucent lines. Two padding bytes may be inserted
    87  *   before each translucent line to keep them 32-bit aligned.
    88  *
    89  *   The end of the sequence is marked by a zero <skip>,<run> pair at the
    90  *   beginning of an opaque line.
    91  */
    92 
    93 #include <stdio.h>
    94 #include <stdlib.h>
    95 #include <string.h>
    96 
    97 #include "SDL_types.h"
    98 #include "SDL_video.h"
    99 #include "SDL_error.h"
   100 #include "SDL_sysvideo.h"
   101 #include "SDL_blit.h"
   102 #include "SDL_memops.h"
   103 #include "SDL_RLEaccel_c.h"
   104 
   105 #ifndef MAX
   106 #define MAX(a, b) ((a) > (b) ? (a) : (b))
   107 #endif
   108 #ifndef MIN
   109 #define MIN(a, b) ((a) < (b) ? (a) : (b))
   110 #endif
   111 
   112 #define PIXEL_COPY(to, from, len, bpp)			\
   113 do {							\
   114     if(bpp == 4) {					\
   115 	SDL_memcpy4(to, from, (unsigned)(len));		\
   116     } else {						\
   117 	SDL_memcpy(to, from, (unsigned)(len) * (bpp));	\
   118     }							\
   119 } while(0)
   120 
   121 /*
   122  * Various colorkey blit methods, for opaque and per-surface alpha
   123  */
   124 
   125 #define OPAQUE_BLIT(to, from, length, bpp, alpha)	\
   126     PIXEL_COPY(to, from, length, bpp)
   127 
   128 /*
   129  * For 32bpp pixels on the form 0x00rrggbb:
   130  * If we treat the middle component separately, we can process the two
   131  * remaining in parallel. This is safe to do because of the gap to the left
   132  * of each component, so the bits from the multiplication don't collide.
   133  * This can be used for any RGB permutation of course.
   134  */
   135 #define ALPHA_BLIT32_888(to, from, length, bpp, alpha)		\
   136     do {							\
   137         int i;							\
   138 	Uint32 *src = (Uint32 *)(from);				\
   139 	Uint32 *dst = (Uint32 *)(to);				\
   140 	for(i = 0; i < (int)(length); i++) {			\
   141 	    Uint32 s = *src++;					\
   142 	    Uint32 d = *dst;					\
   143 	    Uint32 s1 = s & 0xff00ff;				\
   144 	    Uint32 d1 = d & 0xff00ff;				\
   145 	    d1 = (d1 + ((s1 - d1) * alpha >> 8)) & 0xff00ff;	\
   146 	    s &= 0xff00;					\
   147 	    d &= 0xff00;					\
   148 	    d = (d + ((s - d) * alpha >> 8)) & 0xff00;		\
   149 	    *dst++ = d1 | d;					\
   150 	}							\
   151     } while(0)
   152 
   153 /*
   154  * For 16bpp pixels we can go a step further: put the middle component
   155  * in the high 16 bits of a 32 bit word, and process all three RGB
   156  * components at the same time. Since the smallest gap is here just
   157  * 5 bits, we have to scale alpha down to 5 bits as well.
   158  */
   159 #define ALPHA_BLIT16_565(to, from, length, bpp, alpha)	\
   160     do {						\
   161         int i;						\
   162 	Uint16 *src = (Uint16 *)(from);			\
   163 	Uint16 *dst = (Uint16 *)(to);			\
   164 	for(i = 0; i < (int)(length); i++) {		\
   165 	    Uint32 s = *src++;				\
   166 	    Uint32 d = *dst;				\
   167 	    s = (s | s << 16) & 0x07e0f81f;		\
   168 	    d = (d | d << 16) & 0x07e0f81f;		\
   169 	    d += (s - d) * alpha >> 5;			\
   170 	    d &= 0x07e0f81f;				\
   171 	    *dst++ = d | d >> 16;			\
   172 	}						\
   173     } while(0)
   174 
   175 #define ALPHA_BLIT16_555(to, from, length, bpp, alpha)	\
   176     do {						\
   177         int i;						\
   178 	Uint16 *src = (Uint16 *)(from);			\
   179 	Uint16 *dst = (Uint16 *)(to);			\
   180 	for(i = 0; i < (int)(length); i++) {		\
   181 	    Uint32 s = *src++;				\
   182 	    Uint32 d = *dst;				\
   183 	    s = (s | s << 16) & 0x03e07c1f;		\
   184 	    d = (d | d << 16) & 0x03e07c1f;		\
   185 	    d += (s - d) * alpha >> 5;			\
   186 	    d &= 0x03e07c1f;				\
   187 	    *dst++ = d | d >> 16;			\
   188 	}						\
   189     } while(0)
   190 
   191 /*
   192  * The general slow catch-all function, for remaining depths and formats
   193  */
   194 #define ALPHA_BLIT_ANY(to, from, length, bpp, alpha)			\
   195     do {								\
   196         int i;								\
   197 	Uint8 *src = from;						\
   198 	Uint8 *dst = to;						\
   199 	for(i = 0; i < (int)(length); i++) {				\
   200 	    Uint32 s, d;						\
   201 	    unsigned rs, gs, bs, rd, gd, bd;				\
   202 	    switch(bpp) {						\
   203 	    case 2:							\
   204 		s = *(Uint16 *)src;					\
   205 		d = *(Uint16 *)dst;					\
   206 		break;							\
   207 	    case 3:							\
   208 		if(SDL_BYTEORDER == SDL_BIG_ENDIAN) {			\
   209 		    s = (src[0] << 16) | (src[1] << 8) | src[2];	\
   210 		    d = (dst[0] << 16) | (dst[1] << 8) | dst[2];	\
   211 		} else {						\
   212 		    s = (src[2] << 16) | (src[1] << 8) | src[0];	\
   213 		    d = (dst[2] << 16) | (dst[1] << 8) | dst[0];	\
   214 		}							\
   215 		break;							\
   216 	    case 4:							\
   217 		s = *(Uint32 *)src;					\
   218 		d = *(Uint32 *)dst;					\
   219 		break;							\
   220 	    }								\
   221 	    RGB_FROM_PIXEL(s, fmt, rs, gs, bs);				\
   222 	    RGB_FROM_PIXEL(d, fmt, rd, gd, bd);				\
   223 	    rd += (rs - rd) * alpha >> 8;				\
   224 	    gd += (gs - gd) * alpha >> 8;				\
   225 	    bd += (bs - bd) * alpha >> 8;				\
   226 	    PIXEL_FROM_RGB(d, fmt, rd, gd, bd);				\
   227 	    switch(bpp) {						\
   228 	    case 2:							\
   229 		*(Uint16 *)dst = d;					\
   230 		break;							\
   231 	    case 3:							\
   232 		if(SDL_BYTEORDER == SDL_BIG_ENDIAN) {			\
   233 		    dst[0] = d >> 16;					\
   234 		    dst[1] = d >> 8;					\
   235 		    dst[2] = d;						\
   236 		} else {						\
   237 		    dst[0] = d;						\
   238 		    dst[1] = d >> 8;					\
   239 		    dst[2] = d >> 16;					\
   240 		}							\
   241 		break;							\
   242 	    case 4:							\
   243 		*(Uint32 *)dst = d;					\
   244 		break;							\
   245 	    }								\
   246 	    src += bpp;							\
   247 	    dst += bpp;							\
   248 	}								\
   249     } while(0)
   250 
   251 
   252 /*
   253  * Special case: 50% alpha (alpha=128)
   254  * This is treated specially because it can be optimized very well, and
   255  * since it is good for many cases of semi-translucency.
   256  * The theory is to do all three components at the same time:
   257  * First zero the lowest bit of each component, which gives us room to
   258  * add them. Then shift right and add the sum of the lowest bits.
   259  */
   260 #define ALPHA_BLIT32_888_50(to, from, length, bpp, alpha)		\
   261     do {								\
   262         int i;								\
   263 	Uint32 *src = (Uint32 *)(from);					\
   264 	Uint32 *dst = (Uint32 *)(to);					\
   265 	for(i = 0; i < (int)(length); i++) {				\
   266 	    Uint32 s = *src++;						\
   267 	    Uint32 d = *dst;						\
   268 	    *dst++ = (((s & 0x00fefefe) + (d & 0x00fefefe)) >> 1)	\
   269 		     + (s & d & 0x00010101);				\
   270 	}								\
   271     } while(0)
   272 
   273 /*
   274  * For 16bpp, we can actually blend two pixels in parallel, if we take
   275  * care to shift before we add, not after.
   276  */
   277 
   278 /* helper: blend a single 16 bit pixel at 50% */
   279 #define BLEND16_50(dst, src, mask)			\
   280     do {						\
   281         Uint32 s = *src++;				\
   282 	Uint32 d = *dst;				\
   283 	*dst++ = (((s & mask) + (d & mask)) >> 1)	\
   284 	         + (s & d & (~mask & 0xffff));		\
   285     } while(0)
   286 
   287 /* basic 16bpp blender. mask is the pixels to keep when adding. */
   288 #define ALPHA_BLIT16_50(to, from, length, bpp, alpha, mask)		\
   289     do {								\
   290 	unsigned n = (length);						\
   291 	Uint16 *src = (Uint16 *)(from);					\
   292 	Uint16 *dst = (Uint16 *)(to);					\
   293 	if(((unsigned long)src ^ (unsigned long)dst) & 3) {		\
   294 	    /* source and destination not in phase, blit one by one */	\
   295 	    while(n--)							\
   296 		BLEND16_50(dst, src, mask);				\
   297 	} else {							\
   298 	    if((unsigned long)src & 3) {				\
   299 		/* first odd pixel */					\
   300 		BLEND16_50(dst, src, mask);				\
   301 		n--;							\
   302 	    }								\
   303 	    for(; n > 1; n -= 2) {					\
   304 		Uint32 s = *(Uint32 *)src;				\
   305 		Uint32 d = *(Uint32 *)dst;				\
   306 		*(Uint32 *)dst = ((s & (mask | mask << 16)) >> 1)	\
   307 		               + ((d & (mask | mask << 16)) >> 1)	\
   308 		               + (s & d & (~(mask | mask << 16)));	\
   309 		src += 2;						\
   310 		dst += 2;						\
   311 	    }								\
   312 	    if(n)							\
   313 		BLEND16_50(dst, src, mask); /* last odd pixel */	\
   314 	}								\
   315     } while(0)
   316 
   317 #define ALPHA_BLIT16_565_50(to, from, length, bpp, alpha)	\
   318     ALPHA_BLIT16_50(to, from, length, bpp, alpha, 0xf7de)
   319 
   320 #define ALPHA_BLIT16_555_50(to, from, length, bpp, alpha)	\
   321     ALPHA_BLIT16_50(to, from, length, bpp, alpha, 0xfbde)
   322 
   323 
   324 #define CHOOSE_BLIT(blitter, alpha, fmt)				\
   325     do {								\
   326         if(alpha == 255) {						\
   327 	    switch(fmt->BytesPerPixel) {				\
   328 	    case 1: blitter(1, Uint8, OPAQUE_BLIT); break;		\
   329 	    case 2: blitter(2, Uint8, OPAQUE_BLIT); break;		\
   330 	    case 3: blitter(3, Uint8, OPAQUE_BLIT); break;		\
   331 	    case 4: blitter(4, Uint16, OPAQUE_BLIT); break;		\
   332 	    }								\
   333 	} else {							\
   334 	    switch(fmt->BytesPerPixel) {				\
   335 	    case 1:							\
   336 		/* No 8bpp alpha blitting */				\
   337 		break;							\
   338 									\
   339 	    case 2:							\
   340 		switch(fmt->Rmask | fmt->Gmask | fmt->Bmask) {		\
   341 		case 0xffff:						\
   342 		    if(fmt->Gmask == 0x07e0				\
   343 		       || fmt->Rmask == 0x07e0				\
   344 		       || fmt->Bmask == 0x07e0) {			\
   345 			if(alpha == 128)				\
   346 			    blitter(2, Uint8, ALPHA_BLIT16_565_50);	\
   347 			else {						\
   348 			    alpha >>= 3; /* use 5 bit alpha */		\
   349 			    blitter(2, Uint8, ALPHA_BLIT16_565);	\
   350 			}						\
   351 		    } else						\
   352 			goto general16;					\
   353 		    break;						\
   354 									\
   355 		case 0x7fff:						\
   356 		    if(fmt->Gmask == 0x03e0				\
   357 		       || fmt->Rmask == 0x03e0				\
   358 		       || fmt->Bmask == 0x03e0) {			\
   359 			if(alpha == 128)				\
   360 			    blitter(2, Uint8, ALPHA_BLIT16_555_50);	\
   361 			else {						\
   362 			    alpha >>= 3; /* use 5 bit alpha */		\
   363 			    blitter(2, Uint8, ALPHA_BLIT16_555);	\
   364 			}						\
   365 			break;						\
   366 		    }							\
   367 		    /* fallthrough */					\
   368 									\
   369 		default:						\
   370 		general16:						\
   371 		    blitter(2, Uint8, ALPHA_BLIT_ANY);			\
   372 		}							\
   373 		break;							\
   374 									\
   375 	    case 3:							\
   376 		blitter(3, Uint8, ALPHA_BLIT_ANY);			\
   377 		break;							\
   378 									\
   379 	    case 4:							\
   380 		if((fmt->Rmask | fmt->Gmask | fmt->Bmask) == 0x00ffffff	\
   381 		   && (fmt->Gmask == 0xff00 || fmt->Rmask == 0xff00	\
   382 		       || fmt->Bmask == 0xff00)) {			\
   383 		    if(alpha == 128)					\
   384 			blitter(4, Uint16, ALPHA_BLIT32_888_50);	\
   385 		    else						\
   386 			blitter(4, Uint16, ALPHA_BLIT32_888);		\
   387 		} else							\
   388 		    blitter(4, Uint16, ALPHA_BLIT_ANY);			\
   389 		break;							\
   390 	    }								\
   391 	}								\
   392     } while(0)
   393 
   394 
   395 /*
   396  * This takes care of the case when the surface is clipped on the left and/or
   397  * right. Top clipping has already been taken care of.
   398  */
   399 static void RLEClipBlit(int w, Uint8 *srcbuf, SDL_Surface *dst,
   400 			Uint8 *dstbuf, SDL_Rect *srcrect, unsigned alpha)
   401 {
   402     SDL_PixelFormat *fmt = dst->format;
   403 
   404 #define RLECLIPBLIT(bpp, Type, do_blit)					   \
   405     do {								   \
   406 	int linecount = srcrect->h;					   \
   407 	int ofs = 0;							   \
   408 	int left = srcrect->x;						   \
   409 	int right = left + srcrect->w;					   \
   410 	dstbuf -= left * bpp;						   \
   411 	for(;;) {							   \
   412 	    int run;							   \
   413 	    ofs += *(Type *)srcbuf;					   \
   414 	    run = ((Type *)srcbuf)[1];					   \
   415 	    srcbuf += 2 * sizeof(Type);					   \
   416 	    if(run) {							   \
   417 		/* clip to left and right borders */			   \
   418 		if(ofs < right) {					   \
   419 		    int start = 0;					   \
   420 		    int len = run;					   \
   421 		    int startcol;					   \
   422 		    if(left - ofs > 0) {				   \
   423 			start = left - ofs;				   \
   424 			len -= start;					   \
   425 			if(len <= 0)					   \
   426 			    goto nocopy ## bpp ## do_blit;		   \
   427 		    }							   \
   428 		    startcol = ofs + start;				   \
   429 		    if(len > right - startcol)				   \
   430 			len = right - startcol;				   \
   431 		    do_blit(dstbuf + startcol * bpp, srcbuf + start * bpp, \
   432 			    len, bpp, alpha);				   \
   433 		}							   \
   434 	    nocopy ## bpp ## do_blit:					   \
   435 		srcbuf += run * bpp;					   \
   436 		ofs += run;						   \
   437 	    } else if(!ofs)						   \
   438 		break;							   \
   439 	    if(ofs == w) {						   \
   440 		ofs = 0;						   \
   441 		dstbuf += dst->pitch;					   \
   442 		if(!--linecount)					   \
   443 		    break;						   \
   444 	    }								   \
   445 	}								   \
   446     } while(0)
   447 
   448     CHOOSE_BLIT(RLECLIPBLIT, alpha, fmt);
   449 
   450 #undef RLECLIPBLIT
   451 
   452 }
   453 
   454 
   455 /* blit a colorkeyed RLE surface */
   456 int SDL_RLEBlit(SDL_Surface *src, SDL_Rect *srcrect,
   457 		SDL_Surface *dst, SDL_Rect *dstrect)
   458 {
   459 	Uint8 *dstbuf;
   460 	Uint8 *srcbuf;
   461 	int x, y;
   462 	int w = src->w;
   463 	unsigned alpha;
   464 
   465 	/* Lock the destination if necessary */
   466 	if ( dst->flags & (SDL_HWSURFACE|SDL_ASYNCBLIT) ) {
   467 		SDL_VideoDevice *video = current_video;
   468 		SDL_VideoDevice *this  = current_video;
   469 		if ( video->LockHWSurface(this, dst) < 0 ) {
   470 			return(-1);
   471 		}
   472 	}
   473 
   474 	/* Set up the source and destination pointers */
   475 	x = dstrect->x;
   476 	y = dstrect->y;
   477 	dstbuf = (Uint8 *)dst->pixels + dst->offset
   478 	         + y * dst->pitch + x * src->format->BytesPerPixel;
   479 	srcbuf = (Uint8 *)src->map->sw_data->aux_data;
   480 
   481 	{
   482 	    /* skip lines at the top if neccessary */
   483 	    int vskip = srcrect->y;
   484 	    int ofs = 0;
   485 	    if(vskip) {
   486 
   487 #define RLESKIP(bpp, Type)			\
   488 		for(;;) {			\
   489 		    int run;			\
   490 		    ofs += *(Type *)srcbuf;	\
   491 		    run = ((Type *)srcbuf)[1];	\
   492 		    srcbuf += sizeof(Type) * 2;	\
   493 		    if(run) {			\
   494 			srcbuf += run * bpp;	\
   495 			ofs += run;		\
   496 		    } else if(!ofs)		\
   497 			goto done;		\
   498 		    if(ofs == w) {		\
   499 			ofs = 0;		\
   500 			if(!--vskip)		\
   501 			    break;		\
   502 		    }				\
   503 		}
   504 
   505 		switch(src->format->BytesPerPixel) {
   506 		case 1: RLESKIP(1, Uint8); break;
   507 		case 2: RLESKIP(2, Uint8); break;
   508 		case 3: RLESKIP(3, Uint8); break;
   509 		case 4: RLESKIP(4, Uint16); break;
   510 		}
   511 
   512 #undef RLESKIP
   513 
   514 	    }
   515 	}
   516 
   517 	alpha = (src->flags & SDL_SRCALPHA) == SDL_SRCALPHA
   518 	        ? src->format->alpha : 255;
   519 	/* if left or right edge clipping needed, call clip blit */
   520 	if ( srcrect->x || srcrect->w != src->w ) {
   521 	    RLEClipBlit(w, srcbuf, dst, dstbuf, srcrect, alpha);
   522 	} else {
   523 	    SDL_PixelFormat *fmt = src->format;
   524 
   525 #define RLEBLIT(bpp, Type, do_blit)					      \
   526 	    do {							      \
   527 		int linecount = srcrect->h;				      \
   528 		int ofs = 0;						      \
   529 		for(;;) {						      \
   530 		    unsigned run;					      \
   531 		    ofs += *(Type *)srcbuf;				      \
   532 		    run = ((Type *)srcbuf)[1];				      \
   533 		    srcbuf += 2 * sizeof(Type);				      \
   534 		    if(run) {						      \
   535 			do_blit(dstbuf + ofs * bpp, srcbuf, run, bpp, alpha); \
   536 			srcbuf += run * bpp;				      \
   537 			ofs += run;					      \
   538 		    } else if(!ofs)					      \
   539 			break;						      \
   540 		    if(ofs == w) {					      \
   541 			ofs = 0;					      \
   542 			dstbuf += dst->pitch;				      \
   543 			if(!--linecount)				      \
   544 			    break;					      \
   545 		    }							      \
   546 		}							      \
   547 	    } while(0)
   548 
   549 	    CHOOSE_BLIT(RLEBLIT, alpha, fmt);
   550 
   551 #undef RLEBLIT
   552 	}
   553 
   554 done:
   555 	/* Unlock the destination if necessary */
   556 	if ( dst->flags & (SDL_HWSURFACE|SDL_ASYNCBLIT) ) {
   557 		SDL_VideoDevice *video = current_video;
   558 		SDL_VideoDevice *this  = current_video;
   559 		video->UnlockHWSurface(this, dst);
   560 	}
   561 	return(0);
   562 }
   563 
   564 #undef OPAQUE_BLIT
   565 
   566 /*
   567  * Per-pixel blitting macros for translucent pixels:
   568  * These use the same techniques as the per-surface blitting macros
   569  */
   570 
   571 /*
   572  * For 32bpp pixels, we have made sure the alpha is stored in the top
   573  * 8 bits, so proceed as usual
   574  */
   575 #define BLIT_TRANSL_888(src, dst)				\
   576     do {							\
   577         Uint32 s = src;						\
   578 	Uint32 d = dst;						\
   579 	unsigned alpha = s >> 24;				\
   580 	Uint32 s1 = s & 0xff00ff;				\
   581 	Uint32 d1 = d & 0xff00ff;				\
   582 	d1 = (d1 + ((s1 - d1) * alpha >> 8)) & 0xff00ff;	\
   583 	s &= 0xff00;						\
   584 	d &= 0xff00;						\
   585 	d = (d + ((s - d) * alpha >> 8)) & 0xff00;		\
   586 	dst = d1 | d;						\
   587     } while(0)
   588 
   589 /*
   590  * For 16bpp pixels, we have stored the 5 most significant alpha bits in
   591  * bits 5-10. As before, we can process all 3 RGB components at the same time.
   592  */
   593 #define BLIT_TRANSL_565(src, dst)		\
   594     do {					\
   595         Uint32 s = src;				\
   596 	Uint32 d = dst;				\
   597 	unsigned alpha = (s & 0x3e0) >> 5;	\
   598 	s &= 0x07e0f81f;			\
   599 	d = (d | d << 16) & 0x07e0f81f;		\
   600 	d += (s - d) * alpha >> 5;		\
   601 	d &= 0x07e0f81f;			\
   602 	dst = d | d >> 16;			\
   603     } while(0)
   604 
   605 #define BLIT_TRANSL_555(src, dst)		\
   606     do {					\
   607         Uint32 s = src;				\
   608 	Uint32 d = dst;				\
   609 	unsigned alpha = (s & 0x3e0) >> 5;	\
   610 	s &= 0x03e07c1f;			\
   611 	d = (d | d << 16) & 0x03e07c1f;		\
   612 	d += (s - d) * alpha >> 5;		\
   613 	d &= 0x03e07c1f;			\
   614 	dst = d | d >> 16;			\
   615     } while(0)
   616 
   617 /* used to save the destination format in the encoding. Designed to be
   618    macro-compatible with SDL_PixelFormat but without the unneeded fields */
   619 typedef struct {
   620     	Uint8  BytesPerPixel;
   621 	Uint8  Rloss;
   622 	Uint8  Gloss;
   623 	Uint8  Bloss;
   624 	Uint8  Rshift;
   625 	Uint8  Gshift;
   626 	Uint8  Bshift;
   627 	Uint8  Ashift;
   628 	Uint32 Rmask;
   629 	Uint32 Gmask;
   630 	Uint32 Bmask;
   631 	Uint32 Amask;
   632 } RLEDestFormat;
   633 
   634 /* blit a pixel-alpha RLE surface clipped at the right and/or left edges */
   635 static void RLEAlphaClipBlit(int w, Uint8 *srcbuf, SDL_Surface *dst,
   636 			     Uint8 *dstbuf, SDL_Rect *srcrect)
   637 {
   638     SDL_PixelFormat *df = dst->format;
   639     /*
   640      * clipped blitter: Ptype is the destination pixel type,
   641      * Ctype the translucent count type, and do_blend the macro
   642      * to blend one pixel.
   643      */
   644 #define RLEALPHACLIPBLIT(Ptype, Ctype, do_blend)			  \
   645     do {								  \
   646 	int linecount = srcrect->h;					  \
   647 	int left = srcrect->x;						  \
   648 	int right = left + srcrect->w;					  \
   649 	dstbuf -= left * sizeof(Ptype);					  \
   650 	do {								  \
   651 	    int ofs = 0;						  \
   652 	    /* blit opaque pixels on one line */			  \
   653 	    do {							  \
   654 		unsigned run;						  \
   655 		ofs += ((Ctype *)srcbuf)[0];				  \
   656 		run = ((Ctype *)srcbuf)[1];				  \
   657 		srcbuf += 2 * sizeof(Ctype);				  \
   658 		if(run) {						  \
   659 		    /* clip to left and right borders */		  \
   660 		    int cofs = ofs;					  \
   661 		    int crun = run;					  \
   662 		    if(left - cofs > 0) {				  \
   663 			crun -= left - cofs;				  \
   664 			cofs = left;					  \
   665 		    }							  \
   666 		    if(crun > right - cofs)				  \
   667 			crun = right - cofs;				  \
   668 		    if(crun > 0)					  \
   669 			PIXEL_COPY(dstbuf + cofs * sizeof(Ptype),	  \
   670 				   srcbuf + (cofs - ofs) * sizeof(Ptype), \
   671 				   (unsigned)crun, sizeof(Ptype));	  \
   672 		    srcbuf += run * sizeof(Ptype);			  \
   673 		    ofs += run;						  \
   674 		} else if(!ofs)						  \
   675 		    return;						  \
   676 	    } while(ofs < w);						  \
   677 	    /* skip padding if necessary */				  \
   678 	    if(sizeof(Ptype) == 2)					  \
   679 		srcbuf += (unsigned long)srcbuf & 2;			  \
   680 	    /* blit translucent pixels on the same line */		  \
   681 	    ofs = 0;							  \
   682 	    do {							  \
   683 		unsigned run;						  \
   684 		ofs += ((Uint16 *)srcbuf)[0];				  \
   685 		run = ((Uint16 *)srcbuf)[1];				  \
   686 		srcbuf += 4;						  \
   687 		if(run) {						  \
   688 		    /* clip to left and right borders */		  \
   689 		    int cofs = ofs;					  \
   690 		    int crun = run;					  \
   691 		    if(left - cofs > 0) {				  \
   692 			crun -= left - cofs;				  \
   693 			cofs = left;					  \
   694 		    }							  \
   695 		    if(crun > right - cofs)				  \
   696 			crun = right - cofs;				  \
   697 		    if(crun > 0) {					  \
   698 			Ptype *dst = (Ptype *)dstbuf + cofs;		  \
   699 			Uint32 *src = (Uint32 *)srcbuf + (cofs - ofs);	  \
   700 			int i;						  \
   701 			for(i = 0; i < crun; i++)			  \
   702 			    do_blend(src[i], dst[i]);			  \
   703 		    }							  \
   704 		    srcbuf += run * 4;					  \
   705 		    ofs += run;						  \
   706 		}							  \
   707 	    } while(ofs < w);						  \
   708 	    dstbuf += dst->pitch;					  \
   709 	} while(--linecount);						  \
   710     } while(0)
   711 
   712     switch(df->BytesPerPixel) {
   713     case 2:
   714 	if(df->Gmask == 0x07e0 || df->Rmask == 0x07e0
   715 	   || df->Bmask == 0x07e0)
   716 	    RLEALPHACLIPBLIT(Uint16, Uint8, BLIT_TRANSL_565);
   717 	else
   718 	    RLEALPHACLIPBLIT(Uint16, Uint8, BLIT_TRANSL_555);
   719 	break;
   720     case 4:
   721 	RLEALPHACLIPBLIT(Uint32, Uint16, BLIT_TRANSL_888);
   722 	break;
   723     }
   724 }
   725 
   726 /* blit a pixel-alpha RLE surface */
   727 int SDL_RLEAlphaBlit(SDL_Surface *src, SDL_Rect *srcrect,
   728 		     SDL_Surface *dst, SDL_Rect *dstrect)
   729 {
   730     int x, y;
   731     int w = src->w;
   732     Uint8 *srcbuf, *dstbuf;
   733     SDL_PixelFormat *df = dst->format;
   734 
   735     /* Lock the destination if necessary */
   736     if(dst->flags & (SDL_HWSURFACE|SDL_ASYNCBLIT)) {
   737 	SDL_VideoDevice *video = current_video;
   738 	SDL_VideoDevice *this  = current_video;
   739 	if(video->LockHWSurface(this, dst) < 0) {
   740 	    return -1;
   741 	}
   742     }
   743 
   744     x = dstrect->x;
   745     y = dstrect->y;
   746     dstbuf = (Uint8 *)dst->pixels + dst->offset
   747 	     + y * dst->pitch + x * df->BytesPerPixel;
   748     srcbuf = (Uint8 *)src->map->sw_data->aux_data + sizeof(RLEDestFormat);
   749 
   750     {
   751 	/* skip lines at the top if necessary */
   752 	int vskip = srcrect->y;
   753 	if(vskip) {
   754 	    int ofs;
   755 	    if(df->BytesPerPixel == 2) {
   756 		/* the 16/32 interleaved format */
   757 		do {
   758 		    /* skip opaque line */
   759 		    ofs = 0;
   760 		    do {
   761 			int run;
   762 			ofs += srcbuf[0];
   763 			run = srcbuf[1];
   764 			srcbuf += 2;
   765 			if(run) {
   766 			    srcbuf += 2 * run;
   767 			    ofs += run;
   768 			} else if(!ofs)
   769 			    goto done;
   770 		    } while(ofs < w);
   771 
   772 		    /* skip padding */
   773 		    srcbuf += (unsigned long)srcbuf & 2;
   774 
   775 		    /* skip translucent line */
   776 		    ofs = 0;
   777 		    do {
   778 			int run;
   779 			ofs += ((Uint16 *)srcbuf)[0];
   780 			run = ((Uint16 *)srcbuf)[1];
   781 			srcbuf += 4 * (run + 1);
   782 			ofs += run;
   783 		    } while(ofs < w);
   784 		} while(--vskip);
   785 	    } else {
   786 		/* the 32/32 interleaved format */
   787 		vskip <<= 1;	/* opaque and translucent have same format */
   788 		do {
   789 		    ofs = 0;
   790 		    do {
   791 			int run;
   792 			ofs += ((Uint16 *)srcbuf)[0];
   793 			run = ((Uint16 *)srcbuf)[1];
   794 			srcbuf += 4;
   795 			if(run) {
   796 			    srcbuf += 4 * run;
   797 			    ofs += run;
   798 			} else if(!ofs)
   799 			    goto done;
   800 		    } while(ofs < w);
   801 		} while(--vskip);
   802 	    }
   803 	}
   804     }
   805 
   806     /* if left or right edge clipping needed, call clip blit */
   807     if(srcrect->x || srcrect->w != src->w) {
   808 	RLEAlphaClipBlit(w, srcbuf, dst, dstbuf, srcrect);
   809     } else {
   810 
   811 	/*
   812 	 * non-clipped blitter. Ptype is the destination pixel type,
   813 	 * Ctype the translucent count type, and do_blend the
   814 	 * macro to blend one pixel.
   815 	 */
   816 #define RLEALPHABLIT(Ptype, Ctype, do_blend)				 \
   817 	do {								 \
   818 	    int linecount = srcrect->h;					 \
   819 	    do {							 \
   820 		int ofs = 0;						 \
   821 		/* blit opaque pixels on one line */			 \
   822 		do {							 \
   823 		    unsigned run;					 \
   824 		    ofs += ((Ctype *)srcbuf)[0];			 \
   825 		    run = ((Ctype *)srcbuf)[1];				 \
   826 		    srcbuf += 2 * sizeof(Ctype);			 \
   827 		    if(run) {						 \
   828 			PIXEL_COPY(dstbuf + ofs * sizeof(Ptype), srcbuf, \
   829 				   run, sizeof(Ptype));			 \
   830 			srcbuf += run * sizeof(Ptype);			 \
   831 			ofs += run;					 \
   832 		    } else if(!ofs)					 \
   833 			goto done;					 \
   834 		} while(ofs < w);					 \
   835 		/* skip padding if necessary */				 \
   836 		if(sizeof(Ptype) == 2)					 \
   837 		    srcbuf += (unsigned long)srcbuf & 2;		 \
   838 		/* blit translucent pixels on the same line */		 \
   839 		ofs = 0;						 \
   840 		do {							 \
   841 		    unsigned run;					 \
   842 		    ofs += ((Uint16 *)srcbuf)[0];			 \
   843 		    run = ((Uint16 *)srcbuf)[1];			 \
   844 		    srcbuf += 4;					 \
   845 		    if(run) {						 \
   846 			Ptype *dst = (Ptype *)dstbuf + ofs;		 \
   847 			unsigned i;					 \
   848 			for(i = 0; i < run; i++) {			 \
   849 			    Uint32 src = *(Uint32 *)srcbuf;		 \
   850 			    do_blend(src, *dst);			 \
   851 			    srcbuf += 4;				 \
   852 			    dst++;					 \
   853 			}						 \
   854 			ofs += run;					 \
   855 		    }							 \
   856 		} while(ofs < w);					 \
   857 		dstbuf += dst->pitch;					 \
   858 	    } while(--linecount);					 \
   859 	} while(0)
   860 
   861 	switch(df->BytesPerPixel) {
   862 	case 2:
   863 	    if(df->Gmask == 0x07e0 || df->Rmask == 0x07e0
   864 	       || df->Bmask == 0x07e0)
   865 		RLEALPHABLIT(Uint16, Uint8, BLIT_TRANSL_565);
   866 	    else
   867 		RLEALPHABLIT(Uint16, Uint8, BLIT_TRANSL_555);
   868 	    break;
   869 	case 4:
   870 	    RLEALPHABLIT(Uint32, Uint16, BLIT_TRANSL_888);
   871 	    break;
   872 	}
   873     }
   874 
   875  done:
   876     /* Unlock the destination if necessary */
   877     if(dst->flags & (SDL_HWSURFACE|SDL_ASYNCBLIT)) {
   878 	SDL_VideoDevice *video = current_video;
   879 	SDL_VideoDevice *this  = current_video;
   880 	video->UnlockHWSurface(this, dst);
   881     }
   882     return 0;
   883 }
   884 
   885 /*
   886  * Auxiliary functions:
   887  * The encoding functions take 32bpp rgb + a, and
   888  * return the number of bytes copied to the destination.
   889  * The decoding functions copy to 32bpp rgb + a, and
   890  * return the number of bytes copied from the source.
   891  * These are only used in the encoder and un-RLE code and are therefore not
   892  * highly optimised.
   893  */
   894 
   895 /* encode 32bpp rgb + a into 16bpp rgb, losing alpha */
   896 static int copy_opaque_16(void *dst, Uint32 *src, int n,
   897 			  SDL_PixelFormat *sfmt, SDL_PixelFormat *dfmt)
   898 {
   899     int i;
   900     Uint16 *d = dst;
   901     for(i = 0; i < n; i++) {
   902 	unsigned r, g, b;
   903 	RGB_FROM_PIXEL(*src, sfmt, r, g, b);
   904 	PIXEL_FROM_RGB(*d, dfmt, r, g, b);
   905 	src++;
   906 	d++;
   907     }
   908     return n * 2;
   909 }
   910 
   911 /* decode opaque pixels from 16bpp to 32bpp rgb + a */
   912 static int uncopy_opaque_16(Uint32 *dst, void *src, int n,
   913 			    RLEDestFormat *sfmt, SDL_PixelFormat *dfmt)
   914 {
   915     int i;
   916     Uint16 *s = src;
   917     unsigned alpha = dfmt->Amask ? 255 : 0;
   918     for(i = 0; i < n; i++) {
   919 	unsigned r, g, b;
   920 	RGB_FROM_PIXEL(*s, sfmt, r, g, b);
   921 	PIXEL_FROM_RGBA(*dst, dfmt, r, g, b, alpha);
   922 	s++;
   923 	dst++;
   924     }
   925     return n * 2;
   926 }
   927 
   928 
   929 
   930 /* encode 32bpp rgb + a into 32bpp G0RAB format for blitting into 565 */
   931 static int copy_transl_565(void *dst, Uint32 *src, int n,
   932 			   SDL_PixelFormat *sfmt, SDL_PixelFormat *dfmt)
   933 {
   934     int i;
   935     Uint32 *d = dst;
   936     for(i = 0; i < n; i++) {
   937 	unsigned r, g, b, a;
   938 	Uint16 pix;
   939 	RGBA_FROM_8888(*src, sfmt, r, g, b, a);
   940 	PIXEL_FROM_RGB(pix, dfmt, r, g, b);
   941 	*d = ((pix & 0x7e0) << 16) | (pix & 0xf81f) | ((a << 2) & 0x7e0);
   942 	src++;
   943 	d++;
   944     }
   945     return n * 4;
   946 }
   947 
   948 /* encode 32bpp rgb + a into 32bpp G0RAB format for blitting into 555 */
   949 static int copy_transl_555(void *dst, Uint32 *src, int n,
   950 			   SDL_PixelFormat *sfmt, SDL_PixelFormat *dfmt)
   951 {
   952     int i;
   953     Uint32 *d = dst;
   954     for(i = 0; i < n; i++) {
   955 	unsigned r, g, b, a;
   956 	Uint16 pix;
   957 	RGBA_FROM_8888(*src, sfmt, r, g, b, a);
   958 	PIXEL_FROM_RGB(pix, dfmt, r, g, b);
   959 	*d = ((pix & 0x3e0) << 16) | (pix & 0xfc1f) | ((a << 2) & 0x3e0);
   960 	src++;
   961 	d++;
   962     }
   963     return n * 4;
   964 }
   965 
   966 /* decode translucent pixels from 32bpp GORAB to 32bpp rgb + a */
   967 static int uncopy_transl_16(Uint32 *dst, void *src, int n,
   968 			    RLEDestFormat *sfmt, SDL_PixelFormat *dfmt)
   969 {
   970     int i;
   971     Uint32 *s = src;
   972     for(i = 0; i < n; i++) {
   973 	unsigned r, g, b, a;
   974 	Uint32 pix = *s++;
   975 	a = (pix & 0x3e0) >> 2;
   976 	pix = (pix & ~0x3e0) | pix >> 16;
   977 	RGB_FROM_PIXEL(pix, sfmt, r, g, b);
   978 	PIXEL_FROM_RGBA(*dst, dfmt, r, g, b, a);
   979 	dst++;
   980     }
   981     return n * 4;
   982 }
   983 
   984 /* encode 32bpp rgba into 32bpp rgba, keeping alpha (dual purpose) */
   985 static int copy_32(void *dst, Uint32 *src, int n,
   986 		   SDL_PixelFormat *sfmt, SDL_PixelFormat *dfmt)
   987 {
   988     int i;
   989     Uint32 *d = dst;
   990     for(i = 0; i < n; i++) {
   991 	unsigned r, g, b, a;
   992 	Uint32 pixel;
   993 	RGBA_FROM_8888(*src, sfmt, r, g, b, a);
   994 	PIXEL_FROM_RGB(pixel, dfmt, r, g, b);
   995 	*d++ = pixel | a << 24;
   996 	src++;
   997     }
   998     return n * 4;
   999 }
  1000 
  1001 /* decode 32bpp rgba into 32bpp rgba, keeping alpha (dual purpose) */
  1002 static int uncopy_32(Uint32 *dst, void *src, int n,
  1003 		     RLEDestFormat *sfmt, SDL_PixelFormat *dfmt)
  1004 {
  1005     int i;
  1006     Uint32 *s = src;
  1007     for(i = 0; i < n; i++) {
  1008 	unsigned r, g, b, a;
  1009 	Uint32 pixel = *s++;
  1010 	RGB_FROM_PIXEL(pixel, sfmt, r, g, b);
  1011 	a = pixel >> 24;
  1012 	PIXEL_FROM_RGBA(*dst, dfmt, r, g, b, a);
  1013 	dst++;
  1014     }
  1015     return n * 4;
  1016 }
  1017 
  1018 #define ISOPAQUE(pixel, fmt) ((((pixel) & fmt->Amask) >> fmt->Ashift) == 255)
  1019 
  1020 #define ISTRANSL(pixel, fmt)	\
  1021     ((unsigned)((((pixel) & fmt->Amask) >> fmt->Ashift) - 1U) < 254U)
  1022 
  1023 /* convert surface to be quickly alpha-blittable onto dest, if possible */
  1024 static int RLEAlphaSurface(SDL_Surface *surface)
  1025 {
  1026     SDL_Surface *dest;
  1027     SDL_PixelFormat *df;
  1028     int maxsize = 0;
  1029     int max_opaque_run;
  1030     int max_transl_run = 65535;
  1031     unsigned masksum;
  1032     Uint8 *rlebuf, *dst;
  1033     int (*copy_opaque)(void *, Uint32 *, int,
  1034 		       SDL_PixelFormat *, SDL_PixelFormat *);
  1035     int (*copy_transl)(void *, Uint32 *, int,
  1036 		       SDL_PixelFormat *, SDL_PixelFormat *);
  1037 
  1038     dest = surface->map->dst;
  1039     if(!dest)
  1040 	return -1;
  1041     df = dest->format;
  1042     if(surface->format->BitsPerPixel != 32)
  1043 	return -1;		/* only 32bpp source supported */
  1044 
  1045     /* find out whether the destination is one we support,
  1046        and determine the max size of the encoded result */
  1047     masksum = df->Rmask | df->Gmask | df->Bmask;
  1048     switch(df->BytesPerPixel) {
  1049     case 2:
  1050 	/* 16bpp: only support 565 and 555 formats */
  1051 	switch(masksum) {
  1052 	case 0xffff:
  1053 	    if(df->Gmask == 0x07e0
  1054 	       || df->Rmask == 0x07e0 || df->Bmask == 0x07e0) {
  1055 		copy_opaque = copy_opaque_16;
  1056 		copy_transl = copy_transl_565;
  1057 	    } else
  1058 		return -1;
  1059 	    break;
  1060 	case 0x7fff:
  1061 	    if(df->Gmask == 0x03e0
  1062 	       || df->Rmask == 0x03e0 || df->Bmask == 0x03e0) {
  1063 		copy_opaque = copy_opaque_16;
  1064 		copy_transl = copy_transl_555;
  1065 	    } else
  1066 		return -1;
  1067 	    break;
  1068 	default:
  1069 	    return -1;
  1070 	}
  1071 	max_opaque_run = 255;	/* runs stored as bytes */
  1072 
  1073 	/* worst case is alternating opaque and translucent pixels,
  1074 	   with room for alignment padding between lines */
  1075 	maxsize = surface->h * (2 + (4 + 2) * (surface->w + 1)) + 2;
  1076 	break;
  1077     case 4:
  1078 	if(masksum != 0x00ffffff)
  1079 	    return -1;		/* requires unused high byte */
  1080 	copy_opaque = copy_32;
  1081 	copy_transl = copy_32;
  1082 	max_opaque_run = 255;	/* runs stored as short ints */
  1083 
  1084 	/* worst case is alternating opaque and translucent pixels */
  1085 	maxsize = surface->h * 2 * 4 * (surface->w + 1) + 4;
  1086 	break;
  1087     default:
  1088 	return -1;		/* anything else unsupported right now */
  1089     }
  1090 
  1091     maxsize += sizeof(RLEDestFormat);
  1092     rlebuf = (Uint8 *)malloc(maxsize);
  1093     if(!rlebuf) {
  1094 	SDL_OutOfMemory();
  1095 	return -1;
  1096     }
  1097     {
  1098 	/* save the destination format so we can undo the encoding later */
  1099 	RLEDestFormat *r = (RLEDestFormat *)rlebuf;
  1100 	r->BytesPerPixel = df->BytesPerPixel;
  1101 	r->Rloss = df->Rloss;
  1102 	r->Gloss = df->Gloss;
  1103 	r->Bloss = df->Bloss;
  1104 	r->Rshift = df->Rshift;
  1105 	r->Gshift = df->Gshift;
  1106 	r->Bshift = df->Bshift;
  1107 	r->Ashift = df->Ashift;
  1108 	r->Rmask = df->Rmask;
  1109 	r->Gmask = df->Gmask;
  1110 	r->Bmask = df->Bmask;
  1111 	r->Amask = df->Amask;
  1112     }
  1113     dst = rlebuf + sizeof(RLEDestFormat);
  1114 
  1115     /* Do the actual encoding */
  1116     {
  1117 	int x, y;
  1118 	int h = surface->h, w = surface->w;
  1119 	SDL_PixelFormat *sf = surface->format;
  1120 	Uint32 *src = (Uint32 *)((Uint8 *)surface->pixels + surface->offset);
  1121 	Uint8 *lastline = dst;	/* end of last non-blank line */
  1122 
  1123 	/* opaque counts are 8 or 16 bits, depending on target depth */
  1124 #define ADD_OPAQUE_COUNTS(n, m)			\
  1125 	if(df->BytesPerPixel == 4) {		\
  1126 	    ((Uint16 *)dst)[0] = n;		\
  1127 	    ((Uint16 *)dst)[1] = m;		\
  1128 	    dst += 4;				\
  1129 	} else {				\
  1130 	    dst[0] = n;				\
  1131 	    dst[1] = m;				\
  1132 	    dst += 2;				\
  1133 	}
  1134 
  1135 	/* translucent counts are always 16 bit */
  1136 #define ADD_TRANSL_COUNTS(n, m)		\
  1137 	(((Uint16 *)dst)[0] = n, ((Uint16 *)dst)[1] = m, dst += 4)
  1138 
  1139 	for(y = 0; y < h; y++) {
  1140 	    int runstart, skipstart;
  1141 	    int blankline = 0;
  1142 	    /* First encode all opaque pixels of a scan line */
  1143 	    x = 0;
  1144 	    do {
  1145 		int run, skip, len;
  1146 		skipstart = x;
  1147 		while(x < w && !ISOPAQUE(src[x], sf))
  1148 		    x++;
  1149 		runstart = x;
  1150 		while(x < w && ISOPAQUE(src[x], sf))
  1151 		    x++;
  1152 		skip = runstart - skipstart;
  1153 		if(skip == w)
  1154 		    blankline = 1;
  1155 		run = x - runstart;
  1156 		while(skip > max_opaque_run) {
  1157 		    ADD_OPAQUE_COUNTS(max_opaque_run, 0);
  1158 		    skip -= max_opaque_run;
  1159 		}
  1160 		len = MIN(run, max_opaque_run);
  1161 		ADD_OPAQUE_COUNTS(skip, len);
  1162 		dst += copy_opaque(dst, src + runstart, len, sf, df);
  1163 		runstart += len;
  1164 		run -= len;
  1165 		while(run) {
  1166 		    len = MIN(run, max_opaque_run);
  1167 		    ADD_OPAQUE_COUNTS(0, len);
  1168 		    dst += copy_opaque(dst, src + runstart, len, sf, df);
  1169 		    runstart += len;
  1170 		    run -= len;
  1171 		}
  1172 	    } while(x < w);
  1173 
  1174 	    /* Make sure the next output address is 32-bit aligned */
  1175 	    dst += (unsigned long)dst & 2;
  1176 
  1177 	    /* Next, encode all translucent pixels of the same scan line */
  1178 	    x = 0;
  1179 	    do {
  1180 		int run, skip, len;
  1181 		skipstart = x;
  1182 		while(x < w && !ISTRANSL(src[x], sf))
  1183 		    x++;
  1184 		runstart = x;
  1185 		while(x < w && ISTRANSL(src[x], sf))
  1186 		    x++;
  1187 		skip = runstart - skipstart;
  1188 		blankline &= (skip == w);
  1189 		run = x - runstart;
  1190 		while(skip > max_transl_run) {
  1191 		    ADD_TRANSL_COUNTS(max_transl_run, 0);
  1192 		    skip -= max_transl_run;
  1193 		}
  1194 		len = MIN(run, max_transl_run);
  1195 		ADD_TRANSL_COUNTS(skip, len);
  1196 		dst += copy_transl(dst, src + runstart, len, sf, df);
  1197 		runstart += len;
  1198 		run -= len;
  1199 		while(run) {
  1200 		    len = MIN(run, max_transl_run);
  1201 		    ADD_TRANSL_COUNTS(0, len);
  1202 		    dst += copy_transl(dst, src + runstart, len, sf, df);
  1203 		    runstart += len;
  1204 		    run -= len;
  1205 		}
  1206 		if(!blankline)
  1207 		    lastline = dst;
  1208 	    } while(x < w);
  1209 
  1210 	    src += surface->pitch >> 2;
  1211 	}
  1212 	dst = lastline;		/* back up past trailing blank lines */
  1213 	ADD_OPAQUE_COUNTS(0, 0);
  1214     }
  1215 
  1216 #undef ADD_OPAQUE_COUNTS
  1217 #undef ADD_TRANSL_COUNTS
  1218 
  1219     /* Now that we have it encoded, release the original pixels */
  1220     if((surface->flags & SDL_PREALLOC) != SDL_PREALLOC
  1221        && (surface->flags & SDL_HWSURFACE) != SDL_HWSURFACE) {
  1222 	free( surface->pixels );
  1223 	surface->pixels = NULL;
  1224     }
  1225 
  1226     /* realloc the buffer to release unused memory */
  1227     {
  1228 	Uint8 *p = realloc(rlebuf, dst - rlebuf);
  1229 	if(!p)
  1230 	    p = rlebuf;
  1231 	surface->map->sw_data->aux_data = p;
  1232     }
  1233 
  1234     return 0;
  1235 }
  1236 
  1237 static Uint32 getpix_8(Uint8 *srcbuf)
  1238 {
  1239     return *srcbuf;
  1240 }
  1241 
  1242 static Uint32 getpix_16(Uint8 *srcbuf)
  1243 {
  1244     return *(Uint16 *)srcbuf;
  1245 }
  1246 
  1247 static Uint32 getpix_24(Uint8 *srcbuf)
  1248 {
  1249     if(SDL_BYTEORDER == SDL_LIL_ENDIAN)
  1250 	return srcbuf[0] + (srcbuf[1] << 8) + (srcbuf[2] << 16);
  1251     else
  1252 	return (srcbuf[0] << 16) + (srcbuf[1] << 8) + srcbuf[2];
  1253 }
  1254 
  1255 static Uint32 getpix_32(Uint8 *srcbuf)
  1256 {
  1257     return *(Uint32 *)srcbuf;
  1258 }
  1259 
  1260 typedef Uint32 (*getpix_func)(Uint8 *);
  1261 
  1262 static getpix_func getpixes[4] = {
  1263     getpix_8, getpix_16, getpix_24, getpix_32
  1264 };
  1265 
  1266 static int RLEColorkeySurface(SDL_Surface *surface)
  1267 {
  1268         Uint8 *rlebuf, *dst;
  1269 	int maxn;
  1270 	int y;
  1271 	Uint8 *srcbuf, *curbuf, *lastline;
  1272 	int maxsize = 0;
  1273 	int skip, run;
  1274 	int bpp = surface->format->BytesPerPixel;
  1275 	getpix_func getpix;
  1276 	Uint32 ckey, rgbmask;
  1277 	int w, h;
  1278 
  1279 	/* calculate the worst case size for the compressed surface */
  1280 	switch(bpp) {
  1281 	case 1:
  1282 	    /* worst case is alternating opaque and transparent pixels,
  1283 	       starting with an opaque pixel */
  1284 	    maxsize = surface->h * 3 * (surface->w / 2 + 1) + 2;
  1285 	    break;
  1286 	case 2:
  1287 	case 3:
  1288 	    /* worst case is solid runs, at most 255 pixels wide */
  1289 	    maxsize = surface->h * (2 * (surface->w / 255 + 1)
  1290 				    + surface->w * bpp) + 2;
  1291 	    break;
  1292 	case 4:
  1293 	    /* worst case is solid runs, at most 65535 pixels wide */
  1294 	    maxsize = surface->h * (4 * (surface->w / 65535 + 1)
  1295 				    + surface->w * 4) + 4;
  1296 	    break;
  1297 	}
  1298 
  1299 	rlebuf = (Uint8 *)malloc(maxsize);
  1300 	if ( rlebuf == NULL ) {
  1301 		SDL_OutOfMemory();
  1302 		return(-1);
  1303 	}
  1304 
  1305 	/* Set up the conversion */
  1306 	srcbuf = (Uint8 *)surface->pixels+surface->offset;
  1307 	curbuf = srcbuf;
  1308 	maxn = bpp == 4 ? 65535 : 255;
  1309 	skip = run = 0;
  1310 	dst = rlebuf;
  1311 	rgbmask = ~surface->format->Amask;
  1312 	ckey = surface->format->colorkey & rgbmask;
  1313 	lastline = dst;
  1314 	getpix = getpixes[bpp - 1];
  1315 	w = surface->w;
  1316 	h = surface->h;
  1317 
  1318 #define ADD_COUNTS(n, m)			\
  1319 	if(bpp == 4) {				\
  1320 	    ((Uint16 *)dst)[0] = n;		\
  1321 	    ((Uint16 *)dst)[1] = m;		\
  1322 	    dst += 4;				\
  1323 	} else {				\
  1324 	    dst[0] = n;				\
  1325 	    dst[1] = m;				\
  1326 	    dst += 2;				\
  1327 	}
  1328 
  1329 	for(y = 0; y < h; y++) {
  1330 	    int x = 0;
  1331 	    int blankline = 0;
  1332 	    do {
  1333 		int run, skip, len;
  1334 		int runstart;
  1335 		int skipstart = x;
  1336 
  1337 		/* find run of transparent, then opaque pixels */
  1338 		while(x < w && (getpix(srcbuf + x * bpp) & rgbmask) == ckey)
  1339 		    x++;
  1340 		runstart = x;
  1341 		while(x < w && (getpix(srcbuf + x * bpp) & rgbmask) != ckey)
  1342 		    x++;
  1343 		skip = runstart - skipstart;
  1344 		if(skip == w)
  1345 		    blankline = 1;
  1346 		run = x - runstart;
  1347 
  1348 		/* encode segment */
  1349 		while(skip > maxn) {
  1350 		    ADD_COUNTS(maxn, 0);
  1351 		    skip -= maxn;
  1352 		}
  1353 		len = MIN(run, maxn);
  1354 		ADD_COUNTS(skip, len);
  1355 		memcpy(dst, srcbuf + runstart * bpp, len * bpp);
  1356 		dst += len * bpp;
  1357 		run -= len;
  1358 		runstart += len;
  1359 		while(run) {
  1360 		    len = MIN(run, maxn);
  1361 		    ADD_COUNTS(0, len);
  1362 		    memcpy(dst, srcbuf + runstart * bpp, len * bpp);
  1363 		    dst += len * bpp;
  1364 		    runstart += len;
  1365 		    run -= len;
  1366 		}
  1367 		if(!blankline)
  1368 		    lastline = dst;
  1369 	    } while(x < w);
  1370 
  1371 	    srcbuf += surface->pitch;
  1372 	}
  1373 	dst = lastline;		/* back up bast trailing blank lines */
  1374 	ADD_COUNTS(0, 0);
  1375 
  1376 #undef ADD_COUNTS
  1377 
  1378 	/* Now that we have it encoded, release the original pixels */
  1379 	if((surface->flags & SDL_PREALLOC) != SDL_PREALLOC
  1380 	   && (surface->flags & SDL_HWSURFACE) != SDL_HWSURFACE) {
  1381 	    free( surface->pixels );
  1382 	    surface->pixels = NULL;
  1383 	}
  1384 
  1385 	/* realloc the buffer to release unused memory */
  1386 	{
  1387 	    /* If realloc returns NULL, the original block is left intact */
  1388 	    Uint8 *p = realloc(rlebuf, dst - rlebuf);
  1389 	    if(!p)
  1390 		p = rlebuf;
  1391 	    surface->map->sw_data->aux_data = p;
  1392 	}
  1393 
  1394 	return(0);
  1395 }
  1396 
  1397 int SDL_RLESurface(SDL_Surface *surface)
  1398 {
  1399 	int retcode;
  1400 
  1401 	/* Clear any previous RLE conversion */
  1402 	if ( (surface->flags & SDL_RLEACCEL) == SDL_RLEACCEL ) {
  1403 		SDL_UnRLESurface(surface, 1);
  1404 	}
  1405 
  1406 	/* We don't support RLE encoding of bitmaps */
  1407 	if ( surface->format->BitsPerPixel < 8 ) {
  1408 		return(-1);
  1409 	}
  1410 
  1411 	/* Lock the surface if it's in hardware */
  1412 	if ( surface->flags & (SDL_HWSURFACE|SDL_ASYNCBLIT) ) {
  1413 		SDL_VideoDevice *video = current_video;
  1414 		SDL_VideoDevice *this  = current_video;
  1415 		if ( video->LockHWSurface(this, surface) < 0 ) {
  1416 			return(-1);
  1417 		}
  1418 	}
  1419 
  1420 	/* Encode */
  1421 	if((surface->flags & SDL_SRCCOLORKEY) == SDL_SRCCOLORKEY) {
  1422 	    retcode = RLEColorkeySurface(surface);
  1423 	} else {
  1424 	    if((surface->flags & SDL_SRCALPHA) == SDL_SRCALPHA
  1425 	       && surface->format->Amask != 0)
  1426 		retcode = RLEAlphaSurface(surface);
  1427 	    else
  1428 		retcode = -1;	/* no RLE for per-surface alpha sans ckey */
  1429 	}
  1430 
  1431 	/* Unlock the surface if it's in hardware */
  1432 	if ( surface->flags & (SDL_HWSURFACE|SDL_ASYNCBLIT) ) {
  1433 		SDL_VideoDevice *video = current_video;
  1434 		SDL_VideoDevice *this  = current_video;
  1435 		video->UnlockHWSurface(this, surface);
  1436 	}
  1437 
  1438 	if(retcode < 0)
  1439 	    return -1;
  1440 
  1441 	/* The surface is now accelerated */
  1442 	surface->flags |= SDL_RLEACCEL;
  1443 
  1444 	return(0);
  1445 }
  1446 
  1447 /*
  1448  * Un-RLE a surface with pixel alpha
  1449  * This may not give back exactly the image before RLE-encoding; all
  1450  * completely transparent pixels will be lost, and colour and alpha depth
  1451  * may have been reduced (when encoding for 16bpp targets).
  1452  */
  1453 static void UnRLEAlpha(SDL_Surface *surface)
  1454 {
  1455     Uint8 *srcbuf;
  1456     Uint32 *dst;
  1457     SDL_PixelFormat *sf = surface->format;
  1458     RLEDestFormat *df = surface->map->sw_data->aux_data;
  1459     int (*uncopy_opaque)(Uint32 *, void *, int,
  1460 			 RLEDestFormat *, SDL_PixelFormat *);
  1461     int (*uncopy_transl)(Uint32 *, void *, int,
  1462 			 RLEDestFormat *, SDL_PixelFormat *);
  1463     int w = surface->w;
  1464     int bpp = df->BytesPerPixel;
  1465 
  1466     if(bpp == 2) {
  1467 	uncopy_opaque = uncopy_opaque_16;
  1468 	uncopy_transl = uncopy_transl_16;
  1469     } else {
  1470 	uncopy_opaque = uncopy_transl = uncopy_32;
  1471     }
  1472 
  1473     surface->pixels = malloc(surface->h * surface->pitch);
  1474     /* fill background with transparent pixels */
  1475     memset(surface->pixels, 0, surface->h * surface->pitch);
  1476 
  1477     dst = surface->pixels;
  1478     srcbuf = (Uint8 *)(df + 1);
  1479     for(;;) {
  1480 	/* copy opaque pixels */
  1481 	int ofs = 0;
  1482 	do {
  1483 	    unsigned run;
  1484 	    if(bpp == 2) {
  1485 		ofs += srcbuf[0];
  1486 		run = srcbuf[1];
  1487 		srcbuf += 2;
  1488 	    } else {
  1489 		ofs += ((Uint16 *)srcbuf)[0];
  1490 		run = ((Uint16 *)srcbuf)[1];
  1491 		srcbuf += 4;
  1492 	    }
  1493 	    if(run) {
  1494 		srcbuf += uncopy_opaque(dst + ofs, srcbuf, run, df, sf);
  1495 		ofs += run;
  1496 	    } else if(!ofs)
  1497 		return;
  1498 	} while(ofs < w);
  1499 
  1500 	/* skip padding if needed */
  1501 	if(bpp == 2)
  1502 	    srcbuf += (unsigned long)srcbuf & 2;
  1503 	
  1504 	/* copy translucent pixels */
  1505 	ofs = 0;
  1506 	do {
  1507 	    unsigned run;
  1508 	    ofs += ((Uint16 *)srcbuf)[0];
  1509 	    run = ((Uint16 *)srcbuf)[1];
  1510 	    srcbuf += 4;
  1511 	    if(run) {
  1512 		srcbuf += uncopy_transl(dst + ofs, srcbuf, run, df, sf);
  1513 		ofs += run;
  1514 	    }
  1515 	} while(ofs < w);
  1516 	dst += surface->pitch >> 2;
  1517     }
  1518 }
  1519 
  1520 void SDL_UnRLESurface(SDL_Surface *surface, int recode)
  1521 {
  1522     if ( (surface->flags & SDL_RLEACCEL) == SDL_RLEACCEL ) {
  1523 	surface->flags &= ~SDL_RLEACCEL;
  1524 
  1525 	if(recode && (surface->flags & SDL_PREALLOC) != SDL_PREALLOC
  1526 	   && (surface->flags & SDL_HWSURFACE) != SDL_HWSURFACE) {
  1527 	    if((surface->flags & SDL_SRCCOLORKEY) == SDL_SRCCOLORKEY) {
  1528 		SDL_Rect full;
  1529 		unsigned alpha_flag;
  1530 
  1531 		/* re-create the original surface */
  1532 		surface->pixels = malloc(surface->h * surface->pitch);
  1533 
  1534 		/* fill it with the background colour */
  1535 		SDL_FillRect(surface, NULL, surface->format->colorkey);
  1536 
  1537 		/* now render the encoded surface */
  1538 		full.x = full.y = 0;
  1539 		full.w = surface->w;
  1540 		full.h = surface->h;
  1541 		alpha_flag = surface->flags & SDL_SRCALPHA;
  1542 		surface->flags &= ~SDL_SRCALPHA; /* opaque blit */
  1543 		SDL_RLEBlit(surface, &full, surface, &full);
  1544 		surface->flags |= alpha_flag;
  1545 	    } else
  1546 		UnRLEAlpha(surface);
  1547 	}
  1548 
  1549 	if ( surface->map && surface->map->sw_data->aux_data ) {
  1550 	    free(surface->map->sw_data->aux_data);
  1551 	    surface->map->sw_data->aux_data = NULL;
  1552 	}
  1553     }
  1554 }
  1555 
  1556