2 * code/documentation from:
3 * http://www.w3.org/Graphics/JPEG/jfif3.pdf
4 * http://www.w3.org/Graphics/JPEG/itu-t81.pdf
5 * http://en.wikipedia.org/wiki/JPEG
6 * http://en.wikibooks.org/wiki/JPEG_-_Idea_and_Practice
7 * http://code.google.com/p/go/source/browse/src/pkg/image/jpeg/writer.go
11 * http://www.ijg.org/files/jpegsrc.v8c.tar.gz
12 * http://code.google.com/p/go/source/browse/src/pkg/image/jpeg/fdct.go
19 #include "imagefile.h"
22 * imported from libdraw/arith.c to permit
23 * extern log2 function
26 -1, 0, 1, -1, 2, -1, -1, -1, 3,
27 -1, -1, -1, -1, -1, -1, -1, 4,
28 -1, -1, -1, -1, -1, -1, -1, 4 /* BUG */,
29 -1, -1, -1, -1, -1, -1, -1, 5
34 Fix02 = 2446, /* 0.298631336 */
35 Fix03 = 3196, /* 0.390180644 */
36 Fix05 = 4433, /* 0.541196100 */
37 Fix07 = 6270, /* 0.765366865 */
38 Fix08 = 7373, /* 0.899976223 */
39 Fix11 = 9633, /* 1.175875602 */
40 Fix15 = 12299, /* 1.501321110 */
41 Fix18 = 15137, /* 1.847759065 */
42 Fix19 = 16069, /* 1.961570560 */
43 Fix20 = 16819, /* 2.053119869 */
44 Fix25 = 20995, /* 2.562915447 */
45 Fix30 = 25172 /* 3.072711026 */
48 static int zigzag[64] = {
49 0, 1, 5, 6, 14, 15, 27, 28,
50 2, 4, 7, 13, 16, 26, 29, 42,
51 3, 8, 12, 17, 25, 30, 41, 43,
52 9, 11, 18, 24, 31, 40, 44, 53,
53 10, 19, 23, 32, 39, 45, 52, 54,
54 20, 22, 33, 38, 46, 51, 55, 60,
55 21, 34, 37, 47, 50, 56, 59, 61,
56 35, 36, 48, 49, 57, 58, 62, 63
59 static int invzigzag[64] = {
60 0, 1, 8, 16, 9, 2, 3, 10,
61 17, 24, 32, 25, 18, 11, 4, 5,
62 12, 19, 26, 33, 40, 48, 41, 34,
63 27, 20, 13, 6, 7, 14, 21, 28,
64 35, 42, 49, 56, 57, 50, 43, 36,
65 29, 22, 15, 23, 30, 37, 44, 51,
66 58, 59, 52, 45, 38, 31, 39, 46,
67 53, 60, 61, 54, 47, 55, 62, 63
70 /* section K.1 for quantization tables */
71 static int qt[2][64] = {
73 {16, 11, 10, 16, 24, 40, 51, 61,
74 12, 12, 14, 19, 26, 58, 60, 55,
75 14, 13, 16, 24, 40, 57, 69, 56,
76 14, 17, 22, 29, 51, 87, 80, 62,
77 18, 22, 37, 56, 68, 109, 103, 77,
78 24, 35, 55, 64, 81, 104, 113, 92,
79 49, 64, 78, 87, 103, 121, 120, 101,
80 72, 92, 95, 98, 112, 100, 103, 99},
83 {17, 18, 24, 47, 99, 99, 99, 99,
84 18, 21, 26, 66, 99, 99, 99, 99,
85 24, 26, 56, 99, 99, 99, 99, 99,
86 47, 66, 99, 99, 99, 99, 99, 99,
87 99, 99, 99, 99, 99, 99, 99, 99,
88 99, 99, 99, 99, 99, 99, 99, 99,
89 99, 99, 99, 99, 99, 99, 99, 99,
90 99, 99, 99, 99, 99, 99, 99, 99}
93 /* section K.3.3 for huffman tables */
94 static int dcbits[2][16] = {
96 {0x00, 0x01, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01,
97 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
100 {0x00, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
101 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00}
104 static int dchuffval[2][12] = {
106 {0x00, 0x01, 0x02, 0x03, 0x04, 0x05,
107 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b},
110 {0x00, 0x01, 0x02, 0x03, 0x04, 0x05,
111 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b}
114 static int acbits[2][16] = {
116 {0x00, 0x02, 0x01, 0x03, 0x03, 0x02, 0x04, 0x03,
117 0x05, 0x05, 0x04, 0x04, 0x00, 0x00, 0x01, 0x7d},
120 {0x00, 0x02, 0x01, 0x02, 0x04, 0x04, 0x03, 0x04,
121 0x07, 0x05, 0x04, 0x04, 0x00, 0x01, 0x02, 0x77}
124 static int achuffval[2][162] = {
126 {0x01, 0x02, 0x03, 0x00, 0x04, 0x11,
127 0x05, 0x12, 0x21, 0x31, 0x41, 0x06,
128 0x13, 0x51, 0x61, 0x07, 0x22, 0x71,
129 0x14, 0x32, 0x81, 0x91, 0xa1, 0x08,
130 0x23, 0x42, 0xb1, 0xc1, 0x15, 0x52,
131 0xd1, 0xf0, 0x24, 0x33, 0x62, 0x72,
132 0x82, 0x09, 0x0a, 0x16, 0x17, 0x18,
133 0x19, 0x1a, 0x25, 0x26, 0x27, 0x28,
134 0x29, 0x2a, 0x34, 0x35, 0x36, 0x37,
135 0x38, 0x39, 0x3a, 0x43, 0x44, 0x45,
136 0x46, 0x47, 0x48, 0x49, 0x4a, 0x53,
137 0x54, 0x55, 0x56, 0x57, 0x58, 0x59,
138 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67,
139 0x68, 0x69, 0x6a, 0x73, 0x74, 0x75,
140 0x76, 0x77, 0x78, 0x79, 0x7a, 0x83,
141 0x84, 0x85, 0x86, 0x87, 0x88, 0x89,
142 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96,
143 0x97, 0x98, 0x99, 0x9a, 0xa2, 0xa3,
144 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9,
145 0xaa, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6,
146 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3,
147 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9,
148 0xca, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6,
149 0xd7, 0xd8, 0xd9, 0xda, 0xe1, 0xe2,
150 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8,
151 0xe9, 0xea, 0xf1, 0xf2, 0xf3, 0xf4,
152 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa},
155 {0x00, 0x01, 0x02, 0x03, 0x11, 0x04,
156 0x05, 0x21, 0x31, 0x06, 0x12, 0x41,
157 0x51, 0x07, 0x61, 0x71, 0x13, 0x22,
158 0x32, 0x81, 0x08, 0x14, 0x42, 0x91,
159 0xa1, 0xb1, 0xc1, 0x09, 0x23, 0x33,
160 0x52, 0xf0, 0x15, 0x62, 0x72, 0xd1,
161 0x0a, 0x16, 0x24, 0x34, 0xe1, 0x25,
162 0xf1, 0x17, 0x18, 0x19, 0x1a, 0x26,
163 0x27, 0x28, 0x29, 0x2a, 0x35, 0x36,
164 0x37, 0x38, 0x39, 0x3a, 0x43, 0x44,
165 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a,
166 0x53, 0x54, 0x55, 0x56, 0x57, 0x58,
167 0x59, 0x5a, 0x63, 0x64, 0x65, 0x66,
168 0x67, 0x68, 0x69, 0x6a, 0x73, 0x74,
169 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a,
170 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
171 0x88, 0x89, 0x8a, 0x92, 0x93, 0x94,
172 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a,
173 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
174 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4,
175 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
176 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
177 0xc8, 0xc9, 0xca, 0xd2, 0xd3, 0xd4,
178 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda,
179 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
180 0xe8, 0xe9, 0xea, 0xf2, 0xf3, 0xf4,
181 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa}
184 static int ehufcod[2][12]; /* dc codes */
185 static int ehufsid[2][12]; /* dc sizes */
186 static int ehufcoa[2][251]; /* ac codes */
187 static int ehufsia[2][251]; /* ac sizes */
193 static int Bputs(Biobuf *, int);
194 static int min(int, int);
197 static void grey2rgb(int *, int *, int *, int, int);
198 static void rgb2ycc(int *, int *, int *, int, int, int);
199 static void fdct(int *, int);
200 static int csize(int, int);
201 static void writebyte(Biobuf *);
202 static void writebits(Biobuf *, int, int);
203 static void writecode(Biobuf *, int, int);
204 static int huf(Biobuf *, int *, int, int, int);
205 static char *toycc1(int *, int *, int *, int, int, int, int, int,
207 static char *toycc2(int *, int *, int *, int, int, int, int, int,
209 static char *encode(Biobuf *, Rectangle, uchar *, ulong, int,
213 static void makehuf(int *, int *, int *, int *, int);
215 /* tables, markers, headers, trailers */
216 static void writejfif(Biobuf *, int, int);
217 static void writecomment(Biobuf *, char *);
218 static void writequant(Biobuf *, int, int);
219 static void writehuffman(Biobuf *, int, int);
220 static void writeframe(Biobuf *, int, int, int);
221 static void writescan(Biobuf *, int);
222 static void writeheader(Biobuf *, int, int, char *, int, int);
223 static void writetrailer(Biobuf *);
224 static char *writedata(Biobuf *, Image *, Memimage *, int, int);
225 static char *writejpg0(Biobuf *, Image *, Memimage *,
226 Rectangle, ulong, char *, int, int);
229 Bputs(Biobuf *b, int s)
231 if(Bputc(b, s>>8) < 0)
243 grey2rgb(int *r, int *g, int *b, int c, int depth)
248 } else if(depth == 2)
249 c = (c << 6) | (c << 4) | (c << 2) | c;
253 *r = (c >> 16) & 0xff;
254 *g = (c >> 8) & 0xff;
259 rgb2ycc(int *y, int *cb, int *cr, int r, int g, int b)
261 *y = (int)(0.299*r + 0.587*g + 0.114*b);
262 *cb = (int)(128.0 - 0.1687*r - 0.3313*g + 0.5*b);
263 *cr = (int)(128.0 + 0.5*r - 0.4187*g - 0.0813*b);
266 /* coefficients remain scaled up by 8 at the end */
268 fdct(int *b, int sflag)
270 int x, y, z, tmp0, tmp1, tmp2, tmp3;
271 int tmp10, tmp12, tmp11, tmp13;
274 for(y = 0; y < 8; y++) {
275 tmp0 = b[y*8+0] + b[y*8+7];
276 tmp1 = b[y*8+1] + b[y*8+6];
277 tmp2 = b[y*8+2] + b[y*8+5];
278 tmp3 = b[y*8+3] + b[y*8+4];
285 tmp0 = b[y*8+0] - b[y*8+7];
286 tmp1 = b[y*8+1] - b[y*8+6];
287 tmp2 = b[y*8+2] - b[y*8+5];
288 tmp3 = b[y*8+3] - b[y*8+4];
290 b[y*8+0] = (tmp10 + tmp11 - 8*128) << 2;
291 b[y*8+4] = (tmp10 - tmp11) << 2;
293 z = (tmp12 + tmp13) * Fix05;
295 b[y*8+2] = (z + tmp12*Fix07) >> 11;
296 b[y*8+6] = (z - tmp13*Fix18) >> 11;
302 z = (tmp12 + tmp13) * Fix11;
317 b[y*8+1] = (tmp0 + tmp10 + tmp12) >> 11;
318 b[y*8+3] = (tmp1 + tmp11 + tmp13) >> 11;
319 b[y*8+5] = (tmp2 + tmp11 + tmp12) >> 11;
320 b[y*8+7] = (tmp3 + tmp10 + tmp13) >> 11;
323 for(x = 0; x < 8; x++) {
324 tmp0 = b[0*8+x] + b[7*8+x];
325 tmp1 = b[1*8+x] + b[6*8+x];
326 tmp2 = b[2*8+x] + b[5*8+x];
327 tmp3 = b[3*8+x] + b[4*8+x];
330 tmp10 = (tmp0 + tmp3 + 1) << 1;
332 tmp10 = tmp0 + tmp3 + (1 << 1);
337 tmp0 = b[0*8+x] - b[7*8+x];
338 tmp1 = b[1*8+x] - b[6*8+x];
339 tmp2 = b[2*8+x] - b[5*8+x];
340 tmp3 = b[3*8+x] - b[4*8+x];
342 b[0*8+x] = (tmp10 + tmp11) >> 2;
343 b[4*8+x] = (tmp10 - tmp11) >> 2;
345 z = (tmp12 + tmp13) * Fix05;
347 b[2*8+x] = (z + tmp12*Fix07) >> 15;
348 b[6*8+x] = (z - tmp13*Fix18) >> 15;
354 z = (tmp12 + tmp13) * Fix11;
369 b[1*8+x] = (tmp0 + tmp10 + tmp12) >> 15;
370 b[3*8+x] = (tmp1 + tmp11 + tmp13) >> 15;
371 b[5*8+x] = (tmp2 + tmp11 + tmp12) >> 15;
372 b[7*8+x] = (tmp3 + tmp10 + tmp13) >> 15;
377 csize(int coeff, int ac)
387 sysfatal("csize: coeff too big: %d", coeff);
389 while(coeff >= (1<<i))
391 if(ac && (i < 1 || i > 10))
392 sysfatal("csize: invalid ac ssss: %d", i);
393 if(!ac && (i < 0 || i > 11))
394 sysfatal("csize: invalid dc ssss: %d", i);
399 writebyte(Biobuf *fd)
402 if(byte == 0xff) /* byte stuffing */
409 writebits(Biobuf *fd, int co, int si)
413 for(i = si-1; i >= 0; i--) {
414 bit = (co >> i) & 0x1;
415 byte |= bit << nbyte;
423 writecode(Biobuf *fd, int co, int si)
426 writebits(fd, co>>8, si-8);
429 writebits(fd, co, si);
433 huf(Biobuf *fd, int *b, int pred, int chr, int sflag)
435 int k, r, s, rs, si, co, dc, diff, zz[64], p, q, z;
438 for(k = 0; k < 64; k++) {
440 q = qt[chr][zigzag[k]];
444 for(k = 0; k < 64; k++) {
446 q = (qt[chr][k] << 3);
449 z = (p + (q >> 1)) / q;
451 z = -(-p + (q >> 1)) / q;
458 zz[0] = diff = dc - pred;
461 si = ehufsid[chr][s];
462 co = ehufcod[chr][s];
463 writecode(fd, co, si);
466 writecode(fd, diff, s);
469 for(k = 1, r = 0; k < 64; k++) {
474 si = ehufsia[chr][0x00];
475 co = ehufcoa[chr][0x00];
476 writecode(fd, co, si);
480 si = ehufsia[chr][0xf0];
481 co = ehufcoa[chr][0xf0];
482 writecode(fd, co, si);
488 si = ehufsia[chr][rs];
489 co = ehufcoa[chr][rs];
490 writecode(fd, co, si);
493 writecode(fd, zz[k], s);
501 toycc1(int *y, int *cb, int *cr, int jx, int jy, int dx, int dy,
502 int bpl, uchar *data, int ndata, int depth)
504 int i, j, k, l, m, n, u, v, pos, pmask, nmask, pix;
508 pmask = (1 << depth) - 1;
509 nmask = 7 >> log2[depth];
510 for(i = jy, k = 0; i < jy+8; i++) {
512 for(l = 0, j = jx/m; l < 8; l++, k++) {
513 u = min(j, (dx-1)/m);
514 n = l+jx >= dx? dx-jx-1: l;
517 return "WriteJPG: overflow";
518 /* thanks writeppm */
519 pix = (data[pos] >> depth*((nmask - n) &
521 if(((n + 1) & nmask) == 0)
523 grey2rgb(&r, &g, &b, pix, depth);
524 rgb2ycc(&y[k], &cb[k], &cr[k], r, g, b);
531 toycc2(int *y, int *cb, int *cr, int jx, int jy, int dx, int dy,
532 int bpl, uchar *data, int ndata, int depth)
534 int i, j, k, m, u, v, pos;
537 for(i = jy, k = 0; i < jy+8; i++) {
539 for(j = jx*m; j < (jx+8)*m; j+=m, k++) {
540 u = min(j, (dx-1)*m);
543 return "WriteJPG: overflow";
544 rgb2ycc(&y[k], &cb[k], &cr[k],
554 encode(Biobuf *fd, Rectangle r, uchar *data, ulong chan,
555 int ndata, int gflag, int sflag)
557 int k, x, y, dx, dy, depth, bpl, ncomp;
558 int b[3][64], pred[3];
560 char *(*toycc)(int *, int *, int *, int, int, int, int,
561 int, uchar *, int, int);
577 return "WriteJPG: can't handle channel type";
581 * if dx or dy is not a multiple of 8,
582 * the decoder should continue until reaching
583 * the last mcu, even if the extra pixels go beyond
584 * 0xffff. they are not shown anyway.
586 dx = min(Dx(r), 0xffff);
587 dy = min(Dy(r), 0xffff);
588 depth = chantodepth(chan);
589 bpl = bytesperline(r, depth);
591 memset(pred, 0, sizeof pred);
592 for(x = 0, y = 0;;) {
593 err = (*toycc)(b[0], b[1], b[2], x, y, dx, dy,
594 bpl, data, ndata, depth);
597 for(k = 0; k < ncomp; k++) {
599 pred[k] = huf(fd, b[k], pred[k],
608 if(nbyte < 7) { /* bit padding */
609 for(; nbyte >= 0; nbyte--)
610 byte |= 0x1 << nbyte;
617 makehuf(int *ehufco, int *ehufsi, int *bits, int *huffval, int n)
619 int i, j, k, code, si, lastk, *huffcode, *huffsize;
622 if((huffcode = malloc((n+1)*sizeof *huffcode)) == nil)
623 sysfatal("malloc: %r");
624 if((huffsize = malloc((n+1)*sizeof *huffsize)) == nil)
625 sysfatal("malloc: %r");
627 for(k = 0, i = 1, j = 1; i <= 16;) {
628 if(j > bits[i-1]) { /* bits[i] in T.81: bug? */
639 for(k = 0, code = 0, si = huffsize[0];;) {
641 huffcode[k++] = code++;
642 } while(huffsize[k] == si);
645 while(huffsize[k] != si) {
651 for(k = 0; k < lastk; k++) {
653 ehufco[i] = huffcode[k];
654 ehufsi[i] = huffsize[k];
661 writejfif(Biobuf *fd, int dx, int dy)
663 if(dx > 0xffff || dy > 0xffff)
664 sysfatal("writejfif: dx or dy too big");
681 writecomment(Biobuf *fd, char *com)
685 if(com != nil && com[0] != '\0') {
686 n = min(strlen(com)+2, 0xffff);
689 Bwrite(fd, com, n-2);
694 writequant(Biobuf *fd, int tq, int sflag)
698 if(tq != 0x0 && tq != 0x1)
699 sysfatal("writequant: invalid Tq");
703 Bputc(fd, (0x0<<4)|tq);
704 p = sflag? zigzag: invzigzag;
705 for(i = 0; i < 64; i++)
710 writehuffman(Biobuf *fd, int tc, int th)
712 int i, n, m, *b, *hv;
714 if((tc != 0x0 && tc != 0x1) || (th != 0x0 && th != 0x1))
715 sysfatal("writehuffman: invalid Tc or Th");
720 m = nelem(dchuffval[th]);
724 m = nelem(achuffval[th]);
728 Bputc(fd, (tc<<4)|th);
729 for(i = 0; i < 16; i++)
731 for(i = 0; i < m; i++)
736 writeframe(Biobuf *fd, int y, int x, int gflag)
740 nf = gflag? 0x01: 0x03;
741 n = 0x0008 + 0x0003*nf;
752 Bputc(fd, (0x1<<4)|0x1);
758 Bputc(fd, (0x1<<4)|0x1);
763 Bputc(fd, (0x1<<4)|0x1);
769 writescan(Biobuf *fd, int gflag)
773 ns = gflag? 0x01: 0x03;
774 n = 0x0006 + 0x0002*ns;
782 Bputc(fd, (0x0<<4)|0x0);
787 Bputc(fd, (0x1<<4)|0x1);
791 Bputc(fd, (0x1<<4)|0x1);
796 Bputc(fd, (0x0<<4)|0x0);
800 writeheader(Biobuf *fd, int dx, int dy, char *s, int gflag, int sflag)
804 dx = min(dx, 0xffff);
805 dy = min(dy, 0xffff);
808 writejfif(fd, dx, dy);
810 writequant(fd, 0, sflag);
812 writequant(fd, 1, sflag);
813 writeframe(fd, dy, dx, gflag);
814 for(i = 0; i < 2; i++) {
815 writehuffman(fd, i, 0);
817 writehuffman(fd, i, 1);
819 writescan(fd, gflag);
823 writetrailer(Biobuf *fd)
830 writedata(Biobuf *fd, Image *i, Memimage *m, int gflag, int sflag)
849 * potentially one extra byte on each
850 * end of each scan line
852 ndata = Dy(r) * (2 + Dx(r)*depth/8);
853 if((data = malloc(ndata)) == nil)
854 return "WriteJPG: malloc failed";
856 ndata = unloadmemimage(m, r, data, ndata);
858 ndata = unloadimage(i, r, data, ndata);
860 if((err = malloc(ERRMAX)) == nil)
861 return "WriteJPG: malloc failed";
862 snprint(err, ERRMAX, "WriteJPG: %r");
864 err = encode(fd, r, data, chan, ndata, gflag, sflag);
870 writejpg0(Biobuf *fd, Image *image, Memimage *memimage,
871 Rectangle r, ulong chan, char *s, int gflag, int sflag)
884 return "WriteJPG: can't handle channel type";
886 for(i = 0; i < 2; i++) {
887 memset(ehufcod[i], 0, sizeof ehufcod[i]);
888 memset(ehufsid[i], 0, sizeof ehufsid[i]);
889 memset(ehufcoa[i], 0, sizeof ehufcoa[i]);
890 memset(ehufsia[i], 0, sizeof ehufsia[i]);
891 makehuf(ehufcod[i], ehufsid[i], dcbits[i],
892 dchuffval[i], nelem(dchuffval[i]));
893 makehuf(ehufcoa[i], ehufsia[i], acbits[i],
894 achuffval[i], nelem(achuffval[i]));
896 writeheader(fd, Dx(r), Dy(r), s, gflag, sflag);
897 err = writedata(fd, image, memimage, gflag, sflag);
903 writejpg(Biobuf *fd, Image *i, char *s, int gflag, int sflag)
905 return writejpg0(fd, i, nil, i->r, i->chan, s, gflag, sflag);
909 memwritejpg(Biobuf *fd, Memimage *m, char *s, int gflag, int sflag)
911 return writejpg0(fd, nil, m, m->r, m->chan, s, gflag, sflag);