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