sys/src/cmd/jpg/writejpg.c

   1 /*
   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
   8 * /sys/src/cmd/jpg
   9 *
  10 * fdct code from:
  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
  13 */
  14 #include <u.h>
  15 #include <libc.h>
  16 #include <draw.h>
  17 #include <memdraw.h>
  18 #include <bio.h>
  19 #include "imagefile.h"
  20
  21 /*
  22 * imported from libdraw/arith.c to permit
  23 * extern log2 function
  24 */
  25 static int log2[] = {
  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
  30 };
  31
  32 /* fdct constants */
  33 enum {
  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 */
  46 };
  47
  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
  57 };
  58
  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
  68 };
  69
  70 /* section K.1 for quantization tables */
  71 static int qt[2][64] = {
  72         /* luminance */
  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},
  81
  82         /* chrominance */
  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}
  91 };
  92
  93 /* section K.3.3 for huffman tables */
  94 static int dcbits[2][16] = {
  95         /* luminance */
  96         {0x00, 0x01, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01,
  97         0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
  98
  99         /* chrominance */
 100         {0x00, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 101         0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00}
 102 };
 103
 104 static int dchuffval[2][12] = {
 105         /* luminance */
 106         {0x00, 0x01, 0x02, 0x03, 0x04, 0x05,
 107         0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b},
 108
 109         /* chrominance */
 110         {0x00, 0x01, 0x02, 0x03, 0x04, 0x05,
 111         0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b}
 112 };
 113
 114 static int acbits[2][16] = {
 115         /* luminance */
 116         {0x00, 0x02, 0x01, 0x03, 0x03, 0x02, 0x04, 0x03,
 117         0x05, 0x05, 0x04, 0x04, 0x00, 0x00, 0x01, 0x7d},
 118
 119         /* chrominance */
 120         {0x00, 0x02, 0x01, 0x02, 0x04, 0x04, 0x03, 0x04,
 121         0x07, 0x05, 0x04, 0x04, 0x00, 0x01, 0x02, 0x77}
 122 };
 123
 124 static int achuffval[2][162] = {
 125         /* luminance */
 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},
 153
 154         /* chrominance */
 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}
 182 };
 183
 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 */
 188
 189 static int byte;
 190 static int nbyte;
 191
 192 /* utilities */
 193 static int Bputs(Biobuf *, int);
 194 static int min(int, int);
 195
 196 /* encoding */
 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,
 206         uchar *, int, int);
 207 static char *toycc2(int *, int *, int *, int, int, int, int, int,
 208         uchar *, int, int);
 209 static char *encode(Biobuf *, Rectangle, uchar *, ulong, int,
 210         int, int);
 211
 212 /* huffman tables */
 213 static void makehuf(int *, int *, int *, int *, int);
 214
 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);
 227
 228 static int
 229 Bputs(Biobuf *b, int s)
 230 {
 231         if(Bputc(b, s>>8) < 0)
 232                 return -1;
 233         return Bputc(b, s);
 234 }
 235
 236 static int
 237 min(int a, int b)
 238 {
 239         return a < b? a: b;
 240 }
 241
 242 static void
 243 grey2rgb(int *r, int *g, int *b, int c, int depth)
 244 {
 245         if(depth == 1) {
 246                 if(c != 0)
 247                         c = 0xff;
 248         } else if(depth == 2)
 249                 c = (c << 6) | (c << 4) | (c << 2) | c;
 250         else
 251                 c = (c << 4) | c;
 252         c = cmap2rgb(c);
 253         *r = (c >> 16) & 0xff;
 254         *g = (c >> 8) & 0xff;
 255         *b = c & 0xff;
 256 }
 257
 258 static void
 259 rgb2ycc(int *y, int *cb, int *cr, int r, int g, int b)
 260 {
 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);
 264 }
 265
 266 /* coefficients remain scaled up by 8 at the end */
 267 static void
 268 fdct(int *b, int sflag)
 269 {
 270         int x, y, z, tmp0, tmp1, tmp2, tmp3;
 271         int tmp10, tmp12, tmp11, tmp13;
 272
 273         /* rows */
 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];
 279
 280                 tmp10 = tmp0 + tmp3;
 281                 tmp12 = tmp0 - tmp3;
 282                 tmp11 = tmp1 + tmp2;
 283                 tmp13 = tmp1 - tmp2;
 284
 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];
 289
 290                 b[y*8+0] = (tmp10 + tmp11 - 8*128) << 2;
 291                 b[y*8+4] = (tmp10 - tmp11) << 2;
 292
 293                 z = (tmp12 + tmp13) * Fix05;
 294                 z += 1 << 10;
 295                 b[y*8+2] = (z + tmp12*Fix07) >> 11;
 296                 b[y*8+6] = (z - tmp13*Fix18) >> 11;
 297
 298                 tmp10 = tmp0 + tmp3;
 299                 tmp11 = tmp1 + tmp2;
 300                 tmp12 = tmp0 + tmp2;
 301                 tmp13 = tmp1 + tmp3;
 302                 z = (tmp12 + tmp13) * Fix11;
 303                 z += 1 << 10;
 304
 305                 tmp0 *= Fix15;
 306                 tmp1 *= Fix30;
 307                 tmp2 *= Fix20;
 308                 tmp3 *= Fix02;
 309                 tmp10 *= -Fix08;
 310                 tmp11 *= -Fix25;
 311                 tmp12 *= -Fix03;
 312                 tmp13 *= -Fix19;
 313
 314                 tmp12 += z;
 315                 tmp13 += z;
 316
 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;
 321         }
 322         /* columns */
 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];
 328
 329                 if(sflag)
 330                         tmp10 = (tmp0 + tmp3 + 1) << 1;
 331                 else
 332                         tmp10 = tmp0 + tmp3 + (1 << 1);
 333                 tmp12 = tmp0 - tmp3;
 334                 tmp11 = tmp1 + tmp2;
 335                 tmp13 = tmp1 - tmp2;
 336
 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];
 341
 342                 b[0*8+x] = (tmp10 + tmp11) >> 2;
 343                 b[4*8+x] = (tmp10 - tmp11) >> 2;
 344
 345                 z = (tmp12 + tmp13) * Fix05;
 346                 z += 1 << 14;
 347                 b[2*8+x] = (z + tmp12*Fix07) >> 15;
 348                 b[6*8+x] = (z - tmp13*Fix18) >> 15;
 349
 350                 tmp10 = tmp0 + tmp3;
 351                 tmp11 = tmp1 + tmp2;
 352                 tmp12 = tmp0 + tmp2;
 353                 tmp13 = tmp1 + tmp3;
 354                 z = (tmp12 + tmp13) * Fix11;
 355                 z += 1 << 14;
 356
 357                 tmp0 *= Fix15;
 358                 tmp1 *= Fix30;
 359                 tmp2 *= Fix20;
 360                 tmp3 *= Fix02;
 361                 tmp10 *= -Fix08;
 362                 tmp11 *= -Fix25;
 363                 tmp12 *= -Fix03;
 364                 tmp13 *= -Fix19;
 365
 366                 tmp12 += z;
 367                 tmp13 += z;
 368
 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;
 373         }
 374 }
 375
 376 static int
 377 csize(int coeff, int ac)
 378 {
 379         int i, max;
 380
 381         max = 1 << 10;
 382         if(!ac)
 383                 max <<= 1;
 384         if(coeff < 0)
 385                 coeff *= -1;
 386         if(coeff > max)
 387                 sysfatal("csize: coeff too big: %d", coeff);
 388         i = ac? 1: 0;
 389         while(coeff >= (1<<i))
 390                 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);
 395         return i;
 396 }
 397
 398 static void
 399 writebyte(Biobuf *fd)
 400 {
 401         Bputc(fd, byte);
 402         if(byte == 0xff) /* byte stuffing */
 403                 Bputc(fd, 0x00);
 404         byte = 0;
 405         nbyte = 7;
 406 }
 407
 408 static void
 409 writebits(Biobuf *fd, int co, int si)
 410 {
 411         int i, bit;
 412
 413         for(i = si-1; i >= 0; i--) {
 414                 bit = (co >> i) & 0x1;
 415                 byte |= bit << nbyte;
 416                 nbyte--;
 417                 if(nbyte < 0)
 418                         writebyte(fd);
 419         }
 420 }
 421
 422 static void
 423 writecode(Biobuf *fd, int co, int si)
 424 {
 425         if(si > 8) {
 426                 writebits(fd, co>>8, si-8);
 427                 si = 8;
 428         }
 429         writebits(fd, co, si);
 430 }
 431
 432 static int
 433 huf(Biobuf *fd, int *b, int pred, int chr, int sflag)
 434 {
 435         int k, r, s, rs, si, co, dc, diff, zz[64], p, q, z;
 436
 437         if(sflag) {
 438                 for(k = 0; k < 64; k++) {
 439                         p = b[zigzag[k]];
 440                         q = qt[chr][zigzag[k]];
 441                         zz[k] = p / q;
 442                 }
 443         } else {
 444                 for(k = 0; k < 64; k++) {
 445                         p = b[k];
 446                         q = (qt[chr][k] << 3);
 447                         /* rounding */
 448                         if(p >= 0)
 449                                 z = (p + (q >> 1)) / q;
 450                         else
 451                                 z = -(-p + (q >> 1)) / q;
 452                         zz[zigzag[k]] = z;
 453                 }
 454         }
 455
 456         /* dc coefficient */
 457         dc = zz[0];
 458         zz[0] = diff = dc - pred;
 459
 460         s = csize(diff, 0);
 461         si = ehufsid[chr][s];
 462         co = ehufcod[chr][s];
 463         writecode(fd, co, si);
 464         if(diff < 0)
 465                 diff -= 1;
 466         writecode(fd, diff, s);
 467
 468         /* figure F.2 */
 469         for(k = 1, r = 0; k < 64; k++) {
 470                 if(zz[k] == 0) {
 471                         if(k < 63)
 472                                 r++;
 473                         else {
 474                                 si = ehufsia[chr][0x00];
 475                                 co = ehufcoa[chr][0x00];
 476                                 writecode(fd, co, si);
 477                         }
 478                 } else {
 479                         while(r > 15) {
 480                                 si = ehufsia[chr][0xf0];
 481                                 co = ehufcoa[chr][0xf0];
 482                                 writecode(fd, co, si);
 483                                 r -= 16;
 484                         }
 485                         /* figure F.3 */
 486                         s = csize(zz[k], 1);
 487                         rs = (r << 4) | s;
 488                         si = ehufsia[chr][rs];
 489                         co = ehufcoa[chr][rs];
 490                         writecode(fd, co, si);
 491                         if(zz[k] < 0)
 492                                 zz[k] -= 1;
 493                         writecode(fd, zz[k], s);
 494                         r = 0;
 495                 }
 496         }
 497         return dc;
 498 }
 499
 500 static char *
 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)
 503 {
 504         int i, j, k, l, m, n, u, v, pos, pmask, nmask, pix;
 505         int r, g, b;
 506
 507         m = 8 / depth;
 508         pmask = (1 << depth) - 1;
 509         nmask = 7 >> log2[depth];
 510         for(i = jy, k = 0; i < jy+8; i++) {
 511                 v = min(i, dy-1);
 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;
 515                         pos = v*bpl + u;
 516                         if(pos >= ndata)
 517                                 return "WriteJPG: overflow";
 518                         /* thanks writeppm */
 519                         pix = (data[pos] >> depth*((nmask - n) &
 520                                 nmask)) & pmask;
 521                         if(((n + 1) & nmask) == 0)
 522                                 j++;
 523                         grey2rgb(&r, &g, &b, pix, depth);
 524                         rgb2ycc(&y[k], &cb[k], &cr[k], r, g, b);
 525                 }
 526         }
 527         return nil;
 528 }
 529
 530 static char *
 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)
 533 {
 534         int i, j, k, m, u, v, pos;
 535
 536         m = depth / 8;
 537         for(i = jy, k = 0; i < jy+8; i++) {
 538                 v = min(i, dy-1);
 539                 for(j = jx*m; j < (jx+8)*m; j+=m, k++) {
 540                         u = min(j, (dx-1)*m);
 541                         pos = v*bpl + u;
 542                         if(pos+m-1 >= ndata)
 543                                 return "WriteJPG: overflow";
 544                         rgb2ycc(&y[k], &cb[k], &cr[k],
 545                                 data[pos+2*m/3],
 546                                 data[pos+m/3],
 547                                 data[pos]);
 548                 }
 549         }
 550         return nil;
 551 }
 552
 553 static char *
 554 encode(Biobuf *fd, Rectangle r, uchar *data, ulong chan,
 555         int ndata, int kflag, int sflag)
 556 {
 557         int k, x, y, dx, dy, depth, bpl, ncomp;
 558         int b[3][64], pred[3];
 559         char *err;
 560         char *(*toycc)(int *, int *, int *, int, int, int, int,
 561                 int, uchar *, int, int);
 562
 563         byte = 0;
 564         nbyte = 7;
 565
 566         switch(chan) {
 567         case GREY1:
 568         case GREY2:
 569         case GREY4:
 570                 toycc = toycc1;
 571                 break;
 572         case GREY8:
 573         case RGB24:
 574                 toycc = toycc2;
 575                 break;
 576         default:
 577                 return "WriteJPG: can't handle channel type";
 578         }
 579
 580         /*
 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.
 585         */
 586         dx = min(Dx(r), 0xffff);
 587         dy = min(Dy(r), 0xffff);
 588         depth = chantodepth(chan);
 589         bpl = bytesperline(r, depth);
 590         ncomp = kflag? 1: 3;
 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);
 595                 if(err != nil)
 596                         return err;
 597                 for(k = 0; k < ncomp; k++) {
 598                         fdct(b[k], sflag);
 599                         pred[k] = huf(fd, b[k], pred[k],
 600                                 k>0, sflag);
 601                 }
 602                 if((x += 8) >= dx) {
 603                         if((y += 8) >= dy)
 604                                 break;
 605                         x = 0;
 606                 }
 607         }
 608         if(nbyte < 7) { /* bit padding */
 609                 for(; nbyte >= 0; nbyte--)
 610                         byte |= 0x1 << nbyte;
 611                 writebyte(fd);
 612         }
 613         return err;
 614 }
 615
 616 static void
 617 makehuf(int *ehufco, int *ehufsi, int *bits, int *huffval, int n)
 618 {
 619         int i, j, k, code, si, lastk, *huffcode, *huffsize;
 620
 621         /* n+1 for lastk */
 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");
 626         /* figure C.1 */
 627         for(k = 0, i = 1, j = 1; i <= 16;) {
 628                 if(j > bits[i-1]) { /* bits[i] in T.81: bug? */
 629                         i++;
 630                         j = 1;
 631                 } else {
 632                         huffsize[k++] = i;
 633                         j++;
 634                 }
 635         }
 636         huffsize[k] = 0;
 637         lastk = k;
 638         /* figure C.2 */
 639         for(k = 0, code = 0, si = huffsize[0];;) {
 640                 do {
 641                         huffcode[k++] = code++;
 642                 } while(huffsize[k] == si);
 643                 if(huffsize[k] == 0)
 644                         break;
 645                 while(huffsize[k] != si) {
 646                         code <<= 1;
 647                         si++;
 648                 }
 649         }
 650         /* figure C.3 */
 651         for(k = 0; k < lastk; k++) {
 652                 i = huffval[k];
 653                 ehufco[i] = huffcode[k];
 654                 ehufsi[i] = huffsize[k];
 655         }
 656         free(huffcode);
 657         free(huffsize);
 658 }
 659
 660 static void
 661 writejfif(Biobuf *fd, int dx, int dy)
 662 {
 663         if(dx > 0xffff || dy > 0xffff)
 664                 sysfatal("writejfif: dx or dy too big");
 665         Bputs(fd, 0xffe0);
 666         Bputs(fd, 0x0010);
 667         Bputc(fd, 0x4a);
 668         Bputc(fd, 0x46);
 669         Bputc(fd, 0x49);
 670         Bputc(fd, 0x46);
 671         Bputc(fd, 0x00);
 672         Bputs(fd, 0x0102);
 673         Bputc(fd, 0x01);
 674         Bputs(fd, dx);
 675         Bputs(fd, dy);
 676         Bputc(fd, 0x00);
 677         Bputc(fd, 0x00);
 678 }
 679
 680 static void
 681 writecomment(Biobuf *fd, char *com)
 682 {
 683         int n;
 684
 685         if(com != nil && com[0] != '\0') {
 686                 n = min(strlen(com)+2, 0xffff);
 687                 Bputs(fd, 0xfffe);
 688                 Bputs(fd, n);
 689                 Bwrite(fd, com, n-2);
 690         }
 691 }
 692
 693 static void
 694 writequant(Biobuf *fd, int tq, int sflag)
 695 {
 696         int i, *p, *q;
 697
 698         if(tq != 0x0 && tq != 0x1)
 699                 sysfatal("writequant: invalid Tq");
 700         q = qt[tq];
 701         Bputs(fd, 0xffdb);
 702         Bputs(fd, 0x0043);
 703         Bputc(fd, (0x0<<4)|tq);
 704         p = sflag? zigzag: invzigzag;
 705         for(i = 0; i < 64; i++)
 706                 Bputc(fd, q[p[i]]);
 707 }
 708
 709 static void
 710 writehuffman(Biobuf *fd, int tc, int th)
 711 {
 712         int i, n, m, *b, *hv;
 713
 714         if((tc != 0x0 && tc != 0x1) || (th != 0x0 && th != 0x1))
 715                 sysfatal("writehuffman: invalid Tc or Th");
 716         n = 0x0013;
 717         if(tc == 0x0) {
 718                 b = dcbits[th];
 719                 hv = dchuffval[th];
 720                 m = nelem(dchuffval[th]);
 721         } else {
 722                 b = acbits[th];
 723                 hv = achuffval[th];
 724                 m = nelem(achuffval[th]);
 725         }
 726         Bputs(fd, 0xffc4);
 727         Bputs(fd, n+m);
 728         Bputc(fd, (tc<<4)|th);
 729         for(i = 0; i < 16; i++)
 730                 Bputc(fd, b[i]);
 731         for(i = 0; i < m; i++)
 732                 Bputc(fd, hv[i]);
 733 }
 734
 735 static void
 736 writeframe(Biobuf *fd, int y, int x, int kflag)
 737 {
 738         int n, nf;
 739
 740         nf = kflag? 0x01: 0x03;
 741         n = 0x0008 + 0x0003*nf;
 742
 743         Bputs(fd, 0xffc0);
 744         Bputs(fd, n);
 745         Bputc(fd, 0x08);
 746         Bputs(fd, y);
 747         Bputs(fd, x);
 748         Bputc(fd, nf);
 749
 750         /* Y component */
 751         Bputc(fd, 0x00);
 752         Bputc(fd, (0x1<<4)|0x1);
 753         Bputc(fd, 0x00);
 754
 755         if(!kflag) {
 756                 /* Cb component */
 757                 Bputc(fd, 0x01);
 758                 Bputc(fd, (0x1<<4)|0x1);
 759                 Bputc(fd, 0x01);
 760
 761                 /* Cr component */
 762                 Bputc(fd, 0x02);
 763                 Bputc(fd, (0x1<<4)|0x1);
 764                 Bputc(fd, 0x01);
 765         }
 766 }
 767
 768 static void
 769 writescan(Biobuf *fd, int kflag)
 770 {
 771         int n, ns;
 772
 773         ns = kflag? 0x01: 0x03;
 774         n = 0x0006 + 0x0002*ns;
 775
 776         Bputs(fd, 0xffda);
 777         Bputs(fd, n);
 778         Bputc(fd, ns);
 779
 780         /* Y component */
 781         Bputc(fd, 0x00);
 782         Bputc(fd, (0x0<<4)|0x0);
 783
 784         if(!kflag) {
 785                 /* Cb component */
 786                 Bputc(fd, 0x01);
 787                 Bputc(fd, (0x1<<4)|0x1);
 788
 789                 /* Cr component */
 790                 Bputc(fd, 0x02);
 791                 Bputc(fd, (0x1<<4)|0x1);
 792         }
 793
 794         Bputc(fd, 0x00);
 795         Bputc(fd, 0x3f);
 796         Bputc(fd, (0x0<<4)|0x0);
 797 }
 798
 799 static void
 800 writeheader(Biobuf *fd, int dx, int dy, char *s, int kflag, int sflag)
 801 {
 802         int i;
 803
 804         dx = min(dx, 0xffff);
 805         dy = min(dy, 0xffff);
 806
 807         Bputs(fd, 0xffd8);
 808         writejfif(fd, dx, dy);
 809         writecomment(fd, s);
 810         writequant(fd, 0, sflag);
 811         if(!kflag)
 812                 writequant(fd, 1, sflag);
 813         writeframe(fd, dy, dx, kflag);
 814         for(i = 0; i < 2; i++) {
 815                 writehuffman(fd, i, 0);
 816                 if(!kflag)
 817                         writehuffman(fd, i, 1);
 818         }
 819         writescan(fd, kflag);
 820 }
 821
 822 static void
 823 writetrailer(Biobuf *fd)
 824 {
 825         Bputs(fd, 0xffd9);
 826 }
 827
 828 static char *
 829 writedata(Biobuf *fd, Image *i, Memimage *m, int kflag, int sflag)
 830 {
 831         char *err;
 832         uchar *data;
 833         int ndata, depth;
 834         ulong chan;
 835         Rectangle r;
 836
 837         if(m != nil) {
 838                 r = m->r;
 839                 depth = m->depth;
 840                 chan = m->chan;
 841         } else {
 842                 r = i->r;
 843                 depth = i->depth;
 844                 chan = i->chan;
 845         }
 846
 847         /*
 848         * potentially one extra byte on each
 849         * end of each scan line
 850         */
 851         ndata = Dy(r) * (2 + Dx(r)*depth/8);
 852         if((data = malloc(ndata)) == nil)
 853                 return "WriteJPG: malloc failed";
 854         if(m != nil)
 855                 ndata = unloadmemimage(m, r, data, ndata);
 856         else
 857                 ndata = unloadimage(i, r, data, ndata);
 858         if(ndata < 0) {
 859                 if((err = malloc(ERRMAX)) == nil) {
 860                         free(data);
 861                         return "WriteJPG: malloc failed";
 862                 }
 863                 snprint(err, ERRMAX, "WriteJPG: %r");
 864         } else
 865                 err = encode(fd, r, data, chan, ndata, kflag, sflag);
 866         free(data);
 867         return err;
 868 }
 869
 870 static char *
 871 writejpg0(Biobuf *fd, Image *image, Memimage *memimage,
 872         Rectangle r, ulong chan, char *s, int kflag, int sflag)
 873 {
 874         int i;
 875         char *err;
 876
 877         switch(chan) {
 878         case GREY1:
 879         case GREY2:
 880         case GREY4:
 881         case GREY8:
 882                 kflag = 1;
 883                 break;
 884         case RGB24:
 885                 break;
 886         default:
 887                 return "WriteJPG: can't handle channel type";
 888         }
 889         for(i = 0; i < 2; i++) {
 890                 memset(ehufcod[i], 0, sizeof ehufcod[i]);
 891                 memset(ehufsid[i], 0, sizeof ehufsid[i]);
 892                 memset(ehufcoa[i], 0, sizeof ehufcoa[i]);
 893                 memset(ehufsia[i], 0, sizeof ehufsia[i]);
 894                 makehuf(ehufcod[i], ehufsid[i], dcbits[i],
 895                         dchuffval[i], nelem(dchuffval[i]));
 896                 makehuf(ehufcoa[i], ehufsia[i], acbits[i],
 897                         achuffval[i], nelem(achuffval[i]));
 898         }
 899         writeheader(fd, Dx(r), Dy(r), s, kflag, sflag);
 900         err = writedata(fd, image, memimage, kflag, sflag);
 901         writetrailer(fd);
 902         return err;
 903 }
 904
 905 char *
 906 writejpg(Biobuf *fd, Image *i, char *s, int kflag, int sflag)
 907 {
 908         return writejpg0(fd, i, nil, i->r, i->chan, s, kflag, sflag);
 909 }
 910
 911 char *
 912 memwritejpg(Biobuf *fd, Memimage *m, char *s, int kflag, int sflag)
 913 {
 914         return writejpg0(fd, nil, m, m->r, m->chan, s, kflag, sflag);
 915 }