gifdec.c

   1 #include "gifdec.h"
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include <sys/types.h>
   8 #include <sys/stat.h>
   9 #include <fcntl.h>
  10 #ifdef _WIN32
  11 #include <io.h>
  12 #else
  13 #include <unistd.h>
  14 #endif
  15
  16 #define MIN(A, B) ((A) < (B) ? (A) : (B))
  17 #define MAX(A, B) ((A) > (B) ? (A) : (B))
  18
  19 typedef struct Entry {
  20     uint16_t length;
  21     uint16_t prefix;
  22     uint8_t  suffix;
  23 } Entry;
  24
  25 typedef struct Table {
  26     int bulk;
  27     int nentries;
  28     Entry *entries;
  29 } Table;
  30
  31 static uint16_t
  32 read_num(int fd)
  33 {
  34     uint8_t bytes[2];
  35
  36     read(fd, bytes, 2);
  37     return bytes[0] + (((uint16_t) bytes[1]) << 8);
  38 }
  39
  40 gd_GIF *
  41 gd_open_gif(const char *fname)
  42 {
  43     int fd;
  44     uint8_t sigver[3];
  45     uint16_t width, height, depth;
  46     uint8_t fdsz, bgidx, aspect;
  47     int i;
  48     uint8_t *bgcolor;
  49     int gct_sz;
  50     gd_GIF *gif;
  51
  52     fd = open(fname, O_RDONLY);
  53     if (fd == -1) return NULL;
  54 #ifdef _WIN32
  55     setmode(fd, O_BINARY);
  56 #endif
  57     /* Header */
  58     read(fd, sigver, 3);
  59     if (memcmp(sigver, "GIF", 3) != 0) {
  60         fprintf(stderr, "invalid signature\n");
  61         goto fail;
  62     }
  63     /* Version */
  64     read(fd, sigver, 3);
  65     if (memcmp(sigver, "89a", 3) != 0) {
  66         fprintf(stderr, "invalid version\n");
  67         goto fail;
  68     }
  69     /* Width x Height */
  70     width  = read_num(fd);
  71     height = read_num(fd);
  72     /* FDSZ */
  73     read(fd, &fdsz, 1);
  74     /* Presence of GCT */
  75     if (!(fdsz & 0x80)) {
  76         fprintf(stderr, "no global color table\n");
  77         goto fail;
  78     }
  79     /* Color Space's Depth */
  80     depth = ((fdsz >> 4) & 7) + 1;
  81     /* Ignore Sort Flag. */
  82     /* GCT Size */
  83     gct_sz = 1 << ((fdsz & 0x07) + 1);
  84     /* Background Color Index */
  85     read(fd, &bgidx, 1);
  86     /* Aspect Ratio */
  87     read(fd, &aspect, 1);
  88     /* Create gd_GIF Structure. */
  89     gif = calloc(1, sizeof(*gif));
  90     if (!gif) goto fail;
  91     gif->fd = fd;
  92     gif->width  = width;
  93     gif->height = height;
  94     gif->depth  = depth;
  95     /* Read GCT */
  96     gif->gct.size = gct_sz;
  97     read(fd, gif->gct.colors, 3 * gif->gct.size);
  98     gif->palette = &gif->gct;
  99     gif->bgindex = bgidx;
 100     gif->frame = calloc(4, width * height);
 101     if (!gif->frame) {
 102         free(gif);
 103         goto fail;
 104     }
 105     gif->canvas = &gif->frame[width * height];
 106     if (gif->bgindex)
 107         memset(gif->frame, gif->bgindex, gif->width * gif->height);
 108     bgcolor = &gif->palette->colors[gif->bgindex*3];
 109     if (bgcolor[0] || bgcolor[1] || bgcolor [2])
 110         for (i = 0; i < gif->width * gif->height; i++)
 111             memcpy(&gif->canvas[i*3], bgcolor, 3);
 112     gif->anim_start = lseek(fd, 0, SEEK_CUR);
 113     goto ok;
 114 fail:
 115     close(fd);
 116     return 0;
 117 ok:
 118     return gif;
 119 }
 120
 121 static void
 122 discard_sub_blocks(gd_GIF *gif)
 123 {
 124     uint8_t size;
 125
 126     do {
 127         read(gif->fd, &size, 1);
 128         lseek(gif->fd, size, SEEK_CUR);
 129     } while (size);
 130 }
 131
 132 static void
 133 read_plain_text_ext(gd_GIF *gif)
 134 {
 135     if (gif->plain_text) {
 136         uint16_t tx, ty, tw, th;
 137         uint8_t cw, ch, fg, bg;
 138         off_t sub_block;
 139         lseek(gif->fd, 1, SEEK_CUR); /* block size = 12 */
 140         tx = read_num(gif->fd);
 141         ty = read_num(gif->fd);
 142         tw = read_num(gif->fd);
 143         th = read_num(gif->fd);
 144         read(gif->fd, &cw, 1);
 145         read(gif->fd, &ch, 1);
 146         read(gif->fd, &fg, 1);
 147         read(gif->fd, &bg, 1);
 148         sub_block = lseek(gif->fd, 0, SEEK_CUR);
 149         gif->plain_text(gif, tx, ty, tw, th, cw, ch, fg, bg);
 150         lseek(gif->fd, sub_block, SEEK_SET);
 151     } else {
 152         /* Discard plain text metadata. */
 153         lseek(gif->fd, 13, SEEK_CUR);
 154     }
 155     /* Discard plain text sub-blocks. */
 156     discard_sub_blocks(gif);
 157 }
 158
 159 static void
 160 read_graphic_control_ext(gd_GIF *gif)
 161 {
 162     uint8_t rdit;
 163
 164     /* Discard block size (always 0x04). */
 165     lseek(gif->fd, 1, SEEK_CUR);
 166     read(gif->fd, &rdit, 1);
 167     gif->gce.disposal = (rdit >> 2) & 3;
 168     gif->gce.input = rdit & 2;
 169     gif->gce.transparency = rdit & 1;
 170     gif->gce.delay = read_num(gif->fd);
 171     read(gif->fd, &gif->gce.tindex, 1);
 172     /* Skip block terminator. */
 173     lseek(gif->fd, 1, SEEK_CUR);
 174 }
 175
 176 static void
 177 read_comment_ext(gd_GIF *gif)
 178 {
 179     if (gif->comment) {
 180         off_t sub_block = lseek(gif->fd, 0, SEEK_CUR);
 181         gif->comment(gif);
 182         lseek(gif->fd, sub_block, SEEK_SET);
 183     }
 184     /* Discard comment sub-blocks. */
 185     discard_sub_blocks(gif);
 186 }
 187
 188 static void
 189 read_application_ext(gd_GIF *gif)
 190 {
 191     char app_id[8];
 192     char app_auth_code[3];
 193
 194     /* Discard block size (always 0x0B). */
 195     lseek(gif->fd, 1, SEEK_CUR);
 196     /* Application Identifier. */
 197     read(gif->fd, app_id, 8);
 198     /* Application Authentication Code. */
 199     read(gif->fd, app_auth_code, 3);
 200     if (!strncmp(app_id, "NETSCAPE", sizeof(app_id))) {
 201         /* Discard block size (0x03) and constant byte (0x01). */
 202         lseek(gif->fd, 2, SEEK_CUR);
 203         gif->loop_count = read_num(gif->fd);
 204         /* Skip block terminator. */
 205         lseek(gif->fd, 1, SEEK_CUR);
 206     } else if (gif->application) {
 207         off_t sub_block = lseek(gif->fd, 0, SEEK_CUR);
 208         gif->application(gif, app_id, app_auth_code);
 209         lseek(gif->fd, sub_block, SEEK_SET);
 210         discard_sub_blocks(gif);
 211     } else {
 212         discard_sub_blocks(gif);
 213     }
 214 }
 215
 216 static void
 217 read_ext(gd_GIF *gif)
 218 {
 219     uint8_t label;
 220
 221     read(gif->fd, &label, 1);
 222     switch (label) {
 223     case 0x01:
 224         read_plain_text_ext(gif);
 225         break;
 226     case 0xF9:
 227         read_graphic_control_ext(gif);
 228         break;
 229     case 0xFE:
 230         read_comment_ext(gif);
 231         break;
 232     case 0xFF:
 233         read_application_ext(gif);
 234         break;
 235     default:
 236         fprintf(stderr, "unknown extension: %02X\n", label);
 237     }
 238 }
 239
 240 static Table *
 241 new_table(int key_size)
 242 {
 243     int key;
 244     int init_bulk = MAX(1 << (key_size + 1), 0x100);
 245     Table *table = malloc(sizeof(*table) + sizeof(Entry) * init_bulk);
 246     if (table) {
 247         table->bulk = init_bulk;
 248         table->nentries = (1 << key_size) + 2;
 249         table->entries = (Entry *) &table[1];
 250         for (key = 0; key < (1 << key_size); key++)
 251             table->entries[key] = (Entry) {1, 0xFFF, key};
 252     }
 253     return table;
 254 }
 255
 256 /* Add table entry. Return value:
 257  *  0 on success
 258  *  +1 if key size must be incremented after this addition
 259  *  -1 if could not realloc table */
 260 static int
 261 add_entry(Table **tablep, uint16_t length, uint16_t prefix, uint8_t suffix)
 262 {
 263     Table *table = *tablep;
 264     if (table->nentries == table->bulk) {
 265         table->bulk *= 2;
 266         table = realloc(table, sizeof(*table) + sizeof(Entry) * table->bulk);
 267         if (!table) return -1;
 268         table->entries = (Entry *) &table[1];
 269         *tablep = table;
 270     }
 271     table->entries[table->nentries] = (Entry) {length, prefix, suffix};
 272     table->nentries++;
 273     if ((table->nentries & (table->nentries - 1)) == 0)
 274         return 1;
 275     return 0;
 276 }
 277
 278 static uint16_t
 279 get_key(gd_GIF *gif, int key_size, uint8_t *sub_len, uint8_t *shift, uint8_t *byte)
 280 {
 281     int bits_read;
 282     int rpad;
 283     int frag_size;
 284     uint16_t key;
 285
 286     key = 0;
 287     for (bits_read = 0; bits_read < key_size; bits_read += frag_size) {
 288         rpad = (*shift + bits_read) % 8;
 289         if (rpad == 0) {
 290             /* Update byte. */
 291             if (*sub_len == 0) {
 292                 read(gif->fd, sub_len, 1); /* Must be nonzero! */
 293                 if (*sub_len == 0)
 294                     return 0x1000;
 295             }
 296             read(gif->fd, byte, 1);
 297             (*sub_len)--;
 298         }
 299         frag_size = MIN(key_size - bits_read, 8 - rpad);
 300         key |= ((uint16_t) ((*byte) >> rpad)) << bits_read;
 301     }
 302     /* Clear extra bits to the left. */
 303     key &= (1 << key_size) - 1;
 304     *shift = (*shift + key_size) % 8;
 305     return key;
 306 }
 307
 308 /* Compute output index of y-th input line, in frame of height h. */
 309 static int
 310 interlaced_line_index(int h, int y)
 311 {
 312     int p; /* number of lines in current pass */
 313
 314     p = (h - 1) / 8 + 1;
 315     if (y < p) /* pass 1 */
 316         return y * 8;
 317     y -= p;
 318     p = (h - 5) / 8 + 1;
 319     if (y < p) /* pass 2 */
 320         return y * 8 + 4;
 321     y -= p;
 322     p = (h - 3) / 4 + 1;
 323     if (y < p) /* pass 3 */
 324         return y * 4 + 2;
 325     y -= p;
 326     /* pass 4 */
 327     return y * 2 + 1;
 328 }
 329
 330 /* Decompress image pixels.
 331  * Return 0 on success or -1 on out-of-memory (w.r.t. LZW code table). */
 332 static int
 333 read_image_data(gd_GIF *gif, int interlace)
 334 {
 335     uint8_t sub_len, shift, byte;
 336     int init_key_size, key_size, table_is_full;
 337     int frm_off, frm_size, str_len, i, p, x, y;
 338     uint16_t key, clear, stop;
 339     int ret;
 340     Table *table;
 341     Entry entry;
 342     off_t start, end;
 343
 344     read(gif->fd, &byte, 1);
 345     key_size = (int) byte;
 346     if (key_size < 2 || key_size > 8)
 347         return -1;
 348
 349     start = lseek(gif->fd, 0, SEEK_CUR);
 350     discard_sub_blocks(gif);
 351     end = lseek(gif->fd, 0, SEEK_CUR);
 352     lseek(gif->fd, start, SEEK_SET);
 353     clear = 1 << key_size;
 354     stop = clear + 1;
 355     table = new_table(key_size);
 356     key_size++;
 357     init_key_size = key_size;
 358     sub_len = shift = 0;
 359     key = get_key(gif, key_size, &sub_len, &shift, &byte); /* clear code */
 360     frm_off = 0;
 361     ret = 0;
 362     frm_size = gif->fw*gif->fh;
 363     while (frm_off < frm_size) {
 364         if (key == clear) {
 365             key_size = init_key_size;
 366             table->nentries = (1 << (key_size - 1)) + 2;
 367             table_is_full = 0;
 368         } else if (!table_is_full) {
 369             ret = add_entry(&table, str_len + 1, key, entry.suffix);
 370             if (ret == -1) {
 371                 free(table);
 372                 return -1;
 373             }
 374             if (table->nentries == 0x1000) {
 375                 ret = 0;
 376                 table_is_full = 1;
 377             }
 378         }
 379         key = get_key(gif, key_size, &sub_len, &shift, &byte);
 380         if (key == clear) continue;
 381         if (key == stop || key == 0x1000) break;
 382         if (ret == 1) key_size++;
 383         entry = table->entries[key];
 384         str_len = entry.length;
 385         for (i = 0; i < str_len; i++) {
 386             p = frm_off + entry.length - 1;
 387             x = p % gif->fw;
 388             y = p / gif->fw;
 389             if (interlace)
 390                 y = interlaced_line_index((int) gif->fh, y);
 391             gif->frame[(gif->fy + y) * gif->width + gif->fx + x] = entry.suffix;
 392             if (entry.prefix == 0xFFF)
 393                 break;
 394             else
 395                 entry = table->entries[entry.prefix];
 396         }
 397         frm_off += str_len;
 398         if (key < table->nentries - 1 && !table_is_full)
 399             table->entries[table->nentries - 1].suffix = entry.suffix;
 400     }
 401     free(table);
 402     if (key == stop)
 403         read(gif->fd, &sub_len, 1); /* Must be zero! */
 404     lseek(gif->fd, end, SEEK_SET);
 405     return 0;
 406 }
 407
 408 /* Read image.
 409  * Return 0 on success or -1 on out-of-memory (w.r.t. LZW code table). */
 410 static int
 411 read_image(gd_GIF *gif)
 412 {
 413     uint8_t fisrz;
 414     int interlace;
 415
 416     /* Image Descriptor. */
 417     gif->fx = read_num(gif->fd);
 418     gif->fy = read_num(gif->fd);
 419
 420     if (gif->fx >= gif->width || gif->fy >= gif->height)
 421         return -1;
 422
 423     gif->fw = read_num(gif->fd);
 424     gif->fh = read_num(gif->fd);
 425
 426     gif->fw = MIN(gif->fw, gif->width - gif->fx);
 427     gif->fh = MIN(gif->fh, gif->height - gif->fy);
 428
 429     read(gif->fd, &fisrz, 1);
 430     interlace = fisrz & 0x40;
 431     /* Ignore Sort Flag. */
 432     /* Local Color Table? */
 433     if (fisrz & 0x80) {
 434         /* Read LCT */
 435         gif->lct.size = 1 << ((fisrz & 0x07) + 1);
 436         read(gif->fd, gif->lct.colors, 3 * gif->lct.size);
 437         gif->palette = &gif->lct;
 438     } else
 439         gif->palette = &gif->gct;
 440     /* Image Data. */
 441     return read_image_data(gif, interlace);
 442 }
 443
 444 static void
 445 render_frame_rect(gd_GIF *gif, uint8_t *buffer)
 446 {
 447     int i, j, k;
 448     uint8_t index, *color;
 449     i = gif->fy * gif->width + gif->fx;
 450     for (j = 0; j < gif->fh; j++) {
 451         for (k = 0; k < gif->fw; k++) {
 452             index = gif->frame[(gif->fy + j) * gif->width + gif->fx + k];
 453             color = &gif->palette->colors[index*3];
 454             if (!gif->gce.transparency || index != gif->gce.tindex)
 455                 memcpy(&buffer[(i+k)*3], color, 3);
 456         }
 457         i += gif->width;
 458     }
 459 }
 460
 461 static void
 462 dispose(gd_GIF *gif)
 463 {
 464     int i, j, k;
 465     uint8_t *bgcolor;
 466     switch (gif->gce.disposal) {
 467     case 2: /* Restore to background color. */
 468         bgcolor = &gif->palette->colors[gif->bgindex*3];
 469         i = gif->fy * gif->width + gif->fx;
 470         for (j = 0; j < gif->fh; j++) {
 471             for (k = 0; k < gif->fw; k++)
 472                 memcpy(&gif->canvas[(i+k)*3], bgcolor, 3);
 473             i += gif->width;
 474         }
 475         break;
 476     case 3: /* Restore to previous, i.e., don't update canvas.*/
 477         break;
 478     default:
 479         /* Add frame non-transparent pixels to canvas. */
 480         render_frame_rect(gif, gif->canvas);
 481     }
 482 }
 483
 484 /* Return 1 if got a frame; 0 if got GIF trailer; -1 if error. */
 485 int
 486 gd_get_frame(gd_GIF *gif)
 487 {
 488     char sep;
 489
 490     dispose(gif);
 491     read(gif->fd, &sep, 1);
 492     while (sep != ',') {
 493         if (sep == ';')
 494             return 0;
 495         if (sep == '!')
 496             read_ext(gif);
 497         else return -1;
 498         read(gif->fd, &sep, 1);
 499     }
 500     if (read_image(gif) == -1)
 501         return -1;
 502     return 1;
 503 }
 504
 505 void
 506 gd_render_frame(gd_GIF *gif, uint8_t *buffer)
 507 {
 508     memcpy(buffer, gif->canvas, gif->width * gif->height * 3);
 509     render_frame_rect(gif, buffer);
 510 }
 511
 512 int
 513 gd_is_bgcolor(gd_GIF *gif, uint8_t color[3])
 514 {
 515     return !memcmp(&gif->palette->colors[gif->bgindex*3], color, 3);
 516 }
 517
 518 void
 519 gd_rewind(gd_GIF *gif)
 520 {
 521     lseek(gif->fd, gif->anim_start, SEEK_SET);
 522 }
 523
 524 void
 525 gd_close_gif(gd_GIF *gif)
 526 {
 527     close(gif->fd);
 528     free(gif->frame);
 529     free(gif);
 530 }