implement BM_FLAG_RLE_BIG (cockpit support?)
[btb/d2x.git] / 2d / rle.c
1 /* $Id: rle.c,v 1.7 2002-08-17 11:19:56 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  * Changed shorts to ints in parameters.
18  *
19  */
20
21 #ifdef HAVE_CONFIG_H
22 #include <conf.h>
23 #endif
24
25 #ifdef RCS
26 static char rcsid[] = "$Id: rle.c,v 1.7 2002-08-17 11:19:56 btb Exp $";
27 #endif
28
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32
33 #include "pstypes.h"
34 #include "u_mem.h"
35 #include "mono.h"
36
37
38 #include "gr.h"
39 #include "grdef.h"
40 #include "error.h"
41 //#include "key.h"
42 #include "rle.h"
43 //#define RLE_CODE              0xC0
44 //#define NOT_RLE_CODE  63
45
46 #define RLE_CODE                        0xE0
47 #define NOT_RLE_CODE            31
48
49 void rle_expand_texture_sub( grs_bitmap * bmp, grs_bitmap * rle_temp_bitmap_1 );
50
51 #ifndef NO_ASM
52 #ifdef __WATCOMC__
53 int gr_rle_decode_asm( ubyte * src, ubyte * dest );
54 #pragma aux gr_rle_decode_asm parm [esi] [edi] value [edi] modify exact [eax ebx ecx edx esi edi] = \
55 "  cld                  " \
56 "   xor ecx, ecx        " \
57 "   cld                 " \
58 "   jmp NextByte        " \
59 "                           " \
60 "Unique:                    " \
61 "   mov [edi],al        " \
62 "   inc edi         " \
63 "                           " \
64 "NextByte:              " \
65 "   mov al,[esi]        " \
66 "   inc esi         " \
67 "                           " \
68 "   mov ah, al      " \
69 "   and ah, 0xE0    " \
70 "  cmp  ah, 0xE0        " \
71 "   jne   Unique        " \
72 "                           " \
73 "   mov cl, al      " \
74 "   and cl, 31          " \
75 "   je      done            " \
76 "                           " \
77 "   mov al,[esi]        " \
78 "   inc esi         " \
79 "   mov ah, al      " \
80 "   shr ecx,1           " \
81 "   rep stosw           " \
82 "   jnc NextByte        " \
83 "   mov [edi],al        " \
84 "   inc edi         " \
85 "                           " \
86 "   jmp NextByte        " \
87 "                           " \
88 "done:                  ";
89
90 void rle_stosb(char *dest, int len, int color);
91 #pragma aux rle_stosb = "cld rep    stosb" parm [edi] [ecx] [eax] modify exact [edi ecx];
92 #elif defined __GNUC__
93 static inline int gr_rle_decode_asm( ubyte * src, ubyte * dest ) {
94    register int __ret;
95    int dummy;
96    __asm__ __volatile__ (
97 "   cld;"
98 "   xorl %%ecx, %%ecx;"
99 "   jmp 1f;"
100 "0:;"
101 "   movb %%al,(%%edi);"
102 "   incl %%edi;"
103 "1:;"
104 "   movb (%%esi), %%al;"
105 "   incl %%esi;"
106 "   movb %%al, %%ah;"
107 "   andb $0xE0, %%ah;"
108 "   cmpb $0xE0, %%ah;"
109 "   jne 0b;"
110 "   movb %%al, %%cl;"
111 "   andb $31, %%cl;"
112 "   je 2f;"
113 "   movb (%%esi), %%al;"
114 "   incl %%esi;"
115 "   movb %%al, %%ah;"
116 "   shrl $1, %%ecx;"
117 "   rep; stosw;"
118 "   jnc 1b;"
119 "   movb %%al, (%%edi);"
120 "   incl %%edi;"
121 "   jmp 1b;"
122 "2:"
123 : "=D" (__ret), "=S" (dummy) : "1" (src), "D" (dest) : "%eax", "%ecx");
124   return __ret;
125 }
126
127 static inline void rle_stosb(char *dest, int len, int color) {
128         int dummy[2];
129    __asm__ __volatile__ (
130     "cld; rep; stosb"
131     : "=D" (dummy[0]), "=c" (dummy[1])
132         : "0" (dest), "1" (len), "a" (color) );
133 }
134 #elif defined _MSC_VER
135 __inline int gr_rle_decode_asm( ubyte * src, ubyte * dest )
136 {
137          int retval;
138         __asm {
139                 mov esi,[src]
140                 mov edi,[dest]
141         xor ecx, ecx
142                 cld
143                 jmp NextByte
144 Unique:
145                 mov [edi], al
146                 inc edi
147 NextByte:
148                 mov al,[esi]
149                 inc esi
150                 mov ah, al
151                 and ah,0xE0
152                 cmp ah,0xE0
153                 jne Unique
154
155                 mov cl, al
156                 and cl, 31
157                 je done
158
159                 mov al, [esi]
160                 inc esi
161                 mov ah, al
162                 shr ecx, 1
163                 rep stosw
164                 jnc NextByte
165                 mov [edi], al
166                 inc edi
167                 jmp NextByte
168 done:
169                 mov [retval],edi
170         }
171         return retval;
172 }
173
174 __inline void rle_stosb(char *dest, int len, int color)
175 {
176   __asm {
177         mov edi,[dest]
178         mov ecx,[len]
179         mov eax,[color]
180         cld
181         rep stosb
182   }
183 }
184
185 #else
186 # undef NO_ASM
187 # define NO_ASM 1
188 /* Well, if inline assembler is not supported for this compiler, we don't
189  **really** want ASM... */
190 #endif
191 #endif
192
193 #ifdef NO_ASM
194 void rle_stosb(ubyte *dest, int len, int color)
195 {
196         int i;
197         for (i=0; i<len; i++ )
198                 *dest++ = color;
199 }
200 #endif
201
202 void gr_rle_decode( ubyte * src, ubyte * dest )
203 {
204 #ifdef NO_ASM
205         int i;
206         ubyte data, count = 0;
207
208         while(1) {
209                 data = *src++;
210                 if ( (data & RLE_CODE) != RLE_CODE ) {
211                         *dest++ = data;
212                 } else {
213                         count = data & NOT_RLE_CODE;
214                         if (count==0) return;
215                         data = *src++;
216                         for (i=0; i<count; i++ )        
217                                 *dest++ = data;
218                 }
219         }
220 #else
221     gr_rle_decode_asm( src, dest );
222 #endif
223 }
224
225 // Given pointer to start of one scanline of rle data, uncompress it to
226 // dest, from source pixels x1 to x2.
227 void gr_rle_expand_scanline_masked( ubyte *dest, ubyte *src, int x1, int x2  )
228 {
229         int i = 0;
230         ubyte count=0;
231         ubyte color=0;
232
233         if ( x2 < x1 ) return;
234
235         while ( i < x1 )        {
236                 color = *src++;
237                 if ( color == RLE_CODE ) return;
238                 if ( (color & RLE_CODE)==RLE_CODE )     {
239                         count = color & (~RLE_CODE);
240                         color = *src++;
241                 } else {
242                         // unique
243                         count = 1;
244                 }
245                 i += count;
246         }
247         count = i - x1;
248         i = x1;
249         // we know have '*count' pixels of 'color'.
250         
251         if ( x1+count > x2 )    {
252                 count = x2-x1+1;
253                 if ( color != 255 )     rle_stosb( dest, count, color );
254                 return;
255         }
256
257         if ( color != 255 )     rle_stosb( dest, count, color );
258         dest += count;
259         i += count;
260
261         while( i <= x2 )                {
262                 color = *src++;
263                 if ( color == RLE_CODE ) return;
264                 if ( (color & RLE_CODE) == (RLE_CODE) ) {
265                         count = color & (~RLE_CODE);
266                         color = *src++;
267                 } else {
268                         // unique
269                         count = 1;
270                 }
271                 // we know have '*count' pixels of 'color'.
272                 if ( i+count <= x2 )    {
273                         if ( color != 255 )rle_stosb( dest, count, color );
274                         i += count;
275                         dest += count;
276                 } else {
277                         count = x2-i+1;
278                         if ( color != 255 )rle_stosb( dest, count, color );
279                         i += count;
280                         dest += count;
281                 }
282
283         }       
284 }
285
286 void gr_rle_expand_scanline( ubyte *dest, ubyte *src, int x1, int x2  )
287 {
288         int i = 0;
289         ubyte count=0;
290         ubyte color=0;
291
292         if ( x2 < x1 ) return;
293
294         while ( i < x1 )        {
295                 color = *src++;
296                 if ( color == RLE_CODE ) return;
297                 if ( (color & RLE_CODE)==RLE_CODE )     {
298                         count = color & (~RLE_CODE);
299                         color = *src++;
300                 } else {
301                         // unique
302                         count = 1;
303                 }
304                 i += count;
305         }
306         count = i - x1;
307         i = x1;
308         // we know have '*count' pixels of 'color'.
309         
310         if ( x1+count > x2 )    {
311                 count = x2-x1+1;
312                 rle_stosb( dest, count, color );
313                 return;
314         }
315
316         rle_stosb( dest, count, color );
317         dest += count;
318         i += count;
319
320         while( i <= x2 )                {
321                 color = *src++;
322                 if ( color == RLE_CODE ) return;
323                 if ( (color & RLE_CODE)==RLE_CODE )     {
324                         count = color & (~RLE_CODE);
325                         color = *src++;
326                 } else {
327                         // unique
328                         count = 1;
329                 }
330                 // we know have '*count' pixels of 'color'.
331                 if ( i+count <= x2 )    {
332                         rle_stosb( dest, count, color );
333                         i += count;
334                         dest += count;
335                 } else {
336                         count = x2-i+1;
337                         rle_stosb( dest, count, color );
338                         i += count;
339                         dest += count;
340                 }
341         }       
342 }
343
344
345 int gr_rle_encode( int org_size, ubyte *src, ubyte *dest )
346 {
347         int i;
348         ubyte c, oc;
349         ubyte count;
350         ubyte *dest_start;
351
352         dest_start = dest;
353         oc = *src++;
354         count = 1;
355
356         for (i=1; i<org_size; i++ )     {
357                 c = *src++;                                                     
358                 if ( c!=oc )    {
359                         if ( count )    {
360                                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )        {
361                                         *dest++ = oc;
362                                         Assert( oc != RLE_CODE );
363                                 } else {
364                                         count |= RLE_CODE;
365                                         *dest++ = count;
366                                         *dest++ = oc;
367                                 }
368                         }
369                         oc = c;
370                         count = 0;
371                 }
372                 count++;
373                 if ( count == NOT_RLE_CODE )    {
374                         count |= RLE_CODE;
375                         *dest++=count;
376                         *dest++=oc;
377                         count = 0;
378                 }
379         }
380         if (count)      {
381                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )        {
382                         *dest++ = oc;
383                         Assert( oc != RLE_CODE );
384                 } else {
385                         count |= RLE_CODE;
386                         *dest++ = count;
387                         *dest++ = oc;
388                 }
389         }
390         *dest++ = RLE_CODE;
391
392         return dest-dest_start;
393 }
394
395
396 int gr_rle_getsize( int org_size, ubyte *src )
397 {
398         int i;
399         ubyte c, oc;
400         ubyte count;
401         int dest_size=0;
402
403         oc = *src++;
404         count = 1;
405
406         for (i=1; i<org_size; i++ )     {
407                 c = *src++;                                                     
408                 if ( c!=oc )    {
409                         if ( count )    {
410                                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )        {
411                                         dest_size++;
412                                 } else {
413                                         dest_size++;
414                                         dest_size++;
415                                 }
416                         }
417                         oc = c;
418                         count = 0;
419                 }
420                 count++;
421                 if ( count == NOT_RLE_CODE )    {
422                         dest_size++;
423                         dest_size++;
424                         count = 0;
425                 }
426         }
427         if (count)      {
428                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )        {
429                         dest_size++;
430                 } else {
431                         dest_size++;
432                         dest_size++;
433                 }
434         }
435         dest_size++;
436
437         return dest_size;
438 }
439
440 int gr_bitmap_rle_compress( grs_bitmap * bmp )
441 {
442         int y, d1, d;
443         int doffset;
444         ubyte *rle_data;
445         int large_rle = 0;
446
447         // first must check to see if this is large bitmap.
448
449         for (y=0; y<bmp->bm_h; y++ )    {
450                 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
451                 if (d1 > 255) {
452                         large_rle = 1;
453                         break;
454                 }
455         }
456
457         rle_data=d_malloc( (bmp->bm_w+1) * bmp->bm_h );
458         if (rle_data==NULL) return 0;
459         if (!large_rle)
460                 doffset = 4 + bmp->bm_h;
461         else
462                 doffset = 4 + (2 * bmp->bm_h);          // each row of rle'd bitmap has short instead of byte offset now
463
464         for (y=0; y<bmp->bm_h; y++ )    {
465                 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
466                 if ( ((doffset+d1) > bmp->bm_w*bmp->bm_h) || (d1 > (large_rle?32767:255) ) ) {
467                         d_free(rle_data);
468                         return 0;
469                 }
470                 d = gr_rle_encode( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y], &rle_data[doffset] );
471                 Assert( d==d1 );
472                 doffset += d;
473                 if (large_rle)
474                         *((short *)&(rle_data[(y*2)+4])) = (short)d;
475                 else
476                         rle_data[y+4] = d;
477         }
478         //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 );
479         memcpy(         rle_data, &doffset, 4 );
480         memcpy(         bmp->bm_data, rle_data, doffset );
481         d_free(rle_data);
482         bmp->bm_flags |= BM_FLAG_RLE;
483         if (large_rle)
484                 bmp->bm_flags |= BM_FLAG_RLE_BIG;
485         return 1;
486 }
487
488 #define MAX_CACHE_BITMAPS 32
489
490 typedef struct rle_cache_element {
491         grs_bitmap * rle_bitmap;
492         ubyte * rle_data;
493         grs_bitmap * expanded_bitmap;                   
494         int last_used;
495 } rle_cache_element;
496
497 int rle_cache_initialized = 0;
498 int rle_counter = 0;
499 int rle_next = 0;
500 rle_cache_element rle_cache[MAX_CACHE_BITMAPS];
501
502 int rle_hits = 0;
503 int rle_misses = 0;
504
505 void rle_cache_close(void)
506 {
507         if (rle_cache_initialized)      {
508                 int i;
509                 rle_cache_initialized = 0;
510                 for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
511                         gr_free_bitmap(rle_cache[i].expanded_bitmap);
512                 }
513         }
514 }
515
516 void rle_cache_init()
517 {
518         int i;
519         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
520                 rle_cache[i].rle_bitmap = NULL;
521                 rle_cache[i].expanded_bitmap = gr_create_bitmap( 64, 64 );
522                 rle_cache[i].last_used = 0;
523                 Assert( rle_cache[i].expanded_bitmap != NULL );
524         }       
525         rle_cache_initialized = 1;
526         atexit( rle_cache_close );
527 }
528
529 void rle_cache_flush()
530 {
531         int i;
532         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
533                 rle_cache[i].rle_bitmap = NULL;
534                 rle_cache[i].last_used = 0;
535         }       
536 }
537
538
539
540 grs_bitmap * rle_expand_texture( grs_bitmap * bmp )
541 {
542         int i;
543         int lowest_count, lc;
544         int least_recently_used;
545
546         if (!rle_cache_initialized) rle_cache_init();
547
548         Assert( !(bmp->bm_flags & BM_FLAG_PAGED_OUT) );
549
550         lc = rle_counter;
551         rle_counter++;
552         if ( rle_counter < lc ) {
553                 for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
554                         rle_cache[i].rle_bitmap = NULL;
555                         rle_cache[i].last_used = 0;
556                 }
557         }
558
559 //      if (((rle_counter % 100)==1) && (rle_hits+rle_misses > 0))
560 //              mprintf(( 0, "RLE-CACHE %d%%, H:%d, M:%d\n", (rle_misses*100)/(rle_hits+rle_misses), rle_hits, rle_misses ));
561
562         lowest_count = rle_cache[rle_next].last_used;
563         least_recently_used = rle_next;
564         rle_next++;
565         if ( rle_next >= MAX_CACHE_BITMAPS )
566                 rle_next = 0;
567                 
568         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
569                 if (rle_cache[i].rle_bitmap == bmp)     {
570                         rle_hits++;
571                         rle_cache[i].last_used = rle_counter;
572                         return rle_cache[i].expanded_bitmap;
573                 }
574                 if ( rle_cache[i].last_used < lowest_count )    {
575                         lowest_count = rle_cache[i].last_used;
576                         least_recently_used = i;
577                 }
578         }       
579         rle_misses++;
580         rle_expand_texture_sub( bmp, rle_cache[least_recently_used].expanded_bitmap );
581         rle_cache[least_recently_used].rle_bitmap = bmp;
582         rle_cache[least_recently_used].last_used = rle_counter;
583         return rle_cache[least_recently_used].expanded_bitmap;
584 }
585
586 void rle_expand_texture_sub( grs_bitmap * bmp, grs_bitmap * rle_temp_bitmap_1 )
587 {
588         unsigned char * dbits;
589         unsigned char * sbits;
590         int i;
591 #ifndef NO_ASM
592         unsigned char * dbits1;
593 #endif
594
595 #ifdef D1XD3D
596         Assert (bmp->iMagic == BM_MAGIC_NUMBER);
597 #endif
598
599         sbits = &bmp->bm_data[4 + 64];
600         dbits = rle_temp_bitmap_1->bm_data;
601
602         rle_temp_bitmap_1->bm_flags = bmp->bm_flags & (~BM_FLAG_RLE);
603
604         for (i=0; i < 64; i++ )    {
605 #ifdef NO_ASM
606                 gr_rle_decode(sbits,dbits);
607 #else
608                 dbits1=(unsigned char *)gr_rle_decode_asm( sbits, dbits );
609 #endif
610                 sbits += (int)bmp->bm_data[4+i];
611                 dbits += 64;
612 #ifndef NO_ASM
613                 Assert( dbits == dbits1 );              // Get John, bogus rle data!
614 #endif
615         }
616 #ifdef D1XD3D
617         gr_set_bitmap_data (rle_temp_bitmap_1, rle_temp_bitmap_1->bm_data);
618 #endif
619 }
620
621
622 void gr_rle_expand_scanline_generic( grs_bitmap * dest, int dx, int dy, ubyte *src, 
623         int x1, int x2, int masked  )
624 {
625         int i = 0, j;
626         int count=0;
627         ubyte color=0;
628
629         if ( x2 < x1 ) return;
630
631         while ( i < x1 )        {
632                 color = *src++;
633                 if ( color == RLE_CODE ) return;
634                 if ( (color & RLE_CODE) == RLE_CODE )   {
635                         count = color & NOT_RLE_CODE;
636                         color = *src++;
637                 } else {
638                         // unique
639                         count = 1;
640                 }
641                 i += count;
642         }
643         count = i - x1;
644         i = x1;
645         // we know have '*count' pixels of 'color'.
646         
647         if ( x1+count > x2 )    {
648                 count = x2-x1+1;
649                 if (!masked || color != 255)
650                 for ( j=0; j<count; j++ )
651                         gr_bm_pixel( dest, dx++, dy, color );
652                 return;
653         }
654
655         if (masked && color == 255)
656                 dx += count;
657         else
658         for ( j=0; j<count; j++ )
659                 gr_bm_pixel( dest, dx++, dy, color );
660         i += count;
661
662         while( i <= x2 )                {
663                 color = *src++;
664                 if ( color == RLE_CODE ) return;
665                 if ( (color & RLE_CODE) == RLE_CODE )   {
666                         count = color & NOT_RLE_CODE;
667                         color = *src++;
668                 } else {
669                         // unique
670                         count = 1;
671                 }
672                 // we know have '*count' pixels of 'color'.
673                 if ( i+count <= x2 )    {
674                         if (masked && color == 255)
675                                 dx += count;
676                         else
677                         for ( j=0; j<count; j++ )
678                                 gr_bm_pixel( dest, dx++, dy, color );
679                         i += count;
680                 } else {
681                         count = x2-i+1;
682                         if (masked && color == 255)
683                                 dx += count;
684                         else
685                         for ( j=0; j<count; j++ )
686                                 gr_bm_pixel( dest, dx++, dy, color );
687                         i += count;
688                 }
689         }
690 }
691
692 /*
693  * swaps entries 0 and 255 in an RLE bitmap without uncompressing it
694  *
695  * doesn't handle RLE_BIG yet, but neither does anything else...
696  * LEAKS LOTS OF MEMORY!
697  */
698 void rle_swap_0_255(grs_bitmap *bmp)
699 {
700         int i, j;
701         unsigned char *ptr, *ptr2, *temp, *start;
702
703         if (bmp->bm_flags & BM_FLAG_RLE_BIG)
704                 return;
705
706         temp = d_malloc(4 + bmp->bm_h + (bmp->bm_w + 1) * bmp->bm_h);
707
708         *((int *)temp) = 4;
709         ptr = bmp->bm_data + 4 + bmp->bm_h;
710         ptr2 = temp + 4 + bmp->bm_h;
711         for (i = 0; i < bmp->bm_h; i++) {
712                 start = ptr2;
713                 for (j = 0; j < bmp->bm_data[4 + i]; j++) {
714                         if ((ptr[j] & RLE_CODE) != RLE_CODE) {
715                                 if (ptr[j] == 0) {
716                                         *ptr2++ = RLE_CODE | 1;
717                                         *ptr2++ = 255;
718                                 } else
719                                         *ptr2++ = ptr[j];
720                         } else {
721                                 *ptr2++ = ptr[j];
722                                 if ((ptr[j] & NOT_RLE_CODE) == 0)
723                                         break;
724                                 j++;
725                                 if (ptr[j] == 0)
726                                         *ptr2++ = 255;
727                                 else if (ptr[j] == 255)
728                                         *ptr2++ = 0;
729                                 else
730                                         *ptr2++ = ptr[j];
731                         }
732                 }
733                 temp[4 + i] = ptr2 - start;
734                 *((int *)temp) += ptr2 - start;
735                 ptr += bmp->bm_data[4 + i];
736         }
737         bmp->bm_data = temp;
738 }