2d/rle.c

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