1 /* $Id: rle.c,v 1.19 2004-08-28 23:17:45 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
28 static char rcsid[] = "$Id: rle.c,v 1.19 2004-08-28 23:17:45 schaffner Exp $";
48 #define NOT_RLE_CODE 31
50 #define IS_RLE_CODE(x) (((x) & RLE_CODE) == RLE_CODE)
52 #if !defined(NO_ASM) && defined(__WATCOMC__)
53 #define RLE_DECODE_ASM
55 ubyte *gr_rle_decode_asm( ubyte * src, ubyte * dest );
56 #pragma aux gr_rle_decode_asm parm [esi] [edi] value [edi] modify exact [eax ebx ecx edx esi edi] = \
92 #elif !defined(NO_ASM) && defined(__GNUC__)
93 #define RLE_DECODE_ASM
95 static inline int gr_rle_decode_asm( ubyte * src, ubyte * dest ) {
98 __asm__ __volatile__ (
100 " xorl %%ecx, %%ecx;"
103 " movb %%al,(%%edi);"
106 " movb (%%esi), %%al;"
115 " movb (%%esi), %%al;"
121 " movb %%al, (%%edi);"
125 : "=D" (__ret), "=S" (dummy) : "1" (src), "D" (dest) : "%eax", "%ecx");
129 #elif !defined(NO_ASM) && defined(_MSC_VER)
130 #define RLE_DECODE_ASM
132 __inline int gr_rle_decode_asm( ubyte * src, ubyte * dest )
173 #ifdef RLE_DECODE_ASM
176 void gr_rle_decode( ubyte * src, ubyte * dest, int dest_len )
180 dest_end = (ubyte *)gr_rle_decode_asm( src, dest );
182 Assert(dest_end-src < dest_len);
185 void gr_rle_decode( ubyte * src, ubyte * dest )
187 gr_rle_decode_asm( src, dest );
191 #else // NO_ASM or unknown compiler
193 void gr_rle_decode( ubyte * src, ubyte * dest )
196 ubyte data, count = 0;
200 if ( ! IS_RLE_CODE(data) ) {
203 count = data & NOT_RLE_CODE;
207 for (i = 0; i < count; i++)
215 void rle_stosb (unsigned char *dest, int len, int color);
217 #if !defined(NO_ASM) && defined(__WATCOMC__)
219 #pragma aux rle_stosb = "cld rep stosb" parm [edi] [ecx] [eax] modify exact [edi ecx];
221 #elif !defined(NO_ASM) && defined(__GNUC__)
223 inline void rle_stosb (unsigned char *dest, int len, int color) {
225 __asm__ __volatile__ (
227 : "=D" (dummy[0]), "=c" (dummy[1])
228 : "0" (dest), "1" (len), "a" (color) );
231 #elif !defined(NO_ASM) && defined(_MSC_VER)
233 __inline void rle_stosb (unsigned char *dest, int len, int color)
244 #else // NO_ASM or unknown compiler
246 void rle_stosb (unsigned char *dest, int len, int color)
249 for (i=0; i<len; i++ )
255 // Given pointer to start of one scanline of rle data, uncompress it to
256 // dest, from source pixels x1 to x2.
257 void gr_rle_expand_scanline_masked( ubyte *dest, ubyte *src, int x1, int x2 )
263 if ( x2 < x1 ) return;
268 if ( color == RLE_CODE ) return;
269 if ( IS_RLE_CODE(color) ) {
270 count = color & (~RLE_CODE);
280 // we know have '*count' pixels of 'color'.
282 if ( x1+count > x2 ) {
284 if ( color != TRANSPARENCY_COLOR ) rle_stosb( dest, count, color );
288 if ( color != TRANSPARENCY_COLOR ) rle_stosb( dest, count, color );
294 if ( color == RLE_CODE ) return;
295 if ( IS_RLE_CODE(color) ) {
296 count = color & (~RLE_CODE);
302 // we know have '*count' pixels of 'color'.
303 if ( i+count <= x2 ) {
304 if ( color != TRANSPARENCY_COLOR )rle_stosb( dest, count, color );
309 if ( color != TRANSPARENCY_COLOR )rle_stosb( dest, count, color );
317 void gr_rle_expand_scanline( ubyte *dest, ubyte *src, int x1, int x2 )
323 if ( x2 < x1 ) return;
328 if ( color == RLE_CODE ) return;
329 if ( IS_RLE_CODE(color) ) {
330 count = color & (~RLE_CODE);
340 // we know have '*count' pixels of 'color'.
342 if ( x1+count > x2 ) {
344 rle_stosb( dest, count, color );
348 rle_stosb( dest, count, color );
354 if ( color == RLE_CODE ) return;
355 if ( IS_RLE_CODE(color) ) {
356 count = color & (~RLE_CODE);
362 // we know have '*count' pixels of 'color'.
363 if ( i+count <= x2 ) {
364 rle_stosb( dest, count, color );
369 rle_stosb( dest, count, color );
377 int gr_rle_encode( int org_size, ubyte *src, ubyte *dest )
388 for (i=1; i<org_size; i++ ) {
392 if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
394 Assert( oc != RLE_CODE );
405 if ( count == NOT_RLE_CODE ) {
413 if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
415 Assert( oc != RLE_CODE );
424 return dest-dest_start;
428 int gr_rle_getsize( int org_size, ubyte *src )
438 for (i=1; i<org_size; i++ ) {
442 if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
453 if ( count == NOT_RLE_CODE ) {
460 if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
472 int gr_bitmap_rle_compress( grs_bitmap * bmp )
479 // first must check to see if this is large bitmap.
481 for (y=0; y<bmp->bm_h; y++ ) {
482 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
489 rle_data=d_malloc( MAX_BMP_SIZE(bmp->bm_w, bmp->bm_h) );
490 if (rle_data==NULL) return 0;
492 doffset = 4 + bmp->bm_h;
494 doffset = 4 + (2 * bmp->bm_h); // each row of rle'd bitmap has short instead of byte offset now
496 for (y=0; y<bmp->bm_h; y++ ) {
497 d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
498 if ( ((doffset+d1) > bmp->bm_w*bmp->bm_h) || (d1 > (large_rle?32767:255) ) ) {
502 d = gr_rle_encode( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y], &rle_data[doffset] );
506 *((short *)&(rle_data[(y*2)+4])) = (short)d;
510 //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 );
511 memcpy( rle_data, &doffset, 4 );
512 memcpy( bmp->bm_data, rle_data, doffset );
514 bmp->bm_flags |= BM_FLAG_RLE;
516 bmp->bm_flags |= BM_FLAG_RLE_BIG;
520 #define MAX_CACHE_BITMAPS 32
522 typedef struct rle_cache_element {
523 grs_bitmap * rle_bitmap;
525 grs_bitmap * expanded_bitmap;
529 int rle_cache_initialized = 0;
532 rle_cache_element rle_cache[MAX_CACHE_BITMAPS];
537 void rle_cache_close(void)
539 if (rle_cache_initialized) {
541 rle_cache_initialized = 0;
542 for (i=0; i<MAX_CACHE_BITMAPS; i++ ) {
543 gr_free_bitmap(rle_cache[i].expanded_bitmap);
548 void rle_cache_init()
551 for (i=0; i<MAX_CACHE_BITMAPS; i++ ) {
552 rle_cache[i].rle_bitmap = NULL;
553 rle_cache[i].expanded_bitmap = gr_create_bitmap( 64, 64 );
554 rle_cache[i].last_used = 0;
555 Assert( rle_cache[i].expanded_bitmap != NULL );
557 rle_cache_initialized = 1;
558 atexit( rle_cache_close );
561 void rle_cache_flush()
564 for (i=0; i<MAX_CACHE_BITMAPS; i++ ) {
565 rle_cache[i].rle_bitmap = NULL;
566 rle_cache[i].last_used = 0;
570 void rle_expand_texture_sub( grs_bitmap * bmp, grs_bitmap * rle_temp_bitmap_1 )
572 unsigned char * dbits;
573 unsigned char * sbits;
575 #ifdef RLE_DECODE_ASM
576 unsigned char * dbits1;
580 Assert (bmp->iMagic == BM_MAGIC_NUMBER);
583 sbits = &bmp->bm_data[4 + bmp->bm_h];
584 dbits = rle_temp_bitmap_1->bm_data;
586 rle_temp_bitmap_1->bm_flags = bmp->bm_flags & (~BM_FLAG_RLE);
588 for (i=0; i < bmp->bm_h; i++ ) {
589 #ifdef RLE_DECODE_ASM
590 dbits1=(unsigned char *)gr_rle_decode_asm( sbits, dbits );
592 gr_rle_decode( sbits, dbits );
594 sbits += (int)bmp->bm_data[4+i];
596 #ifdef RLE_DECODE_ASM
597 Assert( dbits == dbits1 ); // Get John, bogus rle data!
601 gr_set_bitmap_data (rle_temp_bitmap_1, rle_temp_bitmap_1->bm_data);
605 #if defined(POLY_ACC)
606 grs_bitmap *rle_get_id_sub(grs_bitmap *bmp)
610 for (i=0;i<MAX_CACHE_BITMAPS;i++) {
611 if (rle_cache[i].expanded_bitmap == bmp) {
612 return rle_cache[i].rle_bitmap;
620 grs_bitmap * rle_expand_texture( grs_bitmap * bmp )
623 int lowest_count, lc;
624 int least_recently_used;
626 if (!rle_cache_initialized) rle_cache_init();
628 Assert( !(bmp->bm_flags & BM_FLAG_PAGED_OUT) );
632 if ( rle_counter < lc ) {
633 for (i=0; i<MAX_CACHE_BITMAPS; i++ ) {
634 rle_cache[i].rle_bitmap = NULL;
635 rle_cache[i].last_used = 0;
639 // if (((rle_counter % 100)==1) && (rle_hits+rle_misses > 0))
640 // mprintf(( 0, "RLE-CACHE %d%%, H:%d, M:%d\n", (rle_misses*100)/(rle_hits+rle_misses), rle_hits, rle_misses ));
642 lowest_count = rle_cache[rle_next].last_used;
643 least_recently_used = rle_next;
645 if ( rle_next >= MAX_CACHE_BITMAPS )
648 for (i=0; i<MAX_CACHE_BITMAPS; i++ ) {
649 if (rle_cache[i].rle_bitmap == bmp) {
651 rle_cache[i].last_used = rle_counter;
652 return rle_cache[i].expanded_bitmap;
654 if ( rle_cache[i].last_used < lowest_count ) {
655 lowest_count = rle_cache[i].last_used;
656 least_recently_used = i;
660 Assert(bmp->bm_w<=64 && bmp->bm_h<=64); //dest buffer is 64x64
662 rle_expand_texture_sub( bmp, rle_cache[least_recently_used].expanded_bitmap );
663 rle_cache[least_recently_used].rle_bitmap = bmp;
664 rle_cache[least_recently_used].last_used = rle_counter;
665 return rle_cache[least_recently_used].expanded_bitmap;
669 void gr_rle_expand_scanline_generic( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2 )
675 if ( x2 < x1 ) return;
680 if ( color == RLE_CODE ) return;
681 if ( IS_RLE_CODE(color) ) {
682 count = color & NOT_RLE_CODE;
692 // we know have '*count' pixels of 'color'.
694 if ( x1+count > x2 ) {
696 for ( j=0; j<count; j++ )
697 gr_bm_pixel( dest, dx++, dy, color );
701 for ( j=0; j<count; j++ )
702 gr_bm_pixel( dest, dx++, dy, color );
707 if ( color == RLE_CODE ) return;
708 if ( IS_RLE_CODE(color) ) {
709 count = color & NOT_RLE_CODE;
715 // we know have '*count' pixels of 'color'.
716 if ( i+count <= x2 ) {
717 for ( j=0; j<count; j++ )
718 gr_bm_pixel( dest, dx++, dy, color );
722 for ( j=0; j<count; j++ )
723 gr_bm_pixel( dest, dx++, dy, color );
729 void gr_rle_expand_scanline_generic_masked( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2 )
735 if ( x2 < x1 ) return;
740 if ( color == RLE_CODE ) return;
741 if ( IS_RLE_CODE(color) ) {
742 count = color & NOT_RLE_CODE;
752 // we know have '*count' pixels of 'color'.
754 if ( x1+count > x2 ) {
756 if (color != TRANSPARENCY_COLOR) {
757 for ( j=0; j<count; j++ )
758 gr_bm_pixel( dest, dx++, dy, color );
763 if ( color != TRANSPARENCY_COLOR ) {
764 for ( j=0; j<count; j++ )
765 gr_bm_pixel( dest, dx++, dy, color );
772 if ( color == RLE_CODE ) return;
773 if ( IS_RLE_CODE(color) ) {
774 count = color & NOT_RLE_CODE;
780 // we know have '*count' pixels of 'color'.
781 if ( i+count <= x2 ) {
782 if ( color != TRANSPARENCY_COLOR ) {
783 for ( j=0; j<count; j++ )
784 gr_bm_pixel( dest, dx++, dy, color );
790 if ( color != TRANSPARENCY_COLOR ) {
791 for ( j=0; j<count; j++ )
792 gr_bm_pixel( dest, dx++, dy, color );
802 void gr_rle_expand_scanline_svga_masked( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2 )
807 ubyte * vram = (ubyte *)0xA0000;
808 int VideoLocation,page,offset;
810 if ( x2 < x1 ) return;
812 VideoLocation = (unsigned int)dest->bm_data + (dest->bm_rowsize * dy) + dx;
813 page = VideoLocation >> 16;
814 offset = VideoLocation & 0xFFFF;
816 gr_vesa_setpage( page );
818 if ( (offset + (x2-x1+1)) < 65536 ) {
819 // We don't cross a svga page, so blit it fast!
820 gr_rle_expand_scanline_masked( &vram[offset], src, x1, x2 );
827 if ( color == RLE_CODE ) return;
828 if ( IS_RLE_CODE(color) ) {
829 count = color & NOT_RLE_CODE;
839 // we know have '*count' pixels of 'color'.
841 if ( x1+count > x2 ) {
843 if (color != TRANSPARENCY_COLOR) {
844 for ( j=0; j<count; j++ ) {
845 vram[offset++] = color;
846 if ( offset >= 65536 ) {
849 gr_vesa_setpage(page);
856 if ( color != TRANSPARENCY_COLOR ) {
857 for ( j=0; j<count; j++ ) {
858 vram[offset++] = color;
859 if ( offset >= 65536 ) {
862 gr_vesa_setpage(page);
867 if ( offset >= 65536 ) {
870 gr_vesa_setpage(page);
877 if ( color == RLE_CODE ) return;
878 if ( IS_RLE_CODE(color) ) {
879 count = color & NOT_RLE_CODE;
885 // we know have '*count' pixels of 'color'.
886 if ( i+count <= x2 ) {
887 if ( color != TRANSPARENCY_COLOR ) {
888 for ( j=0; j<count; j++ ) {
889 vram[offset++] = color;
890 if ( offset >= 65536 ) {
893 gr_vesa_setpage(page);
898 if ( offset >= 65536 ) {
901 gr_vesa_setpage(page);
907 if ( color != TRANSPARENCY_COLOR ) {
908 for ( j=0; j<count; j++ ) {
909 vram[offset++] = color;
910 if ( offset >= 65536 ) {
913 gr_vesa_setpage(page);
918 if ( offset >= 65536 ) {
921 gr_vesa_setpage(page);
932 * swaps entries 0 and 255 in an RLE bitmap without uncompressing it
934 void rle_swap_0_255(grs_bitmap *bmp)
936 int i, j, len, rle_big;
937 unsigned char *ptr, *ptr2, *temp, *start;
938 unsigned short line_size;
940 rle_big = bmp->bm_flags & BM_FLAG_RLE_BIG;
942 temp = d_malloc( MAX_BMP_SIZE(bmp->bm_w, bmp->bm_h) );
944 if (rle_big) { // set ptrs to first lines
945 ptr = bmp->bm_data + 4 + 2 * bmp->bm_h;
946 ptr2 = temp + 4 + 2 * bmp->bm_h;
948 ptr = bmp->bm_data + 4 + bmp->bm_h;
949 ptr2 = temp + 4 + bmp->bm_h;
951 for (i = 0; i < bmp->bm_h; i++) {
954 line_size = INTEL_SHORT(*((unsigned short *)&bmp->bm_data[4 + 2 * i]));
956 line_size = bmp->bm_data[4 + i];
957 for (j = 0; j < line_size; j++) {
958 if ( ! IS_RLE_CODE(ptr[j]) ) {
960 *ptr2++ = RLE_CODE | 1;
966 if ((ptr[j] & NOT_RLE_CODE) == 0)
971 else if (ptr[j] == 255)
977 if (rle_big) // set line size
978 *((unsigned short *)&temp[4 + 2 * i]) = INTEL_SHORT(ptr2 - start);
980 temp[4 + i] = ptr2 - start;
981 ptr += line_size; // go to next line
984 *((int *)temp) = len; // set total size
985 memcpy(bmp->bm_data, temp, len);
990 * remaps all entries using colormap in an RLE bitmap without uncompressing it
992 void rle_remap(grs_bitmap *bmp, ubyte *colormap)
994 int i, j, len, rle_big;
995 unsigned char *ptr, *ptr2, *temp, *start;
996 unsigned short line_size;
998 rle_big = bmp->bm_flags & BM_FLAG_RLE_BIG;
1000 temp = d_malloc( MAX_BMP_SIZE(bmp->bm_w, bmp->bm_h) + 30000 );
1002 if (rle_big) { // set ptrs to first lines
1003 ptr = bmp->bm_data + 4 + 2 * bmp->bm_h;
1004 ptr2 = temp + 4 + 2 * bmp->bm_h;
1006 ptr = bmp->bm_data + 4 + bmp->bm_h;
1007 ptr2 = temp + 4 + bmp->bm_h;
1009 for (i = 0; i < bmp->bm_h; i++) {
1012 line_size = INTEL_SHORT(*((unsigned short *)&bmp->bm_data[4 + 2 * i]));
1014 line_size = bmp->bm_data[4 + i];
1015 for (j = 0; j < line_size; j++) {
1016 if ( ! IS_RLE_CODE(ptr[j])) {
1017 if (IS_RLE_CODE(colormap[ptr[j]]))
1018 *ptr2++ = RLE_CODE | 1; // add "escape sequence"
1019 *ptr2++ = colormap[ptr[j]]; // translate
1021 *ptr2++ = ptr[j]; // just copy current rle code
1022 if ((ptr[j] & NOT_RLE_CODE) == 0)
1025 *ptr2++ = colormap[ptr[j]]; // translate
1028 if (rle_big) // set line size
1029 *((unsigned short *)&temp[4 + 2 * i]) = INTEL_SHORT(ptr2 - start);
1031 temp[4 + i] = ptr2 - start;
1032 ptr += line_size; // go to next line
1035 *((int *)temp) = len; // set total size
1036 memcpy(bmp->bm_data, temp, len);