sys/src/cmd/jpg/readtif.c

   1 /*
   2 * code/documentation:
   3 * http://partners.adobe.com/public/developer/en/tiff/TIFF6.pdf
   4 * http://www.fileformat.info/format/tiff/egff.htm
   5 * http://www.fileformat.info/mirror/egff/ch09_05.htm
   6 * http://www.itu.int/rec/T-REC-T.4-199904-S/en
   7 * http://www.itu.int/rec/T-REC-T.6-198811-I/en
   8 *
   9 * many thanks to paul bourke for a simple description of tiff:
  10 * http://paulbourke.net/dataformats/tiff/
  11 *
  12 * copy-pasted fax codes and lzw help:
  13 * http://www.remotesensing.org/libtiff/
  14 */
  15 #include <u.h>
  16 #include <libc.h>
  17 #include <bio.h>
  18 #include <draw.h>
  19 #include "imagefile.h"
  20
  21 enum {
  22         II = 0x4949, /* little-endian */
  23         MM = 0x4d4d, /* big-endian */
  24         TIF = 0x002a /* tiff magic number */
  25 };
  26
  27 enum {
  28         Byte = 1,
  29         Short = 3,
  30         Long = 4
  31 };
  32
  33 enum {
  34         Width = 0x0100,
  35         Length = 0x0101,
  36         Bits = 0x0102,
  37
  38         Compression = 0x0103,
  39         Nocomp = 0x0001,
  40         Huffman = 0x0002,
  41         T4enc = 0x0003,
  42         T6enc = 0x0004,
  43         Lzwenc = 0x0005,
  44         Packbits = 0x8005,
  45
  46         Photometric = 0x0106,
  47         Whitezero = 0x0000,
  48         Blackzero = 0x0001,
  49         Rgb = 0x0002,
  50         Palette = 0x0003,
  51
  52         Fill = 0x010a,
  53         Strips = 0x0111,
  54         Orientation = 0x0112,
  55         Samples = 0x0115,
  56         Rows = 0x0116,
  57         Counts = 0x0117,
  58         Planar = 0x011c,
  59         T4opts = 0x0124,
  60         T6opts = 0x0125,
  61         Predictor = 0x13d,
  62         Color = 0x0140
  63 };
  64
  65 enum {
  66         Nfaxcodes = 10,
  67         Nfaxtab = 105
  68 };
  69
  70 enum {
  71         Clrcode = 256,
  72         Eoicode = 257,
  73         Tabsz = 1<<12
  74 };
  75
  76 typedef struct Tab Tab;
  77 typedef struct Fax Fax;
  78 typedef struct Code Code;
  79 typedef struct Lzw Lzw;
  80 typedef struct Fld Fld;
  81 typedef struct Tif Tif;
  82
  83 struct Tab {
  84         int len;
  85         int code;
  86         int run; /* run length */
  87 };
  88
  89 struct Fax {
  90         ulong n;
  91         int m;
  92         int st; /* state */
  93         Tab *tab[2];
  94         int ntab; /* position in tab */
  95         Tab *eol;
  96         int eolfill;
  97         int (*getbit)(Fax *);
  98         ulong *l1;
  99         ulong *l2;
 100         ulong nl;
 101         uchar *data;
 102         ulong next; /* next strip offset in data */
 103 };
 104
 105 struct Code {
 106         uchar val;
 107         Code *next;
 108 };
 109
 110 struct Lzw {
 111         Code tab[Tabsz];
 112         int ntab;
 113         int len; /* code length */
 114         ulong n;
 115         int m;
 116         uchar *data;
 117         ulong next; /* next strip offset in data */
 118         /* remaining allocated codes */
 119         Code *first;
 120         Code *last;
 121 };
 122
 123 struct Fld {
 124         uint tag;
 125         uint typ;
 126         ulong cnt;
 127         ulong off; /* value offset */
 128         ulong *val;
 129         ulong nval;
 130 };
 131
 132 struct Tif {
 133         Biobuf *fd;
 134         uint end; /* endianness */
 135         uchar tmp[4];
 136         uchar *buf;
 137         ulong nbuf;
 138         int eof; /* reached end of image */
 139         ulong n; /* offset in buf array */
 140         ulong off;
 141         uint nfld;
 142         Fld *fld;
 143         ulong (*byte2)(uchar *);
 144         ulong (*byte4)(uchar *);
 145
 146         /* field data */
 147         ulong dx;
 148         ulong dy;
 149         ulong depth;
 150         ulong comp;
 151         uchar *(*uncompress)(Tif *);
 152         ulong orientation;
 153         ulong photo;
 154         int (*decode)(Tif *, Rawimage *, uchar *);
 155         ulong fill;
 156         ulong *strips;
 157         ulong nstrips;
 158         ulong samples;
 159         ulong rows;
 160         ulong *counts;
 161         ulong ncounts;
 162         ulong planar;
 163         ulong *color; /* color map */
 164         ulong ncolor;
 165         ulong t4;
 166         ulong t6;
 167         ulong predictor;
 168
 169         /* image data */
 170         uchar *data;
 171         ulong ndata;
 172 };
 173
 174 /*
 175 * imported from libdraw/arith.c to permit
 176 * extern log2 function
 177 */
 178 static int log2[] = {
 179         -1, 0, 1, -1, 2, -1, -1, -1, 3,
 180         -1, -1, -1, -1, -1, -1, -1, 4,
 181         -1, -1, -1, -1, -1, -1, -1, 4 /* BUG */,
 182         -1, -1, -1, -1, -1, -1, -1, 5
 183 };
 184
 185 static Tab faxwhite[Nfaxtab] = {
 186         {4, 0x7, 2}, /* 0111 */
 187         {4, 0x8, 3}, /* 1000 */
 188         {4, 0xb, 4}, /* 1011 */
 189         {4, 0xc, 5}, /* 1100 */
 190         {4, 0xe, 6}, /* 1110 */
 191         {4, 0xf, 7}, /* 1111 */
 192         {5, 0x12, 128}, /* 1001 0 */
 193         {5, 0x13, 8}, /* 1001 1 */
 194         {5, 0x14, 9}, /* 1010 0 */
 195         {5, 0x1b, 64}, /* 1101 1 */
 196         {5, 0x7, 10}, /* 0011 1 */
 197         {5, 0x8, 11}, /* 0100 0 */
 198         {6, 0x17, 192}, /* 0101 11 */
 199         {6, 0x18, 1664}, /* 0110 00 */
 200         {6, 0x2a, 16}, /* 1010 10 */
 201         {6, 0x2b, 17}, /* 1010 11 */
 202         {6, 0x3, 13}, /* 0000 11 */
 203         {6, 0x34, 14}, /* 1101 00 */
 204         {6, 0x35, 15}, /* 1101 01 */
 205         {6, 0x7, 1}, /* 0001 11 */
 206         {6, 0x8, 12}, /* 0010 00 */
 207         {7, 0x13, 26}, /* 0010 011 */
 208         {7, 0x17, 21}, /* 0010 111 */
 209         {7, 0x18, 28}, /* 0011 000 */
 210         {7, 0x24, 27}, /* 0100 100 */
 211         {7, 0x27, 18}, /* 0100 111 */
 212         {7, 0x28, 24}, /* 0101 000 */
 213         {7, 0x2b, 25}, /* 0101 011 */
 214         {7, 0x3, 22}, /* 0000 011 */
 215         {7, 0x37, 256}, /* 0110 111 */
 216         {7, 0x4, 23}, /* 0000 100 */
 217         {7, 0x8, 20}, /* 0001 000 */
 218         {7, 0xc, 19}, /* 0001 100 */
 219         {8, 0x12, 33}, /* 0001 0010 */
 220         {8, 0x13, 34}, /* 0001 0011 */
 221         {8, 0x14, 35}, /* 0001 0100 */
 222         {8, 0x15, 36}, /* 0001 0101 */
 223         {8, 0x16, 37}, /* 0001 0110 */
 224         {8, 0x17, 38}, /* 0001 0111 */
 225         {8, 0x1a, 31}, /* 0001 1010 */
 226         {8, 0x1b, 32}, /* 0001 1011 */
 227         {8, 0x2, 29}, /* 0000 0010 */
 228         {8, 0x24, 53}, /* 0010 0100 */
 229         {8, 0x25, 54}, /* 0010 0101 */
 230         {8, 0x28, 39}, /* 0010 1000 */
 231         {8, 0x29, 40}, /* 0010 1001 */
 232         {8, 0x2a, 41}, /* 0010 1010 */
 233         {8, 0x2b, 42}, /* 0010 1011 */
 234         {8, 0x2c, 43}, /* 0010 1100 */
 235         {8, 0x2d, 44}, /* 0010 1101 */
 236         {8, 0x3, 30}, /* 0000 0011 */
 237         {8, 0x32, 61}, /* 0011 0010 */
 238         {8, 0x33, 62}, /* 0011 0011 */
 239         {8, 0x34, 63}, /* 0011 0100 */
 240         {8, 0x35, 0}, /* 0011 0101 */
 241         {8, 0x36, 320}, /* 0011 0110 */
 242         {8, 0x37, 384}, /* 0011 0111 */
 243         {8, 0x4, 45}, /* 0000 0100 */
 244         {8, 0x4a, 59}, /* 0100 1010 */
 245         {8, 0x4b, 60}, /* 0100 1011 */
 246         {8, 0x5, 46}, /* 0000 0101 */
 247         {8, 0x52, 49}, /* 0101 0010 */
 248         {8, 0x53, 50}, /* 0101 0011 */
 249         {8, 0x54, 51}, /* 0101 0100 */
 250         {8, 0x55, 52}, /* 0101 0101 */
 251         {8, 0x58, 55}, /* 0101 1000 */
 252         {8, 0x59, 56}, /* 0101 1001 */
 253         {8, 0x5a, 57}, /* 0101 1010 */
 254         {8, 0x5b, 58}, /* 0101 1011 */
 255         {8, 0x64, 448}, /* 0110 0100 */
 256         {8, 0x65, 512}, /* 0110 0101 */
 257         {8, 0x67, 640}, /* 0110 0111 */
 258         {8, 0x68, 576}, /* 0110 1000 */
 259         {8, 0xa, 47}, /* 0000 1010 */
 260         {8, 0xb, 48}, /* 0000 1011 */
 261         {9, 0x98, 1472}, /* 0100 1100 0 */
 262         {9, 0x99, 1536}, /* 0100 1100 1 */
 263         {9, 0x9a, 1600}, /* 0100 1101 0 */
 264         {9, 0x9b, 1728}, /* 0100 1101 1 */
 265         {9, 0xcc, 704}, /* 0110 0110 0 */
 266         {9, 0xcd, 768}, /* 0110 0110 1 */
 267         {9, 0xd2, 832}, /* 0110 1001 0 */
 268         {9, 0xd3, 896}, /* 0110 1001 1 */
 269         {9, 0xd4, 960}, /* 0110 1010 0 */
 270         {9, 0xd5, 1024}, /* 0110 1010 1 */
 271         {9, 0xd6, 1088}, /* 0110 1011 0 */
 272         {9, 0xd7, 1152}, /* 0110 1011 1 */
 273         {9, 0xd8, 1216}, /* 0110 1100 0 */
 274         {9, 0xd9, 1280}, /* 0110 1100 1 */
 275         {9, 0xda, 1344}, /* 0110 1101 0 */
 276         {9, 0xdb, 1408}, /* 0110 1101 1 */
 277         {11, 0x8, 1792}, /* 0000 0001 000 */
 278         {11, 0xc, 1856}, /* 0000 0001 100 */
 279         {11, 0xd, 1920}, /* 0000 0001 101 */
 280         {12, 0x1, -1}, /* 0000 0000 0001 */
 281         {12, 0x12, 1984}, /* 0000 0001 0010 */
 282         {12, 0x13, 2048}, /* 0000 0001 0011 */
 283         {12, 0x14, 2112}, /* 0000 0001 0100 */
 284         {12, 0x15, 2176}, /* 0000 0001 0101 */
 285         {12, 0x16, 2240}, /* 0000 0001 0110 */
 286         {12, 0x17, 2304}, /* 0000 0001 0111 */
 287         {12, 0x1c, 2368}, /* 0000 0001 1100 */
 288         {12, 0x1d, 2432}, /* 0000 0001 1101 */
 289         {12, 0x1e, 2496}, /* 0000 0001 1110 */
 290         {12, 0x1f, 2560} /* 0000 0001 1111 */
 291 };
 292
 293 static Tab faxblack[Nfaxtab] = {
 294         {2, 0x2, 3}, /* 10 */
 295         {2, 0x3, 2}, /* 11 */
 296         {3, 0x2, 1}, /* 010 */
 297         {3, 0x3, 4}, /* 011 */
 298         {4, 0x2, 6}, /* 0010 */
 299         {4, 0x3, 5}, /* 0011 */
 300         {5, 0x3, 7}, /* 0001 1 */
 301         {6, 0x4, 9}, /* 0001 00 */
 302         {6, 0x5, 8}, /* 0001 01 */
 303         {7, 0x4, 10}, /* 0000 100 */
 304         {7, 0x5, 11}, /* 0000 101 */
 305         {7, 0x7, 12}, /* 0000 111 */
 306         {8, 0x4, 13}, /* 0000 0100 */
 307         {8, 0x7, 14}, /* 0000 0111 */
 308         {9, 0x18, 15}, /* 0000 1100 0 */
 309         {10, 0x17, 16}, /* 0000 0101 11 */
 310         {10, 0x18, 17}, /* 0000 0110 00 */
 311         {10, 0x37, 0}, /* 0000 1101 11 */
 312         {10, 0x8, 18}, /* 0000 0010 00 */
 313         {10, 0xf, 64}, /* 0000 0011 11 */
 314         {11, 0x17, 24}, /* 0000 0010 111 */
 315         {11, 0x18, 25}, /* 0000 0011 000 */
 316         {11, 0x28, 23}, /* 0000 0101 000 */
 317         {11, 0x37, 22}, /* 0000 0110 111 */
 318         {11, 0x67, 19}, /* 0000 1100 111 */
 319         {11, 0x68, 20}, /* 0000 1101 000 */
 320         {11, 0x6c, 21}, /* 0000 1101 100 */
 321         {11, 0x8, 1792}, /* 0000 0001 000 */
 322         {11, 0xc, 1856}, /* 0000 0001 100 */
 323         {11, 0xd, 1920}, /* 0000 0001 101 */
 324         {12, 0x1, -1}, /* 0000 0000 0001 */
 325         {12, 0x12, 1984}, /* 0000 0001 0010 */
 326         {12, 0x13, 2048}, /* 0000 0001 0011 */
 327         {12, 0x14, 2112}, /* 0000 0001 0100 */
 328         {12, 0x15, 2176}, /* 0000 0001 0101 */
 329         {12, 0x16, 2240}, /* 0000 0001 0110 */
 330         {12, 0x17, 2304}, /* 0000 0001 0111 */
 331         {12, 0x1c, 2368}, /* 0000 0001 1100 */
 332         {12, 0x1d, 2432}, /* 0000 0001 1101 */
 333         {12, 0x1e, 2496}, /* 0000 0001 1110 */
 334         {12, 0x1f, 2560}, /* 0000 0001 1111 */
 335         {12, 0x24, 52}, /* 0000 0010 0100 */
 336         {12, 0x27, 55}, /* 0000 0010 0111 */
 337         {12, 0x28, 56}, /* 0000 0010 1000 */
 338         {12, 0x2b, 59}, /* 0000 0010 1011 */
 339         {12, 0x2c, 60}, /* 0000 0010 1100 */
 340         {12, 0x33, 320}, /* 0000 0011 0011 */
 341         {12, 0x34, 384}, /* 0000 0011 0100 */
 342         {12, 0x35, 448}, /* 0000 0011 0101 */
 343         {12, 0x37, 53}, /* 0000 0011 0111 */
 344         {12, 0x38, 54}, /* 0000 0011 1000 */
 345         {12, 0x52, 50}, /* 0000 0101 0010 */
 346         {12, 0x53, 51}, /* 0000 0101 0011 */
 347         {12, 0x54, 44}, /* 0000 0101 0100 */
 348         {12, 0x55, 45}, /* 0000 0101 0101 */
 349         {12, 0x56, 46}, /* 0000 0101 0110 */
 350         {12, 0x57, 47}, /* 0000 0101 0111 */
 351         {12, 0x58, 57}, /* 0000 0101 1000 */
 352         {12, 0x59, 58}, /* 0000 0101 1001 */
 353         {12, 0x5a, 61}, /* 0000 0101 1010 */
 354         {12, 0x5b, 256}, /* 0000 0101 1011 */
 355         {12, 0x64, 48}, /* 0000 0110 0100 */
 356         {12, 0x65, 49}, /* 0000 0110 0101 */
 357         {12, 0x66, 62}, /* 0000 0110 0110 */
 358         {12, 0x67, 63}, /* 0000 0110 0111 */
 359         {12, 0x68, 30}, /* 0000 0110 1000 */
 360         {12, 0x69, 31}, /* 0000 0110 1001 */
 361         {12, 0x6a, 32}, /* 0000 0110 1010 */
 362         {12, 0x6b, 33}, /* 0000 0110 1011 */
 363         {12, 0x6c, 40}, /* 0000 0110 1100 */
 364         {12, 0x6d, 41}, /* 0000 0110 1101 */
 365         {12, 0xc8, 128}, /* 0000 1100 1000 */
 366         {12, 0xc9, 192}, /* 0000 1100 1001 */
 367         {12, 0xca, 26}, /* 0000 1100 1010 */
 368         {12, 0xcb, 27}, /* 0000 1100 1011 */
 369         {12, 0xcc, 28}, /* 0000 1100 1100 */
 370         {12, 0xcd, 29}, /* 0000 1100 1101 */
 371         {12, 0xd2, 34}, /* 0000 1101 0010 */
 372         {12, 0xd3, 35}, /* 0000 1101 0011 */
 373         {12, 0xd4, 36}, /* 0000 1101 0100 */
 374         {12, 0xd5, 37}, /* 0000 1101 0101 */
 375         {12, 0xd6, 38}, /* 0000 1101 0110 */
 376         {12, 0xd7, 39}, /* 0000 1101 0111 */
 377         {12, 0xda, 42}, /* 0000 1101 1010 */
 378         {12, 0xdb, 43}, /* 0000 1101 1011 */
 379         {13, 0x4a, 640}, /* 0000 0010 0101 0 */
 380         {13, 0x4b, 704}, /* 0000 0010 0101 1 */
 381         {13, 0x4c, 768}, /* 0000 0010 0110 0 */
 382         {13, 0x4d, 832}, /* 0000 0010 0110 1 */
 383         {13, 0x52, 1280}, /* 0000 0010 1001 0 */
 384         {13, 0x53, 1344}, /* 0000 0010 1001 1 */
 385         {13, 0x54, 1408}, /* 0000 0010 1010 0 */
 386         {13, 0x55, 1472}, /* 0000 0010 1010 1 */
 387         {13, 0x5a, 1536}, /* 0000 0010 1101 0 */
 388         {13, 0x5b, 1600}, /* 0000 0010 1101 1 */
 389         {13, 0x64, 1664}, /* 0000 0011 0010 0 */
 390         {13, 0x65, 1728}, /* 0000 0011 0010 1 */
 391         {13, 0x6c, 512}, /* 0000 0011 0110 0 */
 392         {13, 0x6d, 576}, /* 0000 0011 0110 1 */
 393         {13, 0x72, 896}, /* 0000 0011 1001 0 */
 394         {13, 0x73, 960}, /* 0000 0011 1001 1 */
 395         {13, 0x74, 1024}, /* 0000 0011 1010 0 */
 396         {13, 0x75, 1088}, /* 0000 0011 1010 1 */
 397         {13, 0x76, 1152}, /* 0000 0011 1011 0 */
 398         {13, 0x77, 1216} /* 0000 0011 1011 1 */
 399 };
 400
 401 static Tab faxcodes[Nfaxcodes] = {
 402         {1, 0x1, 0}, /* 1 */
 403         {3, 0x1, 0}, /* 001 */
 404         {3, 0x2, 0}, /* 010 */
 405         {3, 0x3, 0}, /* 011 */
 406         {4, 0x1, 0}, /* 0001 */
 407         {6, 0x2, 0}, /* 0000 10 */
 408         {6, 0x3, 0}, /* 0000 11 */
 409         {7, 0x2, 0}, /* 0000 010 */
 410         {7, 0x3, 0}, /* 0000 011 */
 411         {12, 0x1, -1} /* 0000 0000 0001 */
 412 };
 413
 414 static int typesizes[] = {0, 1, 0, 2, 4};
 415 static int vcodeval[] = {0, 0, 0, 1, 0, 0, 2, 3};
 416
 417 static ulong byte2le(uchar *);
 418 static ulong byte4le(uchar *);
 419 static ulong byte2be(uchar *);
 420 static ulong byte4be(uchar *);
 421 static void readdata(Tif *, ulong);
 422 static void readnbytes(Tif *, ulong);
 423 static ulong readbyte(Tif *);
 424 static ulong readshort(Tif *);
 425 static ulong readlong(Tif *);
 426 static int gototif(Tif *, ulong);
 427 static int readheader(Tif *);
 428 static uchar *nocomp(Tif *);
 429 static int getbit1(Fax *);
 430 static int getbit2(Fax *);
 431 static Tab *findtab(Fax *, int, int, Tab *, int);
 432 static Tab *gettab(Fax *, int);
 433 static Tab *geteol(Fax *);
 434 static int faxfill(Fax *, uchar *, ulong, ulong *, ulong *, ulong, int);
 435 static void fillbits(Fax *);
 436 static int faxalloclines(Fax *);
 437 static Tab *getfax1d(Fax *, uchar *, ulong, ulong *, ulong *, ulong);
 438 static Tab *getfax2d(Fax *, uchar *, ulong, ulong *, ulong *, ulong);
 439 static int faxstrip(Tif *, Fax *, uchar *, ulong, ulong, ulong *);
 440 static uchar *fax(Tif *);
 441 static void tabinit(Lzw *);
 442 static Code *newcode(Lzw *, Code *);
 443 static void listadd(Lzw *, Code *);
 444 static Code *tabadd(Lzw *, Code *, Code *);
 445 static int getcode(Lzw *);
 446 static int wstr(uchar *, ulong, ulong *, Code *, long *);
 447 static void predict1(Tif *, uchar *);
 448 static void predict8(Tif *, uchar *);
 449 static int lzwstrip(Lzw *, uchar *, ulong, ulong *, long);
 450 static uchar *lzw(Tif *);
 451 static uchar *packbits(Tif *);
 452 static int faxdecode(Tif *, Rawimage *, uchar *);
 453 static int greydecode(Tif *, Rawimage *, uchar *);
 454 static int rgbdecode(Tif *, Rawimage *, uchar *);
 455 static int paldecode(Tif *, Rawimage *, uchar *);
 456 static int parsefield(Tif *, Fld *);
 457 static int readfield(Tif *, Fld *);
 458 static int checkfields(Tif *);
 459 static int readstrips(Tif *);
 460 static Rawimage *decode(Tif *);
 461 static void freefields(Tif *);
 462 static Rawimage *readslave(Tif *);
 463
 464 static ulong
 465 byte2le(uchar *buf)
 466 {
 467         return (buf[1] << 8) | buf[0];
 468 }
 469
 470 static ulong
 471 byte4le(uchar *buf)
 472 {
 473         return (byte2le(buf+2) << 16) | byte2le(buf);
 474 }
 475
 476 static ulong
 477 byte2be(uchar *buf)
 478 {
 479         return (buf[0] << 8) | buf[1];
 480 }
 481
 482 static ulong
 483 byte4be(uchar *buf)
 484 {
 485         return (byte2be(buf) << 16) | byte2be(buf+2);
 486 }
 487
 488 static void
 489 readdata(Tif *t, ulong offset)
 490 {
 491         long n, m;
 492         ulong size;
 493
 494         if(offset < t->nbuf)
 495                 offset = t->nbuf;
 496         m = offset + 4096 - t->nbuf;
 497         size = (m + t->nbuf) * sizeof *t->buf;
 498         if(t->buf == nil) {
 499                 if((t->buf = malloc(size)) == nil)
 500                         sysfatal("malloc: %r");
 501         } else {
 502                 if((t->buf = realloc(t->buf, size)) == nil)
 503                         sysfatal("realloc: %r");
 504         }
 505         if((n = Bread(t->fd, t->buf+t->nbuf, m)) < 0)
 506                 sysfatal("Bread: %r");
 507         if(n != m)
 508                 t->eof = 1;
 509         t->nbuf += n;
 510 }
 511
 512 static void
 513 readnbytes(Tif *t, ulong n)
 514 {
 515         if(n <= 0 || n > 4)
 516                 sysfatal("cannot read %lud bytes", n);
 517         if(t->n+n > t->nbuf) {
 518                 if(t->eof)
 519                         sysfatal("reached end of file");
 520                 readdata(t, 0);
 521         }
 522         memmove(t->tmp, t->buf+t->n, n);
 523         t->n += n;
 524 }
 525
 526 static ulong
 527 readbyte(Tif *t)
 528 {
 529         readnbytes(t, 1);
 530         return t->tmp[0];
 531 }
 532
 533 static ulong
 534 readshort(Tif *t)
 535 {
 536         readnbytes(t, 2);
 537         return (*t->byte2)(t->tmp);
 538 }
 539
 540 static ulong
 541 readlong(Tif *t)
 542 {
 543         readnbytes(t, 4);
 544         return (*t->byte4)(t->tmp);
 545 }
 546
 547 static int
 548 gototif(Tif *t, ulong n)
 549 {
 550         if(n < 8) {
 551                 werrstr("offset pointing to header");
 552                 return -1;
 553         }
 554         if(n > t->nbuf)
 555                 readdata(t, n);
 556         t->n = n;
 557         return 0;
 558 }
 559
 560 static int
 561 readheader(Tif *t)
 562 {
 563         uint n;
 564
 565         t->end = readshort(t);
 566         switch(t->end) {
 567         case II:
 568                 break;
 569         case MM:
 570                 t->byte2 = byte2be;
 571                 t->byte4 = byte4be;
 572                 break;
 573         default:
 574                 werrstr("illegal byte order: %#.4x", t->end);
 575                 return -1;
 576         }
 577         if((n = readshort(t)) != TIF) {
 578                 werrstr("illegal tiff magic: %#.4x", n);
 579                 return -1;
 580         }
 581         t->off = readlong(t);
 582         return gototif(t, t->off);
 583 }
 584
 585 static uchar *
 586 nocomp(Tif *t)
 587 {
 588         return t->data;
 589 }
 590
 591 static int
 592 getbit1(Fax *f)
 593 {
 594         int bit;
 595
 596         if(f->n >= f->next)
 597                 return -1;
 598         bit = (f->data[f->n] >> f->m) & 0x1;
 599         f->m--;
 600         if(f->m < 0) {
 601                 f->n++;
 602                 f->m = 7;
 603         }
 604         return bit;
 605 }
 606
 607 static int
 608 getbit2(Fax *f)
 609 {
 610         int bit;
 611
 612         if(f->n >= f->next)
 613                 return -1;
 614         bit = (f->data[f->n] >> f->m) & 0x1;
 615         f->m++;
 616         if(f->m >= 8) {
 617                 f->n++;
 618                 f->m = 0;
 619         }
 620         return bit;
 621 }
 622
 623 static Tab *
 624 findtab(Fax *f, int code, int len, Tab *tab, int max)
 625 {
 626         Tab *p;
 627
 628         while(f->ntab < max) {
 629                 p = &tab[f->ntab];
 630                 if(p->len > len)
 631                         break;
 632                 if(p->code == code) {
 633                         f->ntab = 0;
 634                         return p;
 635                 }
 636                 f->ntab++;
 637         }
 638         return nil;
 639 }
 640
 641 static Tab *
 642 gettab(Fax *f, int mode)
 643 {
 644         int i, n, maxlen, bit, code;
 645         Tab *p, *tab;
 646
 647         code = 0;
 648         if(mode) {
 649                 n = Nfaxcodes;
 650                 tab = faxcodes;
 651         } else {
 652                 n = Nfaxtab;
 653                 tab = f->tab[f->st];
 654         }
 655         maxlen = tab[n-1].len;
 656         for(i = 1; i <= maxlen; i++) {
 657                 if((bit = (*f->getbit)(f)) < 0) {
 658                         f->st = -1;
 659                         return nil;
 660                 }
 661                 code = (code << 1) | bit;
 662                 if((p = findtab(f, code, i, tab, n)) != nil)
 663                         return p;
 664         }
 665         werrstr("code not found");
 666         return nil;
 667 }
 668
 669 static Tab *
 670 geteol(Fax *f)
 671 {
 672         int i, bit;
 673         Tab *p;
 674
 675         if(f->eol == nil) {
 676                 if(f->eolfill) {
 677                         for(i = 0; i < 4; i++) {
 678                                 if((*f->getbit)(f) < 0) {
 679                                         f->st = -1;
 680                                         return nil;
 681                                 }
 682                         }
 683                 }
 684                 if((p = gettab(f, 0)) == nil || p->run >= 0) {
 685                         werrstr("first eol");
 686                         return nil;
 687                 }
 688                 f->eol = p;
 689                 return p;
 690         }
 691         for(i = 0; (bit = (*f->getbit)(f)) == 0; i++)
 692                 ;
 693         if(bit < 0) {
 694                 f->st = -1;
 695                 return nil;
 696         }
 697         if(i < 11) {
 698                 werrstr("eol");
 699                 return nil;
 700         }
 701         return f->eol;
 702 }
 703
 704 static int
 705 faxfill(Fax *f, uchar *data, ulong size, ulong *i, ulong *x, ulong dx,
 706         int n)
 707 {
 708         if((*x += n) > dx) {
 709                 werrstr("fax row overflow");
 710                 return -1;
 711         }
 712         if((*i += n) > size)
 713                 return -1;
 714         if(f->st != 0)
 715                 memset(data+*i-n, f->st, n);
 716         return 0;
 717 }
 718
 719 static void
 720 fillbits(Fax *f)
 721 {
 722         if(f->getbit == getbit1) {
 723                 if(f->m != 7) {
 724                         f->n++;
 725                         f->m = 7;
 726                 }
 727         } else {
 728                 if(f->m != 0) {
 729                         f->n++;
 730                         f->m = 0;
 731                 }
 732         }
 733 }
 734
 735 static int
 736 faxalloclines(Fax *f)
 737 {
 738         f->nl *= 2;
 739         f->l1 = realloc(f->l1, f->nl*sizeof *f->l1);
 740         if(f->l1 == nil)
 741                 return -1;
 742         f->l2 = realloc(f->l2, f->nl*sizeof *f->l2);
 743         if(f->l2 == nil) {
 744                 free(f->l1);
 745                 return -1;
 746         }
 747         return 0;
 748 }
 749
 750 static Tab *
 751 getfax1d(Fax *f, uchar *data, ulong size, ulong *i, ulong *x,
 752         ulong dx)
 753 {
 754         int j, n;
 755         Tab *p;
 756
 757         for(j = n = 0; *x < dx;) {
 758                 if((p = gettab(f, 0)) == nil)
 759                         return nil;
 760                 if((n = p->run) < 0) {
 761                         f->l1[j] = dx;
 762                         return f->eol;
 763                 }
 764                 if(faxfill(f, data, size, i, x, dx, n) < 0)
 765                         return nil;
 766                 if(n < 64) {
 767                         f->l1[j++] = *x;
 768                         f->st ^= 1;
 769                 }
 770                 if(j >= f->nl)
 771                         faxalloclines(f);
 772         }
 773         if(n >= 64) {
 774                 f->l1[j] = dx;
 775                 if((p = gettab(f, 0)) == nil)
 776                         return nil;
 777                 if((n = p->run) < 0)
 778                         return f->eol;
 779                 if(n != 0) {
 780                         werrstr("no terminating code");
 781                         return nil;
 782                 }
 783         }
 784         return nil;
 785 }
 786
 787 static Tab *
 788 getfax2d(Fax *f, uchar *data, ulong size, ulong *i, ulong *x,
 789         ulong dx)
 790 {
 791         int j, k, n, code, len, v;
 792         long a0, a1, b1, b2;
 793         Tab *p;
 794
 795         a0 = -1;
 796         for(j = 0; *x < dx;) {
 797                 for(k = 0;; k++) {
 798                         b1 = f->l1[k];
 799                         if(b1 > a0 && f->st == k%2)
 800                                 break;
 801                         if(b1 >= dx)
 802                                 break;
 803                 }
 804                 if((b2 = b1) < dx)
 805                         b2 = f->l1[k+1];
 806                 if((p = gettab(f, 1)) == nil)
 807                         return nil;
 808                 /* early eofb */
 809                 if(p->run < 0) {
 810                         f->st = -1;
 811                         return nil;
 812                 }
 813                 if(j+1 >= f->nl)
 814                         faxalloclines(f);
 815                 len = p->len;
 816                 code = p->code;
 817                 if(code == 1 && len == 3) {
 818                         /* horizontal */
 819                         for(k = 0; k < 2;) {
 820                                 if((p = gettab(f, 0)) == nil)
 821                                         return nil;
 822                                 if((n = p->run) < 0) {
 823                                         werrstr("2d eol");
 824                                         return nil;
 825                                 }
 826                                 if(faxfill(f, data, size, i, x,
 827                                         dx, n) < 0)
 828                                         return nil;
 829                                 if(n < 64) {
 830                                         f->l2[j++] = *x;
 831                                         f->st ^= 1;
 832                                         k++;
 833                                 }
 834                         }
 835                 } else if(code == 1 && len == 4) {
 836                         /* pass */
 837                         n = b2 - *x;
 838                         if(faxfill(f, data, size, i, x, dx, n) < 0)
 839                                 return nil;
 840                         if(*x == dx)
 841                                 f->l2[j++] = *x;
 842                 } else {
 843                         /* vertical */
 844                         switch(code) {
 845                         case 1:
 846                         case 2:
 847                                 v = -vcodeval[len];
 848                                 break;
 849                         case 3:
 850                                 v = vcodeval[len];
 851                                 break;
 852                         default:
 853                                 werrstr("mode");
 854                                 return nil;
 855                         }
 856                         a1 = b1 + v;
 857                         n = a1 - *x;
 858                         if(faxfill(f, data, size, i, x, dx, n) < 0)
 859                                 return nil;
 860                         f->l2[j++] = *x;
 861                         f->st ^= 1;
 862                 }
 863                 a0 = *x;
 864         }
 865         memmove(f->l1, f->l2, j*sizeof *f->l1);
 866         return nil;
 867 }
 868
 869 static int
 870 faxstrip(Tif *t, Fax *f, uchar *data, ulong size, ulong rows,
 871         ulong *i)
 872 {
 873         int d1;
 874         ulong x, y;
 875         Tab *p;
 876
 877         d1 = t->comp != T6enc;
 878         p = nil;
 879         for(x = y = 0; x < t->dx || y < rows;) {
 880                 f->st = 0;
 881                 if(t->comp == T4enc) {
 882                         if(p == nil && geteol(f) == nil) {
 883                                 if(f->st >= 0)
 884                                         return -1;
 885                                 break;
 886                         }
 887                         if(y > 0) {
 888                                 *i += t->dx - x;
 889                                 if(*i > size)
 890                                         break;
 891                         }
 892                         if(t->t4 & 1) {
 893                                 d1 = (*f->getbit)(f);
 894                                 if(d1 < 0)
 895                                         break;
 896                         }
 897                 }
 898                 x = 0;
 899                 y++;
 900                 if(d1) {
 901                         p = getfax1d(f, data, size, i,
 902                                 &x, t->dx);
 903                 } else {
 904                         p = getfax2d(f, data, size, i,
 905                                 &x, t->dx);
 906                 }
 907                 if(t->comp == Huffman)
 908                         fillbits(f);
 909                 if(p == nil && x != t->dx) {
 910                         if(f->st >= 0)
 911                                 return -1;
 912                         if(x > t->dx)
 913                                 return -1;
 914                         break;
 915                 }
 916         }
 917         if(*i > size) {
 918                 werrstr("fax data overflow");
 919                 return -1;
 920         }
 921         return 0;
 922 }
 923
 924 /* i've encountered t4 images that did not have rtcs */
 925 static uchar *
 926 fax(Tif *t)
 927 {
 928         int m;
 929         ulong i, j, datasz, r, dy;
 930         uchar *data;
 931         Fax f;
 932
 933         datasz = t->dx * t->dy * sizeof *data;
 934         data = mallocz(datasz, 1);
 935         f.nl = t->dx + 1;
 936         f.l1 = mallocz(f.nl*sizeof *f.l1, 1);
 937         f.l2 = mallocz(f.nl*sizeof *f.l2, 1);
 938         if(data == nil || f.l1 == nil || f.l2 == nil) {
 939                 free(t->data);
 940                 if(data != nil)
 941                         free(data);
 942                 if(f.l1 != nil)
 943                         free(f.l1);
 944                 if(f.l2 != nil)
 945                         free(f.l2);
 946                 return nil;
 947         }
 948         if(t->fill == 1) {
 949                 f.getbit = getbit1;
 950                 m = 7;
 951         } else {
 952                 f.getbit = getbit2;
 953                 m = 0;
 954         }
 955         f.tab[0] = faxwhite;
 956         f.tab[1] = faxblack;
 957         f.ntab = 0;
 958         f.eol = nil;
 959         if(t->comp == T4enc && t->t4 & (1<<1))
 960                 f.eolfill = 1;
 961         else
 962                 f.eolfill = 0;
 963         f.data = t->data;
 964         for(i = j = 0, dy = t->dy; i < t->nstrips; i++) {
 965                 f.l1[0] = t->dx;
 966                 f.n = t->strips[i];
 967                 f.m = m;
 968                 if(i < t->nstrips-1)
 969                         f.next = t->strips[i+1];
 970                 else
 971                         f.next = t->ndata;
 972                 r = dy < t->rows? dy: t->rows;
 973                 if(faxstrip(t, &f, data, datasz, r, &j) < 0)
 974                         break;
 975                 dy -= t->rows;
 976         }
 977         if(i < t->nstrips) {
 978                 free(data);
 979                 data = nil;
 980         }
 981         free(t->data);
 982         free(f.l1);
 983         free(f.l2);
 984         return data;
 985 }
 986
 987 static void
 988 tabinit(Lzw *l)
 989 {
 990         l->ntab = Eoicode + 1;
 991         l->len = 9;
 992 }
 993
 994 static Code *
 995 newcode(Lzw *l, Code *p)
 996 {
 997         Code *q;
 998
 999         if(p == nil)
1000                 return nil;
1001         if(l->first != nil) {
1002                 q = l->first;
1003                 if((l->first = l->first->next) == nil)
1004                         l->last = nil;
1005         } else if((q = malloc(sizeof *q)) == nil)
1006                 return nil;
1007         q->val = p->val;
1008         q->next = nil;
1009         return q;
1010 }
1011
1012 static void
1013 listadd(Lzw *l, Code *p)
1014 {
1015         if(p == nil)
1016                 return;
1017         if(l->last != nil)
1018                 l->last->next = p;
1019         else
1020                 l->first = l->last = p;
1021         while(l->last->next != nil)
1022                 l->last = l->last->next;
1023 }
1024
1025 static Code *
1026 tabadd(Lzw *l, Code *p, Code *q)
1027 {
1028         Code *r, *s;
1029
1030         r = s = &l->tab[l->ntab];
1031         switch(l->ntab) {
1032         case 510:
1033         case 1022:
1034         case 2046:
1035                 l->len++;
1036                 break;
1037         default:
1038                 break;
1039         }
1040         if(l->ntab++ >= Tabsz-3) {
1041                 werrstr("lzw table full");
1042                 return nil;
1043         }
1044         s->val = p->val;
1045         while((p = p->next) != nil) {
1046                 if(s->next != nil)
1047                         s->next->val = p->val;
1048                 else if((s->next = newcode(l, p)) == nil)
1049                         return nil;
1050                 s = s->next;
1051         }
1052         if(s->next != nil) {
1053                 s->next->val = q->val;
1054                 s = s->next;
1055                 if(s->next != nil) {
1056                         listadd(l, s->next);
1057                         s->next = nil;
1058                 }
1059         } else if((s->next = newcode(l, q)) == nil)
1060                 return nil;
1061         return r;
1062 }
1063
1064 static int
1065 getcode(Lzw *l)
1066 {
1067         int i, c, code;
1068
1069         if(l->n >= l->next) {
1070 eof:
1071                 werrstr("lzw eof");
1072                 return -1;
1073         }
1074         code = 0;
1075         for(i = l->len-1; i >= 0; i--) {
1076                 c = (l->data[l->n] >> l->m) & 0x1;
1077                 code |= c << i;
1078                 l->m--;
1079                 if(l->m < 0) {
1080                         l->m = 7;
1081                         if(++l->n >= l->next && i > 0)
1082                                 goto eof;
1083                 }
1084         }
1085         return code;
1086 }
1087
1088 static int
1089 wstr(uchar *data, ulong size, ulong *i, Code *p, long *striplen)
1090 {
1091         for(; p != nil; p = p->next, ++*i, --*striplen) {
1092                 if(*i >= size || *striplen < 0) {
1093                         werrstr("lzw overflow");
1094                         return -1;
1095                 }
1096                 data[*i] = p->val;
1097         }
1098         return 0;
1099 }
1100
1101 static void
1102 predict1(Tif *t, uchar *data)
1103 {
1104         int bpl, pix, b[8], d, m, n, j;
1105         ulong x, y;
1106
1107         d = t->depth;
1108         bpl = bytesperline(Rect(0, 0, t->dx, t->dy), d);
1109         m = (1 << d) - 1;
1110         n = 8 / d;
1111         for(y = 0; y < t->dy; y++) {
1112                 for(x = 0; x < bpl; x++, data++) {
1113                         pix = *data;
1114                         b[n-1] = (pix >> d*(n-1)) & m;
1115                         if(x > 0)
1116                                 b[n-1] += *(data-1) & m;
1117                         for(j = n-2; j >= 0; j--) {
1118                                 b[j] = (pix >> d*j) & m;
1119                                 b[j] += b[j+1];
1120                         }
1121                         for(j = pix = 0; j < n; j++)
1122                                 pix |= (b[j] & m) << d*j;
1123                         *data = pix;
1124                 }
1125         }
1126 }
1127
1128 static void
1129 predict8(Tif *t, uchar *data)
1130 {
1131         ulong j, s, x, y;
1132
1133         s = t->samples;
1134         for(y = 0; y < t->dy; y++) {
1135                 for(x = 1, data += s; x < t->dx; x++) {
1136                         for(j = 0; j < s; j++, data++)
1137                                 *data += *(data-s);
1138                 }
1139         }
1140 }
1141
1142 static int
1143 lzwstrip(Lzw *l, uchar *data, ulong size, ulong *i, long striplen)
1144 {
1145         int c, oc;
1146         Code *p, *q;
1147
1148         if((c = getcode(l)) != Clrcode) {
1149                 werrstr("clear code");
1150                 return -1;
1151         }
1152         for(oc = -1; c != Eoicode;) {
1153                 if(c < 0)
1154                         return -1;
1155                 if(c == Clrcode) {
1156                         if(oc >= 0)
1157                                 tabinit(l);
1158                         if((c = getcode(l)) == Eoicode)
1159                                 break;
1160                         if(c < 0)
1161                                 return -1;
1162                         if(c >= l->ntab) {
1163                                 werrstr("table overflow");
1164                                 return -1;
1165                         }
1166                         if(wstr(data, size, i, &l->tab[c],
1167                                 &striplen) < 0)
1168                                 return -1;
1169                 } else if(c < l->ntab) {
1170                         p = &l->tab[c];
1171                         if(wstr(data, size, i, p,
1172                                 &striplen) < 0)
1173                                 return -1;
1174                         q = &l->tab[oc];
1175                         if(tabadd(l, q, p) == nil)
1176                                 return -1;
1177                 } else if(c == l->ntab) {
1178                         q = &l->tab[oc];
1179                         if((p = tabadd(l, q, q)) == nil)
1180                                 return -1;
1181                         if(wstr(data, size, i, p,
1182                                 &striplen) < 0)
1183                                 return -1;
1184                 } else {
1185                         werrstr("table overflow");
1186                         return -1;
1187                 }
1188                 if(striplen <= 0)
1189                         break;
1190                 oc = c;
1191                 c = getcode(l);
1192         }
1193         return 0;
1194 }
1195
1196 static uchar *
1197 lzw(Tif *t)
1198 {
1199         ulong i, j, size, r, dy;
1200         long striplen;
1201         uchar *data;
1202         Lzw l;
1203         Code *p, *q;
1204
1205         size = ((t->dx*t->dy*t->depth + 7) / 8) * sizeof *data;
1206         if((data = malloc(size)) == nil) {
1207                 free(t->data);
1208                 return nil;
1209         }
1210         for(i = 0; i < Tabsz; i++) {
1211                 l.tab[i].val = i;
1212                 l.tab[i].next = nil;
1213         }
1214         l.data = t->data;
1215         l.first = l.last = nil;
1216         for(i = j = 0, dy = t->dy; i < t->nstrips; i++) {
1217                 tabinit(&l);
1218                 l.n = t->strips[i];
1219                 l.m = 7;
1220                 if(i < t->nstrips-1)
1221                         l.next = t->strips[i+1];
1222                 else
1223                         l.next = t->ndata;
1224                 r = dy < t->rows? dy: t->rows;
1225                 striplen = (t->dx*r*t->depth + 7) / 8;
1226                 if(lzwstrip(&l, data, size, &j, striplen) < 0)
1227                         break;
1228                 dy -= t->rows;
1229         }
1230         if(i < t->nstrips) {
1231                 free(data);
1232                 data = nil;
1233         }
1234         for(i = 0; i < Tabsz; i++) {
1235                 for(p = l.tab[i].next; (q = p) != nil;) {
1236                         p = p->next;
1237                         free(q);
1238                 }
1239         }
1240         for(p = l.first; (q = p) != nil;) {
1241                 p = p->next;
1242                 free(q);
1243         }
1244         free(t->data);
1245         if(data != nil && t->predictor == 2) {
1246                 if(t->depth < 8)
1247                         predict1(t, data);
1248                 else
1249                         predict8(t, data);
1250         }
1251         return data;
1252 }
1253
1254 static uchar *
1255 packbits(Tif *t)
1256 {
1257         char n;
1258         ulong i, j, k, size;
1259         uchar *data;
1260
1261         size = ((t->dx*t->dy*t->depth + 7) / 8) * sizeof *data;
1262         if((data = malloc(size)) == nil) {
1263                 free(t->data);
1264                 return nil;
1265         }
1266         for(i = 0, j = 0; i < t->ndata;) {
1267                 n = (char)t->data[i++];
1268                 if(n >= 0) {
1269                         k = n + 1;
1270                         if((j += k) > size || (i += k) > t->ndata)
1271                                 break;
1272                         memmove(data+j-k, t->data+i-k, k);
1273                 } else if(n > -128 && n < 0) {
1274                         k = j - n + 1;
1275                         if(k > size || i >= t->ndata)
1276                                 break;
1277                         for(; j < k; j++)
1278                                 data[j] = t->data[i];
1279                         i++;
1280                 }
1281         }
1282         if(i < t->ndata) {
1283                 werrstr("packbits overflow");
1284                 free(data);
1285                 data = nil;
1286         }
1287         free(t->data);
1288         return data;
1289 }
1290
1291 static int
1292 faxdecode(Tif *t, Rawimage *im, uchar *data)
1293 {
1294         ulong n;
1295
1296         for(n = 0; n < im->chanlen; n++) {
1297                 if(t->photo == Whitezero)
1298                         data[n] ^= 1;
1299                 im->chans[0][n] = data[n] * 0xff;
1300         }
1301         return 0;
1302 }
1303
1304 static int
1305 greydecode(Tif *t, Rawimage *im, uchar *data)
1306 {
1307         int pix, pmask, xmask;
1308         ulong i, n, x, y;
1309
1310         pmask = (1 << t->depth) - 1;
1311         xmask = 7 >> log2[t->depth];
1312         for(y = 0, n = 0; y < t->dy; y++) {
1313                 i = y * bytesperline(im->r, t->depth);
1314                 for(x = 0; x < t->dx; x++, n++) {
1315                         if(n >= im->chanlen) {
1316                                 werrstr("grey overflow");
1317                                 return -1;
1318                         }
1319                         pix = (data[i] >> t->depth*((xmask -
1320                                 x) & xmask)) & pmask;
1321                         if(((x + 1) & xmask) == 0)
1322                                 i++;
1323                         if(t->photo == Whitezero)
1324                                 pix ^= pmask;
1325                         pix = (pix * 0xff) / pmask;
1326                         im->chans[0][n] = pix;
1327                 }
1328         }
1329         return 0;
1330 }
1331
1332 static int
1333 rgbdecode(Tif *t, Rawimage *im, uchar *data)
1334 {
1335         ulong i, n, x, y;
1336
1337         for(y = 0, n = 0; y < t->dy; y++) {
1338                 for(x = 0; x < t->dx; x++, n += 3) {
1339                         if(n >= im->chanlen) {
1340                                 werrstr("rgb overflow");
1341                                 return -1;
1342                         }
1343                         i = (y*t->dx + x) * 3;
1344                         im->chans[0][n] = data[i+2];
1345                         im->chans[0][n+1] = data[i+1];
1346                         im->chans[0][n+2] = data[i];
1347                 }
1348         }
1349         return 0;
1350 }
1351
1352 static int
1353 paldecode(Tif *t, Rawimage *im, uchar *data)
1354 {
1355         int pix, pmask, xmask;
1356         ulong i, n, x, y, *r, *g, *b, max;
1357
1358         pmask = (1 << t->depth) - 1;
1359         xmask = 7 >> log2[t->depth];
1360         for(i = 0, max = 1; i < t->ncolor; i++) {
1361                 if(t->color[i] > max)
1362                         max = t->color[i];
1363         }
1364         for(i = 0; i < t->ncolor; i++)
1365                 t->color[i] = (t->color[i] * 0xff) / max;
1366         r = t->color;
1367         g = r + pmask + 1;
1368         b = g + pmask + 1;
1369         for(y = 0, n = 0; y < t->dy; y++) {
1370                 i = y * bytesperline(im->r, t->depth);
1371                 for(x = 0; x < t->dx; x++, n += 3) {
1372                         if(n >= im->chanlen) {
1373                                 werrstr("palette overflow");
1374                                 return -1;
1375                         }
1376                         pix = (data[i] >> t->depth*((xmask -
1377                                 x) & xmask)) & pmask;
1378                         if(((x + 1) & xmask) == 0)
1379                                 i++;
1380                         im->chans[0][n] = b[pix];
1381                         im->chans[0][n+1] = g[pix];
1382                         im->chans[0][n+2] = r[pix];
1383                 }
1384         }
1385         return 0;
1386 }
1387
1388 static int
1389 parsefield(Tif *t, Fld *f)
1390 {
1391         ulong v;
1392
1393         v = f->val[0];
1394         switch(f->tag) {
1395         case Width:
1396                 t->dx = v;
1397                 break;
1398         case Length:
1399                 t->dy = v;
1400                 break;
1401         case Bits:
1402                 t->depth = v;
1403                 if(f->cnt == 3)
1404                         t->depth += f->val[1] + f->val[2];
1405                 break;
1406         case Compression:
1407                 t->comp = v;
1408                 break;
1409         case Photometric:
1410                 t->photo = v;
1411                 switch(t->photo) {
1412                 case Whitezero:
1413                 case Blackzero:
1414                         t->decode = greydecode;
1415                         break;
1416                 case Rgb:
1417                         t->decode = rgbdecode;
1418                         break;
1419                 case Palette:
1420                         t->decode = paldecode;
1421                         break;
1422                 default:
1423                         break;
1424                 }
1425                 break;
1426         case Strips:
1427                 t->strips = f->val;
1428                 t->nstrips = f->cnt;
1429                 break;
1430         case Fill:
1431                 t->fill = v;
1432                 break;
1433         case Orientation:
1434                 t->orientation = v;
1435                 break;
1436         case Samples:
1437                 t->samples = v;
1438                 break;
1439         case Rows:
1440                 t->rows = v;
1441                 break;
1442         case Counts:
1443                 t->counts = f->val;
1444                 t->ncounts = f->cnt;
1445                 break;
1446         case Planar:
1447                 t->planar = v;
1448                 break;
1449         case T4opts:
1450                 t->t4 = v;
1451                 break;
1452         case T6opts:
1453                 t->t6 = v;
1454                 break;
1455         case Predictor:
1456                 t->predictor = v;
1457                 break;
1458         case Color:
1459                 t->color = f->val;
1460                 t->ncolor = f->cnt;
1461                 break;
1462         default:
1463                 werrstr("shouldn't reach");
1464                 return -1;
1465         }
1466         return 0;
1467 }
1468
1469 static int
1470 readfield(Tif *t, Fld *f)
1471 {
1472         int size;
1473         ulong i, j, n, off;
1474         ulong (*readval)(Tif *);
1475
1476         f->tag = readshort(t);
1477         f->typ = readshort(t);
1478         f->cnt = readlong(t);
1479         f->val = nil;
1480         switch(f->tag) {
1481         case Width:
1482         case Length:
1483         case Compression:
1484         case Photometric:
1485         case Fill:
1486         case Orientation:
1487         case Samples:
1488         case Rows:
1489         case Planar:
1490         case T4opts:
1491         case T6opts:
1492         case Predictor:
1493                 if(f->cnt != 1) {
1494                         werrstr("field count");
1495                         return -1;
1496                 }
1497                 break;
1498         case Bits:
1499                 if(f->cnt != 1 && f->cnt != 3) {
1500                         werrstr("field count");
1501                         return -1;
1502                 }
1503                 break;
1504         case Strips:
1505         case Counts:
1506         case Color:
1507                 break;
1508         default:
1509                 readlong(t);
1510                 return 0;
1511         }
1512         switch(f->typ) {
1513         case Byte:
1514                 readval = readbyte;
1515                 break;
1516         case Short:
1517                 readval = readshort;
1518                 break;
1519         case Long:
1520                 readval = readlong;
1521                 break;
1522         default:
1523                 werrstr("unsupported type\n");
1524                 return -1;
1525         }
1526         if((f->val = malloc(f->cnt*sizeof *f->val)) == nil)
1527                 return -1;
1528         size = typesizes[f->typ];
1529         if((n = size*f->cnt) <= 4) {
1530                 for(i = 0; i < f->cnt; i++)
1531                         f->val[i] = (*readval)(t);
1532                 f->off = 0x0;
1533                 f->nval = i;
1534                 for(j = n; j < 4; j += size)
1535                         (*readval)(t);
1536         } else {
1537                 f->off = readlong(t);
1538                 off = t->n;
1539                 if(gototif(t, f->off) < 0)
1540                         return -1;
1541                 for(i = 0; i < f->cnt; i++)
1542                         f->val[i] = (*readval)(t);
1543                 f->nval = i;
1544                 if(gototif(t, off) < 0)
1545                         return -1;
1546         }
1547         return parsefield(t, f);
1548 }
1549
1550 static int
1551 checkfields(Tif *t)
1552 {
1553         ulong n, size;
1554
1555         if(t->dx == 0) {
1556                 werrstr("image width");
1557                 return -1;
1558         }
1559         if(t->dy == 0) {
1560                 werrstr("image length");
1561                 return -1;
1562         }
1563         switch(t->depth) {
1564         case 1:
1565         case 4:
1566         case 8:
1567         case 24:
1568                 break;
1569         default:
1570                 werrstr("bits per sample");
1571                 return -1;
1572         }
1573         switch(t->comp) {
1574         case Nocomp:
1575                 t->uncompress = nocomp;
1576                 break;
1577         case Huffman:
1578         case T4enc:
1579         case T6enc:
1580                 t->uncompress = fax;
1581                 if(t->decode != nil)
1582                         t->decode = faxdecode;
1583                 if((t->comp == T4enc && t->t4 & (1<<1)) ||
1584                         (t->comp == T6enc &&
1585                         t->t6 & (1<<1))) {
1586                         werrstr("uncompressed mode");
1587                         return -1;
1588                 }
1589                 break;
1590         case Lzwenc:
1591                 t->uncompress = lzw;
1592                 break;
1593         case Packbits:
1594                 t->uncompress = packbits;
1595                 break;
1596         default:
1597                 werrstr("compression");
1598                 return -1;
1599         }
1600         if(t->decode == nil) {
1601                 werrstr("photometric interpretation");
1602                 return -1;
1603         }
1604         if(t->depth > 1 && (t->comp == Huffman ||
1605                 t->comp == T4enc || t->comp == T6enc)) {
1606                 werrstr("compression");
1607                 return -1;
1608         }
1609         if(t->fill != 1 && t->fill != 2) {
1610                 werrstr("fill order");
1611                 return -1;
1612         }
1613         if(t->fill == 2 && t->depth != 1) {
1614                 werrstr("depth should be 1 with fill order 2");
1615                 return -1;
1616         }
1617         if(t->orientation != 1) {
1618                 werrstr("orientation");
1619                 return -1;
1620         }
1621         if(t->rows == 0) {
1622                 werrstr("rows per strip");
1623                 return -1;
1624         }
1625         n = (t->dy + t->rows - 1) / t->rows;
1626         if(t->strips == nil || t->nstrips != n) {
1627                 werrstr("strip offsets");
1628                 return -1;
1629         }
1630         if(t->samples == 1 && t->photo == Rgb) {
1631                 werrstr("not enough samples per pixel");
1632                 return -1;
1633         }
1634         if(t->samples == 3 && t->photo != Rgb) {
1635                 werrstr("too many samples per pixel");
1636                 return -1;
1637         }
1638         if(t->samples != 1 && t->samples != 3) {
1639                 werrstr("samples per pixel");
1640                 return -1;
1641         }
1642         /*
1643         * strip byte counts should not be missing,
1644         * but we can guess correctly in this case
1645         */
1646         size = sizeof *t->counts;
1647         if(t->counts == nil && t->comp == Nocomp &&
1648                 t->nstrips == 1 &&
1649                 (t->counts = malloc(size)) != nil) {
1650                 t->counts[0] = (t->dx*t->dy*t->depth + 7) / 8;
1651                 t->ncounts = t->nstrips;
1652         }
1653         if(t->counts == nil || t->ncounts != t->nstrips) {
1654                 werrstr("strip byte counts");
1655                 return -1;
1656         }
1657         if(t->planar != 1) {
1658                 werrstr("planar configuration");
1659                 return -1;
1660         }
1661         if(t->photo == Palette && (t->color == nil ||
1662                 t->ncolor != 3*(1<<t->depth))) {
1663                 werrstr("color map");
1664                 return -1;
1665         }
1666         return 0;
1667 }
1668
1669 static int
1670 readstrips(Tif *t)
1671 {
1672         int i, j, n;
1673         ulong off;
1674
1675         t->data = nil;
1676         t->ndata = 0;
1677         for(i = 0; i < t->nstrips; i++)
1678                 t->ndata += t->counts[i];
1679         if(t->ndata == 0) {
1680                 werrstr("no image data");
1681                 return -1;
1682         }
1683         if((t->data = malloc(t->ndata*sizeof *t->data)) == nil)
1684                 return -1;
1685         off = t->n;
1686         for(i = n = 0; i < t->nstrips; i++) {
1687                 if(gototif(t, t->strips[i]) < 0)
1688                         return -1;
1689                 /*
1690                 * we store each strip's offset in t->data
1691                 * in order to skip the final rtc or eofb
1692                 * during fax decoding. t->strips is used
1693                 * to save on memory allocation. these
1694                 * offsets are also used in lzw as a
1695                 * preventive measure.
1696                 */
1697                 t->strips[i] = n;
1698                 for(j = 0; j < t->counts[i]; j++, n++)
1699                         t->data[n] = readbyte(t);
1700         }
1701         return gototif(t, off);
1702 }
1703
1704 static Rawimage *
1705 decode(Tif *t)
1706 {
1707         ulong size;
1708         uchar *data;
1709         Rawimage *im;
1710
1711         if((im = malloc(sizeof *im)) == nil)
1712                 return nil;
1713         im->r = Rect(0, 0, t->dx, t->dy);
1714         im->cmap = nil;
1715         im->cmaplen = 0;
1716         im->chanlen = t->dx * t->dy;
1717         if(t->photo == Rgb || t->photo == Palette) {
1718                 im->chandesc = CRGB24;
1719                 im->chanlen *= 3;
1720         } else
1721                 im->chandesc = CY;
1722         im->nchans = 1;
1723         size = im->chanlen * sizeof *im->chans[0];
1724         if((im->chans[0] = malloc(size)) == nil)
1725                 return nil;
1726         /* unused members */
1727         im->fields = 0;
1728         im->gifflags = 0;
1729         im->gifdelay = 0;
1730         im->giftrindex = 0;
1731         im->gifloopcount = 1;
1732         if((data = (*t->uncompress)(t)) == nil)
1733                 return nil;
1734         if((*t->decode)(t, im, data) < 0) {
1735                 free(im->chans[0]);
1736                 free(im);
1737                 im = nil;
1738         }
1739         free(data);
1740         return im;
1741 }
1742
1743 static void
1744 freefields(Tif *t)
1745 {
1746         uint i;
1747
1748         for(i = 0; i < t->nfld; i++) {
1749                 if(t->fld[i].val != nil)
1750                         free(t->fld[i].val);
1751         }
1752         free(t->fld);
1753 }
1754
1755 static Rawimage *
1756 readslave(Tif *t)
1757 {
1758         uint i, j;
1759         Rawimage *r;
1760
1761         if(readheader(t) < 0)
1762                 return nil;
1763         if((t->nfld = readshort(t)) <= 0) {
1764                 werrstr("illegal field number: %#.4x", t->nfld);
1765                 return nil;
1766         }
1767         if((t->fld = malloc(t->nfld*sizeof *t->fld)) == nil)
1768                 return nil;
1769         for(i = 0; i < t->nfld; i++) {
1770                 if(readfield(t, &t->fld[i]) < 0) {
1771                         if(t->fld[i].val != nil)
1772                                 free(t->fld[i].val);
1773                         break;
1774                 }
1775         }
1776         if(i < t->nfld) {
1777                 for(j = 0; j < i; j++) {
1778                         if(t->fld[j].val != nil)
1779                                 free(t->fld[j].val);
1780                 }
1781                 free(t->fld);
1782                 return nil;
1783         }
1784         readlong(t);
1785         if(checkfields(t) < 0) {
1786                 freefields(t);
1787                 return nil;
1788         }
1789         if(readstrips(t) < 0) {
1790                 freefields(t);
1791                 if(t->data != nil)
1792                         free(t->data);
1793                 return nil;
1794         }
1795         free(t->buf);
1796         r = decode(t);
1797         freefields(t);
1798         return r;
1799 }
1800
1801 Rawimage **
1802 Breadtif(Biobuf *b, int colorspace)
1803 {
1804         Rawimage **array, *r;
1805         Tif *t;
1806
1807         if(colorspace != CRGB24) {
1808                 werrstr("unknown color space: %d",
1809                         colorspace);
1810                 return nil;
1811         }
1812         if((t = malloc(sizeof *t)) == nil)
1813                 return nil;
1814         if((array = malloc(2*sizeof *array)) == nil)
1815                 return nil;
1816         t->fd = b;
1817         t->buf = nil;
1818         t->nbuf = t->eof = t->n = 0;
1819         /* order doesn't matter for the first two bytes */
1820         t->byte2 = byte2le;
1821         t->byte4 = byte4le;
1822         /* defaults */
1823         t->dx = 0;
1824         t->dy = 0;
1825         t->depth = 1;
1826         t->comp = 1;
1827         t->uncompress = nil;
1828         t->photo = 0;
1829         t->decode = nil;
1830         t->fill = 1;
1831         t->orientation = 1;
1832         t->strips = nil;
1833         t->nstrips = 0;
1834         t->samples = 1;
1835         t->rows = 0xffffffff; /* entire image is one strip */
1836         t->counts = nil;
1837         t->ncounts = 0;
1838         t->planar = 1;
1839         t->t4 = 0;
1840         t->t6 = 0;
1841         t->predictor = 1;
1842         t->color = nil;
1843         t->ncolor = 0;
1844         r = readslave(t);
1845         free(t);
1846         array[0] = r;
1847         array[1] = nil;
1848         return array;
1849 }
1850
1851 Rawimage **
1852 readtif(int fd, int colorspace)
1853 {
1854         Rawimage **a;
1855         Biobuf b;
1856
1857         if(Binit(&b, fd, OREAD) < 0)
1858                 return nil;
1859         a = Breadtif(&b, colorspace);
1860         Bterm(&b);
1861         return a;
1862 }