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