1 /* $Id: rle.c,v 1.17 2004-01-08 20:31:35 schaffner Exp $ */
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.
17 * Routines to do run length encoding/decoding
20 * Changed shorts to ints in parameters.
24 * Revision 1.10 1995/08/14 14:26:34 allender
25 * changed transparency color to 0
27 * Revision 1.9 1995/07/05 16:07:49 allender
28 * transparency/kitchen chagnes
30 * Revision 1.8 1995/05/12 11:54:03 allender
31 * changed memory stuff again
33 * Revision 1.7 1995/05/11 12:49:19 allender
34 * change transparency color
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!!!!)
40 * Revision 1.5 1995/05/01 08:40:32 allender
41 * trying to find memory bug....this stuff works -- it's johns code
43 * Revision 1.4 1995/04/27 07:38:24 allender
44 * new rle code ala John
46 * Revision 1.3 1995/04/19 14:36:06 allender
47 * *** empty log message ***
49 * Revision 1.2 1995/04/18 12:08:30 allender
50 * *** empty log message ***
52 * Revision 1.1 1995/03/09 09:23:04 allender
56 * --- PC RCS information ---
57 * Revision 1.19 1995/01/14 19:18:31 john
58 * Added assert to check for paged out bitmap.
60 * Revision 1.18 1995/01/14 11:32:07 john
61 * Added rle_cache_flush function.
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.
68 * Revision 1.16 1994/11/30 00:55:03 mike
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.
75 * Revision 1.14 1994/11/23 16:03:46 john
76 * Fixed generic rle'ing to use new bit method.
78 * Revision 1.13 1994/11/23 15:45:51 john
79 * Changed to a 3 bit rle scheme.
81 * Revision 1.12 1994/11/18 22:50:24 john
82 * Changed shorts to ints in parameters.
84 * Revision 1.11 1994/11/14 17:06:13 john
87 * Revision 1.10 1994/11/14 15:54:09 john
88 * Put code in for maybe checking bogus rle data.
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.
94 * Revision 1.8 1994/11/10 10:31:20 john
95 * Reduce cache buffers to 16.
97 * Revision 1.7 1994/11/09 19:53:43 john
98 * Added texture rle caching.
100 * Revision 1.6 1994/11/09 17:41:44 john
101 * Made a slow version of rle bitblt to svga, modex.
103 * Revision 1.5 1994/11/09 17:07:50 john
104 * Fixed bug with bitmap that gets bigger with rle.
106 * Revision 1.4 1994/11/09 16:35:17 john
107 * First version with working RLE bitmaps.
109 * Revision 1.3 1994/10/26 12:54:47 john
110 * Fixed bug with decode that used rep movsd instead of
113 * Revision 1.2 1994/10/06 17:05:25 john
114 * First version of rle stuff.
116 * Revision 1.1 1994/10/06 16:53:34 john
128 static char rcsid[] = "$Id: rle.c,v 1.17 2004-01-08 20:31:35 schaffner Exp $";
145 #include "byteswap.h"
147 #define RLE_CODE 0xE0
148 #define NOT_RLE_CODE 31
150 #define IS_RLE_CODE(x) (((x) & RLE_CODE) == RLE_CODE)
152 #if !defined(NO_ASM) && defined(__WATCOMC__)
153 #define RLE_DECODE_ASM
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] = \
192 #elif !defined(NO_ASM) && defined(__GNUC__)
193 #define RLE_DECODE_ASM
195 static inline int gr_rle_decode_asm( ubyte * src, ubyte * dest ) {
198 __asm__ __volatile__ (
200 " xorl %%ecx, %%ecx;"
203 " movb %%al,(%%edi);"
206 " movb (%%esi), %%al;"
215 " movb (%%esi), %%al;"
221 " movb %%al, (%%edi);"
225 : "=D" (__ret), "=S" (dummy) : "1" (src), "D" (dest) : "%eax", "%ecx");
229 #elif !defined(NO_ASM) && defined(_MSC_VER)
230 #define RLE_DECODE_ASM
232 __inline int gr_rle_decode_asm( ubyte * src, ubyte * dest )
273 #ifdef RLE_DECODE_ASM
276 void gr_rle_decode( ubyte * src, ubyte * dest, int dest_len )
280 dest_end = (ubyte *)gr_rle_decode_asm( src, dest );
282 Assert(dest_end-src < dest_len);
285 void gr_rle_decode( ubyte * src, ubyte * dest )
287 gr_rle_decode_asm( src, dest );
291 #else // NO_ASM or unknown compiler
293 void gr_rle_decode( ubyte * src, ubyte * dest )
296 ubyte data, count = 0;
300 if ( ! IS_RLE_CODE(data) ) {
303 count = data & NOT_RLE_CODE;
307 for (i = 0; i < count; i++)
315 void rle_stosb(char *dest, int len, int color);
317 #if !defined(NO_ASM) && defined(__WATCOMC__)
319 #pragma aux rle_stosb = "cld rep stosb" parm [edi] [ecx] [eax] modify exact [edi ecx];
321 #elif !defined(NO_ASM) && defined(__GNUC__)
323 inline void rle_stosb(char *dest, int len, int color) {
325 __asm__ __volatile__ (
327 : "=D" (dummy[0]), "=c" (dummy[1])
328 : "0" (dest), "1" (len), "a" (color) );
331 #elif !defined(NO_ASM) && defined(_MSC_VER)
333 __inline void rle_stosb(char *dest, int len, int color)
344 #else // NO_ASM or unknown compiler
346 void rle_stosb(char *dest, int len, int color)
349 for (i=0; i<len; i++ )
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 )
363 if ( x2 < x1 ) return;
368 if ( color == RLE_CODE ) return;
369 if ( IS_RLE_CODE(color) ) {
370 count = color & (~RLE_CODE);
380 // we know have '*count' pixels of 'color'.
382 if ( x1+count > x2 ) {
384 if ( color != TRANSPARENCY_COLOR ) rle_stosb( dest, count, color );
388 if ( color != TRANSPARENCY_COLOR ) rle_stosb( dest, count, color );
394 if ( color == RLE_CODE ) return;
395 if ( IS_RLE_CODE(color) ) {
396 count = color & (~RLE_CODE);
402 // we know have '*count' pixels of 'color'.
403 if ( i+count <= x2 ) {
404 if ( color != TRANSPARENCY_COLOR )rle_stosb( dest, count, color );
409 if ( color != TRANSPARENCY_COLOR )rle_stosb( dest, count, color );
417 void gr_rle_expand_scanline( ubyte *dest, ubyte *src, int x1, int x2 )
423 if ( x2 < x1 ) return;
428 if ( color == RLE_CODE ) return;
429 if ( IS_RLE_CODE(color) ) {
430 count = color & (~RLE_CODE);
440 // we know have '*count' pixels of 'color'.
442 if ( x1+count > x2 ) {
444 rle_stosb( dest, count, color );
448 rle_stosb( dest, count, color );
454 if ( color == RLE_CODE ) return;
455 if ( IS_RLE_CODE(color) ) {
456 count = color & (~RLE_CODE);
462 // we know have '*count' pixels of 'color'.
463 if ( i+count <= x2 ) {
464 rle_stosb( dest, count, color );
469 rle_stosb( dest, count, color );
477 int gr_rle_encode( int org_size, ubyte *src, ubyte *dest )
488 for (i=1; i<org_size; i++ ) {
492 if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
494 Assert( oc != RLE_CODE );
505 if ( count == NOT_RLE_CODE ) {
513 if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
515 Assert( oc != RLE_CODE );
524 return dest-dest_start;
528 int gr_rle_getsize( int org_size, ubyte *src )
538 for (i=1; i<org_size; i++ ) {
542 if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
553 if ( count == NOT_RLE_CODE ) {
560 if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
572 int gr_bitmap_rle_compress( grs_bitmap * bmp )
579 // first must check to see if this is large bitmap.
581 for (y=0; y<bmp->bm_h; y++ ) {
582 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
589 rle_data=d_malloc( MAX_BMP_SIZE(bmp->bm_w, bmp->bm_h) );
590 if (rle_data==NULL) return 0;
592 doffset = 4 + bmp->bm_h;
594 doffset = 4 + (2 * bmp->bm_h); // each row of rle'd bitmap has short instead of byte offset now
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) ) ) {
602 d = gr_rle_encode( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y], &rle_data[doffset] );
606 *((short *)&(rle_data[(y*2)+4])) = (short)d;
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 );
614 bmp->bm_flags |= BM_FLAG_RLE;
616 bmp->bm_flags |= BM_FLAG_RLE_BIG;
620 #define MAX_CACHE_BITMAPS 32
622 typedef struct rle_cache_element {
623 grs_bitmap * rle_bitmap;
625 grs_bitmap * expanded_bitmap;
629 int rle_cache_initialized = 0;
632 rle_cache_element rle_cache[MAX_CACHE_BITMAPS];
637 void rle_cache_close(void)
639 if (rle_cache_initialized) {
641 rle_cache_initialized = 0;
642 for (i=0; i<MAX_CACHE_BITMAPS; i++ ) {
643 gr_free_bitmap(rle_cache[i].expanded_bitmap);
648 void rle_cache_init()
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 );
657 rle_cache_initialized = 1;
658 atexit( rle_cache_close );
661 void rle_cache_flush()
664 for (i=0; i<MAX_CACHE_BITMAPS; i++ ) {
665 rle_cache[i].rle_bitmap = NULL;
666 rle_cache[i].last_used = 0;
670 void rle_expand_texture_sub( grs_bitmap * bmp, grs_bitmap * rle_temp_bitmap_1 )
672 unsigned char * dbits;
673 unsigned char * sbits;
675 #ifdef RLE_DECODE_ASM
676 unsigned char * dbits1;
680 Assert (bmp->iMagic == BM_MAGIC_NUMBER);
683 sbits = &bmp->bm_data[4 + bmp->bm_h];
684 dbits = rle_temp_bitmap_1->bm_data;
686 rle_temp_bitmap_1->bm_flags = bmp->bm_flags & (~BM_FLAG_RLE);
688 for (i=0; i < bmp->bm_h; i++ ) {
689 #ifdef RLE_DECODE_ASM
690 dbits1=(unsigned char *)gr_rle_decode_asm( sbits, dbits );
692 gr_rle_decode( sbits, dbits );
694 sbits += (int)bmp->bm_data[4+i];
696 #ifdef RLE_DECODE_ASM
697 Assert( dbits == dbits1 ); // Get John, bogus rle data!
701 gr_set_bitmap_data (rle_temp_bitmap_1, rle_temp_bitmap_1->bm_data);
705 #if defined(POLY_ACC)
706 grs_bitmap *rle_get_id_sub(grs_bitmap *bmp)
710 for (i=0;i<MAX_CACHE_BITMAPS;i++) {
711 if (rle_cache[i].expanded_bitmap == bmp) {
712 return rle_cache[i].rle_bitmap;
720 grs_bitmap * rle_expand_texture( grs_bitmap * bmp )
723 int lowest_count, lc;
724 int least_recently_used;
726 if (!rle_cache_initialized) rle_cache_init();
728 Assert( !(bmp->bm_flags & BM_FLAG_PAGED_OUT) );
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;
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 ));
742 lowest_count = rle_cache[rle_next].last_used;
743 least_recently_used = rle_next;
745 if ( rle_next >= MAX_CACHE_BITMAPS )
748 for (i=0; i<MAX_CACHE_BITMAPS; i++ ) {
749 if (rle_cache[i].rle_bitmap == bmp) {
751 rle_cache[i].last_used = rle_counter;
752 return rle_cache[i].expanded_bitmap;
754 if ( rle_cache[i].last_used < lowest_count ) {
755 lowest_count = rle_cache[i].last_used;
756 least_recently_used = i;
760 Assert(bmp->bm_w<=64 && bmp->bm_h<=64); //dest buffer is 64x64
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;
769 void gr_rle_expand_scanline_generic( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2 )
775 if ( x2 < x1 ) return;
780 if ( color == RLE_CODE ) return;
781 if ( IS_RLE_CODE(color) ) {
782 count = color & NOT_RLE_CODE;
792 // we know have '*count' pixels of 'color'.
794 if ( x1+count > x2 ) {
796 for ( j=0; j<count; j++ )
797 gr_bm_pixel( dest, dx++, dy, color );
801 for ( j=0; j<count; j++ )
802 gr_bm_pixel( dest, dx++, dy, color );
807 if ( color == RLE_CODE ) return;
808 if ( IS_RLE_CODE(color) ) {
809 count = color & NOT_RLE_CODE;
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 );
822 for ( j=0; j<count; j++ )
823 gr_bm_pixel( dest, dx++, dy, color );
829 void gr_rle_expand_scanline_generic_masked( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2 )
835 if ( x2 < x1 ) return;
840 if ( color == RLE_CODE ) return;
841 if ( IS_RLE_CODE(color) ) {
842 count = color & NOT_RLE_CODE;
852 // we know have '*count' pixels of 'color'.
854 if ( x1+count > x2 ) {
856 if (color != TRANSPARENCY_COLOR) {
857 for ( j=0; j<count; j++ )
858 gr_bm_pixel( dest, dx++, dy, color );
863 if ( color != TRANSPARENCY_COLOR ) {
864 for ( j=0; j<count; j++ )
865 gr_bm_pixel( dest, dx++, dy, color );
872 if ( color == RLE_CODE ) return;
873 if ( IS_RLE_CODE(color) ) {
874 count = color & NOT_RLE_CODE;
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 );
890 if ( color != TRANSPARENCY_COLOR ) {
891 for ( j=0; j<count; j++ )
892 gr_bm_pixel( dest, dx++, dy, color );
902 void gr_rle_expand_scanline_svga_masked( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2 )
907 ubyte * vram = (ubyte *)0xA0000;
908 int VideoLocation,page,offset;
910 if ( x2 < x1 ) return;
912 VideoLocation = (unsigned int)dest->bm_data + (dest->bm_rowsize * dy) + dx;
913 page = VideoLocation >> 16;
914 offset = VideoLocation & 0xFFFF;
916 gr_vesa_setpage( page );
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 );
927 if ( color == RLE_CODE ) return;
928 if ( IS_RLE_CODE(color) ) {
929 count = color & NOT_RLE_CODE;
939 // we know have '*count' pixels of 'color'.
941 if ( x1+count > x2 ) {
943 if (color != TRANSPARENCY_COLOR) {
944 for ( j=0; j<count; j++ ) {
945 vram[offset++] = color;
946 if ( offset >= 65536 ) {
949 gr_vesa_setpage(page);
956 if ( color != TRANSPARENCY_COLOR ) {
957 for ( j=0; j<count; j++ ) {
958 vram[offset++] = color;
959 if ( offset >= 65536 ) {
962 gr_vesa_setpage(page);
967 if ( offset >= 65536 ) {
970 gr_vesa_setpage(page);
977 if ( color == RLE_CODE ) return;
978 if ( IS_RLE_CODE(color) ) {
979 count = color & NOT_RLE_CODE;
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 ) {
993 gr_vesa_setpage(page);
998 if ( offset >= 65536 ) {
1001 gr_vesa_setpage(page);
1007 if ( color != TRANSPARENCY_COLOR ) {
1008 for ( j=0; j<count; j++ ) {
1009 vram[offset++] = color;
1010 if ( offset >= 65536 ) {
1013 gr_vesa_setpage(page);
1018 if ( offset >= 65536 ) {
1021 gr_vesa_setpage(page);
1032 * swaps entries 0 and 255 in an RLE bitmap without uncompressing it
1034 void rle_swap_0_255(grs_bitmap *bmp)
1036 int i, j, len, rle_big;
1037 unsigned char *ptr, *ptr2, *temp, *start;
1038 unsigned short line_size;
1040 rle_big = bmp->bm_flags & BM_FLAG_RLE_BIG;
1042 temp = d_malloc( MAX_BMP_SIZE(bmp->bm_w, bmp->bm_h) );
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;
1048 ptr = bmp->bm_data + 4 + bmp->bm_h;
1049 ptr2 = temp + 4 + bmp->bm_h;
1051 for (i = 0; i < bmp->bm_h; i++) {
1054 line_size = INTEL_SHORT(*((unsigned short *)&bmp->bm_data[4 + 2 * i]));
1056 line_size = bmp->bm_data[4 + i];
1057 for (j = 0; j < line_size; j++) {
1058 if ( ! IS_RLE_CODE(ptr[j]) ) {
1060 *ptr2++ = RLE_CODE | 1;
1066 if ((ptr[j] & NOT_RLE_CODE) == 0)
1071 else if (ptr[j] == 255)
1077 if (rle_big) // set line size
1078 *((unsigned short *)&temp[4 + 2 * i]) = INTEL_SHORT(ptr2 - start);
1080 temp[4 + i] = ptr2 - start;
1081 ptr += line_size; // go to next line
1084 *((int *)temp) = len; // set total size
1085 memcpy(bmp->bm_data, temp, len);
1090 * remaps all entries using colormap in an RLE bitmap without uncompressing it
1092 void rle_remap(grs_bitmap *bmp, ubyte *colormap)
1094 int i, j, len, rle_big;
1095 unsigned char *ptr, *ptr2, *temp, *start;
1096 unsigned short line_size;
1098 rle_big = bmp->bm_flags & BM_FLAG_RLE_BIG;
1100 temp = d_malloc( MAX_BMP_SIZE(bmp->bm_w, bmp->bm_h) + 30000 );
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;
1106 ptr = bmp->bm_data + 4 + bmp->bm_h;
1107 ptr2 = temp + 4 + bmp->bm_h;
1109 for (i = 0; i < bmp->bm_h; i++) {
1112 line_size = INTEL_SHORT(*((unsigned short *)&bmp->bm_data[4 + 2 * i]));
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
1121 *ptr2++ = ptr[j]; // just copy current rle code
1122 if ((ptr[j] & NOT_RLE_CODE) == 0)
1125 *ptr2++ = colormap[ptr[j]]; // translate
1128 if (rle_big) // set line size
1129 *((unsigned short *)&temp[4 + 2 * i]) = INTEL_SHORT(ptr2 - start);
1131 temp[4 + i] = ptr2 - start;
1132 ptr += line_size; // go to next line
1135 *((int *)temp) = len; // set total size
1136 memcpy(bmp->bm_data, temp, len);