home *** CD-ROM | disk | FTP | other *** search
/ Amiga ACS 1998 #6 / amigaacscoverdisc1998-061998.iso / games / descent / source / 2d / rle.c < prev    next >
Text File  |  1998-06-08  |  14KB  |  583 lines
  1. /*
  2. THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
  3. SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
  4. END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
  5. ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
  6. IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
  7. SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
  8. FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
  9. CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  10. AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.  
  11. COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12. */
  13. /*
  14.  * $Source: f:/miner/source/2d/rcs/rle.c $
  15.  * $Revision: 1.19 $
  16.  * $Author: john $
  17.  * $Date: 1995/01/14 19:18:31 $
  18.  * 
  19.  * Routines to do run length encoding/decoding
  20.  * on bitmaps.
  21.  * 
  22.  * $Log: rle.c $
  23.  * Revision 1.19  1995/01/14  19:18:31  john
  24.  * Added assert to check for paged out bitmap.
  25.  * 
  26.  * Revision 1.18  1995/01/14  11:32:07  john
  27.  * Added rle_cache_flush function.
  28.  * 
  29.  * Revision 1.17  1994/12/13  10:58:27  john
  30.  * Fixed bug with 2 consecutive calls to get_expanded_Texture
  31.  * with 2 different bitmaps, returning the same rle texture, 
  32.  * causing doors to disapper.
  33.  * 
  34.  * Revision 1.16  1994/11/30  00:55:03  mike
  35.  * optimization
  36.  * 
  37.  * Revision 1.15  1994/11/24  13:24:44  john
  38.  * Made sure that some rep movs had the cld set first.
  39.  * Took some unused functions out.
  40.  * 
  41.  * Revision 1.14  1994/11/23  16:03:46  john
  42.  * Fixed generic rle'ing to use new bit method.
  43.  * 
  44.  * Revision 1.13  1994/11/23  15:45:51  john
  45.  * Changed to a 3 bit rle scheme.
  46.  * 
  47.  * Revision 1.12  1994/11/18  22:50:24  john
  48.  * Changed shorts to ints in parameters.
  49.  * 
  50.  * Revision 1.11  1994/11/14  17:06:13  john
  51.  * Took out Key_f12.
  52.  * 
  53.  * Revision 1.10  1994/11/14  15:54:09  john
  54.  * Put code in for maybe checking bogus rle data.
  55.  * 
  56.  * Revision 1.9  1994/11/14  15:51:58  john
  57.  * Added rle_disable_caching variable to prove the stability of my rle caching code
  58.  * to any non-believers.
  59.  * 
  60.  * Revision 1.8  1994/11/10  10:31:20  john
  61.  * Reduce cache buffers to 16.
  62.  * 
  63.  * Revision 1.7  1994/11/09  19:53:43  john
  64.  * Added texture rle caching.
  65.  * 
  66.  * Revision 1.6  1994/11/09  17:41:44  john
  67.  * Made a slow version of rle bitblt to svga, modex.
  68.  * 
  69.  * Revision 1.5  1994/11/09  17:07:50  john
  70.  * Fixed bug with bitmap that gets bigger with rle.
  71.  * 
  72.  * Revision 1.4  1994/11/09  16:35:17  john
  73.  * First version with working RLE bitmaps.
  74.  * 
  75.  * Revision 1.3  1994/10/26  12:54:47  john
  76.  * Fixed bug with decode that used rep movsd instead of 
  77.  * rep stosd.
  78.  * 
  79.  * Revision 1.2  1994/10/06  17:05:25  john
  80.  * First version of rle stuff.
  81.  * 
  82.  * Revision 1.1  1994/10/06  16:53:34  john
  83.  * Initial revision
  84.  * 
  85.  * 
  86.  */
  87.  
  88.  
  89. #pragma off (unreferenced)
  90. static char rcsid[] = "$Id: rle.c 1.19 1995/01/14 19:18:31 john Exp $";
  91. #pragma on (unreferenced)
  92.  
  93. #include <stdlib.h>
  94. #include <malloc.h>
  95. #include <stdio.h>
  96. #include <string.h>
  97.  
  98. #include "mem.h"
  99. #include "mono.h"
  100.  
  101.  
  102. #include "gr.h"
  103. #include "grdef.h"
  104. #include "dpmi.h"
  105. #include "error.h"
  106. #include "key.h"
  107.  
  108. //#define RLE_CODE         0xC0
  109. //#define NOT_RLE_CODE    63
  110.  
  111. #define RLE_CODE             0xE0
  112. #define NOT_RLE_CODE        31
  113.  
  114. int gr_rle_decode_asm( ubyte * src, ubyte * dest );
  115. #pragma aux gr_rle_decode_asm parm [esi] [edi] value [edi] modify exact [eax ebx ecx edx esi edi] = \
  116. "  cld                    "\
  117. "    xor    ecx, ecx        "\        
  118. "    cld                    "\        
  119. "    jmp    NextByte        "\                                                                                        
  120. "                            "\                                                                                
  121. "Unique:                    "\                                                                                
  122. "    mov    [edi],al        "\
  123. "    inc    edi            "\        
  124. "                            "\                                                                                
  125. "NextByte:                "\                                                                            
  126. "    mov    al,[esi]        "\        
  127. "    inc    esi            "\        
  128. "                            "\                                                                        
  129. "    mov    ah, al        "\
  130. "    and    ah, 0xE0    "\
  131. "  cmp    ah, 0xE0        "\
  132. "    jne   Unique        "\        
  133. "                            "\                                                                        
  134. "    mov    cl, al        "\        
  135. "    and    cl, 31          "\        
  136. "    je        done            "\
  137. "                            "\                                                
  138. "    mov    al,[esi]        "\        
  139. "    inc    esi            "\        
  140. "    mov    ah, al        "\
  141. "    shr    ecx,1            "\        
  142. "    rep    stosw            "\        
  143. "    jnc    NextByte        "\
  144. "    mov    [edi],al        "\
  145. "    inc    edi            "\        
  146. "                            "\
  147. "    jmp    NextByte        "\    
  148. "                            "\                
  149. "done:                    ";
  150.  
  151. void gr_rle_decode( ubyte * src, ubyte * dest )
  152. {
  153.     gr_rle_decode_asm( src, dest );
  154. }
  155.  
  156. void rle_stosb(char *dest, int len, int color);
  157. #pragma aux rle_stosb = "cld rep    stosb" parm [edi] [ecx] [eax] modify exact [edi ecx];
  158.  
  159. // Given pointer to start of one scanline of rle data, uncompress it to
  160. // dest, from source pixels x1 to x2.
  161. void gr_rle_expand_scanline_masked( ubyte *dest, ubyte *src, int x1, int x2  )
  162. {
  163.     int i = 0;
  164.     ubyte count;
  165.     ubyte color;
  166.  
  167.     if ( x2 < x1 ) return;
  168.  
  169.     count = 0;
  170.     while ( i < x1 )    {
  171.         color = *src++;
  172.         if ( color == RLE_CODE ) return;
  173.         if ( (color & RLE_CODE)==RLE_CODE )    {
  174.             count = color & (~RLE_CODE);
  175.             color = *src++;
  176.         } else {
  177.             // unique
  178.             count = 1;
  179.         }
  180.         i += count;
  181.     }
  182.     count = i - x1;
  183.     i = x1;
  184.     // we know have '*count' pixels of 'color'.
  185.     
  186.     if ( x1+count > x2 )    {
  187.         count = x2-x1+1;
  188.         if ( color != 255 )    rle_stosb( dest, count, color );
  189.         return;
  190.     }
  191.  
  192.     if ( color != 255 )    rle_stosb( dest, count, color );
  193.     dest += count;
  194.     i += count;
  195.  
  196.     while( i <= x2 )        {
  197.         color = *src++;
  198.         if ( color == RLE_CODE ) return;
  199.         if ( (color & RLE_CODE) == (RLE_CODE) )    {
  200.             count = color & (~RLE_CODE);
  201.             color = *src++;
  202.         } else {
  203.             // unique
  204.             count = 1;
  205.         }
  206.         // we know have '*count' pixels of 'color'.
  207.         if ( i+count <= x2 )    {
  208.             if ( color != 255 )rle_stosb( dest, count, color );
  209.             i += count;
  210.             dest += count;
  211.         } else {
  212.             count = x2-i+1;
  213.             if ( color != 255 )rle_stosb( dest, count, color );
  214.             i += count;
  215.             dest += count;
  216.         }
  217.  
  218.     }    
  219. }
  220.  
  221. void gr_rle_expand_scanline( ubyte *dest, ubyte *src, int x1, int x2  )
  222. {
  223.     int i = 0;
  224.     ubyte count;
  225.     ubyte color;
  226.  
  227.     if ( x2 < x1 ) return;
  228.  
  229.     count = 0;
  230.     while ( i < x1 )    {
  231.         color = *src++;
  232.         if ( color == RLE_CODE ) return;
  233.         if ( (color & RLE_CODE)==RLE_CODE )    {
  234.             count = color & (~RLE_CODE);
  235.             color = *src++;
  236.         } else {
  237.             // unique
  238.             count = 1;
  239.         }
  240.         i += count;
  241.     }
  242.     count = i - x1;
  243.     i = x1;
  244.     // we know have '*count' pixels of 'color'.
  245.     
  246.     if ( x1+count > x2 )    {
  247.         count = x2-x1+1;
  248.         rle_stosb( dest, count, color );
  249.         return;
  250.     }
  251.  
  252.     rle_stosb( dest, count, color );
  253.     dest += count;
  254.     i += count;
  255.  
  256.     while( i <= x2 )        {
  257.         color = *src++;
  258.         if ( color == RLE_CODE ) return;
  259.         if ( (color & RLE_CODE)==RLE_CODE )    {
  260.             count = color & (~RLE_CODE);
  261.             color = *src++;
  262.         } else {
  263.             // unique
  264.             count = 1;
  265.         }
  266.         // we know have '*count' pixels of 'color'.
  267.         if ( i+count <= x2 )    {
  268.             rle_stosb( dest, count, color );
  269.             i += count;
  270.             dest += count;
  271.         } else {
  272.             count = x2-i+1;
  273.             rle_stosb( dest, count, color );
  274.             i += count;
  275.             dest += count;
  276.         }
  277.     }    
  278. }
  279.  
  280.  
  281. int gr_rle_encode( int org_size, ubyte *src, ubyte *dest )
  282. {
  283.     int i;
  284.     ubyte c, oc;
  285.     ubyte count;
  286.     ubyte *dest_start;
  287.  
  288.     dest_start = dest;
  289.     oc = *src++;
  290.     count = 1;
  291.  
  292.     for (i=1; i<org_size; i++ )    {
  293.         c = *src++;                            
  294.         if ( c!=oc )    {
  295.             if ( count )    {
  296.                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )    {
  297.                     *dest++ = oc;
  298.                     Assert( oc != RLE_CODE );
  299.                 } else {
  300.                     count |= RLE_CODE;
  301.                     *dest++ = count;
  302.                     *dest++ = oc;
  303.                 }
  304.             }
  305.             oc = c;
  306.             count = 0;
  307.         }
  308.         count++;
  309.         if ( count == NOT_RLE_CODE )    {
  310.             count |= RLE_CODE;
  311.             *dest++=count;
  312.             *dest++=oc;
  313.             count = 0;
  314.         }
  315.     }
  316.     if (count)    {
  317.         if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )    {
  318.             *dest++ = oc;
  319.             Assert( oc != RLE_CODE );
  320.         } else {
  321.             count |= RLE_CODE;
  322.             *dest++ = count;
  323.             *dest++ = oc;
  324.         }
  325.     }
  326.     *dest++ = RLE_CODE;
  327.  
  328.     return dest-dest_start;
  329. }
  330.  
  331.  
  332. int gr_rle_getsize( int org_size, ubyte *src )
  333. {
  334.     int i;
  335.     ubyte c, oc;
  336.     ubyte count;
  337.     int dest_size=0;
  338.  
  339.     oc = *src++;
  340.     count = 1;
  341.  
  342.     for (i=1; i<org_size; i++ )    {
  343.         c = *src++;                            
  344.         if ( c!=oc )    {
  345.             if ( count )    {
  346.                 if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )    {
  347.                     dest_size++;
  348.                 } else {
  349.                     dest_size++;
  350.                     dest_size++;
  351.                 }
  352.             }
  353.             oc = c;
  354.             count = 0;
  355.         }
  356.         count++;
  357.         if ( count == NOT_RLE_CODE )    {
  358.             dest_size++;
  359.             dest_size++;
  360.             count = 0;
  361.         }
  362.     }
  363.     if (count)    {
  364.         if ( (count==1) && ((oc & RLE_CODE)!=RLE_CODE) )    {
  365.             dest_size++;
  366.         } else {
  367.             dest_size++;
  368.             dest_size++;
  369.         }
  370.     }
  371.     dest_size++;
  372.  
  373.     return dest_size;
  374. }
  375.  
  376. int gr_bitmap_rle_compress( grs_bitmap * bmp )
  377. {
  378.     int y, d1, d;
  379.     int doffset;
  380.     ubyte *rle_data;
  381.  
  382.     rle_data=malloc( (bmp->bm_w+1)* bmp->bm_h );
  383.     if (rle_data==NULL) return 0;
  384.     doffset = 4 + bmp->bm_h;
  385.     for (y=0; y<bmp->bm_h; y++ )    {
  386.         d1= gr_rle_getsize( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y] );
  387.         if ( ((doffset+d1) > bmp->bm_w*bmp->bm_h) || (d1 > 255 ) )    {
  388.             free(rle_data);
  389.             return 0;
  390.         }
  391.         d = gr_rle_encode( bmp->bm_w, &bmp->bm_data[bmp->bm_w*y], &rle_data[doffset] );
  392.         Assert( d==d1 );
  393.         doffset    += d;
  394.         rle_data[y+4] = d;
  395.     }
  396.     //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 );
  397.     memcpy(     rle_data, &doffset, 4 );
  398.     memcpy(     bmp->bm_data, rle_data, doffset );
  399.     free(rle_data);
  400.     bmp->bm_flags |= BM_FLAG_RLE;
  401.     return 1;
  402. }
  403.  
  404. #define MAX_CACHE_BITMAPS 32
  405.  
  406. typedef struct rle_cache_element {
  407.     grs_bitmap * rle_bitmap;
  408.     ubyte * rle_data;
  409.     grs_bitmap * expanded_bitmap;            
  410.     int last_used;
  411. } rle_cache_element;
  412.  
  413. int rle_cache_initialized = 0;
  414. int rle_counter = 0;
  415. int rle_next = 0;
  416. rle_cache_element rle_cache[MAX_CACHE_BITMAPS];
  417.  
  418. int rle_hits = 0;
  419. int rle_misses = 0;
  420.  
  421. void rle_cache_close()
  422. {
  423.     if (rle_cache_initialized)    {
  424.         int i;
  425.         rle_cache_initialized = 0;
  426.         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
  427.             gr_free_bitmap(rle_cache[i].expanded_bitmap);
  428.         }
  429.     }
  430. }
  431.  
  432. void rle_cache_init()
  433. {
  434.     int i;
  435.     for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
  436.         rle_cache[i].rle_bitmap = NULL;
  437.         rle_cache[i].expanded_bitmap = gr_create_bitmap( 64, 64 );
  438.         rle_cache[i].last_used = 0;
  439.         Assert( rle_cache[i].expanded_bitmap != NULL );
  440.     }    
  441.     rle_cache_initialized = 1;
  442.     atexit( rle_cache_close );
  443. }
  444.  
  445. void rle_cache_flush()
  446. {
  447.     int i;
  448.     for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
  449.         rle_cache[i].rle_bitmap = NULL;
  450.         rle_cache[i].last_used = 0;
  451.     }    
  452. }
  453.  
  454.  
  455.  
  456. grs_bitmap * rle_expand_texture( grs_bitmap * bmp )
  457. {
  458.     int i;
  459.     int lowest_count, lc;
  460.     int least_recently_used;
  461.  
  462.     if (!rle_cache_initialized) rle_cache_init();
  463.  
  464.     Assert( !(bmp->bm_flags & BM_FLAG_PAGED_OUT) );
  465.  
  466.     lc = rle_counter;
  467.     rle_counter++;
  468.     if ( rle_counter < lc )    {
  469.         for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
  470.             rle_cache[i].rle_bitmap = NULL;
  471.             rle_cache[i].last_used = 0;
  472.         }
  473.     }
  474.  
  475. //    if (((rle_counter % 100)==1) && (rle_hits+rle_misses > 0))
  476. //        mprintf(( 0, "RLE-CACHE %d%%, H:%d, M:%d\n", (rle_misses*100)/(rle_hits+rle_misses), rle_hits, rle_misses ));
  477.  
  478.     lowest_count = rle_cache[rle_next].last_used;
  479.     least_recently_used = rle_next;
  480.     rle_next++;
  481.     if ( rle_next >= MAX_CACHE_BITMAPS )
  482.         rle_next = 0;
  483.         
  484.     for (i=0; i<MAX_CACHE_BITMAPS; i++ )    {
  485.         if (rle_cache[i].rle_bitmap == bmp)     {
  486.             rle_hits++;
  487.             rle_cache[i].last_used = rle_counter;
  488.             return rle_cache[i].expanded_bitmap;
  489.         }
  490.         if ( rle_cache[i].last_used < lowest_count )    {
  491.             lowest_count = rle_cache[i].last_used;
  492.             least_recently_used = i;
  493.         }
  494.     }    
  495.     rle_misses++;
  496.     rle_expand_texture_sub( bmp, rle_cache[least_recently_used].expanded_bitmap );
  497.     rle_cache[least_recently_used].rle_bitmap = bmp;
  498.     rle_cache[least_recently_used].last_used = rle_counter;
  499.     return rle_cache[least_recently_used].expanded_bitmap;
  500. }
  501.  
  502. void rle_expand_texture_sub( grs_bitmap * bmp, grs_bitmap * rle_temp_bitmap_1 )
  503. {
  504.     unsigned char * dbits;
  505.     unsigned char * sbits;
  506.     int i;
  507.     unsigned char * dbits1;
  508.  
  509.     sbits = &bmp->bm_data[4 + 64];
  510.     dbits = rle_temp_bitmap_1->bm_data;
  511.  
  512.     rle_temp_bitmap_1->bm_flags = bmp->bm_flags & (~BM_FLAG_RLE);
  513.  
  514.     for (i=0; i < 64; i++ )    {
  515.         dbits1=(unsigned char *)gr_rle_decode_asm( sbits, dbits );
  516.         sbits += (int)bmp->bm_data[4+i];
  517.         dbits += 64;
  518.         Assert( dbits == dbits1 );        // Get John, bogus rle data!
  519.     }
  520. }
  521.  
  522.  
  523. void gr_rle_expand_scanline_generic( grs_bitmap * dest, int dx, int dy, ubyte *src, int x1, int x2  )
  524. {
  525.     int i = 0, j;
  526.     int count;
  527.     ubyte color;
  528.  
  529.     if ( x2 < x1 ) return;
  530.  
  531.     count = 0;
  532.     while ( i < x1 )    {
  533.         color = *src++;
  534.         if ( color == RLE_CODE ) return;
  535.         if ( (color & RLE_CODE) == RLE_CODE )    {
  536.             count = color & NOT_RLE_CODE;
  537.             color = *src++;
  538.         } else {
  539.             // unique
  540.             count = 1;
  541.         }
  542.         i += count;
  543.     }
  544.     count = i - x1;
  545.     i = x1;
  546.     // we know have '*count' pixels of 'color'.
  547.     
  548.     if ( x1+count > x2 )    {
  549.         count = x2-x1+1;
  550.         for ( j=0; j<count; j++ )
  551.             gr_bm_pixel( dest, dx++, dy, color );
  552.         return;
  553.     }
  554.  
  555.     for ( j=0; j<count; j++ )
  556.         gr_bm_pixel( dest, dx++, dy, color );
  557.     i += count;
  558.  
  559.     while( i <= x2 )        {
  560.         color = *src++;
  561.         if ( color == RLE_CODE ) return;
  562.         if ( (color & RLE_CODE) == RLE_CODE )    {
  563.             count = color & NOT_RLE_CODE;
  564.             color = *src++;
  565.         } else {
  566.             // unique
  567.             count = 1;
  568.         }
  569.         // we know have '*count' pixels of 'color'.
  570.         if ( i+count <= x2 )    {
  571.             for ( j=0; j<count; j++ )
  572.                 gr_bm_pixel( dest, dx++, dy, color );
  573.             i += count;
  574.         } else {
  575.             count = x2-i+1;
  576.             for ( j=0; j<count; j++ )
  577.                 gr_bm_pixel( dest, dx++, dy, color );
  578.             i += count;
  579.         }
  580.     }    
  581. }
  582. 
  583.