2d/rle.c

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