]> icculus.org git repositories - btb/d2x.git/blob - 2d/rle.c
b1124390cfb8e3c6b399dd49cc214de20bcbb786
[btb/d2x.git] / 2d / rle.c
1 /* $Id: rle.c,v 1.6 2002-08-15 08:53:11 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.6 2002-08-15 08:53:11 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
446         rle_data=d_malloc( (bmp->bm_w+1)* bmp->bm_h );
447         if (rle_data==NULL) return 0;
448         doffset = 4 + bmp->bm_h;
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 ( ((doffset+d1) > bmp->bm_w*bmp->bm_h) || (d1 > 255 ) )      {
452                         d_free(rle_data);
453                         return 0;
454                 }
455                 d = gr_rle_encode( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y], &rle_data[doffset] );
456                 Assert( d==d1 );
457                 doffset += d;
458                 rle_data[y+4] = d;
459         }
460         //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 );
461         memcpy(         rle_data, &doffset, 4 );
462         memcpy(         bmp->bm_data, rle_data, doffset );
463         d_free(rle_data);
464         bmp->bm_flags |= BM_FLAG_RLE;
465         return 1;
466 }
467
468 #define MAX_CACHE_BITMAPS 32
469
470 typedef struct rle_cache_element {
471         grs_bitmap * rle_bitmap;
472         ubyte * rle_data;
473         grs_bitmap * expanded_bitmap;                   
474         int last_used;
475 } rle_cache_element;
476
477 int rle_cache_initialized = 0;
478 int rle_counter = 0;
479 int rle_next = 0;
480 rle_cache_element rle_cache[MAX_CACHE_BITMAPS];
481
482 int rle_hits = 0;
483 int rle_misses = 0;
484
485 void rle_cache_close(void)
486 {
487         if (rle_cache_initialized)      {
488                 int i;
489                 rle_cache_initialized = 0;
490                 for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
491                         gr_free_bitmap(rle_cache[i].expanded_bitmap);
492                 }
493         }
494 }
495
496 void rle_cache_init()
497 {
498         int i;
499         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
500                 rle_cache[i].rle_bitmap = NULL;
501                 rle_cache[i].expanded_bitmap = gr_create_bitmap( 64, 64 );
502                 rle_cache[i].last_used = 0;
503                 Assert( rle_cache[i].expanded_bitmap != NULL );
504         }       
505         rle_cache_initialized = 1;
506         atexit( rle_cache_close );
507 }
508
509 void rle_cache_flush()
510 {
511         int i;
512         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
513                 rle_cache[i].rle_bitmap = NULL;
514                 rle_cache[i].last_used = 0;
515         }       
516 }
517
518
519
520 grs_bitmap * rle_expand_texture( grs_bitmap * bmp )
521 {
522         int i;
523         int lowest_count, lc;
524         int least_recently_used;
525
526         if (!rle_cache_initialized) rle_cache_init();
527
528         Assert( !(bmp->bm_flags & BM_FLAG_PAGED_OUT) );
529
530         lc = rle_counter;
531         rle_counter++;
532         if ( rle_counter < lc ) {
533                 for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
534                         rle_cache[i].rle_bitmap = NULL;
535                         rle_cache[i].last_used = 0;
536                 }
537         }
538
539 //      if (((rle_counter % 100)==1) && (rle_hits+rle_misses > 0))
540 //              mprintf(( 0, "RLE-CACHE %d%%, H:%d, M:%d\n", (rle_misses*100)/(rle_hits+rle_misses), rle_hits, rle_misses ));
541
542         lowest_count = rle_cache[rle_next].last_used;
543         least_recently_used = rle_next;
544         rle_next++;
545         if ( rle_next >= MAX_CACHE_BITMAPS )
546                 rle_next = 0;
547                 
548         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
549                 if (rle_cache[i].rle_bitmap == bmp)     {
550                         rle_hits++;
551                         rle_cache[i].last_used = rle_counter;
552                         return rle_cache[i].expanded_bitmap;
553                 }
554                 if ( rle_cache[i].last_used < lowest_count )    {
555                         lowest_count = rle_cache[i].last_used;
556                         least_recently_used = i;
557                 }
558         }       
559         rle_misses++;
560         rle_expand_texture_sub( bmp, rle_cache[least_recently_used].expanded_bitmap );
561         rle_cache[least_recently_used].rle_bitmap = bmp;
562         rle_cache[least_recently_used].last_used = rle_counter;
563         return rle_cache[least_recently_used].expanded_bitmap;
564 }
565
566 void rle_expand_texture_sub( grs_bitmap * bmp, grs_bitmap * rle_temp_bitmap_1 )
567 {
568         unsigned char * dbits;
569         unsigned char * sbits;
570         int i;
571 #ifndef NO_ASM
572         unsigned char * dbits1;
573 #endif
574
575 #ifdef D1XD3D
576         Assert (bmp->iMagic == BM_MAGIC_NUMBER);
577 #endif
578
579         sbits = &bmp->bm_data[4 + 64];
580         dbits = rle_temp_bitmap_1->bm_data;
581
582         rle_temp_bitmap_1->bm_flags = bmp->bm_flags & (~BM_FLAG_RLE);
583
584         for (i=0; i < 64; i++ )    {
585 #ifdef NO_ASM
586                 gr_rle_decode(sbits,dbits);
587 #else
588                 dbits1=(unsigned char *)gr_rle_decode_asm( sbits, dbits );
589 #endif
590                 sbits += (int)bmp->bm_data[4+i];
591                 dbits += 64;
592 #ifndef NO_ASM
593                 Assert( dbits == dbits1 );              // Get John, bogus rle data!
594 #endif
595         }
596 #ifdef D1XD3D
597         gr_set_bitmap_data (rle_temp_bitmap_1, rle_temp_bitmap_1->bm_data);
598 #endif
599 }
600
601
602 void gr_rle_expand_scanline_generic( grs_bitmap * dest, int dx, int dy, ubyte *src, 
603         int x1, int x2, int masked  )
604 {
605         int i = 0, j;
606         int count=0;
607         ubyte color=0;
608
609         if ( x2 < x1 ) return;
610
611         while ( i < x1 )        {
612                 color = *src++;
613                 if ( color == RLE_CODE ) return;
614                 if ( (color & RLE_CODE) == RLE_CODE )   {
615                         count = color & NOT_RLE_CODE;
616                         color = *src++;
617                 } else {
618                         // unique
619                         count = 1;
620                 }
621                 i += count;
622         }
623         count = i - x1;
624         i = x1;
625         // we know have '*count' pixels of 'color'.
626         
627         if ( x1+count > x2 )    {
628                 count = x2-x1+1;
629                 if (!masked || color != 255)
630                 for ( j=0; j<count; j++ )
631                         gr_bm_pixel( dest, dx++, dy, color );
632                 return;
633         }
634
635         if (masked && color == 255)
636                 dx += count;
637         else
638         for ( j=0; j<count; j++ )
639                 gr_bm_pixel( dest, dx++, dy, color );
640         i += count;
641
642         while( i <= x2 )                {
643                 color = *src++;
644                 if ( color == RLE_CODE ) return;
645                 if ( (color & RLE_CODE) == RLE_CODE )   {
646                         count = color & NOT_RLE_CODE;
647                         color = *src++;
648                 } else {
649                         // unique
650                         count = 1;
651                 }
652                 // we know have '*count' pixels of 'color'.
653                 if ( i+count <= x2 )    {
654                         if (masked && color == 255)
655                                 dx += count;
656                         else
657                         for ( j=0; j<count; j++ )
658                                 gr_bm_pixel( dest, dx++, dy, color );
659                         i += count;
660                 } else {
661                         count = x2-i+1;
662                         if (masked && color == 255)
663                                 dx += count;
664                         else
665                         for ( j=0; j<count; j++ )
666                                 gr_bm_pixel( dest, dx++, dy, color );
667                         i += count;
668                 }
669         }
670 }
671
672 /*
673  * swaps entries 0 and 255 in an RLE bitmap without uncompressing it
674  *
675  * doesn't handle RLE_BIG yet, but neither does anything else...
676  * LEAKS LOTS OF MEMORY!
677  */
678 void rle_swap_0_255(grs_bitmap *bmp)
679 {
680         int i, j;
681         unsigned char *ptr, *ptr2, *temp, *start;
682
683         if (bmp->bm_flags & BM_FLAG_RLE_BIG)
684                 return;
685
686         temp = d_malloc(4 + bmp->bm_h + (bmp->bm_w + 1) * bmp->bm_h);
687
688         *((int *)temp) = 4;
689         ptr = bmp->bm_data + 4 + bmp->bm_h;
690         ptr2 = temp + 4 + bmp->bm_h;
691         for (i = 0; i < bmp->bm_h; i++) {
692                 start = ptr2;
693                 for (j = 0; j < bmp->bm_data[4 + i]; j++) {
694                         if ((ptr[j] & RLE_CODE) != RLE_CODE) {
695                                 if (ptr[j] == 0) {
696                                         *ptr2++ = RLE_CODE | 1;
697                                         *ptr2++ = 255;
698                                 } else
699                                         *ptr2++ = ptr[j];
700                         } else {
701                                 *ptr2++ = ptr[j];
702                                 if ((ptr[j] & NOT_RLE_CODE) == 0)
703                                         break;
704                                 j++;
705                                 if (ptr[j] == 0)
706                                         *ptr2++ = 255;
707                                 else if (ptr[j] == 255)
708                                         *ptr2++ = 0;
709                                 else
710                                         *ptr2++ = ptr[j];
711                         }
712                 }
713                 temp[4 + i] = ptr2 - start;
714                 *((int *)temp) += ptr2 - start;
715                 ptr += bmp->bm_data[4 + i];
716         }
717         bmp->bm_data = temp;
718 }