fixed rle_swap leaks, thanks to martin schaffner
[btb/d2x.git] / 2d / rle.c
1 /* $Id: rle.c,v 1.12 2002-12-31 21:51:37 btb Exp $ */
2 /*
3 THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
4 SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
5 END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
6 ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
7 IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
8 SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
9 FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
10 CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
11 AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
12 COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
13 */
14
15 /*
16  *
17  * Routines to do run length encoding/decoding
18  * on bitmaps.
19  *
20  * Changed shorts to ints in parameters.
21  *
22  *
23  * Old Log:
24  * Revision 1.10  1995/08/14  14:26:34  allender
25  * changed transparency color to 0
26  *
27  * Revision 1.9  1995/07/05  16:07:49  allender
28  * transparency/kitchen chagnes
29  *
30  * Revision 1.8  1995/05/12  11:54:03  allender
31  * changed memory stuff again
32  *
33  * Revision 1.7  1995/05/11  12:49:19  allender
34  * change transparency color
35  *
36  * Revision 1.6  1995/05/04  20:00:30  allender
37  * use NewPtr instead of malloc.  Fix gr_rle_scanline (which caused me
38  * *many* hours of frustration!!!!)
39  *
40  * Revision 1.5  1995/05/01  08:40:32  allender
41  * trying to find memory bug....this stuff works -- it's johns code
42  *
43  * Revision 1.4  1995/04/27  07:38:24  allender
44  * new rle code ala John
45  *
46  * Revision 1.3  1995/04/19  14:36:06  allender
47  * *** empty log message ***
48  *
49  * Revision 1.2  1995/04/18  12:08:30  allender
50  * *** empty log message ***
51  *
52  * Revision 1.1  1995/03/09  09:23:04  allender
53  * Initial revision
54  *
55  *
56  * --- PC RCS information ---
57  * Revision 1.19  1995/01/14  19:18:31  john
58  * Added assert to check for paged out bitmap.
59  *
60  * Revision 1.18  1995/01/14  11:32:07  john
61  * Added rle_cache_flush function.
62  *
63  * Revision 1.17  1994/12/13  10:58:27  john
64  * Fixed bug with 2 consecutive calls to get_expanded_Texture
65  * with 2 different bitmaps, returning the same rle texture,
66  * causing doors to disapper.
67  *
68  * Revision 1.16  1994/11/30  00:55:03  mike
69  * optimization
70  *
71  * Revision 1.15  1994/11/24  13:24:44  john
72  * Made sure that some rep movs had the cld set first.
73  * Took some unused functions out.
74  *
75  * Revision 1.14  1994/11/23  16:03:46  john
76  * Fixed generic rle'ing to use new bit method.
77  *
78  * Revision 1.13  1994/11/23  15:45:51  john
79  * Changed to a 3 bit rle scheme.
80  *
81  * Revision 1.12  1994/11/18  22:50:24  john
82  * Changed shorts to ints in parameters.
83  *
84  * Revision 1.11  1994/11/14  17:06:13  john
85  * Took out Key_f12.
86  *
87  * Revision 1.10  1994/11/14  15:54:09  john
88  * Put code in for maybe checking bogus rle data.
89  *
90  * Revision 1.9  1994/11/14  15:51:58  john
91  * Added rle_disable_caching variable to prove the stability of my rle
92  * caching code to any non-believers.
93  *
94  * Revision 1.8  1994/11/10  10:31:20  john
95  * Reduce cache buffers to 16.
96  *
97  * Revision 1.7  1994/11/09  19:53:43  john
98  * Added texture rle caching.
99  *
100  * Revision 1.6  1994/11/09  17:41:44  john
101  * Made a slow version of rle bitblt to svga, modex.
102  *
103  * Revision 1.5  1994/11/09  17:07:50  john
104  * Fixed bug with bitmap that gets bigger with rle.
105  *
106  * Revision 1.4  1994/11/09  16:35:17  john
107  * First version with working RLE bitmaps.
108  *
109  * Revision 1.3  1994/10/26  12:54:47  john
110  * Fixed bug with decode that used rep movsd instead of
111  * rep stosd.
112  *
113  * Revision 1.2  1994/10/06  17:05:25  john
114  * First version of rle stuff.
115  *
116  * Revision 1.1  1994/10/06  16:53:34  john
117  * Initial revision
118  *
119  *
120  */
121
122
123 #ifdef HAVE_CONFIG_H
124 #include <conf.h>
125 #endif
126
127 #ifdef RCS
128 static char rcsid[] = "$Id: rle.c,v 1.12 2002-12-31 21:51:37 btb Exp $";
129 #endif
130
131 #include <stdlib.h>
132 #include <stdio.h>
133 #include <string.h>
134
135 #include "pstypes.h"
136 #include "u_mem.h"
137 #include "mono.h"
138
139
140 #include "gr.h"
141 #include "grdef.h"
142 #include "error.h"
143 //#include "key.h"
144 #include "rle.h"
145
146 #define RLE_CODE        0xE0
147 #define NOT_RLE_CODE    31
148
149 #if !defined(NO_ASM) && defined(__WATCOMC__)
150 #define RLE_DECODE_ASM
151
152 ubyte *gr_rle_decode_asm( ubyte * src, ubyte * dest );
153 #pragma aux gr_rle_decode_asm parm [esi] [edi] value [edi] modify exact [eax ebx ecx edx esi edi] = \
154 "  cld              " \
155 "   xor ecx, ecx    " \
156 "   cld             " \
157 "   jmp NextByte    " \
158 "                   " \
159 "Unique:            " \
160 "   mov [edi],al    " \
161 "   inc edi         " \
162 "                   " \
163 "NextByte:          " \
164 "   mov al,[esi]    " \
165 "   inc esi         " \
166 "                   " \
167 "   mov ah, al      " \
168 "   and ah, 0xE0    " \
169 "  cmp  ah, 0xE0    " \
170 "   jne   Unique    " \
171 "                   " \
172 "   mov cl, al      " \
173 "   and cl, 31      " \
174 "   je      done    " \
175 "                   " \
176 "   mov al,[esi]    " \
177 "   inc esi         " \
178 "   mov ah, al      " \
179 "   shr ecx,1       " \
180 "   rep stosw       " \
181 "   jnc NextByte    " \
182 "   mov [edi],al    " \
183 "   inc edi         " \
184 "                   " \
185 "   jmp NextByte    " \
186 "                   " \
187 "done:              ";
188
189 #elif !defined(NO_ASM) && defined(__GNUC__)
190 #define RLE_DECODE_ASM
191
192 static inline int gr_rle_decode_asm( ubyte * src, ubyte * dest ) {
193    register int __ret;
194    int dummy;
195    __asm__ __volatile__ (
196 "   cld;"
197 "   xorl %%ecx, %%ecx;"
198 "   jmp 1f;"
199 "0:;"
200 "   movb %%al,(%%edi);"
201 "   incl %%edi;"
202 "1:;"
203 "   movb (%%esi), %%al;"
204 "   incl %%esi;"
205 "   movb %%al, %%ah;"
206 "   andb $0xE0, %%ah;"
207 "   cmpb $0xE0, %%ah;"
208 "   jne 0b;"
209 "   movb %%al, %%cl;"
210 "   andb $31, %%cl;"
211 "   je 2f;"
212 "   movb (%%esi), %%al;"
213 "   incl %%esi;"
214 "   movb %%al, %%ah;"
215 "   shrl $1, %%ecx;"
216 "   rep; stosw;"
217 "   jnc 1b;"
218 "   movb %%al, (%%edi);"
219 "   incl %%edi;"
220 "   jmp 1b;"
221 "2:"
222 : "=D" (__ret), "=S" (dummy) : "1" (src), "D" (dest) : "%eax", "%ecx");
223   return __ret;
224 }
225
226 #elif !defined(NO_ASM) && defined(_MSC_VER)
227 #define RLE_DECODE_ASM
228
229 __inline int gr_rle_decode_asm( ubyte * src, ubyte * dest )
230 {
231          int retval;
232         __asm {
233                 mov esi,[src]
234                 mov edi,[dest]
235         xor ecx, ecx
236                 cld
237                 jmp NextByte
238 Unique:
239                 mov [edi], al
240                 inc edi
241 NextByte:
242                 mov al,[esi]
243                 inc esi
244                 mov ah, al
245                 and ah,0xE0
246                 cmp ah,0xE0
247                 jne Unique
248
249                 mov cl, al
250                 and cl, 31
251                 je done
252
253                 mov al, [esi]
254                 inc esi
255                 mov ah, al
256                 shr ecx, 1
257                 rep stosw
258                 jnc NextByte
259                 mov [edi], al
260                 inc edi
261                 jmp NextByte
262 done:
263                 mov [retval],edi
264         }
265         return retval;
266 }
267
268 #endif
269
270 #ifdef RLE_DECODE_ASM
271
272 #if 0
273 void gr_rle_decode( ubyte * src, ubyte * dest, int dest_len )
274 {
275         ubyte *dest_end;
276
277         dest_end = (ubyte *)gr_rle_decode_asm( src, dest );
278
279         Assert(dest_end-src < dest_len);
280 }
281 #else
282 void gr_rle_decode( ubyte * src, ubyte * dest )
283 {
284     gr_rle_decode_asm( src, dest );
285 }
286 #endif
287
288 #else // NO_ASM or unknown compiler
289
290 void gr_rle_decode( ubyte * src, ubyte * dest )
291 {
292         int i;
293         ubyte data, count = 0;
294
295         while(1) {
296                 data = *src++;
297                 if ( (data & RLE_CODE) != RLE_CODE ) {
298                         *dest++ = data;
299                 } else {
300                         count = data & NOT_RLE_CODE;
301                         if (count == 0)
302                                 return;
303                         data = *src++;
304                         for (i = 0; i < count; i++)
305                                 *dest++ = data;
306                 }
307         }
308 }
309
310 #endif
311
312 void rle_stosb(char *dest, int len, int color);
313
314 #if !defined(NO_ASM) && defined(__WATCOMC__)
315
316 #pragma aux rle_stosb = "cld rep    stosb" parm [edi] [ecx] [eax] modify exact [edi ecx];
317
318 #elif !defined(NO_ASM) && defined(__GNUC__)
319
320 inline void rle_stosb(char *dest, int len, int color) {
321         int dummy[2];
322    __asm__ __volatile__ (
323     "cld; rep; stosb"
324     : "=D" (dummy[0]), "=c" (dummy[1])
325         : "0" (dest), "1" (len), "a" (color) );
326 }
327
328 #elif !defined(NO_ASM) && defined(_MSC_VER)
329
330 __inline void rle_stosb(char *dest, int len, int color)
331 {
332   __asm {
333         mov edi,[dest]
334         mov ecx,[len]
335         mov eax,[color]
336         cld
337         rep stosb
338   }
339 }
340
341 #else // NO_ASM or unknown compiler
342
343 void rle_stosb(char *dest, int len, int color)
344 {
345         int i;
346         for (i=0; i<len; i++ )
347                 *dest++ = color;
348 }
349
350 #endif
351
352 // Given pointer to start of one scanline of rle data, uncompress it to
353 // dest, from source pixels x1 to x2.
354 void gr_rle_expand_scanline_masked( ubyte *dest, ubyte *src, int x1, int x2  )
355 {
356         int i = 0;
357         ubyte count;
358         ubyte color=0;
359
360         if ( x2 < x1 ) return;
361
362         count = 0;
363         while ( i < x1 )        {
364                 color = *src++;
365                 if ( color == RLE_CODE ) return;
366                 if ( (color & RLE_CODE)==RLE_CODE )     {
367                         count = color & (~RLE_CODE);
368                         color = *src++;
369                 } else {
370                         // unique
371                         count = 1;
372                 }
373                 i += count;
374         }
375         count = i - x1;
376         i = x1;
377         // we know have '*count' pixels of 'color'.
378         
379         if ( x1+count > x2 )    {
380                 count = x2-x1+1;
381                 if ( color != TRANSPARENCY_COLOR )      rle_stosb( dest, count, color );
382                 return;
383         }
384
385         if ( color != TRANSPARENCY_COLOR )      rle_stosb( dest, count, color );
386         dest += count;
387         i += count;
388
389         while( i <= x2 )                {
390                 color = *src++;
391                 if ( color == RLE_CODE ) return;
392                 if ( (color & RLE_CODE) == (RLE_CODE) ) {
393                         count = color & (~RLE_CODE);
394                         color = *src++;
395                 } else {
396                         // unique
397                         count = 1;
398                 }
399                 // we know have '*count' pixels of 'color'.
400                 if ( i+count <= x2 )    {
401                         if ( color != TRANSPARENCY_COLOR )rle_stosb( dest, count, color );
402                         i += count;
403                         dest += count;
404                 } else {
405                         count = x2-i+1;
406                         if ( color != TRANSPARENCY_COLOR )rle_stosb( dest, count, color );
407                         i += count;
408                         dest += count;
409                 }
410
411         }       
412 }
413
414 void gr_rle_expand_scanline( ubyte *dest, ubyte *src, int x1, int x2  )
415 {
416         int i = 0;
417         ubyte count;
418         ubyte color=0;
419
420         if ( x2 < x1 ) return;
421
422         count = 0;
423         while ( i < x1 )        {
424                 color = *src++;
425                 if ( color == RLE_CODE ) return;
426                 if ( (color & RLE_CODE)==RLE_CODE )     {
427                         count = color & (~RLE_CODE);
428                         color = *src++;
429                 } else {
430                         // unique
431                         count = 1;
432                 }
433                 i += count;
434         }
435         count = i - x1;
436         i = x1;
437         // we know have '*count' pixels of 'color'.
438         
439         if ( x1+count > x2 )    {
440                 count = x2-x1+1;
441                 rle_stosb( dest, count, color );
442                 return;
443         }
444
445         rle_stosb( dest, count, color );
446         dest += count;
447         i += count;
448
449         while( i <= x2 )                {
450                 color = *src++;
451                 if ( color == RLE_CODE ) return;
452                 if ( (color & RLE_CODE)==RLE_CODE )     {
453                         count = color & (~RLE_CODE);
454                         color = *src++;
455                 } else {
456                         // unique
457                         count = 1;
458                 }
459                 // we know have '*count' pixels of 'color'.
460                 if ( i+count <= x2 )    {
461                         rle_stosb( dest, count, color );
462                         i += count;
463                         dest += count;
464                 } else {
465                         count = x2-i+1;
466                         rle_stosb( dest, count, color );
467                         i += count;
468                         dest += count;
469                 }
470         }
471 }
472
473
474 int gr_rle_encode( int org_size, ubyte *src, ubyte *dest )
475 {
476         int i;
477         ubyte c, oc;
478         ubyte count;
479         ubyte *dest_start;
480
481         dest_start = dest;
482         oc = *src++;
483         count = 1;
484
485         for (i=1; i<org_size; i++ )     {
486                 c = *src++;
487                 if ( c!=oc )    {
488                         if ( count )    {
489                                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )        {
490                                         *dest++ = oc;
491                                         Assert( oc != RLE_CODE );
492                                 } else {
493                                         count |= RLE_CODE;
494                                         *dest++ = count;
495                                         *dest++ = oc;
496                                 }
497                         }
498                         oc = c;
499                         count = 0;
500                 }
501                 count++;
502                 if ( count == NOT_RLE_CODE )    {
503                         count |= RLE_CODE;
504                         *dest++=count;
505                         *dest++=oc;
506                         count = 0;
507                 }
508         }
509         if (count)      {
510                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )        {
511                         *dest++ = oc;
512                         Assert( oc != RLE_CODE );
513                 } else {
514                         count |= RLE_CODE;
515                         *dest++ = count;
516                         *dest++ = oc;
517                 }
518         }
519         *dest++ = RLE_CODE;
520
521         return dest-dest_start;
522 }
523
524
525 int gr_rle_getsize( int org_size, ubyte *src )
526 {
527         int i;
528         ubyte c, oc;
529         ubyte count;
530         int dest_size=0;
531
532         oc = *src++;
533         count = 1;
534
535         for (i=1; i<org_size; i++ )     {
536                 c = *src++;
537                 if ( c!=oc )    {
538                         if ( count )    {
539                                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )        {
540                                         dest_size++;
541                                 } else {
542                                         dest_size++;
543                                         dest_size++;
544                                 }
545                         }
546                         oc = c;
547                         count = 0;
548                 }
549                 count++;
550                 if ( count == NOT_RLE_CODE )    {
551                         dest_size++;
552                         dest_size++;
553                         count = 0;
554                 }
555         }
556         if (count)      {
557                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )        {
558                         dest_size++;
559                 } else {
560                         dest_size++;
561                         dest_size++;
562                 }
563         }
564         dest_size++;
565
566         return dest_size;
567 }
568
569 int gr_bitmap_rle_compress( grs_bitmap * bmp )
570 {
571         int y, d1, d;
572         int doffset;
573         ubyte *rle_data;
574         int large_rle = 0;
575
576         // first must check to see if this is large bitmap.
577
578         for (y=0; y<bmp->bm_h; y++ )    {
579                 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
580                 if (d1 > 255) {
581                         large_rle = 1;
582                         break;
583                 }
584         }
585
586         rle_data=d_malloc( (bmp->bm_w+1) * bmp->bm_h );
587         if (rle_data==NULL) return 0;
588         if (!large_rle)
589                 doffset = 4 + bmp->bm_h;
590         else
591                 doffset = 4 + (2 * bmp->bm_h);          // each row of rle'd bitmap has short instead of byte offset now
592
593         for (y=0; y<bmp->bm_h; y++ )    {
594                 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
595                 if ( ((doffset+d1) > bmp->bm_w*bmp->bm_h) || (d1 > (large_rle?32767:255) ) ) {
596                         d_free(rle_data);
597                         return 0;
598                 }
599                 d = gr_rle_encode( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y], &rle_data[doffset] );
600                 Assert( d==d1 );
601                 doffset += d;
602                 if (large_rle)
603                         *((short *)&(rle_data[(y*2)+4])) = (short)d;
604                 else
605                         rle_data[y+4] = d;
606         }
607         //mprintf( 0, "Bitmap of size %dx%d, (%d bytes) went down to %d bytes\n", bmp->bm_w, bmp->bm_h, bmp->bm_h*bmp->bm_w, doffset );
608         memcpy(         rle_data, &doffset, 4 );
609         memcpy(         bmp->bm_data, rle_data, doffset );
610         d_free(rle_data);
611         bmp->bm_flags |= BM_FLAG_RLE;
612         if (large_rle)
613                 bmp->bm_flags |= BM_FLAG_RLE_BIG;
614         return 1;
615 }
616
617 #define MAX_CACHE_BITMAPS 32
618
619 typedef struct rle_cache_element {
620         grs_bitmap * rle_bitmap;
621         ubyte * rle_data;
622         grs_bitmap * expanded_bitmap;
623         int last_used;
624 } rle_cache_element;
625
626 int rle_cache_initialized = 0;
627 int rle_counter = 0;
628 int rle_next = 0;
629 rle_cache_element rle_cache[MAX_CACHE_BITMAPS];
630
631 int rle_hits = 0;
632 int rle_misses = 0;
633
634 void rle_cache_close(void)
635 {
636         if (rle_cache_initialized)      {
637                 int i;
638                 rle_cache_initialized = 0;
639                 for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
640                         gr_free_bitmap(rle_cache[i].expanded_bitmap);
641                 }
642         }
643 }
644
645 void rle_cache_init()
646 {
647         int i;
648         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
649                 rle_cache[i].rle_bitmap = NULL;
650                 rle_cache[i].expanded_bitmap = gr_create_bitmap( 64, 64 );
651                 rle_cache[i].last_used = 0;
652                 Assert( rle_cache[i].expanded_bitmap != NULL );
653         }
654         rle_cache_initialized = 1;
655         atexit( rle_cache_close );
656 }
657
658 void rle_cache_flush()
659 {
660         int i;
661         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
662                 rle_cache[i].rle_bitmap = NULL;
663                 rle_cache[i].last_used = 0;
664         }
665 }
666
667 void rle_expand_texture_sub( grs_bitmap * bmp, grs_bitmap * rle_temp_bitmap_1 )
668 {
669         unsigned char * dbits;
670         unsigned char * sbits;
671         int i;
672 #ifdef RLE_DECODE_ASM
673         unsigned char * dbits1;
674 #endif
675
676 #ifdef D1XD3D
677         Assert (bmp->iMagic == BM_MAGIC_NUMBER);
678 #endif
679
680         sbits = &bmp->bm_data[4 + bmp->bm_h];
681         dbits = rle_temp_bitmap_1->bm_data;
682
683         rle_temp_bitmap_1->bm_flags = bmp->bm_flags & (~BM_FLAG_RLE);
684
685         for (i=0; i < bmp->bm_h; i++ )    {
686 #ifdef RLE_DECODE_ASM
687                 dbits1=(unsigned char *)gr_rle_decode_asm( sbits, dbits );
688 #else
689                 gr_rle_decode( sbits, dbits );
690 #endif
691                 sbits += (int)bmp->bm_data[4+i];
692                 dbits += bmp->bm_w;
693 #ifdef RLE_DECODE_ASM
694                 Assert( dbits == dbits1 );              // Get John, bogus rle data!
695 #endif
696         }
697 #ifdef D1XD3D
698         gr_set_bitmap_data (rle_temp_bitmap_1, rle_temp_bitmap_1->bm_data);
699 #endif
700 }
701
702 #if defined(POLY_ACC)
703 grs_bitmap *rle_get_id_sub(grs_bitmap *bmp)
704 {
705         int i;
706
707         for (i=0;i<MAX_CACHE_BITMAPS;i++) {
708                 if (rle_cache[i].expanded_bitmap == bmp) {
709                         return rle_cache[i].rle_bitmap;
710                 }
711         }
712         return NULL;
713 }
714 #endif
715
716
717 grs_bitmap * rle_expand_texture( grs_bitmap * bmp )
718 {
719         int i;
720         int lowest_count, lc;
721         int least_recently_used;
722
723         if (!rle_cache_initialized) rle_cache_init();
724
725         Assert( !(bmp->bm_flags & BM_FLAG_PAGED_OUT) );
726
727         lc = rle_counter;
728         rle_counter++;
729         if ( rle_counter < lc ) {
730                 for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
731                         rle_cache[i].rle_bitmap = NULL;
732                         rle_cache[i].last_used = 0;
733                 }
734         }
735
736 //      if (((rle_counter % 100)==1) && (rle_hits+rle_misses > 0))
737 //              mprintf(( 0, "RLE-CACHE %d%%, H:%d, M:%d\n", (rle_misses*100)/(rle_hits+rle_misses), rle_hits, rle_misses ));
738
739         lowest_count = rle_cache[rle_next].last_used;
740         least_recently_used = rle_next;
741         rle_next++;
742         if ( rle_next >= MAX_CACHE_BITMAPS )
743                 rle_next = 0;
744
745         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
746                 if (rle_cache[i].rle_bitmap == bmp)     {
747                         rle_hits++;
748                         rle_cache[i].last_used = rle_counter;
749                         return rle_cache[i].expanded_bitmap;
750                 }
751                 if ( rle_cache[i].last_used < lowest_count )    {
752                         lowest_count = rle_cache[i].last_used;
753                         least_recently_used = i;
754                 }
755         }
756
757         Assert(bmp->bm_w<=64 && bmp->bm_h<=64); //dest buffer is 64x64
758         rle_misses++;
759         rle_expand_texture_sub( bmp, rle_cache[least_recently_used].expanded_bitmap );
760         rle_cache[least_recently_used].rle_bitmap = bmp;
761         rle_cache[least_recently_used].last_used = rle_counter;
762         return rle_cache[least_recently_used].expanded_bitmap;
763 }
764
765
766 void gr_rle_expand_scanline_generic( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2 )
767 {
768         int i = 0, j;
769         int count;
770         ubyte color=0;
771
772         if ( x2 < x1 ) return;
773
774         count = 0;
775         while ( i < x1 )        {
776                 color = *src++;
777                 if ( color == RLE_CODE ) return;
778                 if ( (color & RLE_CODE) == RLE_CODE )   {
779                         count = color & NOT_RLE_CODE;
780                         color = *src++;
781                 } else {
782                         // unique
783                         count = 1;
784                 }
785                 i += count;
786         }
787         count = i - x1;
788         i = x1;
789         // we know have '*count' pixels of 'color'.
790
791         if ( x1+count > x2 )    {
792                 count = x2-x1+1;
793                 for ( j=0; j<count; j++ )
794                         gr_bm_pixel( dest, dx++, dy, color );
795                 return;
796         }
797
798         for ( j=0; j<count; j++ )
799                 gr_bm_pixel( dest, dx++, dy, color );
800         i += count;
801
802         while( i <= x2 )                {
803                 color = *src++;
804                 if ( color == RLE_CODE ) return;
805                 if ( (color & RLE_CODE) == RLE_CODE )   {
806                         count = color & NOT_RLE_CODE;
807                         color = *src++;
808                 } else {
809                         // unique
810                         count = 1;
811                 }
812                 // we know have '*count' pixels of 'color'.
813                 if ( i+count <= x2 )    {
814                         for ( j=0; j<count; j++ )
815                                 gr_bm_pixel( dest, dx++, dy, color );
816                         i += count;
817                 } else {
818                         count = x2-i+1;
819                         for ( j=0; j<count; j++ )
820                                 gr_bm_pixel( dest, dx++, dy, color );
821                         i += count;
822                 }
823         }
824 }
825
826 void gr_rle_expand_scanline_generic_masked( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2  )
827 {
828         int i = 0, j;
829         int count;
830         ubyte color = 0;
831
832         if ( x2 < x1 ) return;
833
834         count = 0;
835         while ( i < x1 )        {
836                 color = *src++;
837                 if ( color == RLE_CODE ) return;
838                 if ( (color & RLE_CODE) == RLE_CODE )   {
839                         count = color & NOT_RLE_CODE;
840                         color = *src++;
841                 } else {
842                         // unique
843                         count = 1;
844                 }
845                 i += count;
846         }
847         count = i - x1;
848         i = x1;
849         // we know have '*count' pixels of 'color'.
850
851         if ( x1+count > x2 )    {
852                 count = x2-x1+1;
853                 if (color != TRANSPARENCY_COLOR) {
854                         for ( j=0; j<count; j++ )
855                                 gr_bm_pixel( dest, dx++, dy, color );
856                 }
857                 return;
858         }
859
860         if ( color != TRANSPARENCY_COLOR ) {
861                 for ( j=0; j<count; j++ )
862                         gr_bm_pixel( dest, dx++, dy, color );
863         } else
864                 dx += count;
865         i += count;
866
867         while( i <= x2 )                {
868                 color = *src++;
869                 if ( color == RLE_CODE ) return;
870                 if ( (color & RLE_CODE) == RLE_CODE )   {
871                         count = color & NOT_RLE_CODE;
872                         color = *src++;
873                 } else {
874                         // unique
875                         count = 1;
876                 }
877                 // we know have '*count' pixels of 'color'.
878                 if ( i+count <= x2 )    {
879                         if ( color != TRANSPARENCY_COLOR ) {
880                                 for ( j=0; j<count; j++ )
881                                         gr_bm_pixel( dest, dx++, dy, color );
882                         } else
883                                 dx += count;
884                         i += count;
885                 } else {
886                         count = x2-i+1;
887                         if ( color != TRANSPARENCY_COLOR ) {
888                                 for ( j=0; j<count; j++ )
889                                         gr_bm_pixel( dest, dx++, dy, color );
890                         } else
891                                 dx += count;
892                         i += count;
893                 }
894         }
895 }
896
897
898 #ifdef __MSDOS__
899 void gr_rle_expand_scanline_svga_masked( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2  )
900 {
901         int i = 0, j;
902         int count;
903         ubyte color;
904         ubyte * vram = (ubyte *)0xA0000;
905         int VideoLocation,page,offset;
906
907         if ( x2 < x1 ) return;
908
909         VideoLocation = (unsigned int)dest->bm_data + (dest->bm_rowsize * dy) + dx;
910         page    = VideoLocation >> 16;
911         offset  = VideoLocation & 0xFFFF;
912
913         gr_vesa_setpage( page );
914
915         if ( (offset + (x2-x1+1)) < 65536 )     {
916                 // We don't cross a svga page, so blit it fast!
917                 gr_rle_expand_scanline_masked( &vram[offset], src, x1, x2 );
918                 return;
919         }
920
921         count = 0;
922         while ( i < x1 )        {
923                 color = *src++;
924                 if ( color == RLE_CODE ) return;
925                 if ( (color & RLE_CODE) == RLE_CODE )   {
926                         count = color & NOT_RLE_CODE;
927                         color = *src++;
928                 } else {
929                         // unique
930                         count = 1;
931                 }
932                 i += count;
933         }
934         count = i - x1;
935         i = x1;
936         // we know have '*count' pixels of 'color'.
937
938         if ( x1+count > x2 )    {
939                 count = x2-x1+1;
940                 if (color != TRANSPARENCY_COLOR) {
941                         for ( j=0; j<count; j++ )       {
942                                 vram[offset++] = color;
943                                 if ( offset >= 65536 ) {
944                                         offset -= 65536;
945                                         page++;
946                                         gr_vesa_setpage(page);
947                                 }
948                         }
949                 }
950                 return;
951         }
952
953         if ( color != TRANSPARENCY_COLOR ) {
954                 for ( j=0; j<count; j++ )       {
955                         vram[offset++] = color;
956                         if ( offset >= 65536 ) {
957                                 offset -= 65536;
958                                 page++;
959                                 gr_vesa_setpage(page);
960                         }
961                 }
962         } else  {
963                 offset += count;
964                 if ( offset >= 65536 ) {
965                         offset -= 65536;
966                         page++;
967                         gr_vesa_setpage(page);
968                 }
969         }
970         i += count;
971
972         while( i <= x2 )                {
973                 color = *src++;
974                 if ( color == RLE_CODE ) return;
975                 if ( (color & RLE_CODE) == RLE_CODE )   {
976                         count = color & NOT_RLE_CODE;
977                         color = *src++;
978                 } else {
979                         // unique
980                         count = 1;
981                 }
982                 // we know have '*count' pixels of 'color'.
983                 if ( i+count <= x2 )    {
984                         if ( color != TRANSPARENCY_COLOR ) {
985                                 for ( j=0; j<count; j++ )       {
986                                         vram[offset++] = color;
987                                         if ( offset >= 65536 ) {
988                                                 offset -= 65536;
989                                                 page++;
990                                                 gr_vesa_setpage(page);
991                                         }
992                                 }
993                         } else  {
994                                 offset += count;
995                                 if ( offset >= 65536 ) {
996                                         offset -= 65536;
997                                         page++;
998                                         gr_vesa_setpage(page);
999                                 }
1000                         }
1001                         i += count;
1002                 } else {
1003                         count = x2-i+1;
1004                         if ( color != TRANSPARENCY_COLOR ) {
1005                                 for ( j=0; j<count; j++ )       {
1006                                         vram[offset++] = color;
1007                                         if ( offset >= 65536 ) {
1008                                                 offset -= 65536;
1009                                                 page++;
1010                                                 gr_vesa_setpage(page);
1011                                         }
1012                                 }
1013                         } else  {
1014                                 offset += count;
1015                                 if ( offset >= 65536 ) {
1016                                         offset -= 65536;
1017                                         page++;
1018                                         gr_vesa_setpage(page);
1019                                 }
1020                         }
1021                         i += count;
1022                 }
1023         }
1024 }
1025 #endif // __MSDOS__
1026
1027
1028 /*
1029  * swaps entries 0 and 255 in an RLE bitmap without uncompressing it
1030  *
1031  * doesn't handle RLE_BIG yet, but neither does anything else...
1032  *
1033  * returns the size of the new bmp->bm_data
1034  */
1035 void rle_swap_0_255(grs_bitmap *bmp)
1036 {
1037         int i, j, len;
1038         unsigned char *ptr, *ptr2, *temp, *start;
1039
1040         Assert(!(bmp->bm_flags & BM_FLAG_RLE_BIG));
1041
1042         temp = d_malloc(4 + bmp->bm_h + (bmp->bm_w + 1) * bmp->bm_h);
1043
1044         ptr = bmp->bm_data + 4 + bmp->bm_h; // go to first line
1045         ptr2 = temp + 4 + bmp->bm_h;        // go to first line
1046         for (i = 0; i < bmp->bm_h; i++) {
1047                 start = ptr2;
1048                 for (j = 0; j < bmp->bm_data[4 + i]; j++) {
1049                         if ((ptr[j] & RLE_CODE) != RLE_CODE) {
1050                                 if (ptr[j] == 0) {
1051                                         *ptr2++ = RLE_CODE | 1;
1052                                         *ptr2++ = 255;
1053                                 } else
1054                                         *ptr2++ = ptr[j];
1055                         } else {
1056                                 *ptr2++ = ptr[j];
1057                                 if ((ptr[j] & NOT_RLE_CODE) == 0)
1058                                         break;
1059                                 j++;
1060                                 if (ptr[j] == 0)
1061                                         *ptr2++ = 255;
1062                                 else if (ptr[j] == 255)
1063                                         *ptr2++ = 0;
1064                                 else
1065                                         *ptr2++ = ptr[j];
1066                         }
1067                 }
1068                 temp[4 + i] = ptr2 - start; // set line size
1069                 ptr += bmp->bm_data[4 + i]; // go to next line
1070         }
1071         len = ptr2 - temp;
1072         *((int *)temp) = len;           // set total size
1073         memcpy(bmp->bm_data, temp, len);
1074         d_free(temp);
1075 }