img_gif.c 9.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434
  1. /* GIF87a/89a: first frame, LZW, interlace and transparency. */
  2. #include "img_internal.h"
  3. struct gif_rd {
  4. const unsigned char *d;
  5. unsigned int n, pos;
  6. unsigned int blk_left;
  7. };
  8. static int gif_u8(struct gif_rd *r, unsigned int *v)
  9. {
  10. if (r->pos >= r->n)
  11. return -1;
  12. *v = r->d[r->pos++];
  13. return 0;
  14. }
  15. static int gif_subblock(struct gif_rd *r)
  16. {
  17. unsigned int len;
  18. if (r->blk_left)
  19. return 0;
  20. if (gif_u8(r, &len))
  21. return -1;
  22. r->blk_left = len;
  23. return len ? 0 : 1; /* 1 = end of sub-block chain */
  24. }
  25. static int gif_skip_subblocks(struct gif_rd *r)
  26. {
  27. int e;
  28. do {
  29. e = gif_subblock(r);
  30. if (e < 0)
  31. return -1;
  32. if (e > 0)
  33. return 0;
  34. while (r->blk_left) {
  35. r->blk_left--;
  36. if (r->pos >= r->n)
  37. return -1;
  38. r->pos++;
  39. }
  40. } while (1);
  41. }
  42. static int gif_palette(const unsigned char *d, unsigned int n,
  43. unsigned int off, unsigned int entries,
  44. unsigned char pal[256][3])
  45. {
  46. unsigned int i;
  47. if (off > n || entries * 3u > n - off)
  48. return -1;
  49. for (i = 0; i < entries && i < 256; i++) {
  50. pal[i][0] = d[off + i * 3];
  51. pal[i][1] = d[off + i * 3 + 1];
  52. pal[i][2] = d[off + i * 3 + 2];
  53. }
  54. return 0;
  55. }
  56. static int gif_header(const unsigned char *d, unsigned int n,
  57. unsigned int *w, unsigned int *h, unsigned int *packed,
  58. unsigned int *bg, unsigned int *gct_off,
  59. unsigned int *gct_entries, unsigned int *pos)
  60. {
  61. if (n < 13 || d[0] != 'G' || d[1] != 'I' || d[2] != 'F' ||
  62. d[3] != '8' || (d[4] != '7' && d[4] != '9') || d[5] != 'a')
  63. return -1;
  64. *w = img_le16(d + 6);
  65. *h = img_le16(d + 8);
  66. *packed = d[10];
  67. *bg = d[11];
  68. *gct_entries = 0;
  69. *gct_off = 13;
  70. if (*packed & 0x80) {
  71. *gct_entries = 1u << ((*packed & 7) + 1);
  72. if (*gct_off + *gct_entries * 3u > n)
  73. return -1;
  74. }
  75. *pos = *gct_off + *gct_entries * 3u;
  76. if (*w == 0 || *h == 0 || *w > 32768 || *h > 32768)
  77. return -1;
  78. return 0;
  79. }
  80. /* Walk extensions until the first image descriptor. Fills the transparency
  81. * information; returns 0 with the image descriptor position in *img_pos. */
  82. static int gif_scan(const unsigned char *d, unsigned int n, unsigned int start,
  83. unsigned int *img_pos, int *transparent,
  84. unsigned int *trans_index)
  85. {
  86. struct gif_rd r;
  87. r.d = d;
  88. r.n = n;
  89. r.pos = start;
  90. r.blk_left = 0;
  91. *transparent = 0;
  92. *trans_index = 0;
  93. while (r.pos < n) {
  94. unsigned int b;
  95. if (gif_u8(&r, &b))
  96. return -1;
  97. if (b == 0x3B) {
  98. *img_pos = r.pos;
  99. return 0;
  100. }
  101. if (b == 0x21) {
  102. unsigned int label;
  103. if (gif_u8(&r, &label))
  104. return -1;
  105. if (label == 0xF9) {
  106. unsigned int len, pk = 0, idx = 0;
  107. if (gif_u8(&r, &len) || len < 4)
  108. return -1;
  109. {
  110. unsigned int i;
  111. for (i = 0; i < len; i++) {
  112. unsigned int v;
  113. if (gif_u8(&r, &v))
  114. return -1;
  115. if (i == 0)
  116. pk = v;
  117. if (i == 3)
  118. idx = v;
  119. }
  120. }
  121. if (pk & 1) {
  122. *transparent = 1;
  123. *trans_index = idx;
  124. }
  125. if (gif_u8(&r, &b) || b != 0)
  126. return -1; /* block terminator */
  127. } else {
  128. if (gif_skip_subblocks(&r))
  129. return -1;
  130. }
  131. continue;
  132. }
  133. if (b == 0x2C) {
  134. *img_pos = r.pos - 1;
  135. return 0;
  136. }
  137. if (b == 0x00) {
  138. while (r.pos < n && d[r.pos] == 0)
  139. r.pos++;
  140. continue;
  141. }
  142. return -1;
  143. }
  144. *img_pos = r.pos;
  145. return 0;
  146. }
  147. int img_sniff_gif(const unsigned char *d, unsigned int n, struct img_info *out)
  148. {
  149. unsigned int w, h, packed, bg, goff, gent, pos, ipos, ti;
  150. int tr;
  151. if (gif_header(d, n, &w, &h, &packed, &bg, &goff, &gent, &pos))
  152. return IMG_FMT_UNKNOWN;
  153. out->format = IMG_FMT_GIF;
  154. out->width = w;
  155. out->height = h;
  156. out->has_alpha = 0;
  157. if (gif_scan(d, n, pos, &ipos, &tr, &ti) == 0)
  158. out->has_alpha = tr != 0;
  159. return IMG_FMT_GIF;
  160. }
  161. struct gif_lzw {
  162. struct gif_rd *r;
  163. unsigned int bitbuf;
  164. int bitcnt;
  165. };
  166. static int lzw_code(struct gif_lzw *z, int bits, int *out)
  167. {
  168. int v;
  169. while (z->bitcnt < bits) {
  170. int e = gif_subblock(z->r);
  171. unsigned int b;
  172. if (e < 0)
  173. return -1;
  174. if (e > 0)
  175. return -1;
  176. if (gif_u8(z->r, &b))
  177. return -1;
  178. z->r->blk_left--;
  179. z->bitbuf |= b << z->bitcnt;
  180. z->bitcnt += 8;
  181. }
  182. v = (int)(z->bitbuf & ((1u << bits) - 1u));
  183. z->bitbuf >>= bits;
  184. z->bitcnt -= bits;
  185. *out = v;
  186. return 0;
  187. }
  188. static void gif_put(struct img_image *im, unsigned int x, unsigned int y,
  189. unsigned int r, unsigned int g, unsigned int b,
  190. unsigned int a)
  191. {
  192. if (x >= im->w || y >= im->h)
  193. return;
  194. im->px[y * im->w + x] = img_rgb565(r, g, b);
  195. if (im->alpha)
  196. im->alpha[y * im->w + x] = (unsigned char)a;
  197. }
  198. static unsigned int gif_scan_row(unsigned int fh, unsigned int n)
  199. {
  200. static const unsigned int start[4] = {0, 4, 2, 1};
  201. static const unsigned int step[4] = {8, 8, 4, 2};
  202. unsigned int p;
  203. for (p = 0; p < 4; p++) {
  204. unsigned int count = 0;
  205. if (fh > start[p])
  206. count = (fh - start[p] + step[p] - 1) / step[p];
  207. if (n < count)
  208. return start[p] + n * step[p];
  209. n -= count;
  210. }
  211. return fh ? fh - 1 : 0;
  212. }
  213. int img_decode_gif(const unsigned char *d, unsigned int n,
  214. const struct img_options *opt, struct img_mem *m,
  215. struct img_image *out)
  216. {
  217. unsigned int w, h, packed, bg, goff, gent, pos, ipos;
  218. unsigned int trans_index = 0;
  219. int transparent = 0;
  220. unsigned char gpal[256][3], lpal[256][3];
  221. unsigned int fw, fh, left, top, fpacked, lct_entries = 0;
  222. unsigned int min_code, i;
  223. unsigned int total_pixels, done = 0;
  224. unsigned int mark, image_end;
  225. struct gif_rd rd;
  226. struct gif_lzw z;
  227. int rcode;
  228. mark = img_mem_mark(m);
  229. if (gif_header(d, n, &w, &h, &packed, &bg, &goff, &gent, &pos))
  230. return IMG_ERR_FORMAT;
  231. if (!img_size_ok(w, h, opt))
  232. return IMG_ERR_TOOBIG;
  233. for (i = 0; i < 256; i++)
  234. gpal[i][0] = gpal[i][1] = gpal[i][2] = 0;
  235. if (gent && gif_palette(d, n, goff, gent, gpal))
  236. return IMG_ERR_CORRUPT;
  237. if (gif_scan(d, n, pos, &ipos, &transparent, &trans_index))
  238. return IMG_ERR_CORRUPT;
  239. if (ipos + 9 > n || d[ipos] != 0x2C)
  240. return IMG_ERR_CORRUPT;
  241. left = img_le16(d + ipos + 1);
  242. top = img_le16(d + ipos + 3);
  243. fw = img_le16(d + ipos + 5);
  244. fh = img_le16(d + ipos + 7);
  245. fpacked = d[ipos + 9];
  246. pos = ipos + 10;
  247. if (fw == 0 || fh == 0)
  248. return IMG_ERR_CORRUPT;
  249. if (left > w || top > h || fw > w - left || fh > h - top)
  250. return IMG_ERR_UNSUPPORTED;
  251. if (fpacked & 0x80) {
  252. lct_entries = 1u << ((fpacked & 7) + 1);
  253. if (gif_palette(d, n, pos, lct_entries, lpal))
  254. return IMG_ERR_CORRUPT;
  255. pos += lct_entries * 3u;
  256. } else {
  257. lct_entries = gent;
  258. for (i = 0; i < 256; i++) {
  259. lpal[i][0] = gpal[i][0];
  260. lpal[i][1] = gpal[i][1];
  261. lpal[i][2] = gpal[i][2];
  262. }
  263. }
  264. (void)lct_entries;
  265. if (pos >= n)
  266. return IMG_ERR_CORRUPT;
  267. min_code = d[pos++];
  268. if (min_code < 2 || min_code > 8)
  269. return IMG_ERR_UNSUPPORTED;
  270. rcode = img_alloc(m, w, h, IMG_FMT_GIF, transparent, out);
  271. if (rcode)
  272. return rcode;
  273. image_end = img_mem_mark(m);
  274. if (gent && bg < gent) {
  275. for (i = 0; i < w * h; i++)
  276. out->px[i] = img_rgb565(gpal[bg][0], gpal[bg][1], gpal[bg][2]);
  277. } else {
  278. for (i = 0; i < w * h; i++)
  279. out->px[i] = 0;
  280. }
  281. if (out->alpha)
  282. for (i = 0; i < w * h; i++)
  283. out->alpha[i] = 255;
  284. rd.d = d;
  285. rd.n = n;
  286. rd.pos = pos;
  287. rd.blk_left = 0;
  288. z.r = &rd;
  289. z.bitbuf = 0;
  290. z.bitcnt = 0;
  291. total_pixels = fw * fh;
  292. {
  293. int *prefix;
  294. unsigned char *suffix, *stack;
  295. int clear = 1 << min_code;
  296. int end = clear + 1;
  297. int avail = end + 1;
  298. int code_size = (int)min_code + 1;
  299. int prev = -1;
  300. int interlaced = (fpacked & 0x40) != 0;
  301. prefix = (int *)img_mem_alloc(m, 4096 * sizeof(int), 16);
  302. suffix = (unsigned char *)img_mem_alloc(m, 4096, 16);
  303. stack = (unsigned char *)img_mem_alloc(m, 4096, 16);
  304. if (!prefix || !suffix || !stack) {
  305. img_mem_rewind(m, mark);
  306. return IMG_ERR_NOMEM;
  307. }
  308. for (i = 0; i < (unsigned int)clear; i++) {
  309. prefix[i] = -1;
  310. suffix[i] = (unsigned char)i;
  311. }
  312. for (;;) {
  313. int code;
  314. int stack_len = 0;
  315. unsigned int first;
  316. int cur;
  317. if (lzw_code(&z, code_size, &code)) {
  318. if (done >= total_pixels)
  319. break;
  320. img_mem_rewind(m, mark);
  321. return IMG_ERR_CORRUPT;
  322. }
  323. if (code == clear) {
  324. avail = end + 1;
  325. code_size = (int)min_code + 1;
  326. prev = -1;
  327. continue;
  328. }
  329. if (code == end)
  330. break;
  331. if (prev < 0) {
  332. if (code < 0 || code >= clear) {
  333. img_mem_rewind(m, mark);
  334. return IMG_ERR_CORRUPT;
  335. }
  336. first = (unsigned int)code;
  337. if (done < total_pixels) {
  338. unsigned int idx = (unsigned int)code;
  339. unsigned int fr = done / fw;
  340. unsigned int oy = top +
  341. (interlaced ? gif_scan_row(fh, fr) : fr);
  342. gif_put(out, left + (done % fw), oy,
  343. lpal[idx][0], lpal[idx][1],
  344. lpal[idx][2],
  345. (transparent && idx == trans_index) ? 0 : 255);
  346. done++;
  347. }
  348. prev = code;
  349. continue;
  350. }
  351. cur = code;
  352. if (code >= avail) {
  353. if (code != avail) {
  354. img_mem_rewind(m, mark);
  355. return IMG_ERR_CORRUPT;
  356. }
  357. stack[stack_len++] = (unsigned char)suffix[prev];
  358. cur = prev;
  359. }
  360. while (cur >= 0 && cur < avail && stack_len < 4096) {
  361. stack[stack_len++] = suffix[cur];
  362. cur = prefix[cur];
  363. }
  364. first = stack[stack_len - 1];
  365. if (avail < 4096) {
  366. prefix[avail] = prev;
  367. suffix[avail] = (unsigned char)first;
  368. avail++;
  369. if (avail == (1 << code_size) && code_size < 12)
  370. code_size++;
  371. }
  372. /* The stacked string was pushed in reverse order. */
  373. while (stack_len > 0) {
  374. unsigned int idx = stack[--stack_len];
  375. unsigned int fr, ox, oy;
  376. if (done >= total_pixels)
  377. break;
  378. fr = done / fw;
  379. ox = left + (done % fw);
  380. oy = top + (interlaced ? gif_scan_row(fh, fr) : fr);
  381. gif_put(out, ox, oy, lpal[idx][0], lpal[idx][1],
  382. lpal[idx][2],
  383. (transparent && idx == trans_index) ? 0 : 255);
  384. done++;
  385. }
  386. prev = code;
  387. if (done >= total_pixels)
  388. break;
  389. }
  390. }
  391. if (done < total_pixels) {
  392. img_mem_rewind(m, mark);
  393. return IMG_ERR_CORRUPT;
  394. }
  395. img_mem_rewind(m, image_end);
  396. return 0;
  397. }