if descent.pig available, load d1 textures for d1 levels
[btb/d2x.git] / 2d / rle.c
1 /* $Id: rle.c,v 1.15 2003-03-19 22:44:15 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.15 2003-03-19 22:44:15 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 #include "byteswap.h"
146
147 #define RLE_CODE        0xE0
148 #define NOT_RLE_CODE    31
149
150 #define IS_RLE_CODE(x) (((x) & RLE_CODE) == RLE_CODE)
151
152 #if !defined(NO_ASM) && defined(__WATCOMC__)
153 #define RLE_DECODE_ASM
154
155 ubyte *gr_rle_decode_asm( ubyte * src, ubyte * dest );
156 #pragma aux gr_rle_decode_asm parm [esi] [edi] value [edi] modify exact [eax ebx ecx edx esi edi] = \
157 "  cld              " \
158 "   xor ecx, ecx    " \
159 "   cld             " \
160 "   jmp NextByte    " \
161 "                   " \
162 "Unique:            " \
163 "   mov [edi],al    " \
164 "   inc edi         " \
165 "                   " \
166 "NextByte:          " \
167 "   mov al,[esi]    " \
168 "   inc esi         " \
169 "                   " \
170 "   mov ah, al      " \
171 "   and ah, 0xE0    " \
172 "  cmp  ah, 0xE0    " \
173 "   jne   Unique    " \
174 "                   " \
175 "   mov cl, al      " \
176 "   and cl, 31      " \
177 "   je      done    " \
178 "                   " \
179 "   mov al,[esi]    " \
180 "   inc esi         " \
181 "   mov ah, al      " \
182 "   shr ecx,1       " \
183 "   rep stosw       " \
184 "   jnc NextByte    " \
185 "   mov [edi],al    " \
186 "   inc edi         " \
187 "                   " \
188 "   jmp NextByte    " \
189 "                   " \
190 "done:              ";
191
192 #elif !defined(NO_ASM) && defined(__GNUC__)
193 #define RLE_DECODE_ASM
194
195 static inline int gr_rle_decode_asm( ubyte * src, ubyte * dest ) {
196    register int __ret;
197    int dummy;
198    __asm__ __volatile__ (
199 "   cld;"
200 "   xorl %%ecx, %%ecx;"
201 "   jmp 1f;"
202 "0:;"
203 "   movb %%al,(%%edi);"
204 "   incl %%edi;"
205 "1:;"
206 "   movb (%%esi), %%al;"
207 "   incl %%esi;"
208 "   movb %%al, %%ah;"
209 "   andb $0xE0, %%ah;"
210 "   cmpb $0xE0, %%ah;"
211 "   jne 0b;"
212 "   movb %%al, %%cl;"
213 "   andb $31, %%cl;"
214 "   je 2f;"
215 "   movb (%%esi), %%al;"
216 "   incl %%esi;"
217 "   movb %%al, %%ah;"
218 "   shrl $1, %%ecx;"
219 "   rep; stosw;"
220 "   jnc 1b;"
221 "   movb %%al, (%%edi);"
222 "   incl %%edi;"
223 "   jmp 1b;"
224 "2:"
225 : "=D" (__ret), "=S" (dummy) : "1" (src), "D" (dest) : "%eax", "%ecx");
226   return __ret;
227 }
228
229 #elif !defined(NO_ASM) && defined(_MSC_VER)
230 #define RLE_DECODE_ASM
231
232 __inline int gr_rle_decode_asm( ubyte * src, ubyte * dest )
233 {
234          int retval;
235         __asm {
236                 mov esi,[src]
237                 mov edi,[dest]
238         xor ecx, ecx
239                 cld
240                 jmp NextByte
241 Unique:
242                 mov [edi], al
243                 inc edi
244 NextByte:
245                 mov al,[esi]
246                 inc esi
247                 mov ah, al
248                 and ah,0xE0
249                 cmp ah,0xE0
250                 jne Unique
251
252                 mov cl, al
253                 and cl, 31
254                 je done
255
256                 mov al, [esi]
257                 inc esi
258                 mov ah, al
259                 shr ecx, 1
260                 rep stosw
261                 jnc NextByte
262                 mov [edi], al
263                 inc edi
264                 jmp NextByte
265 done:
266                 mov [retval],edi
267         }
268         return retval;
269 }
270
271 #endif
272
273 #ifdef RLE_DECODE_ASM
274
275 #if 0
276 void gr_rle_decode( ubyte * src, ubyte * dest, int dest_len )
277 {
278         ubyte *dest_end;
279
280         dest_end = (ubyte *)gr_rle_decode_asm( src, dest );
281
282         Assert(dest_end-src < dest_len);
283 }
284 #else
285 void gr_rle_decode( ubyte * src, ubyte * dest )
286 {
287     gr_rle_decode_asm( src, dest );
288 }
289 #endif
290
291 #else // NO_ASM or unknown compiler
292
293 void gr_rle_decode( ubyte * src, ubyte * dest )
294 {
295         int i;
296         ubyte data, count = 0;
297
298         while(1) {
299                 data = *src++;
300                 if ( ! IS_RLE_CODE(data) ) {
301                         *dest++ = data;
302                 } else {
303                         count = data & NOT_RLE_CODE;
304                         if (count == 0)
305                                 return;
306                         data = *src++;
307                         for (i = 0; i < count; i++)
308                                 *dest++ = data;
309                 }
310         }
311 }
312
313 #endif
314
315 void rle_stosb(char *dest, int len, int color);
316
317 #if !defined(NO_ASM) && defined(__WATCOMC__)
318
319 #pragma aux rle_stosb = "cld rep    stosb" parm [edi] [ecx] [eax] modify exact [edi ecx];
320
321 #elif !defined(NO_ASM) && defined(__GNUC__)
322
323 inline void rle_stosb(char *dest, int len, int color) {
324         int dummy[2];
325    __asm__ __volatile__ (
326     "cld; rep; stosb"
327     : "=D" (dummy[0]), "=c" (dummy[1])
328         : "0" (dest), "1" (len), "a" (color) );
329 }
330
331 #elif !defined(NO_ASM) && defined(_MSC_VER)
332
333 __inline void rle_stosb(char *dest, int len, int color)
334 {
335   __asm {
336         mov edi,[dest]
337         mov ecx,[len]
338         mov eax,[color]
339         cld
340         rep stosb
341   }
342 }
343
344 #else // NO_ASM or unknown compiler
345
346 void rle_stosb(char *dest, int len, int color)
347 {
348         int i;
349         for (i=0; i<len; i++ )
350                 *dest++ = color;
351 }
352
353 #endif
354
355 // Given pointer to start of one scanline of rle data, uncompress it to
356 // dest, from source pixels x1 to x2.
357 void gr_rle_expand_scanline_masked( ubyte *dest, ubyte *src, int x1, int x2  )
358 {
359         int i = 0;
360         ubyte count;
361         ubyte color=0;
362
363         if ( x2 < x1 ) return;
364
365         count = 0;
366         while ( i < x1 )        {
367                 color = *src++;
368                 if ( color == RLE_CODE ) return;
369                 if ( IS_RLE_CODE(color) )       {
370                         count = color & (~RLE_CODE);
371                         color = *src++;
372                 } else {
373                         // unique
374                         count = 1;
375                 }
376                 i += count;
377         }
378         count = i - x1;
379         i = x1;
380         // we know have '*count' pixels of 'color'.
381         
382         if ( x1+count > x2 )    {
383                 count = x2-x1+1;
384                 if ( color != TRANSPARENCY_COLOR )      rle_stosb( dest, count, color );
385                 return;
386         }
387
388         if ( color != TRANSPARENCY_COLOR )      rle_stosb( dest, count, color );
389         dest += count;
390         i += count;
391
392         while( i <= x2 )                {
393                 color = *src++;
394                 if ( color == RLE_CODE ) return;
395                 if ( IS_RLE_CODE(color) )       {
396                         count = color & (~RLE_CODE);
397                         color = *src++;
398                 } else {
399                         // unique
400                         count = 1;
401                 }
402                 // we know have '*count' pixels of 'color'.
403                 if ( i+count <= x2 )    {
404                         if ( color != TRANSPARENCY_COLOR )rle_stosb( dest, count, color );
405                         i += count;
406                         dest += count;
407                 } else {
408                         count = x2-i+1;
409                         if ( color != TRANSPARENCY_COLOR )rle_stosb( dest, count, color );
410                         i += count;
411                         dest += count;
412                 }
413
414         }       
415 }
416
417 void gr_rle_expand_scanline( ubyte *dest, ubyte *src, int x1, int x2  )
418 {
419         int i = 0;
420         ubyte count;
421         ubyte color=0;
422
423         if ( x2 < x1 ) return;
424
425         count = 0;
426         while ( i < x1 )        {
427                 color = *src++;
428                 if ( color == RLE_CODE ) return;
429                 if ( IS_RLE_CODE(color) )       {
430                         count = color & (~RLE_CODE);
431                         color = *src++;
432                 } else {
433                         // unique
434                         count = 1;
435                 }
436                 i += count;
437         }
438         count = i - x1;
439         i = x1;
440         // we know have '*count' pixels of 'color'.
441         
442         if ( x1+count > x2 )    {
443                 count = x2-x1+1;
444                 rle_stosb( dest, count, color );
445                 return;
446         }
447
448         rle_stosb( dest, count, color );
449         dest += count;
450         i += count;
451
452         while( i <= x2 )                {
453                 color = *src++;
454                 if ( color == RLE_CODE ) return;
455                 if ( IS_RLE_CODE(color) )       {
456                         count = color & (~RLE_CODE);
457                         color = *src++;
458                 } else {
459                         // unique
460                         count = 1;
461                 }
462                 // we know have '*count' pixels of 'color'.
463                 if ( i+count <= x2 )    {
464                         rle_stosb( dest, count, color );
465                         i += count;
466                         dest += count;
467                 } else {
468                         count = x2-i+1;
469                         rle_stosb( dest, count, color );
470                         i += count;
471                         dest += count;
472                 }
473         }
474 }
475
476
477 int gr_rle_encode( int org_size, ubyte *src, ubyte *dest )
478 {
479         int i;
480         ubyte c, oc;
481         ubyte count;
482         ubyte *dest_start;
483
484         dest_start = dest;
485         oc = *src++;
486         count = 1;
487
488         for (i=1; i<org_size; i++ )     {
489                 c = *src++;
490                 if ( c!=oc )    {
491                         if ( count )    {
492                                 if ( (count==1) && (! IS_RLE_CODE(oc)) )        {
493                                         *dest++ = oc;
494                                         Assert( oc != RLE_CODE );
495                                 } else {
496                                         count |= RLE_CODE;
497                                         *dest++ = count;
498                                         *dest++ = oc;
499                                 }
500                         }
501                         oc = c;
502                         count = 0;
503                 }
504                 count++;
505                 if ( count == NOT_RLE_CODE )    {
506                         count |= RLE_CODE;
507                         *dest++=count;
508                         *dest++=oc;
509                         count = 0;
510                 }
511         }
512         if (count)      {
513                 if ( (count==1) && (! IS_RLE_CODE(oc)) )        {
514                         *dest++ = oc;
515                         Assert( oc != RLE_CODE );
516                 } else {
517                         count |= RLE_CODE;
518                         *dest++ = count;
519                         *dest++ = oc;
520                 }
521         }
522         *dest++ = RLE_CODE;
523
524         return dest-dest_start;
525 }
526
527
528 int gr_rle_getsize( int org_size, ubyte *src )
529 {
530         int i;
531         ubyte c, oc;
532         ubyte count;
533         int dest_size=0;
534
535         oc = *src++;
536         count = 1;
537
538         for (i=1; i<org_size; i++ )     {
539                 c = *src++;
540                 if ( c!=oc )    {
541                         if ( count )    {
542                                 if ( (count==1) && (! IS_RLE_CODE(oc)) )        {
543                                         dest_size++;
544                                 } else {
545                                         dest_size++;
546                                         dest_size++;
547                                 }
548                         }
549                         oc = c;
550                         count = 0;
551                 }
552                 count++;
553                 if ( count == NOT_RLE_CODE )    {
554                         dest_size++;
555                         dest_size++;
556                         count = 0;
557                 }
558         }
559         if (count)      {
560                 if ( (count==1) && (! IS_RLE_CODE(oc)) )        {
561                         dest_size++;
562                 } else {
563                         dest_size++;
564                         dest_size++;
565                 }
566         }
567         dest_size++;
568
569         return dest_size;
570 }
571
572 int gr_bitmap_rle_compress( grs_bitmap * bmp )
573 {
574         int y, d1, d;
575         int doffset;
576         ubyte *rle_data;
577         int large_rle = 0;
578
579         // first must check to see if this is large bitmap.
580
581         for (y=0; y<bmp->bm_h; y++ )    {
582                 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
583                 if (d1 > 255) {
584                         large_rle = 1;
585                         break;
586                 }
587         }
588
589         rle_data=d_malloc( (bmp->bm_w+1) * bmp->bm_h );
590         if (rle_data==NULL) return 0;
591         if (!large_rle)
592                 doffset = 4 + bmp->bm_h;
593         else
594                 doffset = 4 + (2 * bmp->bm_h);          // each row of rle'd bitmap has short instead of byte offset now
595
596         for (y=0; y<bmp->bm_h; y++ )    {
597                 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
598                 if ( ((doffset+d1) > bmp->bm_w*bmp->bm_h) || (d1 > (large_rle?32767:255) ) ) {
599                         d_free(rle_data);
600                         return 0;
601                 }
602                 d = gr_rle_encode( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y], &rle_data[doffset] );
603                 Assert( d==d1 );
604                 doffset += d;
605                 if (large_rle)
606                         *((short *)&(rle_data[(y*2)+4])) = (short)d;
607                 else
608                         rle_data[y+4] = d;
609         }
610         //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 );
611         memcpy(         rle_data, &doffset, 4 );
612         memcpy(         bmp->bm_data, rle_data, doffset );
613         d_free(rle_data);
614         bmp->bm_flags |= BM_FLAG_RLE;
615         if (large_rle)
616                 bmp->bm_flags |= BM_FLAG_RLE_BIG;
617         return 1;
618 }
619
620 #define MAX_CACHE_BITMAPS 32
621
622 typedef struct rle_cache_element {
623         grs_bitmap * rle_bitmap;
624         ubyte * rle_data;
625         grs_bitmap * expanded_bitmap;
626         int last_used;
627 } rle_cache_element;
628
629 int rle_cache_initialized = 0;
630 int rle_counter = 0;
631 int rle_next = 0;
632 rle_cache_element rle_cache[MAX_CACHE_BITMAPS];
633
634 int rle_hits = 0;
635 int rle_misses = 0;
636
637 void rle_cache_close(void)
638 {
639         if (rle_cache_initialized)      {
640                 int i;
641                 rle_cache_initialized = 0;
642                 for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
643                         gr_free_bitmap(rle_cache[i].expanded_bitmap);
644                 }
645         }
646 }
647
648 void rle_cache_init()
649 {
650         int i;
651         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
652                 rle_cache[i].rle_bitmap = NULL;
653                 rle_cache[i].expanded_bitmap = gr_create_bitmap( 64, 64 );
654                 rle_cache[i].last_used = 0;
655                 Assert( rle_cache[i].expanded_bitmap != NULL );
656         }
657         rle_cache_initialized = 1;
658         atexit( rle_cache_close );
659 }
660
661 void rle_cache_flush()
662 {
663         int i;
664         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
665                 rle_cache[i].rle_bitmap = NULL;
666                 rle_cache[i].last_used = 0;
667         }
668 }
669
670 void rle_expand_texture_sub( grs_bitmap * bmp, grs_bitmap * rle_temp_bitmap_1 )
671 {
672         unsigned char * dbits;
673         unsigned char * sbits;
674         int i;
675 #ifdef RLE_DECODE_ASM
676         unsigned char * dbits1;
677 #endif
678
679 #ifdef D1XD3D
680         Assert (bmp->iMagic == BM_MAGIC_NUMBER);
681 #endif
682
683         sbits = &bmp->bm_data[4 + bmp->bm_h];
684         dbits = rle_temp_bitmap_1->bm_data;
685
686         rle_temp_bitmap_1->bm_flags = bmp->bm_flags & (~BM_FLAG_RLE);
687
688         for (i=0; i < bmp->bm_h; i++ )    {
689 #ifdef RLE_DECODE_ASM
690                 dbits1=(unsigned char *)gr_rle_decode_asm( sbits, dbits );
691 #else
692                 gr_rle_decode( sbits, dbits );
693 #endif
694                 sbits += (int)bmp->bm_data[4+i];
695                 dbits += bmp->bm_w;
696 #ifdef RLE_DECODE_ASM
697                 Assert( dbits == dbits1 );              // Get John, bogus rle data!
698 #endif
699         }
700 #ifdef D1XD3D
701         gr_set_bitmap_data (rle_temp_bitmap_1, rle_temp_bitmap_1->bm_data);
702 #endif
703 }
704
705 #if defined(POLY_ACC)
706 grs_bitmap *rle_get_id_sub(grs_bitmap *bmp)
707 {
708         int i;
709
710         for (i=0;i<MAX_CACHE_BITMAPS;i++) {
711                 if (rle_cache[i].expanded_bitmap == bmp) {
712                         return rle_cache[i].rle_bitmap;
713                 }
714         }
715         return NULL;
716 }
717 #endif
718
719
720 grs_bitmap * rle_expand_texture( grs_bitmap * bmp )
721 {
722         int i;
723         int lowest_count, lc;
724         int least_recently_used;
725
726         if (!rle_cache_initialized) rle_cache_init();
727
728         Assert( !(bmp->bm_flags & BM_FLAG_PAGED_OUT) );
729
730         lc = rle_counter;
731         rle_counter++;
732         if ( rle_counter < lc ) {
733                 for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
734                         rle_cache[i].rle_bitmap = NULL;
735                         rle_cache[i].last_used = 0;
736                 }
737         }
738
739 //      if (((rle_counter % 100)==1) && (rle_hits+rle_misses > 0))
740 //              mprintf(( 0, "RLE-CACHE %d%%, H:%d, M:%d\n", (rle_misses*100)/(rle_hits+rle_misses), rle_hits, rle_misses ));
741
742         lowest_count = rle_cache[rle_next].last_used;
743         least_recently_used = rle_next;
744         rle_next++;
745         if ( rle_next >= MAX_CACHE_BITMAPS )
746                 rle_next = 0;
747
748         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
749                 if (rle_cache[i].rle_bitmap == bmp)     {
750                         rle_hits++;
751                         rle_cache[i].last_used = rle_counter;
752                         return rle_cache[i].expanded_bitmap;
753                 }
754                 if ( rle_cache[i].last_used < lowest_count )    {
755                         lowest_count = rle_cache[i].last_used;
756                         least_recently_used = i;
757                 }
758         }
759
760         Assert(bmp->bm_w<=64 && bmp->bm_h<=64); //dest buffer is 64x64
761         rle_misses++;
762         rle_expand_texture_sub( bmp, rle_cache[least_recently_used].expanded_bitmap );
763         rle_cache[least_recently_used].rle_bitmap = bmp;
764         rle_cache[least_recently_used].last_used = rle_counter;
765         return rle_cache[least_recently_used].expanded_bitmap;
766 }
767
768
769 void gr_rle_expand_scanline_generic( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2 )
770 {
771         int i = 0, j;
772         int count;
773         ubyte color=0;
774
775         if ( x2 < x1 ) return;
776
777         count = 0;
778         while ( i < x1 )        {
779                 color = *src++;
780                 if ( color == RLE_CODE ) return;
781                 if ( IS_RLE_CODE(color) )       {
782                         count = color & NOT_RLE_CODE;
783                         color = *src++;
784                 } else {
785                         // unique
786                         count = 1;
787                 }
788                 i += count;
789         }
790         count = i - x1;
791         i = x1;
792         // we know have '*count' pixels of 'color'.
793
794         if ( x1+count > x2 )    {
795                 count = x2-x1+1;
796                 for ( j=0; j<count; j++ )
797                         gr_bm_pixel( dest, dx++, dy, color );
798                 return;
799         }
800
801         for ( j=0; j<count; j++ )
802                 gr_bm_pixel( dest, dx++, dy, color );
803         i += count;
804
805         while( i <= x2 )                {
806                 color = *src++;
807                 if ( color == RLE_CODE ) return;
808                 if ( IS_RLE_CODE(color) )       {
809                         count = color & NOT_RLE_CODE;
810                         color = *src++;
811                 } else {
812                         // unique
813                         count = 1;
814                 }
815                 // we know have '*count' pixels of 'color'.
816                 if ( i+count <= x2 )    {
817                         for ( j=0; j<count; j++ )
818                                 gr_bm_pixel( dest, dx++, dy, color );
819                         i += count;
820                 } else {
821                         count = x2-i+1;
822                         for ( j=0; j<count; j++ )
823                                 gr_bm_pixel( dest, dx++, dy, color );
824                         i += count;
825                 }
826         }
827 }
828
829 void gr_rle_expand_scanline_generic_masked( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2  )
830 {
831         int i = 0, j;
832         int count;
833         ubyte color = 0;
834
835         if ( x2 < x1 ) return;
836
837         count = 0;
838         while ( i < x1 )        {
839                 color = *src++;
840                 if ( color == RLE_CODE ) return;
841                 if ( IS_RLE_CODE(color) )       {
842                         count = color & NOT_RLE_CODE;
843                         color = *src++;
844                 } else {
845                         // unique
846                         count = 1;
847                 }
848                 i += count;
849         }
850         count = i - x1;
851         i = x1;
852         // we know have '*count' pixels of 'color'.
853
854         if ( x1+count > x2 )    {
855                 count = x2-x1+1;
856                 if (color != TRANSPARENCY_COLOR) {
857                         for ( j=0; j<count; j++ )
858                                 gr_bm_pixel( dest, dx++, dy, color );
859                 }
860                 return;
861         }
862
863         if ( color != TRANSPARENCY_COLOR ) {
864                 for ( j=0; j<count; j++ )
865                         gr_bm_pixel( dest, dx++, dy, color );
866         } else
867                 dx += count;
868         i += count;
869
870         while( i <= x2 )                {
871                 color = *src++;
872                 if ( color == RLE_CODE ) return;
873                 if ( IS_RLE_CODE(color) )       {
874                         count = color & NOT_RLE_CODE;
875                         color = *src++;
876                 } else {
877                         // unique
878                         count = 1;
879                 }
880                 // we know have '*count' pixels of 'color'.
881                 if ( i+count <= x2 )    {
882                         if ( color != TRANSPARENCY_COLOR ) {
883                                 for ( j=0; j<count; j++ )
884                                         gr_bm_pixel( dest, dx++, dy, color );
885                         } else
886                                 dx += count;
887                         i += count;
888                 } else {
889                         count = x2-i+1;
890                         if ( color != TRANSPARENCY_COLOR ) {
891                                 for ( j=0; j<count; j++ )
892                                         gr_bm_pixel( dest, dx++, dy, color );
893                         } else
894                                 dx += count;
895                         i += count;
896                 }
897         }
898 }
899
900
901 #ifdef __MSDOS__
902 void gr_rle_expand_scanline_svga_masked( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2  )
903 {
904         int i = 0, j;
905         int count;
906         ubyte color;
907         ubyte * vram = (ubyte *)0xA0000;
908         int VideoLocation,page,offset;
909
910         if ( x2 < x1 ) return;
911
912         VideoLocation = (unsigned int)dest->bm_data + (dest->bm_rowsize * dy) + dx;
913         page    = VideoLocation >> 16;
914         offset  = VideoLocation & 0xFFFF;
915
916         gr_vesa_setpage( page );
917
918         if ( (offset + (x2-x1+1)) < 65536 )     {
919                 // We don't cross a svga page, so blit it fast!
920                 gr_rle_expand_scanline_masked( &vram[offset], src, x1, x2 );
921                 return;
922         }
923
924         count = 0;
925         while ( i < x1 )        {
926                 color = *src++;
927                 if ( color == RLE_CODE ) return;
928                 if ( IS_RLE_CODE(color) )       {
929                         count = color & NOT_RLE_CODE;
930                         color = *src++;
931                 } else {
932                         // unique
933                         count = 1;
934                 }
935                 i += count;
936         }
937         count = i - x1;
938         i = x1;
939         // we know have '*count' pixels of 'color'.
940
941         if ( x1+count > x2 )    {
942                 count = x2-x1+1;
943                 if (color != TRANSPARENCY_COLOR) {
944                         for ( j=0; j<count; j++ )       {
945                                 vram[offset++] = color;
946                                 if ( offset >= 65536 ) {
947                                         offset -= 65536;
948                                         page++;
949                                         gr_vesa_setpage(page);
950                                 }
951                         }
952                 }
953                 return;
954         }
955
956         if ( color != TRANSPARENCY_COLOR ) {
957                 for ( j=0; j<count; j++ )       {
958                         vram[offset++] = color;
959                         if ( offset >= 65536 ) {
960                                 offset -= 65536;
961                                 page++;
962                                 gr_vesa_setpage(page);
963                         }
964                 }
965         } else  {
966                 offset += count;
967                 if ( offset >= 65536 ) {
968                         offset -= 65536;
969                         page++;
970                         gr_vesa_setpage(page);
971                 }
972         }
973         i += count;
974
975         while( i <= x2 )                {
976                 color = *src++;
977                 if ( color == RLE_CODE ) return;
978                 if ( IS_RLE_CODE(color) )       {
979                         count = color & NOT_RLE_CODE;
980                         color = *src++;
981                 } else {
982                         // unique
983                         count = 1;
984                 }
985                 // we know have '*count' pixels of 'color'.
986                 if ( i+count <= x2 )    {
987                         if ( color != TRANSPARENCY_COLOR ) {
988                                 for ( j=0; j<count; j++ )       {
989                                         vram[offset++] = color;
990                                         if ( offset >= 65536 ) {
991                                                 offset -= 65536;
992                                                 page++;
993                                                 gr_vesa_setpage(page);
994                                         }
995                                 }
996                         } else  {
997                                 offset += count;
998                                 if ( offset >= 65536 ) {
999                                         offset -= 65536;
1000                                         page++;
1001                                         gr_vesa_setpage(page);
1002                                 }
1003                         }
1004                         i += count;
1005                 } else {
1006                         count = x2-i+1;
1007                         if ( color != TRANSPARENCY_COLOR ) {
1008                                 for ( j=0; j<count; j++ )       {
1009                                         vram[offset++] = color;
1010                                         if ( offset >= 65536 ) {
1011                                                 offset -= 65536;
1012                                                 page++;
1013                                                 gr_vesa_setpage(page);
1014                                         }
1015                                 }
1016                         } else  {
1017                                 offset += count;
1018                                 if ( offset >= 65536 ) {
1019                                         offset -= 65536;
1020                                         page++;
1021                                         gr_vesa_setpage(page);
1022                                 }
1023                         }
1024                         i += count;
1025                 }
1026         }
1027 }
1028 #endif // __MSDOS__
1029
1030
1031 /*
1032  * swaps entries 0 and 255 in an RLE bitmap without uncompressing it
1033  */
1034 void rle_swap_0_255(grs_bitmap *bmp)
1035 {
1036         int i, j, len, rle_big;
1037         unsigned char *ptr, *ptr2, *temp, *start;
1038         unsigned short line_size;
1039
1040         rle_big = 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         if (rle_big) {                  // set ptrs to first lines
1045                 ptr = bmp->bm_data + 4 + 2 * bmp->bm_h;
1046                 ptr2 = temp + 4 + 2 * bmp->bm_h;
1047         } else {
1048                 ptr = bmp->bm_data + 4 + bmp->bm_h;
1049                 ptr2 = temp + 4 + bmp->bm_h;
1050         }
1051         for (i = 0; i < bmp->bm_h; i++) {
1052                 start = ptr2;
1053                 if (rle_big)
1054                         line_size = INTEL_SHORT(*((unsigned short *)&bmp->bm_data[4 + 2 * i]));
1055                 else
1056                         line_size = bmp->bm_data[4 + i];
1057                 for (j = 0; j < line_size; j++) {
1058                         if ( ! IS_RLE_CODE(ptr[j]) ) {
1059                                 if (ptr[j] == 0) {
1060                                         *ptr2++ = RLE_CODE | 1;
1061                                         *ptr2++ = 255;
1062                                 } else
1063                                         *ptr2++ = ptr[j];
1064                         } else {
1065                                 *ptr2++ = ptr[j];
1066                                 if ((ptr[j] & NOT_RLE_CODE) == 0)
1067                                         break;
1068                                 j++;
1069                                 if (ptr[j] == 0)
1070                                         *ptr2++ = 255;
1071                                 else if (ptr[j] == 255)
1072                                         *ptr2++ = 0;
1073                                 else
1074                                         *ptr2++ = ptr[j];
1075                         }
1076                 }
1077                 if (rle_big)                // set line size
1078                         *((unsigned short *)&temp[4 + 2 * i]) = ptr2 - start;
1079                 else
1080                         temp[4 + i] = ptr2 - start;
1081                 ptr += line_size;           // go to next line
1082         }
1083         len = ptr2 - temp;
1084         *((int *)temp) = len;           // set total size
1085         memcpy(bmp->bm_data, temp, len);
1086         d_free(temp);
1087 }
1088
1089 /*
1090  * remaps all entries using colormap in an RLE bitmap without uncompressing it
1091  */
1092 void rle_remap(grs_bitmap *bmp, ubyte *colormap)
1093 {
1094         int i, j, len, rle_big;
1095         unsigned char *ptr, *ptr2, *temp, *start;
1096         unsigned short line_size;
1097
1098         rle_big = bmp->bm_flags & BM_FLAG_RLE_BIG;
1099
1100         temp = d_malloc(4 + bmp->bm_h + (bmp->bm_w + 1) * bmp->bm_h + 30000);
1101
1102         if (rle_big) {                  // set ptrs to first lines
1103                 ptr = bmp->bm_data + 4 + 2 * bmp->bm_h;
1104                 ptr2 = temp + 4 + 2 * bmp->bm_h;
1105         } else {
1106                 ptr = bmp->bm_data + 4 + bmp->bm_h;
1107                 ptr2 = temp + 4 + bmp->bm_h;
1108         }
1109         for (i = 0; i < bmp->bm_h; i++) {
1110                 start = ptr2;
1111                 if (rle_big)
1112                         line_size = *((unsigned short *)&bmp->bm_data[4 + 2 * i]);
1113                 else
1114                         line_size = bmp->bm_data[4 + i];
1115                 for (j = 0; j < line_size; j++) {
1116                         if ( ! IS_RLE_CODE(ptr[j])) {
1117                                 if (IS_RLE_CODE(colormap[ptr[j]])) 
1118                                         *ptr2++ = RLE_CODE | 1; // add "escape sequence"
1119                                 *ptr2++ = colormap[ptr[j]]; // translate
1120                         } else {
1121                                 *ptr2++ = ptr[j]; // just copy current rle code
1122                                 if ((ptr[j] & NOT_RLE_CODE) == 0)
1123                                         break;
1124                                 j++;
1125                                 *ptr2++ = colormap[ptr[j]]; // translate
1126                         }
1127                 }
1128                 if (rle_big)                // set line size
1129                         *((unsigned short *)&temp[4 + 2 * i]) = INTEL_SHORT(ptr2 - start);
1130                 else
1131                         temp[4 + i] = ptr2 - start;
1132                 ptr += line_size;           // go to next line
1133         }
1134         len = ptr2 - temp;
1135         *((int *)temp) = len;           // set total size
1136         memcpy(bmp->bm_data, temp, len);
1137         d_free(temp);
1138 }