win/share/giftiles.c

   1 /* NetHack 3.7    giftiles.c    $NHDT-Date: 1596498335 2020/08/03 23:45:35 $ $NHDT-Branch: NetHack-3.7 $:$NHDT-Revision: 1.1 $ */
   2 /* Copyright (c) Ray Chason, 2016. */
   3 /* NetHack may be freely redistributed.  See license for details. */
   4
   5 /* giftiles.c -- read a tile map in GIF format */
   6 /* Reference: GIF specification,, retrieved from
   7  * http://www.w3.org/Graphics/GIF/spec-gif89a.txt */
   8
   9 #include "config.h"
  10 #include "tileset.h"
  11
  12 #define MIN_LZW_BITS 3
  13 #define MAX_LZW_BITS 12
  14 #define END_OF_DATA 0x7FFF
  15
  16 /* For use when reading the GIF as a bitstream */
  17 struct Bitstream {
  18     /* The file */
  19     FILE *fp;
  20
  21     /* For unpacking LZW codes */
  22     unsigned long bits;
  23     unsigned char num_bits;
  24     unsigned char bit_width;
  25     unsigned char initial_bit_width;
  26     unsigned char block_size;
  27
  28     /* The dictionary */
  29     struct {
  30         unsigned char byte;
  31         unsigned short next;
  32     } dictionary[1 << MAX_LZW_BITS];
  33     unsigned short dict_size;
  34
  35     /* The string currently being decoded */
  36     unsigned char string[1 << MAX_LZW_BITS];
  37     unsigned short str_size;
  38
  39     unsigned short last_code;
  40 };
  41
  42 struct DataBlock {
  43     size_t size;
  44     size_t index;
  45     unsigned char *data;
  46 };
  47
  48 static boolean read_data_block(struct Bitstream *gif,
  49                                struct DataBlock *block);
  50 static void free_data_block(struct DataBlock *block);
  51 static unsigned short read_u16(const unsigned char buf[2]);
  52 static void init_decoder(struct Bitstream *gif, unsigned bit_width);
  53 static void reset_decoder(struct Bitstream *gif);
  54 static int decode(struct Bitstream *gif, struct DataBlock *block);
  55 static int get_code(struct Bitstream *gif, struct DataBlock *block);
  56 static unsigned interlace_incr(unsigned y, unsigned height);
  57
  58 /*
  59  * GIF specifies a canvas, which may have a palette (the "global color table")
  60  * of up to 256 colors, of which one is a background color, and zero or more
  61  * images, each of which may have its own palette (a "local color table")
  62  * independently of the canvas. We will join all palettes found into a single
  63  * palette, and indicate that the image uses a palette if, and only if, the
  64  * various palettes do not total more than 256 colors.
  65  */
  66
  67 boolean
  68 read_gif_tiles(const char *filename, struct TileSetImage *image)
  69 {
  70     struct Bitstream gif;
  71     struct DataBlock block;
  72
  73     unsigned char buf[1024];
  74     size_t size, num_pixels, i;
  75
  76     /* Image data not returned to the caller */
  77     boolean have_gct;   /* global color table is present */
  78     unsigned gct_size;  /* global color table size */
  79     unsigned back_color; /* index for background color */
  80     unsigned trans_color = 0xFFFF; /* index for transparent palette entry */
  81
  82     block.data = NULL;      /* custodial */
  83     gif.fp = NULL;          /* custodial */
  84
  85     image->width = 0;
  86     image->height = 0;
  87     image->pixels = NULL;       /* custodial, returned */
  88     image->indexes = NULL;      /* custodial, returned */
  89     image->image_desc = NULL;   /* custodial, returned */
  90     image->tile_width = 0;
  91     image->tile_height = 0;
  92
  93     gif.fp = fopen(filename, "rb");
  94     if (gif.fp == NULL) goto error;
  95
  96     /* 17. Header */
  97     size = fread(buf, 1, 6, gif.fp);
  98     if (size < 6) goto error;
  99     if (memcmp(buf, "GIF87a", 6) != 0 && memcmp(buf, "GIF89a", 6) != 0)
 100         goto error;
 101
 102     /* 18. Logical screen descriptor */
 103     size = fread(buf, 1, 7, gif.fp);
 104     if (size < 7) goto error;
 105     image->width = read_u16(buf + 0);
 106     image->height = read_u16(buf + 2);
 107     have_gct = (buf[4] & 0x80) != 0;
 108     gct_size = 1 << ((buf[4] & 0x07) + 1);
 109     back_color = buf[5];
 110     if (image->width == 0 || image->height == 0) goto error;
 111
 112     /* 19. Global Color Table */
 113     for (i = 0; i < SIZE(image->palette); ++i) {
 114         image->palette[i].r = 0;
 115         image->palette[i].g = 0;
 116         image->palette[i].b = 0;
 117         image->palette[i].a = 255;
 118     }
 119     if (have_gct) {
 120         size = fread(buf, 3, gct_size, gif.fp);
 121         if (size < gct_size) goto error;
 122         for (i = 0; i < gct_size; ++i) {
 123             image->palette[i].r = buf[i * 3 + 0];
 124             image->palette[i].g = buf[i * 3 + 1];
 125             image->palette[i].b = buf[i * 3 + 2];
 126             image->palette[i].a = 255;
 127         }
 128     }
 129
 130     /* Allocate pixel area; watch out for overflow */
 131     num_pixels = (size_t) image->width * (size_t) image->height;
 132     if (num_pixels / image->width != image->height) goto error; /* overflow */
 133     size = num_pixels * sizeof(image->pixels[0]);
 134     if (size / sizeof(image->pixels[0]) != num_pixels) goto error; /* overflow */
 135     image->pixels = (struct Pixel *) alloc(size);
 136     image->indexes = (unsigned char *) alloc(num_pixels);
 137
 138     /* Fill with the background color */
 139     for (i = 0; i < num_pixels; ++i) {
 140         image->pixels[i] = image->palette[back_color];
 141         image->indexes[i] = back_color;
 142     }
 143
 144     /* Read the image data */
 145     while (TRUE) {
 146         int b = fgetc(gif.fp);
 147         if (b == EOF) goto error;
 148
 149         /* 27. Trailer (0x3B) */
 150         if (b == 0x3B) break;
 151
 152         switch (b) {
 153         case 0x2C:
 154             /* 20. Image descriptor (0x2C) */
 155             {
 156                 unsigned img_left, img_top, img_width, img_height;
 157                 boolean have_lct, interlace;
 158                 unsigned lct_start, lct_size;
 159                 struct Pixel lct[256];
 160                 int new_b;
 161                 unsigned x, y, x2, y2;
 162
 163                 size = fread(buf, 1, 9, gif.fp);
 164                 if (size < 9) goto error;
 165                 img_left = read_u16(buf + 0);
 166                 img_top = read_u16(buf + 2);
 167                 img_width = read_u16(buf + 4);
 168                 img_height = read_u16(buf + 6);
 169                 have_lct = (buf[8] & 0x80) != 0;
 170                 interlace = (buf[8] & 0x40) != 0;
 171                 lct_size = 1 << ((buf[8] & 0x07) + 1);
 172
 173                 /* 21. Local color table */
 174                 lct_start = 0;
 175                 memcpy(lct, image->palette, sizeof(lct));
 176                 if (have_lct) {
 177                     size = fread(buf, 3, lct_size, gif.fp);
 178                     if (size < lct_size) goto error;
 179                     for (i = 0; i < lct_size; ++i) {
 180                         lct[i].r = buf[i * 3 + 0];
 181                         lct[i].g = buf[i * 3 + 1];
 182                         lct[i].b = buf[i * 3 + 2];
 183                         lct[i].a = 255;
 184                     }
 185                     /*
 186                      * The combined palette may exceed 256 colors, in which
 187                      * case the indexes array will be discarded, indicating a
 188                      * full-color image.
 189                      */
 190                     if (lct_size + gct_size <= 256) {
 191                         memcpy(image->palette, lct, sizeof(lct[0]) * lct_size);
 192                     }
 193                     lct_start = gct_size;
 194                     gct_size += lct_start;
 195                 }
 196                 if (trans_color != 0xFFFF) {
 197                     lct[trans_color].a = 0;
 198                     if (!have_lct) {
 199                         /* FIXME: this will affect all images using the global
 200                          * color table, not just the current one */
 201                         image->palette[trans_color].a = 0;
 202                     }
 203                 }
 204                 /* 22. Table based image data */
 205                 new_b = fgetc(gif.fp);
 206                 if (new_b == EOF) goto error;
 207                 if (new_b < MIN_LZW_BITS - 1 || MAX_LZW_BITS - 1 < new_b) goto error;
 208                 init_decoder(&gif, new_b);
 209                 x = 0;
 210                 y = 0;
 211                 if (!read_data_block(&gif, &block)) goto error;
 212                 while (TRUE) {
 213                     new_b = decode(&gif, &block);
 214                     if (new_b == EOF) goto error;
 215                     if (new_b == END_OF_DATA) break;
 216                     if (y >= img_height) goto error;
 217                     x2 = img_left + x;
 218                     y2 = img_top + y;
 219                     if (x2 < image->width && y2 < image->height) {
 220                         image->pixels[y2 * image->width + x2] = lct[new_b];
 221                         image->indexes[y2 * image->width + x2] = new_b + lct_start;
 222                     }
 223                     ++x;
 224                     if (x >= img_width) {
 225                         x = 0;
 226                         if (interlace) {
 227                             y = interlace_incr(y, img_height);
 228                         } else {
 229                             ++y;
 230                         }
 231                     }
 232                 }
 233                 free_data_block(&block);
 234                 trans_color = 0xFFFF;
 235             }
 236             break;
 237
 238         case 0x21:
 239             /* Extension blocks */
 240             {
 241                 int label;
 242
 243                 label = fgetc(gif.fp);
 244                 if (label == EOF) goto error;
 245                 if (!read_data_block(&gif, &block)) goto error;
 246                 switch (label) {
 247                 case 0xF9:
 248                     /* 23. Graphic control extension (0xF9) */
 249                     if (block.size >= 4 && (block.data[0] & 0x01) != 0) {
 250                         /* image has a transparent index */
 251                         trans_color = block.data[3];
 252                     }
 253                     break;
 254
 255 #if 0
 256                 case 0xFE:
 257                     /* 24. Comment extension (0xFE) */
 258                     break;
 259
 260                 case 0x01:
 261                     /* 25. Plain text extension (0x01) */
 262                     break;
 263 #endif
 264
 265                 case 0xFF:
 266                     /* 26. Application extension (0xFF) */
 267                     if (block.size > 11
 268                     &&  memcmp(block.data, "NETHACK3GIF", 11) == 0
 269                     &&  image->image_desc == NULL) {
 270                         memmove(block.data, block.data + 11, block.size - 11);
 271                         block.data[block.size - 11] = '\0';
 272                         image->image_desc = (char *) block.data;
 273                         block.data = NULL;
 274                     }
 275                     break;
 276
 277                 default:
 278                     /* Unknown extension type */
 279                     break;
 280                 }
 281                 free_data_block(&block);
 282             }
 283             break;
 284
 285         default:
 286             goto error;
 287         }
 288     }
 289
 290     fclose(gif.fp);
 291     free_data_block(&block);
 292     if (gct_size > 256) {
 293         /* Max palette size exceeded; indexes array is not meaningful */
 294         free(image->indexes);
 295         image->indexes = NULL;
 296     }
 297     return TRUE;
 298
 299 error:
 300     if (gif.fp) fclose(gif.fp);
 301     free_data_block(&block);
 302     free(image->pixels);
 303     image->pixels = NULL;
 304     free(image->indexes);
 305     image->indexes = NULL;
 306     free(image->image_desc);
 307     image->image_desc = NULL;
 308     return FALSE;
 309 }
 310
 311 static void
 312 init_decoder(struct Bitstream *gif, unsigned bit_width)
 313 {
 314     unsigned i;
 315     unsigned clear;
 316
 317     gif->bits = 0;
 318     gif->num_bits = 0;
 319     gif->initial_bit_width = bit_width;
 320     gif->block_size = 0;
 321
 322     clear = 1 << bit_width;
 323     gif->dict_size = clear + 2;
 324     for (i = 0; i < clear; ++i) {
 325         gif->dictionary[i].byte = i;
 326         gif->dictionary[i].next = 0xFFFF;
 327     }
 328
 329     gif->str_size = 0;
 330
 331     reset_decoder(gif);
 332 }
 333
 334 static void
 335 reset_decoder(struct Bitstream *gif)
 336 {
 337     /* Set the bit width */
 338     gif->bit_width = gif->initial_bit_width + 1;
 339
 340     /* Reset the dictionary */
 341     gif->dict_size = (1 << gif->initial_bit_width) + 2;
 342
 343     /* No last code */
 344     gif->last_code = 0xFFFF;
 345 }
 346
 347 static int
 348 decode(struct Bitstream *gif, struct DataBlock *block)
 349 {
 350     int code;
 351     unsigned clear = 1 << gif->initial_bit_width;
 352
 353     /* If a string is being decoded, return the next byte */
 354     if (gif->str_size != 0) {
 355         return gif->string[--gif->str_size];
 356     }
 357
 358     /* Get the next code, until code other than clear */
 359     while (TRUE) {
 360         code = get_code(gif, block);
 361         if ((unsigned) code != clear) break;
 362         reset_decoder(gif);
 363     }
 364
 365     if (code == EOF) return EOF;
 366     if ((unsigned) code == clear + 1) return END_OF_DATA;
 367     if (code > gif->dict_size) return EOF;
 368
 369     /* Add a new string to the dictionary */
 370     if (gif->last_code != 0xFFFF && gif->dict_size < SIZE(gif->dictionary)) {
 371         unsigned next_code;
 372         if (code < gif->dict_size) {
 373             next_code = code;
 374         } else {
 375             next_code = gif->last_code;
 376         }
 377         while (next_code >= clear) {
 378             next_code = gif->dictionary[next_code].next;
 379         }
 380         gif->dictionary[gif->dict_size].next = gif->last_code;
 381         gif->dictionary[gif->dict_size].byte = next_code;
 382         ++gif->dict_size;
 383         if (gif->dict_size >= 1 << gif->bit_width
 384         &&  gif->bit_width < MAX_LZW_BITS) {
 385             ++gif->bit_width;
 386         }
 387     }
 388     gif->last_code = code;
 389
 390     /* code is less than gif->dict_size and not equal to clear or clear + 1 */
 391     /* Prepare the decoded string for return; note that it is stored in
 392      * reverse order */
 393     while ((unsigned) code >= clear) {
 394         gif->string[gif->str_size++] = gif->dictionary[code].byte;
 395         code = gif->dictionary[code].next;
 396     }
 397
 398     return code;
 399 }
 400
 401 static int
 402 get_code(struct Bitstream *gif, struct DataBlock *block)
 403 {
 404     int code;
 405
 406     while (gif->num_bits < gif->bit_width) {
 407         unsigned char b;
 408         if (block->index >= block->size) return EOF;
 409         b = block->data[block->index++];
 410         gif->bits |= (unsigned long)b << gif->num_bits;
 411         gif->num_bits += 8;
 412     }
 413
 414     code = (int) (gif->bits & ((1UL << gif->bit_width) - 1));
 415     gif->bits >>= gif->bit_width;
 416     gif->num_bits -= gif->bit_width;
 417     return code;
 418 }
 419
 420 static unsigned
 421 interlace_incr(unsigned y, unsigned height)
 422 {
 423     static const unsigned char incr[] = { 8, 2, 4, 2 };
 424
 425     /* The lower three bits indicate the current pass */
 426
 427     /* Advance to the next row of the current pass */
 428     y += incr[y & 0x3];
 429
 430     /* Go to the next pass if y exceeds height */
 431     /* Might not be the immediately following pass if height is small */
 432     if (y >= height && (y & 0x7) == 0) {
 433         /* Pass 1 -> Pass 2 */
 434         y = 4;
 435     }
 436     if (y >= height && (y & 0x7) == 4) {
 437         /* Pass 2 -> Pass 3 */
 438         y = 2;
 439     }
 440     if (y >= height && (y & 0x3) == 2) {
 441         /* Pass 3 -> Pass 4 */
 442         y = 1;
 443     }
 444
 445     return y;
 446 }
 447
 448 /* Decode an unsigned 16 bit quantity */
 449 static unsigned short
 450 read_u16(const unsigned char buf[2])
 451 {
 452     return ((unsigned short)buf[0] << 0)
 453          | ((unsigned short)buf[1] << 8);
 454 }
 455
 456 static boolean
 457 read_data_block(struct Bitstream *gif, struct DataBlock *block)
 458 {
 459     long pos = ftell(gif->fp);
 460     int b;
 461     size_t i;
 462
 463     free_data_block(block);
 464
 465     /* Get the length of the data block */
 466     while (TRUE) {
 467         b = fgetc(gif->fp);
 468         if (b == EOF) return FALSE;
 469         if (b == 0) break;
 470         block->size += b;
 471         fseek(gif->fp, b, SEEK_CUR);
 472     }
 473     fseek(gif->fp, pos, SEEK_SET);
 474
 475     /* Allocate memory */
 476     block->data = (unsigned char *) alloc(block->size);
 477
 478     /* Read the data from the file */
 479     i = 0;
 480     while (TRUE) {
 481         b = fgetc(gif->fp);
 482         if (b == EOF) return FALSE;
 483         if (b == 0) break;
 484         if (fread(block->data + i, 1, b, gif->fp) != (unsigned) b)
 485             return FALSE;
 486         i += b;
 487     }
 488
 489     block->index = 0;
 490     return TRUE;
 491 }
 492
 493 static void
 494 free_data_block(struct DataBlock *block)
 495 {
 496     free(block->data);
 497     block->size = 0;
 498     block->data = NULL;
 499 }