]> git.lizzy.rs Git - plan9front.git/blob - sys/src/cmd/jpg/writetif.c
merge
[plan9front.git] / sys / src / cmd / jpg / writetif.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 copy-pasted lzw encoding
13 * hash table implementation:
14 * http://www.remotesensing.org/libtiff/
15 */
16 #include <u.h>
17 #include <libc.h>
18 #include <bio.h>
19 #include <draw.h>
20 #include <memdraw.h>
21 #include "imagefile.h"
22
23 enum {
24         Tbyte = 0x0001,
25         Tascii = 0x0002,
26         Tshort = 0x0003,
27         Tlong = 0x0004,
28         Trational = 0x0005,
29         Tnocomp = 0x0001,
30         Thuffman = 0x0002,
31         Tt4enc = 0x0003,
32         Tt6enc = 0x0004,
33         Tlzw = 0x0005,
34         Tpackbits = 0x8005
35 };
36
37 enum {
38         Twidth,
39         Tlength,
40         Tbits,
41         Tcomp,
42         Tphoto,
43         Tfill,
44         Tdesc,
45         Tstrips,
46         Tsamples,
47         Trows,
48         Tcounts,
49         Txres,
50         Tyres,
51         T4opt,
52         Tresunit,
53         Tpredictor,
54         Tcolor
55 };
56
57 enum {
58         Kpar = 2,
59         Nfaxtab = 105
60 };
61
62 enum {
63         Clrcode = 256,
64         Eoicode = 257,
65         Tabsz = 1<<12,
66         Hshift = 13 - 8,
67         Hsize = 9001L
68 };
69
70 typedef struct Tab Tab;
71 typedef struct Fax Fax;
72 typedef struct Hash Hash;
73 typedef struct Lzw Lzw;
74 typedef struct Pkb Pkb;
75 typedef struct Fld Fld;
76 typedef struct Tif Tif;
77
78 struct Tab {
79         int len;
80         int code;
81         int run;
82 };
83
84 struct Fax {
85         int st;
86         Tab *tab[2];
87         int byte;
88         int nbyte;
89         ulong *l1;
90         ulong *l2;
91         uchar *data;
92         ulong ndata;
93         ulong n;
94 };
95
96 struct Hash {
97         long hash;
98         u16int code;
99 };
100
101 struct Lzw {
102         Hash hash[Hsize];
103         int ntab;
104         int len;
105         int byte;
106         int nbyte;
107         uchar *data;
108         ulong ndata;
109         ulong n;
110 };
111
112 struct Pkb {
113         uchar *data;
114         ulong ndata;
115         ulong n;
116 };
117
118 struct Fld {
119         ushort tag;
120         ushort typ;
121 };
122
123 struct Tif {
124         ulong dx;
125         ulong dy;
126         ushort depth[3];
127         ushort comp;
128         ulong opt;
129         char *(*compress)(Tif *);
130         ushort photo;
131         char *desc;
132         ulong *strips;
133         ulong nstrips;
134         ushort samples;
135         ulong rows;
136         ulong *counts;
137         ushort *color;
138         ulong ncolor;
139         uchar *data;
140         ulong ndata;
141         ushort nfld;
142         int bpl;
143 };
144
145 static Fld flds[] = {
146         [Twidth] {0x0100, Tlong},
147         [Tlength] {0x0101, Tlong},
148         [Tbits] {0x0102, Tshort},
149         [Tcomp] {0x0103, Tshort},
150         [Tphoto] {0x0106, Tshort},
151         [Tfill] {0x010a, Tshort},
152         [Tdesc] {0x010e, Tascii},
153         [Tstrips] {0x0111, Tlong},
154         [Tsamples] {0x0115, Tshort},
155         [Trows] {0x0116, Tlong},
156         [Tcounts] {0x0117, Tlong},
157         [Txres] {0x011a, Trational},
158         [Tyres] {0x011b, Trational},
159         [T4opt] {0x0124, Tlong},
160         [Tresunit] {0x0128, Tshort},
161         [Tpredictor] {0x013d, Tshort},
162         [Tcolor] {0x0140, Tshort}
163 };
164
165 static Tab faxwhite[Nfaxtab] = {
166         {8, 0x35, 0}, /* 0011 0101 */
167         {6, 0x7, 1}, /* 0001 11 */
168         {4, 0x7, 2}, /* 0111 */
169         {4, 0x8, 3}, /* 1000 */
170         {4, 0xb, 4}, /* 1011 */
171         {4, 0xc, 5}, /* 1100 */
172         {4, 0xe, 6}, /* 1110 */
173         {4, 0xf, 7}, /* 1111 */
174         {5, 0x13, 8}, /* 1001 1 */
175         {5, 0x14, 9}, /* 1010 0 */
176         {5, 0x7, 10}, /* 0011 1 */
177         {5, 0x8, 11}, /* 0100 0 */
178         {6, 0x8, 12}, /* 0010 00 */
179         {6, 0x3, 13}, /* 0000 11 */
180         {6, 0x34, 14}, /* 1101 00 */
181         {6, 0x35, 15}, /* 1101 01 */
182         {6, 0x2a, 16}, /* 1010 10 */
183         {6, 0x2b, 17}, /* 1010 11 */
184         {7, 0x27, 18}, /* 0100 111 */
185         {7, 0xc, 19}, /* 0001 100 */
186         {7, 0x8, 20}, /* 0001 000 */
187         {7, 0x17, 21}, /* 0010 111 */
188         {7, 0x3, 22}, /* 0000 011 */
189         {7, 0x4, 23}, /* 0000 100 */
190         {7, 0x28, 24}, /* 0101 000 */
191         {7, 0x2b, 25}, /* 0101 011 */
192         {7, 0x13, 26}, /* 0010 011 */
193         {7, 0x24, 27}, /* 0100 100 */
194         {7, 0x18, 28}, /* 0011 000 */
195         {8, 0x2, 29}, /* 0000 0010 */
196         {8, 0x3, 30}, /* 0000 0011 */
197         {8, 0x1a, 31}, /* 0001 1010 */
198         {8, 0x1b, 32}, /* 0001 1011 */
199         {8, 0x12, 33}, /* 0001 0010 */
200         {8, 0x13, 34}, /* 0001 0011 */
201         {8, 0x14, 35}, /* 0001 0100 */
202         {8, 0x15, 36}, /* 0001 0101 */
203         {8, 0x16, 37}, /* 0001 0110 */
204         {8, 0x17, 38}, /* 0001 0111 */
205         {8, 0x28, 39}, /* 0010 1000 */
206         {8, 0x29, 40}, /* 0010 1001 */
207         {8, 0x2a, 41}, /* 0010 1010 */
208         {8, 0x2b, 42}, /* 0010 1011 */
209         {8, 0x2c, 43}, /* 0010 1100 */
210         {8, 0x2d, 44}, /* 0010 1101 */
211         {8, 0x4, 45}, /* 0000 0100 */
212         {8, 0x5, 46}, /* 0000 0101 */
213         {8, 0xa, 47}, /* 0000 1010 */
214         {8, 0xb, 48}, /* 0000 1011 */
215         {8, 0x52, 49}, /* 0101 0010 */
216         {8, 0x53, 50}, /* 0101 0011 */
217         {8, 0x54, 51}, /* 0101 0100 */
218         {8, 0x55, 52}, /* 0101 0101 */
219         {8, 0x24, 53}, /* 0010 0100 */
220         {8, 0x25, 54}, /* 0010 0101 */
221         {8, 0x58, 55}, /* 0101 1000 */
222         {8, 0x59, 56}, /* 0101 1001 */
223         {8, 0x5a, 57}, /* 0101 1010 */
224         {8, 0x5b, 58}, /* 0101 1011 */
225         {8, 0x4a, 59}, /* 0100 1010 */
226         {8, 0x4b, 60}, /* 0100 1011 */
227         {8, 0x32, 61}, /* 0011 0010 */
228         {8, 0x33, 62}, /* 0011 0011 */
229         {8, 0x34, 63}, /* 0011 0100 */
230         {5, 0x1b, 64}, /* 1101 1 */
231         {5, 0x12, 128}, /* 1001 0 */
232         {6, 0x17, 192}, /* 0101 11 */
233         {7, 0x37, 256}, /* 0110 111 */
234         {8, 0x36, 320}, /* 0011 0110 */
235         {8, 0x37, 384}, /* 0011 0111 */
236         {8, 0x64, 448}, /* 0110 0100 */
237         {8, 0x65, 512}, /* 0110 0101 */
238         {8, 0x68, 576}, /* 0110 1000 */
239         {8, 0x67, 640}, /* 0110 0111 */
240         {9, 0xcc, 704}, /* 0110 0110 0 */
241         {9, 0xcd, 768}, /* 0110 0110 1 */
242         {9, 0xd2, 832}, /* 0110 1001 0 */
243         {9, 0xd3, 896}, /* 0110 1001 1 */
244         {9, 0xd4, 960}, /* 0110 1010 0 */
245         {9, 0xd5, 1024}, /* 0110 1010 1 */
246         {9, 0xd6, 1088}, /* 0110 1011 0 */
247         {9, 0xd7, 1152}, /* 0110 1011 1 */
248         {9, 0xd8, 1216}, /* 0110 1100 0 */
249         {9, 0xd9, 1280}, /* 0110 1100 1 */
250         {9, 0xda, 1344}, /* 0110 1101 0 */
251         {9, 0xdb, 1408}, /* 0110 1101 1 */
252         {9, 0x98, 1472}, /* 0100 1100 0 */
253         {9, 0x99, 1536}, /* 0100 1100 1 */
254         {9, 0x9a, 1600}, /* 0100 1101 0 */
255         {6, 0x18, 1664}, /* 0110 00 */
256         {9, 0x9b, 1728}, /* 0100 1101 1 */
257         {11, 0x8, 1792}, /* 0000 0001 000 */
258         {11, 0xc, 1856}, /* 0000 0001 100 */
259         {11, 0xd, 1920}, /* 0000 0001 101 */
260         {12, 0x12, 1984}, /* 0000 0001 0010 */
261         {12, 0x13, 2048}, /* 0000 0001 0011 */
262         {12, 0x14, 2112}, /* 0000 0001 0100 */
263         {12, 0x15, 2176}, /* 0000 0001 0101 */
264         {12, 0x16, 2240}, /* 0000 0001 0110 */
265         {12, 0x17, 2304}, /* 0000 0001 0111 */
266         {12, 0x1c, 2368}, /* 0000 0001 1100 */
267         {12, 0x1d, 2432}, /* 0000 0001 1101 */
268         {12, 0x1e, 2496}, /* 0000 0001 1110 */
269         {12, 0x1f, 2560}, /* 0000 0001 1111 */
270         {12, 0x1, -1} /* 0000 0000 0001 */
271 };
272
273 static Tab faxblack[Nfaxtab] = {
274         {10, 0x37, 0}, /* 0000 1101 11 */
275         {3, 0x2, 1}, /* 010 */
276         {2, 0x3, 2}, /* 11 */
277         {2, 0x2, 3}, /* 10 */
278         {3, 0x3, 4}, /* 011 */
279         {4, 0x3, 5}, /* 0011 */
280         {4, 0x2, 6}, /* 0010 */
281         {5, 0x3, 7}, /* 0001 1 */
282         {6, 0x5, 8}, /* 0001 01 */
283         {6, 0x4, 9}, /* 0001 00 */
284         {7, 0x4, 10}, /* 0000 100 */
285         {7, 0x5, 11}, /* 0000 101 */
286         {7, 0x7, 12}, /* 0000 111 */
287         {8, 0x4, 13}, /* 0000 0100 */
288         {8, 0x7, 14}, /* 0000 0111 */
289         {9, 0x18, 15}, /* 0000 1100 0 */
290         {10, 0x17, 16}, /* 0000 0101 11 */
291         {10, 0x18, 17}, /* 0000 0110 00 */
292         {10, 0x8, 18}, /* 0000 0010 00 */
293         {11, 0x67, 19}, /* 0000 1100 111 */
294         {11, 0x68, 20}, /* 0000 1101 000 */
295         {11, 0x6c, 21}, /* 0000 1101 100 */
296         {11, 0x37, 22}, /* 0000 0110 111 */
297         {11, 0x28, 23}, /* 0000 0101 000 */
298         {11, 0x17, 24}, /* 0000 0010 111 */
299         {11, 0x18, 25}, /* 0000 0011 000 */
300         {12, 0xca, 26}, /* 0000 1100 1010 */
301         {12, 0xcb, 27}, /* 0000 1100 1011 */
302         {12, 0xcc, 28}, /* 0000 1100 1100 */
303         {12, 0xcd, 29}, /* 0000 1100 1101 */
304         {12, 0x68, 30}, /* 0000 0110 1000 */
305         {12, 0x69, 31}, /* 0000 0110 1001 */
306         {12, 0x6a, 32}, /* 0000 0110 1010 */
307         {12, 0x6b, 33}, /* 0000 0110 1011 */
308         {12, 0xd2, 34}, /* 0000 1101 0010 */
309         {12, 0xd3, 35}, /* 0000 1101 0011 */
310         {12, 0xd4, 36}, /* 0000 1101 0100 */
311         {12, 0xd5, 37}, /* 0000 1101 0101 */
312         {12, 0xd6, 38}, /* 0000 1101 0110 */
313         {12, 0xd7, 39}, /* 0000 1101 0111 */
314         {12, 0x6c, 40}, /* 0000 0110 1100 */
315         {12, 0x6d, 41}, /* 0000 0110 1101 */
316         {12, 0xda, 42}, /* 0000 1101 1010 */
317         {12, 0xdb, 43}, /* 0000 1101 1011 */
318         {12, 0x54, 44}, /* 0000 0101 0100 */
319         {12, 0x55, 45}, /* 0000 0101 0101 */
320         {12, 0x56, 46}, /* 0000 0101 0110 */
321         {12, 0x57, 47}, /* 0000 0101 0111 */
322         {12, 0x64, 48}, /* 0000 0110 0100 */
323         {12, 0x65, 49}, /* 0000 0110 0101 */
324         {12, 0x52, 50}, /* 0000 0101 0010 */
325         {12, 0x53, 51}, /* 0000 0101 0011 */
326         {12, 0x24, 52}, /* 0000 0010 0100 */
327         {12, 0x37, 53}, /* 0000 0011 0111 */
328         {12, 0x38, 54}, /* 0000 0011 1000 */
329         {12, 0x27, 55}, /* 0000 0010 0111 */
330         {12, 0x28, 56}, /* 0000 0010 1000 */
331         {12, 0x58, 57}, /* 0000 0101 1000 */
332         {12, 0x59, 58}, /* 0000 0101 1001 */
333         {12, 0x2b, 59}, /* 0000 0010 1011 */
334         {12, 0x2c, 60}, /* 0000 0010 1100 */
335         {12, 0x5a, 61}, /* 0000 0101 1010 */
336         {12, 0x66, 62}, /* 0000 0110 0110 */
337         {12, 0x67, 63}, /* 0000 0110 0111 */
338         {10, 0xf, 64}, /* 0000 0011 11 */
339         {12, 0xc8, 128}, /* 0000 1100 1000 */
340         {12, 0xc9, 192}, /* 0000 1100 1001 */
341         {12, 0x5b, 256}, /* 0000 0101 1011 */
342         {12, 0x33, 320}, /* 0000 0011 0011 */
343         {12, 0x34, 384}, /* 0000 0011 0100 */
344         {12, 0x35, 448}, /* 0000 0011 0101 */
345         {13, 0x6c, 512}, /* 0000 0011 0110 0 */
346         {13, 0x6d, 576}, /* 0000 0011 0110 1 */
347         {13, 0x4a, 640}, /* 0000 0010 0101 0 */
348         {13, 0x4b, 704}, /* 0000 0010 0101 1 */
349         {13, 0x4c, 768}, /* 0000 0010 0110 0 */
350         {13, 0x4d, 832}, /* 0000 0010 0110 1 */
351         {13, 0x72, 896}, /* 0000 0011 1001 0 */
352         {13, 0x73, 960}, /* 0000 0011 1001 1 */
353         {13, 0x74, 1024}, /* 0000 0011 1010 0 */
354         {13, 0x75, 1088}, /* 0000 0011 1010 1 */
355         {13, 0x76, 1152}, /* 0000 0011 1011 0 */
356         {13, 0x77, 1216}, /* 0000 0011 1011 1 */
357         {13, 0x52, 1280}, /* 0000 0010 1001 0 */
358         {13, 0x53, 1344}, /* 0000 0010 1001 1 */
359         {13, 0x54, 1408}, /* 0000 0010 1010 0 */
360         {13, 0x55, 1472}, /* 0000 0010 1010 1 */
361         {13, 0x5a, 1536}, /* 0000 0010 1101 0 */
362         {13, 0x5b, 1600}, /* 0000 0010 1101 1 */
363         {13, 0x64, 1664}, /* 0000 0011 0010 0 */
364         {13, 0x65, 1728}, /* 0000 0011 0010 1 */
365         {11, 0x8, 1792}, /* 0000 0001 000 */
366         {11, 0xc, 1856}, /* 0000 0001 100 */
367         {11, 0xd, 1920}, /* 0000 0001 101 */
368         {12, 0x12, 1984}, /* 0000 0001 0010 */
369         {12, 0x13, 2048}, /* 0000 0001 0011 */
370         {12, 0x14, 2112}, /* 0000 0001 0100 */
371         {12, 0x15, 2176}, /* 0000 0001 0101 */
372         {12, 0x16, 2240}, /* 0000 0001 0110 */
373         {12, 0x17, 2304}, /* 0000 0001 0111 */
374         {12, 0x1c, 2368}, /* 0000 0001 1100 */
375         {12, 0x1d, 2432}, /* 0000 0001 1101 */
376         {12, 0x1e, 2496}, /* 0000 0001 1110 */
377         {12, 0x1f, 2560}, /* 0000 0001 1111 */
378         {12, 0x1, -1} /* 0000 0000 0001 */
379 };
380
381 static Tab faxcodes[] = {
382         {4, 0x1, 0}, /* 0001 */
383         {3, 0x1, 0}, /* 001 */
384         {1, 0x1, 0}, /* 1 */
385         {3, 0x2, 0}, /* 010 */
386         {6, 0x2, 0}, /* 0000 10 */
387         {7, 0x2, 0}, /* 0000 010 */
388         {3, 0x3, 0}, /* 011 */
389         {6, 0x3, 0}, /* 0000 11 */
390         {7, 0x3, 0} /* 0000 011 */
391 };
392
393 static int typesizes[] = {0, 1, 1, 2, 4, 8};
394 static char memerr[] = "WriteTIF: malloc failed";
395
396 static int
397 put1(Biobuf *b, uchar c)
398 {
399         return Bputc(b, c);
400 }
401
402 static int
403 put2(Biobuf *b, uint s)
404 {
405         if(put1(b, s>>8) < 0)
406                 return -1;
407         return put1(b, s);
408 }
409
410 static int
411 put4(Biobuf *b, ulong l)
412 {
413         if(put2(b, l>>16) < 0)
414                 return -1;
415         return put2(b, l);
416 }
417
418 static char *
419 nocomp(Tif *)
420 {
421         return nil;
422 }
423
424 static char *
425 faxputbyte(Fax *f)
426 {
427         if(f->n >= f->ndata) {
428                 f->ndata *= 2;
429                 f->data = realloc(f->data,
430                         f->ndata*sizeof *f->data);
431                 if(f->data == nil)
432                         return memerr;
433         }
434         f->data[f->n++] = f->byte;
435         f->byte = f->nbyte = 0;
436         return nil;
437 }
438
439 static char *
440 faxputbit(Fax *f, int bit)
441 {
442         f->byte = (f->byte << 1) | bit;
443         f->nbyte++;
444         return f->nbyte >= 8? faxputbyte(f): nil;
445 }
446
447 static char *
448 faxbytealign(Fax *f)
449 {
450         char *err;
451
452         err = nil;
453         if(f->nbyte != 0) {
454                 f->byte <<= 8 - f->nbyte;
455                 err = faxputbyte(f);
456         }
457         return err;
458 }
459
460 static char *
461 faxputcode(Fax *f, Tab *tab)
462 {
463         int i, bit;
464         char *err;
465
466         for(i = tab->len-1; i >= 0; i--) {
467                 bit = (tab->code >> i) & 0x1;
468                 if((err = faxputbit(f, bit)) != nil)
469                         return err;
470         }
471         return nil;
472 }
473
474 static int
475 faxgettab(int run)
476 {
477         if(run >= 0) {
478                 if(run <= 64)
479                         return run;
480                 if(run <= 2560)
481                         return 64 + run/64 - 1;
482         }
483         return Nfaxtab - 1;
484 }
485
486 static char *
487 faxputrun(Fax *f, long run)
488 {
489         char *err;
490         Tab *tab, *p;
491
492         tab = f->tab[f->st];
493         p = &tab[faxgettab(2560)];
494         while(run >= 2624) {
495                 if((err = faxputcode(f, p)) != nil)
496                         return err;
497                 run -= 2560;
498         }
499         if(run >= 64) {
500                 p = &tab[faxgettab(run)];
501                 if((err = faxputcode(f, p)) != nil)
502                         return err;
503                 run -= p->run;
504         }
505         p = &tab[faxgettab(run)];
506         err = faxputcode(f, p);
507         f->st ^= 1;
508         return err;
509 }
510
511 static char *
512 faxputeol(Fax *f)
513 {
514         return faxputcode(f, &f->tab[0][faxgettab(-1)]);
515 }
516
517 static char *
518 fax1d(Fax *f, ulong dx)
519 {
520         ulong i;
521         long run;
522         char *err;
523
524         f->st = 0;
525         run = f->l2[0];
526         for(i = 0;;) {
527                 if((err = faxputrun(f, run)) != nil)
528                         return err;
529                 if(f->l2[i++] >= dx)
530                         break;
531                 run = f->l2[i] - f->l2[i-1];
532         }
533         memmove(f->l1, f->l2, i*sizeof *f->l1);
534         return nil;
535 }
536
537 static char *
538 fax2d(Fax *f, ulong dx)
539 {
540         int j, v;
541         ulong i;
542         long a0, a1, a2, b1, b2;
543         char *err;
544         Tab *tab, *p;
545
546         f->st = 0;
547         a0 = a1 = -1;
548         tab = faxcodes;
549         for(i = 0, err = nil; err == nil;) {
550                 while(a1 <= a0)
551                         a1 = f->l2[i++];
552                 for(j = 0;; j++) {
553                         b1 = f->l1[j];
554                         if(b1 > a0 && f->st == j%2)
555                                 break;
556                         if(b1 >= dx)
557                                 break;
558                 }
559                 if((b2 = b1) < dx)
560                         b2 = f->l1[j+1];
561                 if(b2 < a1) {
562                         /* pass */
563                         p = &tab[0];
564                         err = faxputcode(f, p);
565                         a0 = b2;
566                 } else if(abs(v = a1-b1) < 3) {
567                         /* vertical */
568                         p = &tab[2+(v>0?3:0)+abs(v)];
569                         err = faxputcode(f, p);
570                         f->st ^= 1;
571                         a0 = a1;
572                 } else {
573                         /* horizontal */
574                         if(a0 < 0)
575                                 a0 = 0;
576                         p = &tab[1];
577                         if((err = faxputcode(f, p)) != nil)
578                                 return err;
579                         a2 = a1 < dx? f->l2[i++]: a1;
580                         if((err = faxputrun(f, a1-a0)) != nil)
581                                 return err;
582                         err = faxputrun(f, a2-a1);
583                         a0 = a2;
584                 }
585                 if(a0 >= dx)
586                         break;
587         }
588         memmove(f->l1, f->l2, i*sizeof *f->l1);
589         return err;
590 }
591
592 static char *
593 faxstrip(Tif *t, Fax *f, uchar *data, ulong n, ulong dx)
594 {
595         int k, s, d1, two;
596         ulong i, j, x;
597         char *err;
598
599         d1 = t->comp != Tt6enc;
600         two = 0;
601         if(t->comp == Tt4enc) {
602                 if((err = faxputeol(f)) != nil)
603                         return err;
604                 if(t->opt && (err = faxputbit(f, 1)) != nil)
605                         return err;
606         }
607         for(i = j = x = 0; i < n;) {
608                 s = 7 - x++%8;
609                 k = ((data[i] >> s) & 0x1) ^ 0x1;
610                 if(s == 0)
611                         i++;
612                 if(k != f->st) {
613                         f->l2[j++] = x - 1;
614                         f->st ^= 1;
615                 }
616                 if(x == dx) {
617                         f->l2[j] = dx;
618                         if(d1) {
619                                 err = fax1d(f, dx);
620                                 if(t->comp == Tt4enc &&
621                                         t->opt) {
622                                         two = Kpar - 1;
623                                         d1 = 0;
624                                 }
625                         } else {
626                                 err = fax2d(f, dx);
627                                 if(two > 0 && --two <= 0)
628                                         d1 = 1;
629                         }
630                         if(err != nil)
631                                 return err;
632                         if(t->comp == Thuffman)
633                                 err = faxbytealign(f);
634                         else if(t->comp == Tt4enc &&
635                                 t->opt) {
636                                 if((err = faxputeol(f)) != nil)
637                                         return err;
638                                 err = faxputbit(f, d1);
639                         } else if(t->comp == Tt4enc)
640                                 err = faxputeol(f);
641                         if(err != nil)
642                                 return err;
643                         f->st = 0;
644                         if(s != 0)
645                                 i++;
646                         x = 0;
647                         j = 0;
648                 }
649         }
650         if(t->comp == Tt4enc || t->comp == Tt6enc) {
651                 i = t->comp == Tt4enc? 5: 2;
652                 for(; i > 0; i--) {
653                         if((err = faxputeol(f)) != nil)
654                                 return err;
655                         if(t->comp == Tt4enc && t->opt) {
656                                 err = faxputbit(f, 1);
657                                 if(err != nil)
658                                         return err;
659                         }
660                 }
661         }
662         return faxbytealign(f);
663 }
664
665 static char *
666 fax(Tif *t)
667 {
668         ulong i, m, n;
669         char *err;
670         uchar *data;
671         Fax f;
672
673         f.ndata = t->ndata;
674         if((f.data = malloc(f.ndata*sizeof *f.data)) == nil)
675                 return memerr;
676         f.l1 = mallocz((t->dx+1)*sizeof *f.l1, 1);
677         f.l2 = mallocz((t->dx+1)*sizeof *f.l2, 1);
678         if(f.l1 == nil || f.l2 == nil) {
679                 free(f.data);
680                 if(f.l1 != nil)
681                         free(f.l1);
682                 if(f.l2 != nil)
683                         free(f.l2);
684                 return memerr;
685         }
686         f.tab[0] = faxwhite;
687         f.tab[1] = faxblack;
688         f.n = f.byte = f.nbyte = 0;
689         for(i = n = 0, data = t->data; i < t->nstrips; i++) {
690                 f.st = 0;
691                 f.l1[0] = t->dx;
692                 m = t->counts[i];
693                 if((err = faxstrip(t, &f, data, m, t->dx)) != nil) {
694                         if(f.data != nil)
695                                 free(f.data);
696                         return err;
697                 }
698                 data += m;
699                 t->counts[i] = f.n - n;
700                 n = f.n;
701         }
702         free(t->data);
703         free(f.l1);
704         free(f.l2);
705         t->data = f.data;
706         t->ndata = f.n;
707         return nil;
708 }
709
710 static void
711 lzwtabinit(Lzw *l)
712 {
713         long i;
714         Hash *hp;
715
716         l->ntab = Eoicode + 1;
717         l->len = 9;
718         hp = &l->hash[Hsize-1];
719         i = Hsize - 8;
720         do {
721                 i -= 8;
722                 hp[-7].hash = -1;
723                 hp[-6].hash = -1;
724                 hp[-5].hash = -1;
725                 hp[-4].hash = -1;
726                 hp[-3].hash = -1;
727                 hp[-2].hash = -1;
728                 hp[-1].hash = -1;
729                 hp[0].hash = -1;
730                 hp -= 8;
731         } while(i >= 0);
732         for(i += 8; i > 0; i--, hp--)
733                 hp->hash = -1;
734 }
735
736 static char *
737 lzwputbyte(Lzw *l)
738 {
739         if(l->n >= l->ndata) {
740                 l->ndata *= 2;
741                 l->data = realloc(l->data,
742                         l->ndata*sizeof *l->data);
743                 if(l->data == nil)
744                         return memerr;
745         }
746         l->data[l->n++] = l->byte;
747         l->byte = l->nbyte = 0;
748         return nil;
749 }
750
751 static char *
752 lzwbytealign(Lzw *l)
753 {
754         char *err;
755
756         err = nil;
757         if(l->nbyte != 0) {
758                 l->byte <<= 8 - l->nbyte;
759                 err = lzwputbyte(l);
760         }
761         return err;
762 }
763
764 static char *
765 lzwputcode(Lzw *l, int code)
766 {
767         int i, c;
768         char *err;
769
770         for(i = l->len-1; i >= 0; i--) {
771                 c = (code >> i) & 0x1;
772                 l->byte = (l->byte << 1) | c;
773                 l->nbyte++;
774                 if(l->nbyte >= 8) {
775                         if((err = lzwputbyte(l)) != nil)
776                                 return err;
777                 }
778         }
779         return nil;
780 }
781
782 static void
783 predict1(Tif *t)
784 {
785         int pix, b[8], d, m, n, j;
786         ulong x, y;
787         uchar *data, *p;
788
789         p = t->data;
790         d = *t->depth;
791         m = (1 << d) - 1;
792         n = 8 / d;
793         for(y = 0; y < t->dy; y++) {
794                 data = p += t->bpl;
795                 for(x = t->bpl; x > 0; x--) {
796                         pix = *--data;
797                         for(j = 0; j < n; j++) {
798                                 b[j] = (pix >> d*j) & m;
799                                 if(j > 0)
800                                         b[j-1] -= b[j];
801                         }
802                         if(x > 1)
803                                 b[n-1] -= *(data-1) & m;
804                         for(j = pix = 0; j < n; j++)
805                                 pix |= (b[j] & m) << d*j;
806                         *data = pix;
807                 }
808         }
809 }
810
811 static void
812 predict8(Tif *t)
813 {
814         ulong j, s, x, y;
815         uchar *data, *p;
816
817         p = t->data;
818         s = t->samples;
819         for(y = 0; y < t->dy; y++) {
820                 data = p += t->dx * s;
821                 for(x = t->dx; x > 1; x--) {
822                         for(j = 0; j < s; j++) {
823                                 data--;
824                                 *data -= *(data-s);
825                         }
826                 }
827         }
828 }
829
830 static char *
831 lzwstrip(Lzw *l, uchar *data, ulong n)
832 {
833         int k, h;
834         long fcode, disp;
835         ulong i;
836         char *err;
837         Hash *hp;
838         u16int ent;
839
840         if((err = lzwputcode(l, Clrcode)) != nil)
841                 return err;
842         i = 0;
843         ent = data[i++];
844         for(; i < n; i++) {
845                 k = data[i];
846                 fcode = ((long)k << 12) + ent;
847                 h = (k << Hshift) ^ ent;
848                 hp = &l->hash[h];
849                 if(hp->hash == fcode) {
850 hit:
851                         ent = hp->code;
852                         continue;
853                 }
854                 if(hp->hash >= 0) {
855                         disp = h == 0? 1: Hsize - h;
856                         do {
857                                 if((h -= disp) < 0)
858                                         h += Hsize;
859                                 hp = &l->hash[h];
860                                 if(hp->hash == fcode)
861                                         goto hit;
862                         } while(hp->hash >= 0);
863                 }
864                 if((err = lzwputcode(l, ent)) != nil)
865                         return err;
866                 ent = k;
867                 hp->hash = fcode;
868                 switch(hp->code = l->ntab) {
869                 case 511:
870                 case 1023:
871                 case 2047:
872                         l->len++;
873                         break;
874                 default:
875                         break;
876                 }
877                 if(l->ntab++ >= Tabsz-2) {
878                         err = lzwputcode(l, Clrcode);
879                         if(err != nil)
880                                 return err;
881                         lzwtabinit(l);
882                 }
883         }
884         if((err = lzwputcode(l, ent)) != nil)
885                 return err;
886         if((err = lzwputcode(l, Eoicode)) != nil)
887                 return err;
888         return lzwbytealign(l);
889 }
890
891 static char *
892 lzw(Tif *t)
893 {
894         ulong i, m, n;
895         char *err;
896         uchar *data;
897         Lzw l;
898
899         if(t->opt)
900                 *t->depth < 8? predict1(t): predict8(t);
901         l.ndata = t->ndata;
902         if((l.data = malloc(l.ndata*sizeof *l.data)) == nil)
903                 return memerr;
904         l.n = l.byte = l.nbyte = 0;
905         err = nil;
906         for(i = n = 0, data = t->data; i < t->nstrips; i++) {
907                 lzwtabinit(&l);
908                 m = t->counts[i];
909                 if((err = lzwstrip(&l, data, m)) != nil)
910                         break;
911                 data += m;
912                 t->counts[i] = l.n - n;
913                 n = l.n;
914         }
915         if(err != nil) {
916                 if(l.data != nil)
917                         free(l.data);
918                 return err;
919         }
920         free(t->data);
921         t->data = l.data;
922         t->ndata = l.n;
923         return nil;
924 }
925
926 static char *
927 pkbrow(Pkb *p, uchar *data, int ndata, long *buf)
928 {
929         int b, repl;
930         long i, j, k, n;
931         ulong m;
932
933         i = n = 0;
934         buf[n++] = i;
935         b = data[i++];
936         if(i < ndata)
937                 repl = b == data[i]? 1: 0;
938         else
939                 repl = 0;
940         for(; i < ndata; i++) {
941                 k = data[i];
942                 j = labs(buf[n-1]);
943                 if(repl) {
944                         if(b != k) {
945                                 repl ^= 1;
946                                 buf[n++] = -i;
947                         }
948                 } else {
949                         if(b == k) {
950                                 repl ^= 1;
951                                 if(i-j > 1)
952                                         buf[n++] = i - 1;
953                         }
954                 }
955                 b = k;
956         }
957         buf[n++] = repl? -i: i;
958         for(i = 1; i < n;) {
959                 k = buf[i];
960                 j = labs(buf[i-1]);
961                 if(i < n-2 && k > 0 && buf[i+1] < 0 &&
962                         buf[i+2] > 0 && -buf[i+1]-k <= 2) {
963                         buf[i] = buf[i+1] = buf[i+2];
964                         continue;
965                 }
966                 if((b = labs(k) - j) > 128) {
967                         b = 128;
968                         buf[i-1] += buf[i-1] < 0? -b: b;
969                 } else
970                         i++;
971                 if(b == 0)
972                         continue;
973                 m = 1 + (k < 0? 1: b);
974                 if(p->n+m > p->ndata) {
975                         p->ndata = (p->n + m) * 2;
976                         p->data = realloc(p->data,
977                                 p->ndata*sizeof *p->data);
978                         if(p->data == nil)
979                                 return memerr;
980                 }
981                 if(k < 0) {
982                         p->data[p->n++] = 1 - b;
983                         p->data[p->n++] = data[j];
984                 } else {
985                         p->data[p->n++] = b - 1;
986                         memmove(p->data+p->n, data+j, b);
987                         p->n += b;
988                 }
989         }
990         return nil;
991 }
992
993 static char *
994 packbits(Tif *t)
995 {
996         ulong i, j, n;
997         char *err;
998         uchar *data;
999         long *buf;
1000         Pkb p;
1001
1002         p.ndata = t->ndata;
1003         if((p.data = malloc(p.ndata*sizeof *p.data)) == nil)
1004                 return memerr;
1005         if((buf = malloc((t->bpl+1)*sizeof *buf)) == nil) {
1006                 free(p.data);
1007                 return memerr;
1008         }
1009         p.n = 0;
1010         data = t->data;
1011         for(i = j = n = 0, err = nil; i < t->dy; i++) {
1012                 if((err = pkbrow(&p, data, t->bpl, buf)) != nil)
1013                         break;
1014                 data += t->bpl;
1015                 if(i%t->rows == t->rows-1) {
1016                         t->counts[j++] = p.n - n;
1017                         n = p.n;
1018                 }
1019         }
1020         free(buf);
1021         if(err != nil) {
1022                 if(p.data != nil)
1023                         free(p.data);
1024                 return err;
1025         }
1026         if(j < t->nstrips)
1027                 t->counts[j] = p.n - n;
1028         free(t->data);
1029         t->data = p.data;
1030         t->ndata = p.n;
1031         return nil;
1032 }
1033
1034 static char *
1035 alloctif(Tif *t)
1036 {
1037         int rgb;
1038         ulong i, count, n;
1039
1040         count = t->ndata < 0x2000? t->ndata: 0x2000;
1041         t->rows = (count + t->bpl - 1) / t->bpl;
1042         if(t->comp == Tt4enc && t->opt) {
1043                 if((n = t->rows%Kpar) != 0)
1044                         t->rows += Kpar - n;
1045         }
1046         t->nstrips = (t->dy + t->rows - 1) / t->rows;
1047         t->strips = malloc(t->nstrips*sizeof *t->strips);
1048         if(t->strips == nil)
1049                 return memerr;
1050         t->counts = malloc(t->nstrips*sizeof *t->counts);
1051         if(t->counts == nil) {
1052                 free(t->strips);
1053                 return memerr;
1054         }
1055         if(t->ncolor > 0) {
1056                 t->color = malloc(t->ncolor*sizeof *t->color);
1057                 if(t->color == nil) {
1058                         free(t->strips);
1059                         free(t->counts);
1060                         return memerr;
1061                 }
1062                 for(i = 0; i < 256; i++) {
1063                         rgb = cmap2rgb(i);
1064                         t->color[i] = (rgb >> 16) & 0xff;
1065                         t->color[i+256] = (rgb >> 8) & 0xff;
1066                         t->color[i+256*2] = rgb & 0xff;
1067                 }
1068         }
1069         count = t->rows * t->bpl;
1070         for(i = 0, n = t->ndata; i < t->nstrips-1; i++) {
1071                 t->counts[i] = count;
1072                 n -= count;
1073         }
1074         t->counts[i] = n;
1075         return nil;
1076 }
1077
1078 static void
1079 freetif(Tif *t)
1080 {
1081         free(t->strips);
1082         free(t->counts);
1083         if(t->color != nil)
1084                 free(t->color);
1085         free(t->data);
1086 }
1087
1088 static int
1089 typesize(int fld)
1090 {
1091         return typesizes[flds[fld].typ];
1092 }
1093
1094 static void
1095 writefld(Biobuf *fd, int fld, ulong cnt, ulong val)
1096 {
1097         put2(fd, flds[fld].tag);
1098         put2(fd, flds[fld].typ);
1099         put4(fd, cnt);
1100         put4(fd, val);
1101 }
1102
1103 static void
1104 writeflds(Biobuf *fd, Tif *t)
1105 {
1106         int n;
1107         ulong i, off, slen, s, offs[7];
1108
1109         slen = t->desc == nil? 0: strlen(t->desc) + 1;
1110         put2(fd, 0x4d4d);
1111         put2(fd, 0x002a);
1112         off = 0x00000008;
1113         memset(offs, 0, sizeof offs);
1114         n = 0;
1115         offs[n++] = off;
1116         if(t->samples > 1) {
1117                 off += t->samples * typesize(Tbits);
1118                 offs[n++] = off;
1119         }
1120         if(slen > 4) {
1121                 off += slen * typesize(Tdesc);
1122                 offs[n++] = off;
1123         }
1124         if(t->nstrips > 1) {
1125                 off += t->nstrips * typesize(Tstrips);
1126                 offs[n++] = off;
1127                 off += t->nstrips * typesize(Tcounts);
1128                 offs[n++] = off;
1129         }
1130         off += typesize(Txres);
1131         offs[n++] = off;
1132         off += typesize(Tyres);
1133         offs[n] = off;
1134         if(t->color != nil)
1135                 off += t->ncolor * typesize(Tcolor);
1136         for(i = 0; i < t->nstrips-1; i++) {
1137                 t->strips[i] = off;
1138                 off += t->counts[i];
1139         }
1140         t->strips[i] = off;
1141         off += t->counts[i];
1142         put4(fd, off);
1143         if(t->samples > 1) {
1144                 for(i = 0; i < t->samples; i++)
1145                         put2(fd, t->depth[i]);
1146         }
1147         if(slen > 4) {
1148                 Bwrite(fd, t->desc, slen-1);
1149                 put1(fd, 0x00);
1150         }
1151         if(t->nstrips > 1) {
1152                 for(i = 0; i < t->nstrips; i++)
1153                         put4(fd, t->strips[i]);
1154                 for(i = 0; i < t->nstrips; i++)
1155                         put4(fd, t->counts[i]);
1156         }
1157         put4(fd, t->dx);
1158         put4(fd, 0x00000004);
1159         put4(fd, t->dy);
1160         put4(fd, 0x00000004);
1161         if(t->color != nil) {
1162                 for(i = 0; i < t->ncolor; i++)
1163                         put2(fd, t->color[i]);
1164         }
1165         Bwrite(fd, t->data, t->ndata);
1166         n = 0;
1167         put2(fd, t->nfld);
1168         writefld(fd, Twidth, 1, t->dx);
1169         writefld(fd, Tlength, 1, t->dy);
1170         if(t->samples > 1)
1171                 writefld(fd, Tbits, t->samples, offs[n++]);
1172         else
1173                 writefld(fd, Tbits, t->samples, *t->depth<<16);
1174         writefld(fd, Tcomp, 1, t->comp<<16);
1175         writefld(fd, Tphoto, 1, t->photo<<16);
1176         if(t->comp >= 2 && t->comp <= 4)
1177                 writefld(fd, Tfill, 1, 1<<16);
1178         if(slen > 1) {
1179                 if(slen <= 4) {
1180                         for(i = s = 0; i < slen-1; i++)
1181                                 s = (s << 8) | t->desc[i];
1182                         s <<= 8;
1183                         writefld(fd, Tdesc, slen, s);
1184                 } else
1185                         writefld(fd, Tdesc, slen, offs[n++]);
1186         }
1187         if(t->nstrips > 1)
1188                 writefld(fd, Tstrips, t->nstrips, offs[n++]);
1189         else
1190                 writefld(fd, Tstrips, t->nstrips, *t->strips);
1191         if(t->samples > 1)
1192                 writefld(fd, Tsamples, 1, t->samples<<16);
1193         writefld(fd, Trows, 1, t->rows);
1194         if(t->nstrips > 1)
1195                 writefld(fd, Tcounts, t->nstrips, offs[n++]);
1196         else
1197                 writefld(fd, Tcounts, t->nstrips, *t->counts);
1198         writefld(fd, Txres, 1, offs[n++]);
1199         writefld(fd, Tyres, 1, offs[n++]);
1200         if(t->comp == Tt4enc && t->opt)
1201                 writefld(fd, T4opt, 1, 1);
1202         writefld(fd, Tresunit, 1, 2<<16);
1203         if(t->comp == Tlzw && t->opt)
1204                 writefld(fd, Tpredictor, 1, 2<<16);
1205         if(t->color != nil)
1206                 writefld(fd, Tcolor, t->ncolor, offs[n]);
1207         put4(fd, 0x00000000);
1208 }
1209
1210 static char *
1211 writedata(Biobuf *fd, Image *i, Memimage *m, Tif *t)
1212 {
1213         char *err;
1214         uchar *data;
1215         int j, ndata, depth;
1216         Rectangle r;
1217
1218         if(m != nil) {
1219                 r = m->r;
1220                 depth = m->depth;
1221         } else {
1222                 r = i->r;
1223                 depth = i->depth;
1224         }
1225         t->dx = Dx(r);
1226         t->dy = Dy(r);
1227         for(j = 0; j < t->samples; j++)
1228                 t->depth[j] = depth / t->samples;
1229         /*
1230         * potentially one extra byte on each
1231         * end of each scan line
1232         */
1233         ndata = t->dy * (2 + t->dx*depth/8);
1234         if((data = malloc(ndata)) == nil)
1235                 return memerr;
1236         if(m != nil)
1237                 ndata = unloadmemimage(m, r, data, ndata);
1238         else
1239                 ndata = unloadimage(i, r, data, ndata);
1240         if(ndata < 0) {
1241                 free(data);
1242                 if((err = malloc(ERRMAX*sizeof *err)) == nil)
1243                         return memerr;
1244                 snprint(err, ERRMAX, "WriteTIF: %r");
1245         } else {
1246                 t->data = data;
1247                 t->ndata = ndata;
1248                 t->bpl = bytesperline(r, depth);
1249                 err = alloctif(t);
1250                 if(err != nil) {
1251                         freetif(t);
1252                         return err;
1253                 }
1254                 if((err = (*t->compress)(t)) == nil)
1255                         writeflds(fd, t);
1256                 freetif(t);
1257         }
1258         return err;
1259 }
1260
1261 static char *
1262 writetif0(Biobuf *fd, Image *image, Memimage *memimage,
1263         ulong chan, char *s, int comp, int opt)
1264 {
1265         Tif t;
1266
1267         t.nfld = 11;
1268         t.color = nil;
1269         if((t.desc = s) != nil)
1270                 t.nfld++;
1271         t.opt = opt;
1272         t.comp = comp;
1273         switch(chan) {
1274         case GREY1:
1275         case GREY4:
1276         case GREY8:
1277                 t.photo = 1;
1278                 t.samples = 1;
1279                 t.ncolor = 0;
1280                 break;
1281         case CMAP8:
1282                 t.photo = 3;
1283                 t.samples = 1;
1284                 t.ncolor = 3 * 256;
1285                 t.nfld++;
1286                 break;
1287         case BGR24:
1288                 t.photo = 2;
1289                 t.samples = 3;
1290                 t.ncolor = 0;
1291                 t.nfld++;
1292                 break;
1293         default:
1294                 return "WriteTIF: can't handle channel type";
1295         }
1296         switch(t.comp) {
1297         case Tnocomp:
1298                 t.compress = nocomp;
1299                 break;
1300         case Thuffman:
1301         case Tt4enc:
1302         case Tt6enc:
1303                 t.photo = 0;
1304                 t.nfld++;
1305                 if(t.comp == Tt4enc && t.opt)
1306                         t.nfld++;
1307                 t.compress = fax;
1308                 break;
1309         case Tlzw:
1310                 t.compress = lzw;
1311                 if(t.opt)
1312                         t.nfld++;
1313                 break;
1314         case Tpackbits:
1315                 t.compress = packbits;
1316                 break;
1317         default:
1318                 return "WriteTIF: unknown compression";
1319         }
1320         return writedata(fd, image, memimage, &t);
1321 }
1322
1323 char *
1324 writetif(Biobuf *fd, Image *i, char *s, int comp, int opt)
1325 {
1326         return writetif0(fd, i, nil, i->chan, s, comp, opt);
1327 }
1328
1329 char *
1330 memwritetif(Biobuf *fd, Memimage *m, char *s, int comp, int opt)
1331 {
1332         return writetif0(fd, nil, m, m->chan, s, comp, opt);
1333 }